Эволюционно-генетические алгоритмы

Кафедра информатики и автоматизации научных исследований

Специальность: Прикладная информатика

Преподаватель: Неймарк Е.А.

Целями освоения дисциплины (модуля) «Эволюционно-генетические алгоритмы»  являются знакомство студентов с практическим применением теории оптимизации на примере эволюционно-генетических алгоритмов. В рамках курса засматриваются непрерывные и дискретные задачи оптимизации, схема эволюционно-генетического алгоритма и его операторы. Затрагиваются теоретические основы работы алгоритма.

В курс включены основные понятия теории оптимизации, понятие генетического алгоритма, его структура и основные операторы.

К дисциплинам, необходимых для освоения данной дисциплиной, относятся дисциплины базовой части  математического и естественнонаучного цикла «Информатика (математические основы информатики)», вариативной части  «Теория вычислительной сложности».

В результате освоения дисциплины обучающийся должен:

Знать: базовую схему эволюционно-генетического алгоритма и его операторы, основные методы обработки ограничений задач оптимизации при использовании эволюционно-генетического алгоритма.

Уметь: ориентироваться в особенностях применения генетических операторов к различным оптимизационным задачам

Владеть: навыками программной реализации эволюционно-генетического алгоритма, умением грамотно ставить условия эксперимента и делать из него выводы.

Содержание

  1. Математическая модель принятия оптимальных решений. Критерии сравнения. Задача однокритериального выбора. Задачи переборного типа. Классы сложности задач однокритериального выбора. Комбинаторные задачи оптимизации.
  2. Переход от задачи оптимизации к задаче поиска. Кодирование решений. Бинарное кодирование, коды Грея (понятие близости решений и соответствующих кодировок). Функции кодирования и декодирования. Функция приспособленности.  Задача поиска. Диаграмма связи задач. Преобразование непрерывной задачи оптимизации в задачу поиска (метод целочисленного кодирования). Кодирование дискретных задач оптимизации на примере задачи о ранце, задачи коммивояжера.
  3. Пространство поиска и ландшафты приспособленности. Одномутантные соседи конкретных строковых кодировок. Локальный и глобальный оптимумы. Методы «слепого» поиска. Эволюционные стратегии. Эволюционно-генетических алгоритмы. Принципы неодарвинизма, аналогии в эволюционно-генетических алгоритмах.
  4. Генетические алгоритмы и их основные свойства. Схема эволюционно-генетических алгоритмов. Репродукция (схемы скрещивания, кроссоверы, мутация), стратегии формирования следующего поколения популяции, схемы селекции.
    Уравнение жизни, рождения и смерти, уравнение экспоненциального роста высокоприспособленных особей.
    Алгоритмы селекции, реализующие принципы естественного отбора. Ститистические оценки этих алгоритмов.
  5. Особенности решения комбинаторных задач на примере задачи о ранце и задачи коммивояжера. Кодирование решений , операторы кроссовера и мутации, обработка ограничений.
    Причины, требующие масштабирования. Линейное динамическое масштабирование.
  6. Шаблоны сходства. Интерпретация шаблонов сходства в пространстве поиска. Статистические характеристики шаблонов сходства.
    Понятие разбиения. Конкурирующие шаблоны сходства, победитель. Статистическая и динамическая гипотезы строительных блоков. Коэффициент репродукции, рост числа примеров шаблонов сходства.
  7. Фундаментальная теорема эволюционно-генетических алгоритмов. Теорема о неявном параллелизме. Принцип минимальных алфавитов.
    Изменение пропорции аллелей во времени, оценки времени сходимости и захвата.
  8. Исследование эволюционно-генетических алгоритмов с помощью цепей Маркова. Основные понятия марковской цепи. Моделирование эволюционно-генетических алгоритмов при помощи цепи Маркова. Сходимость классического и элитарного эволюционно-генетических алгоритмов к оптимальному решению.
    Процесс генетического дрейфа. Оценка времени дрейфа.
  9. Выбор параметров эволюционно-генетических алгоритмов. Минимальный размер популяции. Nо free lunch теорема .

Лабораторный практикум

  1. Кодирование решений дискретных задач оптимизации.  Бинарное и другие способы кодирования. Понятие близости решений и соответствующих кодировок. Функции кодирования и декодирования. Определение и вычисление функции приспособленности.
  2. Основная схема эволюционно-генетических алгоритмов. Рассмотрение различных схем реализации операторов эволюционно-генетических алгоритмов.
  3. Применение эволюционно-генетических алгоритмов при решении задач дискретной оптимизации. Выбор операторов. Методы обработки ограничений. Определение и вычисление функции приспособленности.
  4. Подбор параметров для решения задач дискретной оптимизации при помощи эволюционно-генетических алгоритмов.

Литература

а) основная литература:

  1. Батищев, Д.И. Вычислительная сложность экстремальных задач переборного типа: Учебное пособие./ Батищев Д.И., Коган Д.И. – Н.Новгород, ННГУ, 1994.
  2. Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации: Учебное пособие. – Н.Новгород, изд-во ННГУ им. Н.И.Лобачевского, 2006. – 136с.
  3. Батищев Д.И., Костюков В.Е., Неймарк Е.А., Старостин Н.В. Решение дискретных задач с помощью эволюционно-генетических алгоритмов: Учебное пособие. - Нижний Новгород: Изд-во ННГУ им. Н.И. Лобачевского, 2011. - 199 с.
  4. Holland, J.H., Adaptation in Natural and Artificial Systems/ J.H. Holland - Ann Arbor: University of Michigan Press, 1975.

б) дополнительная литература:

  1. Батищев Д.И., Костюков В.Е., Старостин Н.В., Смирнов А.И. Популяционно-генетический подход к решению задач покрытия множества: Учебное пособие. Нижний Новгород: Изд-во ННГУ, 2004. 152 с.
  2. Сигал И.Х., Иванова А.П. Введение в прикладное дискретное программирование. Модели и вычислительные алгоритмы. М.: Физматлит, 2002. 229 с.
  3. Rudolph, G. Convergence Analysis of Canonical Genetic Algorithms./ G.Rudolph // IEEE Trans. on Neural Networks, special issue on Evolutionary Computation, vol. 5, no. 1, pages 96-101, Jan. 1994.
  4. Wolpert, D. No Free Lunch Theorems for Search/ D. Wolpert, W. Macready // Santa Fe Institute Technical Report 95-02-010, 1995

в) программное обеспечение и Интернет-ресурсы: http://iani.unn.ru/courses/mathematical/genetic_alg

Отчетность

  • Семестр 5: Экз