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

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

Содержание

Введение

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

2. Постановка задачи

3. Математическая модель генетического алгоритма

3.1 Описание используемых функций в программе

3.2 Блок-схема программы, реализующий генетический алгоритм

3.3 Текст программы, реализующей генетический алгоритм

4. Тестирование генетического алгоритма

Заключение

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



Введение

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

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

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

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

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

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

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

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

Цель ГА состоит в том, чтобы:

¦ абстрактно и формально объяснить адаптацию процессов в ЕС и интеллектуальной ИС;

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

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

ГА отличаются от других оптимизационных и поисковых процедур следующим:

¦ работают в основном не с параметрами задачи, а с закодированным множеством параметров;

¦ осуществляют поиск не путем улучшения одного решения, а путем использования сразу нескольких альтернатив на заданном множестве решений;

¦ используют целевую функцию (ЦФ), а не ее различные приращения для оценки качества принятия решений;

¦ применяют не детерминированные, а вероятностные правила анализа оптимизационных задач.

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

Приведем некоторые понятия и определения из теории ГА. Все ГА работают на основе начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция Р^t = {P₁ P₂.....P_i._, P_NP) есть множество элементов Р_i, t - 0, 1, 2... -- это номер генерации генетического алгоритма, N -- размер популяции. Каждый элемент этой популяции Р.. как правило, представляет собой одну или несколько хромосом или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов Р_i ={g₁,g₂,…,g_v} (элементы, части закодированного решения), и позиции генов в хромосоме называются лоци или локус для одной позиции, то есть ген -- подэлемент (элемент в хромосоме), локус -- позиция в хромосоме, аллель -- функциональное значение гена.

Гены могут иметь числовые или функциональные значения. Обычно эти числовые значения берутся из некоторого алфавита. Генетический материал элементов обычно кодируется на основе двоичного алфавита (0,1), хотя можно использовать буквенные, а также десятичные и другие алфавиты. Примером закодированной хромосомы длины девять на основе двоичного алфавита может служить хромосома Р_i = (001001101).

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

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

Каждый элемент в популяции имеет определенный уровень качества, который характеризуется значением ЦФ (в литературе иногда называется функция полезности, приспособленности или пригодности (fitness)). Эта функция используется в ГА для сравнения альтернативных решений между собой и выбора лучших.

Следовательно, основная задача генетических алгоритмов состоит в оптимизации целевой функции. Другими словами, ГА анализирует популяцию хромосом, представляющих комбинацию элементов из некоторого множества, и оптимизирует ЦФ, оценивая каждую хромосому. Генетические алгоритмы анализируют и преобразовывают популяции хромосом на основе механизма натуральной эволюции. Каждая популяция обладает наследственной изменчивостью. Это означает случайное отклонение от наиболее вероятного среднего значения ЦФ. Отклонение описывается нормальным законом распределения случайных величин. При этом наследственные признаки закрепляются, если они имеют приспособительный характер, то есть обеспечивают популяции лучшие условия существования и размножения.

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

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

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

При решении практических задач с использованием ГА обычно выполняют четыре предварительных этапа:

¦ выбор способа представления решения;

¦ разработка операторов случайных изменений;

¦ определение способов «выживания» решений;

¦ создание начальной популяции альтернативных решений.

Рассмотрим некоторые особенности выполнения этих этапов.

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

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

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

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

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

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

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

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

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

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

Генетический алгоритм состоит из набора генетических операторов.

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

Рассмотрим основные операторы генетических алгоритмов. Оператор репродукции (селекция) (OР) -- это процесс, посредством которого хромосомы (альтернативные решения), имеющие более высокое значение ЦФ (с «лучшими» признаками), получают большую возможность для воспроизводства (репродукции) потомков, чем «худшие» хромосомы. Элементы, выбранные для репродукции, обмениваются генетическим материалом, создавая аналогичных или различных потомков.

Существует большое число видов операторов репродукции. К ним относятся;

¦ Селекция на основе рулетки -- это простой и широко используемый в простом генетическом алгоритме (ПГА) метод. При его реализации каждому элементу в популяции соответствует зона на колесе рулетки, пропорционально соразмерная с величиной ЦФ. Тогда при повороте колеса рулетки каждый элемент имеет некоторую вероятность выбора для селекции. Причем элемент с большим значением ЦФ имеет большую вероятность для выбора.

¦ Селекция на основе заданной шкалы. Здесь популяция предварительно сортируется от «лучшей» к «худшей» на основе заданного критерия. Каждому элементу назначается определенное число и тогда селекция выполняется согласно этому числу.

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

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

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

¦ случайный выбор хромосом;

¦ выбор хромосом на основе значений целевой функции.

При случайном выборе хромосом частота R образования родительских пар не зависит от значения ЦФ хромосом Р_к^t и полностью определяется численностью популяции N:

где -- коэффициент селекции, принимающий в зависимости от условий внешней среды значение 1-4.

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

Для реализации первой стратегии при максимизацией ЦФ с вероятностью

P_r(OP)= , k от 1 до n

выбирают разные хромосомы. Здесь ОР -- это оператор репродукции, моделирующий естественный процесс селекции. Рr(ОР) -- вероятность выбора хромосом для репродукции.

Вторая стратегия реализуется так: часть хромосом выбирается случайным образом, а вторая -- с вероятностью на основе выражении (3.2).

Если ЦФ(Р_к^t) < ЦФ_ср,

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

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

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

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

Простой (одноточечный) ОК. Перед началом работы одноточечного оператора кроссинговера определяется так называемая точка ОК. или разрезающая точка, которая обычно определяется случайно. Эта точка определяет место в двух хромосомах, где они должны быть «разрезаны». Например. пусть популяция Р состоит из хромосом Р {Р₁, Р₂}, которые выступают в качестве родителей. Пусть первый и второй родители имеют вид Р₁: (11111), Р₂: (00000). Выберем точку ОК между вторым и третьим генами в Р₁, Р₂. Тогда, меняя элементы после точки ОК между двумя родителями, можно создать два новых потомка. В нашем примере получим:

Р₁ : 1 1 | 1 1 1 Р'₁ : 0 0 | 0 0 0

Р₂ : 1 1 | 0 0 0 Р'₂ : 0 0 | 1 1 1.

Итак, одноточечный ОК выполняется в три этапа:

1. Две хромосомы А = а₁, а₂,.., a _L и В = а'₁, а'₂,.., a'_L выбираются случайно из текущей популяции.

2. Число к выбирается из {1, 2, ..., L-1} также случайно. Здесь L -- длина хромосомы, к -- точка ОК (номер, значение или код гена, после которого выполняется разрез хромосомы).

3. Две новые хромосомы формируются из А и В путем перестановок элементов согласно правилу

A' = а₁, а₂,..., а'_k, а'_k+1, ,..., a'_L ,

В'=а'₁,а'₂,...,a'_k,а'_k+1,...,a'_L.

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

Двухточечный ОК. В каждой хромосоме определяются две точки ОК, и хромосомы обмениваются участками, расположенными между двумя точками ОК. Например:

Р₁ : 1 1 1 | 0 1 | 0 0

P₂ : 0 0 0 | 1 1 | 1 0

P'₁: 1 1 1 | 1 1 | 0 0

P'₂: 0 0 0 | 0 1 | 1 0

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

Р₁ : 1 | 1 1 | 0 1 | 0 0

Р₂ : 0 | 0 0 | 1 0 | 1 1

Р'₁ : 1 | 0 0 | 0 1 | 1 1

Р'₂ : 0 | 1 1 | 1 0 | 0 0.

Здесь точки ОК делят хромосому на ряд строительных блоков (в данном случае 4). Потомок Р'₁ образуется из нечетных блоков родителя Р₁ и четных блоков родителя Р₂. Потомок Р'₂ образуется соответственно из нечетных блоков родителя Р₂ и четных блоков родителя Р₂.

Тогда многоточечный ОК выполняется аналогичным образом.

Упорядоченный оператор кроссинговера. Здесь «разрезающая» точка также выбирается случайно. Далее происходит копирование левого сегмента Р₁ в Р'₁. Остальные позиции в P'₁ берутся из Р₂ в упорядоченном виде слева направо, исключая элементы, уже попавшие в Р'₁. Например:

Р₁: A B C D | E F G H

Р₂: С А В Е | C D F H

Р'₁ :А В С D | G E F Н.

Получение Р'₂ может выполняться различными способами. Наиболее распространенный метод копирования левого сегмента из Р₁, а далее анализ Р₂ методом, указанным выше. Тогда имеем Р'₂: (G А В Е | С D F Н).

Частично-соответствующий ОК. Здесь также случайно выбирается «разрезающая» точка или точка ОК. Дальше анализируются сегменты (части) в обеих хромосомах и устанавливается частичное соответствие между элементами первого и второго родителей с формированием потомков. При этом правый сегмент Р₂ переносится в Р'₁, левый сегмент Р, переносится в Р'₁ с заменой повторяющихся генов на отсутствующие гены, находящиеся в частичном соответствии. Например:

Р₁: A B C D E F | G H I J

Р₂: Е С I A D H | J B F G

Р'₁ : А Н С D Е I | J В F G.

Аналогично можно получить Р'₂:

Р₁ : A B C D E F | G H I J

Р₂ : Е С I A D H | J B F G

Р'₂ : Е С F A D В | G H I J.

Циклический ОК. Циклический ОК выполняет рекомбинации согласно циклам, которые существуют при установлении соответствия между генами первого и второго родителей. Например, пусть популяция Р состоит из двух хромосом Р - {Р₁, Р₂}. Первый и второй родители и их потомок имеют вид:

Р, : 1 2 3 4 5 6 7 8 9 10

Р₂ : 5 3 9 1 4 8 10 2 6 7

Р'₁ : 1 3 9 4 5 8 10 2 6 7.

При выполнении циклического ОК Р'₁ заполняется, начиная с первой позиции, и копирует элемент с первой позиции Р₁. Элементу 1 в Р₁ соответствует элемент 5 в Р₂. Следовательно, имеем первый путь в цикле (1,5). Элементу 5 в P₁ соответствует элемент 4 в Р₂. Имеем второй путь а первом цикле (1,5; 5,4). Продолжая далее, получим, что элементу 4 в Р₁ соответствует элемент 1 в Р₂ Следовательно, сформирован первый цикл(1,5; 5,4; 4,1). Согласно этому циклу элемент 5 переходит в пятую позицию P'₁, а элемент 4 -- в четвертую позицию. Сформируем теперь второй цикл. Элемент 2 в Р₁ соответствует элементу 3 в Р₂. Продолжая аналогично, получим второй цикл (2,3; 3.9; 9,6; 6,8; 8,2) и третий (7,10; 10.7) циклы. Следовательно, в Р'₁ элемент 3 расположен во втором локусе, то есть на второй позиции, элемент 9 -- в третьем, элемент 6 -- в девятом, элемент 8 -- в шестом, элемент 2 -- в восьмом, элемент 10 -- в седьмом и элемент 7 -- в десятом локусах. Циклический ОК и его модификации эффективно применяются для решения комбинаторно-логических задач на графах и гиперграфах и других оптимизационных задач.

Универсальный ОК. В настоящее время он популярен для решения различных задач из теории расписаний. Вместо использования разрезающей точки (точек) в универсальный ОК определяют двоичную маску, длина которой равна длине заданных хромосом. Первый потомок получается сложением первого родителя с маской на основе следующих правил (0+0=0, 0+1=1,1+1=0). Второй потомок получается аналогичным образом. Для каждого элемента в Р₁, P₂ гены меняются, как показано на следующем примере:

Р₁ : 0 1 1 0 0 1

Р₂: 0 1 0 1 1 1

0 1 1 0 1 0 -- маска

Р'₁: 0 0 0 0 1 1

Р'₂: 0 0 1 1 0 1.



Маска может быть задана или выбирается случайно с заданной вероятностью или на основе генератора случайных чисел. При этом чередование 0 и 1 в маске происходит с вероятностью «50%. В некоторых случаях используется параметризированный универсальный ОК, где маска может выбираться с вероятностью для 1 или 0 выше, чем 50%. Такой вид маски эффективен, когда хромосомы кодируются в двоичном алфавите.

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

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

Оператор мутации обычно состоит из двух этапов:

1. В хромосоме А = (а₁, а₂, а₃,...,a _L-2,a _L-1, a _L) определяются случайным образом две позиции (например, а₂ и а_L-1).

2. Гены, соответствующие выбранным позициям, переставляются, и формируется новая хромосома А' = (a₁, a_L.₁, а₃,...,_аL-2, а₂, a_L).

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

Р₁ : 0 1 1 | 0 1 1

Р'₁: 0 1 0 | 1 1 1.

Здесь Р₁ -- родительская хромосома, а Р'₁. -- хромосома-потомок после применения одноточечного оператора мутации. При реализации двухт-очечного ОМ случайным или направленным образом выбираются две точки разреза. Затем производится перестановка генов между собой, расположенных справа от точек разреза. Например:

Р : А | B C D | E F

Р'₁ : А Е С D В F.

Здесь Р₁ -- родительская хромосома, а Р'₁ -- хромосома-потомок после применения двухточечного оператора мутации.

Развитием двухточечного оператора мутации является многоточечный (или n-точечный) ОМ. В этом случае происходит последовательный обмен генов, расположенных правее точек разреза друг с другом в порядке их расположения. Ген, расположенный правее последней точки разреза, переходит на место первого. Например:

Р: А| В С D | E F | G H

Р' : A G C D B F E H.

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

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

Например:

Р: А В | С D | E F | G H | I J

P': А С B E D G F I H J.

При нечетном числе точек потомок получается после обмена участками хромосом, расположенных между четными точками разреза.

Например:

Р : ABC | DEF | GHI | J

Р': AВС GHI DEF J.

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

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

Р : А | B C D | E F

Р' : А В E С D F.

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

1. Хромосома В = b₁,b₂,…,b _L выбирается случайным образом из текущей популяции.

2. Два числа у'₁и у'₂ выбираются случайным образом из множества {0, 1, 2, .... L+1), причем считается, что у₁ = min{y'₁,y'₂} и у₂= max{y'₁, y'₂}.

3. Новая хромосома сформируется из В путем инверсии сегмента, который лежит справа от позиции у₁ и слева от позиции у₂ в хромосоме В.

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

Рассмотрим оператор транслокации. Оператор транслокации -- это языковая конструкция, позволяющая на основе скрещивания и инвертирования из пары родительских хромосом (или их частей) создавать две хромосомы потомков. Другими словами, он представляет собой комбинацию операторов кроссинговера и инверсии. В процессе его реализации случайным образом производится один разрез в каждой хромосоме. При формировании потомка P'₁ берется левая часть до разрыва из родителя Р₁ и инверсия правой части до разрыва из P₂, .При создании P'₂.. берется левая часть Р₂ и инверсия правой части Р₁. Например:

Р₁ : A В С D Е F

Р₂ : G К Н I J Q

Р'₁: A В Q J I H

Р'₂: О К F E D С.

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

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

Р₁: A|B C|D E F|G H

P'₁: A F E D В С G Н

Здесь три точки разреза. Точки разреза выбираются случайным или направленным образом. В родительской хромосоме P₁ строительный блок DEF инвертируется и вставляется в точку разреза между генами А и В. В результате получаем хромосому-потомок Р'₁ Отметим, что существует большое количество модификаций оператора транспозиции .

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

Приведем один из примеров его реализации. Отметим, что оператор сегрегации, как правило, реализуется на некотором наборе хромосом. Пусть имеется популяция Р, состоящая из четырех родительских хромосом Р - (Р₁, Р₂, Р₃, Р₄}: Р₁ : (12345678); Р₂ : (24316587); Р₃ : (31425768); Р₄ : (87654321). В каждой хромосоме выделим строительные блоки. Выделим по два строительных блока: в Р₁ -- 23 и 67, в Р₂ -- 1 и 4. в Р₃ -- 768 и 425 и в Р₄ -- 54 и 87. Тогда, например, потомок Р'₁ можно сформировать, взяв первые строительные блоки из каждой родительской хромосомы популяции. Так, вариант Р'₁ будет представлен последовательностью 423176854) и является реальным решением, а вариант Р'₂ (67442587) является нереальным (недопустимым). Очевидно, что оператор сегрегации можно реализовать различными способами в зависимости от выборки строительный блоков или генов из хромосом.

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

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

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

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

На конечном этапе поиска целесообразно применять выбор близких решений, в соответствии с определенным критерием, то есть искать решение среди лучших Р^t _k.

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

Численность новой популяции

N^t+1= N^t + N_ок + N_ом + N_oи+ N_ot + N_отр + N_oe + N_oy

где N^t+1 -- численность новой популяции.

N^t -- численность популяции на предыдущем шаге (поколении) t,

N_ок , N_ом , N_oи , N_ot , N_отр , N_oe , N_oy - потомки, полученные в результате применения операторов -- кроссинговера, мутации, инверсии, транслокации, транспозиции, сегрегации, удаления, вставки.

Отметим, что оператор редукции может применяться после каждого оператора или после всех в одной генерации ГА.

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

По аналогии с оператором репродукции известны следующие модификации операторов редукции:

1) равновероятностный отбор с вероятностью

P _k(s)=1/N

где N -- размер популяции;

2) пропорциональный отбор с вероятностью

P _k(s)=ЦФ(P _k )/? ЦФ(P _k )

Подведем итоги. С помощью операторов редукции на ранних стадиях работы ГА происходит выбор хромосом без учета значений их ЦФ (Р_к). т.е. случайный отбор. На заключительной стадии -- определяющий фактор при отборе значения ЦФ(Р_к). Чем выше ЦФ(Р_к), тем выше вероятность отбора Р_к в следующую популяцию. На заключительной стадии проводится уменьшение случайных операций и увеличивается процент направленных.

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

Часто в ГА задается параметр W(P). который управляет этим процессом. Так. N (l-W(P)) элементов в популяции Р, выбранных случайно, могут «выжить» в следующей генерации. Здесь N_p -- размер популяции. Величина W(P) = 0 означает, что целая предыдущая популяция перемещается в новую популяцию в каждой генерации. При дальнейшей реализации алгоритма лучшие или отобранные элементы из родителей и потомков будут выбираться для формирования повой популяции.

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

1. Конструируется начальная популяция. Вводится точка отсчета поколений t = 0. Вычисляется приспособленность каждой хромосомы в популяции, а затем средняя приспособленность всей популяции.

2. Устанавливается t = t + 1. Производится выбор двух родителей (хромосом) для реализации оператора кроссинговера. Он выполняется случайным образом пропорционально приспособляемости родителей.

3. Формируется генотип потомков. Для этого с заданной вероятностью производится оператор кроссинговера над генотипами выбранных хромосом. Далее с вероятностью 0,5 выбирается один из потомков P _i(t) и сохраняется как член новой популяции. После этого к P_i(t) последовательно применяется оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохраняется как P _k(t).

4. Определяется количество хромосом для исключения их на популяции, чтобы ее размер оставался постоянным. Текущая популяция обновляется заменой отобранных хромосом на потомков P_k(t).

5. Производится определение приспособленности (целевой функции) и пересчет средней приспособленности всей полученной популяции.

6. Если t = t_{заданному}, то переход к 7, если нет, то переход к 2.

7. Конец работы.

Данный алгоритм известен как упрощенный «репродуктивный план Д. Холланда». Заметим, что в практических задачах вместо понятия «приспособленность» используют понятие «целевая функция».

Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда. Его механизм несложен. Предварительно ПГА случайно генерирует популяцию последовательностей -- хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем производится копирование последовательности хромосом и перестановка их частей. Далее ПГА реализует множество простых операций на начальной популяции и генерирует новые решения.

ИГА состоит из трех операторов:

¦ репродукция;

¦ кроссинговер;

¦ мутация.

Репродукция--процесс, в котором хромосомы копируются пропорционально значению их ЦФ. Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для попадания в следующую генерацию. Рассматривая эволюцию Ч. Дарвина, можно отметить, что оператор репродукции (ОР) является искусственной версией натуральной селекции -- «выживание сильнейших». Он представляется в алгоритмической форме различными способами. Самый простой -- создать модель «колеса рулетки», в которой каждая хромосома имеет поле, пропорциональное значению ЦФ. Работа ПГА начинается с репродукции. Хромосомы для следующей генерации выбираются путем вращения колеса рулетки. Величину отношения f_i(x)/sum f(x) называют вероятностью выбора копий (хромосом) при реализации оператора репродукции и обозначают

P_i(OP)= f_i(x)/sumf(x)

где f_i(x) -- значение ЦФ i-й хромосомы в популяции, sum f(x)-- суммарное значение ЦФ всех хромосом о популяции. Величину P_i(OP) также называют нормализованной вероятностью выбора. Ожидаемое число копий i-й хромосомы после реализации ОН определяется по формуле

где N_G -- число анализируемых хромосом, причем N_G включается в N.

Ожидаемое число копий хромосомы P_i, переходящее в следующее поколение, также иногда определяют на основе выражения

N_i=f _i(x)/<f(x)>

где <f(x)> -- среднее значение ЦФ по всей популяции.

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

2. Постановка задачи

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



3. Математическая модель генетического алгоритма

3.1 Описание используемых функций в программе

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

1. population (int*a,int*aa,int,n)

В функцию передается массив целочисленный массив a, состоящий из n элементов. Функция генерирует случайные числа и этими числами заполняется массив a. Массив aa является копией массива a.

3.2 Блок-схема программы, реализующий генетический алгоритм

Рисунок 1 - блок-схема программы, реализующий генетический алгоритм

3.3 Текст программы, реализующей генетический алгоритм

#include<iostream.h>

#include<stdlib.h>

#include<math.h>

int dio(int a,int b,int c,int d);

void mf(double*,double*,int*,int);

void breeding(int*,int,int,int*,int*);

void out(int *a,int n,int m);

void mutation(int *a,int n,int m);

int main()

{

const int n=100,m=4;

int p[n][m],i,j,k=0,delta[n],sum=0,mother[n],father[n],kol=1,e=1,key;

double ver[n],sr[n];

cout<<"enter key"<<endl;

cin>>key;

for(;;)

{

for(i=0;i<n;i++)

{

for(j=0;j<m;j++)

p[i][j]=int(10.*key*rand()/RAND_MAX);

delta[i]=dio(p[i][0],p[i][1],p[i][2],p[i][3]);

sum+=delta[i];

}

for(i=0;i<n;i++)

{

ver[i]=1-1.*delta[i]/sum;

}

for(i=0;i<n;i++)

sr[i]=1.*rand()/RAND_MAX;

mf(sr,ver,mother,n);

for(i=0;i<n;i++)

sr[i]=1.*rand()/RAND_MAX;

mf(sr,ver,father,n);

breeding(p[0],n,m,mother,father);

mutation(p[0],n,m);

kol++;

for(i=0;i<n;i++)

if(abs(dio(p[i][0],p[i][1],p[i][2],p[i][3]))<e)

{

cout<<"The solution set to a+2b+3c+4d=30 is:"<<endl;

cout<<"a="<<p[i][0]<<"\tb="<<p[i][1]<<"\tc="<<p[i][2]<<"\td="<<p[i][3]<

<endl;

cout<<"amount of generations: "<<kol<<endl;

return 0;

}

}

return 0;

}

int dio(int a,int b,int c,int d)

{

return abs(a+2*b+3*c+4*d-30);

}

void mf(double *a,double*b,int*c,int m)

{

int i,j;

double sum=b[0];

for(i=0;i<m;i++)

{

for(j=1;j<m;j++)

{

if(a[i]<sum)

{

c[i]=j;

break;

}

else

sum+=b[j];

}

sum=b[0];

}

}

void breeding(int*a,int n,int m,int*b,int*c)

{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<m;j++)

{

if(j<2)

a[i*m+j]=a[b[i]*m+j];

else

a[i*m+j]=a[c[i]*m+j];

}

}

void out(int *a,int n,int m)

{

int i,j;

for(i=0;i<n;i++)

{

cout<<i+1<<"\t";

for(j=0;j<m;j++)

cout<<a[i*m+j]<<"\t";

cout<<endl;

}

}

void mutation(int *a,int n,int m)

{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<m;j++)

a[i*m+int(4*rand()/RAND_MAX)]=int(30*rand()/RAND_MAX);

}



4. Тестирование генетического алгоритма

Входные данные

Название	Обозначение	Диапазон возможных значений
Погрешность вычисления.	е	1
Количество особей	n	100
Количество хромосом у особи	m	4

Выходные данные

Название	Вид представления	Вывод
Корни уравнения.	a=<значение> b=<значение> c=<значение> d=<значение>	на экран
Количество поколений	kol= <значение>	на экран

Все эксперименты производились на компьютере со следующей конфигурацией: AMD Athlon(tm) xp1700+ 1,47 ГГц ,256 MB ОЗУ, Windows XP Professional Service Pack 2.



Заключение

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

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

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

1. Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. - М.: МГАПИ, 2003. - 80 с.

2. Конспект лекций по дисциплине «Математическая логика и теория алгоритмов».

3. Javier Trejos, Eduardo Piza, Alex Murillo A Tabu Search Algorithm for Partitioning. - 1996. - http://google.ru/ globalsearching /materials/1008.pdf.

4. Alain Hertz, Eric Taillard, Dominique de Werra A Tutorial On Tabu Search. - 1995. - http://google.ru/ globalsearching/books/1548/hertz92tutorial.pdf.

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