8769-1 (662916), страница 2
Текст из файла (страница 2)
Каждый раз после перехода к новой магистрали реализуется процедура резервации цель которой исключение возможности блокировки терминалов, лежащих по краям магистрали. Если терминалы левой и правой сторон коммутационного блока, лежащие на выбранной магистрали помечены цепями, то от них по магистрали проводятся горизонтальные фрагменты. От левого терминала вправо, от правого терминала влево. Фрагмент распространяется до ближайшего свободного столбца.
На рис.4а проведены горизонтальные фрагменты от терминалов 11 до 11 и от 21 до 22. В дальнейшем ДС1 и ДС2 трансформируются, т.е. они будут инцидентны терминалам 11 и 22 соответственно. Перед резервацией анализируется состояние столбцов и если необходимо и существует возможность формируется ближайший к терминалу свободный столбец.
Если есть несколько столбцов, занятых терминалами одной цепи и эти терминалы уже связаны, то их можно объединить в один терминал, что приводит к освобождению столбцов. Например на рис.4в при резервации терминала 23 два столбца заняты терминалами 12 и 12. 12 входит в ДС(11 , 12), 12 входит в ДС (12, 13), но они связаны и их можно объединить в один терминал12, при этом ДС(12,13) трансформируется в ДС (12, 13). Это приводит к освобождению столбца в который можно поместить терминал 23, связанный горизонтальным фрагментом с резервируемым терминалом 23.
Представим хромосому Hk виде матрицы Vk, где каждый столбец соответствует гену. Магистрали заполняются последовательно, начиная с первой. Заполнение магистралей осуществляется следующим образом. Вначале осуществляется резервация терминалов левой и правой сторон ОТ, лежащих на магистрали. Затем последовательно по строкам, начиная с первой в пределах строки слева направо просматриваются элементы матрицы Vk. Для каждого выбранного элемента матрицы (ДС) определяется возможность его размещения в формируемой магистрали. Если возможно, то ДС полностью или частично помещается в формируемую магистраль. Если ДС полностью помещается, то оно удаляется из матрицы Vk. Если ДС помещается частично, то трансформируется и остается в матрице. По окончании просмотра матрицы Vk осуществляется сжатие всех столбцов, из которых удалялись ДС, снизу вверх. После этого осуществляется переход к заполнению следующей магистрали. Процесс декодирования и заполнения магистралей показан на рис.5 и 6 для ОТ представленных соответственно на рис.1а и 1б. Отметим, что это фактически одна и та же задача трассировки.
Рассмотрим сначала процесс укладки в ОТ1, показанный на рис.1а. На рис.5а показаны два этапа заполнения первой магистрали: резервация и укладка. Вначале осуществляется резервация терминала 33, лежащего на 1-й магистрали. Для этого от терминала 33 проводится горизонтальный фрагмент до ближайшего свободного столбца. Терминал 33 резервируется терминалом 33, а ДС32=(32,33) трансформируется в ДС32=(32,33). Затем проводится укладка ДС в первую магистраль. Просматривается матрица Vk и первым выбирается ДС31=(31,32). ДС31 укладывается частично, при этом трансформируясь в ДС31=(31,32). Следующим из Vk выбирается ДС32, которое полностью помещается в первую магистраль и удаляется из Vk . Процесс заполнения завершается и Vk сжимается. На рис.5б заполняется вторая магистраль. Вначале резервируются терминалы 21 и 42, ДС21=(21,22) и ДС4=(41,42) трансформируются в ДС21=(21,22) и ДС4=(41,42).
Затем просматривается матрица Vk. ДС31 не помещается, ДС4 помещается полностью и удаляется из Vk , которое потом сжимается. На рис.5в,г,д, показан процесс укладки 3, 4, и 5-й магистралей.
При заполнении 3-й магистрали (рис.5в) в результате трансформации образуются ДС31=(31,32), ДС11=(11,12), ДС12=(12,13). Полностью помещается ДС31, частично ДС12 и ДС11.
При заполнении 4-й магистрали (рис.5г) при трансформации образуется ДС12=(12,13). Полностью помещаются ДС12, ДС22, ДС21.
При заполнении 5-й магистрали (рис.5д) полностью помещаются ДС11, ДС5.
Рассмотрим процесс заполнения ОТ2, представленной на рисунке 1б.
На рис.6а заполняется первая магистраль. Вначале резервируется терминал 51 лежащий на 1-й магистрали. ДС5=(51,52) трансформируется в ДС5=(51,52). Затем при просмотре Vk выбирается ДС11 которое частично укладывается в 1-ю магистраль и трансформируется в ДС11=(11,12).
При заполнении 2-й магистрали (рис.6б) вначале резервируется терминал 11 при этом ДС11 трансформируется в ДС11=(11,12). Для резервации терминала 23 формируется свободный столбец. Для этого терминалы 12 ДС11 и 12 ДС12, поскольку они уже связаны, объединяются в терминал 12, а столбец, занятый терминалом 12, освобождается. ДС12=(12,13)трансформируется в ДС12=(12,13). После этого терминал 23 резервируется терминалом 23, а ДС22=(22,23) трансформируется в ДС22=(22,23). При просмотре Vk полностью во 2-ю магистраль помещается только ДС11, которое удаляется из Vk.
При заполнении 3-й магистрали (рис.6в) резервируются терминалы 21 и 52. Трансформируются: ДС21=(21,22) в ДС21=(21,22), ДС5=(51,52) в ДС5=(51,52). Полностью помещается только ДС5, которое удаляется из Vk.
При заполнении 4-й магистрали (рис.6г) резервируется терминал 41. ДС4=(41,42) трансформируется в ДС4=(41,42). При просмотре Vk частично
помещается ДС12 и полностью ДС4. ДС12 трансформируется в ДС12=(12,13), а ДС4 удаляется из Vk.
При заполнении 5-й магистрали (рис.6д) резервируются терминалы 31.и 13. ДС31=(31,32) трансформируется в ДС31=(31,32), а ДС12=(12,13) в ДС12=(12,13). При просмотре Vk полностью помещаются ДС21, ДС22, ДС31, ДС12, которые удаляются из Vk.
При заполнении 6-й магистрали (рис.6е) полностью помещается ДС32.
При заданных способах кодирования ОТ1 и ОТ2, при декодировании хромосом Hk, соответствующих ОТ1 и ОТ2 и представляемых в виде вышеприведенных матриц Vk, конечные результаты совпали, хотя это и не является обязательным.
Матрица Vk просматривается при заполнении каждой магистрали. Размер матрицы Vk пропорционален числу s содержащихся в ней ДС.
s=k-n , где k - число терминалов, расположенных на границах ОТ, и n - число цепей. Отсюда оценка трудоемкости процедуры декодирования пропорциональна O(m*s).
Генетические операторы
Общая структура генетического поиска представлена на рис.7.
Предварительно осуществляется формирование структуры хромосомы. Эта процедура включает разбиение каждой цепи на ДСj, разбиение множества ДС на подмножества, определение числа и размера генов в составе хромосомы: определение состава каждого гена (т.е. определение ДС, входящих в каждый ген). Далее, случайным образом генерируется исходная популяция Пи хромосом размером М. Суть случайного формирования в том, что для каждого гена каждой хромосомы случайным образом устанавливается порядок расположения в нем элементов (ДС). Для каждой хромосомы рассчитывается фитнесс. Расчет фитнесса осуществляется на основе декодирования хромосомы, т.е. фактически решения задачи трассировки.
Целью генетического поиска является нахождение такой хромосомы и с таким расположением элементов в генах, которые обеспечивают при декодировании оптимальное значение фитнесса.
Основными генетическими операторами являются кроссинговер и мутация. В нашем случае операция кроссинговер реализуется путем вероятностного выбора родительской пары хромосом и формирования на ее основе потомков путем взаимооднозначного обмена гомологичными генами. В общем случае хромосомы могут обмениваться группами гомологичных генов. Оператор кроссинговера для выбранной пары выполняется следующим образом.
Задается вероятность кроссинговера Pk. Затем последовательно просматриваются пары гомологичных генов (генов, расположенных в одном и том же локусе хромосом), которые с заданной вероятностью Pk меняются местами. При выборе пары хромосом для кроссинговера используется принцип рулетки, при котором вероятность P(Hi) Выбора хромосомы Hi определяется как:
,
где Fi - фитнесс хромосомы Hi.
Число пар хромосом W является управляющим параметром процедуры генетического поиска.
В результате выполнения операции кроссинговера формируется дополнительная популяция Пк, которая объединяется с Пи и в дальнейшем подвергается мутации. Для каждой хромосомы популяции Пк рассчитывается фитнесс. Операция мутации заключается в выборе гена, который подвергается мутации и мутации этого гена. Мутация гена заключается в случайном выборе пары элементов, входящих в состав гена, и обмене местами их расположения в гене.
Реализация операции мутации осуществляется следующим образом. Задается вероятность мутации PM, последовательно просматриваются все хромосомы из популяции Пи+Пк, а в хромосоме все гены, и с заданной вероятностью PM ген мутирует. Мутация заключается в случайном выборе в гене пары элементов, которые затем обмениваются местами. Выполнение оператора мутации приводит к формированию дополнительной популяции Пм, для каждой хромосомы которой рассчитывается фитнесс.
Заключительной операцией в пределах одного поколения является селекция расширенной популяции Пт=Пи+Пк+Пм. В результате селекции на основе принципа рулетки отбирается новая популяция Пи лучших решений, которая является исходной для следующей генерации. Число генераций (поколений) Т, размер популяции М и параметры Рк и Рм являются управляющими параметрами, влияющими на эффективность процесса генетического поиска.
3. Экспериментальные исследования
Алгоритм был реализован на языке С++ для ПЭВМ типа IBM PC.
Первой целью экспериментальных исследований - было нахождение наилучшего сочетания значений управляющих параметров таких, как PМ, PК, М и Т, где М - объем популяции.
Исследования проводились следующим образом. Для каждого примера сначала фиксировалось значение РМ и изменялись параметры PК и М. Затем фиксировалось значение PК и изменялись PМ и М. Для каждого набора значений PМ, PК, и М проводилась серия из 10 экспериментов в результате которой определялось среднее, максимальное и минимальное значение Т, при котором не наблюдалось улучшения лучшего решения. Было установлено, что при значении PК=0,4 и PМ=0,1, М=50 и Т=130 обеспечивается нахождение оптимального решения.
Исследования трудоемкости алгоритма показали, что при фиксированных значениях PМ, PК, М и Т она имеет линейную зависимость и пропорциональна O(N), где N - число связываемых контактов.
Заключение
В статье был представлен генетический алгоритм трассировки в коммутационном блоке. При разработке структуры и методов кодирования и декодирования хромосом, генетических операторов использовались специфические знания о проблеме. Исследования показали достаточно высокую эффективность разработки генетических процедур.
Источником усовершенствования может стать правильная настройка параметров управления. Другая возможность состоит в том, чтобы при частичной укладке вводить более двух точек разрыва, что приведет к трансформации укладываемого ДС в несколько ДС.
Понятие верхней и нижней сторон ОТ относительно, поскольку ОТ можно развернуть на 180 и верхняя сторона станет нижней, а нижняя верхней. В связи с этим возможно использовать прием, заключающийся в чередовании порядка заполнения магистралей: первая сверху, первая снизу, вторая сверху, вторая снизу и т.д. При заполнении n-ой сверху магистрали последовательно просматриваются строки матрицы Vk, начиная с первой, а при заполнении n-й снизу магистрали строки матрицы Vk просматриваются в обратном порядке, начиная с последней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
