Поиск в одномерном пространстве, без скрещивания.
# include.
# include.
# include.
int main ().
{.
using namespace std;
srand ((unsigned)time (NULL));
const int N = 1000;
int a[N];
//заполняем нулями.
fill (a, a+N, 0);
for (;;).
{.
//мутация в случайную сторону каждого элемента:
for (int i = 0; i < N; ++i).
if (rand ()%2 == 1).
a[i] += 1;
else.
a[i] -= 1;
//теперь выбираем лучших, отсортировав по возрастанию…
sort (a, a+N);
//… и тогда лучшие окажутся во второй половине массива.
//скопируем лучших в первую половину, куда они оставили потомство, а первые умерли:
copy (a+N/2, a+N, a /*куда*/);
//теперь посмотрим на среднее состояние популяции. Как видим, оно всё лучше и лучше.
cout << accumulate (a, a+N, 0) / N << endl;
}.
}.
Литература
- 1. Александров Д. А. Алгоритм муравьиной колонии для задачи о минимальном покрытии. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т3 (1998), Иркутск, с. 17−20.
- 2. Береснев В. Л., Гимади Э. Х., Дементьев В. Т. Экстремальные задачи стандартизации. Новосибирск: Наука, 1978.
- 3. Гончаров Е. Н., Кочетов Ю. А. Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения. Дискретный анализ и исследование операций. Сер. 2. т6 (1999), № 1, с. 12−32.
- 4. Горбачевская Л. Е., Кочетов Ю. А. Вероятностная эвристика для двухуровневой задачи размещения. XI междунар. Байкальская школа-семинар Методы оптимизации и их приложения, Труды, т1 (1998), Иркутск, с. 249−252.
- 5. Гэри В., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
- 6. Еремеев А. В. Разработка и анализ генетических и гибридных алгоритмов для решения задач дискретной оптимизации. Дисс. канд.физ.-мат.наук. Омск, 2000.
- 7. Растригин Л. А. Случайный поиск — специфика, этапы истории и предрассудки. Вопросы кибернетики. Вып. 33 (1978), с. 3−16.
- 8. Aggarwal C. C., Orlin J. B., Tai R. P. Optimized crossover for maximum independent set. Oper. Res. v45 (1997), pp 225−234.
- 9. Balas E., Niehaus W. Finding large cliques in arbitrary graphs by bipartite matching. Cliques, coloring, and satisfiability. DIMACS Ser. Discrete Math. Theoret. Comput. Sci. v26 (1996), pp 29−49.
- 10. Balas E., Niehaus W. Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems. J. Heuristics. v4 (1998), N4, pp 107−122.
- 11. Boese K. D., Kahng A. B., Muddu S. A new adaptive multi-start technique for combinatorial global optimizations. Oper. Res. Lett. v16 (1994), N2, pp 101−114.
- 12. Bremermann H. J., Roghson J., Salaff S. Global properties of evolution processes. Natural automata and useful simulations. London: Macmillan. 1966. pp 3−42.
