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

Содержание:

/>/>Введение

Глава 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]. Значения кодов Грея рассмотрены в таблице ниже:

Двоичное кодирование Кодирование по коду Грея десятичное двоичное

шестнадца-

теричное

десятичное двоичное

шестнадца-

теричное

000 0h 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 4 6 2 9 2 4 3 2 9 3 6 3 5 9 4 2 2 5 8 5 9 9 9 8

Для решениязадачи применим следующий генетический алгоритм. Ре­шение представим в виде перестановки чисел от 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.     «Генетическиеалгоритмы по-русски» — www.chat.ru/~saisa

13.     «Нейропроект.Аналитические технологии XXI века» — www.neuroproject.ru

14.     «Научноеиздательство ТВП» — www.tvp.ru/mathem3.htm

15.     «Факультетвычислительной математики и кибернетики МГУ (ВМиК)» - http://cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html

16.     «Neural BenchDevelopment» — www.neuralbench.ru/rus/theory/genetic.htm

17.     «Журнал«Автоматизация Проектирования»» — www.opensystems.ru/ap/1999/01/08.htm

18.     «(EHIPS)Генетические алгоритмы» — www.iki.rssi.ru/ehips/genetic.htm

19.     «SENNГенетические Алгоритмы» — fdmhi.mega.ru/ru/senn_ga.htm

20.     Хорева Е.В.Курсовая работа. Тема «Применение генетических алгоритмов для решения задачоптимизации»-КГПУ.: 2007г.

21.     «Лекции понейронным сетям и генетическим алгоритмам» — infoart.baku.az/inews/30000007.htm