|
Оператор скрещивания
— это оператор, который определяет, как из
генотипов родителей формировать генотипы их потомства. Один из
интуитивно очевидных способов заключается в том, чтобы каждый бит
генотипа для потомка брать от случайного родителя. Такой способ
действительно используется и называется равномерным скрещиванием.
Однако в природе гены внутри одной хромосомы являются
сцепленными, поэтому случайным (и независимым) образом от
родителей берутся целые хромосомы. Также есть механизм, который
позволяет рекомбинировать и сцепленным генам. Это механизм
кроссинговера, или перекреста хромосом, при котором (гомологичные)
хромосомы обмениваются участками.
В ГА этот процесс моделируется так: хромосомы (а как отмечалось
выше, обычно в ГА все гены особи располагаются в единственной
хромосоме) делятся в некоторой случайной точке и обмениваются
этими участками (т. е. все, что идет до этой точки, берется от одного
родителя, а все, что после, — от другого). Это одноточечный
кроссинговер. В многоточечном кроссинговере таких участков обмена
больше. В ГА нередко используется такой оператор скрещивания, при
котором формируются генотипы сразу двух потомков, содержащие всю
генетическую информацию родителей. Варианты реализации оператора
скрещивания представлены ниже на рисунке.
А.Е. Кононюк Дискретно-непрерывная математика
48
Если бы в ГА геном представлялся в виде нескольких хромосом, то
моделировался бы одновременно случайный выбор целых хромосом и
рекомбинация генов внутри отдельных хромосом с помощью
кроссинговера.
4. В бытовом понимании мутации обычно представляются как
случайные искажения генов, и именно так (несмотря на то, что это
крайне упрощенное представление) они реализуются в ГА. Действие
оператора мутации сводится к случайной замене одного (иногда
нескольких) бита генотипа. Настроечный параметр алгоритма —
скорость мутации — определяет, как часто эта замена делается. Этот
параметр влияет на скорость сходимости и вероятность попадания в
локальный экстремум. Естественно, чем чаще мутации, тем медленнее
стабилизируется генофонд популяции, но тем меньше шансов, что
эволюция «застрянет» в неоптимальном решении.
А.Е. Кононюк Дискретно-непрерывная математика
49
5. Отбор особей в новую популяцию чаще всего осуществляется в
соответствии с одной из двух стратегий:
пропорционального отбора, при котором вероятность того, что
особь останется в следующей популяции, пропорциональна
значению ее фитнесс-функции;
элитного отбора, при котором из популяции отбираются
лучшие по значению фитнесс-функции особи, и только они
переходят в следующую популяцию.
Формирование новой популяции может осуществляться как на основе
потомков и родителей, так и на основе только потомков в зависимости
от конкретной реализации.
6. Основные критерии остановки алгоритма базируются либо на числе
сменившихся поколений (количестве выполненных итераций), либо на
некотором условии стабильности популяции. Заранее сложно
предсказать, сколько именно популяций потребуется для сходимости,
поэтому этот критерий используется обычно как вспомогательный.
Проверка стабильности популяции в общем виде, как правило, требует
значительных вычислений, поэтому чаще используется проверка того,
что наилучшее по популяции значение фитнесс-функции перестает
заметно изменяться от поколения к поколению.
Отличие эволюционных стратегий от генетических алгоритмов
заключается в том, что в первых не используются битовые
представления. Вместо этого все генетические операторы реализуются в
пространстве исходных объектов (или фенотипических признаков) с
учетом их структуры. Рассмотрим особенности реализации
генетических операторов в эволюционных стратегиях на примере
объектов, описаниями которых являются двухкомпонентные векторы
вида (x, y), т. е. задача заключается просто в поиске экстремума
функции от двух переменных f (x, y).
1.
Генерация начальной популяции может осуществляться путем
выбора случайных векторов из прямоугольной
области
, в которой
ожидается нахождение экстремума фитнесс-функции. В случае
Do'stlaringiz bilan baham: |
