Генетический алгоритм - Контрольная работа

Генетический алгоритм (англ. genetic algorithm) - это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путем случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию .«Отцом-основателем» генетических алгоритмов считается Джон Холланд (en:John Henry Holland ), книга которого «Адаптация в естественных и искусственных системах» (1975)[1] является основополагающим трудом в этой области исследований. Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. На сегодняшний день генетические алгоритмы доказали свою конкурентноспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено. Как мы увидим ниже, выбор начальной популяции не имеет значения для сходимости процесса в асимптотике, однако формирование "хорошей" начальной популяции (например из множества локальных оптимумов) может заметно сократить время достижения глобального оптимума. Затем решение добавляется в популяцию, а решение с наименьшим значением целевой функции удаляется из популяции.Задача формализуется таким образом, чтобы ее решение могло быть закодировано в виде вектора («генотипа ») генов. В классических реализациях ГА предполагается, что генотип имеет фиксированную длину. Они оцениваются с использованием «функции приспособленности», в результате чего с каждым генотипом ассоциируется определенное значение («приспособленность»), которое определяет насколько хорошо фенотип им описываемый решает поставленную задачу. Из полученного множества решений («поколения») с учетом значения «приспособленности» выбираются решения (обычно лучшие особи имеют большую вероятность быть выбранными), к которым применяются «генетические операторы» (в большинстве случаев «скрещивание » - crossover и «мутация » - mutation), результатом чего является получение новых решений. Этот набор действий повторяется итеративно, так моделируется «эволюционный процесс», продолжающийся несколько жизненных циклов (поколений), пока не будет выполнен критерий остановки алгоритма.Перед первым шагом нужно случайным образом создать начальную популяцию; даже если она окажется совершенно неконкурентоспособной, генетический алгоритм все равно достаточно быстро переведет ее в жизнеспособную популяцию. Таким образом, на первом шаге можно особенно не стараться сделать слишком уж приспособленных особей, достаточно, чтобы они соответствовали формату особей популяции, и на них можно было подсчитать функцию приспособленности (Fitness). Итогом первого шага является популяция H, состоящая из N особей.К мутациям относится все то же самое, что и к размножению: есть некоторая доля мутантов m, являющаяся параметром генетического алгоритма, и на шаге мутаций нужно выбрать MN особей, а затем изменить их в соответствии с заранее определенными операциями мутации.На этапе отбора нужно из всей популяции выбрать определенную ее долю, которая останется «в живых» на этом этапе эволюции. Вероятность выживания особи h должна зависеть от значения функции приспособленности Fitness(h).Генетические алгоритмы применяются для решения следующих задач: 1. Генетические алгоритмы: Учебное пособие. Нейронные сети, генетические алгоритмы и нечеткие системы = Sieci neuronowe, algorytmy genetyczne i systemy rozmyte. -Проект CUBERGA расширяемый framework для реализации генетических алгоритмов ·-JAGA (Java API for Genetic Algorithms) Extensible and pluggable open source API for implementing genetic algorithms and genetic programming applications in Java (англ.

Содержание

1 История

2 Описание алгоритма

2.1 Создание начальной популяции

2.2 Размножение (Скрещивание)

2.3 Мутации

2.4 Отбор

3 Применение генетических алгоритмов

4 Пример тривиальной реализации на C

Примечания

Книги

Ссылки

Литература

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.