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