77 работы. С этой целью рассмотрим влияние генетических операторов на скорость и вероятность нахождения экстремума тестовых функций. Описание эксперимента. Запуск алгоритма оптимизации производился из случайно выбранных точек в пространстве области определения функции. Точность нахождения экстремума 10'3. Критерий останова заданное число итераций. Количество хромосом в популяции -50, из которых с целью повышения устойчивости получаемых решений только 20 пар используются для скрещивания. При формировании новой популяции в отборе участвуют хромосомы текущей популяции, а также все потомки и мутанты. Остальные параметры ГА следующие: кроссинговер исследуемый параметр; вероятность генной мутации -0.01 ; схема отбора "мягкая"; селекция "дальнее родство" с переходом на последних 10 итерациях на "ближнее родство", в качестве функции фитнесса Fit используются оптимизируемые функции. Лучшие хромосомы (по значению Fit) каждой популяции сохраняются в новой популяции. Для сравнения методов было произведено по 100 запусков каждой из тестовых задач. 0,04Р-Д 0,035 -003-0,025 0,02 ■ 0,015 -0,01 0,005 •1 3 5 7 9 11 13 15 17 19 21 23 25 26 27 Число итераций Рис. 2.5. Зависимость изменения Fit от.числа итераций для функции Розеиброка Р'1для различных операторов кроссинговера Исследовались функции FI, F4, F6, F7, отличающиеся количеством экстремумов и количеством' оптимизируемых параметров. Результаты фиксировались после выполнения 25 итераций. Как видно из рис. 2.5, 2.6, увеличение |
хромосом текущей популяции; 5) отбор хромосом в новую популяцию. Точ-зность нахождения экстремума величина порядка 10 . Критерий останова заданное число итераций. Количество хромосом в популяции -50, из которых с целью повышения устойчивости получаемых решений только 20 пар используются для скрещивания. При формировании новой популяции в отборе участвуют хромосомы текущей популяции, а также все потомки и мутанты, оцениваемые по формуле (3 .2 1 ). Остальные параметры ГА следующие: кроссинговер одноточечный; вероятность генной мутации -0.01 ; схема отбора "мягкая"; селекция "дальнее родство" с переходом на последних 10 итерациях на "ближнее родство", в качестве функции фитнесса Fit используются оптимизируемые функции. Лучшие хромосомы (по значению Fit) каждой популяции сохраняются в новой популяции. Для сравнения методов было произведено по 100 запусков каждой из тестовых задач. Полученные результаты (рис.3.26) свидетельствуют о низком проценте экспериментов, в которых было получено значение экстремума с заданной точностью для ГА и метода случайного поиска, а также и для градиентного поиска при оптимизации многоэкстремальных функций F5 и F1. Однако, как показано на рис. 3.8., при оптимизации унимодальных функций F1, F2 наблюдается хорошее приближение найденных экстремумов к истинному экстремуму для всех методов, а при оптимизации многоэкстремальных для методов ГА и случайного поиска. Действительно, из рис. 3.8. видно, что величина q, равная усредненному по исследуемым тестовым функциям значению 157 л экстремуму за счет реализации в алгоритме "естественного отбора", поэтому ГА дает больший процент локализации глобального экстремума. Полученные результаты позволяют сделать следующие выводы: 1) генетические алгоритмы не способны с высокой вероятностью находить точное значение экстремума, но, в отличие от градиентных методов, дают возможность локализовать область существования глобального экстремума; 2 ) для повышения эффективности решения задачи поиска глобального экстремума с помощью ГА необходимо исследовать сочетание различных параметров, обеспечивающее увеличение скорости сходимости алгоритма либо уменьшение его вычислительной сложности. В соответствии с первым выводом целесообразным является создание двухэтапного алгоритма оптимизации: на первом этапе с помощью ГА локализуется зона поиска, а на втором этапе с помощью метода локальной оптимизации находится точное значение экстремума. Разработка и реализация этого алгоритма рассматривается ниже. В соответствии со вторым выводом необходимо провести исследование ГА для определения возможности улучшения его работы. С этой целью рассмотрим влияние генетических операторов на скорость и вероятность нахождения экстремума тестовых функций. Влияние генетических операторов сгит на эффективность поиска Исследовались функции /П, -Г4, /^6 , /*7, отличающиеся количеством экстремумов и количеством оптимизируемых параметров. 159 Результаты фиксировались после выполнения 25 итераций. Как видно из рис. 3.9, 3.10, уве личение числа итераций свыше 25 не приводит к существенному изменению результатов Число членов популяции -50, способ кодирования числовой. Для получения устойчивых результатов были вычислены максимальные, минимальные и средние значения функций Fit по 10 запускам. Число вычислений функции Fit по каждому запуску около 1000. Pit 1 3 5 7 9 11 13 15 17 19 21 23 25 26 27 . . . . . . . Од ноточ — • — Двухточ — *— Рекомб Рис. 3.9. Зависимость изменения Fit от числа итераций для функции Розенброка Р1для различных операторов кроссинговера 1 3 5 7 9 11 13 15 17 19 21 23 25 26 27 Одноточ Двухточ Рекомб Число итераций Рис. 3.10. Зависимость изменения Fit от числа итераций для функции Растригина (n=10)-F7 для различных операторов кроссинговера |