<<
>>

Организация процесса коллективной адаптации при перераспределении соединений между выводами в канале

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

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

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

плотность канала, число пересечений соединений, и т. п. Работа алгоритма направлена на минимизацию показателя L.

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

Введем в точках расположения выводов силы притяжения, действующие на подключенные к ним терминалы. Величина и направление сил характеризуют стремление соединения к пере­ключению.

Пусть Viи Vj— два вывода, подключенные к одной цепи, причем Viрасположен слева от Vj. Пусть Zij- — расстояние между Viи Vj. Тогда на терминал соединения, подключенный к выводу Vi,действует сила Fij = k ? lij, а на терминал соединения той же цепи, подключенный к выводу Vj, действует сила Fji= —k ? lij, где k — коэффициент.

Поскольку цепь подключается к нескольким выводам, то на терминал соединения, подключенного к выводу Vi, действует суммарная сила, определяемая как Fi= ∑ Fij.

j

На рис. 9.8 представлена цепь и действующие на терминалы цепи в точках подключения к выводам силы притяжения. При k=1

F1 = 3l1 + 2l2 + l3; F2 = 11 2l2 + l3;

F3 = —11 + 2і2+ l3; F4 = —11 — 2і2— 3⅛.

Отличительной особенностью такого подхода является то, что Fi= 0.

Рис. 9.8. Цепь и действующие на терминалы цепи в точках подключения к выводам силы притяжения

j

Это дает возможность объединять выводы в группы gijи вычис­лять суммарную силу притяжения F (gij∙), действующую на группу терминалов (соединений), подклю­ченных к группе gij. Например, пусть g11= {V1, V2, V3} (см. рис. 9.8). Тогда F (g11) = Ц+ 2l2+ 3l3, а F(g11) + F4 = 0. Наибольшие силы притяжения действуют на термина­лы, подключенные к крайним контактам соединения. Для рас­сматриваемого примера это силы F1и F4.

Объектами адаптации являются терминалы ац, подключен­ные к выводам Vk,и группы терминалов tij, подключенные

к выводам gij. Состояние среды характеризуется топологическим вариантом реализации заданной функции схемой. Фактически, это является вариантом подключения терминалов соединений к выводам и, как следствие, значениями сил притяжения, дей­ствующих на терминалы соединений в точках подключения к вы­водам.

Оценкой состояния объекта является действующая на него сила притяжения.

Локальная цель конкретного объекта α⅛ или tij∙ — достичь состояния, при котором сила притяжения, действующая в Vpили в gij∙, была бы равна 0. Глобальная цель коллектива объектов — достичь состояния среды, обеспечивающего благоприятные усло­вия для последующей трассировки (минимизация плотности ка­нала и числа пересечений).

Для организации процесса переключения на основе анализа множеств gij∙ эквивалентных групп выводов (ЭГВ) формируются множества непересекающихся пар эквивалентных групп выводов, что дает возможность одновременно (параллельно) реализовы­вать переключения во всех парах. Реализация процесса пере­ключения заключается в анализе пары эквивалентных групп выводов. Если соответствующие условия выполняются, то осу­ществляется взаимное переключение соединений между парой эквивалентных групп выводов.

Далее для каждой эквивалентной группы выводов рассчи­таем координаты геометрического центра. Пусть для заданной схемы имеется взаимное расположение геометрических центров со сквозной нумерацией вдоль ряда выводов. Рассмотрим один уровень (рис. 9.9).

Рис. 9.9. Формирование множества непересекающихся пар эквивалентных групп выводов: а — первый элемент пары нечетный; б — первый элемент пары четный

В пределах каждого gi+ι,j- формируются два множества непе- ресекающихся пар эквивалентных групп выводов, входящих в со­став g,i+ι,j.

В первое множество P1+ι jвходят пары (gik;gi,k+ι)такие, что значение к является нечетным числом, k = 1,3,5,..., (рис. 9.9, а).

Во втором множестве Pi2+1 j значение k является четным числом (рис. 9.9, б).

Переключение групп терминалов ti,k и ti,k+1 между эквива­лентными группами выводов gi,k и gi,k+1, соответствует переста­новке элементов tι. и L∙i^, ів векторе ti+1 j.

Поскольку в пределах P1нет пересекающихся пар, то мож­но осуществлять групповую перестановку параллельно всех пар элементов (tik,tik+1), соответствующих парам множества P . Аналогичное рассуждение справедливо и для множества P2.

Для реализации механизма адаптации каждому объекту tij сопоставляется автомат адаптации Aij, моделирующий поведе­ние объекта в среде. Автомат Aij имеет три группы состояний {Ci1j, Ci2j, Cj} (рис. 9.1o), соответствующие трем альтернативам переключения, и одно промежуточное состояние Sij.

о

Рис. 9.10

Если автомат адаптации находится в одном из состояний Cj, то группа терминалов tij∙стремится к переключению с эквива­лентной группы выводов 9ijна эквивалентную группу выводов 9i-1,j. Группа 9i-1,jрасположена слева от gij∙.

Состояние группы Cij соответствует «стремлению» tij∙ к пе­реключению с эквивалентной группы выводов 9ijна эквивалент­ную группу выводов 9i+1,j.

Группа 9i+1,jрасположена справа от эквивалентной группы выводов 9ij. Состояние Cijсоответствует отсутствию стремления к переключению (нейтральное положе­ние). Число состояний AA в каждой группе задается параметром Qk, где k — номер группы.

Переходы в автомате адаптации осуществляются над дей­ствием сигналов поощрения (+) и наказания (—). При выходе из группы автомат адаптации переходит в промежуточное состояние Sij. При этом, если в момент перехода из C2jсила притяжения на tijбыла направлена влево, то автомат адаптации переходит в группу Cj, а если сила притяжения была направлена вправо, то автомат адаптации переходит в группу

Ниже представлен псевдокод алгоритма адаптивной системы перераспределения соединений.

Algorithm ПЕРЕРАСПРЕДЕЛЕНИЕ СОЕДИНЕНИЙ begin

схема=ИСХОДНАЯ_СХЕМА;

Эквив_выводы=ИСХОДНЫЕ ДАННЫЕ; группы=ФОРМ(схема, эквив_выводы); пары=РАЗБИЕНИЕ(эквив_выводы); состоян_аа=НАЧ_СОСТОЯН_АА(группы) ; итерация=ЧИСЛО_ИТЕРАЦИЙ;

while (итерация > 0) do

{ подмнож=2; while (подмнож > 0) do

{

параметры=РАСЧЕТ(группы, схема); управл_состоян=УПРАВ(параметры, состоян_аа); состоян_аа=ПЕРЕХОД(состоян_аа, управл_состоян); группы=ПЕРЕКОМ(группы, подмнож, пары, состоян_аа); подмнож=подмнож-1;

};

итерация=итерация-1;

}; end

Исходными данными являются массивы схема и эквив_ выводы. В массиве схема описывается геометрия канала и элек­трическая схема, связывающая выводы канала и подлежащая трассировке в канале. В массиве эквив_выводы описываются группы выводов, сформированные на основе анализа внутренней схемы (т. е. схема расположенная внутри ячеек за пределами канала).

Подготовительный этап работы адаптивной системы включа­ет прежде всего формирование процедурой ФОРМ (схема, эк- вив_выводы) массива группы с описанием групп терминалов tij, соответствующих эквивалентных групп выводов gij.

Процедурой РАЗБИЕНИЕ (эквив_выводы) формируется массив пары в котором описывается два подмножества P1и P2 пар эквивалентных групп выводов.

C помощью процедуры НАЧ_СОСТОЯН (группа), формиру­ются автомат адаптации и фиксируются их начальные состояния с занесением этой информации в массив состоян_аа.

Число итераций работы адаптивной системы задается пара­метром ЧИСЛО_ИТТЕРАЦИЙ.

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

На каждом такте выполняются четыре шага. На первом шаге процедурой РАСЧЕТ(группы, схема) для каждой tij∙ опреде­ляется суммарный вектор сил притяжения, значение которого заносится в массив параметры. На втором шаге сравниваются между собой состояния объектов в среде и соответствующих им автоматов адаптации. Если они не противоречивы, т. е. на­правление перекоммутации, задаваемое автоматом адаптации, и направление силы притяжения совпадают, то вырабатывает­ся сигнал поощрения. Действия на втором шаге выполняются процедурой УПРАВ(параметры, состоян_аа), формирующей массив управл_сигнал со значениями управляющих сигналов. На третьем шаге по сигналу поощрения или наказания с по­мощью процедуры ПЕРЕХОД (состоян_аа,управл_сигнал) осуществляются переходы автоматов адаптации в новые состоя­ния. На четвертом шаге процедурой ПЕРЕКОМ (группы, под­множ, пары, состоян_аа), в соответствии с комбинацией состояний каждой пары автоматов адаптации рассматриваемого множества непересекающихся пар P1или P2, осуществляются или нет парные переключения соответствующих групп термина­лов.

Обозначим знаком → состояние автомата адаптации Aij, при котором группа терминалов tijстремится к переключению с экви­валентной группы выводов gij∙ на эквивалентную группу выводов gi-ι,j, расположенную слева от gij∙. Знаком обозначим состоя­ние автомата адаптации Aj, при котором группа терминалов tij∙ стремится к переключению с эквивалентной группы выводов gij∙ на эквивалентную группу выводов gi+ι,j∙, расположенную справа от эквивалентной группы выводов gij∙. Знаком 0 обозначим от­сутствие стремления к переключению (нейтральное положение).

Очевидными для взаимного переключения пары групп терми­налов являются следующие комбинации состояний соответству­ющей им пары автоматов адаптации: →^; → 0; 0 ^.

При детерминированном подходе перекоммутация осуществ­ляется для всех трех перечисленных типов комбинаций состоя­ний.

При вероятностном подходе задаются вероятности переком- мутации для каждой комбинации состояний.

Приведем рекомендуемые значения вероятностей перекомму- тации, установленные на основе экспериментальных исследова­ний:

— для комбинаций типа →^ (ситуация 1) вероятность пере- коммутации P1 = 1;

— для комбинаций типа 0 или → 0 (ситуация 2) вероятность перекоммутации P2 = 0,9 ÷ 1.

— для комбинаций типа → → или (ситуация 3) вероят­

ность перекоммутации P3= 0,4 ÷ 0,5.

— для комбинаций типа 00 (ситуация 4) вероятность переком- мутации P4= 0 ÷ 0,1.

— для комбинаций типа < →(ситуация 5) вероятность пере-

коммутации P5 = 0 ÷ 0,1.

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

Возможны две структуры адаптации: одноуровневая и мно­гоуровневая (иерархическая). В случае одноуровневой структу­ры, рассмотренной выше, на каждой итерации осуществляется совместная групповая перекоммутация на всех эквивалентных группах выводов.

В случае иерархического подхода множество непересекаю- щихся пар P1и P2разбивается на подмножества, включающие пары одного уровня P1= {Pi1| i = 1,2,3,...,ni}, P2= {Pi2| i = = 1,2,3,...,ni}.Уровень пары определен уровнем соответству­ющих вершин дерева эквивалентности D.Процесс адаптации осуществляется последовательно по уровням, начиная с высшего уровня. В начале идет адаптация на самом высшем уровне, т. е. рассматриваются подмножества Pjiи Pji,затем Pji-1 и Pji-1 и т. д.

Экспериментальные исследования показали, что использова­ние алгоритма дает снижение начальной плотности канала, сум­марной длины горизонтальных фрагментов и суммарного числа

неустранимых пересечений соединений. Временная сложность алгоритма при фиксированных значениях управляющих парамет­ров имеет оценку O(n),где n— число выводов.

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

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

Еще по теме Организация процесса коллективной адаптации при перераспределении соединений между выводами в канале:

  1. Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с., 2006
  2. 1. Коллективные субъекты административного права: понятие и виды
  3. Тема 6. Коллективные субъектыадминистративного права
  4. Фигуры, промежуточные между кругом и правильными многоугольниками
  5. Связь между дефектами структуры и оптическими неоднородностями в кристаллах.
  6. Жестко защемленные пластинки, форма которых является промежуточной между кругом и правильными многоугольниками
  7. Шарнирно опертые пластинки, форма которых является промежуточной между кругом и правильными многоугольниками
  8. 2. Принципы административного процесса
  9. 1.Сущность административного процесса
  10. Тема 13. Административный процесс