Теоретическая часть. Генетические алгоритмы и эволюционные стратегии поиска

Генетические алгоритмы и эволюционные стратегии поиска

Генетические алгоритмы (ГА) предназначены для нахождения экстремумов функций от произвольных объектов, используя при этом приемы, заимствованные у естественной эволюции. Сами объекты трактуются как некоторые организмы, а оптимизируемая функция – как приспособленность организмов, или фитнесс-функция. Множество возможных объектов взаимно однозначно отображается на некоторое подмножество множество битовых строк (обычно фиксированной длины). Эти строки трактуются как хромосомы (геномы).

Особенность генетических алгоритмов заключается в том, что они работают с битовыми строками, не опираясь на структуру исходных объектов, что позволяет применять ГА без модификации для любых объектов. Единственно, что требуется для такого применения, – это перекодирование объектов в геномы.

Эволюционные стратегии отличаются от генетических алгоритмов лишь в том, что в первых используются структурированные описания объектов, то есть такие описания, элементы которых имеют вполне четкий смысл в той предметной области, к которой относятся данные объекты.

Двумя основными механизмами эволюции, наиболее часто моделируемыми в генетических алгоритмах и эволюционных стратегиях, являются скрещивание и мутации. При этом схема эволюционных методов поиска выглядит следующим образом.

1. Сгенерировать начальную популяцию (случайную совокупность объектов).

2. Выбрать родительские пары.

3. Для каждой родительской пары с использованием оператора скрещивания породить потомство.

4. В хромосомы порожденного потомства внести случайные искажения оператором мутации.

5. Произвести отбор особей из популяции по значению их фитнесс-функции.

6. Повторять шаги 2-4, пока не выполнится критерий остановки.

Рассмотрим каждый из шагов чуть подробнее.

1. Генерация начальной популяции обычно производится равномерно по пространству генов (или по пространству описаний объектов). Размер популяции – установочный параметр.

2. Выбор родительских пар может осуществляться различными способами. Выбор родителей осуществляется в два этапа: выбор первого родителя и формирование пары. При выборе одного родителя обычно используется один из следующих способов:

- с равной вероятностью выбирается любая особь из имеющейся популяции;

- особь выбирается случайно с вероятностью, пропорциональной значению фитнесс-функции; то есть в этом случае значение фитнесс-функции сказывается не только на том, какие особи останутся в популяции в результате отбора, но и на то, сколько потомства они произведут.

Выбор второго родителя осуществляется по одному из следующих критериев:

- независимо от уже выбранного родителя (то есть второй родитель выбирается абсолютно так же, как и первый);

- на основе ближнего родства;

- на основе дальнего родства.

В последних двух случаях выбор одного родителя влияет на выбор другого родителя: с большей вероятностью формируются пары, состоящие из особей, которые больше похожи друг на друга (то есть ближе находятся в пространстве геномов или описаний объектов) в случае использования ближнего родства и меньше похожи – в случае дальнего родства. В генетических алгоритмах в качестве меры близости обычно используется расстояние Хемминга.

3. Оператор скрещивания – это оператор, который определяет, как из хромосом родителей формировать хромосомы их потомства. Часто применяется следующий оператор скрещивания: хромосомы делятся в некоторой случайной точке и обмениваются этими участками (то есть, все, что идет до этой точки, берется от одного родителя, а все, что после, – от другого). Это одноточечный кроссинговер. В многоточечном кроссинговере таких участков обмена больше.

При равномерном скрещивании каждый бит хромосомы берется от случайного родителя.

4. Мутации обычно осуществляются как случайная замена одного бита хромосомы. Скорость мутаций выражается в том, как часто они осуществляются. Это управляемый параметр, который влияет на скорость сходимости и вероятность попадания в локальный экстремум.

5. Отбор особей в новую популяцию чаще всего осуществляется одной из двух стратегий:

- пропорциональный отбор, при котором вероятность того, что некая особь останется в следующей популяции, пропорциональна значению фитнесс-функции этой особи;

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

Формирование новой популяции может осуществляться как на основе потомков и родителей, так и на основе только потомков в зависимости от конкретной реализации.

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

Особенности реализации генетических операторов в эволюционных стратегиях

Рассмотрим особенности реализации генетических операторов в эволюционных стратегиях на примере объектов, описаниями которых являются двухкомпонентные векторы: (x, y).

1. Генерация начальной популяции может осуществляться путем выбора случайных векторов из области , где величины задают ожидаемые минимальные и максимальные значения переменных x и y искомого положения экстремума фитнесс-функции.

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

3. Результатом скрещивания двух особей в рассматриваемом случае будет являться особь , где – случайная величина.

4. Результатом мутации для особи будет являться особь , где – случайные величины. Их распределение вероятностей может быть выбрано гауссовым или, для простоты программной реализации, равномерным в некотором интервале. Дисперсия этих величин определяет скорость мутаций.

5 и 6. Операторы отбора и критерии останова в эволюционных стратегиях не имеют особых отличий от тех, которые используются в генетических алгоритмах.

Дата добавления: 2015-06-27