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

Содержание.

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

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

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

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

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

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

Введение.

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

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

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

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

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

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

Инициализация

Выращивание

Оценивание

Селекция

Скрещивание

Мутация

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция 1.

-65

,

50 индивидов

10 поколений

100 прогонов

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

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,45	0,45	0,44
	Средняя	0,51	0,59	0,64
	Низкая	0,55	0,53	0,68
пропорциональная	Высокая	0,84	0,78	0,75
	Средняя	0,63	0,8	0,77
	Низкая	0,39	0,57	0,42

Таблица 1.

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

,

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

50 индивидов

100 поколений

100 прогонов

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

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,12	0,09	0,03
	Средняя	0,27	0,19	0,11
	Низкая	0,36	0,42	0,3
пропорциональная	Высокая	0,58	0,48	0,37
	Средняя	0,63	0,64	0,56
	Низкая	0,41	0,45	0,4

Таблица 2.

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

,

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

50 индивидов

10 поколений

100 прогонов

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

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,2	0,36	0,29
	Средняя	0,29	0,33	0,25
	Низкая	0,3	0,23	0,26
пропорциональная	Высокая	0,29	0,34	0,4
	Средняя	0,15	0,25	0,32
	Низкая	0,14	0,19	0,35

Таблица 3.

Функция 4. Функция De Jong 2.

,

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

50 индивидов

50 поколений

100 прогонов

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

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,35	0,28	0,24
	Средняя	0,34	0,24	0,32
	Низкая	0,32	0,28	0,34
пропорциональная	Высокая	0,24	0,23	0,2
	Средняя	0,21	0,35	0,15
	Низкая	0,17	0,12	0,22

Таблица 4.

Функция 5. Функция «Сомбреро».

,

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

50 индивидов

200 поколений

100 прогонов

Описание: Сложность функции состоит в том, что вокруг глобального минимума, по кругу расположены локальные минимумы, и перепутать их с глобальным достаточно легко. Но при еще большем увеличении ресурсов, алгоритм снова показывает неплохие результаты.

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,22	0,19	0,2
	Средняя	0,16	0,14	0,16
	Низкая	0,14	0,19	0,16
пропорциональная	Высокая	0,26	0,19	0,24
	Средняя	0,21	0,17	0,22
	Низкая	0,2	0,25	0,29

Таблица 5.

Функция 6. Функция Griewank.

,

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

50 индивидов

50 поколений

100 прогонов

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

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,01	0,01	0,02
	Средняя	0,02	0,01	0,02
	Низкая	0,02	0	0,02
пропорциональная	Высокая	0,02	0,02	0
	Средняя	0,01	0,02	0,02
	Низкая	0	0,01	0,01

Таблица 6.

Функция 7. Функция Катникова.

,

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

50 индивидов

10 поколений

100 прогонов

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

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,42	0,38	0,35
	Средняя	0,46	0,36	0,38
	Низкая	0,35	0,43	0,39
пропорциональная	Высокая	0,27	0,33	0,37
	Средняя	0,37	0,48	0,41
	Низкая	0,43	0,48	0,38

Таблица 7.

Функция 8. Функция Катникова

,

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

50 индивидов

20 поколений

100 прогонов

Описание: из-за увеличения области, увеличивается и количество локальных минимумов, но увеличив ресурсы, мы снова видим неплохой результат.

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	0,15	0,2	0,16
	Средняя	0,3	0,22	0,28
	Низкая	0,3	0,27	0,28
пропорциональная	Высокая	0,41	0,42	0,43
	Средняя	0,59	0,66	0,59
	Низкая	0,61	0,58	0,58

Таблица 8.

Замечание: графики исследуемых функций представлены в приложении.

Заключение.

Я долго подбирала нужное количество ресурсов, при которых алгоритм дает хорошие результаты. Затем я множество раз запускала алгоритм, и в результатах тестирования приведены усредненные результаты. Затем я проводила исследования, какая же модификация алгоритма работает лучше. Для этого я снова составила таблицу. «+» в данной таблице отмечены модификации, в которых был лучший результат (бралось 3 наилучших результата для каждой функции) , «-» худшие результаты.

Селекция	Мутация	Скрещивание
		1-точечное	2-точечное	равномерное
турнирная	Высокая	+ --	+	-
	Средняя	++	+ -
	Низкая			+
пропорциональная	Высокая	+ -	+	-
	Средняя	++	+++++	++
	Низкая	+ ---	+++ -	+++

Таблица 9.

Из таблицы видно, что наилучшей модификацией является пропорциональная селекция + 2-точечное скрещивание + средняя мутация. Наихудший результат так однозначно определить сложнее, но плохие результаты показали пропорциональная селекция + 1-точечное скрещивание + низкая мутация, турнирная селекция + 1-точечное скрещивание +высокая мутация, , турнирная селекция + равномерное скрещивание + высокая мутация, пропорциональная селекция + равномерное скрещивание + высокая мутация.

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

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

Акопян А.М. Генетические алгоритмы для решения задачи глобальной оптимизации. URL:http://www.cp.niif.spb.su/inpe/4/gaover/gaover.htm

Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов. URL:http://saisa.chat.ru/ga/summer97.html

Батищев Д. И. Генетические алгоритмы решения экстремальных задач / Под ред. Львовича Я.Е.: Учеб. пособие. Воронеж, 1995.

Батищев Д.И., Гуляева П.А., Исаев С.А. Генетический алгоритм для решения задач невыпуклой оптимизации / Тез.докл. Междунар. конф. "Новые информационные технологии в науке, образовании и бизнесе", Гурзуф, 1997.

Генетические алгоритмы. НейроПроект, 1999, support@neuroproject.ru

Исаев С.А.. Генетические алгоритмы - эволюционные методы поиска. URL: http://rv.ryazan.ru/~bug/library/ai/isaev/2/part1.html.

Редько В. Прикладное эволюционное моделирование. Генетический алгоритм. Оценка эффективности генетического алгоритма. URL:http://www.keldysh.ru/BioCyber/Lecture10.html

Росс К. Генетические алгоритмы: почему они работают? когда их применять? / Компьютерра, 1999, № 11

Скурихин А.Н. Генетические алгоритмы / Новости искусственного интеллекта, 1995, №4, с. 6-46.

Приложение.

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

,

Рисунок1. Рисунок2.

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

,

Рисунок3. Рисунок4.

Функция 4. Функция De Jong 2.

,

Рисунок5. Рисунок6.

Функция 5. Функция «Сомбреро».

,

Рисунок7. Рисунок8.

Функция 6. Функция Griewank.

,

Рисунок9. Рисунок10.

Функция 7. Функция Катникова.

,

Рисунок11. Рисунок12.

Функция 8. Функция Катникова

,

Рисунок13. Рисунок14.

18