Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

ГОУ ВПО «Северо-Кавказский государственный технический университет»

Факультет информационных технологий и телекоммуникаций

Курсовая работа

на тему:

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

Автор дипломного проекта

Костроминов Владимир Валерьевич

Специальность 090105

«Комплексное обеспечение информационной безопасности

автоматизированных систем»

Группа БАС-081

Руководитель работы Р. А. Воронкин

Ставрополь, 2011

Введение

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

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

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

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

Целью данной работы является рассмотрение генетических алгоритмов.

Задача: Реализовать работу генетического алгоритма.

1. Генетические алгоритмы

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

Идею генетических алгоритмов высказал Дж. Холланд в конце 60-х начале 70-х годов XX века. Он заинтересовался свойствами процессов естественной эволюции, в том числе фактом, что эволюционируют хромосомы, а не сами живые существа. Холланд был уверен в возможности составить и реализовать в виде компьютерной программы алгоритм, который будет решать сложные задачи так, как это делает природа - путем эволюции. Поэтому он начал трудиться над алгоритмами, оперировавшими последовательностями двоичных цифр (единиц и нулей), получившими название хромосом. Эти алгоритмы имитировали эволюционные процессы в поколениях таких хромосом. В них были реализованы механизмы селекции и репродукции, аналогичные применяемым при естественной эволюции. Так же, как и в природе, генетические алгоритмы осуществляли поиск "хороших" хромосом без использования какой-либо информации о характере решаемой задачи. Требовалась только некая оценка каждой хромосомы, отражающая ее приспособленность. Механизм селекции заключается в выборе хромосом с наивысшей оценкой (т.е. наиболее приспособленных), которые репродуцируют чаще, чем особи с более низкой оценкой (хуже приспособленные). Репродукция означает создание новых хромосом в результате рекомбинации генов родительских хромосом. Рекомбинация - это процесс, в результате которого возникают новые комбинации генов. Для этого используются две операции: скрещивание, позволяющее создать две совершенно новые хромосомы потомков путем комбинирования генетического материала пары родителей, а также мутация, которая может вызывать изменения в отдельных хромосомах.

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

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

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

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

1.1 Реализация генетических алгоритмов

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

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

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

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

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

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

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

останов:= FALSE

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

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

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

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

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

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

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

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

КОНЕЦ

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

КОНЕЦ

КОНЕЦ

Схема 1.1. Реализация генетического алгоритма

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

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

1.2 Применение генетических алгоритмов

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

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

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

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

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

1.3 Символьная модель простого генетического алгоритма

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

Структура данных генетического алгоритма состоит из одной или большее количество хромосом. Как правило, хромосома - это битовая строка, так что термин строка часто заменяет понятие "хромосома". В принципе, генетические алгоритмы не ограничены бинарным представлением. Известны другие реализации, построенные исключительно на векторах вещественных чисел. Несмотря на то, что для многих реальных задач, видимо, больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены. Пока и мы ограничимся только структурам, которые являются одиночными строками по l бит.

Каждая хромосома (строка) представляет собой конкатенацию ряда подкомпонентов называемых генами. Гены располагаются в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями. В представлениях с бинарными строками, ген - бит, локус - его позиция в строке, и аллель, его значение (0 или 1). Биологический термин "генотип" относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме. Термин "фенотип" относится к внешним наблюдаемым признакам и соответствует вектору в пространстве параметров. Чрезвычайно простой, но иллюстративный пример - задача максимизации следующей функции двух переменных:

(1)

Обычно, методика кодирования реальных переменных x1 и x2 состоит в их преобразовании в двоичные целочисленные строки достаточной длины, достаточной для того, чтобы обеспечить желаемую точность. Предположим, что 10 разрядное кодирование достаточно и для x1 и x2. Установить соответствие между генотипом и фенотипом закодированных особей можно, разделив соответствующее двоичное целое число на 2??-1. Например, 0000000000 соответствует 0/1023 или 0, тогда как 1111111111 соответствует 1023/1023 или 1. Оптимизируемая структура данных 20 битная строка, представляющая конкатенацию кодировок x1 и x2. Переменная x1 размещается в крайних левых 10 разрядах, тогда как x2 размещается в правой части генотипа особи (20 битовой строке). Генотип - точка в 20 мерном хеммининговом пространстве, исследуемом генетическим алгоритмом. Фенотип - точка в двумерном пространстве параметров.

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

1.4 Работа простого генетического алгоритма

Простой генетический алгоритм случайным образом генерирует начальную популяцию структур. Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий остановки. На каждом поколении генетического алгоритма реализуется отбор пропорционально приспособленности, одноточечный кроссовер и мутация. Сначала, пропорциональный отбор назначает каждой структуре вероятность Ps(i) равную отношению ее приспособленности к суммарной приспособленности популяции:

(2)

Затем происходит отбор (с замещением) всех n особей для дальнейшей генетической обработки, согласно величине Ps(i). Простейший пропорциональный отбор - рулетка, отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-го сектора пропорционален соответствующей величине Ps(i). При таком отборе члены популяции с более высокой приспособленностью с большей вероятность будут чаще выбираться, чем особи с низкой приспособленностью.

После отбора, n выбранных особей подвергаются кроссоверу (иногда называемому рекомбинацией) с заданной вероятностью Pc. n строк случайным образом разбиваются на n/2 пары. Для каждой пары с вероятность Pc может применяться кроссовер. Соответственно с вероятностью 1-Pc кроссовер не происходит и неизмененные особи переходят на стадию мутации. Если кроссовер происходит, полученные потомки заменяют собой родителей и переходят к мутации.

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

Например, предположим, один родитель состоит из 10 нолей, а другой из 10 единиц. Пусть из 9 возможных точек разрыва выбрана точка 3. Родители и их потомки показаны ниже в таблице 1.1:

Кроссовер
Родитель 1	0000000000	000~0000000	-->	111~0000000	1110000000	Потомок 1
Родитель 2	1111111111	111~1111111	-->	000~1111111	0001111111	Потомок 2

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

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

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

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

1.5 Шима (schema)

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

Шима - это строка длины 1 (что и длина любой строки популяции), состоящая из знаков алфавита {0; 1; *}, где {*} - неопределенный символ. Каждая шима определяет множество всех бинарных строк длины 1, имеющих в соответствующих позициях либо 0, либо 1, в зависимости от того, какой бит находится в соответствующей позиции самой шимы. Например, шима, 10**1, определяет собой множество из четырех пятибитовых строк {10001; 10011; 10101; 10111}. У шим выделяют два свойства - порядок и определенная длина. Порядок шимы - это число определенных битов в шиме. Определенная длина - расстояние между крайними определенными битами в шиме. Например, вышеупомянутая шима имеет порядок o(10**1) = 3, а определенная длина d(10**1) = 4. Каждая строка в популяции является примером шим.

Строящие блоки

Строящие блоки - это шимы обладающие:

1. высокой приспособленностью;

2. низким порядком;

3. короткой определенной длиной.

Приспособленность шимы определяется как среднее приспособленностей примеров, которые ее содержат.

После процедуры отбора остаются только строки с более высокой приспособленностью. Следовательно, строки, которые являются примерами шим с высокой приспособленностью, выбираются чаще. Кроссовер реже разрушает шимы с более короткой определенной длиной, а мутация реже разрушает шимы с низким порядком. Поэтому такие шимы имеют больше шансов переходить из поколения в поколение. Голланд показал, что в то время как генетический алгоритм явным образом обрабатывает n строк на каждом поколении, в тоже время неявно обрабатываются порядка таких коротких шим низкого порядка и с высокой приспособленностью (полезных шим, "useful schemata"). Он называл это явление неявным параллелизмом. Для решения реальных задач, присутствие неявного параллелизма означает, что большая популяция имеет больше возможностей локализовать решение экспоненциально быстрее популяции с меньшим числом особей.

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

Пусть m(H,t) - число примеров шимы H в t-ом поколении. Вычислим ожидаемое число примеров H в следующем поколении или m(H,t+1) в терминах m(H,t). Простой генетический алгоритм каждой строке ставит в соответствие вероятность ее "выживания" при отборе пропорционально ее приспособленности. Ожидается, что шима H может быть выбрана m(H,t)Ч (f(H)/fср.) раз, где fср. - средняя приспособленность популяции, а f(H) - средняя приспособленность тех строк в популяции, которые являются примерами H.

Вероятность того, что одноточечный кроссовер разрушит шиму равна вероятности того, что точка разрыва попадет между определенными битами. Вероятность же того, что H "переживает" кроссовер не меньше 1-Pc_ (d(H)/l-1). Эта вероятность - неравенство, поскольку шима сможет выжить если в кроссовере участвовал также пример похожей шимы. Вероятность того, что H переживет мутацию - (1-Pm) o(H), это выражение можно аппроксимировать как (1-o(H)) для малого Pm и o(H). Произведение ожидаемого число отборов и вероятностей выживания известно как теорема шим:

(3)

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

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

Несмотря на простоту, теорема шим описывает несколько важных аспектов поведения генетических алгоритмов. Мутации с большей вероятностью разрушают шимы высокого порядка, в то время как кроссовера с большей вероятность разрушают шимы с большей определенной длиной. Когда происходит отбор, популяция сходится пропорционально отношению приспособленности лучшей особи, к средней приспособленности в популяции; это отношение - мера давления отбора. Увеличение или Pc, или Pм, или уменьшении давления отбора, ведет к увеличенному осуществлению выборки или исследованию пространства поиска, но не позволяет использовать все хорошие шимы, которыми располагает генетический алгоритм. Уменьшение или Pc, или Pм, или увеличение давления выбора, ведет к улучшению использования найденных шим, но тормозит исследование пространства в поисках новых хороших шим. Генетический алгоритм должен поддержать тонкое равновесие между тем и другим, что обычно известно как проблема "баланса исследования и использования".

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

1.6 Вывод

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

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

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

2. Задачи оптимизации

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

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

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

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

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



Рисунок 2.1 Кратчайший путь

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

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

Рисунок 1.2 Переборный метод

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

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

Рисунок 2.2 Метод градиентного спуска

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

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

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

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

В интерфейсе программы необходимо предусмотреть возможность ввода параметров:

1. объём популяции;

2. число поколений;

3. коэффициент скрещивания;

4. коэффициент мутации;

5. для дифференциального кроссовера коэффициенты k,c;

6. для задачи коммивояжёра ввод [4. .40] числа городов и их расстановку вручную и автоматически;

7. для биологической задачи возможность ввода названий характеристик [10.15], их значений [4. .40], значимости и веса [0.1] каждой характеристики.

8. Результаты работы программы должны включать:

9. на каждом шаге отображать номер поколения и лучшее значение фитнес-функции в этом поколении;

10. лучшее значение фитнес-функции за все поколения и соответствующую ей структуру особи;

11. для биологической задачи и задачи оптимизации функции график зависимости значения целевой функции от номера поколения;

12. для задачи коммивояжёра на каждом поколении графически отображать лучший маршрут.

Анализ результатов моделирования на основе разработанной программы представляется в виде таблицы:

оптимизация генетический алгоритм адаптивный

№ эксперимента	Кол- во маршрутов	Число поколений	Коэф. скрещивания	Коэф. мутации	Фитнес- Функция (min)
1	100	500	0,5	0,001	3110
2	150	500	0,5	0,001	2783
3	200	500	0,5	0,001	2697
4	200	1000	0,5	0,001	3034
5	200	1500	0,5	0,001	2817
6	200	2000	0,5	0,001	3088
7	200	500	1	0,001	3282
8	200	500	1,5	0,001	3296
9	100	500	1	0,001	3334
10	100	500	0,5	0,01	3025
11	200	500	0,5	0,01	2511
12	100	500	1	0,01	2852
13	200	500	1	0,01	2749
14	100	500	0,5	0,1	3221
15	200	500	1	0,1	2497

Анализируя полученные результаты моделирования приходим к выводу, что оптимальным количеством маршрутов можно считать 200, число поколений, нет необходимости повторять алгоритм больше 500 раз (поколений), чтобы получить хороший результат. Также на значение фитнес-функции влияет коэффициент скрещивания: оптимальный коэффициент скрещивания - 1, коэффициент мутации также играет большую роль в моделировании генетического алгоритма, оптимальный коэффициент мутации - 0,1. Как видно из таблицы самое лучшее значение фитнес-функции, а значит самое минимальное расстояние за которое можно объехать 20 городов, получают за счет параметров, которые указаны в таблице в строке под номером 15.

2.3 Вывод

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

Заключение

В результате курсовой работы был разработан и реализован генетический алгоритм. Среди наиболее значимых положительных сторон генетических алгоритмов можно отметить:

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

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

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

Наряду с генетическими алгоритмами известны и другие методы решения задач оптимизации, основанные на природных механизмах, такие как моделирование отжига (simulated annealing) и табу-поиск (taboo search). Но эффект случайности, который безусловно присутствует при решении генетическим алгоритмом, очень воодушевляет.

Список использованных источников

1. Галушкин А. Современные направления развития нейрокомпьютерных технологий в России // Открытые системы. - 1997 г., №4.

2. Каллан Р. Основные концепции нейронных сетей. М.: Вильямс 2002 г.

3. Комарцова Л.Г., Максимов А.В. Нейрокомпьютеры: Учеб. пособие для вузов. - 2-е изд., перераб. и доп. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2004. - 400 с: ил.

4. Логовский А. Новейшая история нейрокомпьютинга в России //Открытые системы. - 2001 г., №3.

5. Оссовский С. Нейронные сети для обработки информации / Пер. с польского И.Д. Рудинского. - М.: Финансы и статистика, 2002. - 344 с: ил.

6. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И. Д. Рудинского. - М.: Горячая линия -Телеком, 2006. - 452 с: ил.

7. Стюарт Рассел, Питер Норвиг. Искусственный интеллект: современный подход. 2-е издание М., Вильямс 2006 г.

8. Тархов Д.А. Нейронные сети. Модели и алгоритмы. Изд: Радиотехника. 2005 г.

9. Уоссермен Ф. Нейрокомпьютерная техника. Теория и практика. М.: Мир, 1992 г.

10. Яхъяева Г. Э. Нечеткие множества и нейронные сети: Учебное пособие /Г. Э. Яхъяева. - М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2006.

Приложение 1

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls;

type

TForm1 = class (TForm)

Image1: TImage;

Button1: TButton;

Edit1: TEdit;

Label1: TLabel;

Edit2: TEdit;

Label2: TLabel;

Edit3: TEdit;

Label3: TLabel;

Edit4: TEdit;

Label4: TLabel;

Edit5: TEdit;

Label5: TLabel;

procedure Image1MouseDown (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

procedure Image1Click (Sender: TObject);

procedure FirstGeneration (Sender: TObject);

procedure CreaChildren (Sender: TObject);

procedure Mutation (Sender: TObject);

procedure TrackRead (Sender: TObject);

procedure DrawMarsh (Sender: TObject);

function CrossOver (p,m: integer): string;

procedure Mixer (Sender: TObject);

procedure Button1Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

pX,pY,elite: array of integer; // координаты городов, элитные

road: array of integer;

parents: array of string; // поколений родителей, детей; результат

child: array of string;

result: array of string;

gl: integer; // количество элитных

nCity,nMarsh: integer; // количество городов, маршрутов

kMut,kCross: real; // коэффициент мутации, скрещивания

implementation

{$R *. dfm}

procedure TForm1. Mixer (Sender: TObject);

var

i,j,n,k: integer;

s: string;

label lbl4;

BEGIN

n: =round ( (nMarsh) *kCross) - 1;

for i: =0 to nMarsh-1 do

begin

setLength (child,n+i+2);

child [n+i+1]: =parents [i] ;

end;

TrackRead (sender);

setlength (elite,1);

s: ='_';

{1}for i: =0 to nMarsh-1 do

begin

lbl4:

elite [0]: =random (n+nMarsh);

if pos ('_'+inttostr (elite [0]) +'_',s) <>0 then goto lbl4;

for j: =0 to n+nMarsh-1 do

begin

if pos ('_'+inttostr (j) +'_',s) =0 then

begin

if road [elite [0]] >road [j] then

begin

elite [0]: =j;

end;

end;

end;

s: =s+inttostr (elite [0]) +'_';

parents [i]: =child [elite [0]] ;

{1}end;

END;

function TForm1. CrossOver (p,m: integer): string;

var

gen: char;

i,j: integer; // счетчика

t1,t2: integer; // точки кроссовера

nC,kC: integer; // границы цикла

papa,mama: string;

label lbl3;

BEGIN

papa: =parents [p] ;

mama: =parents [m] ;

randomize;

t1: =random (nCity-1) +1; // выбираем 1 точку

lbl3:

t2: =random (nCity-1) +1; // выбираем 2 точку

if t2=t1 then goto lbl3; // 1 точка не 2 точка

if t1<t2 then // выбираем границы цикла

begin

nC: =t1;

kC: =t2;

end

else

begin

nC: =t2;

kC: =t1;

end;

for i: =nC to kC do // цикл скрещивания

begin

if pos (mama [i],papa) =0 then // проверка на совпадение генов

begin

delete (papa, i,1);

insert (mama [i],papa, i); // добавляем материнские гены

end

else

begin // изменяем повторившийся ген

gen: =papa [i] ;

papa [i]: =papa [i+1] ;

papa [i+1]: =gen;

end;

end;

crossover: =papa; // возварщаем значение функции потомка

END;

procedure TForm1. TrackRead (Sender: TObject);

var

i,j: integer;

p1,p2: integer;

p: string;

BEGIN

{1}for i: =0 to length (child) - 1 do // большой цикл по маршрутам

begin

setlength (road, i+1);

p: ='';

p: =child [i] ;

{2}for j: =1 to nCity-1 do // внутренний цикл по городам маршрутов

begin

if j<>nCity-1 then // проверка на последний город

begin

p1: =StrToInt (p [j]); //

p2: =StrToInt (p [j+1]); // соседний

end

else

begin

p1: =StrToInt (p [j+1]); // последний

p2: =StrToInt (p [1]); // первый

end; // расчет расстояния

road [i]: =road [i] +round (sqrt (sqr (pX [p1] -pX [p2]) +sqr (pY [p1] -pY [p2])));

{2}end;

{1}end;

END;

procedure TForm1. DrawMarsh (Sender: TObject);

var

i,j: integer;

p1,p2: integer;

p: string;

BEGIN

p: =parents [0] ;

Image1. CleanupInstance;

with Image1. Canvas do

begin

for j: =1 to nCity do // внутренний цикл городам маршрута

begin

if j=nCity then

begin

p1: =StrToInt (p [j]);

p2: =StrToInt (p [1]);

end

else

begin

p1: =StrToInt (p [j]);

p2: =StrToInt (p [j+1]);

end;

MoveTo (pX [p1],pY [p1]);

LineTo (pX [p2],pY [p2]);

end;

end;

END;

procedure TForm1. Mutation (Sender: TObject);

var

i,ran: integer; // счетчик, случайное число

gen: char; // мутирующий ген

mutant: string;

BEGIN

mutant: ='';

for i: =0 to round ( (nMarsh) *kCross) - 1 do // цикл мутации

begin

randomize;

if kMut<random (10) /100 then // проверка на мутацию

begin

mutant: =child [i] ; // мутирующая особь

ran: =random (nCity-1);

gen: =mutant [ran] ; //

mutant [ran]: =mutant [ran+1] ; // мутируем

mutant [ran+1]: =gen; //

child [i]: =mutant;

end;

end;

END;

procedure TForm1. FirstGeneration (Sender: TObject);

var

i,j,ram: integer; // счетчики, рандомное значение

s: string; // строка маршрута

label lbl1; // метка

BEGIN

randomize;

for i: =0 to nMarsh-1 do // цикл формирования первого поколения

{1}begin

s: ='';

setlength (parents, i+1); // устанавливаем длину массива родителей

for j: =0 to nCity-1 do // цикл формирования строки маршрута

{2}begin

setlength (s,j+1); // устанавливаем длину строки маршрута

lbl1:

ram: =random (nCity); // случайный выбор номера города

if pos (IntToStr (ram),s) =0 then // проверка на повтор номера города

begin

insert (IntToStr (ram),s,1); // добавление номера города в строку маршрута

end

else goto lbl1; // переход на метку

{2}end;

parents [i]: =s; // заполняем массив родителей (первое поколение)

{1}end;

END;

procedure TForm1. CreaChildren (Sender: TObject);

var

i: integer; // счетчики

p,m: integer; // номера родителей

label lbl2;

BEGIN

randomize;

for i: =0 to round ( (nMarsh) *kCross) - 1 do // цикл создания пар

begin

setlength (child, i+1);

p: = random (nMarsh); // выбираем номер папы

lbl2:

m: = random (nMarsh); // выбираем номер мамы

if m=p then goto lbl2; // папа не мама

child [i]: =crossover (p,m); // создаем потомков

end;

END;

procedure TForm1. Image1Click (Sender: TObject);

begin

inc (nCity); // считаем города

end;

procedure TForm1. Image1MouseDown (Sender: TObject; Button: TMouseButton;

Shift: TShiftState; X, Y: Integer);

begin

// // /

with Image1. Canvas do

begin

Brush. Color: =clRed;

Brush. Style: =bsSolid;

Rectangle (x-5,y-5,x+5,y+5);

Brush. Color: =clWhite;

TextOut (x,y, inttostr (nCity));

end;

// // /

SetLength (pX,nCity+1);

pX [nCity]: =x;

SetLength (py,nCity+1);

pY [nCity]: =y;

// // /

end;

procedure TForm1. Button1Click (Sender: TObject);

var

i,nPokol: integer;

begin

nMarsh: =StrToInt (Edit3. Text);

kMut: =StrToFloat (Edit2. Text);

kCross: =StrToFloat (Edit4. Text);

nPokol: =StrToInt (Edit5. Text);

FirstGeneration (sender);

for i: =1 to nPokol do

begin

CreaChildren (sender);

Mutation (sender);

Mixer (sender);

DrawMarsh (sender);

end;

end;

end.

Размещено на Allbest.ru