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

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

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

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

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

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