Содержание

 

Введение

1. Эволюция в природе

1.1 Естественный отбор

1.2 Задачи оптимизации

2. Генетический алгоритм

2.1 История развития ГА

2.2 Общий вид генетического алгоритма

2.3 Генетические операторы

2.4 Достоинства и недостатки стандартных и генетических методов

3. Влияние параметров генетического алгоритма на

эффективность поиска

3.1 Операторы кроссовера и мутации

3.2 Выбор родительской пары

3.3 Механизм отбора

4. Наиболее актуальные проблемы ГА и интересные модификации ГА

5. Пример ГА: Решение Диофантова уравнения

5.1. Заголовок класса

5.2 Функция Fitness

5.3 Функция Likelihood

5.4 Функции Breeding

5.5 Функция Solve

5.6 Функция Main

Заключение

Список использованной литературы

Приложение «Текст main.cpp

Приложение Б «Текст Diophantine.h

Введение

 

Идея генетических алгоритмов заимствована у живой природы и состоит в организации эволюционного процесса, конечной целью которого является получение оптимального решения в сложной комбинаторной задаче. Разработчик генетических алгоритмов выступает в данном случае как "создатель", который должен правильно установить законы эволюции, чтобы достичь желаемой цели как можно быстрее.

Поскольку качество решения обычно оценивается некоторой оценочной функцией, ГА также называют методом оптимизации многоэкстремальных функций. Никакой дополнительной информации о решаемой задаче ГА больше не имеет. В процессе эволюции популяция вырабатывает качества, необходимые для выживания и приспособления, и которые одновременно и являются оптимальным решением.

На сегодняшний день генетические алгоритмы доказали свою конкурентоспособность при решении многих NP-трудных задач и особенно в практических приложениях, где математические модели имеют сложную структуру и применение стандартных методов типа ветвей и границ, динамического или линейного программирования крайне затруднено. Они позволяют решать задачи прогнозирования, классификации, поиска оптимальных вариантов, и совершенно незаменимы в тех случаях, когда в обычных условиях решение задачи основано на интуиции или опыте, а не на строгом (в математическом смысле) ее описании.

Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде. Представим себе искусственный мир, населенный множеством существ (особей), причем каждое существо — это некоторое решение нашей задачи. Будем считать особь тем более приспособленной, чем лучше соответствующее решение (чем большее значение целевой функции оно дает). Тогда задача максимизации целевой функции сводится к поиску наиболее приспособленного существа. Конечно, мы не можем поселить в наш виртуальный мир все существа сразу, так как их очень много. Вместо этого мы будем рассматривать много поколений, сменяющих друг друга. Теперь, если мы сумеем ввести в действие естественный отбор и генетическое наследование, то полученный мир будет подчиняться законам эволюции. Заметим, что, в соответствии с нашим определением приспособленности, целью этой искусственной эволюции будет как раз создание наилучших решений. ............