一种动态数据结构——池及其在VLSI电路布局设计中的应用
|
摘要
本文提出一个新的数据结构概念——动态数据结构。基于这个概念，本
文实现了一种新的数据结构——池及其在一维和二维时的情况。本文同时对
这种新的数据结构在VLSI电路布局设计中的应用和在打印机任务调度中的
应用进行了研究。
本文的主要贡献概括如下：
1.本文讨论了各种计算机应用中的动态数据处理要求，之后提出了动
态数据结构的概念。根据这一新概念，本文建议了一种新的数据结
构——池，它能对数据进行动态处理（例如，数据的表示，查找，
合并，排序和存储等等）。
2.本文研究了一维池和二维池的实现，对一维池和二维池的顺序存
取、基于周期机制和基于触发机制的动态秩序维持程序进行了研
究，并定义了一维池和二维池的基本运算。
3.本文成功地将池和遗传算法相结合，形成改进的基于池的遗传算法
（PGA），以作为池的一种灵活应用。然后，将基于池的遗传算法
（PGA）用于解决门阵列布局设计。对门阵列布局算例的计算机仿
搞要
真结果表明使用基于池的遗传算法汀GA）能够获得比传统遗传算
法（GA）更好的结果。
4．本文将快速进化规划算法（FEP）用于同样的门阵列布局算例，也
取得了满意的结果。
5．为减小通道布线中线网间的串扰，本文提出一个基于扰动的算法。
我们将此算法运用到若干benchlnn例子上去，并和已知的一些结
果进行了比较，结果表明我们建议的基于扰动的算法能够获得比文 甲
献p7习21更优的性能。
动态数据结构一池是一种普适的工具，可以用来解决其他计算机科学
领域中的问题，比如进程管理、并行计算中的任务分配等。作为一个具体的
应用，本文将二维池应用到打印机任务调度中，仿真结果表明算法能解决繁
重的计算机排队打印问题。
A new idea of data structure ?dynamic data structure is proposed in this
thesis. Based on this idea, a novel type of data structure 棗 Pool is
implemented in 1-dimension and 2-dimension cases. Applications of this novel
data structure in VLSI circuit layout and printer task queuing are also studied.
Main contributions of the thesis are the following:
1. Demand of dynamic data processing in a variety of computer
applications is addressed, a concept of dynamic data structure is then
proposed, upon which a novel data structure Pool able to
dynamically handle data processing (Such as data representation,
searching, merging, ordering and storage, etc.)is suggested.
2. Implementation of 1-D and 2-D pool is described, their sequential data
accessing mechanism and dynamic maintenance program, in both
periodic and trigger manner, are described, and basic pool operations
are also defined.
3. As one of the feasible applications of pooi, we have successfully
m
Abs~act
formulated a modified pool-based genetic algorithni(PGA), then
applied it to solve a gate array placement problem. Computer
simulation results of an example show that improvement over
traditional GA can be nbtained by using our PGA.
4. For the same gate array placement example, we use a fast evolutionary
programming (FEP) to get better results.
5. To minimizing crosstalk among nets in channel routing, a
perturbation-based algoritlun is proposed. The algorithm is applied to
benchmark examples, and comparative simulation results show that
our algorithm is more effective than those given in previous literatures
[87-92]
It is pointed out that the dynamic data structure ?pool is a powerful
general-purpose tool to solve a variety of problems in other areas of computer
sciences, such as process management, task assignment in parallel computing,
etc. As an example, a printer task queuing management algorithm is designed by
using 2-D pool, simulation results show that the algorithm is able to solve
complicate and heavy duty printer queuing problems.
文实现了一种新的数据结构——池及其在一维和二维时的情况。本文同时对
这种新的数据结构在VLSI电路布局设计中的应用和在打印机任务调度中的
应用进行了研究。
本文的主要贡献概括如下：
1.本文讨论了各种计算机应用中的动态数据处理要求，之后提出了动
态数据结构的概念。根据这一新概念，本文建议了一种新的数据结
构——池，它能对数据进行动态处理（例如，数据的表示，查找，
合并，排序和存储等等）。
2.本文研究了一维池和二维池的实现，对一维池和二维池的顺序存
取、基于周期机制和基于触发机制的动态秩序维持程序进行了研
究，并定义了一维池和二维池的基本运算。
3.本文成功地将池和遗传算法相结合，形成改进的基于池的遗传算法
（PGA），以作为池的一种灵活应用。然后，将基于池的遗传算法
（PGA）用于解决门阵列布局设计。对门阵列布局算例的计算机仿
搞要
真结果表明使用基于池的遗传算法汀GA）能够获得比传统遗传算
法（GA）更好的结果。
4．本文将快速进化规划算法（FEP）用于同样的门阵列布局算例，也
取得了满意的结果。
5．为减小通道布线中线网间的串扰，本文提出一个基于扰动的算法。
我们将此算法运用到若干benchlnn例子上去，并和已知的一些结
果进行了比较，结果表明我们建议的基于扰动的算法能够获得比文 甲
献p7习21更优的性能。
动态数据结构一池是一种普适的工具，可以用来解决其他计算机科学
领域中的问题，比如进程管理、并行计算中的任务分配等。作为一个具体的
应用，本文将二维池应用到打印机任务调度中，仿真结果表明算法能解决繁
重的计算机排队打印问题。
A new idea of data structure ?dynamic data structure is proposed in this
thesis. Based on this idea, a novel type of data structure 棗 Pool is
implemented in 1-dimension and 2-dimension cases. Applications of this novel
data structure in VLSI circuit layout and printer task queuing are also studied.
Main contributions of the thesis are the following:
1. Demand of dynamic data processing in a variety of computer
applications is addressed, a concept of dynamic data structure is then
proposed, upon which a novel data structure Pool able to
dynamically handle data processing (Such as data representation,
searching, merging, ordering and storage, etc.)is suggested.
2. Implementation of 1-D and 2-D pool is described, their sequential data
accessing mechanism and dynamic maintenance program, in both
periodic and trigger manner, are described, and basic pool operations
are also defined.
3. As one of the feasible applications of pooi, we have successfully
m
Abs~act
formulated a modified pool-based genetic algorithni(PGA), then
applied it to solve a gate array placement problem. Computer
simulation results of an example show that improvement over
traditional GA can be nbtained by using our PGA.
4. For the same gate array placement example, we use a fast evolutionary
programming (FEP) to get better results.
5. To minimizing crosstalk among nets in channel routing, a
perturbation-based algoritlun is proposed. The algorithm is applied to
benchmark examples, and comparative simulation results show that
our algorithm is more effective than those given in previous literatures
[87-92]
It is pointed out that the dynamic data structure ?pool is a powerful
general-purpose tool to solve a variety of problems in other areas of computer
sciences, such as process management, task assignment in parallel computing,
etc. As an example, a printer task queuing management algorithm is designed by
using 2-D pool, simulation results show that the algorithm is able to solve
complicate and heavy duty printer queuing problems.
引文
[1] 洪先龙，严晓浪，乔长阁，超大规模集成电路布图理论与算法，科学出 版社，1998
[2] 吴雄，“国际集成电路产业发展现状与前景”，电子与自动化，1996(6) ， 3-8
[3] 李春辉，“基于计算智能和性能驱动的深亚微米VLSI物理设计算法研 究”，电子科技大学工学博士学位论文，1999
[4] 潘松，“电子设计自动化(EDA)技术及其应用(一)”,电子与自动化， 2000(1)
[5] 潘松，“电子设计自动化(EDA)技术及其应用(二)”，电子与自动化， 2000(2)
[6] 潘松，“电子设计自动化(EDA)技术及其应用(三)”，电子与自动化， 2000(3)
[7] 潘松，“电子设计自动化(EDA)技术及其应用(四)”电子与自动化， 2000(4)
[8] 陈文华，“中国半导体行业的历史、现状及展望”，半导体技术，1997 (3)
[9] 王阳元，张兴，“21世纪及1999年微电子技术展望”，电子科技导报， 1999，(1)
[10] 田遐，“EDA技术的应用”，煤炭科学技术，1999，27(7)
[11] 窦银昆，“电子设计自动化的发展动向”，压电与声光，1995，17(1)
[12] 肖跃龙，“欣欣向荣的EDA技术”，计算机辅助设计与制造，1995，5
[13] 庄文君，李玉兴，“集成电路布图设计自动化”，上海交通大学出版社， 1986
[14] 张良震，庄文君，马兴图,“超大规模集成电路计算机辅助设计”，北京： 电子工业出版社,1987
[15] 庄镇泉，戴英侠,王荣生，“大规模集成电路计算机辅助设计”，安徽合 肥：中国科学技术大学出版社，1990
[16] 庄昌文，“超大规模集成电路若干布线算法研究”，电子科技大学工学博 士学位论文，2001
[17] 刘志军，“EDA/ESDA设计方法的发展及框架结构微计算信息”，1998 (2)
[18] 郭志信，王平福，“电子CAD到EDA的发展与展望”，现代电子技术， 1999
[19] 顾慧芳，“我国EDA业面临的挑战与机遇”，电子展望与决策，1997， (5)
[20] 周祖成，“EDA(电子设计自动化)的进展”，电子技术与应用，1997， 6-22
[21] 胡庆生，汪晓岩，庄镇泉，“VLSI版图参数撮的分布式并行算法”,电 子学报．1999，27(5)
[22] 陈平，杨刚，刘鑫，李玉山，“VLSI标准单元通道布线的研究”，西安 电子科技大学学报，1998，25(6)
[23] 洪先龙，潘立，王尔乾，“VLSI和PCB双层布线中的通孔取少化算法”， 半导体学报，1996，533-539
[24] 邵秀丽，刘景，“VLSI布局布线及其划分算法的设计与实现”，微机发 展，1999(1)
[25] 吴一帆，李思昆，“基于神经网络的自动布局算法”，计算机工程与科学， 2000，22(2)
[26] Chang Ray-I．Hsiao Pei-Yung，“VLSI Circuit Placement with Rectilinear Modules Using Three-Layer Force-Directed Self-Organizing Maps[J]”,IEEE Trans．On Neural Networks．1997，8(5) ：1049-1064
[27] 周之英，“神经元网络与自动布图[J]”，计算机学报，1997，20(9) ：839-84
[28] 谭悦，蔡世俊，“集成电路布局规划技术”，微电子学，1997，27(2)
[29] [日]渡边诚，江田邦博，可儿贤二等，“超大规模集成电路设计：电路与 版图设计”，北京：科学出版社,1988
[30] 许卓群等，“数据结构”，高等教育出版社
[31] 《数据结构C++语言描述》第三版，William Ford William Topp著，刘 卫东、沈官林译，清华大学出版社，1998年11月
[32] 《OPERATION SYSTEMS INTERNALS AND DESIGN PRINCIPLES》 THIRD EDITION，William Stallings，清华大学出版社，1998年6月
[33] 《数据结构与算法分析》，Difford A．Shaffer著，张铭、刘晓丹译，电子 工业出版社
[34] 张徐亮，虞厥邦，“一种新的数据结构--池(上)”，送审
[35] 张徐亮．虞厥邦．“一种新的数据结构--池(下)”，送审
[36] 张徐亮等，“基于动态数据结构--池的打印任务调度”，计算机科学， 2001，(6)
[37] 唐策善等，“数据结构--用C语言描述”，高等教育出版社
[38] 刘大有，“数据结构”， 高等教育出版社
[39] 闵光太，“C语言程序设计与数据结构完成”，高等教育出版社
[40] 钟诚，宁玲，赵明，“Java动态数据结构与构件重用技术的实现”，计算 机工程，1999，25(10)
[41] 马春光，许维平，武朋，“单任务操作系统下的多任务内核”，计算机应 用，2000，20(2)
[42] 陈思国，李雄飞，赵启哲，苑森淼．“论动态数据结构的程序语义”，吉 林工业大学学报，1995,25(3)
[43] 彭月英，“二维数据组的快速排序算法”，广西科学，1997，4(3) ，93-96
[44] 邓朝辉，贾华，“矢量数据的一种分层动态组织方法”，武汉测绘科技大 学学报，1995，20(2)
[45] 何月顺，李德平，“数据结构体系分析”，华东地质学院学报，1998，21 (3)
[46] 董东，郑玉明，“数据结构图的语法”，计算机工程与应用，1998，2
[47] 卢官明，毕厚杰，“形态重构算法及应用”，信号处理，2000，16(2)
[48] 汪西莉，汪西原，“用C语言实现人工智能中的搜索策略”，陕西师范大 学学报，1999，27(1)
[49] 武继刚，陈国良，“优先队列与并行分枝界限算法”，烟台大学学报，2000， 13(1)
[50] 张徐亮，刘良萍，虞厥邦，进化规划应用于VLSI布局研究，送审
[51] 任庆生，叶中行，曾进，进化算法的收敛速度，上海交通大学学报，1999 (6)
[52] 郭宇春，孙连举，戴宗礼，江涌，遗传算法及其应用，遗传算法及其应 用，1998(7) ，59-62
[53] 史奎凡，陈月辉，提高遗传算法收敛速度的方法，信息与控制，1998 (4) ，289-293
[54] 吴少岩，张青富，陈火旺，基于家族优生学的进化算法，软件学报，1997， 8(2) ：137-144
[55] 姚新，陈国良，徐惠敏，进化算法研究进展，计算机学报，1995，18 (9) ：694-705
[56] 丁承民，张传生，刘辉，遗传算法纵横谈，信息与控制，1997，26(1) ， 40-47
[57] 曲润涛，席裕庚，叶剑，基于进化规划的OCST问题求解，系统工程与 电子技术，1999，21(5) ，39-42
[58] 曲润涛，席裕庚，基于进化规划的树形网络优化规划，通信技术，1998， 31(3) ，13-16
[59] 周明，孙树栋，彭炎午，“并行遗传算法的研究评述”，南昌航空工业学 院学报，1998(2)
[60] Holland J H．基因算法．科学，1992；11：24-31
[61] De Jong K A．Learning with genetic algorithms：an overview．Machine learning 3，Kluwer Acdemic，Hingham，Mass，1988；121-133
[62] 鄢烈祥，麻德贤，连续变量函数全局优化列队竞争算法，湖北工学院学 报，1999，14(1，2) ，38-44
[63] Kirkpatrick S，Gelatt C D，and Vechi M P，Optimization by simulated annealing[J]，Science，1983，220，551-580．
[64] 穆文全，“有关遗传算法、神经网络和模糊逻辑的综合软计算研究”，电 子科技大学工党博士学位论文，1996
[65] Schwefel H．P.,Numerical Optimization of Computer Models, Wiley,Chichestcr,1981
[66] Fogel D．B．，An Introducfion to Simulated Evolutionary Optimization,IEEE Trans．Neural Computation，1994,5(1) ,3-14
[67] Goldberg D E，Genetic Algorithm in Search，Optimization and Machine learning[M]．New York：Addison Wesley,1989
[68] 张良震，刘红，史亮，秦伟，遗传算法应用于VLSI布局的研究，电路 与系统学报，1999，4(3) ，pp．47-53
[69] 吴庆洪，张纪会，徐心和，一种有效的进化规划算法，系统仿真学报， 1999，11(6) ，pp．409-411
[70] 孟祥萍，梁志珊，张化光，一种基于二进制编码的优化方法，控制与决 策，1998，Vol．13，增刊，pp．513-516
[71] 任平，遗传算法(综述)，工程数学学报，1999，16(1)
[72] Rechenberg I．Cybernetic solution path of an experimental problem．Roy
Aircr，Establ，libr Trans 1222，Hants，U K Farnboroungh，1965
[73] 于志伟，“一种新的全局优化神经网络”，电子学报，1999，27(2)
[74] Glover F.”Future paths for integer programming and links to artificial intelligence”，Comput．& Ops．Res．，1986，13(5) ：533-549
[75] Nowicki E，Smntnicki C．”A fast tabu search algorithm for the job shop problem．”，Management Science，June，1996，42(6) ：797-812
[76] De Werra D，Hertz A．”Tabu search techniques：A tutorial and an application to neural network”，OR Spektrum，1989，11：131-141
[77] 吴志远，邵惠鹤，吴新余，“遗传退火进化算法”，上海交通大学学报， 1997,31(12)
[78] Davis L．(Ed)，Handbook of Genetic Algorithms，New York：Van nostrand Reinhold，1991
[79] Kumar Chellapilla，Sathyanarayan S．Rao，Optimization of Bilinear Time Series Models Using Fast Evolutionary Programming，IEEE Signal Processing Letters，1998，5(2) ，pp．39-42
[80] X．Yak and Y.Liu，”Fast evolutionary programming．”In Evolutionary Programming V：Porch．5th Ann．Con．Evolutionary Programming，L.J. Fogged．P. J．Angolan，T．Bck，Eds．
[81] Kim J H Chae H K，Jeon J Y，et al．Identification and control of systems with friction using accelerated evolutionary programming[J]．IEEE Control Systems,Aug 1996，38-47
[82] Fogel I L．Artificial Intelligence through Simulated Evolution[M]．New York：John Wiley,1996
[83] Glover F.Tabu search-part 1/part 2[J]．ORSA J Computing， 1989，(3) ，190-206；1990，(1) ，4-32
[84] Bakoglu，H．B．，Circuits，Interconnections and Packaging for VLSI，
Addison-Wesley Publishing Company, 1990．
[85] HoTT, Lyengar S S. "A General Greedy Channel Routing Algorithm", IEEE Trans, on Computer-Aided Design, 1991,204-211
[86] Douglas B, Jeffrey L B. "Techniques For Multilayer Channel Routing", IEEE Trans. On Circuits & System, 1988,698-712
[87] Chaudhary, K., A. Onazawa and E.S. Kuh, "A Spacing Algorithm for Performance Enhancement and Crosstalk Reduction", Proc. Intl. Conf. Computer-Aided Design, 697-702, 1993．
[88] Gao, T. and C. Liu, "Minimum Crosstalk Channel Routing", IEEE Trans. Computer-Aided Design 15(5) , 465-474,1996．
[89] Prashant Saxena and C.L. Liu, "Crosstalk Minimization using Wire Perturbations", DAC 99, New Orleans, Louisiana
[90] Leong, H.W. and C.L. Liu, "A New Channel Router", Proc. Design Automation Conf., 584-590,1983
[91] Wong, D.F. and C. L. Liu, "Compacted Channel Routing with Via Placement Restriction", Integration 4(4) , 267-307,1986
[92] Yoshimura. T. and E. S. Kuh, "Efficient Algorithms for Channel Routing", IEEE Trans. Computer-Aided Design CAD-1(1) , 25-35,1982
[2] 吴雄，“国际集成电路产业发展现状与前景”，电子与自动化，1996(6) ， 3-8
[3] 李春辉，“基于计算智能和性能驱动的深亚微米VLSI物理设计算法研 究”，电子科技大学工学博士学位论文，1999
[4] 潘松，“电子设计自动化(EDA)技术及其应用(一)”,电子与自动化， 2000(1)
[5] 潘松，“电子设计自动化(EDA)技术及其应用(二)”，电子与自动化， 2000(2)
[6] 潘松，“电子设计自动化(EDA)技术及其应用(三)”，电子与自动化， 2000(3)
[7] 潘松，“电子设计自动化(EDA)技术及其应用(四)”电子与自动化， 2000(4)
[8] 陈文华，“中国半导体行业的历史、现状及展望”，半导体技术，1997 (3)
[9] 王阳元，张兴，“21世纪及1999年微电子技术展望”，电子科技导报， 1999，(1)
[10] 田遐，“EDA技术的应用”，煤炭科学技术，1999，27(7)
[11] 窦银昆，“电子设计自动化的发展动向”，压电与声光，1995，17(1)
[12] 肖跃龙，“欣欣向荣的EDA技术”，计算机辅助设计与制造，1995，5
[13] 庄文君，李玉兴，“集成电路布图设计自动化”，上海交通大学出版社， 1986
[14] 张良震，庄文君，马兴图,“超大规模集成电路计算机辅助设计”，北京： 电子工业出版社,1987
[15] 庄镇泉，戴英侠,王荣生，“大规模集成电路计算机辅助设计”，安徽合 肥：中国科学技术大学出版社，1990
[16] 庄昌文，“超大规模集成电路若干布线算法研究”，电子科技大学工学博 士学位论文，2001
[17] 刘志军，“EDA/ESDA设计方法的发展及框架结构微计算信息”，1998 (2)
[18] 郭志信，王平福，“电子CAD到EDA的发展与展望”，现代电子技术， 1999
[19] 顾慧芳，“我国EDA业面临的挑战与机遇”，电子展望与决策，1997， (5)
[20] 周祖成，“EDA(电子设计自动化)的进展”，电子技术与应用，1997， 6-22
[21] 胡庆生，汪晓岩，庄镇泉，“VLSI版图参数撮的分布式并行算法”,电 子学报．1999，27(5)
[22] 陈平，杨刚，刘鑫，李玉山，“VLSI标准单元通道布线的研究”，西安 电子科技大学学报，1998，25(6)
[23] 洪先龙，潘立，王尔乾，“VLSI和PCB双层布线中的通孔取少化算法”， 半导体学报，1996，533-539
[24] 邵秀丽，刘景，“VLSI布局布线及其划分算法的设计与实现”，微机发 展，1999(1)
[25] 吴一帆，李思昆，“基于神经网络的自动布局算法”，计算机工程与科学， 2000，22(2)
[26] Chang Ray-I．Hsiao Pei-Yung，“VLSI Circuit Placement with Rectilinear Modules Using Three-Layer Force-Directed Self-Organizing Maps[J]”,IEEE Trans．On Neural Networks．1997，8(5) ：1049-1064
[27] 周之英，“神经元网络与自动布图[J]”，计算机学报，1997，20(9) ：839-84
[28] 谭悦，蔡世俊，“集成电路布局规划技术”，微电子学，1997，27(2)
[29] [日]渡边诚，江田邦博，可儿贤二等，“超大规模集成电路设计：电路与 版图设计”，北京：科学出版社,1988
[30] 许卓群等，“数据结构”，高等教育出版社
[31] 《数据结构C++语言描述》第三版，William Ford William Topp著，刘 卫东、沈官林译，清华大学出版社，1998年11月
[32] 《OPERATION SYSTEMS INTERNALS AND DESIGN PRINCIPLES》 THIRD EDITION，William Stallings，清华大学出版社，1998年6月
[33] 《数据结构与算法分析》，Difford A．Shaffer著，张铭、刘晓丹译，电子 工业出版社
[34] 张徐亮，虞厥邦，“一种新的数据结构--池(上)”，送审
[35] 张徐亮．虞厥邦．“一种新的数据结构--池(下)”，送审
[36] 张徐亮等，“基于动态数据结构--池的打印任务调度”，计算机科学， 2001，(6)
[37] 唐策善等，“数据结构--用C语言描述”，高等教育出版社
[38] 刘大有，“数据结构”， 高等教育出版社
[39] 闵光太，“C语言程序设计与数据结构完成”，高等教育出版社
[40] 钟诚，宁玲，赵明，“Java动态数据结构与构件重用技术的实现”，计算 机工程，1999，25(10)
[41] 马春光，许维平，武朋，“单任务操作系统下的多任务内核”，计算机应 用，2000，20(2)
[42] 陈思国，李雄飞，赵启哲，苑森淼．“论动态数据结构的程序语义”，吉 林工业大学学报，1995,25(3)
[43] 彭月英，“二维数据组的快速排序算法”，广西科学，1997，4(3) ，93-96
[44] 邓朝辉，贾华，“矢量数据的一种分层动态组织方法”，武汉测绘科技大 学学报，1995，20(2)
[45] 何月顺，李德平，“数据结构体系分析”，华东地质学院学报，1998，21 (3)
[46] 董东，郑玉明，“数据结构图的语法”，计算机工程与应用，1998，2
[47] 卢官明，毕厚杰，“形态重构算法及应用”，信号处理，2000，16(2)
[48] 汪西莉，汪西原，“用C语言实现人工智能中的搜索策略”，陕西师范大 学学报，1999，27(1)
[49] 武继刚，陈国良，“优先队列与并行分枝界限算法”，烟台大学学报，2000， 13(1)
[50] 张徐亮，刘良萍，虞厥邦，进化规划应用于VLSI布局研究，送审
[51] 任庆生，叶中行，曾进，进化算法的收敛速度，上海交通大学学报，1999 (6)
[52] 郭宇春，孙连举，戴宗礼，江涌，遗传算法及其应用，遗传算法及其应 用，1998(7) ，59-62
[53] 史奎凡，陈月辉，提高遗传算法收敛速度的方法，信息与控制，1998 (4) ，289-293
[54] 吴少岩，张青富，陈火旺，基于家族优生学的进化算法，软件学报，1997， 8(2) ：137-144
[55] 姚新，陈国良，徐惠敏，进化算法研究进展，计算机学报，1995，18 (9) ：694-705
[56] 丁承民，张传生，刘辉，遗传算法纵横谈，信息与控制，1997，26(1) ， 40-47
[57] 曲润涛，席裕庚，叶剑，基于进化规划的OCST问题求解，系统工程与 电子技术，1999，21(5) ，39-42
[58] 曲润涛，席裕庚，基于进化规划的树形网络优化规划，通信技术，1998， 31(3) ，13-16
[59] 周明，孙树栋，彭炎午，“并行遗传算法的研究评述”，南昌航空工业学 院学报，1998(2)
[60] Holland J H．基因算法．科学，1992；11：24-31
[61] De Jong K A．Learning with genetic algorithms：an overview．Machine learning 3，Kluwer Acdemic，Hingham，Mass，1988；121-133
[62] 鄢烈祥，麻德贤，连续变量函数全局优化列队竞争算法，湖北工学院学 报，1999，14(1，2) ，38-44
[63] Kirkpatrick S，Gelatt C D，and Vechi M P，Optimization by simulated annealing[J]，Science，1983，220，551-580．
[64] 穆文全，“有关遗传算法、神经网络和模糊逻辑的综合软计算研究”，电 子科技大学工党博士学位论文，1996
[65] Schwefel H．P.,Numerical Optimization of Computer Models, Wiley,Chichestcr,1981
[66] Fogel D．B．，An Introducfion to Simulated Evolutionary Optimization,IEEE Trans．Neural Computation，1994,5(1) ,3-14
[67] Goldberg D E，Genetic Algorithm in Search，Optimization and Machine learning[M]．New York：Addison Wesley,1989
[68] 张良震，刘红，史亮，秦伟，遗传算法应用于VLSI布局的研究，电路 与系统学报，1999，4(3) ，pp．47-53
[69] 吴庆洪，张纪会，徐心和，一种有效的进化规划算法，系统仿真学报， 1999，11(6) ，pp．409-411
[70] 孟祥萍，梁志珊，张化光，一种基于二进制编码的优化方法，控制与决 策，1998，Vol．13，增刊，pp．513-516
[71] 任平，遗传算法(综述)，工程数学学报，1999，16(1)
[72] Rechenberg I．Cybernetic solution path of an experimental problem．Roy
Aircr，Establ，libr Trans 1222，Hants，U K Farnboroungh，1965
[73] 于志伟，“一种新的全局优化神经网络”，电子学报，1999，27(2)
[74] Glover F.”Future paths for integer programming and links to artificial intelligence”，Comput．& Ops．Res．，1986，13(5) ：533-549
[75] Nowicki E，Smntnicki C．”A fast tabu search algorithm for the job shop problem．”，Management Science，June，1996，42(6) ：797-812
[76] De Werra D，Hertz A．”Tabu search techniques：A tutorial and an application to neural network”，OR Spektrum，1989，11：131-141
[77] 吴志远，邵惠鹤，吴新余，“遗传退火进化算法”，上海交通大学学报， 1997,31(12)
[78] Davis L．(Ed)，Handbook of Genetic Algorithms，New York：Van nostrand Reinhold，1991
[79] Kumar Chellapilla，Sathyanarayan S．Rao，Optimization of Bilinear Time Series Models Using Fast Evolutionary Programming，IEEE Signal Processing Letters，1998，5(2) ，pp．39-42
[80] X．Yak and Y.Liu，”Fast evolutionary programming．”In Evolutionary Programming V：Porch．5th Ann．Con．Evolutionary Programming，L.J. Fogged．P. J．Angolan，T．Bck，Eds．
[81] Kim J H Chae H K，Jeon J Y，et al．Identification and control of systems with friction using accelerated evolutionary programming[J]．IEEE Control Systems,Aug 1996，38-47
[82] Fogel I L．Artificial Intelligence through Simulated Evolution[M]．New York：John Wiley,1996
[83] Glover F.Tabu search-part 1/part 2[J]．ORSA J Computing， 1989，(3) ，190-206；1990，(1) ，4-32
[84] Bakoglu，H．B．，Circuits，Interconnections and Packaging for VLSI，
Addison-Wesley Publishing Company, 1990．
[85] HoTT, Lyengar S S. "A General Greedy Channel Routing Algorithm", IEEE Trans, on Computer-Aided Design, 1991,204-211
[86] Douglas B, Jeffrey L B. "Techniques For Multilayer Channel Routing", IEEE Trans. On Circuits & System, 1988,698-712
[87] Chaudhary, K., A. Onazawa and E.S. Kuh, "A Spacing Algorithm for Performance Enhancement and Crosstalk Reduction", Proc. Intl. Conf. Computer-Aided Design, 697-702, 1993．
[88] Gao, T. and C. Liu, "Minimum Crosstalk Channel Routing", IEEE Trans. Computer-Aided Design 15(5) , 465-474,1996．
[89] Prashant Saxena and C.L. Liu, "Crosstalk Minimization using Wire Perturbations", DAC 99, New Orleans, Louisiana
[90] Leong, H.W. and C.L. Liu, "A New Channel Router", Proc. Design Automation Conf., 584-590,1983
[91] Wong, D.F. and C. L. Liu, "Compacted Channel Routing with Via Placement Restriction", Integration 4(4) , 267-307,1986
[92] Yoshimura. T. and E. S. Kuh, "Efficient Algorithms for Channel Routing", IEEE Trans. Computer-Aided Design CAD-1(1) , 25-35,1982