Генетический алгоритм и его сущность

Содержание.

Введение…………………………………………………………………..2

Описание Генетического  Алгоритма……………………………………3

Результаты тестирования………………………………………………...6

Заключение………………………………………………………………11

Список литературы………………………………………………………13

Приложение………………………………………………………………14 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение.

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

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

     Меня  очень заинтересовали генетические алгоритмы, т.к. ранее я не встречалась с алгоритмами решающими практически любую оптимизационную задачу. Целью моей работы было рассмотреть различные модификации алгоритма на тестовых функциях и проанализировать, при какой модификации алгоритм для всех тестовых функций показывает хорошие результаты. 
 
 

Описание  Генетического Алгоритма.

Генетический  алгоритм- это метод поиска решений  практически любой оптимизационной  задачи, моделирующий процессы природной  эволюции.

Генетический  алгоритм состоит из нескольких этапов:

1. Инициализация
2. Выращивание
3. Оценивание
4. Селекция
5. Скрещивание
6. Мутация

Рассмотрим каждый из этих этапов подробно.

        На первом этапе (Инициализация) случайным образом выбирается первоначальная популяция хромосом (генотипов). Хромосома состоит из генов, которые задаются в бинарном виде, и это является отличительной чертой генетических алгоритмов. Прежде чем проводить Инициализацию, требуется посчитать длину хромосом (количество генов), которые будут использоваться. Длина зависит от количества переменных и области допустимых значений. 

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

      Следующий этап это Оценивание. Он подразумевает вычисление значений функции пригодности индивидов (качества решений-кандидатов). 

     Селекция  - во время этого шага  выбираются особи из текущей популяции и заносятся в популяцию родителей, из которых в свою очередь отбирается  пара индивидов, которые, в конце концов, будут скрещиваться (важно заметить, что всё это происходит случайным образом). Для имитации естественной селекции индивиды с более высокой пригодностью должны выбираться с большей вероятностью. Существует большое число различных видов селекции.

1. Турнирная селекция. Для отбора индивида создается группа из N  (N ³ 2) индивидов, выбранных случайным образом. Индивид с наибольшей пригодностью в группе отбирается, остальные - отбрасываются (турнир). N- размер турнира. Преимущества турнирной селекции заключаются в том, что нет преждевременной сходимости, нет стагнации, не требуется явное вычисление функции пригодности. Более того турнирная селекция имеет глубокие аналоги в биологии.

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

     Пятый этап называется Скрещивание. Оно также бывает нескольких видов.

1. При Одноточечном скрещивании случайным образом выбирается точка разрыва родительской хромосомы, затем в одного из потомков копируется первая часть первого родителя и вторая часть второго, а во второго потомка первая часть второго родителя и вторая часть первого родителя. После чего случайным образом выбирается выживший потомок. Можно сделать и несколько иначе: так же случайным образом находится точка разрыва, после чего случайным образом выбирается, чья часть будет первой и чья соответственно второй, затем выбранные части копируются в потомка.
2. При Двухточечном скрещивании случайным образом выбираются две точки разрыва, после чего в одного потомка копируются первая и третья части случайным образом выбранного родителя и вторая часть второго родителя. Либо в первого потомка копируются первая и третья части первого родителя и вторая второго, а во второго потомка первая и третья части второго родителя и вторая часть первого, и после этого случайным образом выбирается выживший потомок. Не следует оценивать обоих потомков, до того как выбран выживший, так как их пригодность не влияет  на выбор, а её вычисление является наиболее долгим процессом.
3. При Равномерном скрещивании случайным образом (для каждого гена) выбирается номер (первый, второй) родителя, чей ген и записывается в потомка. В этом случае родителей может быть больше двух, в том числе возможно участие всей популяции родителей в целом.

 

     И последний этап это Мутация. Мутация состоит из выполнения(обычно небольших) изменений в значениях одного или нескольких генов в хромосоме. В двоичных хромосомах мутация состоит в инвертировании случайным образом выбранного бита генотипа, например 1010101010  -->   1011101010.В генетических алгоритмах мутация рассматривается как метод восстановления потерянного генетического материала (а не как поиск лучшего решения). В генетических алгоритмах мутация применяется к генам с низкой вероятностью. Можно выбирать вероятность в зависимости от длины хромосомы  p_m = , где M - число бит в хромосоме.

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

Результаты  тестирования.

Функция 1.

-65

,

50 индивидов

10 поколений

100 прогонов

Описание: Решение  функции находили в целых числах.

Таблица 1.

  Функция 2. Функция Растригина.

,

Точность=0,1

50 индивидов

100 поколений

100 прогонов

Описание: Вокруг глобального  минимума находится еще несколько  локальных минимумов. Поэтому для  улучшения результатов поиска, приходится увеличивать ресурсы (количество поколений). 

Таблица 2. 
 

Функция 3. Функция Розенброка.

,

Точность=0,1

50 индивидов

10 поколений

100 прогонов

Описание: Вокруг глобального  минимума, находится область, на которой  значения функции достаточно близки к значению минимума, но т.к. явных  локальных минимумов нет, алгоритм работает достаточно хорошо и при  меньших ресурсах.