Материал: Генетический алгоритм как метод оптимизации

Рисунок 1.3.3 - Инверсия в хромосоме.

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

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

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

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

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

Имеется много способов реализации идеи биологической эволюции в рамках генетического алгоритма. Схема генетического алгоритма представлена на рис. 1.4.1.

Рисунок 1.4.1 - Схема работы классического генетического алгоритма.

Ниже подробнее рассмотрим шаги алгоритма.

.4.1 Генерация начальной популяции

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

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

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

Для кодирования признаков можно использовать самый простой вариант - битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так, например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что значительно увеличивает размер поискового пространства. Одним из решений данной проблемы является использование кода Грея (см. приложение А). И, наоборот, для того чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующие этим признакам, то есть генотип объекта. Операция определения фенотипа объекта по его генотипу называется операцией декодирования или роста, то есть мы выращиваем фенотип из генотипа.

Таким образом, для того чтобы инициализировать начальную популяцию, необходимо сначала определиться со способами кодирования особей. [3]

.4.2 Оценка популяции

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

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

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

Таблица 1.4.2.1 - Метод рулетки. Размер популяции = 5. Суммарная пригодность популяции = 200.

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

Турнирная селекция (tournament selection) - из популяции, состоящей из N особей, создается группа из t ( ≥ 2) особей, выбранных случайным образом (рис. 1.4.2.1). Особь с наибольшей пригодностью в группе отбирается, остальные - отбрасываются. Такая операция повторяется k раз. Затем отобранные особи используются для кроссинговера. Размер группы t часто равен 2, в таких случаях говорят о парных (двоичных) турнирах (binary tournament). Число t называется численностью турнира (tournament size).

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

Отбор усечением (truncation selection) - индивиды сортируются (ранжируются) на основе их пригодности таким образом, чтобы ≥ для ≤, т.е. первым стоит наиболее приспособленный индивид. Число особей для скрещивания выбирается в соответствии с порогом TÎ[0; 1]. Порог определяет, какая доля особей, начиная с самой первой (то есть самой приспособленной) будет принимать участие в отборе. Порог может быть задан и числом больше 1, тогда он будет равен числу особей из текущей популяции, допущенных к отбору. Среди особей, попавших "под порог", случайным образом N раз выбирается самая везучая, среди которых затем выбираются особи непосредственно для скрещивания.

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

.4.3 Проверка условия остановки

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

.4.4 Генерация новой популяции

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

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

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

Отбор с вытеснением (exclusion selection) - отбор, построенный на таком принципе, носит бикритериальный характер - то, будет ли особь из репродукционной группы заноситься в популяцию нового поколения, определяется не только величиной ее приспособленности, но и тем, есть ли уже в формируемой популяции следующего поколения особь с аналогичным хромосомным набором. Из всех особей с одинаковыми генотипами предпочтение сначала, конечно же, отдается тем, чья приспособленность выше. Таким образом, достигаются две цели: во-первых, не теряются лучшие найденные решения, обладающие различными хромосомными наборами, а во-вторых, в популяции постоянно поддерживается достаточное генетическое разнообразие [2];

Только потомки (детерминизм) - метод основан на построении новой популяции только из популяции потомков;

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

.5 Вывод наилучшей особи

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

Используя генетические операторы, схема генетического алгоритма будет выглядеть следующим образом [2]:

Рисунок 1.5.1 - Расширенная схема генетического алгоритма

2. Проектная часть

.1 Применение генетического алгоритма для решения задачи коммивояжера

.1.1 Постановка задачи безусловной оптимизации

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

.2 Ограничения при реализации генетических алгоритмов

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

Под кодированием понимается способ представления данных в генетическом виде.

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

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

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

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

Так же важным параметром генетических алгоритмов является размер популяции.

При практической реализации возможны две крайности:

слишком малый размер популяции (<10). Данный выбор в большинстве случаев годится только для очень простых задач. В противном случае будет наблюдаться быстрое вырождение популяции;

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

Исходя из данных рекомендаций, оптимальным размером популяции является 20-30 особей, однако в некоторых задачах требуется 50-100 особей.

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

Так, для алгоритма с 32-битовыми хромосомами размер популяции будет больше, чем для алгоритма с 16-битовыми. [7]

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

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

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

двухточечный и однородный операторы кроссинговера, как правило, работают лучше, чем одноточечный;

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

применение стратегии элитарности - позволяет гарантированно оставить в популяции наилучших особей;

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

.3 Решение задачи коммивояжера с помощью генетического алгоритма

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

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