基于蚁群算法的类tsp积木块布局优化算法new

《基于蚁群算法的类tsp积木块布局优化算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、天津大学硕士学位论文基于蚁群算法的类TSP积木块布局优化算法QuasiTraveHngSalesmanProblemAlgorithmofBuildingBlockLayoutOptimizationBasedAntcolonyAlgorithm(申请硕士学位)专业：童工理诠生堑捷丕研究生：奎董指导教师：塞堂呈副教授天津大学电气与自动化工程学院二零零四年十二月摘要计算机辅助集成电路版图设计技术又称布图设计技术，它是一门涉及计算机科学与半导体技术的交叉学科。布图设计自动化是整个集成电路设计工程中与产品的研制和生产直接相关的一个设计过程，并且直接影响到IC电路的设计周期、成本

2、、正确性和产品质量“1，其内容包括设计评价和版图校核、布局设计、布线设计几个方面，其中的积木块白局设计己被证明是集成电路布图设计中的一个NP完全问题。蚊群算法(AntcolonyAlgorithm)强1是一种适合于多变量组合优化问题的随机型全局搜索算法，它是群体智能系统最成功的例子之一，如今已被广泛应用到诸如经典TSP问题以及通信网络路由问题等许多类型的问题，受蚁群算法在解决NP问题中所表现出的优良性能的启发，本文将蚁群算法加以进一步改进后用于求解积木块布局设计中的布局优化这一过程。本文在深入研究积木块布局问题的基础上，针对将传统蚁群算法模型用于求解积木块布局问题时无法满

3、足布局过程中积木块单元位置始终处于移动状态下这一要求，文章采用了一种类TSP模型的概念，能够将积木块初始布局转化为一种类似TSP的积木块布局形式，从而建立了一种瓤的类TSP积木块布局优化模型，此外本文还对传统蚁群算法模型中的两个主要更新公式进行了改进并运用于布局优化求解中，并在此基础上提出了基于蚁群算法的类TSP积木块布局优化算法，从而使每一个积木块单元可以在搜索区域内时时进行移动和旋转的同时采用改进后的蚁群算法求解出最优布局结果，并且布局结果满足积木块单元之间所必需的连线关系。为提高算法运算速度，避免过早陷入局部优化，本文对此还提出了相应的改进方法，并进行了理论分析和仿

4、真实验，实验结果表明，该算法是一种有效的积木块布局优化算法，具有一定的实用价值。关键词：蚁群算法，积木块布局，类TSP模型，布局优化AbstractPhysicaldesignCADofintegratedcircuitisalsocalledlayoutdesign．Itbelongstoacrosssubjectbeinginvolvedwithcomputerscienceandsemiconductortechnique．Layoutdesignautomationisanimportantprocesswhichiscorrelativewiththemanuf

5、actureandproductioninwholeICdesignprojectandbeingrelatetothedesignperiod，cost，validityandqualityoftheICItscontentsincludedesignevaluationandphysicalcheck，placement，routingandSO01"I．BuildingblocklayoutplacementhasbeenprovedthatisaNP—completeprobleminIClayoutdesign．Antcolonyalgorithmisaking

6、ofwholestochasticsearchalgorithm．ItisthemostfamousexampleoftheswarmintelligencesystemsandhasbeenappliedtoseveralTSPproblemsandroutingproblemsincommunications．EnlightenedbythegoodperformanceofthealgorithminresolvingtheTSPproblems，thispaperadoptantcolonyalgorithmimprovedinresolvingtheoptimi

7、zationofBBLplacementdesign，namelytheiterativeprocessoftheplacementoptimization．BasedontheresearchoftheformerBBLplacementproblemsaidtheinextricabilityofthepositionmovementinBBLplacementdesignbytraditionalantalgorithmmodel，thepaperproposesakindofdefinitioncalledquasiT