Лебедев О.Б. - Генетический алгоритм глобальной трассировки

Экспериментальные исследования генетического алгоритма глобальной трассировки

Алгоритм глобальной трассировки был реализован на языке С++, экспериментальные исследования проводились на ЭВМ типа IBM PC/AT Pentium 133.
При проведении экспериментальных исследований преследовались две цели:
Первой целью являлось исследование механизмов генетического поиска для задачи глобальной трассировки. Для достижения этой цели исследовалось влияние управляющих операторов, таких как: размер популяции М, число поколений Т, вероятность мутации РМ, вероятность кроссинговера РК. В результате этих исследований определялось такое сочетание значений этих параметров, которое обеспечивает наивысшую эффективность генетических процедур для задачи глобальной трассировки.
Второй целью являлось исследование собственно, эффективности разработанного генетического алгоритма. Исследовались влияния таких параметров, как число вариантов маршрутов для каждого ребра.
Для проведения исследований были синтезированы 5 тестовых примеров.
Основные характеристики примеров.
Использовалось КП с размерами 10*10 (10 дискретов по горизонтали и 10 дискретов по вертикали). Выводы, связываемые цепями, размещались внутри дискретов. В каждом дискрете только один вывод одной цепи. Число выводов, связываемых одной цепью – от 2 до 5. В один дискрет назначалось до 10 выводов. Среднее число цепей – 200-250. Назначение выводов в дискреты осуществлялось случайным образом.
Оптимизация проводилась по критерию:
F1=m [Cmin<Ci=ai-bi]
Если оказывалось, что Сmin<0, то оптимизация автоматически переключалась на критерий F2 = m - g, где g – число ребер, проходящих через грани с отрицательным значением Сmin.
Для нахождения наилучшего сочетания таких параметров, как Рм, Рк, М и Т, а также для выбора последовательности и типа генетических операторов экспериментальные исследования проводились следующим образом:
Для каждого примера сначала фиксировался параметр Рм и изменялись параметры Рк и М. Проводилась серия из десяти экспериментов для каждого фиксированного набора параметров. Затем фиксировался параметр Рк. Формирование исходной популяции осуществлялось следующим образом. Для каждой цепи строилось МСД. Если в процессе его построения возможно несколько альтернатив, то выбиралась первая. Для каждого ребра каждого дерева формировался набор вариантов маршрутов. Для каждой хромосомы исходной популяции выбор вариантов осуществлялся случайным образом.
При проведении испытаний для каждого эксперимента фиксировался номер генерации, после которой не наблюдалось улучшения оценки. В каждой серии из десяти испытаний фиксировались минимальные, максимальные и средние числа генераций.
Для каждой серии испытаний определялось лучшее решение, которое фактически являлось оптимальным. Затем фиксировалось число испытаний, при которых были получены оптимальные решения, число испытаний при которых были получены решения отличающиеся от оптимальных менее чем на 5%, и число испытаний, при которых решения отличались от оптимального более чем на 5%.
Экспериментальные исследования показали, что наилучшим является следующее сочетание управляющих параметров: Рм=0.2, Рк=0.4.
На основе обработки экспериментальных исследований была построена зависимость качества решений от числа генераций.
В качестве аналога для сравнения выбран алгоритм WRST [6], основанный на последовательном построении взвешенных деревьев Штейнера. В алгоритме WRST также как и в рассмотренном в статье, каждая цепь представляется в виде связывающего дерева, построенного алгоритмом Прима, на основе которого последовательно строится дерево Штейнера с учетом веса ребер и динамически изменяющейся в процессе построения среды (коммутационного поля).
В таблице 1. представлены результаты сравнения экспериментальных данных с аналогом для пяти примеров.
В колонках F приводятся усредненные значения критерия F для генетического алгоритма (ГА) и для алгоритма WRST.
В колонке L приводится суммарная длина, а в колонке t время работы алгоритма.
Как видно из таблицы генетический алгоритм обеспечивает более качественное решение, причем время решения на 10-40% меньше.
Сравнение с алгоритмами, использующими идею волнового алгоритма Ли, не проводилось, так как они дают худшие результаты, чем WRST[83].

Таблица 1.

№	F		L		T
	ГА	WRST	ГА	WRST	ГА	WRST
1	+2	0	4212	4570	33	37
2	+3	0	3870	4610	31	34
3	+1	-2	5180	5900	57	69
4	+3	+1	4256	4570	59	61
5	+2	0	3650	4220	29	34

Список использованной литературы

1. J.Soukup. Fast wise router .Proceedings of 15th Design Automation Conference, pages 100-102 ,1972.

2. J.Heisterman and T.Lengauer .The efficient solution of integer programs for hierar-chical global routing . IEEE Transactions on Computer-Aided Design, CAD 10(6): 748-753, Jane 1991.

3. C.Chang , M.Sarrafzadeh ,and C.K. Wong .A powerful global router :Based on sterner min-max trees .Proceedings of IEEE International Conference on Computer-Aided Design, pages 2-5 , November 7-10 1989.

4. S.Burman , H .Chen ,and N. Sherwani . Improved global routing using – geometry .Proceedings of 29th Annual Allerton Conference on Communications , Computing , and Control .October 1991 .

5. J.M. Ho , G. Vijayan , and C. K . Wong . A new approach to the rectilinear Sterner tree problem . IEEE Transactions on Computer–Aided Design , 9(2): 185-193 , Feb-ruary 1985 .

6. Селютин В.А. Автоматизированное проектирование топологии БИС .–М.:Радио и связь , 1983,-112 с .C.Chiang, M.Sarrafradeh, C.K.Wong. A Weighted-Steiner-Tree-Based Global Router, Manuscript, 1992.