Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока



жүктеу 153.14 Kb.
Дата29.02.2016
өлшемі153.14 Kb.

УДК 658.512.2.011.5


Нечеткий оператор кроссинговера для задачи трассировки коммутационного блока

Курейчик В.М. e-mail: kur@tsure.ru

Кныш Д.С. e-mail: wiseman33@ya.ru

Технологический институт ЮФУ в г. Таганроге


Описана одна из возможных схем нечеткого оператора кроссинговера в гибридных генетических алгоритмах для задачи трассировки коммутационного блока. Использование данной схемы дает преимущества по увеличению генетического разнообразия внутри популяции, что приводит к снижению вероятности преждевременной сходимости генетического алгоритма к локальным экстремумам целевой функции.
ВВЕДЕНИЕ
Задача трассировки коммутационного блока состоит в проведении электрических соединений между заданными терминалами сети внутри области трассировки, при соответствующих правилах проектирования, минимизируя длину соединений и интервал между ними [1].

Для оценки качества результатов трассировки используются три критерия оптимизации:



  • Межслойная емкость. Между проводниками печатной платы, находящимися на разных слоях, возникает емкостная связь, когда они пересекаются. Проводники, находящиеся друг над другом на смежных слоях, создают длинный пленочный конденсатор. Поэтому крайне важно уменьшить паразитную емкость.

(1)

В формуле (1.3) F1 определяет суммарную паразитную емкость проводников расположенных на разных слоях. Где - емкость, возникающая между парой пересекающихся проводников, расположенных на противоположных слоях и рассчитывается по формуле (2), а n – кол-во таких пар,



, (2)

где - диэлектрическая постоянная, А – площадь перекрытия, d – расстояние между слоями.



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

(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], к которым относятся одноточечный, двухточечный и равномерный операторы кроссинговера. В большинстве случаев количество точек кроссинговера и сами точки определяются случайным образом, именно на этом этапе я предлагаю ввести нечеткие методы, которые позволят определить оптимальные точки кроссинговера. Выбор точек кроссинговера зависит от значения оценки каждого гена, поскольку ген представляет собой конкретную топологию цепи, то в роли оценки предполагается использовать нечеткую целевую функцию оценки данной топологии коммутационного блока.
Расчет нечеткой целевой функции оценки топологии коммутационного блока
В типовой структуре нечеткого модуля можно выделить следующие компоненты [5-8]:


  • база знаний, которая включает информацию, данную экспертами в форме лингвистических правил управления;

  • интерфейс фаззификации (fuzzification), который преобразует четкий данные в нечеткие наборы;

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

  • интерфейс дефаззификации (defuzzification), который транслирует нечеткое управляющее воздействие;

В разработанном алгоритме используются три критерия определяющих решение задачи трассировки. Хорошее решение подразумевает малую длину соединений, малое число переходов и/или малую межслойную емкость.

Первоначально надо определить следующие составляющие [2]:


  • одно или набор правил;

  • определить правила предпочтения критериев;

  • определить функции принадлежности для каждого критерия.

Рассмотрим каждый пункт применительно к задаче трассировки.

Нечеткие правила. Поскольку три критерия определяют качество критерия то можно представить следующий набор правил:

  1. П1: ЕСЛИ (длина соединений малая и число переходов малое и емкость мала) ТО решение хорошее;

  2. П2: ЕСЛИ (длина соединений малая или число переходов мало) и емкость мала ТО решение хорошее;

  3. П3: ЕСЛИ длина соединений малая и (число соединений мало или емкость мала) ТО решение хорошее.

Т.е. нечеткие правила определяют значимость критериев. В данной работе используется правило П3.

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

ПП1: малая длина соединений более предпочтительна чем малое число переходов;

ПП2: малая длина соединений более предпочтительна чем малая емкость;

ПП3: малая длина соединений более предпочтительна, чем малое число переходов и малая емкость;

ПП4: малое число переходов более предпочтительно чем малая длина соединений.

Слово «предпочтительно» является лингвистической переменной, которая может принимать множество лингвистических значений таких как «сильное», «среднее» и «слабое». В данной работе используется значение «сильное» (более) и правило предпочтения ПП3.



Функции принадлежности. В разработанном алгоритме используются три лингвистические переменные (правило П3), для каждой из них необходимо определить функцию принадлежности. Эти три переменные будут полностью отражать топологию каждой цепи в отдельности.

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




Рис. 1 – График нормализованной функции принадлежности «малая длина соединений»


И рассчитывается по формуле 6
(6)

Малое число переходов. Поскольку в разработанном алгоритме используется зарезервированная модель, то минимальное число переходов можно так же определить из начальной топологии цепи. А максимальное число переходов так же в начальной популяции среди всех особей. График нормализованной функции принадлежности «малое число переходов» отражен на рис. 2.

И рассчитывается по формуле 7




Рис. 2 – График нормализованной функции принадлежности «малое число переходов»



(7)


Малая межслойная емкость. Поскольку алгоритм начальной генерации цепей не размещает их по слоям, то мы не сможем оценить данным способом минимальную межслойную емкость . Поэтому минимальное и максимальное значение определяется из начальной популяции среди всех особей. График нормализованной функции принадлежности отражен на рис. 3. И рассчитывается по формуле 8




Рис. 3 – График нормализованной функции принадлежности «малая межслойная емкость»



(8)


Расчет целевой функции в зависимости от применяемых нечетких операторов


Итак для задачи трассировки в нашем алгоритме используются три критерия длина соединений, число переходов и межслойная емкость. Взвешенная сумма этих критериев дает целевую функцию, все три критерия нормализованы по их верхней границе значений. Эти нечеткие критерии объединяются при помощи нечетких операторов таких как «И», «ИЛИ». В разработанном алгоритме могут использоваться несколько различных операторов, что даст возможность провести их оценку для задачи трассировки.



Не компенсирующие операторы. С не компенсирующими операторами применяется правило П3 согласно которому целевая функция рассчитывается по формуле 9

(9)

Если использовать правило предпочтения ПП3 с функцией принадлежности для лингвистической переменной «сильное предпочтение», целевая функция рассчитывается по формуле 10



(10)

Компенсирующие операторы. Целевая функция с учетом правила П3 и компенсирующим оператором Дюбуа и Прейда рассчитывается по формуле 11

, (11)

где


(12)

С учетом правила предпочтения ПП3 расчет осуществляется по формуле 13



, (13)

где функция принадлежности лингвистической переменной «сильное предпочтение».



Вероятностные операторы. При помощи вероятностных операторов целевая функция рассчитывается в соответствии с правилом П3 по формуле 14

(14)

На самом деле вероятностные операторы повторяют компенсирующие операторы при α=1.



Адъективная свертка. Было проведено много экспериментов использования адъективной свертки [29]. Следующие три правила используются совместно:

  • П1: ЕСЛИ длина соединений мала ТО решение хорошее;

  • П2: ЕСЛИ число переходов мало ТО решение хорошее;

  • П3: ЕСЛИ емкость малая ТО решение хорошее.

Таким образом, целевая функция является линейной комбинацией взвешенных критериев

, (15)

где - весовые коэффициенты назначенные правилам П1, П2,П3.



Среднее арифметическое. Другие правил вида:

ЕСЛИ (длина малая ИЛИ число переходов мало ИЛИ емкость малая) ТО решение хорошее,

где ИЛИ выполняется использованием оператора среднего арифметического представленного Ягером [34] в контексте многокритериальной задачи. Операторы «И», «ИЛИ» определяются следующим образом:



  1. «ИЛИ»

(16)

  1. «И»

(17)

Значение лежит в пределе от 0 до 1. Заметим, что при =1 расчет целевой функции совпадает с не компенсирующими операторами. А при =0 получаем среднее арифметическое критериев задачи.


Таким образом, мы получим нечеткое множество, мощность которого равна количеству цепей в коммутационном блоке, вида

.

Схема работы нечеткого оператора кроссинговера

№ цепи

1

2



n

Оценка

c1

c2



cn
Таким образом, каждая хромосома дополняется вектором оценок каждой топологии цепи данной хромосомы. В систему вводиться пороговый коэффициент kc, задаваемый экспертом. В результате селекции выбираются две родительские хромосомы с векторами оценок вида.

Сначала просматривается первая хромосома родитель и в векторе оценок выбираются оценки значение которых больше порогового коэффициента (условие 18).



(18)

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




1

2

3

4

5

0,64

0,45

0,78

0,32

0,82




1

2

3

4

5

0,45

0,23

1,00

0,00

0,56



Рассмотрим пример. Пусть имеются две родительские хромосомы с векторами оценок


1

2

3




4

5

0,64

0,45

0,78




0,32

0,82




1

2

3




4

5

0,45

0,23

1,00




0,00

0,56



Пусть пороговый коэффициент равен 0,75, в таком случае имеем одну точку кроссинговера. И в результате выполнения, которого хромосома потомок унаследует цепи № 1,2,3 из первой родительской хромосомы и цепи 4,5 из второй родительской хромосомы.

Результат работы нечеткого оператора кроссовера

Для анализа работы нечеткого оператора кроссинговера проводились сравнение работы генетического алгоритма с использованием n-точечного кроссовера и с использованием нечеткого кроссинговера, использующей нечеткую ЦФ. Исследования проводились для коммутационных блоков с количеством выводов от 16 до 32. Для этого проводились серии из пяти опытов для каждого типа коммутационного блока для генетического алгоритма с нечетким оператором кроссовера результаты приводятся в таблице 1. В качестве окончательной оценки работы алгоритма используется ЦФ, рассчитанная методом адъективной свертки. Сравнение полученных результатов отражено на графике (рис. 4).

Таблица 1

Результат работы генетического алгоритма с использованием нечеткого кроссинговера



Серия опытов

Число выводов в коммутационном блоке

16

20

24

29

32

ЦФ

Время, мм-сс

ЦФ

Время, мм-сс

ЦФ

Время, мм-сс

ЦФ

Время, мм-сс

ЦФ

Время, мм-сс

1

11,52

07-31

21,27

14-42

24,02

16-41

30,01

36-51

39,92

37-54

2

13,36

06-58

19,91

13-21

25,05

20-48

31,36

26-28

36,51

56-42

3

10,55

07-48

22,61

14-18

22,96

19-05

30,71

21-40

37,98

51-24

4

10,45

08-24

20,11

15-55

23,93

21-19

33,38

24-37

38,36

46-59

5

11,81

09-48

21,41

13-38

23,15

24-46

28,61

29-25

35,88

45-56

min значение

10,45

08-24

19,91

13-21

22,96

19-05

28,61

29-25

35,88

45-56



Рис. 4 – Зависимость ЦФ для ГА и НГА




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

Список литературы

  1. Shervani, N. Algorithms for VLSI physical design automation [текст] / Kluwer Academy Publisher – USA, 1995. – 538 p.

  2. Adiche H. Fuzzy Genetic Algorithm for VLSI Floorplan Design [текст] / Computer engineering, 1997.

  3. Курейчик, В.М. Генетические алгоритмы [текст] / Монография. Таганрог: ТРТУ, 1998. – 242 с.

  4. Гладков Л., Курейчик В.М., Курейчик В.В. Генетические алгоритмы [текст] / Учебное пособие, Ростов-на-Дону, РостИздаст, 2004.

  5. Lee, C. C. Fuzzy Logic in Control Systems: Fuzzy Logic Controller – Part 1 [текст] / IEEE Transactions on Systems, Man and Cybernetics, 1990, vol. 20, nr 2, s. 419-435.

  6. Cox E. The Fuzzy Systems Handbook [текст] / Academic Press, London 1994.

  7. Kruse R., Gebhardt J., Klawonn R. Foundation of Fuzzy Systems [текст] / John Wiley, Chichester, 1994.

  8. Yan J., Ryan M., Power J. Using Fuzzy Logic [текст] / Prentice Hall, London, 1994.

  9. Вороновский Г. К., Махотило К. В., Петрашев С. Н., Сергеев С. А. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности [текст] / Харьков: ОСНОВА, 1997. – 112 с.

  10. Гладков В. А., Зинченко Л. А., Курейчик В. В., Курейчик В. М., Лебедев Б. К., Нужнов Е. В., Сорокин С. Н. Методы генетического поиска [текст] / Под редакцией В. М. Курейчика. Таганрог: Изд-во ТРТУ, 2002. – 122 с.

  11. Курейчик В. М. Генетические алгоритмы и их применение [текст] / 2-е издание, дополненное. Таганрог: Изд-во ТРТУ, 2002. – 242 с.

  12. Скурихин А. Н. Генетические алгоритмы [текст] / Новости искусственного интеллекта. № 4. 1995.

  13. Frantz, D. R., Non-linearities in genetic adaptive search [текст]/ PhD thesis, University of Michigan, 1972.

  14. Lienig J. Channel and Switchbox Routing with Minimized Crosstalk – A Parallel Genetic Algorithm Approach [текст] / Tanner Research, 180 North Vinedo Avenue Pasadena, CA 91107, U.S.A, 1997.


©dereksiz.org 2016
әкімшілігінің қараңыз

    Басты бет