Алгоритмы / Генетический алгоритм: оптимальный размер популяции

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

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

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

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

Рубрика: Habr