Реферат: Трассировка в коммутационном блоке на основе генетических процедур
При заполнении 4-й магистрали (рис.5г) при трансформации образуется ДС12¢¢=(1¢¢2 ,1¢3 ). Полностью помещаются ДС12¢, ДС22, ДС21¢.
При заполнении 5-й магистрали (рис.5д) полностью помещаются ДС11¢, ДС5.
Рассмотрим процесс заполнения ОТ2, представленной на рисунке 1б.
На рис.6а заполняется первая магистраль. Вначале резервируется терминал 51 лежащий на 1-й магистрали. ДС5=(51 ,52 ) трансформируется в ДС5¢=(5¢1 ,52 ). Затем при просмотре Vk выбирается ДС11 которое частично укладывается в 1-ю магистраль и трансформируется в ДС11¢=(11 ,1¢2 ).
При заполнении 2-й магистрали (рис.6б) вначале резервируется терминал 11 при этом ДС11¢ трансформируется в ДС11¢¢=(1¢1 ,1¢2 ). Для резервации терминала 23 формируется свободный столбец. Для этого терминалы 1¢2 Î ДС11¢¢ и 12 Î ДС12, поскольку они уже связаны, объединяются в терминал 1¢2 , а столбец, занятый терминалом 12 , освобождается. ДС12=(12 ,13 )трансформируется в ДС12¢=(1¢2 ,13 ). После этого терминал 23 резервируется терминалом 2¢3 , а ДС22=(22 ,23 ) трансформируется в ДС22¢=(22 ,2¢3 ). При просмотре Vk полностью во 2-ю магистраль помещается только ДС11¢¢, которое удаляется из Vk .
При заполнении 3-й магистрали (рис.6в) резервируются терминалы 21 и 52 .Трансформируются: ДС21=(21 ,22 ) в ДС21¢=(2¢1 ,22 ), ДС5¢=(5¢1 ,52 ) в ДС5¢¢=(5¢1 ,5¢2 ). Полностью помещается только ДС5¢¢, которое удаляется из Vk .
При заполнении 4-й магистрали (рис.6г) резервируется терминал 41 . ДС4=(41 ,42 ) трансформируется в ДС4¢=(4¢1 ,42 ). При просмотре Vk частично
помещается ДС12¢ и полностью ДС4¢. ДС12¢ трансформируется в ДС12¢¢=(1¢¢2 ,13 ), а ДС4¢ удаляется из Vk .
При заполнении 5-й магистрали (рис.6д) резервируются терминалы 31 .и 13 . ДС31=(31 ,32 ) трансформируется в ДС31¢=(3¢1 ,32 ), а ДС12¢¢=(1¢¢2 ,13 ) в ДС12¢¢¢=(1¢¢2 ,1¢3 ). При просмотре Vk полностью помещаются ДС21¢, ДС22¢, ДС31¢, ДС12¢¢, которые удаляются из Vk .
При заполнении 6-й магистрали (рис.6е) полностью помещается ДС32.
При заданных способах кодирования ОТ1 и ОТ2, при декодировании хромосом Hk , соответствующих ОТ1 и ОТ2 и представляемых в виде вышеприведенных матриц Vk , конечные результаты совпали, хотя это и не является обязательным.
Матрица Vk просматривается при заполнении каждой магистрали. Размер матрицы Vk пропорционален числу as содержащихся в ней ДС.
as =ak -an , где ak - число терминалов, расположенных на границах ОТ, и an - число цепей. Отсюда оценка трудоемкости процедуры декодирования пропорциональна O(m*as ).
Генетические операторы
Общая структура генетического поиска представлена на рис.7.
Предварительно осуществляется формирование структуры хромосомы. Эта процедура включает разбиение каждой цепи на ДСj , разбиение множества ДС на подмножества, определение числа и размера генов в составе хромосомы: определение состава каждого гена (т.е. определение ДС, входящих в каждый ген). Далее, случайным образом генерируется исходная популяция Пи хромосом размером М. Суть случайного формирования в том, что для каждого гена каждой хромосомы случайным образом устанавливается порядок расположения в нем элементов (ДС). Для каждой хромосомы рассчитывается фитнесс. Расчет фитнесса осуществляется на основе декодирования хромосомы, т.е. фактически решения задачи трассировки.
Целью генетического поиска является нахождение такой хромосомы и с таким расположением элементов в генах, которые обеспечивают при декодировании оптимальное значение фитнесса.
Основными генетическими операторами являются кроссинговер и мутация. В нашем случае операция кроссинговер реализуется путем вероятностного выбора родительской пары хромосом и формирования на ее основе потомков путем взаимооднозначного обмена гомологичными генами. В общем случае хромосомы могут обмениваться группами гомологичных генов. Оператор кроссинговера для выбранной пары выполняется следующим образом.
Задается вероятность кроссинговера Pk . Затем последовательно просматриваются пары гомологичных генов (генов, расположенных в одном и том же локусе хромосом), которые с заданной вероятностью Pk меняются местами. При выборе пары хромосом для кроссинговера используется ²принцип рулетки², при котором вероятность P(Hi ) Выбора хромосомы Hi определяется как:
,
где Fi - фитнесс хромосомы Hi .
Число пар хромосом W является управляющим параметром процедуры генетического поиска.
В результате выполнения операции кроссинговера формируется дополнительная популяция Пк, которая объединяется с Пи и в дальнейшем подвергается мутации. Для каждой хромосомы популяции Пк рассчитывается фитнесс. Операция мутации заключается в выборе гена, который подвергается мутации и мутации этого гена. Мутация гена заключается в случайном выборе пары элементов, входящих в состав гена, и обмене местами их расположения в гене.
Реализация операции мутации осуществляется следующим образом. Задается вероятность мутации PM , последовательно просматриваются все хромосомы из популяции Пи+Пк, а в хромосоме все гены, и с заданной вероятностью PM ген мутирует. Мутация заключается в случайном выборе в гене пары элементов, которые затем обмениваются местами. Выполнение оператора мутации приводит к формированию дополнительной популяции Пм, для каждой хромосомы которой рассчитывается фитнесс.
Заключительной операцией в пределах одного поколения является селекция расширенной популяции Пт=Пи+Пк+Пм. В результате селекции на основе ²принципа рулетки² отбирается новая популяция Пи лучших решений, которая является исходной для следующей генерации. Число генераций (поколений) Т, размер популяции М и параметры Рк и Рм являются управляющими параметрами, влияющими на эффективность процесса генетического поиска.
3. Экспериментальные исследования
Алгоритм был реализован на языке С++ для ПЭВМ типа IBMPC.