Курсовая работа: Генетические алгоритмы

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

Хромосома	Подходимость
1	(1/84)/0.135266 = 8.80%
2	(1/24)/0.135266 = 30.8%
3	(1/26)/0.135266 = 28.4%
4	(1/133)/0.135266 = 5.56%
5	(1/28)/0.135266 = 26.4%

Таблица 3: Вероятность оказаться родителем

Для выбора 5-и пар родителей (каждая из которых будет иметь 1 потомка, всего - 5 новых решений), представим, что у нас есть 10000-стонняя игральная кость, на 880 сторонах отмечена хромосома 1, на 3080 - хромосома 2, на 2640 сторонах - хромосома 3, на 556 - хромосома 4 и на 2640 сторонах отмечена хромосома 5. Чтобы выбрать первую пару, кидаем кость два раза и выбираем выпавшие хромосомы. Таким же образом выбирая остальных, получаем:

Хромосома отца	Хромосома матери
3	1
5	2
3	5
2	5
5	3

Таблица 4: Симуляция выбора родителей

Каждый потомок содержит информацию о генах и отца и от матери. Вообще говоря, это можно обеспечить различными способами, однако в нашем случае можно использовать т.н. "кроссовер" (cross-over). Пусть мать содержит следующий набор решений: a1,b1,c1,d1, а отец - a2,b2,c2,d2, тогда возможно 6 различных кросс-оверов (| = разделительная линия):

Хромосома-отец	Хромосома-мать	Хромосома-потомок
a1 | b1,c1,d1	a2 | b2,c2,d2	a1,b2,c2,d2 or a2,b1,c1,d1
a1,b1 | c1,d1	a2,b2 | c2,d2	a1,b1,c2,d2 or a2,b2,c1,d1
a1,b1,c1 | d1	a2,b2,c2 | d2	a1,b1,c1,d2 or a2,b2,c2,d1

Таблица 5: Кросс-оверы между родителями

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

А теперь попробуем проделать это с нашими потомками

Хромосома-отец	Хромосома-мать	Хромосома-потомок
(13 | 5,7,3)	(1 | 28,15,3)	(13,28,15,3)
(9,13 | 5,2)	(14,9 | 2,4)	(9,13,2,4)
(13,5,7 | 3)	(9,13,5 | 2)	(13,5,7,2)
(14 | 9,2,4)	(9 | 13,5,2)	(14,13,5,2)
(13,5 | 7, 3)	(9,13 | 5, 2)	(13,5,5,2)

Таблица 6: Симуляция кросс-оверов хромосом родителей

Теперь мы можем вычислить коэффициенты выживаемости (fitness) потомков.

Хромосома-потомок	Коэффициент выживаемости
(13,28,15,3)	|126-30|=96
(9,13,2,4)	|57-30|=27
(13,5,7,2)	|57-30|=22
(14,13,5,2)	|63-30|=33
(13,5,5,2)	|46-30|=16

Таблица 7: Коэффициенты выживаемости потомков (fitness)

Средняя приспособленность (fitness) потомков оказалась 38.8, в то время как у родителей этот коэффициент равнялся 59.4. Следующее поколение может мутировать. Например, мы можем заменить одно из значений какой-нибудь хромосомы на случайное целое от 1 до 30. Продолжая, таким образом, одна хромосома, в конце концов, достигнет коэффициента выживаемости 0, то есть станет решением. Системы с большей популяцией (например, 50 вместо 5-и) сходятся к желаемому уровню (0) более быстро и стабильно.

2.4. Пути решения задач оптимизации

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

Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера (TSP - travelling salesman problem). [20] Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).

рис.  1 Кратчайший путь

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

рис.2 Переборный метод

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

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

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

рис.  3 Метод градиентного спуска

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

рис.  4

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

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

рис.  5

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

рис. 10

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

2.5  Решение задачи коммивояжера.

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

Для решения предлагается следующая задача: имеется пять городов, стоимость переезда между которыми представлена следующей матрицей:

	1	2	3	4	5
1	0	4	6	2	9
2	4	0	3	2	9
3	6	3	0	5	9
4	2	2	5	0	8
5	9	9	9	8	0

Для решения задачи применим следующий генетический алгоритм. Ре­шение представим в виде перестановки чисел от 1 до 5, отображающей последовательность посещения городов. А значение целевой функции бу­дет равно стоимости всей поездки, вычисленной в соответствии с выше­приведенной матрицей. Сразу заметим, что одним из оптимальных реше­ний задачи является последовательность 514235 стоимостью 25.

Заметим, что чем меньше значение целевой функции, тем лучше. То есть целью в данном случае является поиск минимума целевой функции.

В качестве оператора скрещивания выберем процеду­ру, похожую на двухточечный оператор скрещивания. Поясним его работу на примере. Пусть есть две родительские перестановки (12345) и (34521). Случайно и равновероятно выбираются две точки разрыва. Для примера возьмем ситуацию, когда первая точка разрыва находится между первым и вторым элементами перестановки, а вторая точка – между четвертым и пя­тым: (1 | 2 3 4 | 5), (3 | 4 52 | 1). На первом этапе перестановки обмениваются фрагментами, заключенными между точками разрыва: (* | 452 | *) , (* | 234 | *). На втором этапе вместо звездочек вставляются соответствую­щие числа из исходной родительской перестановки, начиная со второго числа выделенного фрагмента и пропуская уже имеющиеся в новой перестановке числа. В данном случае в первой перестановке (1 | 234 | 5) таким начальным числом является 3, за ним идет 4, которое есть в новой перестановке, и мы его пропускаем, также пропускаем число 5, переходим на начало перестановки и выбираем число 1. В итоге вместо (* | 4 5 2 | *) получаем (34521), аналогич­но из (3| 452|1) и (*|234|*) получаем (52341).

Оператор мутации будет представлять собой случайную перестановку двух чисел в хромосоме, также выбранных случайно по равномерному за­кону. Вероятность мутации 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 действует по следующему сценарию:

o    сценарий Action Script настраивается на обнаружение определенного события.

o    Как только событие происходит, выполняется обрабатывающий это событие набор инструкций 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