6.3. Размещение вершин графов в линейке и на плоскости

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

Алгоритмы размещения вершин графов согласно [118, 159] можно разделить на два основных класса. Это конструктивные (последовательные) алгоритмы и методы итеративного улучшения. Для их решения применяют шесть основных подходов [159]. К ним относятся: моделирование отжига; сила — направленное размещение; размещение посредством разбиения; числовые оптимизационные подходы; размещение на основе методов ЭМ; точные методы.

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

Приведем постановку задачи. Основная цель алгоритмов размещения — минимизировать общую суммарную длину ребер графа или гиперграфа. Часто также ставится задача (или ограничение) минимизировать общее число пересечений ребер графов.

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

или

Здесь (si, ti); (sj,tj) — координаты xj элементов (вершин графа), dij — расстояние между элементами хі, Xj на заданной плоскости.

Выражение (6.5) позволяет определить манхеттоново расстояние, т. е. расстояние между двумя вершинами, определенное по вертикальным и го™ ризонтальным направлениям. Шаг (расстояние) между двумя рядом лежа™ щими вершинами по горизонтали и вертикали считается равным единице. Выражение (6.6) позволяет вычислить прямолинейное расстояние между двумя вершинами. При использовании гиперграфа длина его ребер подсчитывается как полупериметр прямоугольника, охватывающего их концевые точки (длина ребра е гиперграфа на рис. 6.12 равна 6). Тогда общая длина всех ребер графовой модели определяется по известной формуле:

Здесь L(G) — общая суммарная длина ребер графа, сij — количество ребер, соединяющих вершины хі и Xj, п — число вершин графа. Число пересечений ребер графа определяют по формуле:

Здесь П(С) — общее число пересечений ребер графа, П(щ^) — число пересечений ребра соединяющего вершины хі, xj.

Рассмотрим алгоритмы, минимизирующие L(G) и H(G) (L(G) —min, П(С) —> min). Отметим, что минимизация суммарной длины ребер графа обычно приводит к минимизации числа пересечений. Такая одновременная минимизация длины и пересечений происходит до некоторого предела, начиная с которого уменьшение длины приводит к увеличению числа пересечений. Для одновременного учета длины и пересечений ребер графа вводится комплексный критерий

Здесь а, /3 — коэффициенты, учитывающие степень важности того или иного критерия (а + (3 = 1). Значения а и /3 могут определяться на основе знаний ЛПР или экспертных оценок в оптимизационных задачах размещения.

В оптимизационных задачах размещения входными данными будут множества вершин графовой или шперграфовой модели X = {жі, #2,...

множество ребер графа U = {щ, • • •, ит} или гипергра- фа Е = {еі, б2,..., еш} и множество позиций Q = {(/і, (/2причем |Х| ^ |Q|, если производится размещение вершин на заданные позиции. Иногда производится размещение ребер, и тогда число позиций должно быть ^ числа концевых точек размещаемых ребер.

Сформулируем задачу размещения как назначение каждой вершины графа (шперграфа) в единственную позицию таким образом, чтобы оптимизировать ЦФ. В качестве ЦФ выбирается выражение (6.7). Выходными данными будут позиции назначения для каждой вершины. В качестве ограничений выбираются следующие условия. Для каждого хі £ X назначается только одна позиция qi £ Q; каждой позиции qi Е Q соответствует, по крайней мере, один элемент Хі £ X. Следовательно, сформулирована задача размещения как оптимизационная. Известно, что проблема размещения относится к классу NP-полных [159, 160]. Поэтому постоянно производится поиск эвристических процедур для повышения качества и уменьшения сложности алгоритмов. Алгоритм считается «вероятностно хорошим алгоритмом», если его временная сложность 0(п), 0(п logn), 0(п2).

Рассмотрим размещение вершин графа на плоскости в решетке заданной конфигурации. В настоящее время выделяют два подхода применен™ ЭМ для размещения вершин графа на плоскости. Первый подход использует методологию Р. Клинга для размещения элементов, одинаковых по высоте и различных по ширине, на основе ЭМ [166]. Второй подход основан на идеях Д. Кохона, В. Париса, М. Майера, Й. Сааба, Н. Шервани, Р. Шахокара и П. Мазумдера [117, 167-172].

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

Предлагается модификация данного подхода для размещения вершин графа (гиперграфа) на плоскости и в линейке с оптимизацией выражения (6.7). Она заключается в использовании дополнительных генетических операторов, гомеостатического управления и синергетических и иерархических принципов, имеющих аналогии в ЕС. На рис. 6.13 приведена струк

турная схема алгоритма размещен™ вершин графа на плоскости на основе эволюций Ч. Дарвина, Ж. Ламарка, де Фриза и К. Поппера. Отметим, что все разработанные архитектуры поиска, приведенные выше, используются для распараллеливания алгоритмов и совместного применения эвристического, стохастического поиска и ЭМ.

В ГА на рис. 6.13 начальная популяция будет конструироваться тремя способами Аі, А2, А3. В случае Аі популяция решений (заданных размещений) формируется случайным образом. В случае А2 популяция решений получается путем неоднократного применения по с л е д овате льного алгоритма. Формирование популяции А3 производится совместно случайным и направленным образом. Отметим, что ЛПР на основе блока эволюционной адаптации может создавать любое число популяций другими способами. После формирования популяции к каждому ее элементу применяется оператор мутации, причем ОМ может выполняться независимо для каждого элемента популяции.

Заметим, что для задач размещения хорошие результаты (локальные оптимумы) дает применение следующих операторов мутации: ОМ метода золотого сечения, ОМ метода Фибоначчи, ОМ метода дихотомии, ОМ множества Кантора, а также ряд других модификаций, за счет получения реальных решений оптимизационных задач [171].

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

Далее выполняются три версии оператора сегрегации. В первой используется «жадная» стратегия. Во второй — стратегия золотого сечения. В третьей используется метод Монте-Карло. Проводились эксперименты с операторами сегрегации метода золотого сечения, метода Фибоначчи, метода дихотомии и др.

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

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

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

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

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

Пусть для графа G = (X, U), \Х\ = 6, \U\ = 10, показанного на рис. 6.14, случайным образом получена следующая популяция решений (размещение вершин графа в линейке):

Следуя [160], определим оценку минимальной суммарной длины для данного графа. Она определяется при расположении ребер графов по кратчайшим расстояниям без учета изоморфизма. При этом кратные ребра упорядочиваются по длине и располагаются в ближайшие позиции по убыванию длины. В нашем случае для графа G = (X, U) (рис. 6.14) наилучшая оценка будет равна L(GД)мин = 13. Теперь вычислим ЦФ для каждой хромосомы в популяции. Тогда суммарная длина связей для альтернативных решений Р\ — Pq определится так:

Произведем сортировку хромосом согласно их ЦФ: р4; рз; р\; рб; Рб; Р2 • Начиная с р4, применим ОМ. Пусть точка мутации случайным образом определится между 5 и 6 элементами. Тогда получим

Далее предлагаются два основных решения. В первом выполняется мутация всех рі из Р и строится новая популяция Р'. Во втором популяция изменяется после каждого ОМ. Например, вставим р'4 в Р', исключив р2, тогда Р' = {р4, Р4, Рз, Рб , Рі, Рб } • Покажем теперь применение случайной

версии оператора инверсии. Возьмем р4, в котором случайным образом точка инверсии попадает между 1 и 2 элементами. Тогда

Величина L(G) приближается к глобальному минимуму. На этом процесс размещения может быть закончен. На рис. 6.15 показано это размещение.

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

На рис. 6.16 показано размещение графа G (рис. 6.14) с глобальным минимумом L(G) в линейке. Для того, чтобы получить размещение, во всех линейках можно применять описанные выше ГА разбиения. Для этого нужно разбить граф на заданное число линеек, с минимизацией количества ребер между линейками, а затем произвести оптимизацию размещен™ внутри каждой линейки, используя методы генетического поиска.

Определим ориентировочную трудоемкость разработанного линейного алгоритма:

здесь tp — трудоемкость построен™ одной хромосомы в популяции; £<эм — трудоемкость оператора мутации; £<эи — трудоемкость оператора инверсии, toe — трудоемкость оператора сегрегации; £<эт — трудоемкость оператора транслокации, Nq — число генераций, Np — размер популяции.

Временная сложность алгоритма линейного размещения меняется от 0(п) до 0(п2). Вероятность получения оптимального результата можно определить так:

где Рі — вероятность получения оптимального результата при генерации одной хромосомы в популяции; Nn — число полученных потомков.

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

Здесь популяция создается тремя способами: направленно Р\, случайнонаправленно Р2 и случайно Рз. Минимальный размер популяции п/2, где п = \Х\ — число вершин графа. Минимальное число генераций Nq = = 10гг. Схема алгоритма (рис. 6.17) состоит из двух строительных блоков. Она построена таким образом, что в процессе работы устанавливается относительный баланс, причем на вход одного строительного блока подается набор случайно полученных хромосом, а на вход второго — заданный набор хромосом. Далее моделируем каждую хромосому путем выполнения ГА с ОК, ОМ, операторами сегрегации, транслокации, инверсии и другими генетическими операторами. Затем, определяя ЦФ, находим лучшее размещение с заданными параметрами. Выполняем работу алгоритма посредством вы-

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

В заключение производится выбор наилучшего множества параметров из конечной популяции. Размер популяции обычно выбирается, исходя из опыта ЛПР и имеющихся вычислительных ресурсов. Теоретические исследования [163] рекомендуют размер популяции Np^n/2, где п — число вершин графа. Определения числа генераций, наряду с размером популяций, являются открытыми проблемами в ГА. Отметим, что глобальный минимум может быть получен как на первой генерации, так и не найден на последней. Применение стандартных ГА и ПГА может не давать реальных размещений, поэтому необходимо использовать различные модифицированные генетические операторы и новые архитектуры реализации генетического поиска, приведенные выше.

Рассмотрим пример размещения графа на плоскости с минимизацией L(G) (6.7). Пусть задана плоскость, на которую нанесена решетка в декартовой системе координат с осями s, t. Размеры решетки 2x5. Разместим в этой решетке граф G = (X, U), \Х\ = 10. На рис. 6.18 показаны два родительских сегмента (Р±, Р2) размещения вершин графа.

Здесь рі и р2 — две случайно выбранных хромосомы из популяции Р, которые моделируют альтернативные результаты размещения вершин графа в решетке. Применим к р± и р2 одноточечный ОК. Тогда

В р[ имеются повторяющиеся вершины (3, 5, 6, 4), поэтому использование стандартного одноточечного ОК нецелесообразно. Простая модификация любого стандартного ОК позволит получать реальные размещения. Используя модифицированный ОК, выбираем в р\ левый от точки ОК сегмент хромосомы и копируем его в р[. В р2 хромосоме выбираем правый от точки ОК сегмент и производим его анализ на предмет отсутствия повторяющихся генов. Все повторяющиеся гены исключаются из р[, а вместо

них добавляются отсутствующие элементы из левого сегмента р2. Тогда в рассматриваемом примере получим:

На рис. 6.19 показано возможное оптимальное размещение ячеек хромосомы р[ : (1, 2,3,4, 5, б, 8,10,9, 7) после применения модифицированного

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

Важным вопросом в метагенетическом алгоритме размещения является понятие шкал генетических операторов. Обозначим

размер популяции Р через Np, число генераций — No, число размещаемых вариантов для копирования — iV0ff. Тогда шкалы ОК и ОМ можно определить следующим образом:

Здесь ОК управляется посредством шкалы OK (i?,0k); R0к определяется как отношение числа потомков, полученных в каждой генерации ГА, к размеру популяции. Отметим, что R0к косвенно оценивает отношение числа точек разрыва (применение ОК) в областях, где ЦФ имеет лучшее значение, к числу точек разрыва в других местах популяций. Увеличение значения R0k (R0к >50) позволяет анализировать большее пространство и повышает шанс нахождения оптимума. В то же время большое значение Док требует огромных ресурсов вычислительного времени. Количество генераций в оптимизационной задаче можно находить по формуле

Здесь Ngп — количество генераций ГА, задаваемых пользователем.

Шкала мутации і?ом определяется как процент общего числа генов в популяции, которые в ней меняются местами (мутируют). Так, при размещении п вершин графа в решетке при размере популяции Np

В этом выражении nNp — число генов в популяции Р. Величина і?ом характеризует парный обмен генов при мутации. Шкалы остальных генетических операторов определяются аналогично.

Для размещения вершин графа в решетке можно использовать построение минимального кластера и агрегацию фракталов.

На рис. 6.19, а показан граф G = (X, U), \Х\ = 9, расположенный в решетке 3 х 3 с L(G) = 31.

Здесь в качестве ЦФ выбрана L(G). Необходимо из заданного хаоса (случайного расположения вершин) получить порядок с L(G) —min. Построим фрактальное множество. Для этого каждую строку решетки представим в виде одной вершины нового графа G\ с \Хі\ = 3. На рис. 6.19, б показан результат такого преобразования. Применим алгоритм агрегации фракталов. Кроме того, здесь также эффективно используются модифицированные ОМ, оператор инверсии и оператор сегрегации, разработанные авторами. На рис. 6.19, в приведен оптимальный результат расположения графа рис. 6.19, б в линейке.

После перехода от фрактального графа Gі к графу G получим расположение графа G в решетке, показанное на рис. 6.19, г. При этом L(G) = 25. Аналогичные преобразования для графа G (рис. 6.19, г) выполним при построении фракталов по столбцам (G2 с |Х2| = 3). Эти преобразования показаны на рис. 6.19, д. и 6.19, е. Окончательное размещение графа G (рис. 6.19, а) с L(G) = min = 20 приведено на рис. 6.19, ж. Заметим, что такие преобразования в графе, расположенном в решетке, можно выполнять не только по строкам и столбцам решетки, но и для области любой конфигурации.

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

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

Штейнера

Заключительным этапом конструкторского синтеза интегральных схем является комплексная трудоемкая задача, определяющая качество всего процесса — трассировка соединений [159, 160]. Задачу трассировки представляют в виде укрупненных четырех этапов: определение перечня соединений; размещение по слоям; определение порядка соединений; трассировка проводников.

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

Обычно ставится задача соединения заданных точек кратчайшим образом (сумма расстояний между точками должна быть минимальной или стремиться к ней). На рис. 6.21 показано одно из возможных кратчайших связывающих деревьев, построенных на основе алгоритма Прима [159]. Условная суммарная длина L(T) кратчайших связывающих деревьев расчитывается по формуле (6.5). Для примера рис. 6.21 получим ЦТ) = 23.

Для минимизации суммарной длины соединений в кратчайшем связывающим дереве предложено при соединении множества вершин (точек, контактов цепей) использовать дополнительные точки (вершины). Возникающую при этом задачу называют задачей Штейнера [118]. Она формулируется следующим образом. Для заданных п точек плоскости построить соединяющее их кратчайшее связывающее дерево сп' ) п точками (вершинами), общая суммарная длина соединений которого минимальна. Построенное таким образом дерево называется деревом Штейнера, дополнительные вершины — точками Штейнера. На рис. 6.22 показано одно из возможных деревьев Штейнера для пяти соединяемых контактов (рис. 6.20). Суммарная длина соединений дерева Штейнера (рис. 6.22) ЦТ) = 19 и введено две точки Штейнера (q\, q2). Задача Штейнера, как известно, является NP-полной. Для п = 3 известно точное решение задачи. Для п = 4 существует ряд эффективных алгоритмов. При п ^ 5 требуется огромное число

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

В [ 118] сформулирован ряд лемм и теорем о построении деревьев Штейнера. Так, при соединении трех контактов единственная точка Штейнера находится внутри прямоугольника, связывающего эти точки, причем координаты единственной точкой Штейнера определятся как Scp и tcp — значения щ при г = 1, 2, 3 и

где П[R] — длина периметра прямоугольника, построенного на трех точках. Так, для дерева Штейнера (рис. 6.22) qi и q2 будут иметь координаты, определяемые следующим образом:

Длина дерева Штейнера (рис. 6.22) определяется

Предложим простой эвристический алгоритм, временная сложность которого 0(п). Идея построения алгоритма заключается в следующем. Выбираются первые три точки из п точек, на которых должно быть построено дерево Штейнера. Согласно [118] строится оптимальный фрагмент дерева Штейнера для трех точек. Затем выбираются следующие по порядку три точки, одна из которых принадлежит построенному фрагменту. На этих точках строится второй оптимальный фрагмент дерева Штейнера. Далее процесс повторяется аналогично, пока не будет построено дерево Штейнера. Отметим, что каждый фрагмент дерева Штейнера оптимальный, но полное дерево Штейнера в общем случае может оказаться не оптимальным. При наличии достаточных вычислительных ресурсов или распараллеливания алгоритма можно строить оптимальные фрагменты по три вершины и, выполнив перебор, можно получить оптимальное или квазиоптимальное дерево Штейнера.

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

и L(T) = 22. Вертикальный столб можно проводить в любом месте плоскости (желательно в прямоугольнике, ограничивающем заданные точки). Аналогичным образом строится горизонтальный столб Штейнера и дерево Штейнера с использованием описанной выше идеи. На рис. 6.24 показано такое дерево Штейнера с двумя точками Штейнера и L(T) = 19.

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

Сначала, используя предложенные эвристические алгоритмы, строится популяция Р1 = ... ,р\}, каждый элемент популяции представляет

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

Рассмотрим пример. Пусть необходимо построить дерево Штейнера на пяти точках (рис. 6.20). Используя горизонтальные столбы Штейнера, построим четыре дерева Штейнера (рис. 6.25-6.28). На рис. 6.25 столб проходит через точку 1; на рис. 6.26 — через 4; на рис. 6.27 — через 5; на рис. 6.28 — через 3. Получили популяцию Р1 = {р\, р\}. Ко

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

Согласно вычисленной суммарной длине выбранных деревьев Штейнера, соответствующих хромосомам р\, р\, р\, р\, произведем сортировку деревьев Штейнера. Тогда в результате получим р\, р\, р\, р\. Построим новую популяцию Ри = {pli 1Р12 7р¥7Р1!}’ используя вертикальные столбы Штейнера. На рис. 6.23, 6.29-6.31 показаны четыре дерева Штейнера.

Произведя их сортировку, получим: р^1, р^1, р\, р{т. Выберем в качестве родительских пар элитные элементы из первой и второй популяций:

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

На рис. 6.32 показано дерево с двумя точками Штейнера и L(T) = = 20. После применения модифицированного оператора сегрегации здесь первый строительный блок позволил построить фрагмент, соединяющий точки 1 и 3. Второй строительный блок — точки 2, 5, и третий строительный блок позволил подсоединить точку 4. Отметим, что мы специально не включили в популяцию Р1 лучшее решение с горизонтальным столбом, проходящим через точку 2. При включении этого элемента в популяцию было бы получено другое дерево Штейнера с L(T) = 19. С увеличением числа точек время построения дерева Штейнера зависит от количества элементов популяции и числа генераций.

Определим ориентировочную трудоемкость алгоритма:

где tK — трудоемкость кодирования дерева Штейнера, іп — трудоемкость получения одного потомка, Nn — количество потомков, tc — трудоемкость оператора селекции, toc — трудоемкость оператора сегрегации. Отметим, что трудоемкость получения одного потомка меняется в пределах 0(п) —

—    0(п2) и временная сложность алгоритма для разработанных эвристических алгоритмов дерева Штейнера 0(п2).

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