Ранжирование по приспособленности

Теперь нам понадобится процедура преобразования вариантов решений в кодовые двоичные строки и обратно.

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

Задание целевой функции. Битовые строки декодируются в свои десятичные эквиваленты, которые используются для задания целевой функции. (Например, при наличии двух сценарных спектров целевая функция дает нам величину координаты Z, или высоту трехмерного изображения, в предположении, что величины f соответствующих сценарных спектров — это координаты X и Y.) Это проделывается для всех вариантов решений, и значения целевой функции для них сохраняются. (Важно: значения целевой функции должны быть неотрицательными!)

Репродуцирование

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

Случайный отбор по приспособленности. Теперь ранжированные целевые функции упорядочиваются следующим образом. Если, скажем, у первой целевой функции коэффициент приспособленности равен 0,05, у второй — 0,1, а у третьей — 0,08, то они следующим образом включаются в схему отбора (образуются интервалы):

первый вариант 0     — 0,05;

второй вариант 0,05 — 0,15;

третий вариант 0,15 — 0,23.

И так продолжают далее, пока верхняя граница последнего варианта не окажется на 1,0.

Далее генерируются два случайных числа в интервале от 0 до 1, нужные для определения на основе предыдущей схемы отбора, какими будут два родителя. Теперь для каждого варианта решения следующего поколения нужно выбрать двух родителей.

Кроссовер. Последовательно формируется каждый бит ребенка — нового варианта решения популяции. Начинают с копирования первого бита первого родителя в первый бит ребенка. Одновременно с этим вы должны генерировать случайное число. Если это случайное число оказывается меньше или равно вероятности кроссовера, деленной на длину гена, то переключаемся на копирование битов от другого родителя. Так, если у нас три сценарных спектра с двенадцатью битами для каждой переменной, то длина гена равна тридцати шести. Если используемая нами вероятность кроссовера равна 0,6, то для переключения на копирование кода другого родителя в последующих битах, генерируемое при каждом бите случайное число должно быть меньше 0,6/36, или 0,01667. Это продолжается до тех пор, пока все биты не будут скопированы в коде ребенка. Данную операцию нужно проделать для всех новых членов популяции.

Обычно вероятности кроссовера находятся в интервале от 0,6 до 0,9. Так, вероятность кроссовера 0,9 означает, что шансы возникновения кроссовера у ребенка будут равны 90% , в среднем; то есть 10% шансов будет за то, что ребенок будет точной копией одного из родителей.