Содержание:
Введение
Глава 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 Описание программной реализации
Заключение
Библиография
ВВЕДЕНИЕ
Природа поражает своей сложностью и богатством проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, ставшие очевидными при глубоком исследовании природы вокруг нас. Наука - это одна из систем, которая объясняет окружающее и помогает приспособиться к новой информации, получаемой из внешней среды. Многое из того, что мы видим и наблюдаем, можно объяснить теорией эволюции через наследственность, изменение и отбор.
На мировоззрение людей сильно повлияла теория эволюции Чарльза Дарвина, представленная в работе "Происхождение Видов", в 1859 году. Множество областей научного знания многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим современникам, предполагающим, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Однако Дарвин обнаружил главный механизм развития: отбор в соединении с изменчивостью. Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорные, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемые в Природе. Поэтому не удивительно, что ученые, занимающиеся компьютерными исследованиями, в поисках вдохновения обратились к теории эволюции. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в естественных системах, была очень привлекательной. Эта надежда является причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.
Итак, в природе постоянно происходит процесс решения задач оптимизации. Задачи оптимизации — наиболее распространенный и важный для практики класс задач. Их приходится решать каждому из нас либо в быту, распределяя свое время между различными делами, либо на работе, добиваясь максимальной скорости работы программы или максимальной доходности компании — в зависимости от должности.
Благодаря открытиям последних ста лет современной науке известны все основные механизмы эволюции, связанные с генетическим наследованием. Эти механизмы достаточно просты по своей идее, но остроумны (если к природе применимо это слово) и эффективны. Удивительно, но простое моделирование эволюционного процесса на компьютере позволяет получить решения многих практических задач. Такие модели получили название “генетические алгоритмы” и уже широко применяются в различных областях.
В процессе изучения различных подходов к решению задач оптимизации нами выдвигается гипотеза
что, решение задач оптимизации возможно с помощью генетических алгоритмов.
Объектом
изучения данной курсовой работы являются генетические алгоритмы.
Предмет
изучения – применение генетических алгоритмов для нахождения решения оптимизационной задачи.
Методы исследования:
oсбор и анализ литературных источников по данной теме;
oизучение особенностей создания и использования генетических алгоритмов;
oмоделирование работы генетического алгоритма на компьютере применимо к нахождению решения задачи оптимизации.
Целью
данной курсовой работы является разработка электронного пособия, в котором поэтапно описывается решение задачи о нахождении кратчайшего маршрута в существующей системе дорог.
Задачи:
1. проанализировать возможности генетических алгоритмов;
2. изучить особенности генетических алгоритмов;
3. создание электронного пособия по основам генетических алгоритмов;
ГЛАВА 1: ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ
1.1. Естественный отбор в природе
“XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?..”
Автор: РОСС КЛЕМЕНТ
Опубликовано в журнале "Компьютерра" №11 от 16 марта 1999 года
Ключевую роль в эволюционной теории играет естественный отбор. Его суть состоит в том, что наиболее приспособленные особи лучше выживают и приносят больше потомков, чем менее приспособленные. Заметим, что сам по себе естественный отбор еще не обеспечивает развитие биологического вида. Поэтому очень важно понять, каким образом происходит наследование, то есть как свойства потомка зависят от свойств родителей.
Основной закон наследования интуитивно понятен каждому - он состоит в том, что потомки похожи на родителей. В частности, потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. Чтобы понять, на чем основано это сходство, нужно немного углубиться в построение естественной клетки - в мир генов и хромосом [4].
Почти в каждой клетке любой особи есть набор хромосом, несущих информацию об этой особи. Основная часть хромосомы - нить ДНК, определяющая, какие химические реакции будут происходить в данной клетке, как она будет развиваться и какие функции выполнять. Ген - это отрезок цепи ДНК, ответственный за определенное свойство особи, например за цвет глаз, тип волос, цвет кожи и т.д. При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.
При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида. Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название «репродуктивный план Холланда» и лег в основу практически всех вариантов генетических алгоритмов [8]. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.
1.2. Представление объектов. Кодирование признаков
Из биологии мы знаем, что любой организм может быть представлен своим фенотипом, который фактически определяет, чем является объект в реальном мире, и генотипом, который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе [9]. Таким образом, для решения задач нам необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.
В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.
Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма [9]. Значения кодов Грея рассмотрены в таблице ниже:
| Двоичное кодирование | Кодирование по коду Грея | ||||
| десятичное | двоичное | шестнадца- теричное |
десятичное | двоичное | шестнадца- теричное |
| 0 | 000 | 0h | 0 | 0000 | 0h |
| 1 | 0001 | 1h | 1 | 0001 | 1h |
| 2 | 0010 | 2h | 3 | 0011 | 3h |
| 3 | 0011 | 3h | 2 | 0010 | 2h |
| 4 | 0100 | 4h | 6 | 0110 | 6h |
| 5 | 0101 | 5h | 7 | 0111 | 7h |
| 6 | 0110 | 6h | 5 | 0101 | 5h |
| 7 | 0111 | 7h | 4 | 0100 | 4h |
| 8 | 1000 | 8h | 12 | 1100 | Ch |
| 9 | 1001 | 9h | 13 | 1101 | Dh |
| 10 | 1010 | Ah | 15 | 1111 | Fh |
| 11 | 1011 | Bh | 14 | 1110 | Eh |
| 12 | 1100 | Ch | 10 | 1010 | Ah |
| 13 | 1101 | Dh | 11 | 1011 | Bh |
| 14 | 1110 | Eh | 9 | 1001 | 9h |
| 15 | 1111 | Fh | 8 | 1000 | 8h |
Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому. В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины[10]. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит
| 0010 | 1010 | 1001 | 0100 | 1101 |
теперь мы можем определить значения признаков
| Признак | Значение гена | Двоичное значение признака | Десятичное значение признака | ||||
| Признак 1 | 0010 | 0011 | 3 | ||||
| Признак 2 | 1010 | 1100 | 12 | ||||
| Признак 3 | 1001 | 1110 | 14 | ||||
| Признак 4 | 0100 | 0111 | 7 | ||||
| Признак 5 | 1101 | 1001 | 9 | ||||
1.3 Основные генетические операторы
Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:
oиз популяции выбираются две особи, которые будут родителями;
oопределяется (обычно случайным образом) точка разрыва;
oпотомок определяется как конкатенация части первого и второго родителя.
Рассмотрим функционирование этого оператора
| Хромосома_1: | 0000000000 |
| Хромосома_2: | 1111111111 |
Допустим, разрыв происходит после 3-го бита хромосомы, тогда получаем.
| Хромосома_1: | 0000000000 | >> | 000 | 1111111 | Результирующая хромосома 1 |
| Хромосома_2: | 1111111111 | >> | 111 | 0000000 | Результирующая хромосома 2 |
Итак, рассмотрим все же операторы по порядку:
1) кроссинговер - создание структуры, основанной на двух структурах - заменой одной части первой структуры на ту же область во второй.
Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей с популяции. Он называется оператором мутации. При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется.Кроме того, используется еще и так называемый оператор инверсии, который заключается в том, что хромосома делится на две части, и затем они меняются местами. Схематически это можно представить следующим образом:
| 000 | 1111111 | >> | 1111111 | 000 |
2) инверсия - перестановка в структуре некоторой ее части наоборот
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).
3) мутация - замена в структуре одного из значений случайно выбранной компоненты
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 1, 1, 0, 1, 0).
В принципе для функционирования генетического алгоритма достаточно этих двух генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих двух операторов. Например, кроссовер может быть не одноточечный (как было описано выше), а многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.
1.4. Схема функционирования генетического алгоритма
Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.
Инициировать начальный момент времени t=0 . Случайным образом сформировать начальную популяцию, состоящую из k особей.
Вычислить приспособленность каждой особи и популяции в целом (также иногда называемую термином фиттнес). Значение этой функции определяет насколько хорошо подходит особь, описанная данной хромосомой, для решения задачи.
1. Выбрать особь из популяции.
2. С определенной вероятностью (вероятностью кроссовера ) выбрать вторую особь из популяции и произвести оператор кроссовера.
3. С определенной вероятностью (вероятностью мутации) выполнить оператор мутации.
4. С определенной вероятностью (вероятностью инверсии ) выполнить оператор инверсии.
5. Поместить полученную хромосому в новую популяцию
6. Выполнить операции, начиная с пункта 3, k раз.
7. Увеличить номер текущей эпохи t=t+1.
8. Если выполнилось условие остановки, то завершить работу, иначе переход на шаг 2 [13].
Распишем более подробно следующие этапы:
1. Выбор родительской пары .
Первый подход самый простой - это случайный выбор родительской пары ("панмиксия"), когда обе особи, которые составят родительскую пару, случайным образом выбираются из всей популяции, причем любая особь может стать членом нескольких пар. Несмотря на простоту, такой подход универсален для решения различных классов задач. Однако он достаточно критичен к численности популяции, поскольку эффективность алгоритма, реализующего такой подход, снижается с ростом численности популяции.
Второй способ выбора особей в родительскую пару - так называемый селективный. Его суть состоит в том, что "родителями" могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, при равной вероятности таких кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма. Однако из-за быстрой сходимости селективный выбор родительской пары не подходит тогда, когда ставиться задача определения нескольких экстремумов, поскольку для таких задач алгоритм, как правило, быстро сходится к одному из решений. Кроме того, для некоторого класса задач со сложным ландшафтом приспособленности быстрая сходимость может превратиться в преждевременную сходимость к квазиоптимальному решению. Этот недостаток может быть отчасти компенсирован использованием подходящего механизма отбора (о чем будет сказано ниже), который бы "тормозил" слишком быструю сходимость алгоритма.
Другие два способа формирования родительской пары, на которые хотелось бы обратить внимание, это инбридинг и аутбридинг. Оба эти метода построены на формировании пары на основе близкого и дальнего "родства" соответственно. Под "родством" здесь понимается расстояние между членами популяции как в смысле геометрического расстояния особей в пространстве параметров. В связи с этим будем различать генотипный и фенотипный (или географический) инбридинг и аутбридинг. Под инбридингом понимается такой метод, когда первый член пары выбирается случайно, а вторым с большей вероятностью будет максимально близкая к нему особь. Аутбридинг же, наоборот, формирует брачные пары из максимально далеких особей. Использование генетических инбридинга и аутбридинга оказалось более эффективным по сравнению с географическим для всех тестовых функций при различных параметрах алгоритма. Наиболее полезно применение обоих представленных методов для многоэкстремальных задач [14]. Однако два этих способа по-разному влияют на поведение генетического алгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска в локальных узлах, что фактически приводит к разбиению популяции на отдельные локальные группы вокруг подозрительных на экстремум участков ландшафта, напротив аутбридинг как раз направлен на предупреждение сходимости алгоритма к уже найденным решениям, заставляя алгоритм просматривать новые, неисследованные области.
2. Механизм отбора
Обсуждение вопроса о влиянии метода создания родительских пар на поведение генетического алгоритма невозможно вести в отрыве от реализуемого механизма отбора при формировании нового поколения. Наиболее эффективные два механизма отбора элитный и отбор с вытеснением.
Идея элитного отбора, в общем, не нова, этот метод основан на построении новой популяции только из лучших особей репродукционной группы, объединяющей в себе родителей, их потомков и мутантов. В основном это объясняют потенциальной опасностью преждевременной сходимости, отдавая предпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемая элитным отбором, может быть, когда это необходимо, с успехом компенсирована подходящим методом выбора родительских пар, например аутбридингом. Именно такая комбинация "аутбридинг - элитный отбор" является одной из наиболее эффективной. Второй метод, на котором хотелось бы остановиться, это отбор вытеснением. Будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие. Вытеснение в данном случае формирует новую популяцию скорее из далеко расположенных особей, вместо особей, группирующихся около текущего найденного решения. Этот метод особенно хорошо себя показал при решении многоэкстремальных задач, при этом помимо определения глобальных экстремумов появляется возможность выделить и те локальные максимумы, значения которых близки к глобальным.
Вывод
Итак, изложенный подход к изучению генетических алгоритмов является эвристическим, т. е. показывает хорошие результаты на практике, но плохо поддается теоретическому исследованию и обоснованию. Естественно задать вопрос — следует ли пользоваться такими алгоритмами, не имеющими строгого математического обоснования?
Как и в вопросе о нейронных сетях, здесь нельзя ответить однозначно. С одной стороны, в математике существует достаточно большой класс абсолютно надежных (в смысле гарантии получения точного решения) методов решения различных задач. С другой стороны, речь идет о действительно сложных практических задачах, в которых эти надежные методы часто неприменимы. Нередко эти задачи выглядят настолько необозримыми, что не предпринимается даже попыток их осмысленного решения.[15]
Например, фирма, занимающаяся транспортными перевозками, в современных условиях российского бизнеса скорее предпочтет нанять лишних водителей и повысить цены на свои услуги, чем оптимизировать маршруты и расписания поездок. На западном рынке, где уже давно действуют законы более или менее честной конкуренции, оптимальность деятельности компании значительно влияет на ее доходы и даже может стать решающим фактором для ее выживания. Поэтому любые идеи, позволяющие компании стать “умнее” своих конкурентов, находят там широкое применение.
Генетические алгоритмы — реализация одной из наиболее популярных идей такого рода. Эта популярность вызвана, по-видимому, исключительной красотой подхода и его близостью к природному механизму. Подобным образом популярность нейросетевой технологии подогревается во многом ее сходством с работой мозга. По-настоящему активное развитие эвристических подходов непосредственно связано с развитием свободного рынка и экономики в целом.
Таким образом, задав условия жизни в некотором виртуальном мире и заселив его представителями с определенными свойствами, после процессов скрещивания, мутации и естественного отбора, аналоги которых происходят и в реальном мире, мы стабильно получаем особь, свойства которой отвечают ранее заданным требованиям. Успешное решение задачи заставляет восхищаться мудростью природы, реализовавшей такой удивительно несложный и потрясающе эффективный механизм. Этот факт наводит на мысль о том, что понимание проверенных веками законов природы позволяет использовать их при решении, казалось бы, и далеких от нее задач, частным случаем которых является рассмотренные далее задачи оптимизации.
ГЛАВА 2. ЗАДАЧИ ОПТИМИЗАЦИИ.
2.1 Задачи, решаемые с помощью генетических алгоритмов
Теперь мы с вами понимаем, на чем основаны принципы работы генетических алгоритмов. Но для решения каких задач реализуются эти алгоритмы? Итак, в этой главе нами будут рассмотрены задачи оптимизации, их математическая постановка и пути решения. Так же нами будут рассмотрены решение Диофантова уравнения и задачи коммивояжера.
Задачи оптимизации – наиболее распространенный и важный для практики класс задач. Их приходится решать любому из нас или в быту, распределяя свое время между разными делами, или на работе, добиваясь максимальной скорости работы программы или максимальной прибыльности компании – в зависимости от должности.
2.2 Математическая постановка задачи оптимизации
Постановка задачи оптимизации включает в себя множество допустимых решений и числовую функцию , определенную на этом множестве, которая называется целевой функцией.
Нельзя отождествлять критерий (критерии) оптимальности и целевую функцию.
Целевая функция – это аналитическая зависимость между критерием (критериями) оптимальности и подлежащими оптимизации параметрами с указанием направления экстремума.
Отличие понятий «критерий» и «целевая функция» состоит в следующем:
1. Целевая функция может включать в себя более одного критерия.
2. Для целевой функции всегда и обязательно указывается вид экстремума:
Различают два вида задач оптимизации:
oЗадачу минимизации.
oЗадачу максимизации.
Чтобы решить задачу минимизации функции на множестве, необходимо найти такой вектор ( а также соответствующее значение целевой функции), чтобы нераве
Чтобы решить задачу максимизации функции на множестве, необходимо найти такой вектор (а также соответствующее значение целевой функции), чтобы неравенство: выполнялось для всех. При этом называют оптимальным (максимальным ) решением, а– оптимумом ( максимумом ).
В общем виде находится именно вектор , т.к., например, при решении двухпараметрической задачи, он будет включать в себя два параметра, трехпараметрической – три параметра и т.д.
2.3 Решение Диофантова уравнения
Рассмотрим Диофантово (только целые решения) уравнение: a+2b+3c+4d=30, где a, b, c и d - некоторые положительные целые. Применение ГА за очень короткое время находит искомое решение (a, b, c, d).
Конечно, Вы можете спросить: почему бы не использовать метод грубой силы: просто не подставить все возможные значения a, b, c, d (очевидно, 1 <= a,b,c,d <= 30) ?
Архитектура ГА-систем позволяет найти решение быстрее за счет более 'осмысленного' перебора. Мы не перебираем все подряд, но приближаемся от случайно выбранных решений к лучшим.
Для начала выберем 5 случайных решений: 1 =< a,b,c,d =< 30. Вообще говоря, мы можем использовать меньшее ограничение для b,c,d, но для упрощения пусть будет 30.
| Хромосома | (a,b,c,d) |
| 1 | (1,28,15,3) |
| 2 | (14,9,2,4) |
| 3 | (13,5,7,3) |
| 4 | (23,8,16,19) |
| 5 | (9,13,5,2) |
Таблица 1: 1-е поколение хромосом и их содержимое
Чтобы вычислить коэффициенты выживаемости (fitness), подставим каждое решение в выражение a+2b+3c+4d. Расстояние от полученного значения до 30 и будет нужным значением.
| Хромосома | Коэффициент выживаемости |
| 1 | |114-30|=84 |
| 2 | |54-30|=24 |
| 3 | |56-30|=26 |
| 4 | |163-30|=133 |
| 5 | |58-30|=28 |
Таблица 2: Коэффициенты выживаемости первого поколения хромосом (набора решений)
Так как меньшие значения ближе к 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 и, естественно, что тот, кто собирается программировать, стремится писать программы, которые будут работать в этих системах.
Интерактивность – сегодня наиболее важное, мы бы сказали основное
условие для создаваемых приложений. Наиболее полный стандарт, который гарантирует данное условие, стал всем известный ActionScript для Flash. Сравнительно недавно он превратился из простого языка подготовки сценариев в полноценную объектно-ориентированную среду программирования.
Как вы помните, нашей целью является создание электронного пособия, которое позволило бы достаточно понятно и просто донести до читателя основные понятия и принципы организации генетического алгоритма. ActionScript предоставляет прекрасную возможность, организовать красочный, доступный интерфейс и навигацию. И еще один неоспоримый плюс при создании учебника на ActionScript: использование готового продукта, как самостоятельную программу (публикация готового продукта с exe расширением).
3.2 Описание программной реализации
Для начала, мы подготовили материал, который будет представлен в нашем пособии. Определились со структурой и дизайном, и только после этого началось непосредственно создание нашего продукта.
Мы использовали, как было упомянуто выше, MacromediaFlash
MX2004. Алгоритм создания следующий:
1. Создаем новый Flash документ.
2. Прорабатываем дизайн нашего пособия (установка фона, шрифта)
3. Размещаем подготовленный нами материал на кадрах, предварительно вставив на каждом их них ключевой кадр.
4. Организация навигации.
5. Проверка и публикация созданного документа в exe формате.
Распишем подробнее некоторые пункты.
Размещение материала было сформировано наподобие обычной книги с заглавием, содержанием и возможностью перелистывания страниц.
Содержание
Навигация (перелистывание страниц)
Что касаетсянавигации и непосредственно программирования на языке ActionScript, тут тоже не возникло ни каких проблем. Сама программа пишется в окне Action, при выделение объекта, но который пишутся действия.
FlashActionScript действует по следующему сценарию:
o сценарий ActionScript настраивается на обнаружение определенного события.
o Как только событие происходит, выполняется обрабатывающий это событие набор инструкций ActionScript.
На каждый кадр (страницу нашего пособия) пишется определенная заготовка:
stop ();
// останавливает автоматическое проигрывание кадров.
- На каждую кнопку пишется другая заготовка:
on (release) {
gotoAndStop (“Scene 1”, 2);
}
// Итак, поясним эту несложную конструкцию. другими словами первая строка будет выглядеть так: при (отпускании) {выполнить это…}. Команда gotoAndStop позволяет нам перейти на второй кадр первой сцены и остановиться.
Еще одно небольшое замечание, необходимо преобразовать нарисованную или вставленную из библиотеки кнопку в символ. Для этого выделяем наш объект правой кнопкой, и выбираем в контекстном меню Convert, в появившемся меню ставим галочку напротив Button.
Во Flash мы на каждом шаге можем проверять (отлаживать) нашу разработку, для этого в главном меню выбираем Control/Testmovie.
И, наконец, на последнем шаге мы публикуем наше пособие в 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/0
1/08.htm
18. «(EHIPS) Генетические алгоритмы» - http://www.iki.rssi.ru/ehips/gene
tic.htm
19. «SENN Генетические Алгоритмы» - http://fdmhi
.mega.ru/ru/senn_ga.htm
20. Хорева Е.В. Курсовая работа. Тема «Применение генетических алгоритмов для решения задач оптимизации»-КГПУ.: 2007г.
21. «Лекции по нейронным сетям и генетическим алгоритмам» - http://infoart.baku.az/inews/300
00007.htm