Основные определения. Рассмотрим ряд терминов, которые широко используются в области эволюционных вычислений [2]

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

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

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

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

Генерация новых особей в процессе работы алгоритма происходит на основе моделирования процесса размножения. При этом порождающие особи называются родителями, а порожденные – потомками. Родительская пара, как правило, порождает пару потомков. Непосредственная генерация новых кодовых строк из двух выбранных происходит за счет работы оператора скрещивания, называемого также кроссинговером [< англ. crossing over – скрещивание хромосом]. Особь, возникшую в результате кроссинговера, иногда называют кроссовером [англ. crossover].

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

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

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

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

Критерием остановки работы генетического алгоритма может быть одно из трех событий:

· сформировано заданное пользователем число поколений;

· популяция достигла заданного пользователем качества;

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

Характеристики генетического алгоритма выбираются таким образом, чтобы с одной стороны обеспечить наилучшее решение, а с другой – минимизировать затраты времени на его поиск.

Дата добавления: 2014-12-29