| 中文摘要 | 第1-9页 |
| 英文摘要 | 第9-11页 |
| 第一章 引言 | 第11-22页 |
| 1．1 集成电路CAD技术的发展 | 第11-12页 |
| 1．2 VLSI设计流程 | 第12-13页 |
| 1．3 布图设计过程 | 第13-14页 |
| 1．4 布局和布线的复杂性分析 | 第14-16页 |
| 1．5 布图模式 | 第16-18页 |
| 1．5．1 全定制设计模式 | 第16页 |
| 1．5．2 标准单元设计模式 | 第16-17页 |
| 1．5．3 门阵列设计模式 | 第17页 |
| 1．5．4 门海设计模式 | 第17页 |
| 1．5．5 现场可编程门阵列 | 第17-18页 |
| 1．5．6 不同设计方法的比较 | 第18页 |
| 1．6 测试生成和测试集优化 | 第18-20页 |
| 1．7 遗传算法 | 第20页 |
| 1．8 本文结构 | 第20-22页 |
| 第二章 遗传算法的发展及理论基础 | 第22-46页 |
| 2．1 进化算法简介 | 第22-27页 |
| 2．1．1 遗传算法（Genetic algorithms，GA） | 第23-24页 |
| 2．1．2 进化规划（Evolutionary programming，EP） | 第24-25页 |
| 2．1．3 进化策略（Evolution strategies，ES） | 第25页 |
| 2．1．4 三种进化算法的关系 | 第25-27页 |
| 2．2 遗传算法的特点、结构和理论研究 | 第27-33页 |
| 2．2．1 遗传算法的历史 | 第27-29页 |
| 2．2．2 传统遗传算法的结构 | 第29-32页 |
| 2．2．3 遗传算法的特点 | 第32-33页 |
| 2．3 遗传算法的理论基础 | 第33-39页 |
| 2．3．1 模式定理 | 第33-36页 |
| 2．3．2 积木块假设 | 第36-37页 |
| 2．3．3 遗传算法的收敛性 | 第37-38页 |
| 2．3．4 No Free Lunch定理 | 第38-39页 |
| 2．4 遗传算法的发展 | 第39-45页 |
| 2．4．1 并行遗传算法 | 第39-43页 |
| 2．4．2 层次遗传算法 | 第43-45页 |
| 2．5 遗传算法的设计重点 | 第45页 |
| 2．6 小结 | 第45-46页 |
| 第三章 基于遗传算法的VLSI电路划分方法 | 第46-56页 |
| 3．1 引言 | 第46-47页 |
| 3．2 电路划分问题 | 第47-48页 |
| 3．3 电路划分算法的回顾 | 第48-49页 |
| 3．4 电路划分的遗传算法设计 | 第49-52页 |
| 3．4．1 编码方式 | 第49页 |
| 3．4．2 染色体的交叉 | 第49-50页 |
| 3．4．3 染色体的变异 | 第50页 |
| 3．4．4 评估函数 | 第50-51页 |
| 3．4．5 染色体的选择 | 第51-52页 |
| 3．5 算法流程 | 第52-53页 |
| 3．5．1 算法流程图 | 第52页 |
| 3．5．2 初始化 | 第52页 |
| 3．5．3 初始种群的产生 | 第52-53页 |
| 3．5．4 循环结束的判别 | 第53页 |
| 3．6 算法复杂性分析 | 第53页 |
| 3．6．1 算法的时间复杂度 | 第53页 |
| 3．6．2 算法的空间复杂度 | 第53页 |
| 3．7 实验结果 | 第53-55页 |
| 3．7．1 二划分的测试 | 第53-54页 |
| 3．7．2 K划分多约束情况的测试 | 第54-55页 |
| 3．8 小结 | 第55-56页 |
| 第四章 基于遗传算法的VLSI布图规划方法 | 第56-70页 |
| 4．1 布图规划和布局 | 第56页 |
| 4．2 VLSI布图规划问题的描述 | 第56-60页 |
| 4．2．1 数据结构 | 第56-57页 |
| 4．2．2 版图结构 | 第57-58页 |
| 4．2．3 布局中的线长估计 | 第58-60页 |
| 4．3 布图规划和布局算法的回顾 | 第60-62页 |
| 4．4 染色体的编码和评估函数 | 第62-63页 |
| 4．4．1 染色体编码 | 第62页 |
| 4．4．2 评估函数的设计 | 第62-63页 |
| 4．5 布图规划问题的遗传算法设计 | 第63-65页 |
| 4．5．1 染色体的选择 | 第63页 |
| 4．5．2 染色体的交叉 | 第63-64页 |
| 4．5．3 染色体的变异 | 第64-65页 |
| 4．6 启发式解码算法 | 第65-66页 |
| 4．6．1 解码规则 | 第65页 |
| 4．6．2 启发式算法 | 第65-66页 |
| 4．7 算法复杂度分析 | 第66-67页 |
| 4．7．1 算法的时间复杂度 | 第66页 |
| 4．7．2 算法的空间复杂度 | 第66-67页 |
| 4．8 实验结果和讨论 | 第67-69页 |
| 4．8．1 算法的总流程 | 第67页 |
| 4．8．2 实验结果 | 第67-69页 |
| 4．9 小结 | 第69-70页 |
| 第五章 遗传算法在通道布线中的应用 | 第70-91页 |
| 5．1 通道布线 | 第70-74页 |
| 5．1．1 通道布线概念的提出 | 第70-71页 |
| 5．1．2 基于网格的通道布线模型 | 第71页 |
| 5．1．3 水平约束和垂直约束 | 第71-73页 |
| 5．1．4 连通孔数最小化通道布线的图论模型 | 第73-74页 |
| 5．2 布线的主要算法的回顾 | 第74-76页 |
| 5．3 通孔最小化三层布线的算法步骤 | 第76-77页 |
| 5．4 最佳着色的遗传算法模型 | 第77-79页 |
| 5．4．1 染色体的表达 | 第77页 |
| 5．4．2 目标函数的确定 | 第77-78页 |
| 5．4．3 交叉、变异和选择 | 第78-79页 |
| 5．5 线网排序的遗传算法模型 | 第79-81页 |
| 5．5．1 初始群体的产生 | 第79页 |
| 5．5．2 适值函数的确定 | 第79-80页 |
| 5．5．3 选择 | 第80页 |
| 5．5．4 交叉 | 第80页 |
| 5．5．5 变异 | 第80-81页 |
| 5．6 “沉积法”布线 | 第81-84页 |
| 5．6．1 A类和C类线网的布线 | 第81-82页 |
| 5．6．2 B类线网的布线 | 第82-84页 |
| 5．7 布线总流程图 | 第84-85页 |
| 5．8 通孔最小化多层通道布线算法 | 第85-86页 |
| 5．8．1 多层通孔最小化通道布线算法 | 第85-86页 |
| 5．8．2 计算复杂性分析 | 第86页 |
| 5．9 实验结果及讨论 | 第86-89页 |
| 5．9．1 实验结果 | 第86-89页 |
| 5．9．2 讨论 | 第89页 |
| 5．10 小结 | 第89-91页 |
| 第六章 基于遗传算法的测试生成和故障测试集最小化方法 | 第91-116页 |
| 6．1 VLSI故障测试 | 第91-92页 |
| 6．2 故障的类型和故障模型 | 第92-93页 |
| 6．2．1 故障的分类 | 第92页 |
| 6．2．2 故障的模型 | 第92-93页 |
| 6．3 伪穷举测试 | 第93-97页 |
| 6．3．1 电路划分 | 第93-95页 |
| 6．3．2 多输出电路 | 第95-97页 |
| 6．4 伪穷举测试传统的分块方法 | 第97-99页 |
| 6．5 伪穷举测试的遗传算法设计 | 第99-104页 |
| 6．5．1 针对多输出电路的图的着色问题的遗传算法（MCR-GA） | 第99-101页 |
| 6．5．2 多输出电路的图的着色问题的遗传算法（MCR-GA）的复杂性 | 第101-102页 |
| 6．5．3 针对电路的有向图划分的遗传算法（DGP-GA） | 第102-103页 |
| 6．5．4 针对电路的有向图划分的遗传算法（DGP-GA）的复杂性分析 | 第103-104页 |
| 6．5．5 测试结果与分析 | 第104页 |
| 6．6 完全测试集的极小化 | 第104-105页 |
| 6．7 故障测试集最小化问题的遗传算法设计 | 第105-108页 |
| 6．7．1 编码方式 | 第105-106页 |
| 6．7．2 评估函数 | 第106页 |
| 6．7．3 染色体的选择、交叉和变异 | 第106页 |
| 6．7．4 惩罚法和改进法 | 第106-107页 |
| 6．7．5 面向测试矢量的遗传算法的复杂性分析 | 第107-108页 |
| 6．8 面向故障的遗传算法 | 第108-112页 |
| 6．8．1 编码方式 | 第108页 |
| 6．8．2 染色体的交叉 | 第108-109页 |
| 6．8．3 染色体的变异 | 第109-110页 |
| 6．8．4 评估函数 | 第110页 |
| 6．8．5 染色体的选择 | 第110页 |
| 6．8．6 算法流程 | 第110-112页 |
| 6．8．7 面向故障的遗传算法复杂性分析 | 第112页 |
| 6．9 实验结果 | 第112-115页 |
| 6．10 小结 | 第115-116页 |
| 第七章 总结与展望 | 第116-118页 |
| 参考文献 | 第118-129页 |
| 发表文章目录 | 第129-130页 |
| 致谢 | 第130页 |
