复杂性能驱动的两类布局问题分治与阶梯式优化理论与方法研究

项目名称： 复杂性能驱动的两类布局问题分治与阶梯式优化理论与方法研究

项目编号： No.61272294

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 自动化技术、计算机技术

项目作者： 黎自强

作者单位： 湘潭大学

项目金额： 70万元

中文摘要： 复杂性能驱动的布局问题属NP完全问题，很难求解. 目前,启发式和演化计算是两类有效方法.但前者针对性强,后者干涉量计算耗时是其它计算耗时总和的50-500倍,已成为其求解精度和效率提高的瓶颈.针对加权和平衡约束两类布局问题,研究无干涉量计算的分治与阶梯式优化方法和求解精度控制新机制,建立复杂性能驱动的布局问题数学模型; 受人机结合思想启示，从问题本身的已知信息和问题领域发现并获取布局知识，研究基于布局知识构造可行或亚可行布局方案(1-3个相交待布物)的、计算复杂度较低的启发式规则和方法; 研究阶梯式优化策略,启发式构造与阶梯式并行演化结合搜索近似最优解,并调整它为最优解的分治优化机理;构建实验平台以构成完整的求解体系. 预计:提出的方法比现有方法提高效率5倍以上,求解精度和稳定性都明显提高.本项目的研究成果为其应用打下基础,也为其它复杂布局问题求解提供理论与方法上的借鉴和指导.

中文关键词： 装填问题；下料问题；知识；启发式方法；群智能优化

英文摘要： Layout problems with the complex performance constraints belong to NP-complete problem, and are difficult to solve in polynomial time. Currently, heuristic methods and evolutionary computation are two types of effective approaches. But the pertinence of heuristic methods is stronger than other approaches, the time of overlapping calculation of evolutionary computation is 50-500 times of others' calculation time, and has become the bottleneck that restricts further improvement on performances of evolutionary algorithms for the larger scale complex layout problems. Aim at the layout problems with equilibrium constraint and the weighted layout problems, a stepwise optimization strategy and divided-conquer optimization mechanism without overlapping calculation is proposed, in which the heuristic and stepwise parallel evolutionary iterative search(e.g. any colony optimization) with the adjust strategy is combined, and propose a corresponding mathematical model;Inspired by the idea of the human-computer cooperation, the main contents for this project are included as follows: the layout knowledge from the known information and the field of the layout problem is discovered; layout knowledge based heuristic mechanism and high performance heuristic algorithm with the lower computation complexity is presented to be used to

英文关键词： Packing problem；Stock cutting problem；Knowledge；Heuristic mathod；Swarm intelligent optimization