Введение
1 Основные понятия 4
1.1 Цели и задачи работы 4
1.2 Понятия и параметры применяемые в работе 5
1.3 Ход работы 13
2 Исследование влияние мутации на примере тестовых функций 15
2.1 Описание параметров экспериментов в области [-20;20] 15
2.2 Описание параметров экспериментов в области [-10;10] 17
2.3 Функция Растригина 19
2.4 Овражная функция Розенброка 29
2.5 Сферическая функция Де Ионга 38
2.6 Безымянная функция 3 47
2.7 Безымянная функция 4 56
Заключение 65
Список использованных источников 66
Приложение 1 Листинг пользовательский функций 67
Темой дипломной работы является исследование генетического алгоритма с ведением управляемых мутаций.
Генетические алгоритмы тесно связаны с эволюционной теорией, используя методы наследования, скрещивания, мутации и отбора. Главный принцип сформировал Чарльз Дарвин, сказав, что, «Чем выше приспособленность особи к окружающей среде, тем выше ее шансы на выживание».
Генетические алгоритмы направлены на решение задач оптимизации, основой которых является метод случайного поиска. Генетические алгоритмы используют эвристический алгоритм поиска.
Каждую особь нужно рассматривать в какой степени она приспособлена к определенному решению задачи (т.е. в какой степени особь эффективна в конкуренции за какие - либо ресурсы). Такие особи смогут воспроизводить потомство, с помощью перекрестного скрещивания и нести информацию, наследуемую от родителей.
А для особей с наименьшей приспособленностью, уменьшается вероятность скрещивания. За счет этого, свойства и характеристики этих особей будут постепенно исчезать из популяции в процессе эволюции.
Таким образом, можно оптимизировать любую систему, с помощью конкуренции между разными ее состояниями.
Это способ оптимизации чего угодно, что можно выразить в числовой форме. Это позволяет оптимизировать любую функцию с фиксированным набором параметров, оптимизировать поведение любой имитационной модели, математической модели.
Случайный характер процесса мутации особей, лежащий в основе генетического алгоритма, приводит к тому, что результаты экспериментов даже при одних и тех же заданных расчётных параметрах, могут заметно отличаться от эксперимента к эксперименту.
Сравнивая работу генетического алгоритма для разных типов тестовых функций легко заметить, что наиболее адекватные результаты и быстрая скорость сходимости обеспечивается для «гладких» функций (функции Розенброка и Де Ионга), когда глобальный экстремум один во всей области анализа, или локальные экстремумы выражены неярко (функция Растригина) и не мешают процессу размножения особей.
В случае многочисленных локальных экстремумов (Безымянная функция №4), сравнимых по характеру поведения функции в их окрестности с глобальным экстремумом, генетический алгоритм легко «обманывается» и даёт порой неприемлемые результаты, сходясь к точкам локальных минимумов. Точность определения координат минимума при этом также страдает.
Трудности при поиске минимума так же возникают в случаях с резким экспоненциальным характером изменения функции в районе минимума (Безымянная функция №3): даже в случае с более или менее точным определением координат «шипа» погрешности в определении минимального значения функции очень заметны.
Было замечено, что при увеличении процента мутации, так же увеличивается дистанция (расстояние) особей друг от друга, соответственно увеличивается пространство поиска. При увеличении процента мутации, требовалось больше итераций и времени на нахождение минимума. В то время как при малых процентах мутации, поиск минимума занимал гораздо меньше времени. Отсюда можно сделать вывод, что малый процент мутации ускоряет поиск минимума, а больший, наоборот замедляет. Так же было замечено, что при малых процентах мутации, живучесть особей, была гораздо меньшей, чем с мутациями большего процента.
