Содержание
- 2. Эволюционный поиск Эволюционный поиск – это последовательное преобразование одного конечного множества промежуточных решений в другое. Основой
- 3. Особенности АЭ Выделяют три особенности алгоритма эволюции (АЭ): 1) каждая новая популяция, состоит только из «жизнеспособных»
- 4. История В конце 1960-х годов американский исследователь Джон Холланд предложил в качестве механизма комбинаторного перебора вариантов
- 5. Основные принципы ГА Генетические алгоритмы (ГА) есть случайно направленные поисковые алгоритмы, основанные на механизмах естественной селекции
- 6. Принципы моделирования ГА Генетический алгоритм поиска решения заключается в моделировании эволюционирования подобной искусственной популяции. В ГА
- 7. Принципы моделирования ГА В общем случае ГА работает с кодированными структурами безотносительно их смысловой интерпретации. Сам
- 8. Принципы моделирования ГА Популяция развивается (эволюционирует) от одного поколения к другому. Создание новых особей в процессе
- 9. Принципы моделирования ГА Моделирование процесса мутации новых особей осуществляется за счет применения оператора мутации, которые позволяют
- 10. Принципы настройки готового ГА К таким параметрам ГА относятся: размер популяции, набор генетических операторов, задействованных в
- 11. Общая схема классического ГА Генерация исходной популяции. Селекция родителей. Кроссинговер (скрещивание). Мутация. Объединение популяций и редукция.
- 12. Генерация исходной популяции Стратегия "одеяла" – формирование полной популяции, содержащей все возможные решения. Например, для n-разрядной
- 13. Отбор родителей (селекция) Пропорциональный отбор (метод "рулетки") Ранжирование Равномерное ранжирование (случайный выбор) Локальный отбор Отбор на
- 14. Пропорциональный отбор (метод "рулетки") Этот вид отбора чаще всего используется на практике. При этом особи (решения)
- 15. Пропорциональный отбор (метод "рулетки") - зависимость от положительных значений целевой функции (целевая функция должна для всех
- 16. Ранжирование Особи популяции сортируются согласно значениям целевой функции. Отметим, что здесь вероятность отбора для каждой особи
- 17. Равномерное ранжирование Вероятность выбора особи определяется выражением: где параметр определяет какие особи не будут рассматриваться.
- 18. Локальный отбор Производится среди особей, для которых возможно определить отношение ближнего соседства. (Ранее в качестве соседей
- 19. Отбор на основе усечения Отбираемые особи упорядочиваются согласно их значениям целевой функции. В качестве родителей выбираются
- 20. Турнирный отбор Из популяции случайно отбираются m особей, и лучшая из них выбирается в качестве родителя.
- 21. Отбор родителей из промежуточной группы Случайный выбор (панмиксия) родительской пары, при котором оба родителя случайным образом
- 22. Кроссинговер (скрещивание) Различают два основных вида кроссинговера: “Двоичная” рекомбинация: 1) Одноточечный кроссинговер 2) Многоточечный кроссинговер 3)
- 23. Двоичная рекомбинация Одноточечный кроссинговер
- 24. Двоичная рекомбинация Многоточечный кроссинговер
- 25. Двоичная рекомбинация:однородный кр-р Случайным образом генерируется двоичная маска кроссинговера той же длины. Маска задаёт какой из
- 26. Двоичная рекомбинация: ограниченный кр-р Точки скрещивания кроссинговера могут выбираться только там, где значения генов у родителей
- 27. Рекомбинация действительных значений Дискретная рекомбинация: аналогична однородному кроссинговеру, только подразумевается, что генами являются числа. Промежуточная рекомбинация:
- 28. Рекомбинация действительных значений Линейная рекомбинация аналогична промежуточной рекомбинации с тем только отличием, что коэффициент выбирается для
- 29. Понятие “схемы” Понятие «схема» (по Холанду) - это шаблон, описывающий подмножество стрингов, имеющих одинаковые значения в
- 30. Влияние кроссинговера: сохранение схем Рассмотрим конкретный стринг длины n = 7 А = 011| 1000 и
- 31. Влияние кроссинговера: сохранение схем Схема Н2 имеет L(H2) = 1 и вероятность её уничтожения P(d) =
- 32. Влияние кроссинговера: сохранение схем Таким образом, число схем Н в новой популяции зависит от двух факторов:
- 33. Влияние мутации: сохранение схем Оператор мутации (ОМ) - это случайное изменение гена в хромосоме с вероятностью
- 34. Влияние кроссинговера и мутации: сохранение схем Поскольку вероятность выживания равна (1- вероятности разрушения при ОК и
- 35. Мутация После выполнения оператора скрещивания полученные потомки с вероятностью Рm подвергаются мутации, которая может быть выполнена
- 36. Мутация Двоичная мутация: 1) Классическая мутация: замена случайно выбранного узла. 2) Оператор инверсии: изменение прямого порядка
- 37. Сокращение промежуточной популяции Глобальная редукция - промежуточную популяцию (репродукционную группу) составляют все особи t-поколения, особи полученные
- 38. Чистая замена и Элитарная схема В простейшем случае с помощью скрещивания и мутации генерируются столько потомков,
- 39. Равномерная случайная замена и пропорциональная редукция При равномерной случайной замене потомков также генерируется меньше, чем было
- 40. Селекционная схема Родители и потомки выступают на равных правах, все они помещаются в одну репродукционную группу.
- 41. Локальная замена Родитель особи определяются первым родителем из локального окружения (множества соседей). Для выбора удаляемых родителей
- 42. ГА с изменяемой мощностью популяции Если мощность популяции относительно мала, то ГА работает быстро, но при
- 43. Структура ГА с изменяемой мощностью популяции Инициализация начальной популяции p(t); Оценка ЦФ p(t); Определение срока жизни
- 44. ГА с изменяемой мощностью популяции Срок жизни для каждой особи определяется после оценки значений ЦФ и
- 45. Стратегии определения срока жизни особи 1) Пропорциональный метод определения срока жизни. 2) Линейный метод определения срока
- 46. Пропорциональный метод определения срока жизни Срок жизни определяется формулой: где , переменные L - означают минимальный
- 47. Линейный способ определения срока жизни особи Срок жизни определяется формулой: где переменные L - означают минимальный
- 48. Билинейный способ определения срока жизни особи Срок жизни определяется формулой: где переменные L - означают минимальный
- 49. Пример решения задачи Рассмотрим следующий пример, в котором для функции f(x)=(1,85 -x)*cos(3,5x – 0,5) необходимо найти
- 50. Порядок решения задачи Создание исходной популяции: приемлемые варианты. Аргументация выбора сбособа создания исходной популяции. Кодирование особи-решения.
- 51. Пример внешнего вида UI реализации
- 53. Скачать презентацию