Содержание к диссертации
Введение
Глава 1. Анализ оптимизационных алгоритмов на графах 10
1.1. Постановка оптимизационных задач на графах 10
1.2. Исследование алгоритмов разбиения и размещения графов 17
1.3. Анализ алгоритмов определения пути коммивояжера 27
1.4. Раскраска, построение клик и независимых подмножеств графов 30
Выводы 34
Глава 2. Использование перспективных технологий эволюционного моделирования для решения задач на графах 35
2.1. Построение моделей эволюции 35
2.2. Разработка концепции генетического поиска для графовых задач 44
2.3. Разработка и анализ поисковых методов для решения задач на графах 57
2.4. Построение новых архитектур генетического поиска 64
Выводы 78
Глава 3. Разработка комбинированных генетических алгоритмов для решения задач на графах 79
3.1. Построение генетических алгоритмов разбиения графов 79
3.2. Разработка генетических алгоритмов размещения вершин графов 97
3.3. Анализ генетического алгоритма определения пути коммивояжера 111
3.4. Разработка генетического алгоритма раскраски графа, определение независимых подмножеств и клик графов 121
3.5. Построение и анализ эволюционного алгоритма определения паросочетаний графа 128
Выводы 134
Глава 4. Экспериментальные исследования разработанных алгоритмов 135
4.1. Основные задачи построения программного обеспечения для решения графовых задач 135
4.2. Результаты экспериментальных исследований на стандартных и тестовых задачах : 140
Выводы 162
Заключение , 164
Список использованной литературы 166
Приложения 175
- Раскраска, построение клик и независимых подмножеств графов
- Разработка и анализ поисковых методов для решения задач на графах
- Разработка генетического алгоритма раскраски графа, определение независимых подмножеств и клик графов
- Результаты экспериментальных исследований на стандартных и тестовых задачах
Введение к работе
При решении современных задач науки и техники особое значение приобретают эффективные методы решения оптимизационных задач на графах и гиперграфах. Их использование позволяет создавать высоконадёжную аппаратуру в короткие сроки и при сравнительно низких затратах.
Разработка методов и алгоритмов для решения оптимизационных задач на графах осуществляется на протяжении ряда лет, являясь, по-прежнему, актуальной проблемой. Это связано, в первую очередь, с тем, что эти задачи являются NP-полными и NP-трудными. Поэтому затруднительна разработка универсальных методов и алгоритмов, позволяющих находить точное оптимальное решение за приемлемое время. Появление новых, более совершенных средств электронно-вычислительной техники, и, как следствие, увеличение их степени интеграции является причиной для разработки новых совершенных технологий решения задач на графах. Существует несколько подходов к решению NP - полных задач на графах [1-17].
К первому классу относятся методы, явным или неявным образом обеспечивающие возможность нахождения решения за экспоненциальное время работы. Это такие методы, как метод ветвей и границ, нелинейного программирования и их модификации. Ко второму классу относятся эвристические алгоритмы, позволяющие получать решения за приемлемое время. К третьему классу относятся алгоритмы случайно-направленного поиска. К четвертому классу относятся комбинированные алгоритмы.
Использование методов первого класса для решения практических задач неприемлемо. В этом случае трудоемкость задач на графах резко возрастает, и использовать алгоритмы с экспоненциальной временной сложностью становится невозможным из-за необходимости обработки огромных массивов информации. В этой связи становится необходимым модернизация структуры, как самих алгоритмов, так и основных стратегий, принципов и методов решения задач на графах.
Стр.3
Недостатки эвристических алгоритмов решения задач на графах заключаются в низком качестве решения. Поиск решения, которое может быть близко к локальному оптимуму, требует избыточное количество времени.
Алгоритмы случайно-направленного поиска обладают способностью находить более качественное решение за приемлемое время.
Комбинированные алгоритмы при незначительном увеличении времени позволяют получать локально оптимальный результат.
Одним из подходов создания комбинированных методов является использование технологии эволюционного моделирования. Она включает ряд новых концепций и стратегий. Например, «эволюция - поиск»; «поиск — эволюция»; «поиск - поиск - эволюция - эволюция»; «поиск - эволюция -поиск», «эволюция - поиск - эволюция» «эволюция — поиск - эволюция — поиск» и т.п. Они реализуются различными поисковыми и генетическими алгоритмами.
Основой технологии эволюционного моделирования, являются генетические алгоритмы. Генетические алгоритмы - эффективная оптимизационная технология, которую будем применять для решения различных задач на графах. Она основана на моделировании процессов селекции и генетических преобразований в биологии. Причем основой этой технологии является «выживание сильнейших», что выполняется путем исключения «неэффективных» элементов (альтернативных решений задач на графах) и оставления оптимальных или квазиоптимальных решений [18-38].
Большой вклад в разработку и исследование методов решения задач на графах и теорию эволюционного моделирования внесли Д.И.Батищев, Л.С.Берштейн, И.Л.Букатова, В.А.Горбатов, А.А.Зыков, В.В.Емельянов, В.М.Курейчик, А.Н.Мелихов, И.П.Норенков, Л.А.Растригин, К.Берж, Д.Гольдберг, Ж.Грефенстетте, Л.Дэвис, Т.Кормен, Н.Кристофидес, О.Оре, И.Чамберс, Ф. Харари, Д.Холланд, и многие другие.
Стр.4
Достоинства эволюционного моделирования, в сравнении с другими подходами к решению задач на графах, заключаются в том, что генетические алгоритмы начинают работать с несколькими начальными решениями, распараллеливая процесс, и позволяют частично решать проблему выхода из локальных оптимумов, при этом комбинируя, изменяя и наследуя элементы и ансамбли элементов качественных альтернативных решений [25,27,35].
В этой связи, разработка методов и алгоритмов, позволяющих найти приемлемое по качеству и по трудоёмкости решение задач на графах, является актуальной и важной проблемой.
ЦЕЛЬЮ ДИССЕРТАЦИОННОЙ РАБОТЫ является разработка эволюционных методов и генетических алгоритмов для решения графовых задач. Достижение указанной цели предполагает решение следующих основных задач:
Разработка и исследование алгоритмов анализа данных на основе генетического поиска.
Применение эволюционных принципов, методов и моделей для решения задач разбиения, размещения, раскраски, построения пути коммивояжера, определения независимых подмножеств, паросочетаний и клик графов.
Построение архитектур генетического поиска и модифицированных генетических операторов, ориентированных на решение оптимизационных графовых задач.
Для решения поставленных задач в диссертационной работе используются следующие методы: теория графов, множеств, алгоритмов, методология эволюционного моделирования и генетические алгоритмы.
НАУЧНАЯ НОВИЗНА диссертационной работы заключается в следующем:
Стр.5
разработаны принципы разбиения графов на части и размещение графов на плоскости на основе комбинации поисковых и генетических алгоритмов;
определена процедура построения «жадных» стратегий для решения оптимизационных задач на графах;
использованы концепции моделей синтетической теории эволюции для построения алгоритмов решения задач" на графах с полиномиальной временной сложностью.
Решение поставленных задач позволяет автору защищать следующие новые научные результаты:
Стратегии взаимодействия поисковых методов и эволюционного моделирования. Нестандартные архитектуры решения оптимизационных задач на графах.
Генетические алгоритмы разбиения и размещения графов с генетическими операторами на основе модифицированных поисковых методов.
Комбинированные методы и алгоритмы построения пути коммивояжера, определения независимых подмножеств, паросочетаний и клик графов, основанных на «жадных» стратегиях и эвристиках, позволяющие, в отличие от существующих методов, находить не одно, а некоторое множество эффективных решений.
ПРАКТИЧЕСКАЯ ЦЕННОСТЬ результатов диссертационной работы определяется созданием комплекса программ и алгоритмов для решения задач на графах, позволяющих использовать разработанные математические модели, стратегии, методы и эвристики, отвечающие конкретным конструкторским и технологическим задачам. Программы реализованы на языке C++ под WINDOWS. Проведенные экспериментальные исследования, показали преимущество комбинированных поисковых и генетических алгоритмов для решения оптимизационных задач на графах по сравнению с существующими
Стр.6
методами. Разработанные методы и алгоритмы решения графовых задач позволяют получать не одно, а набор оптимальных, или квазиоптимальных результатов. Время получения лучших результатов решения графовых задач соответствует полиномиальному времени, которого требуют итерационные алгоритмы.
РЕАЛИЗАЦИЯ РЕЗУЛЬТАТОВ РАБОТЫ. Основные теоретические и практические - результаты диссертационной работы использованы в госбюджетных работах, проводимых в Таганрогском государственном радиотехническом университете: грант РФФИ № 01-01-00044 «Эволюционное проектирование с адаптацией»; грант РФФИ на проведение фундаментальных исследований в области технических наук № 02-01-01275 «Разработка теории и принципов эволюционного проектирования на основе многоагентных подходов»; госбюджетная работа по заказу Минобразования РФ «Разработка теории и принципов построения интеллектуальных систем автоматизированного проектирования на основе эволюционной адаптации, нейросетевых моделей и методов принятия решений».
Материалы диссертации также использованы в учебном процессе на кафедре САПР в Таганрогском государственном радиотехническом университете в цикле практических занятий по курсам «Методы оптимизации, дискретная математика и теория алгоритмов».
АПРОБАЦИЯ основных теоретических и практических результатов работы. Результаты работы докладывались и обсуждались на научной международной научно-технической конференции «Интеллектуальные САПР» (г. Дивноморск, 2001, 2002 гг.), на международной конференции IEEE «Прикладные интеллектуальные системы» (г. Дивноморск, 2002г.), на научных семинарах Северо-Кавказкого научного центра высшей школы (г. Ростов-на-Дону, Таганрог, 2001, 2002 гг.), а также на научных семинарах Рос НИИ информационных технологий и автоматизации проектирования Минпромнауки России.
Стр.7
ПУБЛИКАЦИИ. Результаты диссертации отражены в 6 печатных работах.
СТРУКТУРА И ОБЪЁМ ДИССЕРТАЦИОННОЙ РАБОТЫ.
Диссертационная работа состоит из введения, четырёх глав, заключения, списка литературы и приложений. Работа содержит 175 стр., а также 84 рис., список литературы из 105 наименований, 2 стр. приложений и актов об использовании.
Во ВВЕДЕНИИ обоснована актуальность темы диссертационной работы, поставлена цель работы, дано общее описание выполненной работы.
В ПЕРВОЙ ГЛАВЕ сформулирована постановка оптимизационных задач на графах. Проанализированы способы определения временной сложности алгоритмов при решении задач на графах. Исследованы методы разбиения вершин графа на части с минимизацией количества внешних ребер и размещения графов на плоскости с минимизацией общей суммарной длины ребер графа. Описаны способы решения задач определения пути коммивояжера, раскраски, построения клик, независимых подмножеств и паросочетаний вершин и ребер графов. Определены временные сложности алгоритмов решения этих задач.
Во ВТОРОЙ ГЛАВЕ рассмотрены вопросы использования технологий генетического поиска для решения оптимизационных задач на графах. Проанализированы различные методы поиска при решении графовых задач. Построены такие поисковые алгоритмы разбиения и размещения, как дихотомии; на основе чисел Фибоначчи; поиска в глубину, ширину, с возвратом; метода «горизонта». Сформулированы стратегии комбинированного генетического и эвристического поиска решений. Разработаны новые архитектуры генетического поиска на основе модели синтетической эволюции. Построены модифицированные операторы селекции, кроссинговера, мутации, инверсии, транслокации, сегрегации, удаления и вставки, ориентированные на решение графовых задач и имеющие полиномиальную временную сложность. Это дает возможность распараллеливать процесс оптимизации, эффективно
Стр.8
управлять поиском, получать оптимальные и квазиоптимальные решения задач на графах.
В ТРЕТЬЕЙ ГЛАВЕ разработаны модифицированные алгоритмы агрегации фракталов для реализации «жадных» стратегий анализа графов с временной сложностью алгоритма (ВСА) 0(n ) (п - число входов алгоритма) для одной генерации. Приведены модифицированные алгоритмы генетического поиска для определения независимых и доминирующих подмножеств, клик и паросочетаний графа. Построена архитектура комбинированного поиска для устранения преждевременной сходимости при решении графовых задач. ВСА таких алгоритмов ориентировочно равна O(nlogn).
В ЧЕТВЕРТОЙ ГЛАВЕ описаны результаты экспериментальных исследований приведенных алгоритмов, приведены количественные и качественные оценки разработанных алгоритмов. Определены параметры генетических и поисковых процедур. Установлены оптимальные размеры популяций и вероятности применения генетических операторов. По результатам экспериментов уточнены оценки временной сложности алгоритмов. Определены оптимальные сочетания управляющих параметров разработанных алгоритмов при решении оптимизационных задач на графах. Произведено сравнение разработанных алгоритмов с существующими аналогами. Описаны структурные схемы алгоритмов, даны компоненты разработанного программного обеспечения.
В ЗАКЛЮЧЕНИИ изложены основные выводы и результаты диссертационной работы.
В приложении даны копии актов внедрения.
Стр.9
Раскраска, построение клик и независимых подмножеств графов
Если после этого получается NP-полная задача, то тем самым установлена трудность исходной задачи. Если для ОЗ имеется быстрый алгоритм, то и полученную из неё задачу разрешения можно решить быстро (надо просто сравнить ответ этого алгоритма с заданной границей). Поэтому, некоторые положения теории NP-полноты будем использовать и для исследования ОЗ на графах. На практике решить инженерную задачу часто намного труднее, чем проверить уже готовое решение, особенно если время работы ограничено. Понятие NP-полноты является важным средством классификации графовых задач, оно сводит вопрос о сложности данной задачи к общему (пусть и не решённому) вопросу о соотношении классов полиномиальных (Р) и NP.
Говоря неформально, задача Q сводится к задаче Q , если задачу Q можно решить для любого входа (например, числа вершин графа), считая известным решение задачи Q1 для какого-то другого входа. Например, задача размещения вершин графа в линейках с минимизацией суммарной длины ребер сводится к задаче разбиения графа на части с минимизацией суммарного количества внешних ребер. Если задача Q сводится к задаче Q , то любой алгоритм, решающий Q1, можно использовать для решения задачи Q, т.е. Q «не труднее» Q .
Например, к итерационным алгоритмам разбиения графа на части (размещения графа на плоскости) относятся: алгоритмы парных и групповых перестановок, релаксационные алгоритмы и алгоритмы моделирования отжига. При использовании итерационных алгоритмов сначала граф разбивают на определенное число частей произвольным или заданным образом, например с помощью последовательных алгоритмов. Затем по некоторым правилам делают перестановку вершин из одной части в другую для оптимизации заданного критерия. Далее процесс продолжается итерационно до получения локальных оптимумов. ВСА итерационных алгоритмов составляет ориентировочно 0(п2)-0(п4). К точным алгоритмам относятся различные виды полного перебора и методы ветвей и границ. Например, алгоритмы размещения вершин графа на плоскости, использующие метод ветвей и границ [49,51], состоят из следующих этапов. Сначала определяют нижнюю оценку размещения графа на плоскости с минимизацией суммарной длины ребер. Затем строят дерево решений, производят его ветвление по уровням, оценивают их и, отбрасывая .неперспективные, находят оптимальное решение. ВСА составляет ориентировочно 0(п )-0(п!).
К классу комбинированных алгоритмов разбиения (размещения) можно отнести различные смешанные алгоритмы. Например, совместный поисковый и точный алгоритм; алгоритм градиентный и групповых перестановок и т.д. ВСА здесь меняется от О(п) до 0(п!). Отметим, что такая классификация является условной. Так, например, случайный алгоритм может быть последовательным, итерационным, комбинированным и т.п.
Рассмотрим кратко основные существующие алгоритмы разбиения (размещения) графов и отметим их достоинства и недостатки. Сущность большинства из них заключается в выборе или построении некоторого начального разбиения (размещения) исходного графа или гиперграфа и последующего его улучшения с помощью итерационного, точного или комбинированного разбиения. При этом на каждой итерации осуществляется перестановка вершин или групп вершин, которая обеспечивает максимальное улучшение заданного критерия.
Комбинаторные методы [48] предназначены для поиска оптимального решения в некотором конечном множестве. В большинстве случаев они используют различные варианты сокращенного перебора, поскольку полный перебор в реальных задачах неосуществим из-за слишком большой их размерности. Алгоритмы, использующие . идеи метода ветвей и границ, основаны на последовательном разбиении множества вершин графа на подмножества и формировании оценок, позволяющих рассматривать только те подмножества, которые могут содержать решение задачи (т.е. отбрасываются заведомо нереальные варианты). Основной недостаток этих методов заключается в необходимости корректного выбора оценок, в противном случае (при неверном выборе) данный метод будет осуществлять полный перебор. Вычислительная сложность алгоритмов данного типа лежит в пределах от О (п2) до 0(п4).
Эвристические методы [1,48,50]. Для данного класса методов нет четкого математического обоснования, отсутствуют оценки точности решений и условия, гарантирующие получение локальных оптимумов. Данные методы зависят от класса и описания решаемой задачи. Эвристические методы на практике позволяют получать неплохие результаты, однако предсказать их поведение невозможно. Они могут использоваться как самостоятельно, так и совместно с другими методами, используя найденное с помощью эвристики решение в качестве исходного и дальнейшего улучшения его каким-либо другим, например, комбинаторным методом. Это позволяет сократить время решения задачи. Сложность эвристических алгоритмов может быть любой, но большинство известных алгоритмов имеют ВСА от О(п) до 0(п3).
Методы динамического программирования и дискретной оптимизации [39-41] при поиске новых решений используют информацию, полученную на предыдущих шагах (итерациях) применяемого алгоритма. Знание о получаемых решениях способствует формированию определенного поискового пространства, в котором определяются новые улучшенные решения. Это позволяет сократить время нахождения оптимума по сравнению с методами, реализующими полный перебор. Естественно, данные методы требуют больших ресурсов памяти для хранения промежуточных результатов и мощный процессор для обработки массивов данных. Отметим, что данные задачи эффективно решать на многопроцессорных ЭВМ. ВСА данного метода составляет в среднем 0(п ).
Для решения практических задач используются следующие алгоритмы разбиения графа на части: алгоритм Кернигана-Лина и его улучшенные эвристики [52,53]; алгоритм моделирования отжига [54]; алгоритм Федичио-Матеуса и его модификации [51-53]; алгоритм Лучио-Фабрицио и его улучшенные эвристики [51]; алгоритм Сааба и многие другие [54,55].
Некоторые из них используют эвристическую базу, что исключает непосредственную зависимость от значения целевой функции в процессе решения (а, следовательно, и попадание в локальный оптимум, что в задачах такого класса при стандартном подходе случается довольно часто из-за дискретности целевой функции и переменных) [54]. Сравнительная оценка нескольких из вышеприведенных алгоритмов показывает, что алгоритмы, использующие эвристику, дают приблизительно тот же результат, затрачивая при этом на каждую итерацию значительно меньше (до 10 раз) времени [54]. Это связано с тем, что многие эвристические алгоритмы используют для решения не полный перебор, а перебор, направленный на улучшение целевой функции, отбрасывая при этом множество «неперспективных» решений.
Разработка и анализ поисковых методов для решения задач на графах
В ГА предварительно анализируется множество входных параметров оптимизационной задачи на графах и находится некоторое множество альтернативных решений, которое называется популяцией. Каждое решение кодируется как последовательность конечной длины в некотором алфавите. Отметим, что для решения оптимизационных задач на графах наиболее приемлемыми являются двоичный, троичный, десятичный и символьный алфавиты. ГА работает до тех пор, пока не будет получено решение заданного качества или не будет выполнено заданное количество генераций, или на некоторой генерации не возникнет преждевременная сходимость, когда найден локальный оптимум. В отличие от других методов оптимизации ГА, как правило, анализируют различные области пространства решений одновременно и более приспособлены к .нахождению новых областей с лучшими значениями ЦФ.
Процесс эволюции основан на анализе начальной популяции и ГА начинает свою работу с создания исходного множества альтернативных решений. Затем эти «родительские» решения создают «потомков» путем случайных, направленных и комбинированных преобразований. После этого оценивается эффективность каждого альтернативного решения и они подвергаются селекции. Во всех рассмотренных моделях эволюции используется принцип «выживания сильнейших», т.е. наименее приспособленные решения устраняются, а лучшие решения переходят в следующую генерацию. Затем процесс повторяется вновь [25,27,28].
При решении ОЗ на графах ГА дают много преимуществ. Одно из них — это приспособление к изменяющейся окружающей среде. Другое преимущество ГА для решения задач состоит в способности быстрой генерации достаточно хороших альтернативных решений [27].
Предлагается модифицированный ГА, состоящий из трех основных блоков. Первый блок назовем препроцессором. Здесь производится создание одной или некоторого множества начальных популяций. Второй блок состоит из четырех этапов: выбор представления решения; разработка операторов случайных, направленных и комбинированных изменений; определение законов выживания решения; рекомбинация. Третий блок назовем постпроцессором. Здесь реализуются принципы эволюционной адаптации к внешней среде (лицу, принимающему решения) и самоорганизации. Схема такого поиска показана на рис.2.7. Преимущества горизонтально организованной архитектуры ГП, состоит в том, что в ней все уровни связаны с уровнем внешней среды и могут общаться между собой. Принцип целостности. В генетических алгоритмах значение целевой функции альтернативного решения не сводится к сумме целевых функций частичных решений. Принцип дополнительности. При решении 03 на графах в ГА возникает необходимость использования различных не совместимых и взаимодополняющих моделей эволюции и генетических операторов. Принцип неточности. При росте сложности анализируемой задачи уменьшается возможность построения точной модели. Принцип управления неопределенностью. Необходимо вводить различные виды неопределенности в генетические алгоритмы. Принцип соответствия. Язык описания исходной задачи должен соответствовать наличию имеющейся о ней информации. Принцип разнообразия путей развития. Реализация ГА многовариантна и альтернативна. Существует много путей эволюции. Основная задача выбрать путь, приводящий к получению оптимального решения. Принцип единства и противоположности порядка и хаоса. «Хаос не только разрушителен, но и конструктивен», т.е. в хаосе области допустимых решений обязательно содержится порядок, определяющий искомое решение. Принцип совместимости и разделительности. Процесс эволюции носит поступательный, пульсирующий или комбинированный характер. Поэтому модель синтетической эволюции должна сочетать все эти принципы. Принцип иерархичности. ГА могут надстраиваться сверху вниз и снизу вверх. Принцип «Бритвы Оккама». Нежелательно увеличивать сложность архитектуры ГА без необходимости. Принцип спонтанного возникновения Пригожина. ГА позволяют спонтанно генерировать наборы альтернативных решений, среди которых может возникнуть оптимальное. Принцип гомеостаза. ГА конструируются таким образом, чтобы любое полученное альтернативное решение не выходило из области допустимых. Операторы в ГА должны позволять получать реальные решения. Наиболее известным является простой генетический алгоритм (ПГА). Он состоит из трех основных блоков (операторов) [27]: селекции (репродукции), кроссинговера и мутации. Приведем некоторые понятия и определения из теории ГА [21-38,65-67]. Все ГА работают на основе начальной информации, в качестве которой выступает популяция альтернативных решений Р. Популяция Р = {pl,P2,...,P„...PNp\ есть множество элементов Pi. Здесь Np - размер популяции.
Каждый элемент этой популяции Pi, как правило, представляет собой одну или несколько хромосом или особей, или индивидуальностей (альтернативных упорядоченных или неупорядоченных решений). Хромосомы состоят из генов (элементы, части закодированного решения), и позиции генов в хромосоме называются локус для одной позиции, то есть ген - подэлемент (элемент в хромосоме), локус - позиция в хромосоме, аллель -функциональное значение гена. Гены могут .иметь числовые или функциональные значения. Элементы в ГА часто называют родителями. Родители выбираются из популяции на основе заданных правил, а затем смешиваются (скрещиваются) для производства «детей» (потомков). Дети и родители создают новую популяцию. Генерация ГА, то есть процесс реализации одной итерации алгоритма, называется поколением.
Разработка генетического алгоритма раскраски графа, определение независимых подмножеств и клик графов
Заметим, что предложенная схема ГП позволяет варьировать размер популяции, менять модели эволюции от генерации к генерации, быстрее находить локально-оптимальные результаты, что позволяет частично предотвращать сходимость алгоритма в задачах разбиения. Это связано с использованием различных моделей эволюции, параллельной обработкой множества альтернативных решений. Периодически в каждой итерации ГА можно проводить различные изменения в перспективных, неперспективных и в других решениях. Можно предложить большое число аналогичных схем ГП для решения задач разбиения [26,75].
Отметим, что для получения качественных результатов основные ГА для решения комбинаторно-логических задач на графах предлагается строить на общей простой основе согласно принципу «бритвы Оккама» [64]. Для этого определяется простой общий строительный блок (СБ), на основе которого конструируется топология архитектуры ГП. В случае необходимости СБ достраивается, изменяется, входит в сложные иерархические архитектуры конечным числом способов, по нескольким определенным алгоритмам. Сложные архитектуры ГП имеют инвариантное строение, т.е они могут собираться из универсальных СБ, которые повторяются в различных масштабах.
В 1980 г. Бенуа Мандельброт определил, что различные системы могут строиться на основе принципов фрактальной геометрии [76,77]. Фрактальные объекты самоподобны, т.е. их вид не претерпевает существенных изменений при изменении их геометрических масштабов. Множества, имеющие такую структуру, считаются обладающими геометрической (масштабной) универсальностью [76-81]. Процессы, создающие такие структуры, это процессы с обратной связью с большим числом итераций, когда одна и та же операция выполняется снова и снова, аналогично моделям эволюции. Объекты такого типа называются фрактальными множествами (ФМ). Стандартными, классическими ФМ считаются множества Кантора (МК) [79]. Такие множества обладают геометрической инвариантностью и называются «множества средних третей». Построение МК выполняется следующим образом. Отрезок единичной длины [0,1] делится на три равные части и средняя из них - интервал [1/3, 2/3] вырезается. Далее все происходит аналогично с каждым оставшимся из отрезков. Получаем последовательность, отрезков все убывающей длины. На первом этапе это один отрезок, на втором - два, на третьем — 4 и т.д., на k-том -2к. При к— оо имеем множество точек, называемое МК. Суммарная длина всех вырезанных отрезков равна 1 [77-79].
В [4,26,82] описан ОК на основе множества Кантора (ОКМК). Приведем модификацию данного оператора и покажем его работу на примере. Пусть заданы две хромосомы Рь Р2. Согласно построению МК в Pi, Р2 вырежем отрезки между [1/3,2/3] и произведем перестановку соответствующих генов. Модификацией ОММК [26,82], является ГО заключающейся в перестановке генов, находящихся между точками разреза. Например: Отметим, что можно построить большое число модификаций ОММК. Идеи ФМ автор использовал для построения всех ГО для решения ОЗ разбиения графов на части. Эффективность ГО определяется выживанием хромосом с лучшей ЦФ в следующих генерациях. В [78] рассмотрен механизм агрегации (DLA), описывающий создание фракталов. Например, пусть при разбиении графа на части задан кластер (объект максимальной связности, в графе - максимально связанное подмножество вершин или клика), растущий следующим образом: с течением времени к нему присоединяется некоторая вершина согласно значению ЦФ. Агрегация вершин графа, протекающая в условиях случайного движения, это и есть модель стандартной DLA [78]. Рассмотрим алгоритм разбиения графов на части на основе модифицированной агрегации фракталов. Механизм разбиения графа в отличие от [82,83] основан на восьми принципах: существенная зависимость от начальных условий; «Бритвы Оккама»; гомеостаза; использование различных моделей эволюции; построение кластеров (массивов, определенным образом связанных между собой вершин графа); факторизации кластеров, т.е. уменьшение размерности графа путем представления кластеров в виде новых объединенных вершин графа; DLA, т.е. агрегация, протекающая в условиях случайного, направленного и комбинированного присоединения вершин графа к кластерам; иерархичности.
Такой механизм является открытым, т.е. количество используемых принципов можно варьировать. Опишем теперь этот процесс подробнее. Существенная зависимость от начальных условий предполагает постоянный анализ исходного разбиения графа для выбора наилучшего. Усложнение схемы поиска нежелательно, необходимо использовать различные комбинации простейших строительных блоков. Любое полученное альтернативное решение не должно выходить из области допустимых решений задачи разбиения. Процесс создания кластеров основан на идеях построения минимальных и квазиминимальных массивов в графе [49,51,82]. В работах [3-5,49,51] введено понятие кластера в графе G=(X,U). Кластер - это часть графа ФсЮ, причем Ф=(Хі,иі), XIQX, UiCjU. Вершины кластера соединены внутренними ребрами с остальными вершинами Х\Х] графа G. Внешние ребра не входят в подмножество ребер кластеров. Мощность подмножества внешних ребер кластера обозначим Кластер Ф; называется минимальным, если для любого другого кластера Ф} Фj сФ; выполняется условие f) fj [51]. Другими словами, удаление произвольных вершин из ФІ (ФДХт) приводит к новому кластеру с большим числом внешних ребер. По определению будем считать: где 8 - коэффициент, определяющий на какую величину можно увеличить число внешних ребер в минимальном кластере ФІ. ОН определяется в процессе анализа графа, на основе решения ЛПР или ЭС (в среднем 8=0,1,2,..., 10). На рис.3.2,а показан КМ на три вершины с fi=6. Соответственно на рис.3.2,б показан простой кластер с f 2= 11. На рис.3.3,а показан КМ на две вершины с f3=3. При присоединении к этому КМ вершины xg получим квазиминимальньщ кластер (ККМ) на три вершины с =5 (рис.3.3,6). В этом случае величина є=1. Построение КМ и ККМ связано с выделением почти всех подмножеств множества X, а оно составляет 2П, если Х=п. В этой связи продолжаются разрабатываться различные эвристики выделения набора простых кластеров, КМ и ККМ. Эти эвристики основаны на теоремах о минимальных массивах в графах [51,82,83] и принципах построения ККМ.
Результаты экспериментальных исследований на стандартных и тестовых задачах
Кроме того, были проведены исследования зависимостей ЦФ и времени решения от вероятности применения ОК. На рис.4.26 и рис.4.27 приведены графики зависимости значения ЦФ и времени решения от вероятности применения ОК.
Алгоритм, реализованный в работе, определяет раскраску графа, близкую к оптимальной, за приемлемое время при следующих значениях параметров генетического алгоритма: число поколений — 100; размер популяции — 100; вероятность применения ОК - (30 - 50) %; вероятность применения ОМ - 60%; количество итераций для ОК и ОМ - 50 и 30. Были проведены экспериментальные исследования для определения зависимости времени работы и значения ЦФ генетического алгоритма раскраски графа от числа вершин, при оптимальных значениях параметров. Получена зависимость времени решения от числа вершин графа. Даны сравнительные характеристики для работы генетического алгоритма: средний процент улучшения целевой функции, при разных размерах графа; качества применения генетического алгоритма и алгоритма случайных перестановок. Результаты решения тестовых задач раскраски графа приведены в табл. 4.10.
Для получения показателей работы генетического алгоритма были найдены средние значения ЦФ и времени решения для отдельных графов, а затем средние значения этих параметров по всем графам (при одинаковом числе вершин). На рис.4.27. приведена диаграмма сравнения зависимости результатов, полученных «жадным» и генетическим алгоритмами. Из рисунка видно, что ГА имеет преимущества по качеству решения задачи. Реализация комбинированных генетических алгоритмов при разбиении графов на части показала преимущество разработанных алгоритмов по сравнению с простыми генетическими и другими классическими методами. Управление процессом генетического поиска при разбиении позволяет находить оптимальные параметры. Применение совместных моделей эволюции, различных методов поиска и модифицированных генетических операторов позволяет повысить качество и уменьшить время размещения вершин графов с минимизацией суммарной длины ребер. Применение нестандартных архитектур генетического поиска позволяет эффективно решать задачи определения пути коммивояжера, выделения клик, построения независимых подмножеств и раскраски графов. Произведены экспериментальные исследования поведения целевой функции в зависимости от размера популяции. Определён квазиоптимальный размер популяции обеспечивающий решение задач на графах с высоким качеством. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов задач на графах. Проведенные комплексные исследования позволили найти оптимальные параметры управления генетическим поиском. Это позволило улучшить работу алгоритмов по сравнению с известными методами. Улучшение составило по качеству от 10% до 25%, в зависимости от вида задач на графах. Основные результаты работы сформулированы следующим образом. 1. Сформулирована постановка оптимизационных задач на графах. Проанализированы способы определения временной сложности алгоритмов решения задач на графах. На основе анализа существующих методов предлагается использовать перспективную технологию эволюционного моделирования, генетического поиска и их различные модификации для решения задач на графах. 2. Приведены две новые стратегии взаимодействия поисковых методов и эволюционного моделирования для решения задач на графах. Показана возможность использования модели модифицированной синтетической эволюции для построения новых архитектур генетического поиска. 3. Разработаны принципы поисковых и генетических методов для разбиения графа на части. Приведены новые комбинированные алгоритмы размещения графа на плоскости и в линейке с полиномиальной временной сложностью. Разработаны «жадные» стратегии и эвристики эффективного решения задачи определения пути коммивояжера, позволяющие получать набор локально-оптимальных решений. 4. Предложены новые генетические операторы, использующие методы дихотомии, горизонта, поиска в глубину и ширину для решения раскраски графа, определение независимых подмножеств и клик графов. Это позволяет расширить область поиска решений без увеличения времени работы алгоритмов и сократить преждевременную сходимость алгоритмов. 5. Разработаны новые эвристики определения максимальных паросочетаний в двудольных графах. Использование принципов агрегации фракталов и поисковых методов позволяют получать набор максимальных паросочетаний за время, сопоставимое с реализацией последовательных алгоритмов. 6. Произведены экспериментальные исследования поведения целевой функции в зависимости от размера популяции. Определён квазиоптимальный размер популяции, обеспечивающий решение задач на графах с высоким качеством. 7. Проведенные серии тестов и экспериментов позволили уточнить теоретические оценки временной сложности алгоритмов задач на графах. Проведенные комплексные исследования позволили найти оптимальные параметры управления генетическим поиском. Это позволило улучшить работу алгоритмов по сравнению с известными методами. Улучшение составило по качеству от 10% до 25%, в зависимости от вида задач на графах.
