Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока
жүктеу/скачать 245.5 Kb.
|
УДК 658.512.2.011.5Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока Курейчик В.М. e-mail: kur@tsure.ru Кныш Д.С. e-mail: wiseman33@ya.ru Технологический институт ЮФУ в г. Таганроге Описана одна из возможных схем нечеткого оператора кроссинговера в гибридных генетических алгоритмах для задачи трассировки коммутационного блока. Использование данной схемы дает преимущества по увеличению генетического разнообразия внутри популяции, что приводит к снижению вероятности преждевременной сходимости генетического алгоритма к локальным экстремумам целевой функции. ВВЕДЕНИЕ Задача трассировки коммутационного блока состоит в проведении электрических соединений между заданными терминалами сети внутри области трассировки, при соответствующих правилах проектирования, минимизируя длину соединений и интервал между ними [1]. Для оценки качества результатов трассировки используются три критерия оптимизации:
 (1)
В формуле (1.3) F1 определяет суммарную паразитную емкость проводников расположенных на разных слоях. Где  , (2)
где
 (3)
В формуле (3) значение функции F2 определяет количество межслойных переходов. Viai – обозначает i–межслойный переход, i=[1,NumVia].
 (4)
F3 суммирует длину проводников всех цепей в коммутационном блоке (формула (4)). LenghtNeti – определяет длину проводников цепи i, где i меняется в периоде от 1 до количества цепей NumNet. Оператор кроссинговера Согласно определению, приведенному в [9, 10, 11], кроссинговер – это обмен гомологичными участками в различных точках гомологичных хромосом, приводящий к появлению нового сочетания сцепленных генов. В генетических алгоритмах оператору кроссинговера (ОК) отводится основная роль. ОК способствует образованию новых свойств у потомков из уже имеющегося генетического материала. Современные представления о механизме кроссинговера восходят к представлениям школы Т. Моргана, согласно которым рекомбинация заключается в разрыве гомологичных хроматид с последующим соединением их в новом сочетании [3]. В разработанном алгоритме хромосома представляет собой векторную структуру, где каждый вектор содержит участки трасс топологии i-ой цепи. Размер хромосомы равен количеству цепей в коммутационном блоке. Фактически такое представление хромосом представляет готовую топологию коммутационного блока и не требует декодирования. Похожий способ представления хромосом был представлен в работе [14]. Так же такой способ не зависит от модели коммутационного блока (зарезервированная или не зарезервированная). В приложениях, где использован простой генетический алгоритм (ПГА), наибольшее применение нашли классические операторы рекомбинации, работающие с бинарными строками [10, 11, 12, 13], к которым относятся одноточечный, двухточечный и равномерный операторы кроссинговера. В большинстве случаев количество точек кроссинговера и сами точки определяются случайным образом, именно на этом этапе я предлагаю ввести нечеткие методы, которые позволят определить оптимальные точки кроссинговера. Выбор точек кроссинговера зависит от значения оценки каждого гена, поскольку ген представляет собой конкретную топологию цепи, то в роли оценки предполагается использовать нечеткую целевую функцию оценки данной топологии коммутационного блока.
В разработанном алгоритме используются три критерия определяющих решение задачи трассировки. Хорошее решение подразумевает малую длину соединений, малое число переходов и/или малую межслойную емкость. Первоначально надо определить следующие составляющие [2]:
Рассмотрим каждый пункт применительно к задаче трассировки. Нечеткие правила. Поскольку три критерия определяют качество критерия то можно представить следующий набор правил:
Т.е. нечеткие правила определяют значимость критериев. В данной работе используется правило П3. Правила предпочтения. В дополнение нечетким логическим правилам можно ввести правила предпочтения одного критерия по отношению к другим, и тем самым акцентировать на нем внимание или же наоборот уменьшить его влияние. Правила предпочтения могут быть следующего вида: ПП1: малая длина соединений более предпочтительна чем малое число переходов; ПП2: малая длина соединений более предпочтительна чем малая емкость; ПП3: малая длина соединений более предпочтительна, чем малое число переходов и малая емкость; ПП4: малое число переходов более предпочтительно чем малая длина соединений. Слово «предпочтительно» является лингвистической переменной, которая может принимать множество лингвистических значений таких как «сильное», «среднее» и «слабое». В данной работе используется значение «сильное» (более) и правило предпочтения ПП3. Функции принадлежности. В разработанном алгоритме используются три лингвистические переменные (правило П3), для каждой из них необходимо определить функцию принадлежности. Эти три переменные будут полностью отражать топологию каждой цепи в отдельности. Малая длина соединений. Для начала мы определим два экстремума значений данного критерия. Минимальное значение  мы определим при помощи алгоритма формирования начального решения, т.к. данный алгоритм ищет минимальный маршрут прокладки соединений цепи. Максимальное значение  определяется на этапе генерации начальной популяции и является максимальной длиной соединений данной цепи во всех особях популяции. Далее мы нормализуем функцию принадлежности со значением . График функции принадлежности показан на рис. 1.
Рис. 1 – График нормализованной функции принадлежности «малая длина соединений» И рассчитывается по формуле 6 (6) Малое число переходов. Поскольку в разработанном алгоритме используется зарезервированная модель, то минимальное число переходов  можно так же определить из начальной топологии цепи. А максимальное число переходов  так же в начальной популяции среди всех особей. График нормализованной функции принадлежности «малое число переходов» отражен на рис. 2.
И рассчитывается по формуле 7
Рис. 2 – График нормализованной функции принадлежности «малое число переходов» (7)
Малая межслойная емкость. Поскольку алгоритм начальной генерации цепей не размещает их по слоям, то мы не сможем оценить данным способом минимальную межслойную емкость  . Поэтому минимальное и максимальное значение  определяется из начальной популяции среди всех особей. График нормализованной функции принадлежности отражен на рис. 3. И рассчитывается по формуле 8
Рис. 3 – График нормализованной функции принадлежности «малая межслойная емкость» (8) Расчет целевой функции в зависимости от применяемых нечетких операторовИтак для задачи трассировки в нашем алгоритме используются три критерия длина соединений, число переходов и межслойная емкость. Взвешенная сумма этих критериев дает целевую функцию, все три критерия нормализованы по их верхней границе значений. Эти нечеткие критерии объединяются при помощи нечетких операторов таких как «И», «ИЛИ». В разработанном алгоритме могут использоваться несколько различных операторов, что даст возможность провести их оценку для задачи трассировки. Не компенсирующие операторы. С не компенсирующими операторами применяется правило П3 согласно которому целевая функция рассчитывается по формуле 9  (9)
Если использовать правило предпочтения ПП3 с функцией принадлежности  (10)
Компенсирующие операторы. Целевая функция с учетом правила П3 и компенсирующим оператором Дюбуа и Прейда рассчитывается по формуле 11  , (11)
где
 (12)
С учетом правила предпочтения ПП3 расчет осуществляется по формуле 13  , (13)
где Вероятностные операторы. При помощи вероятностных операторов целевая функция рассчитывается в соответствии с правилом П3 по формуле 14  (14)
На самом деле вероятностные операторы повторяют компенсирующие операторы при α=1. Адъективная свертка. Было проведено много экспериментов использования адъективной свертки [29]. Следующие три правила используются совместно:
Таким образом, целевая функция является линейной комбинацией взвешенных критериев  , (15)
где Среднее арифметическое. Другие правил вида: ЕСЛИ (длина малая ИЛИ число переходов мало ИЛИ емкость малая) ТО решение хорошее, где ИЛИ выполняется использованием оператора среднего арифметического представленного Ягером [34] в контексте многокритериальной задачи. Операторы «И», «ИЛИ» определяются следующим образом:
 (16)
 (17)
Значение Таким образом, мы получим нечеткое множество, мощность которого равна количеству цепей в коммутационном блоке, вида  .
Схема работы нечеткого оператора кроссинговера
Сначала просматривается первая хромосома родитель и в векторе оценок выбираются оценки значение которых больше порогового коэффициента (условие 18).  (18)
Далее просматривается вторая хромосома родитель, и добавляются новые точки кроссовера. Если же нет оценок, удовлетворяющих условию 18, то пороговый коэффициент уменьшается, и процесс повторяется, пока не будет определена, хотя бы одна точка кроссинговера.
Рассмотрим пример. Пусть имеются две родительские хромосомы с векторами оценок
Пусть пороговый коэффициент равен 0,75, в таком случае имеем одну точку кроссинговера. И в результате выполнения, которого хромосома потомок унаследует цепи № 1,2,3 из первой родительской хромосомы и цепи 4,5 из второй родительской хромосомы. Результат работы нечеткого оператора кроссовера Для анализа работы нечеткого оператора кроссинговера проводились сравнение работы генетического алгоритма с использованием n-точечного кроссовера и с использованием нечеткого кроссинговера, использующей нечеткую ЦФ. Исследования проводились для коммутационных блоков с количеством выводов от 16 до 32. Для этого проводились серии из пяти опытов для каждого типа коммутационного блока для генетического алгоритма с нечетким оператором кроссовера результаты приводятся в таблице 1. В качестве окончательной оценки работы алгоритма используется ЦФ, рассчитанная методом адъективной свертки. Сравнение полученных результатов отражено на графике (рис. 4). Таблица 1 Результат работы генетического алгоритма с использованием нечеткого кроссинговера
Рис. 4 – Зависимость ЦФ для ГА и НГА Заключение Преимущества данного метода состоит в том, что при определении точек кроссинговера, от которых собственно зависит результат работы оператора, учитывается реальная оценка топологии коммутационного блока, а не случайный механизм. В то же время данный механизм отличается от банального выбора лучших генов, что приводит к вырождению популяции и следовательно преждевременной сходимости. Список литературы
жүктеу/скачать 245.5 Kb. Достарыңызбен бөлісу:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
- емкость, возникающая между парой 
- диэлектрическая постоянная, А – площадь перекрытия, d – расстояние между слоями.
для лингвистической переменной «сильное предпочтение», целевая функция рассчитывается по формуле 10
- весовые коэффициенты назначенные правилам П1, П2,П3. 
лежит в пределе от 0 до 1. Заметим, что при