<<
>>

Эволюционная трассировка в канале на основе символьных представлений

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

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

На первом этапе эволюционная модификация матрицы D производится путем выборочных групповых парных перестановок соседних элементов в столбцах. Адаптивный процесс состоит из повторяющихся шагов, каждый из которых представляет собой переход от одного решения (состояния матрицы D) к другому — лучшему [10.2]. Это обеспечивает направленное последователь­ное перемещение элементов в столбцах матрицы D. Глобальная цель адаптивного процесса — ликвидация вертикальных и гори­зонтальных конфликтов между горизонтальными фрагментами.

На каждом шаге анализируются пары элементов в столбцах матрицы D. Анализ осуществляется за четыре такта.

На каждом такте рассматриваются множество непересекаю- щихся пар элементов (dij, di+1,j) матрицы D, каждая из которых расположена в одном j-м столбце и в двух соседних строках іи i + 1. Отметим, что первый элемент пары расположен над вторым элементом пары. Будем в дальнейшем первый элемент пары называть верхним, а второй нижним.

На первом такте анализируется множество P1 непересека- ющихся пар элементов, у которых j — нечетное число, i — нечетное число:

На втором такте анализируется множество P2 непересекаю- щихся пар элементов, у которых j — четное число, i — нечетное число:

На третьем такте анализируется множество P3 непересекаю- щихся пар элементов, у которых j — нечетное число, і — четное число:

На четвертом такте анализируется множество непересекаю- щихся пар элементов, у которых j — четное число, і — четное число:

На рис. 1o.1o показаны механизмы, в соответствии с кото­рыми образуются подмножества пар. Пара элементов в столбце помечена одной цифрой.

Рис. 10.10. Механизмы образования подмножества пар

Пары элементов на каждом такте анализируются независимо друг от друга. По результатам анализа принимается решение о перестановке элементов каждой пары. Локальная цель переме­щения элемента dijв столбце j матрицы D — достижение им позиции i, в которой у элемента dij∙ отсутствуют вертикальные и горизонтальные конфликты с остальными элементами матрицы D. Глобальная цель — формирование решения задачи канальной трассировки в минимальном числе магистралей.

В процессе анализа для каждого элемента матрицы D (с ненулевым значением), соответствующего некоторому участку fi, определяется его состояние, т.

е. наличие или отсутствие горизонтальных и вертикальных конфликтов с остальными эле­ментами матрицы D в соответствии с их расположением в мат­рице. Если элемент dkiнаходится в горизонтальном конфликте с каким-либо элементом dkj, расположенным в той же строке, что и dki,то оба они помечаются меткой т. е. dkiи dkj∙ необходимо разнести по разным строкам. Пусть, в соответствии с расположением элементов в матрице D, элемент dpiнаходится в вертикальном конфликте с каким-либо элементом dij, причем для его ликвидации необходимо dpiпоместить выше dij. Тогда dpiпомечается меткой ↑, а элемент dij меткой J. Если элемент dpiне конфликтует с другими элементами матрицы D, т. е. для него отсутствуют нарушения ограничений, задаваемых графом вертикальных и горизонтальных ограничений, то элемент dkiпо­мечается меткой 0. Метки J и ↑ суммируются. Если число меток J больше числа меток ↑, то окончательно элемент помечается

одной меткой j. И наоборот. Если же число меток j равно числу меток ↑, то окончательно элемент случайным образом помечается либо меткой 0, либо меткой J. Отметим, что возможна ситуация, когда отдельные элементы могут быть помечены парой меток, одна из которых — а другая — либо ↑, либо j. В этом случае остается только одна метка: соответственно либо ↑, либо j.

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

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

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

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

Для реализации механизма адаптации каждому объекту (эле­менту dijматрицы D) сопоставляются два автомата адаптации (AA), Ai1j и A2j, моделирующих поведение объекта адаптации в среде. Aвтомaт Aij управляет перестановками элемента dij матрицы D в том случае, когда он является верхним элементом пары, а Ai2jуправляет перестановками элемента dij матрицы D в том случае, когда он является нижним элементом пары. Число групп состояний AA равно числу возможных альтернатив при

перестановке элемента dij. Aij. Таких альтернатив три: перестав­лять (y), не переставлять (n), нейтральное положение (e).

Не нарушая общности, рассмотрим принципы функциони­рования одного автомата адаптации. Автомат адаптации име­ет 3 группы состояний {Cij, Cij, Cij}. Если автомат адаптации находится в группе Ci1j∙, то соответствующий ему элемент dij стремится к перестановке со вторым элементом рассматриваемой пары (альтернатива V1). Cjj- соответствует запрету перестановки для dij (альтернатива V3). C2j- — нейтральное состояние (альтер­натива V2). Граф-схема переходов автомата адаптации показана на рис. 7.9.

На каждой итерации работа адаптивного алгоритма трасси­ровки осуществляется за четыре шага. На каждом шаге рассмат­ривается одно из подмножеств пар P1,P2,P3,P4.

На каждом шаге выполняется 4 такта.

На 1-м такте определяется состояние каждого элемента dij в соответствии с его расположением в матрице D. В результате элементы помечаются метками, как указано выше.

На 2-м такте сравниваются между собой состояния объектов в среде и соответствующих им автомат адаптации. Последова­тельно просматриваются все пары рассматриваемого подмноже­ства. Для каждой пары сначала рассматривается верхний эле­мент, а потом нижний.

Если рассматривается верхний элемент, то сигнал поощрения вырабатывается при следующих комбинациях состояний элемен­та и автомата адаптации: j y, ↑ n, J y,0e, а сигнал наказания вы­рабатывается при следующих комбинациях состояний элемента и автомата адаптации: ↑ y, J n, j n. Сигнал подается на автомат адаптации Aj.

Если рассматривается нижний элемент, то сигнал поощрения вырабатывается при следующих комбинациях состояний элемен­та и автомата адаптации: ↑ y, j n, J y,0e, а сигнал наказания вы­рабатывается при следующих комбинациях состояний элемента и автомата адаптации: ↑ n, J n, j y. Сигнал подается на автомат адаптации Ai2j

ij

На 3-м такте по сигналу поощрения или наказания произво­дится переход автомат адаптации в новое состояние в соответ­ствии с алгоритмом поведения автомата адаптации.

На 4-м такте в соответствии с комбинацией состояний ав­томата адаптации Aj и A2+1 j∙ осуществляются или нет парные перестановки в каждой паре (dij, di+1,j∙), принадлежащей рас­

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

(ye). (ey).

Эксперименты показали, что в ряде случаев в это число можно включить и ситуации типа (ее). Такое включение поз­воляло выйти из локального оптимума при трассировки. Было определено, что быстрее всего алгоритм сходится при значении параметра Qj равным 1 ÷ 3.

Работа адаптивной процедуры завершается в двух случаях.

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

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

Строки матрицы Dkзаполняются элементами матрицы D последовательно, начиная с первой. Заполнение строки матрицы Dkосуществляется следующим образом. Последовательно по строкам, начиная с первой, в пределах строки слева направо про­сматриваются элементы матрицы D и определяется возможность их размещения в формируемой строке матрицы Dkв соответ­ствии с Gy и Gh. Если возможно, то элемент помещается в фор­мируемую строку матрицы Dkи удаляется из D. По окончании просмотра матрицы D осуществляется переход к заполнению следующей строки матрицы Dkи т. д., пока не обнулится мат­рица D. Временная сложность адаптивной процедуры на одном шаге — O(n). Сравнение с известными алгоритмами показало,

что при меньшем времени работы новый алгоритм дает более качественные решения.

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

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

характеризующее ухудшение состояний анализируемой пары.

Во втором подходе используется одна из структур генетиче­ского поиска [1o.12]. Популяция представляет собой множество матриц D (закодированных в виде хромосом). Декодирование, т. е. получение решения, осуществляется с помощью вышеопи­санной адаптивной процедуры.

Хромосома Нкявляется упорядоченной совокупностью ге­нов gik. Значением gikявляется некоторый вектор dk, соответству­ющий столбцу матрицы D. Гены gikи g хромосом Нки го­мологичны, они одинаковы по составу элементов, соответствуют одному и тому же подмножеству фрагментов Fi, но отличаются порядком расположения элементов.

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

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

Наилучшие результаты были достигнуты при значениях веро­ятности кроссинговера Рк= o.6, вероятности мутации Рм= o.1. Исследования трудоемкости алгоритма показали, что на одной итерации при фиксированных значениях Рм, Рк, размера попу­ляции М, числе генераций Tона пропорциональна O(N), где N— число связываемых контактов.

На рис. 1o.11 представлен совмещенный в одном слое эскиз трассировки для стандартного тестового примера EX 3а, разрабо­танного с помощью описанного выше алгоритма.

Рис. 10.11. Эскиз трассировки для стандартного тестового примера EXЗа

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

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Эволюционная трассировка в канале на основе символьных представлений:

  1. § 3. Порядок подачи надзорных жалоб и представлений прокурора
  2. Генезис теоретических представлений о персональных финансах[3]
  3. Графическое представление решений для пластинок в виде треугольников
  4. 3.1 Аналитическое представление зависимости максимальный прогиб - основная частота колебаний в упругих пластинках
  5. § 3. Обязанности банков по представлению налоговым органам сведений о финансово-хозяйственной деятельности налогоплательщиков
  6. 1. Правовые основы системы образования
  7. 3. Основы административно-правового статуса граждан
  8. 2.2 Технология получения КМ на основе алюминия (Al-3масс.%Ni- 1масс.%Cu)
  9. Тема 18. Правовые основы управления образованием
  10. II ТЕОРЕТИЧЕСКИЕ ОСНОВЫ МЕТОДА ИНТЕРПОЛЯЦИИ ПО КОЭФФИЦИЕНТУ ФОРМЫ
  11. ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ И МЕТОДОЛОГИЧЕСКИЕ ОСНОВЫ РАЗВИТИЯ ПЕРСОНАЛЬНЫХ ФИНАНСОВ
  12. 1.7. Влияние OA на характеристики оптических, оптоэлектронных и лазерных устройств на основе кристаллов.
  13. 34. Наем жилого помещения на коммерческой основе: юридическая характеристика, элементы, срок, отличие от договора социального найма.
  14. Глава I. ТЕОРЕТИЧЕСКИЕ И ЭМПИРИЧЕСКИЕ ОСНОВЫ ВКЛЮЧЕНИЯ ЛИЧНОСТНЫХ РЕЗУЛЬТАТОВ ОБУЧЕНИЯ В СОСТАВЕ СОДЕРЖАНИЯ ОБРАЗОВАНИЯ