4479-1 (Генетический алгоритм глобальной трассировки), страница 3
Описание файла
Документ из архива "Генетический алгоритм глобальной трассировки", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "4479-1"
Текст 3 страницы из документа "4479-1"
Экспериментальные исследования показали, что наилучшим является следующее сочетание управляющих параметров: Рм=0.2, Рк=0.4.
На основе обработки экспериментальных исследований была построена зависимость качества решений от числа генераций.
В качестве аналога для сравнения выбран алгоритм WRST [7], основанный на последовательном построении взвешенных деревьев Штейнера. В алгоритме 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 | ||
5. Заключение
Приведена формулировка задачи глобальной трассировки. Определены перспективные критерии оптимизации. Разработана структура хромосомы, принципы ее кодирования и декодирования, использующие знания о задаче глобальной трассировки, исключающие возникновение неэффективных решений и повышающих скорость проектирования. Модернизированы и реализованы новые механизмы генетических процедур кроссинговера, мутации, смены популяций. Разработан генетический алгоритм глобальной трассировки на базе новых структур хромосом и модифицированных генетических процедур. Проведены экспериментальные исследования генетического алгоритма глобальной трассировки. Определены оптимальные сочетания значений управляющих параметрами М, Т, Рм, Рк. Проведено сравнение с аналогом показавшее, что разработанный алгоритм позволяет сократить сроки проектирования на 10-40%.
Список литературы
J.Soukup. Fast wise router .Proceedings of 15th Design Automation Conference, pages 100-102 ,1972.
J.Heisterman and T.Lengauer .The efficient solution of integer programs for hierarchical global routing . IEEE Transactions on Computer-Aided Design, CAD 10(6): 748-753, Jane 1991.
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.
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 .
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 , February 1985 .
Селютин В.А. Автоматизированное проектирование топологии БИС .-М.:Радио и связь , 1983,-112 с .C.Chiang, M.Sarrafradeh, C.K.Wong. A Weighted-Steiner-Tree-Based Global Router, Manuscript, 1992.
