求解加权圆集布局问题启发式演化算法的研究

《求解加权圆集布局问题启发式演化算法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ResearchonEvolutionaryAlgorithmwithHeuristicStrategyforWeightedCirclesLayoutProblemCandidateXieYanfangSupervisorLiZiqiang(professor)CollegeSchoolofinformationandengineeringProgramTechnologyofComputerApplicationSpecializationIntelligentComputingDegreeMasterofeng

2、ineeringUniversityXiangtanUniversityDateMay20th,2012湘潭大学学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名：日期：年月日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家

3、有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权湘潭大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期：年月日导师签名：日期：年月日摘要带性能约束布局问题有着较为广泛的应用背景。如钢铁企业的板材切割(最大成材率约束)，印刷电路板(PCB)的布局设计(最小权距积之和约束)，航天器舱的布局方案设计(最小不平衡量约束)及工厂机床设备布置(最小货运花费约束)问题等。目前，加权布局问题与带平衡约束的布局

4、问题是我们课题组主要讨论的两类2维带性能约束布局问题。本文研究前者，由于加权圆集布局问题属于NP-hard组合优化问题，在多项式时间内求解是十分困难的。因此，学者们进行了深入研究，并提出诸如启发式和演化算法等有效算法。但计算精度和计算效率都有待提高,尤其是大规模布局问题。为此，本文在湖南省自然科学基金和湖南省教育厅基金项目的资助工下，对加权布局问题展开研究，提出一种求解加权圆集布局问题的有效机理和算法。主要工作如下：1.本文针对加权圆集布局问题，提出一种新的启发式算法。它是根据问题本身的已知信息，获得其布局知识，用于

5、建立启发式定序和定位规则：圆半径和权矩阵的行向量范数作为轮盘赌选择的概率因子，对圆集的放置顺序进行定序；定位采用外围逆时针排列定位规则。该启发式算法能快速构造出外包络矩形面积较小的布局方案，且计算复杂度低。2.本文针对加权圆集布局问题提高一种蚁群布局优化算法。它是将提出的启发式策略和蚁群算法相结合。实验结果表明：提高的算法比已有算法提高了计算精度。3.本文针对加权圆集布局问题提高一种带拟人策略的粒子群优化算法。该算法是将拟人策略与粒子群局部优化算法相结合，对通过启发式构造得到的较优解作进一步优化，获得最优解。数值试验

6、验证表明：与已经存在的算法相比，本文算法的计算效率和计算精度都得到了明显的提高。本文以印刷电路板布局和车间机器摆放为背景，充分利用布局问题本身的已知信息研究了加权圆集的布局问题的优化求解算法。先给出一种启发式算法，进而探索出启发式蚁群算法和拟人粒子群算法，较好地解决了二维加权圆集布局问题。最后，希望本文算法能推广应用于其他同类布局问题。关键词：加权圆集布局问题；启发式；拟人粒子群；粒子群算法IAbstractLayoutproblemwithperformanceconstraints(PCLPproblem)has

7、widespreadapplicationbackground,forexample,cuttingplatesofironandsteelplateenterprise(themaximumproductrateconstraint),thelayoutdesignofprintedcircuitboard(PCB)(theminimalthesumofweighteddistanceproductconstraint),thelayoutschemedesignofspacecraftcabin(theminim

8、alunbalanceconstraint)andmachineequipmentlayoutinfactory(minimumfreightcostconstraint)etc..2-dimensionalPCLPproblemsdiscussedcurrentlyincludetheweightedlayoutproblemandlayou