6.2.  Генетические алгоритмы разбиения графов

Одной из важнейших оптимизационных задач является разбиение графа на заданное или произвольное число частей [159, 160]. Задача разбиения графа на части имеет много практических применений. Она используется при проектировании устройств автоматики и вычислительной техники, создании систем управления, компьютерных и инженерных сетей, а также при решении различных задач ИИ. Отметим, что задача разбиения графа относится к классу NP-полных проблем, т. е. не существует эффективных алгоритмов ее решения с полиномиальной временной сложностью.

В полиномиальных алгоритмах временная сложность составляет О(п), 0(п2), 0(п3),... Для экспоненциальных алгоритмов (NP) временная сложность алгоритма составляет О (и11), 0(n2n), 0(п3п),.... Класс NP-полных задач включает такие задачи, для которых не найдены полиномиальные алгоритмы, однако и не доказано, что их не существует. Для рассмотрения вопроса о NP-полноте оптимизационной задачи их преобразуют в задачу разрешения. Обычно в качестве такой задачи рассматривают проверку, является ли некоторое число верхней или нижней границей для оптимизируемой величины. Если для оптимизационной задачи имеется быстрый алгоритм, то и полученную из нее задачу разрешения можно решать быстро. Для этого надо сравнить ответ этого алгоритма с заданной границей. Говорят, что алгоритм решает оптимизационную задачу за время 0(Т(п)), если на входных данных длины п алгоритм работает время О(Т(п)) [161]. Отметим, что время работы алгоритма Т(п) = Ѳ(п3) означает, что найдутся такие константы сі, > 0 и такое число по, что сіп3 ^ Т(п) ^ при всех п ^ по. Эта запись включает две оценки: верхнюю и нижнюю. Следуя [161], для любых двух функций f(n) и д(п) свойство f(n) — В(д(п)) выполнено, когдаf(n) = 0(д(п)). Это выражение является нижней границей, если найдутся такая константа с > 0 и по, что 0 ^ f(n) ^ с(дп) для всех п ^ по. Выражение f(n) = Щд(п)) — верхняя граница, если найдутся с > 0 и по, что 0 ^ сд(п) ^ /(п) для всех п ^ 'щ. В этой связи разрабатываются различные эвристики, основанные на идеях по с л е д овате льных и итерационных алгоритмов.

В [118] дана классификация существующих методов разбиения графа на части. При решении оптимизационной задачи большой размерности наибольший интерес, с точки зрения реализации, представляют последовательные (конструктивно-начальные) и итерационные эвристические методы. Временная сложность таких методов лежит в интервале О(п) — 0(п3), где п — число вершин графа. В некоторых случаях для разбиения графа могут быть использованы методы случайного поиска, но они не гарантируют получения локального оптимума за конечное число шагов. В настоящее время для решения задач разбиения графов широкое применение получили методы генетического поиска [16-19,91,92]. Эти методы используют ЭМ и критерии типа «выживания сильнейших» для получения оптимальных решений. Опишем модифицированные ГА с управлением процессом поиска на основе синергетических принципов и адаптации для разбиения графа на подграфы. Они отличаются применением нетрадиционных архитектур генетте ского поиска, а также генетте ской оптимизации, ориентированных на использование знаний о решаемых задачах.

Сформулируем постановку задачи разбиения графа на заданное или произвольное число частей. Пусть задан граф G = (X, Е, W), где X представляет множество вершин графа, Е — множество ребер, a W — общий суммарный вес вершин. Вес вершины соответствует интегральной оценке, в которую могут входить различные конструкторско-технологические ограничения на исследуемую модель, причем значения ѵоі Е W не превышают некоторой пороговой величины.

Пусть В = {Ві, В2,..., Bs} — множество разбиений графа G на части Ві, В2,..., Bs такие, что В± П В2 П ... П Bs = 0, и В± U В2 U ... U Bs = = В. Тогда задача разбиения графа G на части заключается в получении разбиения Ві Е I?, удовлетворяющего трем условиям и ограничениям:

Целевая функция для разбиения графа G запишется так:

где Kij — число связей между частями Ві и Bj при разбиении графа G на части; s — количество частей в разбиении; К — суммарное количество ребер при разбиении графа на части.

Стандартная задача разбиения заключается в минимизации К (К —» —» іиіп). Минимизация К при разбиении графа на части позволяет косвенно

учитывать многие критерии и конструкторско-технологические ограничения исследуемой модели при решении оптимизационной задачи. Рассмотрим задачу разбиения графа G с минимизацией К. Следовательно, задача разбиения состоит в отыскании такого разбиения Ві из множества возможных разбиений В некоторого графа или гиперграфа G, при котором минимизируется (либо максимизируется) некоторая величина К, являющаяся ЦФ разбиения, и учитываются все поставленные в задаче ограничения и граничные условия, если они существуют.

Разбиение графа относится к задачам дискретной условной оптимизации из-за прерывности ее ЦФ и наличия множества ограничений на переменные. Количество методов решения задач условной оптимизации достаточно велико, хотя эффективные алгоритмы известны лишь для специальных классов задач, таких, как задачи линейного, квадратичного или выпуклого программирования; наиболее распространены для разбиения графов симплекс-метод и метод нелинейного программирования (метод штрафных и барьерных функций) [159]. Однако применительно к задаче разбиения большинство из вышеприведенных методов не может быть использовано в связи с ее дискретностью, которая приводит к существенному росту трудностей при поиске оптимума. Поэтому данные задачи выделяют в особый класс оптимизационных комбинаторных задач на графах. В задачах такого класса общее число вариантов решения равно числу перестановок из п вершин графов, т. е. Сп = п!, а с учетом ограничений на формирование подмножеств (частей графа в задаче разбиения) — числу сочетаний из п вершин по т частей, т. е.:

Из вышесказанного следует, что решение задачи разбиения графа на основе полного перебора затруднительно из-за экспоненциальной сложности процесса. В этой связи разрабатываются различные эвристики решения данных задач. К ним относятся итерационные методы парных и групповых перестановок, методы последовательного приближения, релаксации, поиска в глубину и ширину, направленного перебора и др. В последнее время появились эвристики, использующие различные методы случайности. Это методы ЭМ, отжига, генетического поиска и их модификации. Все они в каком-то смысле основаны на анализе и переборе вариантов решения, однако различаются по технологии и принципам реализации.

Комбинаторные методы предназначены для поиска оптимального решения на некотором конечном множестве. В большинстве случаев они используют различные варианты сокращенного перебора, поскольку полный перебор в реальных задачах неосуществим из-за слишком большой размерности. Наиболее распространен для разбиения графов небольшой размерности метод ветвей и границ и его модификации. Эти методы основаны на идее последовательного разбиения множества на подмножества и формировании оценок, позволяющих рассматривать только те подмножества, которые могут содержать решение задачи (т. е. отбрасываются заведомо плохие ва-

рианты). Основной недостаток этих методов заключается в необходимости корректного выбора оценок, в противном случае (при неверном выборе) данный метод будет осуществлять полный перебор. Временная сложность алгоритмов данного типа лежит в пределах от 0(п3) до 0(п5).

В основе эвристических методов лежат нечеткие логические рассуждения. Данные методы не гарантируют нахождение оптимального решения и сильно зависят от класса и описания решаемой задачи. Эвристические методы на практике позволяют получать неплохие результаты, однако предсказать их поведение невозможно. Они могут использоваться как самостоятельно, так и совместно с другими. Это позволяет сокращать время работы. Временная сложность алгоритма в них может быть любой, но большинство известных алгоритмов имеют сложность от 0(п) до 0(п2).

Методы динамического программирования и дискретной оптимизации при поиске новых решений используют информацию, полученную на предыдущих шагах (итерациях) применяемого алгоритма [112, 113]. Знание о получаемых решениях способствует формированию определенного поискового пространства, в котором будет производиться нахождение новых улучшенных решений. Это позволяет сократить время нахождения оптимума по сравнению с методами, реализующими полный перебор. Естественно, данные методы требуют больших ресурсов памяти для хранения промежуточных результатов и для обработки массивов данных. Временная сложность алгоритма для данного метода составляет в среднем 0(п2).

Сущность большинства алгоритмов разбиения графов заключается в выборе некоторого начального разбиения исходного графа и последующего его улучшения с помощью итерационного, парного или группового обмена вершин из различных частей разбиения. При этом для каждой итерации осуществляется перестановка таких вершин, которая обеспечивает максимальное уменьшение числа связей между частями разбиения графа или минимальное приращение числа внешних ребер. Среди наиболее известных алгоритмов разбиения графа на части отметим следующие [159-166]:

•    А. Мелихова и др.; В. Кернигана, С. Лина и их улучшенные эвристики;

•    формирования минимальных массивов;

•    моделирования отжига;

•    С. Фидучео, Р. Матеусса и их модификации;

•    матричные, списковые и фреймовые;

•    случайных назначений;

•    эволюционного моделирования.

Сравнительная оценка существующих методов показывает, что алгоритмы, использующие высокоэффективную эвристику, дают приблизительно тот же результат, затрачивая при этом на каждую генерацию значительно меньше (до 10 раз) времени. Это связано с тем, что многие эвристики используют для решения не полный перебор, а направленный на улучшение ЦФ, отбрасывая множество заведомо неперспективных решений. Таким преимуществом обладают ГА, базирующиеся на методах ЭМ. Практика показывает, что ГА, в основном, дают преимущество на больших популяциях — более 1000 вершин в задаче разбиения. При уменьшении коли

чества элементов возрастает риск преждевременной сходимости ГА, что является прототипом локального оптимума в градиентных методах поиска решения.

Приведем краткое описание известных на сегодняшний день алгоритмов, использующих ту или иную эвристическую базу. Одними из популярных алгоритмов разбиения графа G = (X, U) на части являются итерационные алгоритмы, требующие для своей работы некоторого начального разбиения [160]. Они довольно чувствительны к начальному разбиению, что, в основном, сказывается на времени работы алгоритма. Кроме того, они часто попадают в локальный оптимум, когда размер графа велик (п > 1000). Один из путей преодоления этого недостатка состоит в группировке сильно связанных вершин в кластеры и в дальнейшем сборе этих кластеров в заданные части разбиения, а также использование фрактальных множеств для группирования сильно связанных вершин [165]. Итерационный эвристический алгоритм начинается со случайного разбиения и затем применяет парный обмен между двумя подмножествами, улучшая начальное решение путем многократной перестановки вершин. Разработано много модификаций этого подхода для того, чтобы алгоритм смог работать с гиперграфами, уменьшив временную сложность алгоритма до 0(п) для графов специального вида [160, 163].

Существенным преимуществом ГА является то, что они могут работать в любом классе задач, связанных с графами. Здесь важно только правильно представить постановку задачи в генетической форме, чтобы верно отобразить поисковое пространство ЦФ. Для этого поставленная задача анализируется с точки зрения применяемых критериев оптимальности и использования того или иного ГА, что в свою очередь определяет закодированную форму представления решений задачи.

Построим схему разбиения графа на части на основе генетического поиска. Такая схема дана на рис. 6.1. Здесь в первом блоке строится текущая (начальная) популяция решений, т. е. определяется заданное подмножество Ві, І?2, • • •, Bk (к <С s). На построение популяции оказывает влияние внешняя среда в виде ЛПР или ЭС. Отметим, что такое подмножество решений может быть получено случайным, направленным или случайно- направленным методами.

При наличии большого количества элементов наиболее предпочтительными будут конструктивные, итерационные, случайные и поисковые алгоритмы для получения текущей популяции. В качестве ЦФ выберем К (выражение (6.2)). В некоторых исследованиях, например, в [173], предлагается при решении задачи разбиения графа на части не минимизировать К (число связей между частями разбиения), а максимизировать количество связей (критерий А) внутри частей разбиения. Известно, что критерии К и А являются взаимообратными, т. е. минимизация К максимизирует А и наоборот. Для каждого элемента текущей популяции в блоке 2 вычисляется К и определяется Кср — среднее значение ЦФ на данной популяции (рис. 6.1). Блок 3 осуществляет сортировку популяции на основе ЦФ.

Здесь могут быть применены все существующие методы сортировки [164]. Сначала расставляются элементы с наименьшим значением К, затем с наименьшим значением из оставшихся и так далее по возрастанию. Блок 4 выполняет селекцию популяции для получения родительских пар. Селекция выполняется одним из методов, описанных выше. Блок 5 осуществляет реализацию генетических операторов и их модификаций. Блок 6 собирает и анализирует неперспективные решения задачи разбиения. Блок 7 реализует стратегии адаптации и на основе обратных связей выбирает модель эволюции, а также порядок использования и применения различных алгоритмов генетической оптимизации. В восьмом блоке осуществляется построение новой популяции решений. Девятый блок позволяет управлять процессом поиска с помощью информирующих обратных связей. Далее для каждой хромосомы из новой популяции вычисляется К, и выживают те элементы из старой и новой популяции, у которых К ^ Кср. При этом в стандартном случае количество элементов в новой популяции не должно превышать число элементов в старой популяции.

Предложенная схема генетического поиска позволяет варьировать размер популяции от генерации к генерации, что позволяет частично предотвращать преждевременную сходимость алгоритма в задачах разбиения. Можно предложить большое число аналогичных схем генетического поиска для решения задач разбиения. Их эффективность проверяется экспериментальным путем.

Заметим, что такая стратегия поиска позволяет быстрее находить ло- кально-оптимальные результаты. Это связано с параллельной обработкой

множества альтернативных решений, причем в такой схеме возможно концентрировать поиск на получение более перспективных решений. Отметим, что периодически в каждой итерации ГА можно проводить различные изменения в перспективных, неперспективных и в других решениях.

Рассмотрим последовательный ГА разбиения. Пусть задан граф G = = (X, U). Первоначально упорядочим все вершины графа по возрастанию локальных степеней вершин. Это соответствует списку вершин, а также может соответствовать тривиальному разбиению, когда количество групп разбиения равно упорядоченным вершинам графа. Далее начинаем составлять пары вершин и для каждой пары вычислять оценку связности:

где eij — число ребер между вершинами х\ и Xj, образовавшими пару; еi,t и ejyt — это число ребер, соединяющих выбранную пару со всеми остальными вершинами графа, причем t = 1,2,... ,п — 2.

Составим второй список, где будут оставлены такие пары вершин, у которых Sij ^ 0. Отметим, что если пар Sij ^ 0 не находится, то возможны два случая. В первом образуются пары с наименее отрицательным Sij. Во втором случае пары из двух вершин не образуются и сразу происходит переход к образованию групп из трех вершин. Далее процесс повторяется аналогично, пока не будет выполнено разбиение графа на заданное или произвольное число частей. Это — основная идея стандартной процедуры разбиения. При небольшом количестве вершин она дает удовлетворительные результаты, так как практически здесь осуществляется полный перебор вариантов решений. С увеличением числа вершин использование напрямую такого подхода становится нецелесообразно. Для сокращения числа просматриваемых пар применим простые и модифицированные генетические операторы. Отметим, что вместо выражения (6.3) можно использовать выражение

где ті + Tj — внутренние ребра разбиения,

Tt (і = 1, 2,..., п — 2) — внешние ребра разбиения.

Рассмотрим пример. Пусть задан граф (рис. 6.2). Определим локальные степени вершин и упорядочим их в виде списка по возрастанию (табл. 6.1). Построим теперь пары вершин для определения разбиения графа, по две, вершины в каждой части.

На этом уровне выделим два блока разбиения: это вершины (жі,жз), (ж2, xq). Для удобства записи вместо (х\, •. •) будем иногда записывать

их соответствующие номера (1,2,...). Если стоит задача разбить граф на части по две вершины в каждой с минимизацией К, то в качестве третьего блока разбиения можно взять блок с наименьшим отрицательным значением выражения (6.4). Такое разбиение показано на рис. 6.3.

В табл. 6.2 приведены все пары, которые можно получить, объединяя все вершины заданного графа. Очевидно, что для большого числа вершин данная процедура нецелесообразна. Применим одну из множества модифицированных схем генетического поиска, описанных в предыдущих разделах.

Построим случайным образом некоторую популяцию решений Р = = {рі, Р‘2, рз, Р4, Ръ, Рб }, Рі • (1,2). Теперь проверим выполнение условия (6.4) для всех элементов популяции Р. Для первого элемента — 1^7 (условие не выполняется). Продолжая далее, получим:

В качестве ЦФ взято выражение (6.4). Определим для каждой хромосомы в популяции значение ЦФ. Произведем сортировку анализируемой популяции и получим:

Произведем селекцию и образуем родительские пары:

Применим стандартный OK и получим новые хромосомы:

В результате однократного применения О К мы получили лучшее решение Р2:(2,6). Тенденции преимущества ГА видны даже на данном простом примере.

Использование стандартного ОК может приводить к несуществующим решениям (разбиения pf6, pf6). В этом случае можно предложить несколько модификаций ОК. В частности, при скрещивании пар потомки могут получаться путем объединен™ первых и вторых элементов родителей с анализом полученных решений. При этом повторяющиеся элементы устраняются, а. отсутствующие добавляются. Тогда в нашем примере получим:

Здесь, кроме потомков, повторяющих родителей (р^р^р^), находится элемент р” с одним из лучших значений целевой функции (3 ^ 3). Продолжая аналогично, построим группы разбиения по три вершины.

На рис. 6.4 показано разбиение графа G (рис. 6.2) на две части по три вершины в каждой. При этом значение целевой функции К — 5. Отметим, что генетическая процедура поиска может быть применена как единственная, так и множественная оптимизационная процедура. Кроме того, генетические операторы и операторы поиска могут быть вставлены в структурную схему генетического поиска как вспомогательные блоки для повышения качества последовательных алгоритмов.

В первом случае сложность алгоритма разбиения графа будет лежать в пределах 0(п)+0(п3), причем крайний случай с О(п13) будет иметь место при популяции больше ста и выше тысячи генераций алгоритма.

Фракталами, как отмечалось выше, обычно называют множества, которые обладают масштабной инвариантностью, т. е. в любом

масштабе они выглядят практически одинаково. Алгоритмы решения большинства нелинейных оптимизационных задач могут использовать идеи фрактальных множеств.

Рассмотрим алгоритм разбиения графов на части на основе модифицированной агрегации фракталов [165]. Процесс создания кластеров основан на идеях построения минимальных и квазиминимальных массивов в графе

или гиперграфе. Кластер — это часть графа ФСС, причем Ф = (Xi, U\), Хі С X, Ui С U. Вершины кластера соединены внутренними ребрами с остальными вершинами Х\Х± графа G. Внешние ребра не входят в подмножество ребер кластеров. Мощность подмножества внешних, ребер кластера обозначим /. Кластер Фі называется минимальным, если для любого другого кластера Фj С Фі выполняется условие /і ^ fj. Другими словами, удаление произвольных вершин из Фі (ФДХт) приводит к новому кластеру с большим числом внешних, ребер. По определению будем считать:

Это означает, что минимальный кластер не может быть пустым. Кроме того, в тривиальном частном случае каждая вершина графа образует минимальный кластер. Кластер будем называть квазиминимальным, если выполняется условие:

где е — коэффициент, определяющий, на какую величину можно увеличить число внешних ребер в минимальном кластере Фі . Он определяется в процессе анализа математических, моделей графа, на основе решения ЛПР или ЭС.

На рис. 6.5, а показан минимальный кластер на три вершины с /і = = 4. Соответственно на рис. 6.5, б показан простой кластер с /2 = 9. На рис. 6.6, а показан минимальный кластер на две вершины с /3 = 3. При присоединении к нему вершины х% получим квазиминимальный кластер на три вершины с /4 = 5 (рис. 6.6, б). В этом случае величина е = 1.

 

Построение кластера связано с выделением почти всех подмножеств множества X, а. оно составляет 2П, если \Х\ = п. В этой связи продолжают разрабатывать различные эвристики выделения набора простых кластеров. Эти эвристики основаны на теоремах о минимальных массивах в графах [165] и принципах построен™ квазиминимального кластера,

Теорема 6.1. Если Фі и Фj являются минимальными кластерами и Фі Л Ф3 то Фі П 0j = 0.

Теорема 6.2. Пусть Фі, Фj —минимальные кластеры. Если Ф8 = = Фі U Фj A fs < fi A fs < fj, то Ф8 — минимальный кластер. Если ф8 = фі и Ф^ A fs+£ ^ fi A fs ^ fj, то Ф8 —квазимшимальныйкластер.

Теорема 6.3. Пусть Фі, Ф2, ■ • •, Фь — минимальные кластеры, причем любое объединение части из них не являет,ся минимальным кластером. Если Фі = Фі U Ф2 U ... U Фь A fi < /і A fi < /2,..., Afi < fL то Фі —минимальный кластер. Если Фі = Ф\ U Ф2 U ... U Фь fi A fi + + £ ^ /2,..., Afi + e ^ fb то Фі — квазиминимальный кластер.

Доказательства теорем следуют из описанных способов построения кластеров.

Из теоремы 6.1 следует, что в общем случае при полном переборе процедура построения минимального кластера сходящаяся и решение единственно при разбиении графа на части, когда не задано общее число вершин в частях, разбиения. При разбиении графа на заданное число вершин количество решений в общем случае — это мощность некоторого подмножества альтернатив разбиений графа. На основе теорем 6.2 и 6.3 возможно агрегировать (объединять) кластеры и строить минимальные и квазиминималь- ные кластеры. На основе теорем 6.1, 6.2, 6.3 опишем модифицированный эвристический нечеткий алгоритм построен™ минимальных, и квазимини- мальных кластеров в графе.

1.   Упорядочим все локальные степени вершин графа как тривиальные минимальные и квазиминимальные кластеры.

2.   Начиная с вершин с большей локальной степенью, попарно проанализируем все вершины графа G. Если определяется пара вершин (а^, Xj), для которой

и Ф = (Хь U\), Хі = {хі, Xj}, то Ф является минимальным кластером. Здесь p(xi),p(xj) — локальные степени вершин Хі, Xj\ r'ij — число ребер, соединяющих вершины хі, Xj между собой, / — число ребер, соединяющих минимальный кластер с остальными вершинами графа G, причем / < p(xi),f < p(xj). Если определяется пара вершин (Xi, Xj), для которой

причем / + £ ^ р(хі), / + £ ^ p(%j), то Ф = (Xi, Ui), Хг = %j} и Ф является квазиминимальным кластером. Минимальные или квазиминимальные кластеры Ф заносим в специальный список, а. вершины

Xi, Xj исключаем из рассмотрен™. Переход к 2. Если новых минимальных или квазиминимальных кластеров не образовалось, то переход к 3.

3.   Выполняем факторизацию. Вершины хі, Xj в минимальных или квазиминимальных кластерах заменяем одной Xij. При этом ребра, соединяющие Хі и Xj, удаляются, а. ребра из вершины хі, Xj к другим вершинам приписываются общей вершине Xij. Получается граф G'.

4.   В графе G' анализируются все вершины. Если определится тройка вершин ха, хв, хс, для которой справедливо:

причем / < р(ха), / < р(хв), / < р(хс), то объединенная вершина Ф = (ха, хв, хс) образует минимальный кластер согласно теореме 6.3. Если определится тройка вершин ха, хв, хс, для которой справедливо:

причем / + £ ^ р(ха), / + £ ^ р(хв), / + £ ^ р(хс), то вершины ха, хв, хс образуют квазиминимальный кластер согласно теореме 6.3. Переход к 2. Минимальный или квазиминимальный кластер заносится в список. Если в минимальных или квазиминимальных кластеров больше нет, то переход к 4.

5.   Увеличим параметр мощности минимального или квазиминимального кластера на единицу и переходим к 3. Если мощность минимального или квазиминимального кластера равна заданному или равна числу вершин графа, то переход к 6.

6.   Конец работы алгоритма.

Здесь £ — наименьшее относительное отклонение от минимального кластера {е = 0,1, 2,...). После построения набора минимальных или квазиминимальных кластеров, если в графе G остались свободные вершины, необходимо провести процедуру агрегации. Она заключается в пробном помещении вершин в минимальный или квазиминимальный кластер с анализом ЦФ. Вершина помещается в минимальный кластер, если нарушение происходит на величину, не превышающую е. Если после второй процедуры остались свободные вершины, реализуются процедуры, основанные на моделировании эволюций Ч. Дарвина, де Фризе, Ж. Ламарка и К. Поппера, описанные выше. Предпочтение отдается модифицированным операторам мутации, инверсии, сегрегации, удаления и вставки. Рассмотрим пример, показанный на рис. 6.7. Приведен граф G = (X, U), \Х\ = 14, \U\ = 36, который должен быть разбит на части с наименьшим значением К (6.2).

Отметим, что число частей разбиения заранее не задано и определяется в процессе реализации алгоритма после каждого шага построения минимальных и квазиминимальных кластеров. Матрица смежности R графа G

имеет вид:

По матрице определим локальную степень каждой вершины и построим упорядоченный по возрастанию список степеней этих вершин. Сначала определяется минимальный кластер Фі = {х 2^X14} при этом К\ = 2, \Ui\ = 4, \Ui\ - Кі = 2 > 0. Производится факторизация. Строки и столбцы х2, Хі4 матрицы R представляются объединенной строкой и столбцом (#2,жі4), т-е- вершины Х2, Хі4 с соединяющими их ребрами заменяются вершиной Фі и продолжается поиск минимального или квазиминимального кластеров, состоящих из двух вершин. Таких кластеров больше нет. Переходим к поиску указанных кластеров, состоящих из трех вершин. Согласно алгоритму получим: Ф2 = {#8, жю, #із}, при этом К2 = 1, \ІІ2\ = б, \ЬТ2\ - К2 = 5 > 0. При определении К2 не учитываются связи Фі с Ф2, чтобы не определять одни и те же внешние ребра дважды. Продолжая реализацию алгоритма, аналогично получим: Фз = {жз, xq, хп, Ж12}, К3 = 1,

\Us\ = 10, \Us\ - К3 = 9 > 0иФ4 = {ж4,ж5,ж6,ж7,жі}, К4 = 0, \U±\ = = 12, 11/41 — K4 = 12 > 0. Общее число внешних связей между частями разбиения графа G (рис. 6.7) равно К = Кі-\- К2-\- К3 + К 4 = 2 + 1 + 1 = 4.

Рассмотрим другой пример, показанный на рис. 6.8.

Матрица, смежности графа G имеет вид

По матрице определим локальную степень каждой вершины и построим упорядоченный по возрастанию список степеней этих вершин. В результате выполнения алгоритма определим минимальный кластер: Фі = {хі,х2}, Ф2 = {ж8, жд}. Представив Фі и Ф2 в виде вершин, получим новый граф, матрица смежности которого примет вид

Так как минимальных кластеров мощности 2 больше нет, то построим согласно алгоритму минимальный кластер мощности 3. Получим Фз = = {Фх , хз }, Ф4 = {хв, хв, хг }, Ф5 = {х 1 о, х 11, х 12 }. Работа алгоритма закончена, больше минимальных кластеров нет. Вершину Х4, которая, вообще говоря, есть тривиальный минимальный кластер, можно случайным образом добавлять во все остальные минимальные кластеры с вычислением ЦФ. В результате получим два варианта разбиения:

1 -йвариант: {хІ7 х2, х3, х4}, {х5,хв,х7}, {ж8,ж9}, {жю, х,ц, х12}-При этом К = 9.

2-йвариант:   {жьж2,жз}, {ж4, х5, х6, х7}, {ж8,ж9}, {%, хц, х12}. При этом К — 9.

Например, если задано разбиение графа на три части, вариант 1 после процедуры эволюции запишется так:

3-й  вариант: {хг, ж2, ж3, ж4}, {ж5, х6, ж7, ж8, ж9}, {х10 ,хц, х12}. В этом случае К = 7.

Рассмотрим основную идею итерационного разбиения гиперграфа. Н = = (X, Е) на части с минимизацией К. Для каждого ребра гиперграфа G G Е можно определить разрезающую функцию, определяющую число вершин дерева, моделирующего это ребро, попадающих в различные блоки. Если хотя бы одна вершина ребра гиперграфа лежит не в той части, что остальные вершины этого ребра, то обязательно будет существовать, по крайней мере, одно разрезающее ребро. Просуммировав все разрезающие ребра, получим общее число К (связей) между блоками, которое необходимо минимизировать.

Предлагаемый алгоритм состоит из трех этапов. На первом этапе строятся популяции решений, которые могут быть получены случайным, последовательным или итерационным методами. На втором этапе для каждой хромосомы в популяции определяется ЦФ. В качестве ЦФ выбирается К. Затем полученная популяция сортируется и упорядочивается согласно ЦФ. Далее выполняется разбиение популяции на две под популяции: перспективных и неперспективных хромосом. Для первой подпопуляции используется точный поиск, т. е. применяются различные архитектуры ГА, описанные выше. Для второй подпопуляции используется быстрый поиск — ПГА. Затем реализуется оператор миграции хромосом между подпопуляциями. На третьем этапе, используя описанные схемы селекции, выбираются родительские пары или отдельные хромосомы для выполнен™ генетических операторов.

Перед выполнением генетических операторов в каждой хромосоме (текущий вариант разбиения) определяется стоимость существующих строительных блоков. Работа генетических операторов начинается с модифицированного ОК. При этом точка или точки ОК определяются не случайно, а. направленно, выделяя лучшие строительные блоки в каждой хромосоме.

Например, на рис. 6.9 показана схема модифицированного ОК. Здесь Р2 — хромосомы из популяции Р. Строительные блоки, т. е. части разбиения, следующие: {а, Ь, с}, {d, е}, {f, g}; {d, е, с}, {a, f}, {b, g}. Определяя ЦФ, найдем, что К 2 и К§ — наименьшие. Тогда точки ОК в р± направленным образом выделяют блок {d, е}, авр2 — блок {a, f}. Затем производится копирование лучших строительных блоков из р\ и р2 в р[. Свободные места в р[ заполняются оставшимися элементами из р± и р2.

Возможны случаи, когда выбранные строительные блоки могут иметь частичное или полное совпадение элементов. При полном совпадении элементов производится копирование в потомка только одного из строительных блоков. При частичном совпадении — строительный блок из первого родителя копируется полностью, а. из второго родителя копируются несовпадающие элементы. Оператор мутации может выполняться случайно и направленно.

 

 

На рис. 6.10 показано возможное применение ОМ, причем элементы (члены) можно переставлять только между строительными блоками. При направленной мутации в каждом строительном блоке выбирается наихудший элемент.

Для выхода из локальных оптимумов предлагаются две процедуры. В основе первой лежит модифицированный оператор сегрегации. На рис. 6.11 показан пример данного оператора. Заметим, что строительные блоки из хромосом копируются полностью, если они не пересекаются с уже выделенными. В противном случае копируются только непере с екающие ся элементы из строительного блока.

Важную роль в генетических операторах, как отмечалось выше, играет вероятность кроссинго- вера. Р(ОК) и вероятность мутации Р(ОМ). Эксперименты показали, что в задачах разбиения Р(ОК), лежащая в пределах 0,5 0,98, и Р(ОМ) в пределах 0,01 + 0,05, позволяют получать большое число локальных оптимумов за 1000 10000 генераций [165].

Для выхода из локальных оптимумов предлагается ряд процедур. В основе первой лежат модифицированные операторы сегрегации, транслокации, удаления и вставки. В основе второй процедуры лежат идеи миграции хромосом внутри одной популяции и между популяциями. В зависимости от наличия вычислительных ресурсов можно первоначально строить не одну, а. некоторый набор популяций. Далее выбирать «лучшего» представителя из каждой популяции и на этом множестве осуществлять ЭМ.

Определим асимптотическую трудоемкость данного алгоритма. Пусть Np — размер популяции, ІѴП — число полученных потомков, Nq — число генераций ГА. Тогда общую трудоемкость алгоритма можно ориентировочно определить:

где tp — трудоемкость построен™ одной хромосомы в популяции; іп — трудоемкость генерации одного потомка; іс — совокупная трудоемкость селекции и отбора, а, /3, 7 — коэффициенты, определяющие параметры генетического поиска. Заметим, что трудоемкость построения одной хромосомы может колебаться от 0(п) до 0(п\), а. трудоемкость генерации одного потомка зависит от сложности применяемого генетического оператора и ориентировочно изменяется от 0(п) до 0(п log га). Трудоемкость селекции и отбора может меняться от 0(п) до 0(п2). Временная сложность описанного алгоритма ориентировочно составляет 0(п2) для одной генерации.

Следует заметить, что с увеличением числа генераций в ГА время решен™ оптимизационной задачи разбиен™ повышается, но это повышение незначительное и может быть компенсированно получением множества локально-оптимальных решений. Генетические алгоритмы требуют больших затрат времени, чем алгоритмы парных перестановок и случайного разбиен™ графов. Но они позволяют получать набор локально-оптимальных решений.

Допустимое решение экстремальной задачи разбиен™ графа на части является га-мерным вектором. В том случае, когда задача принадлежит классу задач переборного типа, имеется конечное множество допустимых решений, в которых каждая компонента вектора может быть закодирована с помощью целого неотрицательного числа: Е [0, Ѵ^], г = 1, га, где (Ѵ^Н-І) — число возможных дискретных значений і-управляемой переменной в области поиска D [92]. Это позволяет поставить во взаимнооднозначное соответствие каждому вектору рі Е D вектор (3 с целочисленными компонентами. Согласно [92], символьная модель экстремальной задачи разбиен™ графа на части может быть представлена в виде множества бинарных строк, которые описывают конечное множество допустимых решений, принадлежащих области поиска D. Необходимо отметить, что выбор символьной модели исходной экстремальной задачи разбиен™ графа на части во многом определяет эффективность и качество применяемых алгоритмов.

Представим, например, разбиение графа G = (X, U) на две части в виде бинарной строки Е (Хі, Х2), состоящей из п бит, расположенных в порядке возрастания их номеров. Каждому номеру бита поставим во взаимнооднозначное соответствие номер вершины графа (1-й бит соответствует вершине 2-й бит — вершине ж2,..., п-й бит — вершине хп). Потребуем, чтобы бинарное значение щ 1 -го бита указывало, какому подмножеству вершин (Хі или Х2) принадлежит вершина xf.

Число битов, содержащих «1» в бинарной строке Е(Хі,Х2), должно равняться мощности подмножества вершин подграфа Gi = (Хь Ui), равной порядку этого подграфа щ. Так, для графа G (рис. 6.4) получим следующую кодировку разбиения в виде бинарных строк:

В задаче оптимального разбиения графа на части в качестве хромосомы выступает конкретное разбиение, удовлетворяющее заданным условиям, что позволяет интерпретировать решения задачи разбиения как эволюционный процесс, связанный с перераспределением вершин хі Е X графа G по частям разбиения.

В [92] для описания популяций введено два типа вариабельных признака, отражающих, качественные и количественные различия между хромосомами. Качественные признаки — признаки, которые позволяют однозначно разделять совокупность хромосом на четко различимые группы. Количественные признаки—признаки, проявляющие непрерывную изменчивость, в связи с чем степень их описания задается числом.

В работе [92] предлагается генетический алгоритм дихотомического разбиения графа G = (X, U) на два подграфа, основанный на работе [159]: вг = (Хииг) и G2 = (X2,U2), Хг U Х2 = X, V\ U U2 U U3 = U, где Us - подмножество ребер, соединяющих два подграфа, причем для любого ребра Ui Е Us, Ьті = (xi,xj), Хі Е Хг и xj Е Х2 или Хі Е Х2 и xj Е Х\. Целевая функция или критерий разбиения — это число ребер, соединяющих подграфы (К = |Е/з|). Тогда оптимально дихотомическое разбиение является решением (X*, Х£) следующей экстремальной задачи однокритериального вектора

причем К = I U\(U\ U U2) I, где Ѵ\, U2 —подмножества ребер, соединяющих только вершины подмножеств Хг и Х2 между собой.

При взаимодействии хромосомы с внешней средой ее генотип порождает совокупность внешне наблюдаемых количественных признаков, включающих степень приспособленности р(рк) хромосомы pk к внешней среде и ее фенотип. Приняв в качестве внешней среды критерий оптимальности К, в [92] говорят, что степенью приспособленности р(рк) каждой хромосомы является численное значение функции К, определенное для допустимого решения pk ED. В общем случае степень приспособленности р(рк) ^ О можно задать с помощью следующего выражения:

Из данного выражения следует, что чем больше численное значение степени приспособленности /л(рк), тем лучше хромосома приспособлена к внешней среде. Следовательно, цель эволюции хромосом заключается в повышении их степени приспособленности. Степень приспособленности р(рк) в задаче разбиения просто совпадает с критерием оптимальности К — общей суммой числа внешних ребер между частями разбиения.

Очевидно, что в популяции Р1 может иметь место наличие нескольких различающихся форм того или иного вариабельного признака (так называемый полиморфизм), что позволяет проводить разделение популяции на ряд локальных подпопуляции Р\ С Pf, і = 1, V, включающих в свой состав те хромосомы, которые имеют одинаковые или «достаточно близкие» формы тех или иных качественных и/или количественных признаков.

Так, в задаче оптимального разбиения графа на части для дифференциации хромосом по количественному признаку может быть выбрано, например, условие, что в локальную популяцию Р[ С Р1 включаются только те хромосомы, у которых значение К не превосходит некоторой заданной величины. Тогда другую локальную популяцию Р\ С Р1 составят все те хромосомы Pk, которые не попали в Р[.

При решении проблем разбиения графов на части часто возникают задачи группировки элементов, обладающих одинаковыми свойствами. Для решения таких задач будем использовать идеи построения квазиминимальных кластеров на основе агрегации фракталов [165]. Моделью исходных данных задачи, может, например, быть матрица следующего вида:

Здесь столбцы матрицы R соответствуют заданным элементам графа, а строки — свойствам или выполненным функциям этих элементов. Например, единица на пересечении А4 строки и 4 столбца означает, что элемент 4 обладает свойствами Л*. Необходимо сгруппировать элементы, обладающие наибольшим числом одинаковых свойств. Данная задача относится к классу задач разбиения и может быть решена одним из эвристических алгоритмов.

Приведем основную идею предлагаемого эвристического алгоритма [16, 163]. Предварительно выполняется анализ матричной модели. В результате анализа предлагается удалить из рассмотрен™ строки матрицы, содержащие все единицы, все нули, а также строки, содержащие около 1% нулей или единиц. Такое удаление не будет влиять на создание требуемых групп, так как все или почти все элементы будут входить или не входить в формируемые группы. Тогда в рассматриваемом примере исключим строки А$ и А$. Далее произведем сортировку матрицы R. При этом на первое место поместим столбец с наибольшим числом единиц и так далее по убыванию. В этом случае матрица R запишется:

Затем производится разбиение матрицы R на две части: R\ «перспективных» хромосом и R2 «неперспективных» хромосом. Разбиение, включающее элементы {12,4, 7,8,9,11}, относится к «перспективным», а разбиение {1,5,6, 2,3,10} — к «неперспективным». В свою очередь, для распараллеливания процесса части R\ и R2 можно снова разбить на две части R[, R" и R2, R2. Данный процесс можно продолжать до получения подмножеств разбиения, которые легко поддаются обработке генетическими операторами. Предполагается процедура поэлементного сложения столбцов матрицы R по следующим правилам: 1 + 1 = 1; 1 + 0 = 0; 0 + 0 = 0. Например, выполняя указанные сложения для «перспективных» столбцов матрицы R внутри частей R[ и R” (12 + 4; 12 + 7; 4 + 7), получим:

В группе (12,4) — 3 общих свойства, в группе (12,7) — 4 общих свойства и в группе (4, 7) — 2 общих свойства. Продолжая далее, согласно процедурам агрегации фракталов, получим:

В группе (8,9) — 2 общих свойства, в группе (8,11) — 2 общих свойства и в группе (9,11) — 3 общих свойства. Условимся фиксировать группы, имеющие три и более общих свойств. Выполняя аналогичные преобразования внутри «перспективных» частей R2 и R", получим следующие группы

(1.5)     ~ 2 общих свойства; (1,6) ~ 1; (5,6) ~ 1; (2,3) ~ 0; (2,10) ~ 1;

(3.10)    0. Производя сортировку полученных решений в группах, сформируем следующую популяцию: Р = {(12,7), (12,4), (9,11), (4,7), (8,9),

(8.11),   (1, 5), (2,10)}. Для реализации совместной эволюции (Ч. Дарвина, Ж. Ламарка и де Фризе) сформируем следующие родительские пары и выполним ОК:

В группах после применения стандартного одноточечного ОК имеем

(12.11)   4 общих свойства; (9, 7) ~ 3; р'2 совпадает с рі, поэтому не рассматривается, р’А ~ нелегальная группа; (8, 5) ~ 2; (1,9) ~ 3; (8,10) ~ 2; (2,П) ~ 1. Отметим, что использование жадных и других модифицированных ОК позволит избегать получение нереальных групп. Сформируем теперь новую популяцию: Р\ = {(12, 7), (12,11), (9,11), (12,4), (9, 7), (1,9),

(8.5),    (8,10)}.

Здесь размер Р\ оставлен равным Р. Как отмечалось выше, размер популяции можно варьировать в зависимости от качества получаемых решений. В принципе можно выполнить некоторое множество генераций данной операции. Произведем теперь склеивание (объединение) групп по критерию максимума общих, свойств. Тогда получим следующие группы: (12, 7,11) — 4 общих свойства; (12, 7,9) — 3; (12,11,9) — 3; (7,11,9) — 3. Продолжая аналогично, получим группу (12, 7,11,9,1) — 3 общих свойства.

Временная сложность данного алгоритма для одной генерации меняется от О (га) до О (га log га). Данный алгоритм несложен и может выполняться параллельно. Ориентировочная трудоемкость алгоритма:

где іок — трудоемкость ОК, а іскл — трудоемкость операции склеивания.

Реализация алгоритмов разбиения показала преимущество ГА с нестандартными архитектурами поиска по сравнению с алгоритмами парного обмена и случайными алгоритмами. Управление процессом генетического поиска при разбиении позволяет находить оптимальные параметры. Применение модифицированных генетических операторов позволяет повысить качество разбиения. Следует заметить, что с увеличением числа

генераций в алгоритме время решения увеличивается, но оно незначительное и компенсируется получением множества локально-оптимальных решений. ГА требуют больших затрат времени, чем алгоритмы парных перестановок и случайного разбиения графов. ГА по скорости практически

совпадают с итерационными и несколько хуже последовательных. Причем ГА быстрее, чем метод ветвей и границ и метод отжига. В отличие от всех рассмотренных алгоритмов разбиения, генетические позволяют получать набор квазиоптимальных результатов. Разбиение графов с применением методов ЭМ позволяет всегда получать локальные оптимумы, иметь возможность выхода из них и приближаться к получению оптимальных и квазиоптимальных решений, причем, что особенно важно, временная сложность алгоритма не уходит из области полиномиальной сложности (« 0(п log га)+0(га3)).