Эволюционная теория утверждает, что каждый биологический вид целенаправленно развивается и изменяется для того, чтобы наилучшим образом приспособиться к окружающей среде. В процессе эволюции многие виды насекомых и рыб приобрели защитную окраску, еж стал неуязвимым благодаря иглам, человек стал обладателем сложнейшей нервной системы. Можно сказать, что эволюция - это процесс оптимизации всех живых организмов. Рассмотрим, какими же средствами природа решает эту задачу оптимизации.
Основной механизм эволюции - это естественный отбор.
Его суть состоит в том, что более приспособленные особи имеют больше возможностей для выживания и размножения и, следовательно, приносят больше потомства, чем плохо приспособленные особи. При этом благодаря передаче генетической информации (генетическому наследованию ) потомки наследуют от родителей основные их качества. Таким образом, потомки сильных индивидуумов также будут относительно хорошо приспособленными, а их доля в общей массе особей будет возрастать. После смены нескольких десятков или сотен поколений средняя приспособленность особей данного вида заметно возрастает.
Чтобы сделать понятными принципы работы генетических алгоритмов, поясним также, как устроены механизмы генетического наследования в природе. В каждой клетке любого животного содержится вся генетическая информация этой особи. Эта информация записана в виде набора очень длинных молекул ДНК (ДезоксирибоНуклеиновая Кислота). Каждая молекула ДНК - это цепочка, состоящая из молекул нуклеотидов четырех типов, обозначаемых А, T, C и G. Собственно, информацию несет порядок следования нуклеотидов в ДНК. Таким образом, генетический код индивидуума - это просто очень длинная строка символов, где используются всего 4 буквы. В животной клетке каждая молекула ДНК окружена оболочкой - такое образование называется хромосомой.
Каждое врожденное качество особи (цвет глаз, наследственные болезни, тип волос и т.д.) кодируется определенной частью хромосомы, которая называется геном этого свойства. Например, ген цвета глаз содержит информацию, кодирующую определенный цвет глаз. Различные значения гена называются его аллелями .
При размножении животных происходит слияние двух родительских половых клеток и их ДНК взаимодействуют, образуя ДНК потомка. Основной способ взаимодействия - кроссовер (cross-over, скрещивание). При кроссовере ДНК предков делятся на две части, а затем обмениваются своими половинками.
При наследовании возможны мутации из-за радиоактивности или других влияний, в результате которых могут измениться некоторые гены в половых клетках одного из родителей. Измененные гены передаются потомку и придают ему новые свойства. Если эти новые свойства полезны, они, скорее всего, сохранятся в данном виде - при этом произойдет скачкообразное повышение приспособленности вида.
2. Что такое генетический алгоритмПусть дана некоторая сложная функция (целевая функция ), зависящая от нескольких переменных, и требуется найти такие значения переменных, при которых значение функции максимально. Задачи такого рода называются задачами оптимизации и встречаются на практике очень часто.
Один из наиболее наглядных примеров - задача распределения инвестиций, описанная ранее. В этой задаче переменными являются объемы инвестиций в каждый проект (10 переменных), а функцией, которую нужно максимизировать - суммарный доход инвестора. Также даны значения минимального и максимального объема вложения в каждый из проектов, которые задают область изменения каждой из переменных.
Попытаемся решить эту задачу, применяя известные нам природные способы оптимизации. Будем рассматривать каждый вариант инвестирования (набор значений переменных) как индивидуума, а доходность этого варианта - как приспособленность этого индивидуума. Тогда в процессе эволюции (если мы сумеем его организовать) приспособленность индивидуумов будет возрастать, а значит, будут появляться все более и более доходные варианты инвестирования. Остановив эволюцию в некоторый момент и выбрав самого лучшего индивидуума, мы получим достаточно хорошее решение задачи.
Генетический алгоритм - это простая модель эволюции в природе, реализованная в виде компьютерной программы. В нем используются как аналог механизма генетического наследования, так и аналог естественного отбора. При этом сохраняется биологическая терминология в упрощенном виде.
Вот как моделируется генетическое наследование
Чтобы смоделировать эволюционный процесс, сгенерируем вначале случайную популяцию - несколько индивидуумов со случайным набором хромосом (числовых векторов). Генетический алгоритм имитирует эволюцию этой популяции как циклический процесс скрещивания индивидуумов и смены поколений.
Жизненный цикл популяции - это несколько случайных скрещиваний (посредством кроссовера) и мутаций, в результате которых к популяции добавляется какое-то количество новых индивидуумов. Отбор в генетическом алгоритме - это процесс формирования новой популяции из старой, после чего старая популяция погибает. После отбора к новой популяции опять применяются операции кроссовера и мутации, затем опять происходит отбор, и так далее.
Отбор в генетическом алгоритме тесно связан с принципами естественного отбора в природе следующим образом:
Таким образом, модель отбора определяет, каким образом следует строить популяцию следующего поколения. Как правило, вероятность участия индивидуума в скрещивании берется пропорциональной его приспособленности. Часто используется так называемая стратегия элитизма, при которой несколько лучших индивидуумов переходят в следующее поколение без изменений, не участвуя в кроссовере и отборе. В любом случае каждое следующее поколение будет в среднем лучше предыдущего. Когда приспособленность индивидуумов перестает заметно увеличиваться, процесс останавливают и в качестве решения задачи оптимизации берут наилучшего из найденных индивидуумов.
Возвращаясь к задаче оптимального распределения инвестиций, поясним особенности реализации генетического алгоритма в этом случае.
Ниже приведены результаты работы генетического алгоритма для трех различных значений суммарного объема инвестиций K.
Цветными квадратами на графиках прибылей отмечено, какой объем вложения в данный проект рекомендован генетическим алгоритмом. Видно, что при малом значении K инвестируются только те проекты, которые прибыльны при минимальных вложениях.
Если увеличить суммарный объем инвестиций, становится прибыльным вкладывать деньги и в более дорогостоящие проекты.
При дальнейшем увеличении K достигается порог максимального вложения в прибыльные проекты, и инвестирование в малоприбыльные проекты опять приобретает смысл.
3. Особенности генетических алгоритмовГенетический алгоритм - новейший, но не единственно возможный способ решения задач оптимизации. С давних пор известны два основных пути решения таких задач - переборный и локально-градиентный. У этих методов свои достоинства и недостатки, и в каждом конкретном случае следует подумать, какой из них выбрать.
Рассмотрим достоинства и недостатки стандартных и генетических методов на примере классической задачи коммивояжера (TSP - travelling salesman problem). Суть задачи состоит в том, чтобы найти кратчайший замкнутый путь обхода нескольких городов, заданных своими координатами. Оказывается, что уже для 30 городов поиск оптимального пути представляет собой сложную задачу, побудившую развитие различных новых методов (в том числе нейросетей и генетических алгоритмов).
Каждый вариант решения (для 30 городов) - это числовая строка, где на j-ом месте стоит номер j-ого по порядку обхода города. Таким образом, в
этой задаче 30 параметров, причем не все комбинации значений допустимы. Естественно, первой идеей является полный перебор всех вариантов обхода.
Переборный метод наиболее прост по своей сути и тривиален в программировании. Для поиска оптимального решения (точки максимума целевой функции) требуется последовательно вычислить значения целевой функции во всех возможных точках, запоминая максимальное из них. Недостатком этого метода является большая вычислительная стоимость. В частности, в задаче коммивояжера потребуется просчитать длины более 10 30 вариантов путей, что совершенно нереально. Однако, если перебор всех вариантов за разумное время возможен, то можно быть абсолютно уверенным в том, что найденное решение действительно оптимально.
Второй популярный способ основан на методе градиентного спуска. При этом вначале выбираются некоторые случайные значения параметров, а затем эти значения постепенно изменяют, добиваясь наибольшей скорости роста целевой функции. Достигнув локального максимума, такой алгоритм останавливается, поэтому для поиска глобального оптимума потребуются дополнительные усилия. Градиентные методы работают очень быстро, но не гарантируют оптимальности найденного решения.
Они идеальны для применения в так называемых унимодальных
задачах, где целевая функция имеет единственный локальный
максимум (он же - глобальный). Легко видеть, что задача коммивояжера унимодальной не является.
Типичная практическая задача, как правило, мультимодальна и многомерна, то есть содержит много параметров. Для таких задач не существует ни одного универсального метода, который позволял бы достаточно быстро найти абсолютно точное решение.
Однако, комбинируя переборный и градиентный методы, можно надеяться получить хотя бы приближенное решение, точность которого будет возрастать при увеличении времени расчета.
Генетический алгоритм представляет собой именно такой комбинированный метод. Механизмы скрещивания и мутации в каком-то смысле реализуют переборную часть метода, а отбор лучших решений - градиентный спуск. На рисунке показано, что такая комбинация позволяет обеспечить устойчиво хорошую эффективность генетического поиска для любых типов задач.
Итак, если на некотором множестве задана сложная функция от нескольких переменных, то генетический алгоритм - это программа, которая за разумное время находит точку, где значение функции достаточно близко к максимально возможному. Выбирая приемлемое время расчета, мы получим одно из лучших решений, которые вообще возможно получить за это время.
Компанией Ward Systems Group подготовлен наглядный пример решения задачи коммивояжера с помощью генетического алгоритма. Для этого была использована библиотека функций продукта GeneHunter.
Генетические алгоритмы предназначены для решения задач оптимизации. Примером подобной задачи может служить обучение нейросети, то есть подбора таких значений весов, при которых достигается минимальная ошибка. При этом в основе генетического алгоритма лежит метод случайного поиска. Основным недостатком случайного поиска является то, что нам неизвестно сколько понадобится времени для решения задачи. Для того, чтобы избежать таких расходов времени при решении задачи, применяются методы, проявившиеся в биологии. При этом используются методы открытые при изучении эволюции и происхождения видов. Как известно, в процессе эволюции выживают наиболее приспособленные особи. Это приводит к тому, что приспособленность популяции возрастает, позволяя ей лучше выживать в изменяющихся условиях.
Впервые подобный алгоритм был предложен в 1975 году Джоном Холландом (John Holland) в Мичиганском университете. Он получил название "репродуктивный план Холланда" и лег в основу практически всех вариантов генетических алгоритмов. Однако, перед тем как мы его рассмотрим подробнее, необходимо остановится на том, каким образом объекты реального мира могут быть закодированы для использования в генетических алгоритмах.
Из биологии мы знаем, что любой организм может быть представлен своим , который фактически определяет, чем является объект в реальном мире, и генотипом , который содержит всю информацию об объекте на уровне хромосомного набора. При этом каждый ген, то есть элемент информации генотипа, имеет свое отражение в фенотипе. Таким образом, для решения задач нам необходимо представить каждый признак объекта в форме, подходящей для использования в генетическом алгоритме. Все дальнейшее функционирование механизмов генетического алгоритма производится на уровне генотипа, позволяя обойтись без информации о внутренней структуре объекта, что и обуславливает его широкое применение в самых разных задачах.
В наиболее часто встречающейся разновидности генетического алгоритма для представления генотипа объекта применяются битовые строки. При этом каждому атрибуту объекта в фенотипе соответствует один ген в генотипе объекта. Ген представляет собой битовую строку, чаще всего фиксированной длины, которая представляет собой значение этого признака.
Для кодирования таких признаков можно использовать самый простой вариант – битовое значение этого признака. Тогда нам будет весьма просто использовать ген определенной длины, достаточной для представления всех возможных значений такого признака. Но, к сожалению, такое кодирование не лишено недостатков. Основной недостаток заключается в том, что соседние числа отличаются в значениях нескольких битов, так например числа 7 и 8 в битовом представлении различаются в 4-х позициях, что затрудняет функционирование генетического алгоритма и увеличивает время, необходимое для его сходимости. Для того, чтобы избежать эту проблему лучше использовать кодирование, при котором соседние числа отличаются меньшим количеством позиций, в идеале значением одного бита. Таким кодом является код Грея, который целесообразно использовать в реализации генетического алгоритма. Значения кодов Грея рассмотрены в таблице ниже:
Таблица 1. Соответствие десятичных кодов и кодов Грея
Двоичное кодирование |
Кодирование по коду Грея |
||||
|---|---|---|---|---|---|
Десятичный код |
Двоичное значение |
Шестнадцатеричное значение |
Десятичный код |
Двоичное значение |
Шестнадцатеричное значение |
| 0 | |||||
| 1 | |||||
| 2 | |||||
| 3 | |||||
| 4 | |||||
| 5 | |||||
| 6 | |||||
| 7 | |||||
| 8 | |||||
| 9 | |||||
| 10 | |||||
| 11 | |||||
| 12 | |||||
| 13 | |||||
| 14 | |||||
| 15 | |||||
Таким образом, при кодировании целочисленного признака мы разбиваем его на тетрады и каждую тетраду преобразуем по коду Грея.
В практических реализациях генетических алгоритмов обычно не возникает необходимости преобразовывать значения признака в значение гена. На практике имеет место обратная задача, когда по значению гена необходимо определить значение соответствующего ему признака.
Таким образом, задача декодирования значения генов, которым соответствуют целочисленные признаки, тривиальна.
Самый простой способ кодирования, который лежит на поверхности – использовать битовое представление. Хотя такой вариант имеет те же недостатки, что и для целых чисел. Поэтому на практике обычно применяют следующую последовательность действий:
Рассмотрим вышеописанную последовательность действий на примере:
Допустим, что значения признака лежат в интервале . При кодировании использовалось разбиение участка на 256 интервалов. Для кодирования их номера нам потребуется таким образом 8 бит. Допустим значение гена: 00100101bG (заглавная буква G показывает, что используется кодирование по коду Грея). Для начала, используя код Грея, найдем соответствующий ему номер интервала: 25hG->36h->54d. Теперь посмотрим, какой интервал ему соответствует… После несложных подсчетов получаем интервал . Значит значение нашего параметра будет (0,20703125+0,2109375)/2=0,208984375.
При кодировании нечисловых данных необходимо предварительно преобразовать их в числа. Более подробно это описано в статьях нашего сайта, посвященных использованию нейронных сетей.
Таким образом, для того, чтобы определить фенотип объекта (то есть значения признаков, описывающих объект) нам необходимо только знать значения генов, соответствующим этим признакам, то есть генотип объекта. При этом совокупность генов, описывающих генотип объекта, представляет собой хромосому . В некоторых реализациях ее также называют особью. Таким образом, в реализации генетического алгоритма хромосома представляет собой битовую строку фиксированной длины. При этом каждому участку строки соответствует ген. Длина генов внутри хромосомы может быть одинаковой или различной. Чаще всего применяют гены одинаковой длины. Рассмотрим пример хромосомы и интерпретации ее значения. Допустим, что у объекта имеется 5 признаков, каждый закодирован геном длинной в 4 элемента. Тогда длина хромосомы будет 5*4=20 бит
| 0010 | 1010 | 1001 | 0100 | 1101 |
теперь мы можем определить значения признаков
| Признак | Значение гена | Двоичное значение признака | Десятичное значение признака |
|---|---|---|---|
| Признак 1 | |||
| Признак 2 | |||
| Признак 3 | |||
| Признак 4 | |||
| Признак 5 |
Как известно в теории эволюции важную роль играет то, каким образом признаки родителей передаются потомкам. В генетических алгоритмах за передачу признаков родителей потомкам отвечает оператор, который называется скрещивание (его также называют кроссовер или кроссинговер). Этот оператор определяет передачу признаков родителей потомкам. Действует он следующим образом:
Рассмотрим функционирование этого оператора:
Затем с вероятностью 0,5 определяется одна из результирующих хромосом в качестве потомка.
Следующий генетический оператор предназначен для того, чтобы поддерживать разнообразие особей с популяции. Он называется оператором мутации . При использовании данного оператора каждый бит в хромосоме с определенной вероятностью инвертируется.
Кроме того, используется еще и так называемый оператор инверсии , который заключается в том, что хромосома делится на две части, и затем они меняются местами. Схематически это можно представить следующим образом
| 000 | 1111111 | >> | 1111111 | 000 |
В принципе для функционирования генетического алгоритма достаточно этих двух генетических операторов, но на практике применяют еще и некоторые дополнительные операторы или модификации этих двух операторов. Например, кроссовер может быть не одноточечный (как было описано выше), а многоточечный, когда формируется несколько точек разрыва (чаще всего две). Кроме того, в некоторых реализациях алгоритма оператор мутации представляет собой инверсию только одного случайно выбранного бита хромосомы.
Теперь, зная как интерпретировать значения генов, перейдем к описанию функционирования генетического алгоритма. Рассмотрим схему функционирования генетического алгоритма в его классическом варианте.
Теперь рассмотрим подробнее отдельные этапы алгоритма.
Наибольшую роль в успешном функционировании алгоритма играет этап отбора родительских хромосом на шагах 3 и 4. При этом возможны различные варианты. Наиболее часто используется метод отбора, называемый рулеткой . При использовании такого метода вероятность выбора хромосомы определяется ее приспособленностью, то есть $P_{Get(Ai)} ~ Fit(A_i)/Fit(B_t)$. Использование этого метода приводит к тому, что вероятность передачи признаков более приспособленными особями потомкам возрастает. Другой часто используемый метод – турнирный отбор . Он заключается в том, что случайно выбирается несколько особей из популяции (обычно 2) и победителем выбирается особь с наибольшей приспособленностью. Кроме того, в некоторых реализациях алгоритма применяется так называемая стратегия элитизма , которая заключается в том, что особи с наибольшей приспособленностью гарантировано переходят в новую популяцию. Использование элитизма обычно позволяет ускорить сходимость генетического алгоритма. Недостаток использования стратегии элитизма в том, что повышается вероятность попадания алгоритма в локальный минимум.
Другой важный момент – определение критериев останова. Обычно в качестве них применяются или ограничение на максимальное число эпох функционирования алгоритма, или определение его сходимости, обычно путем сравнивания приспособленности популяции на нескольких эпохах и остановки при стабилизации этого параметра.
Природа поражает своей сложность и богатством всех своих проявлений. Среди примеров можно назвать сложные социальные системы, иммунные и нейронные системы, сложные взаимосвязи между видами. Они - всего лишь некоторые из чудес, которые стали более очевидны, когда мы стали глубже исследовать себя самих и мир вокруг нас. Наука - это одна из сменяющих друг друга систем веры, которыми мы пытается объяснять то, что наблюдаем, этим самым изменяя себя, чтобы приспособиться к новой информации, получаемой из внешнего мира. Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией: теорией эволюции через наследственность, изменчивость и отбор.
Теория эволюции повлияла на изменение мировоззрения людей с самого своего появления. Теория, которую Чарльз Дарвин представил в работе, известной как "Происхождение Видов", в 1859 году, стала началом этого изменения. Многие области научного знания в настоящее время наслаждаются свободой мысли в атмосфере, которая многим обязана революции, вызванной теорией эволюции и развития. Но Дарвин, подобно многим своим современникам, кто предполагал, что в основе развития лежит естественный отбор, не мог не ошибаться. Например, он не смог показать механизм наследования, при котором поддерживается изменчивость. Его гипотеза о пангенезисе оказалась неправильной. Это было на пятьдесят лет до того, как теория наследственности начала распространяться по миру, и за тридцать лет до того, как "эволюционный синтез" укрепил связь между теорией эволюции и относительно молодой наукой генетикой. Однако Дарвин выявил главный механизм развития: отбор в сочетании с изменчивостью или, как он его называл, "спуск с модификацией". Во многих случаях, специфические особенности развития через изменчивость и отбор все еще не бесспорны, однако, основные механизмы объясняют невероятно широкий спектр явлений, наблюдаемых в Природе.
Поэтому неудивительно, что ученые, занимающиеся компьютерными исследованиями, обратились к теории эволюции в поисках вдохновения. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в природных системах, была очень привлекательна. Эта надежда стала причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.
История эволюционных вычислений началась с разработки ряда различных независимых моделей. Основными из них были генетические алгоритмы и классификационные системы Голланда (Holland), опубликованные в начале 60-х годов и получившие всеобщее признание после выхода в свет книги, ставшей классикой в этой области, - "Адаптация в естественных и искусственных системах" ("Adaptation in Natural and Artifical Systems", 1975). В 70-х годах в рамках теории случайного поиска Растригиным Л.А. был предложен ряд алгоритмов, использующих идей бионического поведения особей. Развитие этих идей нашло отражение в цикле работ Букатовой И.Л. по эволюционному моделированию. Развивая идеи Цетлина М.Л. о целесообразном и оптимальном поведении стохастических автоматов, Неймарк Ю.И. предложил осуществлять поиск глобального экстремума на основе коллектива независимых автоматов, моделирующих процессы развития и элиминации особей. Большой вклад в развитие эволюционного программирования внесли Фогел (Fogel) и Уолш (Walsh). Несмотря на разницу в подходах, каждая из этих "школ" взяла за основу ряд принципов, существующих в природе, и упростила их до такой степени, чтобы их можно было реализовать на компьютере.
Главная трудность с возможностью построения вычислительных систем, основанных на принципах естественного отбора и применением этих систем в прикладных задачах, состоит в том, что природные системы достаточно хаотичны, а все наши действия, фактически, носят четкую направленность. Мы используем компьютер как инструмент для решения определенных задач, которые мы сами и формулируем, и мы акцентируем внимание на максимально быстром выполнении при минимальных затратах. Природные системы не имеют никаких таких целей или ограничений, во всяком случае нам они не очевидны. Выживание в природе не направлено к некоторой фиксированной цели, вместо этого эволюция совершает шаг вперед в любом доступномее направлении.
Возможно это большое обобщение, но я полагаю, что усилия, направленные на моделирование эволюции по аналогии с природными системами, к настоящему времени можно разбить на две большие категории: 1) системы, которые смоделированы на биологических принципах. Они успешно использовались для задач типа функциональной оптимизации и могут легко быть описаны на небиологическом языке, 2) системы, которые являются биологически более реалистичными, но которые не оказались особенно полезными в прикладном смысле. Они больше похожи на биологические системы и менее направлены (или ненаправлены вовсе). Они обладают сложным и интересным поведением, и, видимо, вскоре получат практическое применение.
Конечно, на практике мы не можем разделять эти вещи так строго. Эти категории - просто два полюса, между которыми лежат различные вычислительные системы. Ближе к первому полюсу - эволюционные алгоритмы, такие как Эволюционное Программирование (Evolutionary Programming), Генетические Алгоритмы (Genetic Algorithms) и Эволюционные Стратегии (Evolution Strategies). Ближе ко второму полюсу - системы, которые могут быть классифицированы как Искусственная Жизнь (Artificial Life).
Конечно, эволюция биологических систем не единственный "источник вдохновения" создателей новых методов, моделирующих природные процессы. Нейронные сети (neural networks), например, основаны на моделировании поведения нейронов в мозге. Они могут использоваться для ряда задач классификации, например, задачи распознавания образов, машинного обучения, обработки изображений и др. Область их приложения частично перекрывается со сферой применения ГА. Моделируемый отжиг (simulated annealing) - другая методика поиска, которая основана скорее на физических, а не биологических процессах.
Эволюционный процесс представляется как способность «лучших» хромосом оказывать большее влияние на состав новой популяции на основе длительного выживания из более многочисленного потомства. Основные этапы эволюционного поиска следующие:
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(x)=x 2 на целочисленном интервале . Традиционными методами можно изменять значения переменной x, пока не получим максимальное значение f(x).
Для объяснения и реализации ПГА построим следующую таблицу:
|
Номер хромосом |
Хромосома (двоичный код) |
Десятичный код |
Значение ЦФ |
Значение ЦФ, в процентах |
В столбце 2 табл. расположены 4 хромосомы (представленные в двоичном коде), сгенерированные случайным образом. Значение ЦФ для каждой хромосомы (столбец 4) определяется как квадрат значения десятичного кода двоичного числа, которое приведено для хромосом во втором столбце таблицы. Тогда суммарное значение ЦФ всех хромосом равно 890. Для селекции хромосом используется оператор репродукции на основе колеса рулетки. На рисунке поля колеса рулетки соответствуют значению ЦФ каждой хромосомы в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для реализации следующего оператора. Очевидно, не всегда хромосома с большим значением ЦФ в результате ОР будет выбрана для дальнейших преобразований.
Колесо рулетки для примера
На основе реализации ОР выбираются хромосомы для применения ОК. Оператор кроссинговера, как правило, выполниться в 3 шага, одним из ОК описанным выше. Точка разрыва kвыбирается случайно между 1 и числом равным длине хромосомы минус единица, то есть в интервале (1, L-1). Длина хромосомы L – это число значащих цифр в ее коде. В рассматриваемом примере таблицы длина каждой хромосомы равна пяти (L=5). На основе ОК создаются две новые хромосомы, путем обмена их частей между позициями (k+1) и L соответственно.
Например, рассмотрим хромосомы 1 и 2 из начальной популяции. Пусть k=1. Тогда получим:
P 1 0 | 1 1 0 0 До применения оператора кроссинговера
P 2 1 | 0 0 0 0,
-----------------
P 1 0 0 0 0 0 После применения оператора кроссинговера
P 2 1 1 1 0 0.
Работа ПГА начинается с репродукции. Хромосомы для следующей генерации выбираются путем вращения колеса рулетки. В примере колесо рулетки вращается 4 раза. Это число соответствуют мощности начальной популяции.
Величину отношения
называют вероятностью выбора копий
(хромосом) при реализации оператора
репродукции и обозначают:
где f i (x)значение ЦФ i-й хромосомы в популяции,
sum f(x)суммарное
значение ЦФ всех хромосом в популяции.
Величину
также
называют нормализованной вероятностью
выбора. Ожидаемое число копий
i-й хромосомы после реализации ОР определяются по формуле:
где
число анализируемых
хромосом, причемN G
включается вN.
Ожидаемое число копий хромосомы P i , переходящее в следующее поколение, также иногда определяют на основе выражения:
.
где
среднее значение
ЦФ по всей популяции.
Тогда для рассматриваемого примера, ожидаемое число копий для первой хромосомы из таблицы равно 0,164=0,64 копий, для второй0,294=1,16 копий, для третьей0,054 = 0,2 и наконец для четвертой0,54=2. Используя модель «бросание монеты» можно определить число полученных копий. Например, (см. столбец 7 таблицы) хромосомы P 1 и P 2 получают 1 копию, хромосома P 4 – 2 копии, и хромосома 3 не получает копий. Сравнивая этот результат с ожидаемым числом копий, получаем то, что «лучшие» хромосомы дают большее число копий, «средние» остаются и «плохие» удаляются после реализации оператора репродукции.
|
Начальная популяция |
Значение f i (x)/sum |
Ожидаемое число копий |
Число полученных копий |
|||
|
Суммарное значение ЦФ (sumf(x)) | ||||||
|
Среднее значение ЦФ
| ||||||
|
Max значение ЦФ | ||||||
Для рассматриваемого примера построим таблицу. В столбце 2 приведен вид 4 хромосом после выполнения оператора репродукции. В столбце 3 приведены списки пар хромосом, которые выбраны случайным образом для реализации оператора кроссинговера. В столбце 4 указан номер позиции для точки разреза хромосом. В столбце 5 приведен вид 4 хромосом после выполнения оператора кроссинговера. В столбце 6 приведены значения десятичного кода двоичного числа каждой хромосомы столбца 5. В столбце 7 приведено значение f(x) для каждой из 4 хромосом новой популяции. В строке 5 приведено суммарное значение ЦФ хромосом новой популяции, в строке 6 –среднее значение их ЦФ, а в строке 7- максимальное значение ЦФ хромосомы из новой популяции.
|
Популяция после оператора репродукции |
выбранные случайно |
Новая популяция | ||||
|
| ||||||
Применяя к популяции полученной после реализации оператора репродукции (столбец 2 табл.) оператор кроссинговера, получим новую популяцию хромосом (5 столбец таблицы). В принципе оператор кроссинговера можно применять любое число раз. После проведения одной генерации ПГА улучшились все показатели: среднее и максимальное значение ЦФ.
Далее, согласно схеме выполнения ПГА, реализуется оператор мутации. Существует большое количество видов операторов мутации. Заметим, что эти операторы соответствуют перестановкам элементов внутри заданного множества. Очевидно, что при небольшой длине хромосомы L (порядка 1020) можно выполнить полный перебор за приемлемое время и найти наилучшие решения. При увеличении L до 50200 и выше, полный перебор произвести затруднительно, и необходимы другие механизмы поиска. Здесь как раз и приходит на помощь направленно-случайный поиск, который реализуется на основе ПГА.
Отметим, что глобальный максимум можно было найти еще на этапе реализации кроссинговера. Для этого необходимо было увеличить пространство поиска. Например, если в столбце 5 табл. выбрать хромосомы P 2 и P 4 и между ними выполнить оператор кроссинговера (точка ОК выбрана случайно и равна 3), то получим:
P 2: 1 0 1 | 1 1 (ЦФ-23)
P 4: 1 1 1 | 0 0 (ЦФ-28)
P 2 : 1 0 1 0 0 (ЦФ-20)
P 4 : 1 1 1 1 1 (ЦФ-31).
Решение P 4 , полученное в результате применения ОК случайным образом, является наилучшим результатом (глобальным оптимумом).
Как отмечалось выше, в генетических алгоритмах можно выделять два основных механизма воспроизводства хромосом:
потомки являются точными копиями родителей (неполовое воспроизводство без мутации);
потомки имеют «большие» отличия от родителей.
В генетических алгоритмах в основном используют комбинации этих механизмов. Отметим, что в инженерных задачах начальная популяция может выбираться любым образом, например, моделированием «бросания монеты» (орел = 1, решка = 0). Тогда оператор репродукции выполняется через моделирование движения колеса рулетки. Оператор кроссинговера в задачах вычислительного характера обычно выполняется через двоичное декодирование двух положений монеты. Часто применяют другие типы ОК и другие технологии его выполнения. Вероятность ОК допускается равной Рr(ОК) = 1.0 и меньше, вероятность ОМ допускается равной Рr(ОМ) = 0.01 и больше. В общем случае вероятность применения оператора мутации зависит от знаний о решаемой задаче.
Приведем другой стандартный тип генетического алгоритма, описанный Л.Девисом:
Инициализация популяции хромосом.
Оценка значения каждой хромосомы в популяции.
Создание новых хромосом посредством скрещивания текущих хромосом; применение операторов мутации и рекомбинации.
Устранение хромосом из популяции, чтобы освободить место для новых хромосом.
Оценка значений новых хромосом и вставка их в популяцию.
Если время, заданное на реализацию алгоритма, закончено, то останов и возврат к наилучшей хромосоме, если нет, то переход к 3.
Конец работы алгоритма.
Сравнивая описание ПГА Д. Гольдберга, Д. Холланда и Л. Девиса, видно, что в них реализована одна основная идея моделирования эволюции с некоторыми модификациями. Однако заметим, что эти изменения могут существенно влиять на окончательное качество решения.
Приведем пример модифицированного ПГА:
1. Создание начальной популяции решений.
2. Моделирование популяции (определение ЦФ для каждой хромосомы).
3. Пока не проведено необходимое число генераций или не закончилось время, заданное на реализацию алгоритма или не найдено оптимальное значение ЦФ (если оно известно):
а) выбор элементов для репродукции;
Применение:
б) оператора кроссинговера для создания потомков;
в) оператора мутации;
г) оператора инверсии;
д) оператора транспозиции;
е) оператора транслокации;
ж) оператора сегрегации;
з) оператора удаления вершин;
и) оператора вставки вершин;
к) рекомбинация родителей и потомков для создания новой генерации;
л) оператора редукции.
4. Реализация новой генерации.
Новые модификации ГА могут строиться путем объединения, например, пунктов «б – л» или их частичного устранения, или их перестановок, а также на основе применения адаптационных принципов управления эволюционным поиском.
Введение в аксиоматическую теорию генетических алгоритмов
Сформулируем описание генетических алгоритмов в виде научной теории. Отметим, что способ построения научной теории, в основе которой используются исходные положения, называемые аксиомами, а все остальные предложения теории получаются как логические следствия аксиом, называется аксиоматический метод .Аксиома - положение принимаемое без доказательств в качестве исходного, отправного для данной теории. Основным в нем является метод интерпретаций. Тогда для генетических алгоритмов можно построить следующую базовую теорию.
Пусть каждому исходному понятию и отношению аксиоматической теории ГА поставлен в соответствие некоторый конкретный математический объект. Совокупность таких объектов называется полем интерпретации . Всякому утверждению U теории ГА ставится в соответствие некоторое высказывание U* об элементах поля интерпретации, которое может быть истинным или ложным. Тогда можно сказать, что утверждение U теории ГА соответственно истинно или ложно в данной интерпретации. Поле интерпретации и его свойства сами обычно являются объектом рассмотрения другой теории ПГА, которая в частности может быть аксиоматической. Этот метод позволяет доказывать суждения типа: если теория ГА непротиворечива, то непротиворечива и теория ПГА.
Пусть теория ГА проинтерпретирована в теории ПГА таким образом, что все аксиомы A i теории ГА интерпретируются истинными суждениями A i * теории ПГА. Тогда всякая теорема теории ГА, то есть всякое утверждение А, логически выведенное из аксиом A i в ГА, интерпретируется в ПГА некоторым утверждением A * , выводимым в ПГА из интерпретаций A i * аксиом A i и, следовательно, истинным.
Метод интерпретаций позволяет также решать вопрос о независимости систем аксиом: для доказательства того, что аксиома А теории ГА не зависит от остальных аксиом этой теории, то есть не выводима из них, и, следовательно, необходима для получения всего объема данной теории, достаточно построить такую интерпретацию ГА, в которой аксиома А была бы ложна, а все остальные аксиомы этой теории истинны. Уточнением понятия аксиоматической теории является понятие формальной системы . Это позволяет представлять математические теории как точные математические объекты и строить общую теорию или метатеорию таких теорий. Всякая формальная система строится как точно очерченный класс выражений – формул, в котором некоторым точным образом выделяется подкласс формул, называемых теоремами данной формальной системе. При этом формулы формальной системы непосредственно не несут в себе содержательного смысла. Их можно строить из произвольных знаков и символов. Общая схема построения произвольной формальной системы ГА такова:
Язык системы ГА: аппарат алгебры логики; теория множеств; теория графов, теория алгоритмов, основные положения биологии и теории систем.
Алфавит – перечень элементарных символов системы: двоичный, десятичный, буквенный, Фибоначчи и др.
Правила образования (синтаксис), по которым из элементарных символов строятся формулы теории ГА:
построение моделей эволюций;
конструирования популяций;
построения ЦФ;
разработки генетических операторов;
репродукции популяций;
рекомбинации популяций;
редукции;
адаптации.
Последовательность элементарных символов считается формулой тогда и только тогда, когда она может быть построена с помощью правил образования.
Аксиомы системы ГА. Выделяется некоторое множество конечных формул, которые называются аксиомами системы. В ГА существует большое число наборов аксиом. Например, базовый набор аксиом следующий:
Популяция конструируется случайным образом.
Выполнение оператора репродукции производится на основе «колеса рулетки».
Обязательное использование операторов кроссинговера и мутации.
Размер популяции после каждой генерации остается постоянным.
Размер популяции меняется.
Число копий (решений), переходящих в следующую генерацию меняется.
Целевая функция определяется на основе принципа «Выживание сильнейших».
Правила вывода ГА. Фиксируется конечная совокупность предикатов П 1 , П 2 ,…, П k на множестве всех формул системы. Пусть П (x 1 ,…,x ni +1) – какой-либо из этих предикатов (n i 0) если, для данных формулF 1 ,…,F ni +1 утверждение П (F 1 ,…,F ni +1) истинно, то говорят, что формулаF ni +1 непосредственно следует из формулF 1 ,…,F ni +1 по правилу П i .
Заданием 1,2,3 исчерпывается задание формальной системы ГА как точного математического объекта. При этом степень точности определяется уровнем точности задания алфавита, правил образования и правил вывода. Выводом системы ГА называется всякая конечная последовательность формул, в которой каждая формула либо является аксиомой системы ГА, либо непосредственно следует из каких-либо предшествующих ей (этой последовательности) формул по одному из правил вывода П i системы.
Всякую конкретную математическую теорию ГА можно перевести на язык подходящей формальной системы таким образом, что каждое ложное или истинное предложение теории ГА выражается некоторой формулой системы. Метод интерпретаций позволяет устанавливать факт относительной непротиворечивости, то есть доказывать суждения типа: «если теория ГА непротиворечива, то непротиворечива и теория ПГА». В общем случае, проблема непротиворечивости не решена и является одной из основных в математике.
Предлагается ряд основных стратегий взаимодействия методов эволюционного и локального поиска:
«поиск – эволюция»;
«эволюция – поиск»;
«поиск – эволюция - поиск»;
«эволюция – поиск - эволюция».
Заметим, что иерархически можно строить стратегии такого типа любого уровня сложности. Например, «эволюция – поиск – эволюция - поиск – эволюция - поиск» и т.д. Отметим, что такое построение зависит от наличия вычислительных ресурсов и времени, заданного на получения окончательного решения.
В первом случае любым из описанных алгоритмов поиска или их комбинаций определяется одно или пара альтернативных решений задачи. На основе этих решений строится популяция, к которой применяется одна из схем эволюции. Далее процесс продолжается итерационно до достижения критерия остановки.
Во втором случае конструируется популяция и реализуется одна из схем эволюции. Лучшее решение анализируется и улучшается (если это возможно) одним из алгоритмов поиска. Далее процесс выполняется, как в первом случае. В остальных случаях процесс поиска результатов выполняется аналогично.
Выводы
Генетические алгоритмы - поисковые алгоритмы, основанные на механизмах натуральной селекции и натуральной генетики. Они являются мощной стратегией выхода из локальных оптимумов. Она заключается в параллельной обработке множества альтернативных решений, концентрируя поиск на наиболее перспективных из них. Причем периодически в каждой итерации можно проводить стохастические изменения в менее перспективных решениях.
Существует четыре основных отличия ГА от оптимизационных методов:
прямое преобразование кодов;
поиск из популяции, а не из единственной точки;
поиск через элементы (слепой поиск);
поиск, использующий стохастические и модифицированные операторы, а не детерминированные правила.
Использование ГА при решении инженерных задач позволяет уменьшить объем и время вычислений и упростить моделирование функций, сократить число ошибок моделирования.
Эволюция в природе показала себя как мощный механизм развития и приспособления живых организмов к окружающей среде и удивляет многообразием и эффективностью решений. Поэтому исследователи в области компьютерных технологий обратились к природе в поисках новых алгоритмов.
Группа алгоритмов, использующих в своей основе идею эволюции Дарвина, называется эволюционными алгоритмами. В ней выделяют следующие направления.
Генетические алгоритмы применяются для решения таких задач, как:
Фактически, генетические алгоритмы максимизируют многопараметрические функции. Поэтому их область применения столь широка. Все приведенные задачи решаются именно путем формирования функции, зависящей от некоторого числа параметров, глобальный максимум которой будет соответствовать решению задачи.
Живые существа характеризуются их внешними параметрами (фенотипом). Некоторые из параметров оказываются полезными для выживания и размножения, другие скорее вредят. Все внешние данные особи кодируются ее цепью ДНК (генотипом). Отдельные участки этой цепи (гены) определяют различные параметры особи.
Согласно теории эволюции Чарльза Дарвина, особи популяции конкурируют между собой за ресурсы (пищу) и за привлечение брачного партнера. Те особи, которые наиболее приспособлены к окружающим условиям, проживут дольше и создадут более многочисленное потомство, чем их собратья. Скрещиваясь, они будут передавать потомкам часть своего генотипа. Некоторые дети совместят в себе части цепи ДНК, отвечающие за наиболее удачные качества родителей, и, таким образом, окажутся еще более приспособленными.
Те особи, которые не обладают качествами, способствующими их выживанию, с большой вероятностью не проживут долго и не смогут создать многочисленное потомство. Кроме того, им сложнее будет найти хорошую пару для скрещивания, поэтому с большой вероятностью генотип таких особей исчезнет из генофонда популяции.
Изредка происходит мутация: некоторый случайный нуклеотид цепи ДНК особи может измениться на другой. Если полученная цепь будет использоваться для создания потомства, то возможно появление у детей совершенно новых качеств.
Естественный отбор, скрещивание и мутация обеспечивают развитие популяции. Каждое новое поколение в среднем более приспособлено, чем предыдущее, т. е. оно лучше удовлетворяет требованиям внешней среды. Этот процесс называется эволюцией.
Рассматривая эволюцию в природе, возникает мысль о том, что можно искусственно отбирать особи, подходящие нам по некоторым параметрам, создавая таким образом искусственные внешние условия. Это называется селекцией и используется людьми для получения новых пород животных, к примеру, дающих больше молока или с более густой шерстью. Но почему бы не устроить собственную эволюцию с помощью компьютера? Действительно, пусть есть функция, которая по заданному набору численных параметров возвращает некоторое значение (многопараметрическая функция). Создадим множество строк, каждая из которых будет кодировать вектор чисел (длина вектора равна количеству параметров функции). По заданному вектору можно высчитать соответствующее ему значение функции. Те строки, для которых это значение велико, будем считать более приспособленными, чем те, для которых оно мало. Запуская эволюцию на строках по подобию природной, на каждом поколении будем получать строки со все большими значениями функции. Таким образом, такого рода эволюция решает задачу максимизации многопараметрической функции.
Родителем современной теории генетических алгоритмов (ГА) считается Холланд (J. Holland), чья работа «Adaptation in Natural and Artificial Systems» (1975), стала классикой в этой области. В ней Холланд впервые ввел термин «генетический алгоритм». Сейчас описанный там алгоритм называют «классический ГА» (иногда «канонический ГА», canonical GA), а понятие «генетические алгоритмы» стало очень широким, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического ГА.
Ученики Холланда Кеннет Де Йонг (Kenneth De Jong) и Дэвид Голдберг (David E. Goldberg) внесли огромный вклад в развитие ГА. На книгу Голдберга «Genetic algorithms in search optimization and machine learning» (1989), ссылаются авторы практически каждой работы по этой теме.
Как уже было сказано выше, генетические алгоритмы работают по аналогии с природой. Они оперируют с совокупностью «особей», представляющих собой строки, каждая из которых кодирует одно из решений задачи. Приспособленность особи оценивается с помощью специальной функции. Наиболее приспособленные получают шанс скрещиваться и давать потомство. Наихудшие особи удаляются и не дают потомства. Таким образом, приспособленность нового поколения в среднем выше предыдущего.
Итак, пусть перед нами стоит задача оптимизации. Варьируя некоторые параметры, к примеру, если решать задачу размещения, координаты размещаемых элементов, нужно найти такую их комбинацию, чтобы минимизировать занимаемую площадь. Такую задачу можно переформулировать как задачу нахождения максимума некоторой функции f (x 1 , x 2 , …, x n). Эта функция называется функцией приспособленности (fitness function) и используется для вычисления приспособленности особей. Она должна принимать неотрицательные значения, а область определения параметров должна быть ограничена.
Если нам, к примеру, требуется найти минимум некоторой функции, то достаточно перенести область ее значений на положительную область, а затем инвертировать. Таким образом, максимум новой функции будет соответствовать минимуму исходной.
В генетических алгоритмах никак не используются такие свойства функции, как непрерывность, дифференцируемость и т. д. Она подразумевается как устройство (blackbox ), которое на вход получает параметры, а на выход выводит результат.
Теперь обратимся к кодировке набора параметров. Закодируем каждый параметр строкой битов. Если он принимает непрерывное множество значений, то выберем длину строки в соответствии с требуемой точностью. Таким образом, параметр сможет принимать только дискретные значения (этих значений будет степень 2), в некотором заданном диапазоне.
Например, пусть переменная x k принадлежит отрезку [ x min , x max ]. Закодируем ее бинарной строкой из l битов. Тогда строка s k обозначает следующее значение переменной x k:
X k = x min + s k (x max − x min) ⁄ 2 l
если в формуле s k обозначает значение бинарного числа, кодируемого этой строкой.
Если же некоторый параметр принимает конечное количество значений, к примеру, целые от 0 до 1000, то закодируем его бинарной строкой достаточной длины, в данном случае 10. Лишние 23 строки могут повторять уже закодированные значения параметра, либо они могут быть доопределены в функции приспособленности как «худшие», т. е. если параметр кодируется одной из этих строк, то функция принимает заведомо наименьшее значение.
Итак, мы определили для каждого параметра строку, кодирующую его. Особью будет называться строка, являющаяся конкатенацией строк всего упорядоченного набора параметров:
101100 11001011 01101100 1100 1 11101 | x 1 | x 2 | | | | x n |
Приспособленность особи высчитывается следующим образом: строка разбивается на подстроки, кодирующие параметры. Затем для каждой подстроки высчитывается соответствующее ей значение параметра, после чего приспособленность особи получается как значение функции приспособленности от полученного набора.
Вообще говоря, от конкретной задачи зависят только такие параметры ГА, как функция приспособленности и кодирование решений. Остальные шаги для всех задач производятся одинаково, в этом проявляется универсальность ГА.
На рисунке изображена схема работы любого генетического алгоритма:
В классическом ГА начальная популяция формируется случайным образом. Фиксируется размер популяции (количество особей в ней будем обозначать символом N), который не изменяется в течение работы всего алгоритма. Каждая особь генерируется как случайная L -битная строка, где L — длина кодировки особи, она тоже фиксирована и для всех особей одинакова.
Следует заметить, что каждая особь является одним из решений поставленной задачи. Более приспособленные особи — это более подходящие ответы. Этим ГА отличается от большинства других алгоритмов оптимизации, которые оперируют лишь с одним решением, улучшая его.
Шаг алгоритма состоит из трех стадий: генерация промежуточной популяции (intermediate generation ) путем отбора (selection ) текущего поколения (current generation ), скрещивание (recombination ) особей промежуточной популяции путем кроссовера (crossover ), что приводит к формированию нового поколения (next generation ), и мутация нового поколения. На рисунке изображены первые две стадии:
Промежуточная популяция — это набор особей, которые получили право размножаться. Приспособленные особи могут быть записаны туда несколько раз. «Плохие» особи с большой вероятностью туда вообще не попадут.
В классическом ГА вероятность каждой особи попасть в промежуточную популяцию пропорциональна ее приспособленности, т. е. работает пропорциональный отбор (proportional selection ). Можно его реализовать следующим образом: пусть особи располагаются на колесе рулетки, так что размер сектора каждой особи пропорционален ее приспособленности. Изначально промежуточная популяция пуста. N раз запуская рулетку, выберем требуемое количество особей для записи в промежуточную популяцию. Ни одна выбранная особь не удаляется с рулетки. Такой отбор называется stochastic sampling .
Другой способ отбора, который также является пропорциональным, это . Для каждой особи вычисляется отношение ее приспособленности к средней приспособленности популяции. Целая часть этого отношения указывает, сколько раз нужно записать особь в промежуточную популяцию, а дробная — это ее вероятность попасть туда еще раз. Пусть, к примеру, для некоторой особи i f i ⁄ < f > = 1.36 (< f > — средняя приспособленность текущей популяции). Тогда она будет выбрана один раз, а затем с вероятностью 0.36 еще раз. Реализовать такой способ отбора удобно следующим образом: расположим особи на рулетке так же, как было описано. Теперь пусть у рулетки не одна стрелка, а N , причем они отсекают одинаковые сектора. Тогда один запуск рулетки выберет сразу все N особей, которые нужно записать в промежуточную популяцию. Такой способ иллюстрируется следующим рисунком:
После отбора особи промежуточной популяции случайным образом разбиваются на пары. Каждая из них с вероятностью p c скрещивается, т. е. к ней применяется оператор кроссовера, в результате чего получаются два потомка. Они записываются в новое поколение. Если же паре не выпало скрещиваться, в новое поколение записываются сами особи этой пары.
В классическом генетическом алгоритме применяется одноточечный оператор кроссовера (1-point crossover ): для родительских хромосом (т. е. строк) случайным образом выбирается точка раздела, и они обмениваются отсеченными частями. Полученные две строки являются потомками:
11010 01100101101 ⇒ 10110 01100101101 10110 10011101001 ⇒ 11010 10011101001К полученному в результате скрещивания новому поколению применяется оператор мутации. Каждый бит каждой особи популяции с вероятностью p m инвертируется. Эта вероятность обычно очень мала, менее 1%.
1011001100 101101 ⇒ 1011001101 101101
Таким образом, процесс отбора, скрещивания и мутации приводит к формированию нового поколения. Шаг алгоритма завершается объявлением нового поколения текущим. Далее все действия повторяются.
Вообще говоря, такой процесс эволюции может продолжаться до бесконечности. Критерием останова может служить заданное количество поколений или схождение (convergence ) популяции.
Схождением называется такое состояние популяции, когда все строки популяции почти одинаковы и находятся в области некоторого экстремума. В такой ситуации кроссовер практически никак не изменяет популяции. А вышедшие из этой области за счет мутации особи склонны вымирать, так как чаще имеют меньшую приспособленность, особенно если данный экстремум является глобальным максимумом. Таким образом, схождение популяции обычно означает, что найдено лучшее или близкое к нему решение.
Ответом на поставленную задачу может служить набор параметров, кодируемый наилучшей особью последнего поколения.
Шаблоном (schema ) называется строка длины L (т. е. той же длины, что и любая строка популяции), состоящая из символов {0, 1, *} (где * — «don"t care» символ). Будем говорить, что строка является представителем данного шаблона, если в позициях, где знак шаблона равен 0 или 1, она имеет тот же символ. Например, у шаблона 01*0*110 следующие представители:
Порядком (order ) шаблона называется количество фиксированных битов в нем. Определяющей длиной (defining length ) шаблона называется расстояние между его крайними фиксированными битами. Например, для шаблона *1***01* порядок o = 3, а определяющая длина Δ = 5.
Очевидно, что количество представителей шаблона H равно 2 L − o (H) , а количество шаблонов равно 3 L (действительно, шаблоны — это строки, у которых на каждой позиции может находиться один из трех символов).
Если представить пространство поиска в виде гиперкуба, то строки это его вершины, а шаблон определяет в нем гиперплоскость. К примеру, шаблон **1 определяет правую грань этого трехмерного куба:
Поэтому термины «гиперплоскость» и «шаблон» взаимозаменяемы. Следующий рисунок изображает другое представление шаблонов:
На нем видно, что некоторые шаблоны имеют с среднем по всему пространству поиска большую приспособленность, чем другие.
Приспособленностью шаблона называется средняя приспособленность строк из популяции, являющихся его представителями. Следует заметить, что эта величина зависит от популяции, и поэтому меняется со временем.
Внешне кажется, что генетический алгоритм при отборе выбирает строку, однако при этом неявным образом происходит выборка шаблонов, представителем которых она является. Это означает, что на каждом поколении количество представителей шаблона изменяется в соответствии с текущей приспособленностью этого шаблона. У «хороших» шаблонов представители в среднем более приспособленные, а значит, они чаще будут выбираться в промежуточную популяцию. «Плохие» шаблоны имеют много шансов вымереть. Одна строка является представителем сразу многих шаблонов (а именно 2 L: на каждой позиции мы либо оставляем бит строки, либо заменяем его на «*»). Поэтому при отборе одной строки отбирается сразу целое множество шаблонов. Это явление получило название неявный параллелизм (implicit parallelism ).
Теорема шаблонов (The Schema Theorem ) была приведена в упомянутой выше работе Холланда и является первой попыткой объяснить, почему генетические алгоритмы работают. Она показывает, как изменяется доля представителей шаблона в популяции.
Пусть M (H , t) — число представителей шаблона H в t -ом поколении. В силу того, что при построении промежуточной популяции используется пропорциональный отбор, в ней количество представителей данного шаблона будет
M (H , t + intermediate) = M (H , t) f (H , t) ⁄ < f (t)>
где f (H , t) — приспособленность шаблона H в t -ом поколении, а < f (t)> — средняя приспособленность t -го поколения.
Особи промежуточной популяции с вероятностью p c подвергаются кроссоверу. Одноточечный кроссовер может разрушить шаблон, что означает, что один из родителей был представителем рассматриваемого шаблона, но ни один из детей уже таковым являться не будет. Вероятность разрушения меньше, чем
Δ(H) (1 − P (H , t) f (H , t) ⁄ < f (t)>) ⁄ (L −1)
где P(H, t) — доля представителей шаблона H в t -ом поколении. Первый множитель произведения равен вероятности точки раздела попасть между фиксированными битами шаблона, а второй — вероятности выбрать в пару представителя другого шаблона.
Действительно, кроссовер разрушает шаблон не чаще, чем когда второй родитель (а он выбирается в промежуточной популяции) не является представителем этого шаблона, и при этом точка раздела попадает между фиксированными битами шаблона. Даже в этих ситуациях он не обязательно разрушается, например, если мы рассматриваем шаблон 11****, а кроссоверу подвергаются строки 110101 и 100000, и точка раздела попадает между первыми двумя битами, то, хотя вторая строка не является представителем нужного шаблона, все равно один из потомков окажется подходящим и шаблон не разрушится.
Таким образом, после кроссовера, переходя от количества представителей к их доле, получаем следующее неравенство:
< f (t)>) ⁄ (L −1)] ⁄ < f (t)>
Теперь учтем влияние мутации. Для каждого фиксированного бита вероятность того, что он не будет инвертирован, равна (1 − p m). Поскольку всего в шаблоне фиксированных битов o (H), то верна следующая итоговая формула теоремы шаблонов:
P (H , t + 1) ≥ P (H , t) f (H , t) (1 − p m) o (H) ⁄ < f (t)>
Полученное выражение не слишком удачно для анализа работы генетического алгоритма. Во-первых, в нем присутствует знак неравенства, связанный также с тем, что мы не учитывали случаи, когда рассматриваемый шаблон получается в результате кроссовера пары строк, не являющихся его представителями. Во-вторых, приспособленность шаблона и средняя приспособленность популяции быстро изменяются от поколения к поколению, поэтому полученное неравенство хорошо описывает ситуацию только для следующего поколения.
Тем не менее, теорема шаблонов является хоть каким-то теоретическим обоснованием работы классического генетического алгоритма (следует заметить, что она верна только для классического ГА с его пропорциональным отбором и одноточечным кроссовером). На данный момент существуют более точные версии этой теоремы, а также другие рассуждения, доказывающие целесообразность использования генетических алгоритмов.
Из полученного в теореме шаблонов выражения видно, что шаблоны с малым порядком и малой определяющей длиной менее подвержены разрушению в результате кроссовера или мутации, поэтому рост (или уменьшение) их доли в популяции происходит динамичнее. Шаблоны с высокой приспособленностью, малым порядком и малой определяющей длиной называются строительными блоками (building blocks ).
Холланд (1992) показал, что в то время, как ГА обрабатывает N строк на каждом поколении, в то же время неявно обрабатываются порядка N 3 гиперплоскостей. Это доказывается с рассчетом на реально применимые размеры популяции и длины строки. Практически это означает, что большая популяция имеет возможность локализовать решение быстрее, чем маленькая. Для оценки рекомендуемого размера популяции в зависимости от длины строки можно вспомнить, что всего гиперплоскостей 3 L .
Еще один аргумент в пользу больших популяций: в случае, если разброс приспособленностей представителей блока большой, то вероятность выбрать некоторое количество представителей блока с меньшей приспособленностью вместо представителей более хорошего достаточно велика, поскольку отдельные особи «слабого» блока могут оказаться лучше, чем многие особи «сильного». Увеличение размера популяции увеличит количество осуществляемых при генерации промежуточной популяции выборок, и вероятность сделать в итоге выбор неверного блока окажется достаточно малой.
В гипотезе о строительных блоках считается, что в процессе приближения популяции к глобальному оптимуму порядок и приспособленность строительных блоков увеличиваются. Это легко видно на простом примере:
Все локальные максимумы приведенной функции приходятся на блок **0*, а минимумы — на **1*, поэтому очевидно, что после отбора основная часть особей будут представителями первого блока. Левая половина графика в среднем ниже правой, поэтому доля блока 1*** будет преобладать над долей 0***. Получается, что основная масса особей окажутся представителями блока 1*** и в то же время **0*, значит, большое их количество будут представителями блока 1*0*. Теперь, выбирая между блоками 100* и 110*, получаем, что второй блок будет преобладать над первым. Таким образом, можно сказать, что хорошие строительные блоки малого порядка сложились в приспособленные блоки большего порядка, и в результате мы оказались в области глобального максимума, чем приблизились к решению задачи.
Генетический алгоритм производит поиск решений двумя методами одновременно: отбором гиперплоскостей (hyperplane sampling ) и методом hill-climbing . Кроссовер осуществляет первый из них, поскольку комбинирует и совмещает шаблоны родителей в их детях. Мутация обеспечивает второй метод: особь случайным образом изменяется, неудачные варианты вымирают, а если полученное изменение оказалось полезным, то, скорее всего, эта особь останется в популяции.
Возникает вопрос: какой же из этих методов лучше осуществляет поиск хороших решений? Исследования показали, что на простых задачах, таких, как максимизация унимодальной функции, ГА с мутацией (и без кроссовера) находят решение быстрее. Также для такого метода требуется меньший размер популяции. На сложных многоэкстремальных функциях лучше использовать ГА с кроссовером, поскольку этот метод более надежен, хотя и требует большего размера популяции.
С точки зрения теоремы шаблонов, мутация только вредит росту количества представителей хороших шаблонов, поскольку лишний раз их разрушает. Однако мутация просто необходима для ГА с малым размером популяции. Дело в том, что для малочисленных популяций свойственна преждевременная сходимость (premature convergence ). Это ситуация, когда в некоторых позициях все особи имеют один и тот же бит, но такой набор битов не соответствует глобальному экстремуму. При этом кроссовер практически не изменяет популяции, т. к. все особи почти одинаковы. В этом случае мутация способна инвертировать «застрявший» бит у одной из особей и вновь расширить пространство поиска.
Введем понятие давления отбора (selection pressure ) — это мера того, насколько различаются шансы лучшей и худшей особей популяции попасть в промежуточную популяцию. Для пропорционального отбора эта величина имеет свойство уменьшаться с увеличением средней приспособленности популяции. Действительно, при этом для каждой особи отношение f ⁄ < f > стремится 1, а значит шансы плохой и хорошей особей создать потомство уравниваются.
При увеличении p c или p m и при уменьшении давления отбора (например, за счет использования других стратегий отбора) размножение представителей приспособленных шаблонов замедляется, но зато происходит интенсивный поиск других шаблонов. Обратно, уменьшение p c или p m и увеличение давления отбора ведет к интенсивному использованию найденных хороших шаблонов, но меньше внимания уделяется поиску новых. Таким образом, для эффективной работы генетического алгоритма необходимо поддерживать тонкое равновесие между исследованием и использованием . Это можно сформулировать также как необходимость сбалансированной сходимости ГА: быстрая сходимость может привести к схождению к неоптимальному решению, а медленная сходимость часто приводит к потере найденной наилучшей особи.
Методология управления сходимостью классического ГА до сих пор не выработана.
Классический ГА хорош для понимания работы генетических алгоритмов, однако он не является наиболее эффективным из них. Сейчас мы рассмотрим различные варианты кодировки, генетические операторы и стратегии отбора, а также другие модели ГА.
Если сравнивать кодирование бинарным алфавитом и небинарным, то первый вариант обеспечивает лучший поиск с помощью гиперплоскостей, т. к. предоставляет максимальное их количество. Действительно, если требуется закодировать 2 L значений, то для бинарного алфавита количество гиперплоскостей будет 3 L , тогда как при использовании, к примеру, четырехзначного алфавита длина слов будет в 2 раза меньше, и гиперплоскостей будет 5 L ⁄ 2 , т. е. меньше.
Еще один аргумент в пользу бинарных алфавитов — это то, что для встречаемости каждого символа в каждой позиции им требуется меньший размер популяции. Действительно, даже если имеется всего две строки, есть вероятность, что на каждой позиции в популяции есть и 0, и 1 (т. е. одна строка является результатом инвертирования другой). Если же алфавит большей мощности, то популяция из двух строк заведомо не будет содержать в каждой позиции несколько символов, и до применения мутации большая часть пространства поиска будет недоступна с точки зрения кроссовера. После применения мутации станет недоступна другая часть.
С другой стороны, небинарные алфавиты зачастую обеспечивают более наглядное представление решений задачи.
Исследования показали, что для большинства функций генетические алгоритмы будут работать лучше, если закодировать параметры в строку кодом Грея , а не прямым бинарным кодом. Это связано с т. н. Hamming cliffs , когда, к примеру, числа 7 и 8 различаются на 4 бита. Бинарное кодирование добавляет дополнительные разрывы, что осложняет поиск. Это можно показать на примере: пусть требуется минимизировать функцию f (x) = x 2 . Если в популяции изначально преобладали отрицательные хорошие решения, то с большой вероятностью она сойдется к −1 = 11…1. При этом достигнуть глобального минимума будет практически невозможно, поскольку любые изменения одного бита будут приводить к ухудшению решения. При кодировании кодом Грея такой проблемы не возникает.
Кодирование с плавающей точкой тоже является более удачным, чем прямое бинарное. На вопрос, лучше ли оно, чем кодирование кодом Грея, можно ответить, что на каких-то задачах лучше работает первый вариант, на других — второй. Как определить, какой вариант использовать для конкретной задачи, пока неизвестно.
Одноточечный кроссовер мы рассмотрели выше.
При двухточечном кроссовере для родительской пары случайным образом выбираются 2 точки раздела, и родители обмениваются промежутками между ними. В результате получаются два ребенка. Удобно в этом случае представить строки в виде колец:
Определяющая длина в этом случае тоже измеряется в кольце, поэтому для такого шаблона, как 1*****1, при одноточечном кроссовере определяющая длина равна 6, и точка раздела всегда попадает между крайними фиксированными битами, а при двухточечном эта длина равна 1.
Следует заметить, что одноточечный кроссовер является частным случаем двухточечного, когда одна из точек раздела фиксирована.
Однородный кроссовер осуществляется следующим образом: один из детей наследует каждый бит с вероятностью p 0 у первого родителя, а иначе у второго. Второй ребенок получает все остальные не унаследованные биты. Обычно p 0 = 0.5. Для однородного кроссовера не важна определяющая длина шаблона, и вообще в большинстве случаев шаблон разрушается. Такой агрессивный оператор плохо предназначен для отбора гиперплоскостей, однако его применение оправдано при малом размере популяции, т. к. он препятствует преждевременному схождению, свойственному таким популяциям.
Как мы уже отмечали выше, для пропорционального отбора свойственно уменьшение давления отбора с увеличением средней приспособленности популяции. Исправить этот недостаток можно с помощью масштабирования (scaling ): на каждом поколении нулем приспособленности можно считать наихудшую особь.
Ранковый отбор (rank selection ) отличается от пропорционального тем, что для каждой особи ее вероятность попасть в промежуточную популяцию пропорциональна ее порядковому номеру в отсортированной по возрастанию приспособленности популяции. Такой вид отбора не зависит от средней приспособленности популяции.
Турнирный отбор (tournament selection ) осуществляется следующим образом: из популяции случайным образом выбирается t особей, и лучшая из них помещается в промежуточную популяцию. Этот процесс повторяется N раз, пока промежуточная популяция не будет заполнена. Наиболее распространен вариант при t = 2. Турнирный отбор является более агрессивным, чем пропорциональный.
Отбор усечением (truncation selection ): популяция сортируется по приспособленности, затем берется заданная доля лучших, и из них случайным образом N раз выбирается особь для дальнейшего развития.
Выделяют два типа формирования нового поколения после получения множества детей в результате кроссовера и мутации:
Также для формирования нового поколения возможно использование принципа элитизма: в новое поколение обязательно включается заданное количество лучших особей предыдущего поколения (часто одна лучшая особь).
Использование второй стратегии и элитизма оказывается весьма полезным для эффективности ГА, т. к. не допускает потерю лучших решений. К примеру, если популяция сошлась в локальном максимуме, а мутация вывела одну из строк в область глобального, то при первой стратегии весьма вероятно, что эта особь в результате скрещивания будет потеряна, и решение задачи не будет получено. Если же используется элитизм, то полученное хорошее решение будет оставаться в популяции до тех пор, пока не будет найдено еще лучшее.
Классический ГА был рассмотрен выше. Напомним, что его создал Holland (1975).
Этот алгоритм был создан Уитли (D. Whitley). Genitor -подобные алгоритмы отличаются от классического ГА следующими тремя свойствами:
Утверждается (Syswerda, 1991), что в Genitor поиск гиперплоскостей происходит лучше, а сходимость быстрее, чем у классического ГА.
CHC расшифровывается как Cross generational elitist selection, Heterogenous recombination, Cataclysmic mutation . Этот алгоритм был создан Eshelman (1991) и характеризуется следующими параметрами:
Идея гибридных алгоритмов (hybrid algorithms ) заключается в сочетании генетического алгоритма с некоторым другим методом поиска, подходящим в данной задаче (зачастую это бывает hill-climbing ). На каждом поколении каждый полученный потомок оптимизируется этим методом, после чего производятся обычные для ГА действия. При использовании hill-climbing получается, что каждая особь достигает локального максимума, вблизи которого она находится, после чего подвергается отбору, скрещиванию и мутации.
Такой вид развития называется Ламарковой эволюцией, при которой особь способна обучаться, а затем полученные навыки записывать в собственный генотип, чтобы потом передать их потомкам. И хотя такой метод ухудшает способность алгоритма искать решение с помощью отбора гиперплоскостей, однако на практике гибридные алгоритмы оказываются очень удачными. Это связано с тем, что обычно велика вероятность того, что одна из особей попадет в область глобального максимума и после оптимизации окажется решением задачи.
Генетический алгоритм способен быстро найти во всей области поиска хорошие решения, но он может испытывать трудности в получении из них наилучших. Такой метод, как hill-climbing быстро достигает локального максимума, однако не может искать глобальный. Сочетание этих двух алгоритмов способно использовать преимущества обоих.
В природе все процессы происходят параллельно и независимо друг от друга. Генетические алгоритмы тоже можно организовать как несколько параллельно выполняющихся процессов, и это увеличит их производительность.
Сделаем из классического ГА параллельный. Для этого будем использовать турнирный отбор. Заведем N ⁄ 2 процессов (здесь и далее процесс подразумевается как некоторая машина, процессор, который может работать независимо). Каждый из них будет выбирать случайно из популяции 4 особи, проводить 2 турнира, и победителей скрещивать. Полученные дети будут записываться в новое поколение. Таким образом, за один цикл работы одного процесса будет сменяться целое поколение.
Изредка (например, каждые 5 поколений) процессы (или острова) будут обмениваться несколькими хорошими особями. Это называется миграция. Она позволяет островам обмениваться генетическим материалом.
Так как населенность островов обычно бывает невелика, подпопуляции будут склонны к преждевременной сходимости. Поэтому важно правильно установить частоту миграции. Чересчур частая миграция (или миграция слишком большого числа особей) приведет к смешению всех подпопуляций, и тогда островная модель будет несильно отличаться от обычного ГА. Если же миграция будет слишком редкой, то она не сможет предотвратить преждевременного схождения подпопуляций.
Генетические алгоритмы стохастичны, поэтому при разных его запусках популяция может сходиться к разным решениям (хотя все они в некоторой степени «хорошие»). Островная модель позволяет запустить алгоритм сразу несколько раз и пытаться совмещать «достижения» разных островов для получения в одной из подпопуляций наилучшего решения.
Cellular Genetic Algorithms — модель параллельных ГА. Пусть дано 2500 процессов, расположенных на сетке размером 50×50 ячеек, замкнутой, как показано на рисунке (левая сторона замыкается с правой, верхняя с нижней, получается тор).
Каждый процесс может взаимодействовать только с четырьмя своими соседями (сверху, снизу, слева, справа). В каждой ячейке находится ровно одна особь. Каждый процесс будет выбирать лучшую особь среди своих соседей, скрещивать с ней особь из своей ячейки и одного полученного ребенка помещать в свою ячейку вместо родителя.
По мере работы такого алгоритма возникают эффекты, похожие на островную модель. Сначала все особи имеют случайную приспособленность (на рисунке она определяется по цвету). Спустя несколько поколений образуются небольшие области похожих особей с близкой приспособленностью. По мере работы алгоритма эти области растут и конкурируют между собой.
До сих пор мы рассматривали ГА с фиксированными параметрами, такими как размер популяции, длина строки, вероятность кроссовера и мутации. Однако существуют генетические алгоритмы, в которых эти параметры могут изменяться и подстраиваться.
К примеру, пусть вероятность мутации для каждой особи будет отдельной. Можно добавить к строке особи подстроку, кодирующую эту вероятность. При вычислении приспособленности эта подстрока будет игнорироваться, но она будет подвергаться кроссоверу и мутации так же, как и остальная часть строки. Вероятность каждого бита данной особи быть инвертированным при мутации будет равна значению, кодируемому добавленной подстрокой. Инициализируются вероятности мутации случайным образом.
Thomas Back (1992) в своей работе заметил, что для унимодальных функций вариант с глобальной вероятностью мутации работает лучше, однако для многоэкстремальных функций использование адаптивной мутации дает лучшие результаты.
Укажем некоторые наблюдения, полученные исследователями генетических алгоритмов.
Как и для любого алгоритма оптимизации, для генетических алгоритмов есть некоторые типы функций, с которыми им работать сложнее, чем с другими. Обычно ГА тестируют именно на таких функциях. Ниже приведены свойства функций приспособленности, создающие сложность для ГА.
Для того, чтобы получить хорошие результаты, необходимо правильно выбрать размер популяции. На графике изображена зависимость количества вычислений функции приспособленности для нахождения максимума унимодальной функции от размера популяции. Видно, что существует оптимальный размер популяции. Действительно, если популяция мала, то при заданном ограничении количества вычислений функции приспособленности (а значит, фиксированном времени вычислений) она успеет создать большее количество поколений, но вероятнее всего преждевременно сойдется. Слишком большая популяция должна найти решение, но она может не успеть достичь этого момента, т. к. ей отведено малое количество поколений.
Для алгоритмов с кроссовером (т. е. без мутации) существуют оценки оптимального размера, а для ГА с мутацией (и без кроссовера) их пока нет. Однако эксперименты показывают, что для них оптимальный размер популяции тоже существует. В любом случае, он зависит от задачи.
Булат Яминов
Спасибо, полезная статья.
Хочу обратить ваше внимание на несколько моментов.
В разделе?Шаблоны? в столбик перечислены представители шаблона. В третьем и четвертом представителях следует на четвертой позиции писать цифру 0, вместо 1. В абзаце перед изображением куба говорится, что?шаблон определяет в нем гиперплоскость?, что верно лишь для некоторых шаблонов. Например, *11 уже не гиперплоскость (коразмерность не равна 1).
Надеемся, посетители этой страницы обратят внимание на ваши замечания.
И некоторые языковые опечатки. <... ...="">
Спасибо, указанные вами опечатки устранены.
В разделе?Примеры применения ГА?, к сожалению, 3 битых ссылки.
