Готовая курсовая работа

Генетические операторы



Генетический алгоритм включает три операции: селекция, скрещивание, мутация.

Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир.

• Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n \"запусков\" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален соответствующей величине Psel(i) вычисляемой по формуле:



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





Рис. 2. Оператор селекции типа колеса рулетки

с пропорциональными функции приспособленности секторами



• Турнирный отбор (tou
ament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

В данной работе реализован турнирный отбор.

Для выполнения отбора используются вспомогательные подпрограммы – процедура shuffle, «перемешивающая» популяцию (меняющая местами особи) и функция select1, выбирающая одну более приспособленную особь из двух (сравниваются соседние особи, когда достигнут конец популяции – они перемешиваются и отбор начинается с первой особи). Основная процедура select осуществляет отбор требуемого количества особей за счет вызова функции select1 внутри цикла.

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

Схема скрещивания представлена на рисунке 3.





Рис. 3. Схема скрещивания





При скрещивании происходит случайный выбор позиции разделителя d (d=1, 2, ..., l-1, где l - длина строки). Затем значения первых d элементов первой строки записываются в соответствующие элементы второй, а значения первых d элементов второй строки - в соответствующие элементы первой. В результате получаем две новых строки, каждая из которых является комбинацией частей двух родительских строк.

Наряду с одноточечным может быть рассмотрено многоточечное скрещивание.

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

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

Мутация представляет собой процесс случайного изменения значений элементов строки. Для этого строки, получившиеся на этапе скрещивания, просматриваются поэлементно, и каждый элемент с заданной вероятностью мутации pмут может мутировать, т.е. изменить значение на любой случайно выбранный символ, допустимый для данной позиции. В случае, когда элемент может принять только одно из двух значений (0 и 1, истина и ложь) говорят об инверсионной мутации – значение может измениться только на противоположное, т.е. происходит инверсия.

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

Схема мутации представлена на рисунке 4.





Рис.4. Схема мутации



В данной работе мутация инверсионная, осуществляется с помощью функции mutation. Внутри данной функции с помощью функции flip определяется, необходимо ли проводить мутацию (она происходит с заданной вероятностью – pmutation). Если необходимость есть, функция возвращает значение аллели, обратное переданному как параметр. Если нет необходимости, возвращаемая аллель совпадает с переданной.



Фитнес-функция

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

Для оценки качества хромосом применяется специальная фитнес-функция, на входе которой – хромосома, а на выходе – ее оценка. В генетических алгоритмах никак не используются такие свойства функции, как непрерывность, дифференцируемость и т. д. Она подразумевается как устройство (blackbox), которое на вход получает параметры, а на выход выводит результат.

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

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

Фитнес-функция - это единственная часть программы, которая должна понимать, что же на самом деле кодирует хромосома. Поэтому для каждого приложения надо писать новые фитнес-функции. К счастью, они обычно довольно просты, особенно по сравнению с программой, которая могла бы понадобиться для полного решения задачи. Очень трудно написать программу, которая строит расписания работы экипажей для автобусных компаний. Очень легко написать процедуру, которая подсчитывает количество шоферов и оценивает те расписания, где заняты (читай: оплачиваются) меньше шоферов, выше, чем те, где шоферов нужно больше. Для ряда приложений генетические алгоритмы приближаются к мифической системе \"дай описание задачи и жди готового решения\".

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

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

Введение 4

Понятие генетического алгоритма 6

Генетические операторы 9

Фитнес-функция 12

Выводы 14

Заключение 16

Литература 17

Приложение А 18





Введение

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

Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как \"Происхождение Видов\", в 1859 году, стала началом этого изменения. XIX веке Чарльз Дарвин совершил кругосветное плавание, собирая информацию для теории эволюции на основе естественного отбора, при котором выживает сильнейший. Мог ли он предполагать, что сто лет спустя математики будут использовать эту теорию для решения задачи об оптимальном маршруте кругосветного путешествия с остановками на многих маленьких островах?

Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как \"эволюционный синтез\" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, \"спуск с модификацией\". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.

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

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

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



Понятие генетического алгоритма

Генетические Алгоритмы - адаптивные методы поиска, которые в последнее время часто используются для решения задач функциональной оптимизации. Они основаны на генетических процессах биологических организмов: биологические популяции развиваются в течении нескольких поколений, подчиняясь законам естественного отбора и по принципу \"выживает наиболее приспособленный\" (survival of the fittest), открытому Чарльзом Дарвином. Подражая этому процессу генетические алгоритмы способны \"развивать\" решения реальных задач, если те соответствующим образом закодированы.

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

ГА используют прямую аналогию с таким механизмом. Они работают с совокупностью \"особей\" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее \"приспособленности\" согласно тому, насколько \"хорошо\" соответствующее ей решение задачи. Например, мерой приспособленности могло бы быть отношение силы/веса для данного проекта моста. (В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы.) Наиболее приспособленные особи получают возможность \"воспроизводить\" потомство с помощью \"перекрестного скрещивания\" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции.

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

Имеются много способов реализации идеи биологической эволюции в рамках ГА. Традиционным считается ГА, представленный на рисунке 1.

НАЧАЛО /* генетический алгоритм */

Создать начальную популяцию

Оценить приспособленность каждой особи

останов := FALSE

ПОКА НЕ останов ВЫПОЛНЯТЬ

НАЧАЛО /* создать популяцию нового поколения */

ПОВТОРИТЬ (размер_популяции/2) РАЗ

НАЧАЛО /* цикл воспроизводства */

Выбрать две особи с высокой приспособленностью из предыдущего поколения для скрещивания

Скрестить выбранные особи и получить двух потомков

Оценить приспособленности потомков

Поместить потомков в новое поколение

КОНЕЦ

ЕСЛИ популяция сошлась ТО останов := TRUE

КОНЕЦ

КОНЕЦ



Рис.1.1. Псевдокод





Рис.1.2. Блок-схема генетического алгоритма



Рис.1. Схема генетического алгоритма



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

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

1. Mitchell M. An Introduction to Genetic Algorithms. Cambridge, MA: The MIT Press, 1996

2. Thomas Back. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford: University Press, New York, 1996.

3. Аналитические технологии для прогнозирования и анализа данных // Нейропроект [Электронный ресурс]. – Режим доступа: http://www.neuroproject.ru/genealg.php - Загл. с экрана

4. Батищев Д.А. Генетические алгоритмы решения экстремальных задач. - Воронеж: Изд-во ВГТУ, 1995

5. Вороновский Г.К., и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности / Г.К.Вороновский, К.В.Махотило, С.Н.Петрашев, С.А.Сергеев. – Харьков: Основа, 1997

6. Генетические алгоритмы - математический аппарат// Методы оптимизации [Электронный ресурс]. – Режим доступа: http://www.basegroup.ru/library/optimization/ga_math/ - Загл. с экрана

7. Генетические алгоритмы //Дискретная математика: алгоритмы[Электронный ресурс]: портал Санкт-Петербургского Государственного Университета информационных технологий, механики и оптики. – Режим доступа: http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005 - Загл. с экрана

8. Генетические операторы // Генетические алгоритмы [Электронный ресурс]. – Режим доступа: http://qai.narod.ru/GA/genoperators.html - Загл. с экрана

9. Генетический алгоритм: основные операции // Генетические алгоритмы [Электронный ресурс]. – Режим доступа: http://g-u-t.chat.ru/ga/oper.htm - Загл. с экрана

10. Емельянов В.В., Курейчик В.В., Курейчик В.М. Теория и практика эволюционного моделирования. - М.:ФИЗМАТЛИТ, 2003

11. Исаев С. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов //Алголист [Электронный ресурс]. – Режим доступа: http://algolist.manual.ru/ai/ga/ga2.php - Загл. с экрана

12. Клемент Р. Генетические алгоритмы: почему они работают? когда их применять? //Компьютерра. №11 от 16 марта 1999 г. - С.57-64

13. Математические методы и алгоритмы / Под ред. В.П.Иванникова. – М.: ИСП РАН, 2004

14. Тимченко С.В. Информатика - 4, Учебно – методическое пособие по курсовому проекту. – Томск, 2004

15. Эволюционные вычисления // GetInfo [Электронный ресурс]: портал Компьютерной библиотеки GetInfo. / Yuri Burger. – Режим доступа: http://www.getinfo.ru/article31_2.html . – Загл. с экрана.