|
FlexTool
найти
минимум функции, заданной формулой
f(x) = 2х
2
+
1
для целых значений
х
в интервале от 0 до 31.
Генетический микроалгоритм программы
FlexTool
выполняется на
популяции с размерностью, равной пяти. Селекция производится
детерминированным турнирным методом с применением элитарной
А.Е. Кононюк Дискретно-непрерывная математика
174
стратегии, благодаря которой лучшая хромосома текущей популяции
всегда переходит в следующее поколение. Производится одноточечное
скрещивание. Вероятность скрещивания принимается равной 1, а
вероятность мутации - равной 0.
Длина хромосом равна пяти, что очевидно следует из возможности
кодирования 32 целых чисел (для указанного интервала изменения
переменной
х
) пятью битами двоичной последовательности. В
программе FlexTool применяется двоичное кодирование, аналогичное
представленному в примерах 3.1 и 2, однако для удобства программной
реализации используется обратный код, т.е. на первой позиции
находится наименее значащий бит, а на последней - наиболее
значащий. Такой способ записи прямо противоположен повсеместно
распространенной форме записи двоичных чисел.
Существенным элементом выполнения генетического микроалгоритма
считается процедура «рестарта», т.е. запуска его с начальной точки при
обнаружении сходимости (п. 3.13.8). В программе
FlexTool
рестарт
производится периодически после выполнения установленного
количества итераций. По умолчанию оно равно 7, примеры вы-
полнялись именно при этом значении.
Исходная популяция - на первой итерации генетического
микроалгоритма - состоит из следующих хромосом:
[01100] [11000] [01111] [10101] [11001]
со значениями фенотипов
6 3 30 21 19,
которые являются действительными целыми числами из интервала от 0
до 31.
Наименьшее значение функции приспособленности в этой популяции
имеет стоящая на втором месте хромосома с фенотипом, равным трем.
Оно равно 19. Наибольшее значение функции приспособленности у
стоящей на третьем месте хромосомы с фенотипом, равным 30,
составляет 1801. Легко подсчитать, что среднее значение функции
приспособленности будет равно 699,8.
Популяция, полученная в результате селекции и скрещивания,
становится текущей для следующей (второй) итерации. Она характе-
ризуется средним значением функции приспособленности, равным
173,8. Заметно, что это значение меньше, чем рассчитанное для пер-
вого поколения. Наибольшее значение функции приспособленности,
равное 723, имеет хромосома с фенотипом 19. Это наихудшая особь
данной популяции. «Наилучшая к текущему моменту» хромосома с
А.Е. Кононюк Дискретно-непрерывная математика
175
фенотипом, равным двум, имеет минимальное значение функции
приспособленности, которое равно девяти.
В третьем поколении среднее значение функции приспособленности
уменьшается до 13. Наибольшее значение для хромосомы с
фенотипом, равным трем, составляет 19, а наименьшее значение
функции приспособленности для этой популяции, также, как и для
предыдущей, равно девяти. «Наилучшей к текущему моменту» про-
должает оставаться хромосома с фенотипом, равным двум.
В следующих четырех поколениях (от четвертого до седьмого) среднее
значение функции приспособленности по популяции совпадает с
наибольшим и наименьшим значениями, равными девяти. Это
означает, что популяция состоит из одинаковых хромосом с феноти-
пами, равными двум. Следовательно, наблюдается сходимость к ре-
шению, которое не является оптимальным.
До этого момента алгоритм выполнялся аналогично классическому
генетическому алгоритму, причем селекция проводилась детер-
минированным турнирным методом с сохранением наилучшей хро-
мосомы из популяции (элитарная стратегия).
После семи итераций начинается новый цикл выполнения
генетического микроалгоритма. Производится его «рестарт», т.е.
повторный запуск алгоритма с начальной точки - случайного выбора
четырех новых хромосом для включения в популяцию. Из особей
предыдущего поколения сохраняется только одна - «наилучшая к
текущему моменту» хромосома с фенотипом, равным двум.
После селекции и скрещивания в очередном (девятом) поколении
получаем популяцию со средним значением функции приспособ-
ленности, равным 481,4. Наибольшее значение функции приспособ-
ленности, равное 1579, имеет хромосома с фенотипом 28, а наимень-
шее значение, равное девяти, - с фенотипом, равным двум.
На следующих пяти итерациях второго цикла генетического
микроалгоритма мы вновь получаем популяцию, состоящую из
одинаковых хромосом с фенотипом, равным двум, для которых
среднее,
наибольшее
и
наименьшее
значения
функции
приспособленности равны девяти. Следовательно, опять наблюдается
сходимость к решению, которое не является оптимальным.
С пятнадцатого поколения начинается очередной (третий) цикл
выполнения генетического микроалгоритма. Он также открывается
случайным выбором четырех новых хромосом и формированием по-
пуляции с сохранением «наилучшей к текущему моменту» особи с
фенотипом, равным двум.
А.Е. Кононюк Дискретно-непрерывная математика
176
На девятнадцатой итерации генетического микроалгоритма, т.е. в
пятом поколении третьего цикла (состоящего из семи итераций)
возникает сходимость к оптимальному решению, которым оказывается
хромосома с фенотипом, равным 0. Среднее, наибольшее и наи-
меньшее значения функции приспособленности по всей популяции с
19 по 21 поколение остается равным 1.
Далее выполняются очередные циклы по семь итераций,
начинающиеся «рестартом» алгоритма, и в каждом из них наблюдается
сходимость к оптимальному решению, т.е. к хромосоме с фенотипом,
равным 0.
Конечно, задачу из примера 4.1 можно решить с применением
генетического алгоритма с произвольной размерностью популяций,
при задании пользователем значений вероятностей скрещивания и
мутации, а также при выборе им одного из методов селекции (рулетки,
турнирного или рангового). Таким образом, вместо микроалгоритма
можно применить реализованный в программе
Do'stlaringiz bilan baham: |
