Дискретно-непрерывная математика. Кн. 0 : Алгоритмы. Ч. Генетические алгоритмы

Стратегии формирования нового поколения
После скрещивания особей необходимо решить проблему о том какие 
из новых особей войдут в следующее поколение, а какие - нет, и что 
делать с их предками. Есть два способа:
1.
Новые особи (потомки) занимают места своих родителей. 
После чего наступает следующий этап, в котором потомки 
оцениваются, отбираются, дают потомство и уступают место 
своим "детям".
2.
Создается промежуточная популяция, которая включает в себя 
как родителей, так и их потомков. Члены этой популяции 
оцениваются, а затем из них выбираются N самых лучших, 
которые и войдут в следующее поколение.

---

А.Е. Кононюк Дискретно-непрерывная математика 
168 
4.2. 
Проверка эффективности ГА с 
использованием тестовых функций 
После того как написан свой собственный ГА вам хочется знать 
насколько он хорош. Ниже приведены некоторые тестовые функции 
для ГА. Все тестовые функции могут иметь различное число 
параметров (n). Поэтому имеет смысл запустить алгоритм для 
оптимизации некоторой функции сначала с небольшим n (например, 10 
или 20), а затем с n=50, 100, 200,... Это даст возможность проверить 
масштабируемость алгоритма.
Эффективность работы ГА принято оценивать количеством 
вычислений целевой функции. Чем меньше, тем лучше. После 
некоторых функций приведены результаты работы QGA генетического 
олгаритма. Результаты целевой функции меньше 0.001 тоже 
засчитывались 
как 
найденный 
глобальный 
минимум. 
Вот 
характеристики QGA:

Фиксированный размер популяции;

Фиксированная разрядность генов;

Количество точек разрыва кроссовера равно числу генов (на 
каждый ген приходится ровно одна точка);

Для скрещивания отбираются 50% популяции;

Вероятность мутации 95%;

Две "элитные" особи;

Удаление одинаковых особей из популяции (с помощью 
мутации);

Точность вычислений: 0.001;

Результат подсчитан по 50 запускам алгоритма;
Т.к. генетические алгоритмы используют стохастичность, то для того, 
чтобы определить, насколько эффективен ваш ГА нужно запустить его 
на одной и той же тестовой функции несколько раз и только после 
этого анализировать результат. Например, QGA ГА для функции 
Растригина от 50 переменных находит глобальный минимум в ~40% 
случаев, используя не более 10000 вычислений функции.

---

А.Е. Кононюк Дискретно-непрерывная математика 
169 
Для некоторых функций есть графики для случая двух переменных. 
Графики представляют "сечение" поверхности функции плоскостью, 
проходящей через глобальный минимум, перпендикулярной одной из 
осей координат.
Ниже приводится набор тестовых функций.
Sphere model.
Считается легкой функцией для любого метода оптимизации.
хО
(-5,12; 5,12) 
Один минимум равный 0 в точке, где x
i
=0.0.
Результат QGA
: 
n=10
, количество нахождений глобального минимума (он здесь один) 
86%, число вычислений целевой функции не более 1250, максимальное 
значение 0,008325. 
n=30
, количество нахождений глобального минимума 34%, число 
вычислений целевой функции не более 1250, максимальное значение 
0,108851. 
n=50
, количество нахождений глобального минимума 46%, число 
вычислений целевой функции не более 2500, максимальное значение 
0,016291, для скрещивания отбиралось 40% популяции.