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

Дальневосточный Государственный Университет

Институт Математики и Компьютерных Наук

Кафедра Информатики

Курсовой проект

Тема:

“ Генетические Алгоритмы”

Исполнил – Студент3-го курса

Несов РоманГеннадьевич

Руководитель – Ассистенткафедры информатики

КленинАлександр Сергеевич

Владивосток 1999г.

Содержание:

1. Естественный отбор в природе….… .3

2. Что такое генетический алгоритм….… .4

3. Подробноеописание генетического aлгоритма… .6

4. Влияние параметров генетическогоалгоритма на эффективность

поиска….… .7

5. Особенности генетических алгоритмов….… .9

6. Список литературы и ссылки….… .11

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

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

Естественный отбор в природе

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

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

Чтобысделать понятными принципы работы генетических алгоритмов, поясним также, какустроены механизмы генетического наследования в природе. В каждой клетке любогоживотного содержится вся генетическая информация этой особи. Эта информациязаписана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиноваяКислота). Каждая молекула ДНК — это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемыхА, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК.Таким образом, генетический код индивидуума — это просто очень длинная строкасимволов, где используются всего 4 буквы. В животной клетке каждая молекула ДНКокружена оболочкой — такое образование называется хромосомой.

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

Приразмножении животных происходит слияние двух родительских половых клеток и ихДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия — кроссовер (cross-over, скрещивание). Прикроссовере ДНК предков делятся на две части, а затем обмениваются своимиполовинками.

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

Что такое генетический алгоритм

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

Один из наиболее наглядных примеров — задача ра/>спределения инвестиций. В этой задаче переменнымиявляются объемы инвестиций в каждый проект, а функцией, которую нужномаксимизировать — суммарный доход инвестора. Также даны значения минимального имаксимального объема вложения в каждый из проектов, которые задают областьизменения каждой из переменных.

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

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

Воткак моделируется генетическое наследование:

Хромосома

Вектор (последовательность) из нулей и единиц.
Каждая позиция (бит) называется геном.

Индивидуум =
генетический код

Набор хромосом = вариант решения задачи. Кроссовер Операция, при которой две хромосомы обмениваются своими частями. Мутация Cлучайное изменение одной или нескольких позиций в хромосоме.

Чтобы смоделировать эволюционный процесс, сгенерируемвначале случайную популяцию — несколько индивидуумов со случайным наборомхромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этойпопуляции как циклический процесс скрещивания индивидуумов и смены поколений.

Жизненныйцикл популяции — это несколько случайных скрещиваний (посредством кроссовера) имутаций, в результате которых к популяции добавляется какое-то количество новыхиндивидуумов.

Отборв генетическом алгоритме — это процесс формирования новой популяции из старой,после чего старая популяция погибает. После отбора к новой популяции опятьприменяются операции кроссовера и мутации, затем опять происходит отбор, и такдалее.

Отборв генетическом алгоритме тесно связан с принципами естественного отбора вприроде следующим образом:

Приспособленность
индивидуума

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

Выживание наиболее
приспособленных

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

Такимобразом, модель отбора определяет, каким образом следует строить популяциюследующего поколения. Как правило, вероятность участия индивидуума вскрещивании берется пропорциональной его приспособленности. Часто используетсятак называемая стратегия элитизма,при которой несколько лучших индивидуумов переходят в следующее поколение безизменений, не участвуя в кроссовере и отборе. В любом случае каждое следующеепоколение будет в среднем лучше предыдущего. Когда приспособленностьиндивидуумов перестает заметно увеличиваться, процесс останавливают и вкачестве решения задачи оптимизации берут наилучшего из найденных индивидуумов.

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

Индивидуум = вариант решения задачи = набор из 10 хромосом Хj Хромосома Хj= объем вложения в проект j = 16-разрядная запись этого числа Так как объемы вложений ограничены, не все значения хромосом являются допустимыми. Это учитывается при генерации популяций. Так как суммарный объем инвестиций фиксирован, то реально варьируются только 9 хромосом, а значение 10-ой определяется по ним однозначно.

Подробное описание генетического aлгоритма

1.Создание структуры решения искомой задачи в виде массива a[i], i = 1,… .n, где n — максимальное число компонент структуры. Пример:поиск функции y=f(x) наилучшего в классе полиномов приближенияэкспериментальных точек {xi, yi}, j=1,...,m.
Структура определяется битовым массивом, где каждому элементу массивасопоставлен простейший многочлен типа xi, i=1,...n, где n — максимальная степень полинома.

2.Создание показателя эффективности структуры, заполненной конкретнымизначениями. Пример:Показателем эффективности для нашего примера будет невязка определенная методомнаименьших квадратов Ja=I1+I2+..+Im,где Ij=(yj–fa(xj))2,
где fa(x) есть сумма всех элементов вида aixi, где ai = 0 или 1

3.Задание некоторого массива различных структур Sk, k=1,...,N,размерностью N, большей, чем число компонент n в структуре
Данный массив можно сгенерировать случайно, задав нули и единицы в каждойструктуре.

4.Расчет показателей эффективности Jk для каждой структуры Sk.По формуле заданной в пункте 2.

5.Естественный отбор структур по некоторому правилу выбора наилучших структурсреди заданного массива структур. Пример:можно по правилу вида J0=M(Jk) — среднее значение Jk,если Jk<J0, то структура остается, иначе умирает. Еслиразница между предыдущим J0 и новым J0 меньше какого-томалого числа, то конец расчета.

6. Замена выбывших структурна новые, рожденные от наиболее приспособленных структур с помощью генетическихоператоров

а.) мутация — замена в структуре одногоиз значений случайно выбранной компоненты
Пример: из (1, 1, 0,1,, 0, 1, 0)получится (1, 1, 0, 1, 1,0, 1, 0).

б.)инверсия — перестановка вструктуре некоторой ее части наоборот
Пример: из (1, 1, 0, 1, 0, 0, 1, 0) получится (1, 1, 0, 0, 1, 0, 1, 0).

в.) кроссинговер — создание структуры,основанной на двух структурах — заменой одной части первой структуры на ту жеобласть во второй.
Пример: из (A, B, C, D, E) и (a, b, c, d, e) получится (A, B, c, d, E).

7. Переход к этапу 4.

Влияние параметров генетического алгоритма на эффективность поиска

Операторы кроссовера и мутации

Наиболее традиционным подходом является отход оттрадиционной схемы «размножения», используемой в большинствереализованных ГА-мах и повторяющих классическую схему. Классическая схемапредполагает ограничение численности потомков путем использования такназываемой вероятности кроссовера. Такая модель придает величине,соответствующей численности потомков, вообще говоря, недетерминированныйхарактер. Есть метод предлагающий отойти от вероятности кроссовера ииспользовать фиксированное число брачных пар на каждом поколении, при этомкаждая брачная пара «дает» двух потомков. Такой подход хорош тем, чтоделает процесс поиска более управляемым и предсказуемым в смыслевычислительных затрат.

В качестве генетических операторов получения новых генотипов«потомков», используя генетическую информацию хромосомных наборовродителей мы применяются два типа кроссоверов — одно- и двухточечный.Вычислительные эксперименты показали, что даже для простых функций нельзяговорить о преимуществе того или иного оператора. Более того было показано, чтоиспользование механизма случайного выбора одно- или двух точечного кроссоверадля каждой конкретной брачной пары подчас оказывается более эффективным, чемдетерминированный подход к выбору кроссоверов, поскольку достаточно трудноопределить который из двух операторов более подходит для каждого конкретноголандшафта приспособленности. Использование же случайного выбора преследовалоцелью прежде всего сгладить различия этих двух подходов и улучшить показателисреднего ожидаемого результата. Для всех представленных тестовых функций так ипроизошло, — случайного выбор оказался эффективнее худшего.

Повышение эффективности поиска при использованиислучайного выбора операторов кроссовера повлияло на то, чтобы применить аналогичныйподход при реализации процесса мутагинеза новых особей, однако в этом случаепреимущество перед детерминированным подходом не так очевидно в силутрадиционно малой вероятности мутации. В основном вероятность мутациисоставляет 0.001 — 0.01.

Выбор родительской пары

Первыйподход самый простой — это случайный выбор родительской пары ("панмиксия"),когда обе особи, которые составят родительскую пару, случайным образомвыбираются из

всей популяции, причем любаяособь может стать членом нескольких пар. Несмотря на простоту, такой подходуниверсален для решения различных классов задач. Однако он достаточно критиченк численности популяции, поскольку эффективность алгоритма, реализующего такойподход, снижается с ростом численности популяции.
Второй способ выбора особей в родительскую пару — так называемый селективный.Его суть состоит в том, что «родителями» могут стать только те особи,значение приспособленности которых не меньше среднего значенияприспособленности по популяции, при равной вероятности таких кандидатовсоставить брачную пару. Такой подход обеспечивает более быструю сходимостьалгоритма. Однако из-за быстрой сходимости селективный выбор родительской парыне подходит тогда, когда ставиться задача определения нескольких экстремумов,поскольку для таких задач алгоритм, как правило, быстро сходится к одному изрешений. Кроме того, для некоторого класса задач со сложным ландшафтомприспособленности быстрая сходимость может превратиться в преждевременнуюсходимость к квазиоптимальному решению. Этот недостаток может быть отчастикомпенсирован использованием подходящего механизма отбора (о чем будет сказанониже), который бы «тормозил» слишком быструю сходимость алгоритма.
Другие два способа формирования родительской пары, на которые хотелось бы обратитьвнимание, это инбридинг и аутбридинг. Оба эти метода построены наформировании пары на основе близкого и дальнего «родства»соответственно. Под «родством» здесь понимается расстояние междучленами популяции как в смысле геометрического расстояния особей в пространствепараметров. В связи с этим будем различать генотипный и фенотипный (илигеографический) инбридинг и аутбридинг. Под инбридингом понимается такой метод,когда первый член пары выбирается случайно, а вторым с большей вероятностьюбудет максимально близкая к нему особь. Аутбридинг же, наоборот, формируетбрачные пары из максимально далеких особей. Использование генетическихинбридинга и аутбридинга оказалось более эффективным по сравнению сгеографическим для всех тестовых функций при различных параметрах алгоритма.Наиболее полезно применение обоих представленных методов для многоэкстремальныхзадач. Однако два этих способа по-разному влияют на поведение генетическогоалгоритма. Так инбридинг можно охарактеризовать свойством концентрации поиска влокальных узлах, что фактически приводит к разбиению популяции на отдельныелокальные группы вокруг подозрительных на экстремум участков ландшафта,напротив аутбридинг как раз направлен на предупреждение сходимости алгоритма куже найденным решениям, заставляя алгоритм просматривать новые, неисследованныеобласти.

Механизм отбора

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

Идея элитного отбора, в общем, не нова, этот методоснован на построении новой популяции только из лучших особей репродукционнойгруппы, объединяющей в себе родителей, их потомков и мутантов. В основном этообъясняют потенциальной опасностью преждевременной сходимости, отдаваяпредпочтение пропорциональному отбору. Быстрая сходимость, обеспечиваемаяэлитным отбором, может быть, когда это необходимо, с успехом компенсированаподходящим методом выбора родительских пар, например аутбридингом. Именно такаякомбинация «аутбридинг — элитный отбор» является одной из наиболееэффективных.

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

Особенности генетических алгоритмов

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

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

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

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

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

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

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

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

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

/> На рисункепоказано, что такая комбинация позволяет обеспечить устойчиво хорошуюэффективность генетического поиска для любых типов задач.

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

Литература и Ссылки:

/>Генетическиеалго/>ритмы по-русски www.chat.ru/~saisa

НейроПроект. Аналитические технологии XXI века http://www.neuroproject.ru

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

Факультет вычислительнойматематики и кибернетики МГУ (ВМиК)

cmc.cs.msu.su/labs/lvk/materials/tez_sapr99_1.html

Neural BenchDevelopment www.neuralbench.ru/rus/theory/genetic.htm

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

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

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

Генетические алгоритмы имашинное обучение
www.math.tsu.ru/russian/center/ai_group/ai_collection/docs/faqs/ai/part5/faq3.html

Компьютерра | 11/1999 |Генетические алгоритмы: почему они работают?