Разнообразие генетических алгоритмов

Известно, что генетический алгоритм способен быстро найти во всей области поиска хорошие решения, но он может испытывать трудности в получении из них наилучших. Обычный оптимизационный метод может быстро достичь локального максимума, но не может найти глобальный. Сочетание двух алгоритмов позволяет использовать преимущества обоих.

СНС (Eshelman, 1991) расшифровывается как Cross-population selection, Heterogeneous recombination and Cataclysmic mutation. Данный алгоритм довольно быстро сходится из-за того, что в нем нет мутаций, следующих за оператором кроссинговера, используются популяции небольшого размера, и отбор особей в следующее поколение ведется и между родительскими особями, и между их потомками. В данном методе для кроссинговера выбирается случайная пара, но не допускается, чтобы между родителями было маленькое хеммингово расстояние или мало расстояние между крайними различающимися битами. Для скрещивания используется разновидность однородного кроссовера HUX (Half Uniform Crossover), при котором потомку переходит ровно половина битов каждого родителя. Для нового поколения выбираются N лучших различных особей среди родителей и детей. При этом дублирование строк не допускается. В модели СНС размер популяции относительно мал - около 50 особей. Это оправдывает использование однородного кроссинговера и позволяет алгоритму сойтись к решению. При получении более или менее одинаковых строк СНС применяет cataclysmic mutation: все строки, кроме самой приспособленной, подвергаются сильной мутации (изменяется около трети битов). Таким образом, алгоритм перезапускается и далее продолжает работу, применяя только кроссинговер.

В генетическом алгоритме с нефиксированным размером популяции (Genetic Algorith with Varying Population Size - GAVaPS) каждой особи приписывается максимальный возраст, т.е. число поколений, по прошествии которых особь погибает. Внедрение в алгоритм нового параметра - возраста - позволяет исключить оператор отбора в новую популяцию. Возраст каждой особи индивидуален и зависит от ее приспособленности. В каждом поколении t на этапе воспроизведения обычным образом создается дополнительная популяция из потомков. Размер дополнительной популяции (AuxPopsize(t)) пропорционален размеру основной популяции (Popsize(t)) и равен:

AuxPopsize(t) = [Popsize(t) pc],

где pc - вероятность воспроизведения.

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

Popsize(t + 1) = Popsize(t) + AuxPopsize(t) - D(t),

где D(t) - число особей, которые умирают в поколении t.