6.8.  Определение планарности графов на основе генетического поиска

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

Граф G — (X, U) называют плоским, если существует такое изображение на плоскости его вершин и ребер, что каждая вершина х% £ X изображается на плоскости отдельной точкой и каждое ребро uj £ U изображается простой кривой, имеющей концевые точки    причем эти кривые пересекаются только в общих концевых точках, т. е. в вершинах. Здесь и далее под термином граф понимается связный неориентированный граф [123].

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

—    т + / = 2, где п — число вершин, т — число ребер графа, / — число граней графа [123]. Исходя из указанной формулы, был сформулирован ряд следствий:

Следствие!. В любом простом планарном графе существует вершина, степень которой не больше пяти.

Следствие 2. Каждый планарный граф G с п ^ 4 вершинами имеет по крайней мере четыре вершины со степенями, не превышающими 5.

Следствие 3. ЕслиС — связный простой планарный граф с п ^ 3 вершинами и т ребрами, то т ^ 3п — 6.

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

Все графы можно условно разбить на три непересекающихся подмножества: G[, G'2 и Gз- В первое подмножество G[ входят заведомо планарные графы, для которых справедливо неравенство т ^ п + 2. Второе подмножество G2 образуют заведомо непланарные графы, для которых справедливо неравенство т > 3(п — 2). А третье подмножество Gf3 составляют графы, число ребер которых находится в пределах интервала: (п + 2) < т ^ 3(п —

—    2). Именно для этих графов требуется проведение дополнительных исследований, поскольку каждый из них может быть как планарным, так и не планарным.

Следствие 4. Графы К§ и не являются планарными.

Здесь К § — это полный граф на пять вершин, а — двудольный однородный граф с локальной степенью вершин, равной трем (рис. 6.53).

Критерий Понтрягина-Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфа, гомеоморфного К§ или 1<з,з*

Данный критерий является наиболее распространенным. Смысл его

можно пояснить на примере. Пусть задан граф G — (X, U), не имеющий петель и кратных ребер. Подразбиением ребра и = (ж*, xj) называется замена данного ребра двумя ребрами и\ = (ж*, Xk) и и2 — (xk,xj) с введением промежуточной вершины х^. Два графа называются гомеоморфными, если они имеют изоморфные подразбиения [123]. Примеры графов, гомео- морфных графам и показаны на рисунке 6.54.

Существуют и другие критерии планарности.

Критерий Харари-Татта. Граф планарный тогда и только тогда, когда у него нет подграфов, стягиваемых к и к

Критерий Уитни. Граф G планарный тогда и только тогда, когда он имеет комбинаторно двойственный граф G*.

Уитни связал планарность графов с существованием двойственных графов. Для построения геометрически двойственного графа G* каждая грань исходного графа G, включая внешнюю, преобразуется в вершину графа G*.

При этом вершины графа G* будут смежными в случае, если были смежными (т. е. имели общее ребро) соответствующие грани графа G.

Критерий Мак-Лейна. Граф G планарный тогда и только тогда, когда каждый его блок, содержащий, по крайней мере, три вершины, обладает таким базисом циклов Z\, • ■ •, Zq и таким дополнительным циклом Zо, что любое ребро блока принадлежит точно двум из этих q + 1 циклов. Этот критерий основан на рассмотрении циклической структуры графа. Как следует из формулы Эйлера, все внутренние грани двусвязного плоского графа G образуют базис циклов Zl7 Z2,..., Zq, где q — циклический ранг графа G. Кроме того, имеется также Zq — внешний простой цикл графа G. Тогда любое ребро такого графа G будет принадлежать точно двум из q + 1 циклов Zi.

Практическое использование перечисленных критериев затруднено из- за необходимости полного перебора для содержательного рассмотрения графа. Поэтому были разработаны эвристические методы определения планарности. Условно их можно разделить на три класса: циклические, матричные и комбинированные (рис. 6.55). Рассмотрим кратко идею каждого из перечисленных подходов.

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

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

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

Работу матричного алгоритма определения планарности проиллюстрируем на примере. Пусть задан граф G, изображенный на рисунке 6.56. Граф имеет п = 6, т = 9, а число строк, которое необходимо выделить из матрицы циклов Ват для установления планарности графа, будет равно: т — п + 2 = 9 — б + 2 = 5.

В матрице Ват строки — номера циклов, а столбцы — номера ребер графа. В процессе работы алгоритма генерируется множество всех возможных циклов длины к:

С к = {Сі, С 2 ч • • ■, С а], где а — число циклов длины к. Каждый элемент множества Ск представляет собой цикл длины к, состоящий из номеров ребер, составляющих данный цикл. Сформируем реберно-ориентированную матрицу Ват, вектор множества ребер М (рис. 6.57) и вектор комбинаций циклов Ск. В векторе С к выбирается первая комбинация С\ = = [11111000000000] и находится алгебраическое произведение векторов: С\М = 3+3+4+4+4 = 18. На следующем шаге полученное значение С\М = р сравнивается с числом 2т. В случае, еслир < 2т, алгоритм генерирует новую комбинацию циклов и процесс повторяется. Если р > > 2т, то исследуемый граф непланарный. В случае же, когда р = 2т, как,

например, в рассматриваемом примере, алгоритм продолжает работу. Если в результате удалось сформировать подматрицу Ве (рис. 6.58), отвечающую критерию Мак-Лейна, то граф планарный, в противном случае после генерации новой комбинации циклов процесс повторяется.

Основная проблема рассмотренного алгоритма — это генерация и хранение необходимых для работы алгоритма массивов данных (матрицы инцидентности, циклов, реберно-ориентированная матрица и так далее).

К числу достоинств алгоритма можно отнести возможность гарантированного определения планарности.

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

Затем производится попытка расположить каждый полученный фрагмент на плоскость во внешней либо внутренней областях первоначального цикла. Далее укладки фрагментов, по возможности, объединяют, получая плоскую укладку всего графа. Алгоритм основан на идеях поиска в глубину и имеет временную сложность 0(п log п).

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

При решении задачи минимизации пересечений возможен вариант, когда из одной полуплоскости в другую перемещают не отдельные ребра,

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

Для применения универсального ОК к подобной хромосоме необходимо предварительно сформировать маску оператора таким образом, чтобы при обмене ребрами во время выполнения ОК изменение внутренней структуры цепочек ребер не приводило к образованию разрывов.

Рассмотрим порядок выполнения ОМ для определения планарности графа. Например, в ходе решения задачи получена векторная хромосома, каждый ген которой представляет собой закодированную последовательность ребер. Для выполнения операции мутации случайным образом выбираем ген:

где— ген, выбранный для мутации. А затем к выбранному гену

применяем мутацию:

где II — точка мутации. После выполнения операции простой мутации получаем хромосому следующего вида:

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

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

А затем к выбранному гену применяем ОМ, причем разряды для мутации выбираются в соответствии с числами Фибоначчи, т. е. 1, 2, 3, 5,8,..., а обмен числовых значений между разрядами происходит по кругу со сдвигом вправо:

После выполнения ОМ получаем хромосому следующего вида:

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

 

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

Блок генерации циклов производит генерацию всех циклов заданной длины, выполняя это действие столько раз, сколько потребует от него блок анализа. Иначе говоря, он является своего рода поставщиком «сырья» для блока генетических операторов, в котором происходит процесс планаризации исследуемого графа, т. е. плоской укладки графа на плоскость. Блок укладки выполняет плоскую укладку графа, либо его максимально планарной части.

Исходный граф G может быть задан матрицей либо списком смежности. Матричное представление является избыточным. Для алгоритма определения планарности используется модифицированная форма списка смежности LS, где каждой вершине ставятся в соответствие номера ребер, инцидентных рассматриваемой вершине, например, запись 1(1,2) означает, что ребро инцидентно вершинам х\ и х2 и имеет номер 1, причем в список смежности некоторой вершины Хі не включаются номера вершин от х\ до хі-і включительно.

Например, для сгенерированного случайным образом графа G, изображенного на рисунке 6.61, исходные данные для начала работы алгоритма запишутся:

Здесь, например, запись Lxq = {16(6, 7)} означает, что вершины 6 и 7 графа G связаны ребром 16. Такая форма представления исходных данных не содержит избыточной информации, и позволяет увеличить эффективность алгоритма генерации циклов.

Генерация циклов осуществляется на основе поиска в глубину. Число списков смежности будет меньше либо равно числу вершин графа, а число элементов в списке Ьхі находится в интервале: 0 < \Ьхі\ < р(хі). Процесс

генерации циклов к-й длины начинается со списка Lxі, в котором выбирается вершина ж*, стоящая на первом месте, после чего выполняется переход к списку Ьхі. В случае, если на любом из шагов обнаруживается невозможность дальнейшего продолжения (замыкания) цепи, алгоритм возвращается на один шаг назад и просматривает другие возможности для выбора пути. Таким образом формируется множество циклов длины к, представляющих собой цепочки вида х\ ... Хі ... Хк •. • х\. После того, как просмотрены все возможности и сформированы все циклы, использующие вершину х\ в качестве начальной, список Lx 1 удаляется из рассмотрения, после чего процесс повторяется для следующего списка.

В процессе работы алгоритма генерируется множество всех возможных циклов длины к: С к = {Ci, С2,..., Са}, где а — число циклов длины к. Каждый элемент множества С к представляет собой цикл длины к, состоящий из номеров ребер, составляющих данный цикл. Так, например, для графа, изображенного на рисунке 6.61, в процессе работы блока генерации циклов были получены следующее множество циклов длины три:

Здесь, например в цикле Сз, 2 это ребро (1,3), 8 — ребро (3,6), 4 — ребро (1,6). На основе этих списков может быть сформирована матрица циклов В = ||%Цехт, где с — число циклов, а т — число ребер графа, причем элемент матрицы % = 1 в случае, если ребро rrij принадлежит циклу Сі(rrij £ Сі), и = 0 в противном случае. Пример матрицы циклов длины 3 показан на рисунке 6.62.

Полученные данные являются исходными для работы ГА. Алгоритм анализа и принятия решений можно записать в следующем виде:

1.   Подсчет числа циклов NCk = \Ск\ и числа повторов Nmj каждого ребра rrij, где j = 1,..., М.

2.   Если выполняется условие:

то переход к пункту 3, если нет, то возврат к блоку генерации циклов и начало генерации циклов длины к + 1.

3.   Из множества циклов С к выбираются первые т — п + 2 цикла и подсчитывается общее число ребер Nm, принадлежащих этим циклам: Nm —

к

= к ' \Ск\, где к — длина цикла, \Ск\ — мощность множества циклов

к=3

длины к, К — длина самого длинного из всех сгенерированных циклов,

вычисляемая по формуле К — k + s, где s — число шагов в блоке генерации циклов.

4.   Полученное значение Nm сравнивается с удвоенным числом ребер исходного графа G. Если Nm > 2m, то рассматриваемый граф является непланарным. После чего необходимо принять решение. Если нужно выделить максимальную планарную часть графа и получить для нее плоскую укладку, то переход к пункту 6, в противном случае к 7.

5.   Необходимо сформировать такую комбинацию циклов, чтобы выполнялось условие: Nm — 2т. Если полученное значение Nm < 2m, то необходимое условие достигается путем замены некоторого числа циклов меньшей длины (например длины к) на циклы большей длины (циклы длины А:+1). Если циклы длины к + 1 отсутствуют, то нужно вернуться к блоку генерации циклов и начать генерацию циклов длины к + 1, в противном случае переходим к пункту 6.

6.   В случае, когда Nc = 2m, либо после преобразований, описанных в пункте 5, либо в случае, описанном в пункте 4, работа блока анализа завершена, полученные данные (множество циклов и предполагаемая схема комбинации) фиксируются и передаются для работы ГА.

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

Для графа, представленного на рисунке 6.61, процесс выбора решения будет следующим.

Согласно пункту 1 алгоритма:

1.1. Сформировано девять циклов длины три (NC3 = 9).

1.2. Необходимое число циклов р = т — п + 2 = 16 — 8 + 2 = 10. Поскольку Ncз < р, то необходимо вернуться к блоку генерации циклов и начать генерацию циклов длины 4.

Согласно пункту 2 алгоритма:

2.1. В результате работы блока генерации циклов сформировано 16 циклов длины четыре:

);

2.2. Общее число циклов стало равным двадцати пяти (Nc = 9 + 16 = = 25), т. е. Nc > р. Число повторений каждого ребра Nmj > 2, поэтому переходим к пункту 3.

2.3. Поскольку р — 10, то для первых десяти циклов подсчитываем число ребер: Nc = 3 х 9 + 4 х 1 = 27 + 4 = 31.

2.4. Число ребер Nm не больше удвоенного числа ребер графа 2т. (2т = 2 х 16 = 32), поэтому переходим к пункту 5.

2.5. Полученное значение Nm меньше удвоенного числа ребер графа (2т, = 2 х 16 = 32 => Nc < 2т). Формируем предполагаемую схему

комбинации. Для этого необходимо заменить один из циклов длины три на цикл длины четыре.

2.6. После проведения замены условие Nc = 2т выполнено и выясняется, что для решения поставленной задачи необходимо из имеющегося множества циклов выделить некоторый базис, включающий десять циклов, в том числе 8 циклов длины три и 2 цикла длины четыре.

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

1    этап. «Строительство фундамента» — процесс формирования начального базового решения, которое должно стать основой для дальнейших преобразований.

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

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

4    этап. «Корректировка проекта». На этом этапе полученное квазиоптимальное решение в виду невозможности дальнейшего улучшения запоминается, после чего в данное решение («проект») вносятся изменения и строительство возобновляется со второго этапа.

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

ванные к специфике поставленной задачи. Задача корректировки проекта выполняется с помощью операторов мутации и инверсии.

Сырьем для производства строительных блоков, используемых в процессе строительства, является множество циклов, сформированное блоком генерации циклов, причем строительные блоки могут быть размера два (число циклов в каждом из них) на первом и втором этапах работы генетического алгоритма, либо один. Схема функционирования блока генетических операторов показана на рисунке 6.63.

Исходными данными для рассматриваемого ГА является множество циклов, из которого необходимо некоторым образом выделить базис циклов Вр, где р = т — п + 2. То есть, для представления базиса в виде хромосомы необходимо, чтобы в ней было не менее р разрядов (генов), каждый из которых соответствует номеру цикла. Таким образом, под хромосомой понимается комбинация из р циклов, являющаяся одновременно вариантом плоской укладки исходного графа.

В алгоритме используются специального вида хромосомы с числом генов, равным (р + 3), причем каждая хромосома в популяции состоит из двух частей. Левая часть хромосомы имеет р разрядов, представляющих, собой комбинацию задействованных в данном варианте решения циклов, а правая, часть имеет три разряда, несущих информацию о том, какие ребра и сколько раз содержатся, в выбранной комбинации (0, 1 или 2 раза соответственно для разрядов р + 1, р + 2 ир + 3). Кроме того, последние три разряда используются при количественной оценке качества полученного решения, для. этого вводится, в рассмотрение функция 6(т), которая, стремится, к ми-

нимуму для генов р + 1 и р + 2    0) и стремится к максимуму для

генар + 3 (/(Я) т):

где Nmp +3 — число элементов в р + 3 разряде хромосомы, a Nmp +2 — соответственно число элементов в р + 2 разряде хромосомы.

Как следует из формулы, значения, которые может принимать функция оценки 5(т), находятся в интервале [0,1], причем качество решения будет тем выше, чем большее число ребер (и прежде всего ребер, встречающихся дважды) задействовано в оцениваемом решении. Левая часть хромосомы, в свою очередь, может содержать как значащую, так и незначащую части. Разряды значащей части заполняются номерами циклов, а незначащей — нулями. При этом чем выше качество решения, тем меньше длина незначащей части (L0 —0). Для оптимального решения L0 будет равна нулю. Таким образом, целевая функция хромосомы полученного решения f(H) является аддитивной функцией двух переменных: f(H) = (tf(m); L0), причем f(H) —»• max, когда 5(т) —»• 2т и L® —»■ 0.

Методику расчета ЦФ хромосомы покажем на следующем примере. Пусть существует некая произвольная комбинация циклов Сі, С 2 и (%, закодированная хромосомой следующего вида:

Здесь 1,2,3 — номера циклов, 3,9-16 — номера неиспользованных ребер, 4-8 — номера ребер, задействованных один раз, а 1,2 — номера ребер, использованных дважды.

Тогда значение ЦФ данной хромосомы равно / (Я) = (0,2813; 7): L0 = = 7; ё(т) = (2x2 + 5)/(2 х 16) = 9/32 = 0,2813. Решение, имеющее подобное значение ЦФ, соответствует промежуточному решению, поскольку значение ЦФ базового решения не может быть менее 0,5.

Для алгоритма используются два варианта стратегии создания начального базового решения, избираемые в зависимости от характера исходных данных и решения ЛПР.

Первый вариант заключается в том, что в имеющемся множестве циклов С выбираем циклы, в которых ребра повторяются точно два раза. Если это не удается сделать, то область поиска сужается и просматривается не все множество, а только первые р циклов. Циклы, которым принадлежат найденные в результате такого поиска ребра, суммируются, образуя определенную комбинацию. Эта комбинация проверяется на предмет образования нереальных решений (т. е. наличия ребер, повторяющихся более двух раз). Если такие ребра обнаруживаются, то из комбинации удаляется минимально возможное число циклов, содержащих «лишние» ребра, а полученная комбинация преобразуется в хромосому. Таким образом получается начальное базовое решение.

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

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

Рассмотрим подробнее первый вариант стратегии создания начального множества решений на примере матрицы циклов графа G, сгенерированного случайным образом (рис. 6.61).

В результате работы алгоритма сформировано множество циклов Ck длины 3 и 4, где Nc = 25. В каждом цикле этого множества ищем ребра, повторяющиеся два раза. Так как таких ребер нет (Vj Е M)(Nmj > 2), то сужаем область поиска и просматриваем первые р элементов множества С. В результате поиска выясняется, что таких ребер четыре. Это ребра номер 3, 7, 13, 16. Теперь суммируем все циклы, включающие указанные ребра. Получаем комбинацию циклов: {С 2, С§, Cq , С 7, С%, Cq }, а затем проверяем, не создает ли полученная комбинация нереальных решений. Поскольку ни в одном столбце сумма единиц не превышает два, данная комбинация является начальным базовым решением и будет закодирована следующей хромосомой:

Здесь 1н — первая хромосома начальной популяции.

ЦФ хромосомы 1н равна: 8(т) = (2 x 5 + 8)/32 = 18/32 = 0,5625; L0 = 4; /(1н) = (0,5625; 4). На данном этапе продолжается процесс заполнения сформированного ранее начального базового решения с помощью генетических операторов селекции, кроссиншвера и отбора. Схема работы ГА на этом этапе выглядит следующим образом (рис. 6.64).

Шаг «А». Имеется хромосома, представляющая начальное базовое решение. Теперь необходимо сформировать множество промежуточных решений, из числа которых будет выбран второй родитель для участия в операции скрещивания. Множество промежуточных решений формируется путем попарного объединения циклов, причем объединение производится таким образом, чтобы образующиеся в результате парные ребра были идентичны ребрам, присутствующим в разрядах р +1, р + 2 начального базового решения. Кроме того, номера циклов множества промежуточных решений не должны совпадать с номерами циклов, участвующих в базовом решении. Размер популяции промежуточных решений зависит от числа ребер в разрядах р + 1, р + 2 базового решения и от длины хромосомы L (т. е. размерности исследуемого графа). Для рассматриваемого примера множество промежуточных решений формируется случайным образом путем попарного объединения циклов, включающих ребра 2, 8, 12.

Размер начальной популяции примем равным трем (по одной хромосоме для каждого ребра):

После того, как множество промежуточных решений сформировано, алгоритм переходит на следующий шаг.

Шаг «В». Здесь производится селекция множества промежуточных решений с целью выбора хромосомы. Для оценки каждого решения были разработаны следующие правила:

1.   В генах р + 2 и р + 3 претендента, по возможности, не должно быть ребер, совпадающих с ребрами из разряда р + 3 первого родителя.

2.   В генах р + 1 претендента и р + 3 первого родителя желательно иметь максимальное количество совпадающих ребер.

3.   В гене р + 2 претендента должно быть максимальное число ребер, идентичных ребрам из разряда р + 2 хромосомы первого родителя.

На основе правил создан комплексный параметр — функция пригодности промежуточных решений относительно базового решения     Данный параметр является аддитивной функцией двух переменных f!(H) = (5'(т); А^), где ё\т) — относительное увеличение числа ребер; N'c — относительное увеличение числа циклов. Количественное значение функции пригодности рассчитывается следующим образом:

а)   определяется число совпадений ребер из разряда р + 3 оцениваемого промежуточного решения с ребрами из разрядар+3 первого родителя. Затем подсчитывается число совпадений Л^2 в разрядах р + 3 промежуточного решения и р + 2 первого родителя, а также число совпадений А^3 в разрядах р + 2 промежуточного решения и р + 3 родителя. Сумма этих чисел характеризует возможное число ребер, которые необходимо будет удалить из базового решения после выполнения кроссиншвера. Следовательно, в оптимальных промежуточных решениях значение суммы будет стремиться к нулю;

б)   находится число совпадений NSl ребер из разряда р + 3 оцениваемого промежуточного решения с ребрами из разряда р + 1 первого родителя. Затем подсчитывается число совпадений NS2 в разрядах р + 2 промежуточного решения и р + 1 первого родителя и, наконец, подсчитывается число совпадений NS3 в разрядах р + 2 промежуточного решения и р + 2 родителя. В этом случае определяется число ребер, которые добавляются в базовое ре-

шение в результате операции кроссинговера, т. е. качество промежуточного решения тем выше, чем больше значение этой суммы;

в)   подсчитывается значение S\m) по формуле: S\m) = 1 — [(2 х Nd-^ + + + TVdg)/(2 X + Ns^ + Ns^)]. Полученное значение зависит от соотношения возможного числа удаляемых и добавляемых ребер и стремится к единице для наилучших, промежуточных решений. .В случае получения отрицательного значения функции пригодности делается вывод о том, что данное решение непригодно для участия в дальнейших операциях;

г)   сравниваются ребра в разрядах р + 2 и р + 3 промежуточного решения с ребрами в разряде р + 3 базового решения и, при наличии совпадений, выявляется минимальное число циклов Nc^, которые после выполнения ОК будут удалены из базовой хромосомы для устранения нереальных решений.

То есть, в оптимальном промежуточном решении значение будет стремиться к нул.ю;

д)   вычисляется значение по формуле:

Здесь 7Ѵс+ — число добавляемых циклов, Nc^ — удаляемых;

е)   подсчитывается значение функции пригодности хромосомы относительно текущего базового решения /'(Я).

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

Для рассматриваемого примера подсчитаем значения функций пригодности относительно базового решения (хромосома 1н):

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

Шаг «С». На этом шаге выполняется ОК двух родительских особей. Здесь используется двухточечный суммирующий ОК. Точки скрещивания в операторе выбираются следующим образом:

1.   В первом родителе первая точка скрещивания ti находится за последним значащим (ненулевым) элементом hi хромосомы, а позиция второ.й точки І2 выбирается после элемента hi + к, где к — число значащих элементов во второй родительской хромосоме.

2.   Во втором родителе первая точка находится перед первым элементом хромосомы, а вторая точка определяется так же, как в случае с первым родителем.

в результате выполнения ОК происходит объединение значащих частей родительских хромосом. В случае, если в функции пригодности второго родителя (5^ (ш) / О, то из хромосомы потомка удаляются ребро (или ребра), которые повторяются в данной комбинации более двух раз. Параллельно с удалением ребер удаляются ТѴс- циклов, которым принадлежит данное ребро. Данный цикл (циклы) вместе с принадлежащими им ребрами заносятся в хромосому второго родителя. При этом вновь появившиеся в хромосоме циклы не могут быть удалены. В примере точки ОК для хромосомы 1н: 1^1 = 6,12 = 8, и для хромосомы 2н: = 0,1^2 = 2.

После выполнения ОК получается новое базовое решение:

Шаг «О». Здесь популяция промежуточных решений переупорядочивается. Для этого производится пересчет функций пригодности каждого элемента популяции относительно нового базового решения. В случае, если после произведенного пересчета функции пригодности всех элементов имеют низкие оценки (f\pi) = {S^{m) < 25% и < 0)), то необходимо либо расширить размер популяции промежуточных значений, либо перейти к следующему этапу строительства. Решение принимается ЛПР на основании оценки размера популяции и числа пройденных поколений. Расширение размера популяции производится за счет добавления промежуточных решений, включающих пары ребер, иденттных ребрам из разряда р + 3 базовой хромосомы. Если получено базовое решение, в котором число ребер в разряде р + 1: А^шр+і = О, а в разряде р + 2: ІѴшр+2 / 0. алгоритм также переходит к следующему этапу.

Поскольку размер популяции промежуточных решений в рассматриваемом примере изначально мал и число пройденных поколений {Nq = 1) невелико, увеличиваем популяцию промежуточных решений за счет добавления хромосом, содержащих ребро 12, так как в разряде р + 1 базового решения осталось только одно это ребро:

Подсчитаем функции пригодности новых промежуточных решений:

Лучшую оценку пригодности имеет хромосома 6н, которая будет выбрана в качестве второго родителя для ОК. Теперь возвращаемся к этапу «С» и выполняем ОК для хромосом 1н и 6н:

В полученной хромосоме 2п все разряды с Ьго по р-й (т. е. с Ьго по 10”й) являются значащими, а разряды р+1ир + 2 — пустые. Следовательно, условие планарности графа выполнено. Таким образом, в результате выполнения ОК построено оптимальное базовое решение (хромосома 2п).

После декодирования хромосомы будет сформирован необходимый базис циклов Вр (рис. 6.65). Следовательно, данный граф может быть уложен на плоскости без пересечений.

Задача алгоритма на этапе 3 состоит в том, чтобы при имееющемся квазиоптимальном решении поиск оптимального решения вести, не ухудшая качества имеющегося. Для этого популяция промежуточных решений расщепляется таким образом, чтобы каждая хромосома новой популяции содержала в себе только один цикл, после чего выполняются действия, идентичные шагам «В»-«0» этапа 2. При построении оптимального решения алгоритм завершает работу, в противном случае переходит к этапу 4. Переход к этапу 4 осуществляется, если в ходе решения задачи получено квазиоптимальное решение, не улучшающееся на протяжении значительного числа поколений (попадание в локальный оптимум).

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

полнения ОМ элементы меняются местами, после чего значащий элемент обнуляется, все принадлежащие данному циклу ребра удаляются из генов р + 2 и р + 3 и, при необходимости, оставшиеся значащие элементы сдвигаются вправо, вытесняя нулевой элемент из значащей части. Например, для хромосомы 1п ОМ выполняется следующим образом. В хромосоме случайным образом выбираем два гена, один из которых значащий, а второй нулевой. Пусть это будут гены 3 и 10:

После этого производим обмен:

Из генов р + 2 и р + 3 удаляем ребра принадлежащие циклу 6.

Сдвигаем значащие элементы влево, после чего ОМ заканчивает свою работу:

Здесь 1пм_ — первое решение потомок после мутации.

Схема проведения оператора инверсии аналогична ОМ с той лишь разницей, что для обмена выбирается не один ген хромосомы, а несколько. Число обмениваемых генов задается случайным образом, однако оно не должно быть больше числа незначащих разрядов инвертируемой хромосомы. Вероятности проведения операций мутации Р(ОМ) и инверсии Р(ОИ) выбираются случайным образом на интервале [0,1], причем их суммарная вероятность P(SUM) = Р(ОМ) + Р(ОИ) = 1.

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

На каждом (і+1)-м шаге находим разность множеств = СвнДС^і+і и = Сі^і\СвИг-> где Сви — внешний цикл графа, после чего вы

полняем суммирование Свн^+і = + ^і+і- Работа алгоритма плоской укладки заканчивается после того, как все ребра графа будут пройдены, как минимум, один раз. Покажем работу алгоритма плоской укладки для графа G (рис. 6.61). Выбираем первый цикл в подматрице р. Это цикл Сі. На первом шаге цикл С\ совпадает с внешним циклом Свні • C'bhi = {1(1,2) — — 6(2,3) —2(3,1)}. Затем выбираем следующий цикл в базисе р. Это цикл С2. Находим разность множеств:

После суммирования и получим:

Далее процесс продолжается аналогичным образом:

На следующем шаге алгоритма должен быть выбран цикл Cs, однако в нем нет ни одного ребра, принадлежащего внешнему циклу. Поэтому временно пропустим его и перейдем к циклу Cq :

Теперь во внешнем цикле появилось ребро 16, соединяющее вершины графа (6,7) и возвращаемся к циклу :

Алгоритм плоской укладки завершил работу, так как все ребра графа пройдены. В результате получена плоская укладка исходного графа G (рис. 6.66).

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

(рис. 6.67). Списки смежности данного графа будут выглядеть следующим образом:

После работы блока генерации циклов будет сформировано следующее множество циклов длины три:

Поскольку Nc < р, то продолжаем генерацию циклов длины четыре:

В результате общее число сгенерированных циклов Nc равно 16. Пе™

реходим к блоку анализа (п. 2) и сравниваем: ТѴс > р; Njn^ > 2. Условие выполнено, переходим к пункту 3. Выбираем первые 10 циклов и подсчитываем число ребер: 5 X 3 + 5 X 4 = 35; 2 х ш = 2 х 17 = 34; 35 > 34. Следовательно, граф непланарный. Для минимизации числа пересечений ребер данного графа переходим к блоку генетических операторов.

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

Просуммировав их, получим начальное базовое решение:

Целевая функция полученного базового начального решения равна: Lo = 2;с5(ш) = (2х14+0)/(2х17) = 28/34 = 0,8235; /(Я) = (0,8235; 2). Теперь необходимо сформировать популяцию промежуточных решений. Поскольку в начальном базовом решении отсутствуют 6 ребер, примем размер популяции равным 6:

Теперь вычисляем функции пригодности полученных хромосом:

Согласно полученным функциям пригодности хромосомы 6, 8, 11 удаля™ ются из популяции. Из трех оставшихся хромосом наибольшее значение функции пригодности имеет хромосома 7 (/'(7н) = (0;0,5)), которая и будет отобрана для проведения ОК:

В полученной хромосоме (1п) есть четыре ребра (10, 11, 13, 14), повторяющиеся трижды. Для того, чтобы избежать появления нереального решения достаточно удалить один цикл 14. Тогда базовое решение примет вид:

Определим ЦФ полученного базового решения: Lq = 1; S{m) = (2 х X 16)/(2 • 17) = 28/38 = 0,9412; /(Я) = (0,9412; 1). Как видно, значение ЦФ базового решения улучшилось. Полученное значение /(Я) позволяет считать, что найдено некоторое квазрюптимальное решение. Однако базис циклов сформирован не полностью. Продолжим процесс исследования. Для этого применяется ОМ. Для проведения ОМ случайным образом выбираем разряд 7 в хромосоме базового решения и обнуляем его:

Затем из правой части хромосомы удаляем ребра, соответствующие циклу 5:

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

жество решений, состоящих из одного цикла:

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

Построим теперь максимально планарную укладку данного графа. В результате работы ГА сформирован следующий базис циклов:

Выбираем первый цикл базиса С\:

Алгоритм плоской укладки завершил работу. В результате работы получена укладка максимальной планарной части исходного графа G' (рис. 6.68).

Для алгоритма определения планарности в классической постановке временная и пространственная сложности определяются как функщіи от гі, т. Временная сложность ГА складывается из временных сложностей отдель-

ных операторов. Временная сложность алгоритма селекции, в худшем случае, составляет 0{Np + 2 log 2Np). Временные сложности ОК и ОМ составляют 0{L).

Здесь ПСА — пространственная сложность алгоритма, определяемая объемом оперативной памяти при работе алгоритма. В течение одного поколения выполняется один оператор селекции и один ОК. ОМ выполняются не чаще одного раза в 4-5 поколений. Необходимо учесть, что при начальной генерации популяции формирование одной хромосомы требует L операций для определения генов. После генерации начальной популяции необходимо выполнить ее сортировку, что требует Np log 2Np операций. То есть, временная сложность генетического алгоритма составит: 0{{п + + ш) + 2ш + [Nplog2Np + (Np + 2log2Np) + 0{L) + 0(Ь)/5]Жс), где Ng — число поколений, Np — размер популяции. Следовательно, временная сложность алгоритма определения планарности пропорциональна 0{п + т). Зависимость временной и пространственной сложности от числа вершин графа приведена на рисунке 6.69.