论文部分内容阅读
本文以超大规模集成电路板(VLSI)的布局设计和工厂机械设备摆放为工程应用背景,深入研究一类具备NP难度的带权重圆形布局(WCP)问题。WCP问题要求最终的合法解满足:1)待布物之间的权重距离之和尽可能小;2)能容纳所有待布物的外包络容器的面积尽可能小,并同时满足待布物之间不嵌入约束。本文采用线性加权法和多目标方法分别求解WCP问题。主要研究内容及成果如下:(1)研究了 WCP问题的单目标求解算法,提出了一种基于二分策略的粗精调启发式拟物算法(HQPA-CFDM)。首先基于线性加权法,将带约束的WCP问题转化为无约束优化问题,并建立相应的数学模型。然后从任意一个初始构形出发,采用二分法逐步构造外包络容器,并采用拟物算法逐步优化当前构形下总的挤压弹性势能。为了快速找到问题的合法解,受工业制造中粗精控制过程的启发,将拟物算法分解为两个过程:粗调过程和精调过程。在拟物算法中,提出了一种弹性系数可变的策略。另外,为了避免算法陷入局部极小点,提出了一种启发式跳坑策略。通过对当前国际上3个典型算例进行计算,数值实验结果表明,算法HQPA-CFDM刷新了所有算例的最好结果。对计算结果进行统计分析,进一步验证了算法HQPA-CFDM的有效性和稳定性。(2)研究了 WCP问题的多目标方法,提出了一种多目标构形空间进化算法(MOCSEA)。首先依据拟物思想和罚函数法,将带约束的WCP问题转化为无约束的多目标优化问题,并建立相应的数学模型。然后随机产生初始构形库(种群),并采用带提前结束策略的自适应步长梯度法(GD)对初始构形库中的构形(个体)进行合法化操作;然后对初始构形库执行进化操作(包括选择、交叉和变异,其中选择操作采用精英策略,交叉操作采用单点交叉和多点交叉相结合的方式,变异操作采用启发式变异策略),产生进化构形库,并运用GD进行合法化操作。另外,提出了一种最优个体选取方法和一种构形更新机制,结合快速非支配排序法,从进化构形库中挑选若干优良个体,并对构形库进行更新。经多次更新构形库,最后得到一组Pareto最优解。通过对当前国际上3个典型算例进行计算,实验结果表明,算法MOCSEA具备较好的求解性能。