Решение оптимизационных задач на графах генетическими алгоритмами

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

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

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

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

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

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

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

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

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

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

Содержание

  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: Экз