Генетический алгоритм и его сущность (стр. 2 из 3)

Функция 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-точечное скрещивание +высокая мутация, , турнирная селекция + равномерное скрещивание + высокая мутация, пропорциональная селекция + равномерное скрещивание + высокая мутация.

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

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

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

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

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

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

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

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

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

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

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

Приложение.

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