Создание исходной популяции

Существует основных 3 способа создания исходной популяции:

1. Стратегия "одеяла" - формирование полной популяции, содержащей все возможные решения. Например, для n - разрядной хромосомы мы имеем всего 2ⁿ вариантов решений, которые формируют полную популяцию.

2. Стратегия "дробовика" - генерация достаточно большого случайного подмножества решений.

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

Первый подход (стратегия «одеяла») практически не реализуем даже для задач большой и средней размерности, вследствие больших вычислительных затрат. Популяция не может развиваться, т.к. в ней уже содержатся всевозможные решения.

Третий способ используется тогда, когда есть предположение, что некоторое решение является вариацией известного значения. В этом случае время поиска оптимального решения существенно сокращается, т.к. алгоритм начинает работу в окрестности оптимального решения.

Чаще всего применяют второй способ. В этом случае в результате эволюции есть возможность перейти в другие подобласти поиска.

Эффективность ГА во многом зависит от качества и структуры начальной популяции.

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

Отбор родителей (селекция)

Оператор отбора S порождает промежуточную популяцию ^tиз текущей популяции ^t → Р^t.

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

Рассмотрим наиболее распространенные методы решения:

Пропорциональный отбор (метод "рулетки")

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

Здесь на отрезке [0,1] для каждой особи строятся отрезки, длины которых пропорциональны вероятностям выбора особей, как это показано на рисунке.

1 2 3 4 5 6 7 8

Рисунок - Вероятность выбора особей методом рулетки

Случайно генерируются числа от 0 до 1 и в промежуточную популяцию выбираются те особи, в "чей отрезок" попадают эти случайные числа.

Данный метод имеет следующие недостатки:

- зависимость от положительных значений целевой функции;

- без модификации метод может использоваться без модификации только для максимизации функции;

- простое добавление очень большой константы к целевой функции, может свести способ отбора практически к случайному выбору;

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

Для устранения этих недостатков используют масштабирование относительно минимального значения в популяции или используется метод ранжирования.

Для приведенного примера можно привести следующую гистограмму выбора особей.

Метод ранжирования

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

P_s (a_i) = ,

где 1 ≤ a ≤ 2 выбирается случайным образом;

b = 2 – a;

N – мощность популяции;

i – номер особи в упорядоченном списке.

Для приведенного примера гистограмма вероятностей выбора особей методом ранжирования, представлена на следующем рисунке. Высота "ступенек " в отличие от предыдущего выбора.

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

Равномерное ранжирование (случайный выбор)

Здесь вероятность выбора особи определяется следующем выражением:

P_s (a_i) = при 1 ≤ i ≤ µ

0 при µ ≤ i ≤ N

где µ ≤ N – параметр метода.