Многое из того, что мы видим и наблюдаем, можно объяснить единой теорией – теорией эволюции, через наследственность, изменчивость и отбор. В 1859 году Чарльз Дарвин опубликовал свою знаменитую работу «Происхождение видов», где были провозглашены основные принципы эволюционной теории:
1) наследственность – потомки сохраняют свойства родителей;
2) изменчивость – потомки почти всегда различаются;
3) естественный отбор – выживают наиболее приспособленные.
В данном труде было показано, какие принципы приводят к эволюционному развитию. Однако человечество все еще не знало, как передается генетическая информация от родителей потомкам.
В 1944 году Эвери, Маклеод и Маккарти опубликовали результаты своих исследований, которые доказывали, что за наследственность отвечает ДНК. Однако на тот момент все еще было неизвестно, как она работает.
В 1953 году Уотсон и Крик рассказали о своем открытии в статье, в которой они первыми предложили модель двухцепочной спирали ДНК. После этого стали известны все необходимые компоненты для реализации эволюционной модели.
Первые публикации, которые можно отнести к генетическим алгоритмам, принадлежат Баричелли Н. А. Его работы «Symbiogenetic evolution processes realised by artificial methods» (1957 год) и «Numerical testing of evolution theories» (1962 год) были направлены на понимание читателем природного феномена наследственности.
В 1975 году Холланд Д. Х. публикует свою самую знаменитую работу «Adaptation in Natural and Artificial Systems». В ней он впервые ввел понятие «генетический алгоритм» и предложил схему классического генетического алгоритма (canonical GA). В дальнейшем «генетические алгоритмы» [1] стало очень широким понятием, и зачастую к ним относятся алгоритмы, сильно отличающиеся от классического генетического алгоритма.
Большинство алгоритмов оперируют лишь с одним решением, улучшая его. Этим генетический алгоритм отличается от других алгоритмов, ведь он оперирует совокупностью потенциальных решений [2].
Особь – это каждое потенциальное решение задачи. В зависимости от удобства кодирования информации, особь состоит из одной или нескольких хромосом. Хромосома – это упорядоченная последовательность генов (динамический массив). Ген – это атомарный элемент хромосомы. Популяция – совокупность особей.
Работа генетического алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнится какой-либо критерий остановки. Каждая итерация алгоритма называется поколением.
Рассмотрим подробнее этапы классического генетического алгоритма [3], а также различные видоизменения этих этапов, которые также имеют место.
На этапе создания начальной популяции происходит случайная генерация заданного количества особей в популяции. Классический генетический алгоритм имеет фиксированный размер популяции (в каждом поколении находится одинаковое количество особей), фиксированная разрядность генов (размеры хромосом каждой особи одинаковы). Нет необходимости наследовать данные пункты из классического алгоритма, главное, чтобы разработанная структура особи и размер популяции были эффективны.
На этапе вычисления полезности каждой особи каждая особь в популяции оценивается мерой ее полезности (приспособленности) согласно тому, насколько «хорошо» соответствующее ей решение задачи. Универсальность генетического алгоритма в том, что от конкретной задачи зависят только такие параметры, как функция полезности и кодирование структуры особей, а остальные этапы всех задач производятся одинаково. Использование функции полезности является эффективным решением, потому что она является аддитивным критерием, составленным из различных критериев оценки полезности.
Далее на каждой итерации следует этап проверки условия об остановке работы генетического алгоритма и выводе лучшей особи. Этим условием может быть количество пройденных поколений, сходимость решения, достижение особями какого-либо порога полезности и другие.
На этапе селекции особей в популяции происходит отбор пар особей, которые будут участвовать в процессе создания новых особей-потомков, называемом скрещиванием (кроссинговером). В классическом генетическом алгоритме вероятность особи участвовать в скрещивании пропорциональна ее полезности (приспособленности), т.е. работает пропорциональный отбор. При этом наиболее полезные особи могут быть выбраны несколько раз, а наименее полезные с большой вероятностью не будут выбраны вовсе.
Существует несколько способов реализации пропорционального отбора.
Первым способом пропорционального отбора является усредненный метод, который назначает каждой особи вероятность, равную отношению ее полезности к средней полезности популяции.
Целая часть этого отношения указывает, сколько раз нужно выбрать особь для участия в скрещивании, а дробная показывает ее вероятность быть выбранной еще раз.
Вторым способом пропорционального отбора является метод рулетки, который назначает каждой особи вероятность, равную отношению ее полезности к суммарной полезности популяции.
Особи, а точнее их вероятности, располагаются на колесе рулетки в виде секторов. Сумма вероятностей всех особей в популяции равна единице – площади всего колеса рулетки. Запуская рулетку, отбираем требуемое количество особей для участия в скрещивании.
Помимо пропорционального отбора существует еще два популярных метода отбора: турнирный отбора и отбор усечением [4].
Турнирный отбор может быть описан следующим образом: из популяции случайным образом выбирается некоторое число особей, лучшая из них будет участвовать в процессе скрещивания. Эта операция повторяется необходимое количество раз.
Отбор усечением использует отсортированную по полезности популяцию. Число особей для скрещивания выбирается в соответствии с порогом, лежащем в диапазоне [0, 1]. Порог определяет, какая доля особей, начиная с самой полезной (первой) будет принимать участие в отборе. Среди особей, прошедших порог, выбирается случайным образом необходимое число особей, которые будут участвовать в скрещивании.
На следующем этапе применяются генетические операторы: проходят процессы скрещивания, мутации и других пользовательских операций по видоизменению и добавлению особей.
Скрещивание – это процесс создания новых особей, унаследовавшие черты обоих родителей. В классическом генетическом алгоритме применяется одноточечное скрещивание, суть которого заключается в том, что для родительских хромосом случайным образом выбирается точка раздела, потомки получаются путем обмена отсеченными частями. Пара особей скрещивается с некоторой вероятностью, в результате чего получаются два потомка, которые переходят в новое поколение. Если скрещивания не происходит, то в новое поколение записывается сама пара. Процесс скрещивания может быть разнообразным – одноточечным, двухточечным, многоточечным. Главное, что должно сохраниться, это наследование черт родителей.
Мутация – это процесс изменения нескольких особей, необходимый для «выбивания» популяции из локального экстремума и способствующий защите от преждевременной сходимости. В классическом генетическом алгоритме применяется одноточечная мутация к новому поколению, суть которой заключается в том, что каждый ген каждой особи популяции с некоторой вероятностью изменяется на случайный. Эта вероятность обычно очень мала, менее 1%. Процесс мутации также может быть разнообразным, но суть его всегда одна – «выбивание» популяции из состояния застоя (локальный экстремум).
Последним этапом становится этап создания новой популяции. На нем происходит переход от текущей популяции к популяции потомков и уже она становится текущей (потомки занимают места своих родителей). Следуя классическому генетическому алгоритму, новое поколение формируется из потомков текущего поколения без «элитизма». Суть принципа «элитизма» заключается в том, что в новое поколение включаются лучшие родительские особи. Использование «элитизма» позволяет не потерять хорошее промежуточное решение, но, в то же время, из-за этого алгоритм может «застрять» в локальном экстремуме.
Библиографический список
- Гладков Л.А. Генетические алгоритмы / Л.А. Гладков, В.В. Курейчик, В.М. Курейчик – М.: Физматлит, 2010. – 317 с.
- Рутковская Д. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского / Д. Рутковская, М. Пилиньский, Л. Рутковский. – М.: Горячая линия – Телеком, 2006. – 452 с.
- Панченко Т.В. Генетические алгоритмы: Учебно-методическое пособие / под ред. Ю.Ю. Тарасевича. – Астрахань: АГУ, 2007. – 87 с.
- Курейчик В.М. Генетические алгоритмы и их применение. Таганрог: Изд-во ТРТУ, издание второе, дополненное, 2002. – 242 с.