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

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

В предыдущем очерке) в качестве эффективного метода борьбы с преждевременной  сходимостью было выбрано использование  оператора митоза: 
 
Каждая хромосома, к которой применен оператор митоза, заведомо производит как минимум одного полностью идентичного ей самой потомка. 
Помимо этого, чем больше приспособленность хромосомы превышает среднее значение приспособленности по всей популяции, тем больше вероятность того, что хромосома произведет второго потомка. 
 
Хромосомы с меньшей приспособленностью формируют пул для скрещивания между собой. Попарное скрещивание хромосом из пула проводится до тех пор пока не будет достигнута требуемая общая численность популяции (с учетом хромосом уже созданных с помощью оператора митоза). Выбор хромосом для скрещивания производится случайным образом методом рулетки (хромосомам с большей приспособленностью соответствует больший сектор на колесе рулетки). Численность популяции остается постоянной на протяжении всего времени работы генетического алгоритма. 
 
Доля хромосом к которым применяется оператор митоза обратно пропорциональна средней величине приспособленности популяции и прямо пропорциональна среднеквадратичному отклонению приспособленности популяции (причем зависимость выбираем не линейную, а логарифмическую). Для первого поколения задаем долю популяции, размножающейся митозом, равной 50% 
 
 
Итак зависимость полученного результата от размера популяции выглядит следующим образом: 
 
— по вертикальной оси отложены средние значения функции приспособленности хромосом, полученных в результате работы генетического алгоритма, где 1 — это значение функции приспособленности, равное глобальному максимуму; 
— по горизонтальной оси отложены значения размера популяции, где 1 — это размер популяции равный N (минимально необходимый размер популяции). 
, где: 
P — требуемая вероятность того, что популяция будет содержать все необходимые для рекомбинирования элементы; 
L — число локусов в хромосоме. 
Для рассматриваемого примера N=20 
 
Из графика хорошо видно, что в ситуации практически неограниченных ресурсов можно последовательно увеличивать размер популяции до тех пор пока не будет достигнуто насыщение (соответствует достижению абсолютного максимума).  
 
Если же ресурсы ограничены (в конечном итоге все сводится к временным ограничениям), то важным становится вопрос эффективности их использования. 
 
Рассмотрим вопрос о том какой размер популяции является наиболее выгодным с точки зрения соотношения достигнутый результат / затраченные на вычисление ресурсы. 
 
Переформулируем задачу следующим образом: что выгоднее один раз запустить ГА с размером популяции 2N или два раза запустить алгоритм с размером популяции N и выбрать из 2-х полученных наилучший результат? 
Результаты сравнения можно увидеть на следующем графике: 
 
 
— по вертикальной оси отложены средние значения функции приспособленности хромосом, полученных в результате работы генетического алгоритма, где 1 — это значение функции приспособленности, равное глобальному максимуму; 
— по горизонтальной оси отложено количество расчетов функции приспособленности, где 1 — это N подсчетов. 
Количество расчетов определяется как размер популяции (выраженный в единицах N), умноженное на количество поколений (до останова алгоритма) и умноженное на количество запусков алгоритма. 
 
Точки, обозначенные x1, соответствуют размеру популяции N. 
При этом первая точка соответствует единичному запуску ГА; 
вторая точка соответствует 2-м запускам ГА и выбору из полученных результатов максимального значения и т.д. 
 
Точки, обозначенные x2, соответствуют размеру популяции 2N 
и т.д. 
 
Хорошо видно, что заметный рост эффективности достигается только при переходе от популяции размером N к популяции размером 2N. 
Дальнейшее наращивание размера популяции не приводит к сколь-нибудь заметному росту эффективности. 
 
Таким образом в ситуации жесткого лимита по времени эффективной стратегией будет запустить ГА с размером популяции 2N, если лимит по времени не исчерпан, то запустить ГА еще раз и выбрать наилучший результат и т.д. — до исчерпания лимита. 
В итоге последовательно улучшать результат пока не исчерпан лимит времени. 
Количество запусков до исчерпания лимита — будет постоянно варьироваться (как из-за вариаций в количестве поколений до останова алгоритма; так и из-за того, что в зависимости от загрузки процессора другими задачами одно и тоже процессорное время будет разниться по физическому времени). 
Также, при наличии такой физической возможности, возможны несколько запусков в паралель.