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

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

Канонический ГА. Данная модель алгоритма является классической. Она была предложена Джоном Холландом. Согласно ей, популяция состоит из N хромосом с фиксированной разрядностью генов. С помощью пропорционального отбора формируется промежуточный массив, из которого случайным образом выбираются два родителя. Далее производится одноточечный кроссинговер, и созданные два потомка мутируют (одноточечная мутация) с заданной вероятностью. Мутировавшие потомки занимают места своих родителей. Процесс продолжается до тех пор, пока не будет достигнут критерий окончания алгоритма.

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

Метод прерывистого равновесия. Данный метод основан на палеонтологической теории прерывистого равновесия, которая описывает быструю эволюцию за счет вулканических и других изменений земной коры. Для применения данного метода в технических задачах предлагается после каждой генерации промежуточного поколения случайным образом перемешивать особи в популяции, а затем применять основной ГА. В данной модели для отбора родительских пар используется панмиксия. Получившиеся в результате кроссинговера потомки и наиболее пригодные родители случайным образом смешиваются. Из общей массы в новое поколения попадут лишь те особи, пригодность которых выше средней. Тем самым достигается управление размером популяции в зависимости от наличия лучших особей. Такая модификация метода прерывистого равновесия может позволить сократить неперспективные популяции и расширить популяции, в которых находятся лучшие индивидуальности. Данный метод используется для эффективного выхода из локальных ям.

Гибридный алгоритм. Идея гибридных алгоритмов (Hybrid algorithms) заключается в сочетании генетического алгоритма с некоторым другим классическим методом поиска, подходящим в данной задаче. В каждом поколении все сгенерированные потомки оптимизируются выбранным методом и затем заносятся в новую популяцию. Тем самым получается, что каждая особь в популяции достигает локального оптимума, вблизи которого она находится. Далее производятся обычные для ГА действия: отбор родительских пар, кроссинговер и мутации. На практике гибридные алгоритмы оказываются очень удачными. Это связано с тем, что вероятность попадания одной из особей в область глобального максимума обычно велика. После оптимизации такая особь будет являться решением задачи.

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

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

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

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

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

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

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

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