|
Шаг 10. Если к<>0, то провести отбор # хромосом в соответствии с ГкВ1угр, в новую популяцию; перейти к ш. 8. Шаг 11. Завершить работу внутреннего ГА с выдачей лучшей хромосомы по всем популяциям внутреннего ГА.. Шаг.12. Сохранить лучшую хромосому внешней популяции.р:~р-\. Шаг 12. Если /?<>0, то провести отбор г хромосом в соответствии с Ркш1еш. в новую популяцию; перейти к ш. З.то (перейти к ш. 15). Шаг 13. Завершить работу внешнего ГА с выдачей лучшей хромосомы по всем популяциям внешнего ГА. Шаг 14. Останов. Экспериментальное исследование данного алгоритма проводилось при следующих условиях. Число членов внешней популяции -30 (максимальное число пар -10). Число членов внутренней популяции -50. Число итераций внутреннего алгоритма от 25 (для функции Розенброка) до 50 (для более сложной функции Растригина) , внешнего 10; К исходной популяции во внешнем алгоритме при выполнении генетических операторов добавлялось по одному потомку от каждой пары. Типы генетических операторов во внешнем ГА выбирались в соответствии с рекомендациями, полученными в разделе 2.9.; учитывая сложность комбинаторной задачи в качестве кроссинговера использовался разработанный оператор рекомбинации; оператора мутации инверсия; оператора отбора "мягкая схема". Общее число вычислений функции Ик (внутреннего И' внешнего алгоритма) для функции Розенброка составило около-300000, для функции Растригина 600000-800000. Для*уменьшения вычислительной сложности* алгоритмов Конструктора ГА целесообразно исследовать комбинированные алгоритмы, один из которых на основе генетического алгоритма и имитации отжига разрабатывается^ исследуется в 4.1.2. Пример результатов работы предложенного Конструктора при выборе генетических операторов для оптимизации функций Розенброка и Растригина |
других параметров, которые подлежат перебору. Определение числа итераций внутреннего ГЛ -к. Задание числа внешних итераций -р, других параметров внешнего ГА Шаг 2. Начало работы внешнего алгоритма. Число итераций = р. Размер популяции = г. Шаг 3. Селекция пар хромосом для скрещивания. Шаг 4. Выполнить оператор кроссинговера.. Шаг 5. Выполнить мутацию. Шаг 6 . Для всех хромосом внешней популяции запустить внутренний ГА с целью определения функции РкШ1СШ. Шаг 7. Начало работы внутреннего ГА. Сгенерировать популяцию (в виде хромосом рис. 3.16) для внутреннего ГА. Установить число итераций к; размер популяции q. Шаг 8 . Применить генетические операторы (закодированные в хромосоме внешнего ГА) к популяции внутреннего ГА. Вычислить функции Рквнутр. для всех хромосом внутренней популяции (вычисление значений функций П или Р7). Шаг 9. Сохранить лучшую хромосому популяции. к:=к-1. Шаг 10. Если к<>0, то провести отбор # хромосом в соответствии с Р^внутр.в новую популяцию; перейти к ш. 8 . Шаг 11. Завершить работу внутреннего ГА с выдачей лучшей хромосомы по всем популяциям внутреннего ГА.. Шаг.12. Сохранить лучшую хромосому внешней популяции. /?:=/?-1. по Шаг 12. Если р о О, то провести отбор г хромосом в соответствии с ВНСШ .в новую популяцию; перейти к ш. З.то (перейти к ш. 15). Шаг 13. Завершить работу внешнего ГА с выдачей лучшей хромосомы по всем популяциям внешнего ГА. Шаг 14. Останов. Экспериментальное исследование данного алгоритма проводилось при следующих условиях. Число членов внешней популяции -30 (максимальное число пар -10). Число членов внутренней популяции -50. Число итераций внутреннего алгоритма от 25 (для функции Розенброка) до 50 (для более сложной функции Растригина) , внешнего 10. К исходной популяции во внешнем алгоритме при выполнении генетических операторов добавлялось по одному потомку от каждой пары. Типы генетических операторов во внешнем ГА выбирались в соответствии с рекомендациями, полученными в разделе З.З.З.: учитывая сложность комбинаторной задачи в качестве кроссинговера использовался разработанный оператор рекомбинации; оператора мутации инверсия; оператора отбора "мягкая схема". Общее число вычислений функции Гй (внутреннего и внешнего алгоритма) для функции Розенброка составило около 300000, для функции Растригина 600000-800000. Для уменьшения вычислительной сложности алгоритмов Конструктора ГА целесообразно исследовать комбинированные алгоритмы, один из которых на основе генетического алгоритма и имитации отжига разрабатывается и исследуется в 4.1.2. 171 Пример результатов работы предложенного Конструктора при выборе генетических операторов для оптимизации функций Розенброка и Растригина представлен на рис. 3.17. Полученные результаты подтверждают выводы, сделанные в 3.21. Для сложных многоэкстремальных функций (например, для исследуемой функции Растригина) целесообразно использовать следующие генетические операторы: кроссинговер рекомбинация; мутация инверсия; селекция "дальнее родство", а для унимодальных (например, функции Розенброка): кроссинговер одноточечный или двухточечный; мутация генная; селекция "ближнее родство". N А V»*!'Ч V»V/.Л • >, ••.уп* . * * •! *• • 1м ». * V • / ••• • ч •-ч-.чч.•► .• Размер популяции:82 Вид отбора:Злитный Тип мутации:Инверсия Вероятность мутации:0.05 Выбор родительской пары;Дальнее родство на фенотипе Коэффициент изменения мутации:3.69 Кроссинговер:Рекомбинация л*.* На какой Функции л >. поколении Лучшее значение ф ' \ мм Размер популяции:41 Вид отбора:С вытеснением Тип мутации:Генная Вероятность мугации:0.44 Выбор родительской парьгБлижнее родство на генотипе Коэффициент изменения мугации:4.44 Кроссинговер:2*х точечный фиггнесса ш: ш » « ■ ч М 1 ■ ш пм 111Ц м Ц п>>11ц и 1ц ^эд цш ш м На какой Функции1 * ,** * •> 1 • * Количество поколений Розенброка •V. т м м т ш * * * * * — * * * * ' / * * * * * ^ « ^ ^ ; • > * * ---------------------------— — г . г . у ^ш4• * » к ч ч * • ; » * » * • * > * • < * ■ * • * / ^ * . * » * < > * . . * . Лучшее значение Рис.3.17. Результаты работы внешнего генетического алгоритма ГА Применение полученных с помощью внешнего алгоритма параметров ГА, используемых для оптимизации функций Розенброка, позволило сократить число итераций при поиске ~ до £=10-15 (по сравнению с к=25 в предыдущих экспериментах), а функции Растригина до &=20-25 (по сравнению с к=50) при той же точности. 172 |