В настоящее время наиболее известными и часто применяемыми на практике являются три способа создания исходной популяции (начального множества решений)[1,2].
Стратегия "одеяла" – формирование полной популяции, содержащей все возможные решения. Например, для $$n$$-разрядной хромосомы мы имеем всего $$2^n$$ вариантов решений, которые составляют полную популяцию.
Стратегия "дробовика" - генерация достаточно большого случайного подмножества решений.
Стратегия фокусировки - генерация подмножества решений, включающих разновидности одного решения.
Первый подход (стратегия "одеяла") практически не реализуем даже для задач средней размерности, вследствие больших вычислительных затрат. Заметим, что при этом подходе начальная популяция не может развиваться, т.к. в ней уже содержатся все возможные решения.
Третий способ используется тогда, когда есть предположение, что некоторое решение является вариацией известного значения. В этом случае время поиска оптимального решения существенно сокращается, т.к. алгоритм начинает работу в окрестности оптимума.
Чаще всего применяют второй способ. В этом случае в результате эволюции есть возможность перейти в другие подобласти поиска и каждая из них имеет сравнительно небольшое пространство поиска.
В целом эффективность ГА, качество решения и дальнейшая эволюция в значительной степени определяются структурой и качеством начальной популяции.
На практике часто применяют комбинацию второго и третьего способов. Сначала определяются особи с высокими значениями целевой функции, а затем случайно формируются начальные решения в этих подобластях.
При отборе конкурентоспособных особей используют целевую (fitness) функцию, как единственно доступный источник информации о качестве решения. Но различные методы отбора родителей по-разному используют эту информацию. Далее мы рассмотрим наиболее распространенные методы отбора родителей [1,2,3].
Данный вид отбора чаще всего используется на практике. При этом особи (решения) отображаются в отрезки линии (или сектора рулетки) таким образом, что их размер пропорционален значению целевой функции для данной особи. Это показано в следующем примере, представленном в табл.3.1
| Номер особи | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Значение ЦФ | 2,0 | 1,8 | 1,6 | 1,4 | 1,2 | 1,0 | 0,8 | 0,6 | 0,4 | 0,2 | 0,0 |
| Вероятность выбора | 0,18 | 0,16 | 0,15 | 0,13 | 0,11 | 0,09 | 0,07 | 0,06 | 0,03 | 0,02 | 0,0 |
Здесь на отрезке [0,1] для каждой особи строятся отрезки, длины которых пропорциональны вероятностям выбора особей, как это показано на рис.3.1
(рис 3.1) Вероятности выбора особей методом рулетки
Далее случайно генерируются числа из диапазона [0,1] и в промежуточную популяцию выбираются те особи, в чей "отрезок" попадают эти случайные числа. Таким образом, каждая попытка представляет собой случайное число из отрезка [0,1], в результате чего выбирается особь, соответствующая выбранному отрезку. В данном примере в результате пяти попыток были выбраны в промежуточную популяцию особи 1, 2, 3, 6 и 9.
Данный метод, несмотря на частое применение, имеет следующие недостатки:
Для устранения этих недостатков используют масштабирование оценок значений целевой функции относительно минимального значения в популяции (см. раздел 3.2.8) или метод ранжирования (раздел 3.2.2).
Очевидно, что проблема минимизации может быть сведена к задаче максимизации функции и обратно. Поэтому в некоторых реализациях ГА метод рулетки применяется и для поиска минимума функции, что в практических задачах встречается чаще (минимизация затрат, расстояния, погрешности и т.д.).
Для приведенного примера можно привести следующую гистограмму вероятностей выбора особей, представленную на рис.3.2. Отметим, что здесь высота "ступенек" различна, в отличие от следующего метода выбора, для которого гистограмма представлена на рис.3.3.
При этом методе особи популяции сортируются (упорядочиваются) согласно значениям целевой функции. Отметим, что здесь вероятность отбора для каждой особи зависит только от ее позиции (номера) в этом упорядоченном множестве особей, а не от самого значения целевой функции. Этот метод отбора более устойчив, чем предыдущий. В основном применяют линейное ранжирование, где вероятность отбора особи определяют в соответствии со следующим выражением:
$$P_s(a_i)=\frac{1}{N}\left(a-(a-b)\frac{i-1}{N-1}\right)$$Для приведенного примера гистограмма вероятностей выбора особей методом ранжирования, представлена на рис.3.3. Отметим, что здесь высота "ступенек" (разность значений вероятностей отбора- высот столбцов) одинакова, в отличие от предыдущего метода выбора. Иногда применяют нелинейное ранжирование. При этом вероятность отбора также определяется номером позиции в упорядоченном множестве особей, но вид функции может быть сложнее.
(рис 3.2) Ранжирование особей в операторе селекции методом асимметричного колеса рулетки
(рис 3.3) Сортировка особей в операторе селекции методом ранжирования с равным шагом
Достоинством метода ранжирования является возможность его применения при поиске как максимумов, так и минимумов функций. Этот метод также не требует масштабирования для предотвращения преждевременной сходимости в отличие от метода рулетки.
Здесь вероятность выбора особи определяется выражением:
$$P_s(a_i)=\begin{cases}\frac{1}{\mu},\text{при $1\le i\le\mu$}\\0,\text{при $\mu\le i\le N$}\end{cases}$$где $$\mu\le N$$ параметр метода.
Производится среди особей, которые находятся в некоторой ограниченной среде, где определено отношение соседства. Ранее, фактически, в качестве соседей каждой особи рассматривалась вся популяция. При этом в качестве соседей подразумевается множество партнеров для выполнения операции скрещивания.
Соседство можно определить по-разному. Далее рассмотрим типичные отношения соседства, используемые при локальном отборе.
(рис 3.4) Линейное соседствоНа рис.3.4 представлен пример линейного соседства. На практике рассматривают полную окрестность (на рис.3.4 вверху показана полная окрестность выделенного элемента с расстоянием $$d=2$$) и "полуокрестность" (в правом нижнем углу рисунка показана "полуокрестность" с расстоянием $$d=1$$).
(рис 3.5) Соседство на четырехсвязной решетке
(рис 3.6) Соседство на восьмисвязной решеткеОднако, из-за перекрытия соседних областей, распространение новых вариантов решений все же возможно. Мощность множества соседей определяет скорость распространения информации между особями популяции, способствуя либо быстрому распространению новых решений, либо сохранению имеющегося генофонда в популяции. Часто при решении задачи требуется высокая изменчивость, которая поможет избежать преждевременной сходимости в районе локального оптимума. Обычно локальный отбор в малом окружении дает лучшие результаты, чем в большем окружении.
В малых и средних популяциях $$(N<100)$$ для локального отбора рекомендуется двумерная структура типа "полузвезда" с расстоянием $$d=1$$.При большом размере популяции $$(N>100)$$ лучше использовать большие расстояния $$d>1$$ и двумерные структуры с соседством типа "звезда".
Предыдущие методы отбора в какой то степени заимствованы у (или имеют аналогию с) эволюции естественных популяций. Этот метод не имеет аналогов в естественной эволюции и обычно используется для больших популяций $$(N>100)$$. При этом сначала отбираемые особи упорядочиваются согласно их значениям целевой функции. Затем в качестве родителей выбираются только лучшие особи. Далее, с равной вероятностью, среди них случайным образом выбирают пары, которые производят потомков.
При этом методе используется параметр – порог отсечения $$T$$(иногда используется термин интенсивность отбора), показывающий долю (часть популяции), которая отбирается в качестве родителей. Обычно $$10\% \le T\le 50\%$$.
В этом случае все особи популяции разбиваются на подгруппы размера $$m$$ с последующим выбором в каждой из них особи с лучшим значением фитнесс-функции. Параметром этой процедуры является размер тура $$m$$, который принимает значения из диапазона $$2\le m < N$$. Используются два способа выбора - детерминированный и случайный. При детерминированном способе выбор выполняется с вероятностью, равной 1, в то время как при случайном методе выбор осуществляется с вероятностью меньше 1. Чаще всего популяция разбивается на подгруппы по 2-3 особи в каждой ($$m=2,3$$).Рис.3.7 иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей.Турнирный метод может быть использован как при максимизации, так и при минимизации функции. Кроме этого, он легко распространяется на задачи многокритериальной оптимизации. Экспериментальные исследования показывают, что часто данный метод эффективней метода рулетки.
(рис 3.7) Схема турнирной селекции
В этом случае при отборе особей используется подход, который используется в известном методе оптимизации "моделирование отжига", где при управлении процессом поиска применяется "искусственная температура". Для этого вводится действительная переменная $$T$$, которая, начиная с некоторого достаточно большого значения, постепенно уменьшается (по определенному закону) и изменяет вероятность отбора особей. Вероятность отбора особи, имеющей значение фитнесс-функции $$f(i)$$, определяется следующим образом
$$P_s(a_i)=\frac{1}{N}\left(\frac{e^{f(a_i)/T}}{\overline{e^{f(a)/T}}}\right)$$где $$\overline{e^{f(a)/T}}$$ представляет среднее значение $$e^{f(a_i)/T}$$ по текущей популяции. Отметим, что с уменьшением температуры разность значений $$P_s(a_i)$$ между худшими и лучшими особями увеличивается. Это позволяет на заключительном этапе сузить поиск в наиболее перспективной области пространства поиска, сохраняя при этом достаточную степень разнообразия в популяции. Показано, что для некоторых задач этот метод отбора дает лучшие результаты, чем стандартный пропорциональный отбор типа "рулетка"[3].
До сих пор мы, в основном, рассматривали методы отбора родителей в промежуточную популяцию. Далее из этой популяции необходимо выбрать пары особей для выполнения операции скрещивания. Основными методами выбора пар особей являются следующие.
Случайный выбор (панмиксия) родительской пары, при котором оба родителя случайным образом выбираются из всей промежуточной популяции. Следует отметить, что при этом любая особь может входить в несколько пар. Этот метод является универсальным для решения различных задач, но достаточно критичен к численности популяции, поскольку его эффективность снижается с ростом мощности популяции $$N$$.
Селективный выбор. Здесь родителями могут стать только те особи, значение целевой функции которых не меньше среднего значения по популяции при равной вероятности этих кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма, но неприемлем для мультимодальных задач (имеющих несколько экстремумов), для которых этот метод, как правило, быстро сходится к одному из решений. Это может привести к преждевременной сходимости к локальному экстремуму.
Часто используется также два следующих подхода: инбридинг и аутбридинг. В них формирование пары происходит на основе близкого или дальнего родства соответственно. Под родством обычно понимается расстояние между особями популяции в пространстве параметров. В связи с этим различают генотипный и фенотипный инбридинг и аутбридинг.
Инбридинг – здесь первый член пары выбирается случайно, а вторым является максимально близкая к нему особь.
Аутбридинг формирует пары из максимально далеких особей.
Комбинация этих походов используется при решении многоэкстремальных задач.
Кроме рассмотренных выше явных методов отбора часто применяются также и неявные методы, которые, как правило, сводятся к масштабированию фитнесс-функции [1,4]. Масштабирование фитнесс-функции производится обычно в следующих случаях: 1) для предотвращения преждевременной сходимости ГА; 2) на последнем этапе выполнения ГА, когда в популяции сохраняется значительная неоднородность, однако среднее значение фитнесс-функции ненамного отличается от максимального значения. Масштабирование позволяет избежать ситуаций, в которых средние и лучшие особи дают практически одинаковое количество потомков, что считается нежелательным явлением. Преждевременная сходимость соответствует ситуации, когда в популяции доминируют лучшие, но еще не оптимальные особи. Это особенно характерно для ГА, использующих при отборе родителей метод рулетки. При этом часто возникают ситуации, когда через несколько поколений популяция состоит в основном из копий лучшей особи. Поскольку в качестве исходной популяции часто используется небольшая случайная выборка из пространства возможных решений, то маловероятно, что именно эта лучшая особь соответствует оптимальному решению. Масштабирование фитнесс-функции часто позволяет избежать доминирования неоптимальной особи, и, тем самым, предохраняет ГА от преждевременной сходимости.
Масштабирование выполняется с помощью трех основных преобразований фитнесс-функций: 1) линейное, 2) сигма-отсечение и 3) степенное.
Линейное масштабирование сводится к линейному преобразованию фитнесс-функции следующего вида
$$F'=a\times F+b$$где $$a$$ и $$b$$- константы, которые обычно подбираются так, чтобы среднее значение фитнесс-функции после масштабирования было равно ее среднему значению до масштабирования, а максимальное значение фитнесс-функции после преобразования было кратным ее среднему значению. Здесь $$F$$ и $$F'$$ соответствуют фитнесс-функции до и после преобразования. При этом коэффициент кратности обычно выбирается в пределах от 1,2 до 2 и необходимо следить, чтобы новая фитнесс-функция $$F'$$ не принимала отрицательных значений.
Сигма отсечение основано на следующем преобразовании фитнесс-функции
$$F'=F+(\bar F-c\cdot \sigma)$$где $$\bar F$$ означает среднее значение фитнесс-функции по популяции, $$c$$– малое натуральное число (обычно от 1 до 5), а $$\sigma$$- стандартное отклонение по популяции. Если при этом значения $$F'$$ получаются отрицательными, то они полагаются равными нулю.
При степенном масштабировании используется следующее преобразование
$$F'=F^k$$где $$k$$– число, обычно близкое к 3. В общем случае $$k$$ подбирается эвристическим путем с учетом специфики задачи.
(рис 3.8) Одноточечный кроссинговер
Разработаны различные обобщения классического одноточечного кроссинговера, которые наиболее полно представлены в [2,4].При двухточечном кроссинговере потомки наследуют фрагменты хромосом родителей между двумя случайно выбранными точками скрещивания, как это, например, показано на рис. 3.9
(рис 3.9) Пример двухточечного кроссинговера
Графически это пример удобно представить в виде, показанном на рис. 3.10. Многоточечный кроссинговер является обобщением предыдущих операторов на случай большего числа точек скрещивания. Например, трехточечный кроссинговер представлен на рис. 3.11.
Многоточечный кроссинговер с большим четным количеством точек скрещивания графически удобно представить для хромосом в виде "колец", что показано на рис. 3.12 [1,4]. При этом хромосома рассматривается как замкнутое кольцо, а точки скрещивания выбираются с равной вероятностью по всей его окружности. Например, на рис. 3.10 обмен производится фрагментами между 4-й и 6-й точек скрещивания родительских особей, что также иллюстрируется на рис. 3.11.
(рис 3.10) Пример двухточечного кроссинговера
(рис 3.11) Пример трехточечного кроссинговера
(рис 3.12) Пример четырехточечного кроссинговера
Кроссинговер с нечетным количеством точек скрещивания можно представить таким же способом, если добавить дополнительную точку скрещивания в нулевой позиции.
Этот вид скрещивания радикально отличается от предыдущих видов. Здесь каждый ген потомка создается путем копирования соответствующего гена из первого или второго родителя, то есть каждая позиция потенциально является точкой кроссинговера.
Для этого случайным образом генерируется двоичная маска кроссинговера той же длины (с тем же числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 – второму. На рис. 3.13 показана схема выполнения этого типа кроссинговера на конкретном примере. Каждый бит потомка копируется из 1-го или 2-го родителя в соответствии со значением этого бита маски.
(рис 3.13) Однородный кроссинговер
Таким образом, потомок содержит смесь генов из каждого родителя.
В этом виде скрещивания точки кроссинговера могут выбираться только там, где значения генов у родителей различны.
При этом хромосома представляется действительными (вещественными) числами.
Этот вид скрещивания определен над векторами, компонентами которых являются вещественные числа. Рассмотрим это на примере двух особей, соответствующие вектора которых имеют три целых значения. Для каждой переменной (позиции) значение переменной выбирается из первого или второго родителя с равной вероятностью. Пример выполнения этого оператора показан на рис. 3.14. Здесь образцы (маски) показывают принадлежность данной компоненты потомка определенному родителю. Отметим, что этот тип рекомбинации применим к значениям любого типа.
Этот метод применим только для особей, представленных только вещественными значениями. Здесь значения потомков строятся в окрестности или между значениями родителей.
В случае промежуточной рекомбинации потомки $$O_1$$ и $$O_2$$ формируется следующим образом:
$$O_1=P_1+\alpha_1\cdot(P_2-P_1),O_2=P_1+a_2\cdot(P_2-P_1)$$
(рис 3.14) Дискретная рекомбинация
где $$P_1,P_2$$– вещественные значения, представляющие первого и второго родителя;
$$O_i$$– вещественное значение, представляющее потомка;
$$\alpha_i$$- масштабирующий множитель, который выбирается случайным образом из отрезка $$[-d, 1+d]$$.
При обычной промежуточной рекомбинации $$d=1$$ и $$\alpha_i\in[0,1]$$. Для обобщенной промежуточной рекомбинации $$d>0$$, обычно полагают $$d=0,25$$. Значение каждой переменной, в том числе и для векторов, формируется по приведенному выражению. Отметим, что здесь используются чисто арифметические операции (сложение и умножение). Заметим, что при $$d=0$$ потомки принадлежат отрезку $$[P_1,P_2]$$. Эти операторы совершенно не похожи на классический кроссинговер. Фактически, этот оператор заимствован из другого направления эволюционных вычислений - "эволюционных стратегий". На рис. 3.15 показан пример выполнения этого оператора для тех же данных, которые использовались в предыдущем примере.
(рис 3.15) Промежуточная рекомбинация
Для примера подробно приведем выполнение оператора для 1-ой компоненты
$$O_1=P_1+\alpha_1\cdot(P_2-P_1)=12+0,5\cdot (123-12)=67,5$$Этот вид оператора аналогичен предыдущему, за исключением того, что значение масштабирующего множителя $$\alpha$$ одинаково для всех переменных (компонент) векторов. Пример выполнения этого оператора представлен на рис.3.16
(рис 3.16) Линейная рекомбинация
Этот вид оператора уже рассматривался в простом ГА. Здесь для каждой особи случайно выбирается позиция и с малой вероятностью (от $$Р_m=0,01$$ до $$Р_m=0,001$$) выполняется инвертирование значения переменной в выбранной позиции. Пример выполнения этого оператора представлен на рис.3.17.
(рис 3.17) Классическая мутация
Иногда используется следующий оператор инверсии, фактически являющийся разновидностью мутации. При этом случайным образом выбираются две позиции в особи и далее производится обмен значениями генов между ними. Пример выполнения этого оператора представлен на рис.3.18.
(рис 3.18) Инверсия
Мутация над вещественными потомками выполняется путем сложения особи с небольшим случайным значением, которое называется шагом мутации. Выбор размера шага мутации зависит от рассматриваемой проблемы, и шаг в общем случае может изменяться в процессе решения задачи. Маленький шаг дает большую точность, но ведет к большим временным затратам. Мутация с постоянным шагом и постоянной вероятностью называется однородной.
Оператор мутации над вещественным числом выполняется следующим образом
$$V_m=V\pm r\cdot\Delta$$где $$V,V_m$$– значения вещественной переменной до и после мутации;
$$r=0,5$$(диапазон изменения переменной) и $$\Delta$$ - случайное число от 0 до 1
Часто для повышения эффективности поиска вероятность мутации и шаг изменяются в процессе решения задачи.
Рассмотрим далее способы изменения вероятности мутации. Мутация с равной вероятностью может привести как к увеличению, так и к уменьшению значения целевой функции. На этапе сходимости ГА к оптимуму целесообразно уменьшать вероятность случайной мутации. Обычно на начальном этапе $$P_m=0,05\dots 0,1$$, а на конечном этапе вероятность мутации уменьшают. Для реализации этой процедуры иногда используют метод моделирования отжига (simulation annealing), который дает следующий закон изменения вероятности мутации:
$$P_m=P_m^0\cdot e^{-\frac{1}{t}}$$где $$t$$– номер поколения.
Здесь изменяется шаг мутации. Вначале шаг мутации имеет достаточно большое значение, которое далее постепенно уменьшается. Рассмотрим этот тип оператора для векторного случая
$$\begin{array}{cl}S_v^t=\langle V_1,V_2,\dots ,V_k,\dots V_m\rangle\\V_k\in[l_k,U_k]\end{array}$$В результате выполнения мутации получаем следующий вектор (особь популяции)
$$\begin{array}{cl}S_v^{t+1}=\langle V_1,V_2,\dots ,V'_k,\dots V_m\rangle\\k\in[1,\dots n]\end{array}$$где компонента вектора вычисляется следуюшим образом
$$V'_k=\begin{cases}V_k+\Delta(t,U_k-V_k)\text{при случ. число $=0$}\\V_k-\Delta(t,V_k-l_k)\text{при случ. число $=1$}\end{cases}$$где $$\Delta(t,y)\in[0,y]$$ и $$\Delta(t,y)$$ определяет шаг мутации, который с увеличением номера поколения $$t$$ уменьшается:
$$\begin{array}{cl}\Delta(t,y)\to 0\\t\to\infty\end{array}$$Один из вариантов реализации функции, определяющей шаг $$\Delta(t,y)$$,следующий:
$$\Delta(t,y)=y\cdot\left(1-r^{\left(1-\frac{t}{T}\right)\cdot b}\right)$$где $$r\in[1,\dots n]$$($$r$$-случайное число) и $$T$$ – максимальное число поколений; $$b=2$$– параметр, определяющий степень неоднородности. На рис.3.19 показан для наглядности график изменения шага мутации, который в пределе стремится к 0.
(рис 3.19) Уменьшение шага мутации
Необходимой компонентой является устранение плохих решений, полученных в процессе формирования новой популяции.
Промежуточную популяцию (репродукционную группу) составляют все особи $$t$$-го поколения и новые особи, полученные в результате скрещивания и мутации. Численность этой популяции можно определить следующим образом
$$R^{t+1}=r^t+r_{cr}^t+r_m^t$$где: $$r^t$$- число особей предыдущей популяции;
$$r_{cr}^t$$– численность особей, полученных путем скрещивания;
$$r_m^t$$– число "мутантов".
Обычно в
В простейшем случае с помощью скрещивания и мутации генерируются столько потомков, сколько было родителей. Далее родители устраняются, а потомки формируют следующее поколение $$P(t+1)$$. При этом каждая особь живет лишь одно поколение. Такая схема часто используется в простом ГА. Однако при этом очевидно не исключено, что некоторые очень хорошие решения могут быть заменены худшими, и лучшее решение будет потеряно.
В ней потомков генерируется меньше, чем было родителей. Далее вновь построенные потомки заменяют худших родителей согласно значениям фитнесс-функции. Для этой схемы возможна преждевременная сходимость к локальным экстремумам.
При таком подходе потомков также генерируется меньше, чем было родителей, далее случайным образом удаляется необходимое число родителей, которые заменяются новыми потомками.
Здесь потомков генерируется больше, чем необходимо для замены. Далее заменяют заданное число родителей только лучшими потомками согласно значениям фитнесс-функции
Здесь родители и потомки выступают на равных правах - они помещаются в одну репродукционную группу. В ней все особи этой группы ранжируются и в следующее поколение включаются только лучшие $$N$$ особей. Иногда применяется следующая модификация этого метода. Сначала вычисляется среднее значение ЦФ группы и в следующее поколение включаются те особи, у которых значение ЦФ больше среднего значения группы.
В общем случае к репродукционной группе $$R^{t+1}$$ может быть применен любой метод отбора родителей, которые были рассмотрены в разделе 3.2.
При локальном отборе особи выбираются из ограниченного окружения множества соседей. Замена особей потомками выполняется по такой же схеме. Таким образом сохраняется локальность информации. При этом используются те же структуры и отношения соседства, что и в разделе 3.2.4.
Родитель особи определяются первым родителем из локального окружения (множества соседей). Для выбора удаляемых родителей и отбора потомков для замены применяются следующие схемы:
До сих пор мы рассматривали стационарные синхронные эволюционные алгоритмы, где мощность популяции поддерживается постоянной и переход к следующему поколению "синхронизирован". Здесь обрабатываются все потомки предыдущего поколения, а затем следует переход на следующую итерацию (поколение).
Иногда на практике применяется и асинхронный эволюционный алгоритм, где нет явного разбиения эволюции на поколения, а процесс развития реализуется "по событию" в виде непрерывного потока событий отбора, кроссинговера, мутации и т.п. Здесь вновь порожденные потомки сразу замещают (в некотором смысле худшие) особи (не дожидаясь остальных родительских пар своего поколения). Ниже представлен один из возможных вариантов асинхронного алгоритма реализации ГА с применением турнирного отбора родителей.
Следует отметить, что такой метод, как правило, проще в реализации (особенно аппаратной) и имеет некоторые преимущества.
Данная модификация предназначена для решения задач, которые не требуют популяций с большим числом особей и длинных хромосом. Такой подход оправдан в том случае, когда решение (не обязательно глобальный оптимум) необходимо найти как можно быстрее. В этом случае необходимо уменьшить трудоемкость, связанную с большим количеством итераций, ценой возможно ухудшения качества решения. Такой подход, например, реализован в программе FlexTool [4] следующим генетическим микроалгоритмом.
Отметим, что в
Мощность популяции $$N$$ является важнейшим параметром ГА, который критичен во многих приложениях. Если $$N$$ мало, то ГА работает быстро, но при этом увеличивается опасность преждевременной сходимости к локальному экстремуму. Большая мощность популяции увеличивает генофонд, но процесс поиска замедляется.
На разных этапах работы ГА оптимальное значение $$N$$ может быть различным. На начальном этапе $$N$$ должно быть большим, а на заключительном $$N$$ можно уменьшить.
При одном из подходов в ГА с изменяемым размером популяции каждой особи после ее рождения на текущем этапе оценки целевой функции (ЦФ) присваивается "время жизни" (life time) $$L_f$$– параметр, зависящий от ЦФ особи. Таким образом, каждая особь живет определенное число поколений и умирает по окончании срока жизни. Очевидно, значение этого параметра влияет на размер популяции. В этом случае ГА можно реализовать, например, следующим образом [5].
Нестационарный_ГА
{
t =0;
Инициализация;
Оценка ЦФ p(t);
While (условие окончания не выполнено)
{
t=t+1;
Увеличение возраста каждой особи на 1;
Рекомбинация p(t):
Мутация p(t):
Оценка ЦФ p(t):
Определение срока жизни особей;
Удаление из p(t) всех особей с возрастом больше срока жизни;
}
}
Здесь в текущем поколении $$t$$ алгоритм обрабатывает популяцию $$P(t)$$. В процессе рекомбинации и мутации генерируется промежуточная популяция, состоящая из потомков, и ее размер пропорционален числу исходной $$r_{cr}^t+r_m^t=r\cdot P$$.
Тогда $$|P(t+1)|=|P(t)|+r_a^t-D(t)$$– число особей в новой популяции.
Срок жизни для каждой особи определяется после оценки ЦФ (по формулам, приведенным ниже) и является окончательным, то есть постоянным в процессе эволюции. В таком случае особь живет определенное число поколений, а затем умирает. Срок жизни определяет число поколений, в течении которых особь держится в популяции. Очевидно, что в этом случае, чем больше срок жизни, тем больше потомков может дать особь, так как на каждом этапе родители для рекомбинации выбираются случайно с равной вероятностью. При этом подходе важнейшую роль играет метод определения срока жизни особи.
Очевидно, постоянное значение $$L\ge 2$$ для каждой особи ведет к экспоненциальному росту размеров популяции. Поэтому для каждой особи срок жизни вычисляется индивидуально в зависимости от значения ее ЦФ.
Наиболее часто используются следующие три способа определения срока жизни.
Для их определения введем следующие обозначения:
$$L_f$$:
$$L_f=\min\left\{L_{min} +\eta\cdot\frac{f[i]}{\bar f},L_{max}\right\}$$где $$\eta=\frac12\cdot(L_{max}-L_{min})$$ (используется для всех формул).
Очевидно, что первый метод соответствует пропорциональному отбору отбора родителей - "рулетке". К минимальному сроку жизни добавляется премиальный срок, который пропорционален значению ЦФ для данной особи. Однако эта стратегия имеет серьезный недостаток – она не учитывает информацию о некоторых объективных характеристиках особи, такой, например, как отношение $$\frac{f[i]}{f_\max}$$ (или $$\frac{f[i]}{f_\min}$$) целевой функции по популяции.
Эту проблему решает вторая (линейная) стратегия, где срок жизни определяется исходя из значения ЦФ данной особи относительно максимального значения в популяции $$f_\max$$. Но этот метод тоже имеет свои недостатки - если в популяции много особей имеют значение ЦФ стремящееся к максимальному ($$(f[i]\to f_\max)$$) значению, то такой подход приведет к чрезмерному увеличению размера популяции.
В третьей стратегии (билинейной) предпринята попытка найти компромисс между первыми двумя методами. В ней учитываются разница между сроками жизни, близкими к лучшей особи, используя информацию о среднем значении популяции. Однако в тоже время принимается во внимание минимальное и максимальное значение по популяции.
Для мультимодальных функций, которые имеют много экстремумов, часто представляет интерес найти не одно, а несколько экстремальных значений. С помощью стандартного ГА это трудно сделать, поскольку в процессе эволюции, как правило, благодаря "генетическому дрейфу" особи концентрируются в окрестности одного экстремума. Поэтому для поиска экстремумов мультимодальных функций были разработаны соответствующие методы.
Простейший из них основан на многократном запуске ГА на различных подмножествах пространства поиска решений. Показано [6], что, если все экстремумы имеют примерно одинаковую небольшую вероятность поиска (быть найденными), то число независимых запусков ГА должно быть
$$p\sum_{i=1}^p \frac{1}{i}\approx p(\gamma+\log p)$$где $$p$$– число экстремумов и $$\gamma\approx 0,577$$ - константа Эйлера. К сожалению, в большинстве реальных задач экстремумы не являются равновероятными и поэтому число запусков должно быть больше приведенной оценки. Возможна также параллельная реализация этого итеративного метода.
$$s_f(i)=\frac{f(i)}{m(i)}$$где $$f(i)$$– значение исходной фитнесс-функции и $$m(i)$$ называется счетчиком
где $$d_{ij}$$- евклидово расстояние между двумя особями $$i$$ и $$j$$. Разделяющая функция $$sh(d_{ij})$$ должна обладать следующими свойствами:
$$0\le sh(d_{ij})\le 1$$ для каждого $$d_{ij}$$,
$$s(0)=1,$$$$\lim_{d_{ij}\to \infty} s(d_{ij})=0$$Одной из применяемых на практике функций, для которой эти условия выполняются, является следующая
$$sh(d_{ij})=\begin{cases}1-\left(\frac{d_{ij}}{\sigma_s}\right)^\alpha,\text{если $d_{ij}<\sigma_s$}\\0,\text{в противном случае.}\end{cases}$$Здесь $$\alpha$$ и $$\sigma_s$$ являются константами. Наибольшие трудности в этом методе вызывает выбор значения $$\sigma_s$$, который требует априорного знания числа экстремумов функции, что, как правило, заранее неизвестно.
Имеются различные модификации этого метода. Например, расстояние $$d_{ij}$$ между особями иногда определяются не на уровне фенотипа (евклидово расстояние), а на уровне генотипа, где используется расстояние Хэмминга между двоичными кодами хромосом.
Одним из важнейших преимуществ ГА является то, что они прекрасно сочетаются с другими методами оптимизации, поэтому разработано множество гибридных ГА. Пожалуй самым распространенным подходом является включение локальной оптимизации наряду с генетическими операторами в классическую блок-схему простого ГА. В этом случае локальная оптимизация применяется к каждому полученному потомку, чтобы "сдвинуть" его в сторону локального оптимума перед внедрением его в новую популяцию. При этом ГА используется для глобального расширения пространства поиска, в то время как эвристические методы применяются для "эксплуатации" ближайшего окружения особей. Вследствие того, что ГА и эвристические методы имеют взаимно дополняющие свойства, гибридные ГА часто превосходят по характеристикам входящие в него компоненты.
Другой распространенной формой гибридизации является внедрение адаптации параметров ГА. Характеристики ГА характеризуются балансом между расширением и эксплуатацией пространства поиска решений, который в значительной степени определяется значениями основных параметров ГА, таких как мощность популяции, максимальное число поколений, вероятностей кроссинговера и мутации. Выбор значений этих параметров является одной из важнейших задач при разработке ГА.
Комбинирование ГА и эвристик локального поиска исследовалось многими авторами и предложено множество методов гибридизации, но наиболее распространенными является два: 1)
При втором подходе изменяется только значение фитнесс-функции особи, а генотип остается неизменным. Отметим, что классический ГА разработан Холландом на основе моделирования эволюции Дарвина. Но еще в XIX веке в теорию Дарвина были предложены Ламарком дополнения, где изменения особи в течение ее жизни вследствие воздействия окружающей среды передавались потомкам. Эта теория позволяет организмам накопленный опыт и знания в течение жизни передавать потомкам. Далеко не все биологи разделяют эту точку зрения, но этот эффект имеет место, например, в эволюции общества. Использование
(рис 3.20) Общая структура гибридного ГА
Эксперименты на некоторых тестовых задачах показали [8], что стратегия с Балдвин-эффектом чаще сходится к глобальному оптимуму, в то время как
В ранних работах первого направления в ГА использовались операторы Ламарка [9]. Некоторые авторы [10] ввели вероятность Ламарка для мутации с тем, чтобы получить более контролируемый оператор мутации и операторы локального поиска.
Пусть $$P(t)$$ и $$C(t)$$ обозначают множество родителей и потомков текущей популяции $$t$$. Ниже представлен в виде псевдокода укрупненный алгоритм
Эти идеи получили развитие в
Поскольку ГА навеяны идеей эволюции, естественно ввести элементы адаптации не только в процесс поиска решений задачи, но и в настройку значений параметров ГА для данной проблемы.
(рис 3.21) Пример применения локального поиска в ГА
В последние годы проведено достаточно много исследований в этом направлении, когда в основном рассматриваются два вида адаптации:
Разница между ними в том, что первая модифицирует некоторые компоненты ГА, такие как вид представления особи, кроссинговер, мутация и отбор. Естесственно, для удачного выбора или модификации компонентов необходимо понимать суть решаемой задачи. Во втором виде адаптации предлагается способ настройки значений параметров и конфигурации ГА в процессе решения задачи. Следуя [15, 16] последний вид адаптации можно разбить на следующие классы:
Из этих видов в последние десять лет исследовались различные способы адаптации параметров, таких как вероятности кроссинговера и мутации, мощность популяции, которые играют решающую роль в балансе расширения и эксплуатации пространства поиска решений. Ключевым вопросом является выбор значений параметров для эффективного решения данной проблемы. Обычно в простом ГА используются фиксированные значения параметров, которые находятся методом проб и ошибок. Поскольку сам ГА является динамическим и адаптивным процессом, то фиксированные значения параметров противоречат самому духу эволюции. Поэтому возникла естественная идея попробовать изменять значения параметров в процессе поиска решения. Это можно сделать различными способами:
В работах [15,17] представлен обзор используемых на текущий момент методов адаптации в ГА, в котором выделены три основные категории.
Отметим, что изменение мощности популяции между двумя соседними поколениями прежде всего влияет на функционирование оператора отбора. Пусть $$n_t$$ и $$n_{t+1}$$ обозначают мощность популяции текущего и последующего поколения соответственно. Отбор особей можно рассматривать как повторяющийся процесс $$n_{t+1}$$ операторов отбора с вероятностью $$p_j$$ для $$j$$-ой особи. Для большинства методов отбора, таких, как например, пропорциональный или турнирный отбор с замещением, вероятность выбора $$p_j$$ остается неизменной при выполнении $$n_{t+1}$$ операторов. Тогда ожидаемое количество копий $$j$$-ой особи можно выразить как $$c(j,t+1)=p_j n_{t+1} c(j,t)$$, где $$c(j,t)$$– число копий $$j$$-ой особи в поколении $$t$$. Ожидаемое количество копий $$j$$-ой особи прямо пропорционально мощности популяции следующего поколения. Таким образом, долю в популяции особей, связанных с $$j$$-ой особью после отбора можно выразить следующим выражением:
$$c(j,t+1)=\frac{c(j,t+1)}{n_{t+1}}=\frac{p_j n_{t+1}c(j,t)}{n_{t+1}}=p_j c(j,t)$$которое не зависит от размера следующей популяции на том основании, что изменение мощности популяции несущественно влияет на значение вероятности $$p_j$$. Отметим, что ГА, где мощность популяции уменьшается с ростом поколения, имеет большую начальную и меньшую конечную популяцию. Это повышает эффективность ГА, поскольку большая начальная популяция покрывает большее подпространство поиска, а в конце процесса, когда найдена "зона интереса", для сходимости к оптимуму достаточно и небольшого количества особей в популяции
Основываясь на этих предположениях, был предложен так называемый пилообразный ГА [20], где изменение мощности популяции комбинируется с реинициализацией, которая выполняется для улучшения характеристик ГА. При этом среднее значение мощности популяции $$\bar n$$ по периоду соответствует постоянной популяции ГА с той же вычислительной сложностью. Кроме этого, закон изменения мощности популяции характеризуется амплитудой $$D$$ и периодом $$T$$. В этой нотации размер популяции изменяется следующим образом:
$$n(t)=int\left(\bar n+D-\frac{2D}{T-1}\left(t-T\cdot int\left(\frac{t-1}{T}\right)-1\right)\right)$$На рис.3.22 представлен пример пилообразного изменения мощности популяции.
(рис 3.22) Пилообразное изменение количества особей в популяции
В
Баланс между этими характеристиками ГА определяется значениями вероятности $$P_c$$ и $$P_m$$ и типом используемых генетических операторов (прежде всего кроссинговера). Увеличение значений $$P_c$$ и $$P_m$$ ведет к расширению пространства поиска.
Обычно используют следующие значения вероятностей - $$P_c\in[0,5;1]$$ и $$P_c\in[0,001;0,01]$$. Далее мы рассмотрим другой подход [7], который использует различные значения $$P_c$$ и $$P_m$$ в зависимости от значения ЦФ текущих особей. Для мультимодальных функций существует серьезная проблема преждевременной сходимости к локальным экстремумам.
Чтобы изменять $$P_c$$ и $$P_m$$ адаптивно, с целью предотвращения преждевременной сходимости к локальному экстремуму, надо научиться идентифицировать ситуации, когда ГА сходится к оптимуму. Рассмотрим этот подход на примере поиска максимума для мультимодальной функции (которая имеет несколько экстремумов), которая показана на рис. 3.23
(рис 3.23) Мультимодальная функция
Один из возможных способов обнаружения сходимости – наблюдение разности среднего и максимального значения целевой функции по популяции $$(f_{\max} -\overline f)$$. Обычно эта разность меньше для популяции, которая сходится к оптимуму, чем для популяции, "разбросанной" по пространству поиска решений. Будем использовать разность $$(f_{\max} -\overline f)$$ в качестве основного признака сходимости к оптимуму, причем не обязательно глобальному.
Поскольку вероятности $$P_c$$ и $$P_m$$ должны увеличиваться при преждевременной сходимости к локальному оптимуму (чтобы "выпрыгнуть из ловушки" локального экстремума), то значение $$(f_{\max} -\overline f)$$ должны изменяться обратно пропорционально разности $$(f_{\max} -\overline f)$$:
$$P_c=\frac{k_1}{f_{\max} -\overline f}\qquad P_m=\frac{k_2}{f_{\max} -\overline f}$$Здесь $$P_c$$ и $$P_m$$ не зависят от значений ЦФ для конкретной особи, а определяются для всей популяции, но для разных популяций различных поколений они уже будут разными.
Отметим, что как для хороших решений с высокими значениями целевой функции, так и для плохих, используются одни и те же величины $$P_c$$ и $$P_m$$. Это не рационально, так как когда популяция сходится к глобальному или локальному оптимуму, то $$P_c$$ и $$P_m$$ увеличиваются, что ведет к разрушению близких к оптимуму решений. В результате популяция может не сойтись к глобальному оптимуму. Таким образом, мы избежали ловушки локального экстремума ценой снижения характеристик ГА по поиску глобальных экстремумов.
Чтобы решить эту проблему, нужно сохранить хорошие решения текущей популяции. Это можно сделать, полагая низкие значения вероятности $$P_c$$ и $$P_m$$ для особей с высоким значением ЦФ и высокие значения $$P_c$$ и $$P_m$$ для плохих особей с низкими значениями ЦФ. Тогда лучшие решения будут способствовать сходимости, а худшие – предотвращать ГА от "ловушек" локальных экстремумов. Таким образом, значение $$P_c$$ и $$P_m$$ должны зависеть не только от разности $$(f_{\max} -\overline f)$$, но еще и от значений ЦФ конкретных особей. Чем ближе значение функции к максимальному, тем меньше должно быть значение $$P_c$$ и $$P_m$$:
$$P_c=k_1\cdot\frac{f_{\max} - f'}{f_{\max} -\overline f},\qquad k_1\le 1\\ P_m=k_2\cdot\frac{f_{\max} - f}{f_{\max} -\overline f},\qquad k_2\le 1$$где $$f'$$– лучшее значение целевой функции у двух родителей.
Положим $$P_c=P_m=0$$ для решений, имеющих максимальное значение ЦФ и
$$P_c=k_1,\qquad f'=\bar f\\P_m=k_2,\qquad f'=\bar f$$Отметим, что для плохих решений $$(f,f'<\bar f)$$ значения вероятностей $$P_c$$ и $$P_m$$ в соответствии с формулой (3.23) могут быть больше 1, что некорректно. Поэтому для плохих решений примем:
$$P_c=k_3,\qquad f'\le\bar f\\P_m=k_4,\qquad f'\le\bar f$$В итоге получим:
$$P_c=\begin{cases}k_1\cdot\frac{f_{\max}-f'}{f_{\max}-\bar f}, f'>\bar f\\k_3,\text{иначе}\end{cases}\\P_m=\begin{cases}k_2\cdot\frac{f_{\max}-f'}{f_{\max}-\bar f}, f>\bar f\\k_4,\text{иначе}\end{cases}\\k_1=k_3=1\\k_2=k_4=0,5$$Лучшие решения при этом сохраняются и переходят в следующее поколение. Этот факт может привести к чрезмерному росту популяции, что чревато преждевременной сходимостью. Поэтому иногда дополнительно вводится одна (default) мутация (с вероятностью $$P_d=0,005$$) для всех особей популяции.
Существуют и более строгие
Эвристическая мутация является разновидностью эвристического поиска. Для этого часто используется LS-техника, которая позволяет генерировать новых потомков из отобранных родителей. Следует отметить, что этот оператор может сдвигать потомков в сторону локального оптимума. Число потомков зависит от вероятности мутации $$P_m$$. Фактически значение вероятности мутации определяет вес процесса исследования новых областей в пространстве поиска.
Значения вероятностей иммиграции и кроссинговера определяют вес процесса эксплуатации в пространстве поиска решений. В основной схеме используются два
где $$parSize$$ и $$offSize$$ – означают соответственно значения мощности популяций родителей и потомков, удовлетворяющие заданным ограничениям. Регулирование $$P_M$$ определяется с использованием значений $$\Delta f_{avg}(t-i),i=1,2\dots \mu$$ и регулирование $$P_C$$ и $$P_I$$ выполняется на основе значений коэффициента корреляции особей текущей популяции следующим образом:
$$P_M=regulation1(\Delta f_{avg}(t-i),i=1,2\dots,\mu\\P_C=regulation2(\Delta f_{avg}(t-i),i=1,2\dots,\mu\\P_I=1-(P_M+P_C)$$где процедуры regulation 1 и regulation 2 представлены ниже в виде псевдокода.
Функции принадлежности для $$P_C$$ и $$P_M$$ показаны на рис.3.24 и рис.3.25 соответственно.
(рис 3.24) Функция принадлежности PM.
(рис 3.25) Функция принадлежности PC.
Кроме этого, значения $$\Delta f,\mu_M,\mu_C$$ определяются следующим образом:
$$\Delta f=\sum 2^{t-i}\cdot\lambda(\Delta f_{avg}(t-i)),t\ge\mu\\\\\mu_M=\frac{0,8-0,2}{2^{\mu}-2\alpha},0\le\alpha\le\frac{2^{\mu}}{4}\\\\\mu_C=\frac{0,8(1-P_M)-0,1}{2^{\mu}-2\alpha},0\le\alpha\le\frac{2^{\mu}}{4}\\\\\lambda(x)=\begin{cases}1, if\ x\ge 0\\\\0,\text{otherwise}\end{cases}$$Пусть $$P(t)$$ и $$C(t)$$ обозначают популяции родителей и потомков соответственно, тогда укрупненный алгоритм
Критерий остановки вычислений – повторение лучшего результата заданное количество раз или достижение популяцией определенного возраста (например, 100 эпох).
| № вв. | Название | Оптимум | Вид функции | График функции |
|---|---|---|---|---|
| 1 | De Jong's function 1 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_1(x)=\sum_{i=1}^n x_i^2,\qquad -5,12\le x_i\le 5,12$$ |  |
| 2 | Axis parallel hyper-ellipsoid function | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_{la}(x)=\sum_{i=1}^n i\cdot x_i^2,\qquad -5,12\le x_i\le 5,12$$ |  |
| 3 | Rotated hyper-ellipsoid function | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_{1b}(x)=\sum_{i=1}^n\left(\sum_{j=1}^i x_j\right)^2,\qquad -65,536\le x_i\le 65,536$$ |  |
| 4 | Moved axis parallel hyper-ellipsoid function | global minimum $$f(x)=0; x_i=5*i,\\ I=1:n.$$ | $$f_{1c}(x)=\sum_{i=1}^n 5i\cdot x_i^2,\qquad -5,12\le x_i\le 5,12$$ |  |
| 5 | Rosenbrock's valley (De Jong's function 2) | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_2(x)=\sum_{i=1}^{n-1} 100\cdot (x_{i+1}-x_i^2)^2+(1-x_i)^2),\qquad -2,048\le x_i\le 2,048$$ |  |
| 6 | Rastrigin's function 6 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_6(x)=10\cdot n+\sum_{i=1}^n(x_i^2-10\cdot \cos(2\cdot\pi\cdot x_i)),\qquad -5,12\le x_i\le 5,12$$ |  |
| 7 | Schwefel's function 7 | global minimum $$f(x)=n\cdot 418.9829; x_i=420.9687,\\i=1:n.$$ | $$f_7(x)=\sum_{i=1}^n -x_i\cdot \sin(\sqrt{|x_i|}),\qquad -500\le x_i\le 500$$ |  |
| 8 | Griewangk's function 8 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_8(x)=\sum_{i=1}^n \frac{x_i^2}{4000}-\prod_{i=1}^n\cos\left(\frac{x_i}{\sqrt{i}\right)+1,\qquad -600\le x_i\le 600$$ |  |
| 9 | Sum of different power function 9 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_9(x)=\sum_{i=1}^n|x_i|^{(i+1)},\qquad -1\le x_i\le 1$$ |  |
| 10 | Ackley's Path function 10 | global minimum $$f(x)=0; x_i_=0,\\ I=1:n.$$ | $$f_{10}(x)=-a\cdot e^{-b\cdot \sqrt{\frac{\sum_{i=1}^n x_i^2}{n}}}-e^{\frac{\sum_{i=1}^n cos(c\cdot x_i)}{n}}+a+e^1;\qquad -1\le x_i\le 1\\a=20;b=0,2;c=2\cdot \pi$$ |  |
| 11 | Langermann's function 11 | global minimum $$f(x)=-1.4 (for\ m=5); x_i=???,\\i=1:n.$$ | $$f_{11}(x)=-\sum_{i=1}^m c_i\cdot(e^{-\frac{\|x-A(i)\|^2}{\pi}}\cdot\cos\left(\pi\cdot\|\bar x-A(i)\|^2)),\qquad 0\le x_i\le 10,\ 2\le m\le10$$ |  |
| 12 | Michalewicz's function 12 | global minimum $$f(x)=-4.687 (n=5); x_i=???,\\i=1:n.\\f(x)=-9.66 (n=10); x_i=???,\\i=1:n.$$ | $$f_{12}(x)=-\sum_{i=1}^n \sin(x_i)\cdot\left(\sin\left(\frac{i\cdot x_i^2}{\pi} \right ) \right)^{2\cdot m},\qquad 0\le x_i\le \pi,\ m=10$$ |  |
| 13 | Branins's rcos function | global minimum $$f(x_1,x_2)=0.397887;(x_1,x_2)=(-pi,12.275),\\ (\pi,2.275), (9.42478,2.475).$$ | $$f_{Bran}(x_1,x_2)=a\cdot(x_2-b\cdot x_1^2+c\cdotx_1-d)^2+e\cdot(1-f)\cdot(x_1)+e,\\ -5\le x_1\le 10,\ 0\le x_2\le \15\\a=1,b=\frac{5,1}{4\cdot \pi^2},c=\frac{5}{\pi},d=6,e=10,f=\frac{1}{8\cdot\pi}$$ |  |
| 14 | Easom's function | global minimum $$f(x_1,x_2)=-1;\\(x_1,x_2)=(\pi,\pi).$$ | $$f_{Easo}(x_1,x_2)=-\cos(x_1)\cdot\cos(x_2)\cdot e^{-((x_1-\pi)^2+(x_2-\pi)^2)},\qquad -100\le x_i\le 100$$ |  |
| 15 | Goldstein-Price's function | global minimum $$f(x_1,x_2)=3;\\(x_1,x_2)=(0,-1).$$ | $$f_{Gold}(x_1,x_2)=(1+(x_1+x_2+1)^2\cdot(19-14x_1+3x_1^2-14x_2+6x_1x_2+3x_2^2))\\\cdot(30+(2x_1-3x_2)^2\cdot(18-32x_1+12x_1^2+48x_2-36x_1x_2+27x_2^2)),\\ -2\le x_i\le 2$$ |  |
| 16 | Six-hump camel back function | global minimum $$f(x_1,x_2)=-1.0316;\\(x_1,x_2)=(-0.0898,0.7126), (0.0898,-0.7126).$$ | $$f_{Sixh}(x_1,x_2)=(4-2.1\cdot x_1^2+x_1^{4/3})\cdot x_1^2+x1\cdot x_2+(-4+4\cdot x_2^2)\cdot x_2^2;\\ -3\le x_1\le 3,-2\le x_2\le2$$ |  |
В настоящее время наиболее известными и часто применяемыми на практике являются три способа создания исходной популяции (начального множества решений)[1,2].
Стратегия "одеяла" – формирование полной популяции, содержащей все возможные решения. Например, для $$n$$-разрядной хромосомы мы имеем всего $$2^n$$ вариантов решений, которые составляют полную популяцию.
Стратегия "дробовика" - генерация достаточно большого случайного подмножества решений.
Стратегия фокусировки - генерация подмножества решений, включающих разновидности одного решения.
Первый подход (стратегия "одеяла") практически не реализуем даже для задач средней размерности, вследствие больших вычислительных затрат. Заметим, что при этом подходе начальная популяция не может развиваться, т.к. в ней уже содержатся все возможные решения.
Третий способ используется тогда, когда есть предположение, что некоторое решение является вариацией известного значения. В этом случае время поиска оптимального решения существенно сокращается, т.к. алгоритм начинает работу в окрестности оптимума.
Чаще всего применяют второй способ. В этом случае в результате эволюции есть возможность перейти в другие подобласти поиска и каждая из них имеет сравнительно небольшое пространство поиска.
В целом эффективность ГА, качество решения и дальнейшая эволюция в значительной степени определяются структурой и качеством начальной популяции.
На практике часто применяют комбинацию второго и третьего способов. Сначала определяются особи с высокими значениями целевой функции, а затем случайно формируются начальные решения в этих подобластях.
При отборе конкурентоспособных особей используют целевую (fitness) функцию, как единственно доступный источник информации о качестве решения. Но различные методы отбора родителей по-разному используют эту информацию. Далее мы рассмотрим наиболее распространенные методы отбора родителей [1,2,3].
Данный вид отбора чаще всего используется на практике. При этом особи (решения) отображаются в отрезки линии (или сектора рулетки) таким образом, что их размер пропорционален значению целевой функции для данной особи. Это показано в следующем примере, представленном в табл.3.1
| Номер особи | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Значение ЦФ | 2,0 | 1,8 | 1,6 | 1,4 | 1,2 | 1,0 | 0,8 | 0,6 | 0,4 | 0,2 | 0,0 |
| Вероятность выбора | 0,18 | 0,16 | 0,15 | 0,13 | 0,11 | 0,09 | 0,07 | 0,06 | 0,03 | 0,02 | 0,0 |
Здесь на отрезке [0,1] для каждой особи строятся отрезки, длины которых пропорциональны вероятностям выбора особей, как это показано на рис.3.1
(рис 3.1) Вероятности выбора особей методом рулетки
Далее случайно генерируются числа из диапазона [0,1] и в промежуточную популяцию выбираются те особи, в чей "отрезок" попадают эти случайные числа. Таким образом, каждая попытка представляет собой случайное число из отрезка [0,1], в результате чего выбирается особь, соответствующая выбранному отрезку. В данном примере в результате пяти попыток были выбраны в промежуточную популяцию особи 1, 2, 3, 6 и 9.
Данный метод, несмотря на частое применение, имеет следующие недостатки:
Для устранения этих недостатков используют масштабирование оценок значений целевой функции относительно минимального значения в популяции (см. раздел 3.2.8) или метод ранжирования (раздел 3.2.2).
Очевидно, что проблема минимизации может быть сведена к задаче максимизации функции и обратно. Поэтому в некоторых реализациях ГА метод рулетки применяется и для поиска минимума функции, что в практических задачах встречается чаще (минимизация затрат, расстояния, погрешности и т.д.).
Для приведенного примера можно привести следующую гистограмму вероятностей выбора особей, представленную на рис.3.2. Отметим, что здесь высота "ступенек" различна, в отличие от следующего метода выбора, для которого гистограмма представлена на рис.3.3.
При этом методе особи популяции сортируются (упорядочиваются) согласно значениям целевой функции. Отметим, что здесь вероятность отбора для каждой особи зависит только от ее позиции (номера) в этом упорядоченном множестве особей, а не от самого значения целевой функции. Этот метод отбора более устойчив, чем предыдущий. В основном применяют линейное ранжирование, где вероятность отбора особи определяют в соответствии со следующим выражением:
$$P_s(a_i)=\frac{1}{N}\left(a-(a-b)\frac{i-1}{N-1}\right)$$Для приведенного примера гистограмма вероятностей выбора особей методом ранжирования, представлена на рис.3.3. Отметим, что здесь высота "ступенек" (разность значений вероятностей отбора- высот столбцов) одинакова, в отличие от предыдущего метода выбора. Иногда применяют нелинейное ранжирование. При этом вероятность отбора также определяется номером позиции в упорядоченном множестве особей, но вид функции может быть сложнее.
(рис 3.2) Ранжирование особей в операторе селекции методом асимметричного колеса рулетки
(рис 3.3) Сортировка особей в операторе селекции методом ранжирования с равным шагом
Достоинством метода ранжирования является возможность его применения при поиске как максимумов, так и минимумов функций. Этот метод также не требует масштабирования для предотвращения преждевременной сходимости в отличие от метода рулетки.
Здесь вероятность выбора особи определяется выражением:
$$P_s(a_i)=\begin{cases}\frac{1}{\mu},\text{при $1\le i\le\mu$}\\0,\text{при $\mu\le i\le N$}\end{cases}$$где $$\mu\le N$$ параметр метода.
Производится среди особей, которые находятся в некоторой ограниченной среде, где определено отношение соседства. Ранее, фактически, в качестве соседей каждой особи рассматривалась вся популяция. При этом в качестве соседей подразумевается множество партнеров для выполнения операции скрещивания.
Соседство можно определить по-разному. Далее рассмотрим типичные отношения соседства, используемые при локальном отборе.
(рис 3.4) Линейное соседствоНа рис.3.4 представлен пример линейного соседства. На практике рассматривают полную окрестность (на рис.3.4 вверху показана полная окрестность выделенного элемента с расстоянием $$d=2$$) и "полуокрестность" (в правом нижнем углу рисунка показана "полуокрестность" с расстоянием $$d=1$$).
(рис 3.5) Соседство на четырехсвязной решетке(рис 3.6) Соседство на восьмисвязной решеткеОднако, из-за перекрытия соседних областей, распространение новых вариантов решений все же возможно. Мощность множества соседей определяет скорость распространения информации между особями популяции, способствуя либо быстрому распространению новых решений, либо сохранению имеющегося генофонда в популяции. Часто при решении задачи требуется высокая изменчивость, которая поможет избежать преждевременной сходимости в районе локального оптимума. Обычно локальный отбор в малом окружении дает лучшие результаты, чем в большем окружении.
В малых и средних популяциях $$(N<100)$$ для локального отбора рекомендуется двумерная структура типа "полузвезда" с расстоянием $$d=1$$.При большом размере популяции $$(N>100)$$ лучше использовать большие расстояния $$d>1$$ и двумерные структуры с соседством типа "звезда".
Предыдущие методы отбора в какой то степени заимствованы у (или имеют аналогию с) эволюции естественных популяций. Этот метод не имеет аналогов в естественной эволюции и обычно используется для больших популяций $$(N>100)$$. При этом сначала отбираемые особи упорядочиваются согласно их значениям целевой функции. Затем в качестве родителей выбираются только лучшие особи. Далее, с равной вероятностью, среди них случайным образом выбирают пары, которые производят потомков.
При этом методе используется параметр – порог отсечения $$T$$(иногда используется термин интенсивность отбора), показывающий долю (часть популяции), которая отбирается в качестве родителей. Обычно $$10\% \le T\le 50\%$$.
В этом случае все особи популяции разбиваются на подгруппы размера $$m$$ с последующим выбором в каждой из них особи с лучшим значением фитнесс-функции. Параметром этой процедуры является размер тура $$m$$, который принимает значения из диапазона $$2\le m < N$$. Используются два способа выбора - детерминированный и случайный. При детерминированном способе выбор выполняется с вероятностью, равной 1, в то время как при случайном методе выбор осуществляется с вероятностью меньше 1. Чаще всего популяция разбивается на подгруппы по 2-3 особи в каждой ($$m=2,3$$).Рис.3.7 иллюстрирует метод турнирной селекции для подгрупп, состоящих из двух особей.Турнирный метод может быть использован как при максимизации, так и при минимизации функции. Кроме этого, он легко распространяется на задачи многокритериальной оптимизации. Экспериментальные исследования показывают, что часто данный метод эффективней метода рулетки.
(рис 3.7) Схема турнирной селекции
В этом случае при отборе особей используется подход, который используется в известном методе оптимизации "моделирование отжига", где при управлении процессом поиска применяется "искусственная температура". Для этого вводится действительная переменная $$T$$, которая, начиная с некоторого достаточно большого значения, постепенно уменьшается (по определенному закону) и изменяет вероятность отбора особей. Вероятность отбора особи, имеющей значение фитнесс-функции $$f(i)$$, определяется следующим образом
$$P_s(a_i)=\frac{1}{N}\left(\frac{e^{f(a_i)/T}}{\overline{e^{f(a)/T}}}\right)$$где $$\overline{e^{f(a)/T}}$$ представляет среднее значение $$e^{f(a_i)/T}$$ по текущей популяции. Отметим, что с уменьшением температуры разность значений $$P_s(a_i)$$ между худшими и лучшими особями увеличивается. Это позволяет на заключительном этапе сузить поиск в наиболее перспективной области пространства поиска, сохраняя при этом достаточную степень разнообразия в популяции. Показано, что для некоторых задач этот метод отбора дает лучшие результаты, чем стандартный пропорциональный отбор типа "рулетка"[3].
До сих пор мы, в основном, рассматривали методы отбора родителей в промежуточную популяцию. Далее из этой популяции необходимо выбрать пары особей для выполнения операции скрещивания. Основными методами выбора пар особей являются следующие.
Случайный выбор (панмиксия) родительской пары, при котором оба родителя случайным образом выбираются из всей промежуточной популяции. Следует отметить, что при этом любая особь может входить в несколько пар. Этот метод является универсальным для решения различных задач, но достаточно критичен к численности популяции, поскольку его эффективность снижается с ростом мощности популяции $$N$$.
Селективный выбор. Здесь родителями могут стать только те особи, значение целевой функции которых не меньше среднего значения по популяции при равной вероятности этих кандидатов составить брачную пару. Такой подход обеспечивает более быструю сходимость алгоритма, но неприемлем для мультимодальных задач (имеющих несколько экстремумов), для которых этот метод, как правило, быстро сходится к одному из решений. Это может привести к преждевременной сходимости к локальному экстремуму.
Часто используется также два следующих подхода: инбридинг и аутбридинг. В них формирование пары происходит на основе близкого или дальнего родства соответственно. Под родством обычно понимается расстояние между особями популяции в пространстве параметров. В связи с этим различают генотипный и фенотипный инбридинг и аутбридинг.
Инбридинг – здесь первый член пары выбирается случайно, а вторым является максимально близкая к нему особь.
Аутбридинг формирует пары из максимально далеких особей.
Комбинация этих походов используется при решении многоэкстремальных задач.
Кроме рассмотренных выше явных методов отбора часто применяются также и неявные методы, которые, как правило, сводятся к масштабированию фитнесс-функции [1,4]. Масштабирование фитнесс-функции производится обычно в следующих случаях: 1) для предотвращения преждевременной сходимости ГА; 2) на последнем этапе выполнения ГА, когда в популяции сохраняется значительная неоднородность, однако среднее значение фитнесс-функции ненамного отличается от максимального значения. Масштабирование позволяет избежать ситуаций, в которых средние и лучшие особи дают практически одинаковое количество потомков, что считается нежелательным явлением. Преждевременная сходимость соответствует ситуации, когда в популяции доминируют лучшие, но еще не оптимальные особи. Это особенно характерно для ГА, использующих при отборе родителей метод рулетки. При этом часто возникают ситуации, когда через несколько поколений популяция состоит в основном из копий лучшей особи. Поскольку в качестве исходной популяции часто используется небольшая случайная выборка из пространства возможных решений, то маловероятно, что именно эта лучшая особь соответствует оптимальному решению. Масштабирование фитнесс-функции часто позволяет избежать доминирования неоптимальной особи, и, тем самым, предохраняет ГА от преждевременной сходимости.
Масштабирование выполняется с помощью трех основных преобразований фитнесс-функций: 1) линейное, 2) сигма-отсечение и 3) степенное.
Линейное масштабирование сводится к линейному преобразованию фитнесс-функции следующего вида
$$F'=a\times F+b$$где $$a$$ и $$b$$- константы, которые обычно подбираются так, чтобы среднее значение фитнесс-функции после масштабирования было равно ее среднему значению до масштабирования, а максимальное значение фитнесс-функции после преобразования было кратным ее среднему значению. Здесь $$F$$ и $$F'$$ соответствуют фитнесс-функции до и после преобразования. При этом коэффициент кратности обычно выбирается в пределах от 1,2 до 2 и необходимо следить, чтобы новая фитнесс-функция $$F'$$ не принимала отрицательных значений.
Сигма отсечение основано на следующем преобразовании фитнесс-функции
$$F'=F+(\bar F-c\cdot \sigma)$$где $$\bar F$$ означает среднее значение фитнесс-функции по популяции, $$c$$– малое натуральное число (обычно от 1 до 5), а $$\sigma$$- стандартное отклонение по популяции. Если при этом значения $$F'$$ получаются отрицательными, то они полагаются равными нулю.
При степенном масштабировании используется следующее преобразование
$$F'=F^k$$где $$k$$– число, обычно близкое к 3. В общем случае $$k$$ подбирается эвристическим путем с учетом специфики задачи.
(рис 3.8) Одноточечный кроссинговер
Разработаны различные обобщения классического одноточечного кроссинговера, которые наиболее полно представлены в [2,4].При двухточечном кроссинговере потомки наследуют фрагменты хромосом родителей между двумя случайно выбранными точками скрещивания, как это, например, показано на рис. 3.9
(рис 3.9) Пример двухточечного кроссинговера
Графически это пример удобно представить в виде, показанном на рис. 3.10. Многоточечный кроссинговер является обобщением предыдущих операторов на случай большего числа точек скрещивания. Например, трехточечный кроссинговер представлен на рис. 3.11.
Многоточечный кроссинговер с большим четным количеством точек скрещивания графически удобно представить для хромосом в виде "колец", что показано на рис. 3.12 [1,4]. При этом хромосома рассматривается как замкнутое кольцо, а точки скрещивания выбираются с равной вероятностью по всей его окружности. Например, на рис. 3.10 обмен производится фрагментами между 4-й и 6-й точек скрещивания родительских особей, что также иллюстрируется на рис. 3.11.
(рис 3.10) Пример двухточечного кроссинговера
(рис 3.11) Пример трехточечного кроссинговера
(рис 3.12) Пример четырехточечного кроссинговера
Кроссинговер с нечетным количеством точек скрещивания можно представить таким же способом, если добавить дополнительную точку скрещивания в нулевой позиции.
Этот вид скрещивания радикально отличается от предыдущих видов. Здесь каждый ген потомка создается путем копирования соответствующего гена из первого или второго родителя, то есть каждая позиция потенциально является точкой кроссинговера.
Для этого случайным образом генерируется двоичная маска кроссинговера той же длины (с тем же числом бит), что у хромосом родителей. Четность бита маски показывает родителя, из которого копируется ген потомка. Для определенности допустим, что 1 соответствует первому родителю, а 0 – второму. На рис. 3.13 показана схема выполнения этого типа кроссинговера на конкретном примере. Каждый бит потомка копируется из 1-го или 2-го родителя в соответствии со значением этого бита маски.
(рис 3.13) Однородный кроссинговер
Таким образом, потомок содержит смесь генов из каждого родителя.
В этом виде скрещивания точки кроссинговера могут выбираться только там, где значения генов у родителей различны.
При этом хромосома представляется действительными (вещественными) числами.
Этот вид скрещивания определен над векторами, компонентами которых являются вещественные числа. Рассмотрим это на примере двух особей, соответствующие вектора которых имеют три целых значения. Для каждой переменной (позиции) значение переменной выбирается из первого или второго родителя с равной вероятностью. Пример выполнения этого оператора показан на рис. 3.14. Здесь образцы (маски) показывают принадлежность данной компоненты потомка определенному родителю. Отметим, что этот тип рекомбинации применим к значениям любого типа.
Этот метод применим только для особей, представленных только вещественными значениями. Здесь значения потомков строятся в окрестности или между значениями родителей.
В случае промежуточной рекомбинации потомки $$O_1$$ и $$O_2$$ формируется следующим образом:
$$O_1=P_1+\alpha_1\cdot(P_2-P_1),O_2=P_1+a_2\cdot(P_2-P_1)$$(рис 3.14) Дискретная рекомбинация
где $$P_1,P_2$$– вещественные значения, представляющие первого и второго родителя;
$$O_i$$– вещественное значение, представляющее потомка;
$$\alpha_i$$- масштабирующий множитель, который выбирается случайным образом из отрезка $$[-d, 1+d]$$.
При обычной промежуточной рекомбинации $$d=1$$ и $$\alpha_i\in[0,1]$$. Для обобщенной промежуточной рекомбинации $$d>0$$, обычно полагают $$d=0,25$$. Значение каждой переменной, в том числе и для векторов, формируется по приведенному выражению. Отметим, что здесь используются чисто арифметические операции (сложение и умножение). Заметим, что при $$d=0$$ потомки принадлежат отрезку $$[P_1,P_2]$$. Эти операторы совершенно не похожи на классический кроссинговер. Фактически, этот оператор заимствован из другого направления эволюционных вычислений - "эволюционных стратегий". На рис. 3.15 показан пример выполнения этого оператора для тех же данных, которые использовались в предыдущем примере.
(рис 3.15) Промежуточная рекомбинация
Для примера подробно приведем выполнение оператора для 1-ой компоненты
$$O_1=P_1+\alpha_1\cdot(P_2-P_1)=12+0,5\cdot (123-12)=67,5$$Этот вид оператора аналогичен предыдущему, за исключением того, что значение масштабирующего множителя $$\alpha$$ одинаково для всех переменных (компонент) векторов. Пример выполнения этого оператора представлен на рис.3.16
(рис 3.16) Линейная рекомбинация
Этот вид оператора уже рассматривался в простом ГА. Здесь для каждой особи случайно выбирается позиция и с малой вероятностью (от $$Р_m=0,01$$ до $$Р_m=0,001$$) выполняется инвертирование значения переменной в выбранной позиции. Пример выполнения этого оператора представлен на рис.3.17.
(рис 3.17) Классическая мутация
Иногда используется следующий оператор инверсии, фактически являющийся разновидностью мутации. При этом случайным образом выбираются две позиции в особи и далее производится обмен значениями генов между ними. Пример выполнения этого оператора представлен на рис.3.18.
(рис 3.18) Инверсия
Мутация над вещественными потомками выполняется путем сложения особи с небольшим случайным значением, которое называется шагом мутации. Выбор размера шага мутации зависит от рассматриваемой проблемы, и шаг в общем случае может изменяться в процессе решения задачи. Маленький шаг дает большую точность, но ведет к большим временным затратам. Мутация с постоянным шагом и постоянной вероятностью называется однородной.
Оператор мутации над вещественным числом выполняется следующим образом
$$V_m=V\pm r\cdot\Delta$$где $$V,V_m$$– значения вещественной переменной до и после мутации;
$$r=0,5$$(диапазон изменения переменной) и $$\Delta$$ - случайное число от 0 до 1
Часто для повышения эффективности поиска вероятность мутации и шаг изменяются в процессе решения задачи.
Рассмотрим далее способы изменения вероятности мутации. Мутация с равной вероятностью может привести как к увеличению, так и к уменьшению значения целевой функции. На этапе сходимости ГА к оптимуму целесообразно уменьшать вероятность случайной мутации. Обычно на начальном этапе $$P_m=0,05\dots 0,1$$, а на конечном этапе вероятность мутации уменьшают. Для реализации этой процедуры иногда используют метод моделирования отжига (simulation annealing), который дает следующий закон изменения вероятности мутации:
$$P_m=P_m^0\cdot e^{-\frac{1}{t}}$$где $$t$$– номер поколения.
Здесь изменяется шаг мутации. Вначале шаг мутации имеет достаточно большое значение, которое далее постепенно уменьшается. Рассмотрим этот тип оператора для векторного случая
$$\begin{array}{cl}S_v^t=\langle V_1,V_2,\dots ,V_k,\dots V_m\rangle\\V_k\in[l_k,U_k]\end{array}$$В результате выполнения мутации получаем следующий вектор (особь популяции)
$$\begin{array}{cl}S_v^{t+1}=\langle V_1,V_2,\dots ,V'_k,\dots V_m\rangle\\k\in[1,\dots n]\end{array}$$где компонента вектора вычисляется следуюшим образом
$$V'_k=\begin{cases}V_k+\Delta(t,U_k-V_k)\text{при случ. число $=0$}\\V_k-\Delta(t,V_k-l_k)\text{при случ. число $=1$}\end{cases}$$где $$\Delta(t,y)\in[0,y]$$ и $$\Delta(t,y)$$ определяет шаг мутации, который с увеличением номера поколения $$t$$ уменьшается:
$$\begin{array}{cl}\Delta(t,y)\to 0\\t\to\infty\end{array}$$Один из вариантов реализации функции, определяющей шаг $$\Delta(t,y)$$,следующий:
$$\Delta(t,y)=y\cdot\left(1-r^{\left(1-\frac{t}{T}\right)\cdot b}\right)$$где $$r\in[1,\dots n]$$($$r$$-случайное число) и $$T$$ – максимальное число поколений; $$b=2$$– параметр, определяющий степень неоднородности. На рис.3.19 показан для наглядности график изменения шага мутации, который в пределе стремится к 0.
(рис 3.19) Уменьшение шага мутации
Необходимой компонентой является устранение плохих решений, полученных в процессе формирования новой популяции.
Промежуточную популяцию (репродукционную группу) составляют все особи $$t$$-го поколения и новые особи, полученные в результате скрещивания и мутации. Численность этой популяции можно определить следующим образом
$$R^{t+1}=r^t+r_{cr}^t+r_m^t$$где: $$r^t$$- число особей предыдущей популяции;
$$r_{cr}^t$$– численность особей, полученных путем скрещивания;
$$r_m^t$$– число "мутантов".
Обычно в
В простейшем случае с помощью скрещивания и мутации генерируются столько потомков, сколько было родителей. Далее родители устраняются, а потомки формируют следующее поколение $$P(t+1)$$. При этом каждая особь живет лишь одно поколение. Такая схема часто используется в простом ГА. Однако при этом очевидно не исключено, что некоторые очень хорошие решения могут быть заменены худшими, и лучшее решение будет потеряно.
В ней потомков генерируется меньше, чем было родителей. Далее вновь построенные потомки заменяют худших родителей согласно значениям фитнесс-функции. Для этой схемы возможна преждевременная сходимость к локальным экстремумам.
При таком подходе потомков также генерируется меньше, чем было родителей, далее случайным образом удаляется необходимое число родителей, которые заменяются новыми потомками.
Здесь потомков генерируется больше, чем необходимо для замены. Далее заменяют заданное число родителей только лучшими потомками согласно значениям фитнесс-функции
Здесь родители и потомки выступают на равных правах - они помещаются в одну репродукционную группу. В ней все особи этой группы ранжируются и в следующее поколение включаются только лучшие $$N$$ особей. Иногда применяется следующая модификация этого метода. Сначала вычисляется среднее значение ЦФ группы и в следующее поколение включаются те особи, у которых значение ЦФ больше среднего значения группы.
В общем случае к репродукционной группе $$R^{t+1}$$ может быть применен любой метод отбора родителей, которые были рассмотрены в разделе 3.2.
При локальном отборе особи выбираются из ограниченного окружения множества соседей. Замена особей потомками выполняется по такой же схеме. Таким образом сохраняется локальность информации. При этом используются те же структуры и отношения соседства, что и в разделе 3.2.4.
Родитель особи определяются первым родителем из локального окружения (множества соседей). Для выбора удаляемых родителей и отбора потомков для замены применяются следующие схемы:
До сих пор мы рассматривали стационарные синхронные эволюционные алгоритмы, где мощность популяции поддерживается постоянной и переход к следующему поколению "синхронизирован". Здесь обрабатываются все потомки предыдущего поколения, а затем следует переход на следующую итерацию (поколение).
Иногда на практике применяется и асинхронный эволюционный алгоритм, где нет явного разбиения эволюции на поколения, а процесс развития реализуется "по событию" в виде непрерывного потока событий отбора, кроссинговера, мутации и т.п. Здесь вновь порожденные потомки сразу замещают (в некотором смысле худшие) особи (не дожидаясь остальных родительских пар своего поколения). Ниже представлен один из возможных вариантов асинхронного алгоритма реализации ГА с применением турнирного отбора родителей.
Следует отметить, что такой метод, как правило, проще в реализации (особенно аппаратной) и имеет некоторые преимущества.
Данная модификация предназначена для решения задач, которые не требуют популяций с большим числом особей и длинных хромосом. Такой подход оправдан в том случае, когда решение (не обязательно глобальный оптимум) необходимо найти как можно быстрее. В этом случае необходимо уменьшить трудоемкость, связанную с большим количеством итераций, ценой возможно ухудшения качества решения. Такой подход, например, реализован в программе FlexTool [4] следующим генетическим микроалгоритмом.
Отметим, что в
Мощность популяции $$N$$ является важнейшим параметром ГА, который критичен во многих приложениях. Если $$N$$ мало, то ГА работает быстро, но при этом увеличивается опасность преждевременной сходимости к локальному экстремуму. Большая мощность популяции увеличивает генофонд, но процесс поиска замедляется.
На разных этапах работы ГА оптимальное значение $$N$$ может быть различным. На начальном этапе $$N$$ должно быть большим, а на заключительном $$N$$ можно уменьшить.
При одном из подходов в ГА с изменяемым размером популяции каждой особи после ее рождения на текущем этапе оценки целевой функции (ЦФ) присваивается "время жизни" (life time) $$L_f$$– параметр, зависящий от ЦФ особи. Таким образом, каждая особь живет определенное число поколений и умирает по окончании срока жизни. Очевидно, значение этого параметра влияет на размер популяции. В этом случае ГА можно реализовать, например, следующим образом [5].
Нестационарный_ГА
{
t =0;
Инициализация;
Оценка ЦФ p(t);
While (условие окончания не выполнено)
{
t=t+1;
Увеличение возраста каждой особи на 1;
Рекомбинация p(t):
Мутация p(t):
Оценка ЦФ p(t):
Определение срока жизни особей;
Удаление из p(t) всех особей с возрастом больше срока жизни;
}
}
Здесь в текущем поколении $$t$$ алгоритм обрабатывает популяцию $$P(t)$$. В процессе рекомбинации и мутации генерируется промежуточная популяция, состоящая из потомков, и ее размер пропорционален числу исходной $$r_{cr}^t+r_m^t=r\cdot P$$.
Тогда $$|P(t+1)|=|P(t)|+r_a^t-D(t)$$– число особей в новой популяции.
Срок жизни для каждой особи определяется после оценки ЦФ (по формулам, приведенным ниже) и является окончательным, то есть постоянным в процессе эволюции. В таком случае особь живет определенное число поколений, а затем умирает. Срок жизни определяет число поколений, в течении которых особь держится в популяции. Очевидно, что в этом случае, чем больше срок жизни, тем больше потомков может дать особь, так как на каждом этапе родители для рекомбинации выбираются случайно с равной вероятностью. При этом подходе важнейшую роль играет метод определения срока жизни особи.
Очевидно, постоянное значение $$L\ge 2$$ для каждой особи ведет к экспоненциальному росту размеров популяции. Поэтому для каждой особи срок жизни вычисляется индивидуально в зависимости от значения ее ЦФ.
Наиболее часто используются следующие три способа определения срока жизни.
Для их определения введем следующие обозначения:
$$L_f$$:
$$L_f=\min\left\{L_{min} +\eta\cdot\frac{f[i]}{\bar f},L_{max}\right\}$$где $$\eta=\frac12\cdot(L_{max}-L_{min})$$ (используется для всех формул).
Очевидно, что первый метод соответствует пропорциональному отбору отбора родителей - "рулетке". К минимальному сроку жизни добавляется премиальный срок, который пропорционален значению ЦФ для данной особи. Однако эта стратегия имеет серьезный недостаток – она не учитывает информацию о некоторых объективных характеристиках особи, такой, например, как отношение $$\frac{f[i]}{f_\max}$$ (или $$\frac{f[i]}{f_\min}$$) целевой функции по популяции.
Эту проблему решает вторая (линейная) стратегия, где срок жизни определяется исходя из значения ЦФ данной особи относительно максимального значения в популяции $$f_\max$$. Но этот метод тоже имеет свои недостатки - если в популяции много особей имеют значение ЦФ стремящееся к максимальному ($$(f[i]\to f_\max)$$) значению, то такой подход приведет к чрезмерному увеличению размера популяции.
В третьей стратегии (билинейной) предпринята попытка найти компромисс между первыми двумя методами. В ней учитываются разница между сроками жизни, близкими к лучшей особи, используя информацию о среднем значении популяции. Однако в тоже время принимается во внимание минимальное и максимальное значение по популяции.
Для мультимодальных функций, которые имеют много экстремумов, часто представляет интерес найти не одно, а несколько экстремальных значений. С помощью стандартного ГА это трудно сделать, поскольку в процессе эволюции, как правило, благодаря "генетическому дрейфу" особи концентрируются в окрестности одного экстремума. Поэтому для поиска экстремумов мультимодальных функций были разработаны соответствующие методы.
Простейший из них основан на многократном запуске ГА на различных подмножествах пространства поиска решений. Показано [6], что, если все экстремумы имеют примерно одинаковую небольшую вероятность поиска (быть найденными), то число независимых запусков ГА должно быть
$$p\sum_{i=1}^p \frac{1}{i}\approx p(\gamma+\log p)$$где $$p$$– число экстремумов и $$\gamma\approx 0,577$$ - константа Эйлера. К сожалению, в большинстве реальных задач экстремумы не являются равновероятными и поэтому число запусков должно быть больше приведенной оценки. Возможна также параллельная реализация этого итеративного метода.
$$s_f(i)=\frac{f(i)}{m(i)}$$где $$f(i)$$– значение исходной фитнесс-функции и $$m(i)$$ называется счетчиком
где $$d_{ij}$$- евклидово расстояние между двумя особями $$i$$ и $$j$$. Разделяющая функция $$sh(d_{ij})$$ должна обладать следующими свойствами:
$$0\le sh(d_{ij})\le 1$$ для каждого $$d_{ij}$$,
$$s(0)=1,$$$$\lim_{d_{ij}\to \infty} s(d_{ij})=0$$Одной из применяемых на практике функций, для которой эти условия выполняются, является следующая
$$sh(d_{ij})=\begin{cases}1-\left(\frac{d_{ij}}{\sigma_s}\right)^\alpha,\text{если $d_{ij}<\sigma_s$}\\0,\text{в противном случае.}\end{cases}$$Здесь $$\alpha$$ и $$\sigma_s$$ являются константами. Наибольшие трудности в этом методе вызывает выбор значения $$\sigma_s$$, который требует априорного знания числа экстремумов функции, что, как правило, заранее неизвестно.
Имеются различные модификации этого метода. Например, расстояние $$d_{ij}$$ между особями иногда определяются не на уровне фенотипа (евклидово расстояние), а на уровне генотипа, где используется расстояние Хэмминга между двоичными кодами хромосом.
Одним из важнейших преимуществ ГА является то, что они прекрасно сочетаются с другими методами оптимизации, поэтому разработано множество гибридных ГА. Пожалуй самым распространенным подходом является включение локальной оптимизации наряду с генетическими операторами в классическую блок-схему простого ГА. В этом случае локальная оптимизация применяется к каждому полученному потомку, чтобы "сдвинуть" его в сторону локального оптимума перед внедрением его в новую популяцию. При этом ГА используется для глобального расширения пространства поиска, в то время как эвристические методы применяются для "эксплуатации" ближайшего окружения особей. Вследствие того, что ГА и эвристические методы имеют взаимно дополняющие свойства, гибридные ГА часто превосходят по характеристикам входящие в него компоненты.
Другой распространенной формой гибридизации является внедрение адаптации параметров ГА. Характеристики ГА характеризуются балансом между расширением и эксплуатацией пространства поиска решений, который в значительной степени определяется значениями основных параметров ГА, таких как мощность популяции, максимальное число поколений, вероятностей кроссинговера и мутации. Выбор значений этих параметров является одной из важнейших задач при разработке ГА.
Комбинирование ГА и эвристик локального поиска исследовалось многими авторами и предложено множество методов гибридизации, но наиболее распространенными является два: 1)
При втором подходе изменяется только значение фитнесс-функции особи, а генотип остается неизменным. Отметим, что классический ГА разработан Холландом на основе моделирования эволюции Дарвина. Но еще в XIX веке в теорию Дарвина были предложены Ламарком дополнения, где изменения особи в течение ее жизни вследствие воздействия окружающей среды передавались потомкам. Эта теория позволяет организмам накопленный опыт и знания в течение жизни передавать потомкам. Далеко не все биологи разделяют эту точку зрения, но этот эффект имеет место, например, в эволюции общества. Использование
(рис 3.20) Общая структура гибридного ГА
Эксперименты на некоторых тестовых задачах показали [8], что стратегия с Балдвин-эффектом чаще сходится к глобальному оптимуму, в то время как
В ранних работах первого направления в ГА использовались операторы Ламарка [9]. Некоторые авторы [10] ввели вероятность Ламарка для мутации с тем, чтобы получить более контролируемый оператор мутации и операторы локального поиска.
Пусть $$P(t)$$ и $$C(t)$$ обозначают множество родителей и потомков текущей популяции $$t$$. Ниже представлен в виде псевдокода укрупненный алгоритм
Эти идеи получили развитие в
Поскольку ГА навеяны идеей эволюции, естественно ввести элементы адаптации не только в процесс поиска решений задачи, но и в настройку значений параметров ГА для данной проблемы.
(рис 3.21) Пример применения локального поиска в ГА
В последние годы проведено достаточно много исследований в этом направлении, когда в основном рассматриваются два вида адаптации:
Разница между ними в том, что первая модифицирует некоторые компоненты ГА, такие как вид представления особи, кроссинговер, мутация и отбор. Естесственно, для удачного выбора или модификации компонентов необходимо понимать суть решаемой задачи. Во втором виде адаптации предлагается способ настройки значений параметров и конфигурации ГА в процессе решения задачи. Следуя [15, 16] последний вид адаптации можно разбить на следующие классы:
Из этих видов в последние десять лет исследовались различные способы адаптации параметров, таких как вероятности кроссинговера и мутации, мощность популяции, которые играют решающую роль в балансе расширения и эксплуатации пространства поиска решений. Ключевым вопросом является выбор значений параметров для эффективного решения данной проблемы. Обычно в простом ГА используются фиксированные значения параметров, которые находятся методом проб и ошибок. Поскольку сам ГА является динамическим и адаптивным процессом, то фиксированные значения параметров противоречат самому духу эволюции. Поэтому возникла естественная идея попробовать изменять значения параметров в процессе поиска решения. Это можно сделать различными способами:
В работах [15,17] представлен обзор используемых на текущий момент методов адаптации в ГА, в котором выделены три основные категории.
Отметим, что изменение мощности популяции между двумя соседними поколениями прежде всего влияет на функционирование оператора отбора. Пусть $$n_t$$ и $$n_{t+1}$$ обозначают мощность популяции текущего и последующего поколения соответственно. Отбор особей можно рассматривать как повторяющийся процесс $$n_{t+1}$$ операторов отбора с вероятностью $$p_j$$ для $$j$$-ой особи. Для большинства методов отбора, таких, как например, пропорциональный или турнирный отбор с замещением, вероятность выбора $$p_j$$ остается неизменной при выполнении $$n_{t+1}$$ операторов. Тогда ожидаемое количество копий $$j$$-ой особи можно выразить как $$c(j,t+1)=p_j n_{t+1} c(j,t)$$, где $$c(j,t)$$– число копий $$j$$-ой особи в поколении $$t$$. Ожидаемое количество копий $$j$$-ой особи прямо пропорционально мощности популяции следующего поколения. Таким образом, долю в популяции особей, связанных с $$j$$-ой особью после отбора можно выразить следующим выражением:
$$c(j,t+1)=\frac{c(j,t+1)}{n_{t+1}}=\frac{p_j n_{t+1}c(j,t)}{n_{t+1}}=p_j c(j,t)$$которое не зависит от размера следующей популяции на том основании, что изменение мощности популяции несущественно влияет на значение вероятности $$p_j$$. Отметим, что ГА, где мощность популяции уменьшается с ростом поколения, имеет большую начальную и меньшую конечную популяцию. Это повышает эффективность ГА, поскольку большая начальная популяция покрывает большее подпространство поиска, а в конце процесса, когда найдена "зона интереса", для сходимости к оптимуму достаточно и небольшого количества особей в популяции
Основываясь на этих предположениях, был предложен так называемый пилообразный ГА [20], где изменение мощности популяции комбинируется с реинициализацией, которая выполняется для улучшения характеристик ГА. При этом среднее значение мощности популяции $$\bar n$$ по периоду соответствует постоянной популяции ГА с той же вычислительной сложностью. Кроме этого, закон изменения мощности популяции характеризуется амплитудой $$D$$ и периодом $$T$$. В этой нотации размер популяции изменяется следующим образом:
$$n(t)=int\left(\bar n+D-\frac{2D}{T-1}\left(t-T\cdot int\left(\frac{t-1}{T}\right)-1\right)\right)$$На рис.3.22 представлен пример пилообразного изменения мощности популяции.
(рис 3.22) Пилообразное изменение количества особей в популяции
В
Баланс между этими характеристиками ГА определяется значениями вероятности $$P_c$$ и $$P_m$$ и типом используемых генетических операторов (прежде всего кроссинговера). Увеличение значений $$P_c$$ и $$P_m$$ ведет к расширению пространства поиска.
Обычно используют следующие значения вероятностей - $$P_c\in[0,5;1]$$ и $$P_c\in[0,001;0,01]$$. Далее мы рассмотрим другой подход [7], который использует различные значения $$P_c$$ и $$P_m$$ в зависимости от значения ЦФ текущих особей. Для мультимодальных функций существует серьезная проблема преждевременной сходимости к локальным экстремумам.
Чтобы изменять $$P_c$$ и $$P_m$$ адаптивно, с целью предотвращения преждевременной сходимости к локальному экстремуму, надо научиться идентифицировать ситуации, когда ГА сходится к оптимуму. Рассмотрим этот подход на примере поиска максимума для мультимодальной функции (которая имеет несколько экстремумов), которая показана на рис. 3.23
(рис 3.23) Мультимодальная функция
Один из возможных способов обнаружения сходимости – наблюдение разности среднего и максимального значения целевой функции по популяции $$(f_{\max} -\overline f)$$. Обычно эта разность меньше для популяции, которая сходится к оптимуму, чем для популяции, "разбросанной" по пространству поиска решений. Будем использовать разность $$(f_{\max} -\overline f)$$ в качестве основного признака сходимости к оптимуму, причем не обязательно глобальному.
Поскольку вероятности $$P_c$$ и $$P_m$$ должны увеличиваться при преждевременной сходимости к локальному оптимуму (чтобы "выпрыгнуть из ловушки" локального экстремума), то значение $$(f_{\max} -\overline f)$$ должны изменяться обратно пропорционально разности $$(f_{\max} -\overline f)$$:
$$P_c=\frac{k_1}{f_{\max} -\overline f}\qquad P_m=\frac{k_2}{f_{\max} -\overline f}$$Здесь $$P_c$$ и $$P_m$$ не зависят от значений ЦФ для конкретной особи, а определяются для всей популяции, но для разных популяций различных поколений они уже будут разными.
Отметим, что как для хороших решений с высокими значениями целевой функции, так и для плохих, используются одни и те же величины $$P_c$$ и $$P_m$$. Это не рационально, так как когда популяция сходится к глобальному или локальному оптимуму, то $$P_c$$ и $$P_m$$ увеличиваются, что ведет к разрушению близких к оптимуму решений. В результате популяция может не сойтись к глобальному оптимуму. Таким образом, мы избежали ловушки локального экстремума ценой снижения характеристик ГА по поиску глобальных экстремумов.
Чтобы решить эту проблему, нужно сохранить хорошие решения текущей популяции. Это можно сделать, полагая низкие значения вероятности $$P_c$$ и $$P_m$$ для особей с высоким значением ЦФ и высокие значения $$P_c$$ и $$P_m$$ для плохих особей с низкими значениями ЦФ. Тогда лучшие решения будут способствовать сходимости, а худшие – предотвращать ГА от "ловушек" локальных экстремумов. Таким образом, значение $$P_c$$ и $$P_m$$ должны зависеть не только от разности $$(f_{\max} -\overline f)$$, но еще и от значений ЦФ конкретных особей. Чем ближе значение функции к максимальному, тем меньше должно быть значение $$P_c$$ и $$P_m$$:
$$P_c=k_1\cdot\frac{f_{\max} - f'}{f_{\max} -\overline f},\qquad k_1\le 1\\ P_m=k_2\cdot\frac{f_{\max} - f}{f_{\max} -\overline f},\qquad k_2\le 1$$где $$f'$$– лучшее значение целевой функции у двух родителей.
Положим $$P_c=P_m=0$$ для решений, имеющих максимальное значение ЦФ и
$$P_c=k_1,\qquad f'=\bar f\\P_m=k_2,\qquad f'=\bar f$$Отметим, что для плохих решений $$(f,f'<\bar f)$$ значения вероятностей $$P_c$$ и $$P_m$$ в соответствии с формулой (3.23) могут быть больше 1, что некорректно. Поэтому для плохих решений примем:
$$P_c=k_3,\qquad f'\le\bar f\\P_m=k_4,\qquad f'\le\bar f$$В итоге получим:
$$P_c=\begin{cases}k_1\cdot\frac{f_{\max}-f'}{f_{\max}-\bar f}, f'>\bar f\\k_3,\text{иначе}\end{cases}\\P_m=\begin{cases}k_2\cdot\frac{f_{\max}-f'}{f_{\max}-\bar f}, f>\bar f\\k_4,\text{иначе}\end{cases}\\k_1=k_3=1\\k_2=k_4=0,5$$Лучшие решения при этом сохраняются и переходят в следующее поколение. Этот факт может привести к чрезмерному росту популяции, что чревато преждевременной сходимостью. Поэтому иногда дополнительно вводится одна (default) мутация (с вероятностью $$P_d=0,005$$) для всех особей популяции.
Существуют и более строгие
Эвристическая мутация является разновидностью эвристического поиска. Для этого часто используется LS-техника, которая позволяет генерировать новых потомков из отобранных родителей. Следует отметить, что этот оператор может сдвигать потомков в сторону локального оптимума. Число потомков зависит от вероятности мутации $$P_m$$. Фактически значение вероятности мутации определяет вес процесса исследования новых областей в пространстве поиска.
Значения вероятностей иммиграции и кроссинговера определяют вес процесса эксплуатации в пространстве поиска решений. В основной схеме используются два
где $$parSize$$ и $$offSize$$ – означают соответственно значения мощности популяций родителей и потомков, удовлетворяющие заданным ограничениям. Регулирование $$P_M$$ определяется с использованием значений $$\Delta f_{avg}(t-i),i=1,2\dots \mu$$ и регулирование $$P_C$$ и $$P_I$$ выполняется на основе значений коэффициента корреляции особей текущей популяции следующим образом:
$$P_M=regulation1(\Delta f_{avg}(t-i),i=1,2\dots,\mu\\P_C=regulation2(\Delta f_{avg}(t-i),i=1,2\dots,\mu\\P_I=1-(P_M+P_C)$$где процедуры regulation 1 и regulation 2 представлены ниже в виде псевдокода.
Функции принадлежности для $$P_C$$ и $$P_M$$ показаны на рис.3.24 и рис.3.25 соответственно.
(рис 3.24) Функция принадлежности PM.
(рис 3.25) Функция принадлежности PC.
Кроме этого, значения $$\Delta f,\mu_M,\mu_C$$ определяются следующим образом:
$$\Delta f=\sum 2^{t-i}\cdot\lambda(\Delta f_{avg}(t-i)),t\ge\mu\\\\\mu_M=\frac{0,8-0,2}{2^{\mu}-2\alpha},0\le\alpha\le\frac{2^{\mu}}{4}\\\\\mu_C=\frac{0,8(1-P_M)-0,1}{2^{\mu}-2\alpha},0\le\alpha\le\frac{2^{\mu}}{4}\\\\\lambda(x)=\begin{cases}1, if\ x\ge 0\\\\0,\text{otherwise}\end{cases}$$Пусть $$P(t)$$ и $$C(t)$$ обозначают популяции родителей и потомков соответственно, тогда укрупненный алгоритм
Критерий остановки вычислений – повторение лучшего результата заданное количество раз или достижение популяцией определенного возраста (например, 100 эпох).
| № вв. | Название | Оптимум | Вид функции | График функции |
|---|---|---|---|---|
| 1 | De Jong's function 1 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_1(x)=\sum_{i=1}^n x_i^2,\qquad -5,12\le x_i\le 5,12$$ | |
| 2 | Axis parallel hyper-ellipsoid function | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_{la}(x)=\sum_{i=1}^n i\cdot x_i^2,\qquad -5,12\le x_i\le 5,12$$ | |
| 3 | Rotated hyper-ellipsoid function | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_{1b}(x)=\sum_{i=1}^n\left(\sum_{j=1}^i x_j\right)^2,\qquad -65,536\le x_i\le 65,536$$ | |
| 4 | Moved axis parallel hyper-ellipsoid function | global minimum $$f(x)=0; x_i=5*i,\\ I=1:n.$$ | $$f_{1c}(x)=\sum_{i=1}^n 5i\cdot x_i^2,\qquad -5,12\le x_i\le 5,12$$ | |
| 5 | Rosenbrock's valley (De Jong's function 2) | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_2(x)=\sum_{i=1}^{n-1} 100\cdot (x_{i+1}-x_i^2)^2+(1-x_i)^2),\qquad -2,048\le x_i\le 2,048$$ | |
| 6 | Rastrigin's function 6 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_6(x)=10\cdot n+\sum_{i=1}^n(x_i^2-10\cdot \cos(2\cdot\pi\cdot x_i)),\qquad -5,12\le x_i\le 5,12$$ | |
| 7 | Schwefel's function 7 | global minimum $$f(x)=n\cdot 418.9829; x_i=420.9687,\\i=1:n.$$ | $$f_7(x)=\sum_{i=1}^n -x_i\cdot \sin(\sqrt{|x_i|}),\qquad -500\le x_i\le 500$$ | |
| 8 | Griewangk's function 8 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_8(x)=\sum_{i=1}^n \frac{x_i^2}{4000}-\prod_{i=1}^n\cos\left(\frac{x_i}{\sqrt{i}\right)+1,\qquad -600\le x_i\le 600$$ | |
| 9 | Sum of different power function 9 | global minimum $$f(x)=0; x_i=0,\\ I=1:n.$$ | $$f_9(x)=\sum_{i=1}^n|x_i|^{(i+1)},\qquad -1\le x_i\le 1$$ | |
| 10 | Ackley's Path function 10 | global minimum $$f(x)=0; x_i_=0,\\ I=1:n.$$ | $$f_{10}(x)=-a\cdot e^{-b\cdot \sqrt{\frac{\sum_{i=1}^n x_i^2}{n}}}-e^{\frac{\sum_{i=1}^n cos(c\cdot x_i)}{n}}+a+e^1;\qquad -1\le x_i\le 1\\a=20;b=0,2;c=2\cdot \pi$$ | |
| 11 | Langermann's function 11 | global minimum $$f(x)=-1.4 (for\ m=5); x_i=???,\\i=1:n.$$ | $$f_{11}(x)=-\sum_{i=1}^m c_i\cdot(e^{-\frac{\|x-A(i)\|^2}{\pi}}\cdot\cos\left(\pi\cdot\|\bar x-A(i)\|^2)),\qquad 0\le x_i\le 10,\ 2\le m\le10$$ | |
| 12 | Michalewicz's function 12 | global minimum $$f(x)=-4.687 (n=5); x_i=???,\\i=1:n.\\f(x)=-9.66 (n=10); x_i=???,\\i=1:n.$$ | $$f_{12}(x)=-\sum_{i=1}^n \sin(x_i)\cdot\left(\sin\left(\frac{i\cdot x_i^2}{\pi} \right ) \right)^{2\cdot m},\qquad 0\le x_i\le \pi,\ m=10$$ | |
| 13 | Branins's rcos function | global minimum $$f(x_1,x_2)=0.397887;(x_1,x_2)=(-pi,12.275),\\ (\pi,2.275), (9.42478,2.475).$$ | $$f_{Bran}(x_1,x_2)=a\cdot(x_2-b\cdot x_1^2+c\cdotx_1-d)^2+e\cdot(1-f)\cdot(x_1)+e,\\ -5\le x_1\le 10,\ 0\le x_2\le \15\\a=1,b=\frac{5,1}{4\cdot \pi^2},c=\frac{5}{\pi},d=6,e=10,f=\frac{1}{8\cdot\pi}$$ | |
| 14 | Easom's function | global minimum $$f(x_1,x_2)=-1;\\(x_1,x_2)=(\pi,\pi).$$ | $$f_{Easo}(x_1,x_2)=-\cos(x_1)\cdot\cos(x_2)\cdot e^{-((x_1-\pi)^2+(x_2-\pi)^2)},\qquad -100\le x_i\le 100$$ | |
| 15 | Goldstein-Price's function | global minimum $$f(x_1,x_2)=3;\\(x_1,x_2)=(0,-1).$$ | $$f_{Gold}(x_1,x_2)=(1+(x_1+x_2+1)^2\cdot(19-14x_1+3x_1^2-14x_2+6x_1x_2+3x_2^2))\\\cdot(30+(2x_1-3x_2)^2\cdot(18-32x_1+12x_1^2+48x_2-36x_1x_2+27x_2^2)),\\ -2\le x_i\le 2$$ | |
| 16 | Six-hump camel back function | global minimum $$f(x_1,x_2)=-1.0316;\\(x_1,x_2)=(-0.0898,0.7126), (0.0898,-0.7126).$$ | $$f_{Sixh}(x_1,x_2)=(4-2.1\cdot x_1^2+x_1^{4/3})\cdot x_1^2+x1\cdot x_2+(-4+4\cdot x_2^2)\cdot x_2^2;\\ -3\le x_1\le 3,-2\le x_2\le2$$ | |
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.