Разработка и исследование генетических и эволюционных алгоритмов на графах

• Автор: Стасенко, Леонид Александрович
• Шифр специальности: 05.13.17
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Таганрог
• Количество страниц: 177 с. : ил

Содержание
Содержание
Введение

Глава 1. Анализ оптимизационных алгоритмов на графах.

1.1. Постановка оптимизационных задач на графах

1.2. Исследование алгоритмов разбиения и размещения графов.

1.3. Анализ алгоритмов определения пути коммивояжера.

1.4. Раскраска, построение клик и независимых подмножеств графов.

Выводы
Глава 2. Использование перспективных технологий эволюционного моделирования для решения задач на графах

2.1. Построение моделей эволюций.

2.2. Разработка концепции генетического поиска для графовых задач
2.3. Разработка и анализ поисковых методов для решения задач на графах
2.4. Построение новых архитектур генетического поиска
Выводы
Глава 3. Разработка комбинированных генетических алгоритмов для решения задач на графах
3.1. Построение генетических алгоритмов разбиения графов.
3.2. Разработка генетических алгоритмов размещения вершин графов.
3.3. Анализ генетического алгоритма определения пути коммивояжера.
3.4. Разработка генетического алгоритма раскраски графа, определение независимых подмножеств и клик графов.
3.5. Построение и анализ эволюционного алгоритма определения
паросочетаний графа.
Выводы .
Глава 4. Экспериментальные исследования разработанных алгоритмов
4.1, Основные задачи построения программного обеспечения для решения графовых задач.
4.2. Результаты экспериментальных исследований на стандартных и тестовых
задачах ..
Выводы
Заключение,.
Список использованной литературы


В процессе принятия и выбора решений на графах стремятся определять значения вектора управляемых переменных, принадлежащего области поиска ъ е Эг, таким образом, чтобы удовлетворить требования ЛПР. Стр. ВЫХОДНЫМИ переменными Уз и их предельно допустимыми по техническому заданию значениями у/ и у/, называемыми условиями работоспособности [-]. Область пространства управляемых переменных, в которой выполняются все условия работоспособности, называют областью работоспособности Эя. Область V может оказаться выпуклым или невыпуклым множеством, которое может быть односвязным или многосвязным. В случае невыпуклого множества Р его необходимо разбивать на выпуклые подмножества Р|,Р2,. Рк. I Э2 . I Эк=0. Область Р определяет множество всех работоспособных вариантов решений задачи, каждый из которых однозначно описывается вектором управляемых переменных Одна из проблем принятия решений в на графах- реализовать процедуру выбора из различных работоспособных вариантов одного или некоторого множества, предпочтительных с точки зрения ЛПР []. Принимая предварительное решение, ЛПР дихотомически разбивает область О на три подмножества 0 = УЕ)2УВ, • В подмножество включаются отобранные по заданному критерию варианты решения с ЦФ выше среднего значения, в - все имеющие ЦФ близкое к среднему значению, а в - все отклоненные варианты. Причем Эп 1 Э3 = 0, но на каждой итерации принятия решения ряд вариантов могут переходить из Э) в или Э3 и наоборот. Стр. D работоспособных вариантов и определение подмножеств Dl, D2 и D3. В-третьих, указывается принцип сравнения любых двух (множества) допустимых решений с тем, чтобы для них можно было выяснить, какое лучше в интересующем нас смысле. Как правило, этот способ сравнения задается с помощью критерия оптимальности. Критерий опГимальности представляет собой отображение (т. Обозначим это отображение, т. F: (1. R - множество неотрицательных вещественных чисел. Зная функцию F, можно задать два способа сравнения []. При первом способе решение шеМ' лучше, чем решение ш'е М', если F(m) F(m’). В этом случае говорят, что состоит в максимизации критерия F, т. F(m") = max F(m’) /ш'еМ1. Обычно требуемое правило сравнения указывается для задачи минимизации F(m) ->min, или для задачи максимизации F(m) ->max. Итак, на графах и гиперграфах записывается в виде кортежа длины три: <М, D, F>, где М-пространство решений; D-ограничения, выделяющие в М область допустимых решений М'сМ; F:M'-*R - критерий оптимизации. Выбор задачи заканчивается ее содержательной постановкой. Стр. Тогда оптимизационная задача должна удовлетворять двум основным требованиям: должно существовать как минимум два решения; надо знать, в каком смысле искомое решение должно быть наилучшим. Следовательно, математическая модель оптимизационной задачи состоит из трех составляющих: целевой функции, ограничений, граничных условий. Часто классификацию оптимизационных задач проводят по трем основным принципам: область применения; содержание задачи; класс математических моделей [-]. Классификацию математических моделей упрощенно можно провести: по элементам модели; по искомым переменным; по зависимостям, описывающим ЦФ, ограничениям и граничным условиям. При этом выделяют модели: детерминированные; случайные; непрерывные; дискретные; линейные и нелинейные. Комбинации элементов математических моделей приводят к различным классам оптимизационных задач. Наиболее простые - линейные оптимизационные задачи, однако, на практике чаще всего встречаются нелинейные. Наибольшее или наименьшее значение функции без учета того, где находится такое значение - внутри заданного интервала или на его границе, называют не экстремумом, а оптимумом. Оптимум - более общее понятие, чем экстремум. Экстремум есть не у всех функций, а в оптимизационных задачах на графах оптимум есть всегда. Оптимум может быть локальным и глобальным []. Глобальным максимумом (минимумом) называют такой максимум (минимум), который больше (меньше) всех остальных. Стр.