Введение
1. Анализ алгоритмов решения задачи разбиения 4 Схемэва 15
1.1. Постановка задачи разбиения схем 15
1.2. Классификация методов и алгоритмов решения задачи разбиения 25
1.3. Выводы и рекомендации 29
2. Анализ и выбор моделей и алгоритмов решения задачи 30
2.1. Анализ и выбор математической модели 30
2.1.1. Виды математических моделей 30
2.1.2. Графовые модели 34
2.1.3. Модели на основе специальных графов 38
2.1.4. Гиперграфовые и ультраграфовые модели 38
2.2. Внутренняя и внешняя устойчивость 44
2.3. Анализ алгоритмов определения независимых и і» доминирующих подмножеств 48
2.3.1. Алгоритм полного перебора 48
2.3.2. Алгоритм систематического перебора 50
2.3.3 Последовательный алгоритм 52
2.3.4. Методы, основанные на логических произведениях 54
2.3.5. Векторный способ нахождения вершинного и реберного покрытий 55
2.4. Выводы и рекомендации 58
3. Разработка генетических алгоритмов выделения Ядер графа 59
3.1.Анализ существующих алгоритмов решения оптимизационных задач 59
3.1.1. Методы решения оптимизационных задач 59
3.1.2. Основные парадигмы генетических алгоритмов 60
3.1.3. Структура генетического алгоритма 70
3.2. Разработка итерационного алгоритма выделения экстремальных подмножеств 74
3.2.1. Алгоритм «Поиск в глубину» 74
3.2.2. Алгоритм «Поиск в глубину с отсечением» 75
3.3. Разработка простого генетического алгоритма выделения экстремальных подмножеств 78
3.3.1. Разработка методики кодирования 78
3.3.2. Подбор генетических операторов 81
3.3.3. Разработка структуры простого генетического алгоритма построения экстремальных подмножеств 87
3.4. Разработка модифицированного генетического алгоритма выделения независимых подмножеств в графе 91
3.4.1. Разработка структуры хромосом 91
3.4.2. Стратегия формирования начальной популяции 92
3.4.3. Разработка генетических операторов 92
3.4.4. Разработка схемы генетического поиска 95
3.5. Разработка эволюционного алгоритма выделения экстремальных подмножеств в графе 97
3.5.1. Алгоритм выделения доминирующих подмножеств 97
3.5.2. Алгоритм выделения независимых подмножеств 105
3.6. Теоретические оценки алгоритмов 110
3.7. Выводы и рекомендации 113
4. Экспериментальные исследования 115
4.1. Итерационный алгоритм нахождения экстремальных подмножеств 115
4.1.1. Анализ временной сложности алгоритма 115
4.1.2. Описание программы 116
4.1.3. Экспериментальные исследования 118
4.2. Простой генетический алгоритм нахождения экстремальных подмножеств 118
4.2.1. Описание интерфейса 118
4.2.2. Результаты экспериментальных исследований 121
4.2.3. Анализ временной сложности 123
4.3. Модифицированный генетический алгоритм выделения экстремальных подмножеств 125
4.3.1. Описание интерфейса 125
4.3.2. Экспериментальные исследования 128
4.4. Эволюционный алгоритм нахождения экстремальных подмножеств в графе 130
4.4.1. Описание интерфейса программы 130
4.4.2. Результаты экспериментальных исследований 138
4.5. Выводы и рекомендации 143
Заключение 145
Литература 146
Приложения 155
Приложение № 1 156
