Батищев Д.И., Неймарк Е.А., Старостин Н.В. Применение генетических алгоритмов к решению задач дискретной оптимизации

Учебное пособие. — Нижний Новгород: Нижегородский государственный университет им. Н.И. Лобачевского (ННГУ), 2007. — 85 с.Учебно-методический материал по программе повышения квалификации «Информационные технологии и компьютерное моделирование в прикладной математике».
Излагаются основы новой информационной технологии, позволяющей сводить классические задачи дискретной оптимизации, такие как комбинаторные задачи о ранце, коммивояжере, покрытии и разбиении, к задаче поиска на дискретном множестве кодировок. Рассматриваются основные принципы, типовые структуры и механизмы предлагаемого популяционно-генетического подхода к решению задач поиска с помощью генетических методов. Описаны основы генетического поиска и проанализированы математические модели генетических операторов кроссовера для разных типов представлений (кодировок). Приведены конкретные примеры, в которых большое
внимание уделяется вычислительной реализации генетических методов.
Учебное пособие предназначено для преподавателей, аспирантов и специалистов, связанных с решением задач дискретной оптимизации. Также учебное пособие будет полезно студентам факультета вычислительной математики и кибернетики, изучающим курсы: «Методы и модели принятия решений» (общий курс по специальности «Прикладная информатика») и «Популяционно-генетический подход к решению экстремальных задач» (спецкурс по специальности «Прикладная математика и информатика»).Сведение комбинаторных задач дискретной.
Оптимизации к задачам поиска.
Постановки задач дискретной оптимизации.
Метод исчерпывающего перебора и понятие задачи переборного типа.
Оценка трудности задач дискретной оптимизации.
Задача поиска и ее абстрактная модель.
Бинарное представление дискретных решений с помощью двоичных чисел и кодов грея.
Небинарное (N-арное) представление дискретных решений.
Примеры экстремальных комбинаторных задач.
Понятие окрестности решения для задач комбинаторного типа.
Методы обработки ограничений.
Основы генетического поиска.
Интерпретация экстремальной задачи поиска и операторов генетического алгоритма с помощью понятий популяционной генетики.
Обобщенная структура генетического алгоритма.
Операторы генетического алгоритма, не зависящие от типа представления.
Классические генетические операторы кроссовера.
Классические генетические операторы мутации.
Операторы кроссовера и мутации для порядкового представления.