Читать онлайн «Улучшающий генетический алгоритм: Методические указания по курсу ''Генетические алгоритмы: теория и приложения решения оптимизационных задач''»

Нижегородский государственный университет им. Н. И. Лобачевского Факультет вычислительной математики и кибернетики Кафедра информатики и автоматизации научных исследований Методические указания «Улучшающий генетический алгоритм» по курсу «Генетические алгоритмы: теория и приложения решения оптимизационных задач» специальность «Прикладная информатика» Н. Новгород, 2008 УДК. 681. 3. 015 Методические указания «Улучшающий генетический алгоритм» по курсу «Генетические алгоритмы: теория и приложения решения оптимизационных задач» для студентов факультета ВМК специальности «Прикладная информатика». /Нижегородский государственный университет, 2008, 10 c. В методических указаниях излагается один из способов построения улучшающих алгоритмов с применением методов эволюционно-генетического поиска. В качестве примера приводится процедура построения алгоритма, осуществляющего оптимизацию k-разбиения графа. Методическое пособие подготовлено соискателем А. В. Филимоновым. Рецензент д. т. н. , проф. Д. И. Батищев. (М. Х. Прилуцкий?) Содержание Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 4 Принцип построения улучшающего ГА ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 4 Алгоритм оптимизации k-разбиения графа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6 Постановка задачи разбиения ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 6 Жадный улучшающий алгоритм... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 7 Генетический улучшающий алгоритм ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 8 Литература... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 10  Введение Класс задач, для которых не существует точных решающих алгоритмов с полиномиальной оценкой вычислительной сложности, очень обширен. Для решения таких задач, как правило, вводится понятие приемлемости решения и строятся алгоритмы, находящие решения, не являющиеся точными, но приемлемые с точки зрения исследователя. Часто такого рода методы носят характер улучшающих алгоритмов и сценарий получения решения следующий: строится некоторое начальное решение, затем это решение улучшается до тех пор, пока исследователь не сочтет решение приемлемым, или алгоритм не исчерпает свой ресурс по улучшению решения. Основная проблема такого рода эвристик, особенно основанных на жадном принципе, - трудности преодоления локальных экстремумов. Предлагается для преодоления такого рода трудностей и расширения области пространства поиска, которая потенциально может быть исcледована алгоритмом, интегрировать в улучшающий алгоритм элементы эволюционно-генетического поиска. Классический генетический алгоритм (ГА) подразумевает манипулирование так называемыми кодировками (генотипами).