论文部分内容阅读
布局问题来源于现代生产的许多领域并且表现为多种形式,如服装行业,部件拼装和超大规模集成电路(SLSI),但是由于布局问题具有高度的复杂性,属于组合优化问题和NP完全问题,它很难用单一的知识模型(如数学模型)来精确表达,另外,可用数学模型表达的部分具有NP完全计算复杂度。本论文对二维不规则多边形布局问题的求解算法(模拟退火法,遗传算法和合成多边形法)进行了深入研究。 模拟退火算法是一种用于解决连续、有序离散和多模态优化问题的随机优化技术。文中改进了模拟退火算法的搜索方法,采用扩展模式搜索:选择三种改变物体布局状态的方式(平移、旋转、交换),采取两种模式搜索矩阵(平移和旋转模式矩阵)。并给出了该搜索算法的一般模型,把该模型应用到不规则多边形的布局中,针对不规则多边形的具体情况,对它的相交判断以及其它约束条件进行了分析,如,两多边形互不重叠,所有多边形应完全放置在给定的矩形原料内,多边形布局完成后应尽量靠近原料的左下角,布局完成后多边形的总宽度要小于原料的宽度等。结果证明该算法提高搜索速度和布局效果。 遗传算法是一种基于生物学进化原理的搜索算法。文中把生物学中的遗传、变异、交叉用于二维布局中,从多个父代个体中生成多个子代个体,根据目标函数值的优劣进行淘汰。文中对其编码方式进行分析,采用模拟退火法产生初始布局,保证了父辈解群的优良性,采用交叉概率Pc有效地防止具有高适应度值的个体被排挤掉,变异概率Pm防止了搜索在成熟前收敛。而以随机的方式产生交叉断点和变异断点,则保证GA能搜索到空间的每一区域,使GA跳出局部最优解。结果表明应用该方法缩短了计算时间并使问题的解得到了很好的改善。 文中对多边形的合成技术进行了研究,通过模拟布局状态,吸取人工布局的经验,采用启发式知识控制搜索方向,限制搜索空间,把布局问题转化为在状态空间下寻找最优路径的问题。 最后,总结本文的工作并展望了进一步的研究方向。