近些年,研究者对装箱问题的研究方兴未艾,其中包括一维装箱问题、二维装箱问题以及三维装箱问题。而布图规划是二维平面的装箱问题,它是超大规模集成电路(Very Large Scale Integration,VLSI)物理设计的关键环节,它对最终芯片尺寸大小以及整体芯片全局互连结构有着十分重要影响。随着技术的发展,工业对芯片尺寸以及内部互连性能要求越来越严格,从而更加突出布图规划的重要性。对于布图规划问题,已研究的算法很少采用进化算法优化,这里运用一种新的编码方法(moving modal sequence,MMS),将全局搜索—遗传算法和局部搜索—禁忌搜索相结合对布图规划问题进行优化。我们知道,布图规划可以看成二维装箱问题,因此我们将该思路拓展到三维空间,即对三维装箱问题进行优化。我们将2D-MMS编码方法扩展到三维,形成3D-MMS。运用全局搜索—遗传算法和局部搜索—爬山法对三维装箱问题进行优化。论文的研究包括下面的内容。1.我们运用已有的编码方法MMS,将一个二维物体看成一个模块,放置之前随机产生移动模式,根据移动模式的值,执行不同的操作。我们知道遗传算法属于一种进化算法,由于进化算法与传统优化方法相比,具有普遍、鲁棒性能强和可以并行化处理等优点,但大量的实践表明,单独使用遗传算法等进化算法来求解这类问题是远远不够的,还要深层次研究和更加充分的利用生物的智能资源,因此我们运用密母算法对布图规划问题进行优化,即在遗传算法的框架下对每个个体进行局部搜索,并对MCNC,GSRC数据集进行实验,实验表明该算法可以快速找到最优解。2.我们将2D-MMS扩展到三维空间,提出了三维移动模式(three-dimensional moving modal sequence,3D-MMS),它是三维装箱(three-dimensional bin packing problems,3D-BPP)领域的一种新方法。本章介绍了3D-MMS的编码方法以及放置策略。3.三维装箱问题(Three-dimensional Bin Packing Problem,3D-BPP)是在工业生产中常遇到的问题,如船舶集装箱装卸、飞机货运管理、仓库管理等。在货物装载以及运输过程中,资源以及运输空间的高效利用是公司间的核心竞争力。因此由于其实际需求,寻求一种合理有效地放置策略仍然是研究的重要方向。基于这一点,我们在3D-MMS的基础上,用密母算法求解三维装箱问题。实验结果表明该方法在寻求多个最优解方面有明显的优势。