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

Автор работы: Пользователь скрыл имя, 04 Декабря 2009 в 18:15, Не определен

Описание работы

Курсовая работа

Скачать архив (169.43 Кб) Сколько стоит заказать работу?
Файлы: 1 файл

основной.docx

— 677.71 Кб (Скачать файл)

Таблица 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. Функция Растригина.

,

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

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

,

      

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

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

,

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

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

,

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

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

,

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

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

,

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

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

Информация о работе Генетический алгоритм и его сущность