Генетические алгоритмы

Автор работы: Пользователь скрыл имя, 01 Февраля 2014 в 14:21, курсовая работа

Краткое описание

Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая объясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение и отбор.

Содержание

Введение
Глава 1. Генетические алгоритмы
1.1 Естественный отбор в природе
1.2 Представление объектов. Кодирование признаков
1.3 Основные генетические операторы
1.4 Схема функционирования генетического алгоритма
Вывод
Глава 2. Задачи оптимизации
2.1 Задачи, решаемые с помощью генетических алгоритмов
2.2 Математическая постановка задачи оптимизации
2.3 Решение Диофантова уравнения
2.4 Пути решения задач оптимизации
2.5 Задача коммивояжера
Вывод
Глава 3. Программная реализация. Создание пособия по генетическим алгоритмам
3.1 Обоснование выбора программного обеспечения
3.2 Описание программной реализации
Заключение
Библиография

Прикрепленные файлы: 1 файл

нургуль ген.doc

— 318.00 Кб (Скачать документ)

Оператор  мутации будет представлять собой  случайную перестановку двух чисел  в хромосоме, также выбранных случайно по равномерному закону. Вероятность мутации 0,01. Размер популяции выберем равным 4.

Исходная  популяция представлена в таблице 1.

 

Таблица 1

№ строки

Код

Значение целевой функции

Вероятность участия  в процессе размножения

1

12345

29

32/122

2

21435

29

32/122

3

54312

32

29/122

4

43125

32

29/122


 

Пусть для  скрещивания были выбраны следующие  пары: (1, 3) и (2, 4). В результате были получены потомки, представленные в таблице 2.

Таблица 2

№ строки

Родители

Потомки

Значение целевой функции  для потомков

1

1|23|45

5|43|12

32

3

5|43|12

1|23|54

мутация 13254

28

2

2|143|5

4|312|5

32

4

4|312|5

2|143|5

29


 

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

Таблица 3

№ строки

Код

Значение целевой функции

Вероятность участия  в процессе размножения

1(1)

12345

29

28/122

2(2)

21435

29

28/122

3(н)

13254

28

29/122

4(н)

21435

29

28/122


 

Пусть для получения второго поколения были выбраны следующие пары строк: (1,4) и (2, 3). И в результате были получены потомки, показанные в таблице 4.

Таблица 4

№ строки

Родители

Потомки

Значение целевой функции  для потомков

1

|123|45

|214|35

29

4

|214|35

|123|45

29

2

|21|435

|13|452

32

3

|13|254

|21|354

29


 

Популяция второго  поколения после отсечения худших особей приняла вид, показанный в таблице 5.

Таблица 5

№ строки

Код

Значение целевой функции

Вероятность участия в процессе размножения

1(1)

12345

29

28/111

2(2)

21435

29

28/111

3(3)

13254

28

29/111

4(н)

21354

29

28/111


 

Таким образом, после двух итераций значение целевой  функции для лучшего решения изменилось с 29 на 28, среднее значение изменилось с 30,5 до 28,75, а общее качество с 122 до 111. То есть также налицо незначительное, но улучшение популяции [21].

Вывод

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

 

ГЛАВА 3. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ. СОЗДАНИЕ ПОСОБИЯ ПО ГЕНЕТИЧЕСКИМ АЛГОРИТМАМ.

 

3.1 Обоснование выбора  программного обеспечения

 

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

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

Интерактивность – сегодня наиболее важное, мы бы сказали основное

 условие для создаваемых  приложений. Наиболее полный стандарт, который гарантирует данное условие,  стал всем известный Action Script для Flash. Сравнительно недавно он превратился из простого языка подготовки сценариев в полноценную объектно-ориентированную среду программирования.

      Как  вы помните, нашей целью является  создание электронного пособия,  которое позволило бы достаточно понятно и просто донести до читателя основные понятия и принципы организации генетического алгоритма. Action Script предоставляет прекрасную возможность, организовать красочный, доступный интерфейс и навигацию. И еще один неоспоримый плюс при создании учебника на Action Script: использование готового продукта, как самостоятельную программу (публикация готового продукта с exe расширением).

 

 

3.2 Описание программной реализации

 

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

Мы использовали, как  было упомянуто выше, Macromedia Flash MX2004. Алгоритм создания следующий:

    1. Создаем новый Flash документ.
    2. Прорабатываем дизайн нашего пособия (установка фона, шрифта)
    3. Размещаем подготовленный нами материал на кадрах, предварительно вставив на каждом их них ключевой кадр.
    4. Организация навигации.
    5. Проверка и публикация созданного документа в exe формате.

Распишем подробнее некоторые пункты.

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


 

Содержание                             Навигация (перелистывание страниц)

 

Что касается навигации и непосредственно программирования на языке Action Script, тут тоже не возникло ни каких проблем. Сама программа пишется в окне Action, при выделение объекта, но который пишутся действия.

Flash Action Script действует по следующему сценарию:

  • сценарий Action Script настраивается на обнаружение определенного события.
  • Как только событие происходит, выполняется обрабатывающий это событие набор инструкций Action Script.

На каждый кадр (страницу нашего пособия) пишется определенная заготовка:

 

stop ();

// останавливает автоматическое проигрывание кадров.

 

- На каждую кнопку  пишется другая заготовка:

 

on (release) {

   gotoAndStop (“Scene 1”, 2);

        }

// Итак, поясним эту  несложную конструкцию. другими  словами первая строка будет  выглядеть так: при (отпускании) {выполнить это…}. Команда gotoAndStop позволяет нам перейти на второй кадр первой сцены и остановиться.

Еще одно небольшое замечание, необходимо преобразовать нарисованную или вставленную из библиотеки кнопку в символ. Для этого выделяем наш объект правой кнопкой, и выбираем в контекстном меню Convert, в появившемся меню ставим галочку напротив Button.

Во Flash мы на каждом шаге можем проверять (отлаживать) нашу разработку, для этого в главном меню выбираем Control/Test movie.

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

 

Заключение

 

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

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

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

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

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

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

 

Библиография

 

  1. Вентцель Е.С. «Исследование операций», - М.: 1972 г.
  2. Гальцына О.Л., Попов И.И.   «Основы алгоритмизации и программирования».
  3. Грешилов А.А.  «Как принять наилучшее решение в реальных условиях», - М.: 1991 г., стр. 164-170
  4. Корнеев В.В., Гареев А.Ф. «Базы данных. Интеллектуальная обработка данных», М.: 2001г., стр. 220
  5. Коршунов Ю.М. «Математические основы кибернетики. Для студентов вузов», - М.: 1987 г., стр. 67-89
  6. Леонов О.И.   «Теория графов».
  7. Майника Э., «Алгоритмы оптимизации на сетях и графах.» - М.: 1981
  8. Новиков Ф.А. «Дискретная математика для программистов».
  9. «Генетические алгоритмы: почему они работают?»/ Компьютерра, № 11, 1999 год
  10. Де Джонг К. А. Введение ко второму специальному выпуску по 
    генетическим алгоритмам. Машинное обучение, №5(4), с. 351-353
  11. Электронные источники:
  12. «Генетические алгоритмы по-русски» - http://www.chat.ru/~saisa
  13. «Нейропроект. Аналитические технологии XXI века» - http://www.neuroproject.ru
  14. «Научное издательство ТВП» - http://www.tvp.ru/mathem3.htm
  15. «Факультет вычислительной математики и кибернетики МГУ (ВМиК)» -  http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html
  16. «Neural Bench Development» - http://www.neuralbench.ru/rus/theory/genetic.htm
  17. «Журнал "Автоматизация Проектирования"» - http://www.opensystems.ru/ap/1999/01/08.htm
  18. «(EHIPS) Генетические алгоритмы» - http://www.iki.rssi.ru/ehips/genetic.htm
  19. «SENN Генетические Алгоритмы» - http://fdmhi.mega.ru/ru/senn_ga.htm
  20. Хорева Е.В. Курсовая работа. Тема «Применение генетических алгоритмов для решения задач оптимизации»-КГПУ.: 2007г.
  21. «Лекции по нейронным сетям и генетическим алгоритмам» - http://infoart.baku.az/inews/30000007.htm

Информация о работе Генетические алгоритмы