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