|
74 Сравним возможности ГА с классическими алгоритмами оптимизации: с методом градиентного спуска и методом случайного поиска по вероятности нахождения экстремума [8, 102]. Для этого выберем из набора тестовых функций такие, которые имеют только локальный экстремум: П , Г2, а также многоэкстремальную функцию Р5 и 10-мерную функцию Р7. На рис. 2.3 представлены зависимости вероятности нахождения экстремума для выбранных функций и сравниваемых алгоритмов, усредненные по числу запусков = 100. Рис, 2.3. Вероятность р нахождения точного значения экстремумов функций Для ГА каждая итерация представляет собой выполнение следующих действий: 1) селекция хромосом; 2) выполнение операции кроссинговера; 3) выполнение операции мутации; 4) вычисление функции фитнесса для всех хромосом текущей популяции; 5) отбор хромосом в новую популяцию. Описание эксперимента. Запуск алгоритма оптимизации производился из случайно выбранных точек в пространстве области определения функции. Точность нахождения экстремума —10"3. Критерий останова заданное число итераций. Количество хромосом в популяции -50, из которых с целью повышения устойчивости получаемых решений только 20 пар используются для скрещивания. При формировании новой популяции в отборе участвуют хро |
сание поведения популяции, управляемой генетическим алгоритмом при определенных значениях его параметров. Оценка эффективности ГА по вероятности нахождения экстремума Сравним возможности ГА с классическими алгоритмами оптимизации: с методом градиентного спуска и методом случайного поиска по вероятности нахождения экстремума, вычисляемой по формуле (3.26.). Для этого выберем из набора тестовых функций такие, которые имеют только локальный экстремум: Г\, F2 , а также многоэкстремальную функцию Г5 и 10-мерную функцию Г7. На рис. 3.7 представлены зависимости вероятности нахождения экстремума для выбранных функций и сравниваемых алгоритмов, усредненные по числу запусков = 100. град, метод ген. алгоритм случ. поиск Рис. 3.7. Вероятностьр нахождения точного значения экстремумов функций Для ГА каждая итерация представляет собой выполнение следующих действий: 1) селекция хромосом; 2 ) выполнение операции кроссинговера; 3) выполнение операции мутации; 4) вычисление функции фитнесса для всех 156 хромосом текущей популяции; 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 |