Аннотация:
Отличительной особенностью эволюционных алгоритмов (ЭА) для решения задач оптимизации является имитация случайного процесса эволюционной адаптации биологической популяции к условиям окружающей среды. Особи соответствуют пробным точкам в пространстве решений задачи оптимизации, а приспособленность особей определяется значениями целевой функции. Построение новых пробных точек в ЭА осуществляется посредством операторов мутации и кроссинговера. При использовании кроссинговера алгоритмы принято называть генетическими. Множество бинарных векторов называется популяцией, а его элементы - особями. Первичные исследования новых ЭА традиционно проводятся для onemax весовой функции $f(x)=|x|$. Это одноэкстремальная задача. В генетическом алгоритме $(1+(\lambda,\lambda))$ из работы (Doerr,Doerr,Ebel, 2015) единственная родительская особь порождает $\lambda=\lambda(n)\to\infty $ потомков независимо друг от друга на случайном расстоянии Хэмминга $\ell$ от родителя, а затем одна из них с максимальным весом кроссинговером (каждый его бит сохраняется с вероятностью $\lambda^{-1}$, иначе берётся бит родителя) с родителем порождает $\lambda$ потомков независимо друг от друга, из которых выбирается наилучший. Если она не хуже родителя, то становится новым родителем и независимо от истории запускается новый цикл до попадания в оптимальный вектор, иначе родитель не изменяется и начинается новый цикл. Одна из проблем: найти оценки для среднего числа вычислений целевой функции. Традиционно описывается вероятность увеличения нормы родителя за один цикл и в их терминах производятся требуемые оценки. Мы предлагаем учесть величину приращения нормы Хемминга для нового родителя на основе предельных теорем, включая сходимость к распределению Гумбеля для максимума случайных величин. Это позволяет усилить некоторые имевшиеся ранее результаты.
|
