Применение генетических алгоритмов к решению задач дискретной оптимизации

Description

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