【作者】 王大志；

【导师】 汪定伟； 叶伟雄；

【作者基本信息】 东北大学 ， 系统工程， 2009， 博士

【摘要】 随着计算机软、硬件的发展和广范应用,智能优化技术得到了迅速发展,并被广大科技人员引入工程优化领域来求解各种复杂工业过程问题,以期获得更大的经济效益和社会效益。大量的实践表明,经过优化方法的处理,对系统生产效率的提高、资源合理的配置、能耗降低以及经济效益的提升均有显著的效果。由于工程领域中的很多实际问题都可以归结为某个特定数学模型下的优化问题,因而高效的寻优算法对于工程问题的解决有着至关重要的影响。目前,智能优化方法作为替代传统优化方法一个有力工具已在社会生活的各个领域和工农业生产的各个部门发挥着巨大作用,比如机械系统中的结构优化设计、计算机图形学中的图像优化处理、流程工业中的系统优化、运输系统的优化调度、生产过程的最优排产、国土资源的优化配置以及最优开发等。粒子群优化算法(Particle Swarm Optimization,PSO算法)源于对鸟群和鱼群的群体运动行为的研究,是一种新颖的群体智能优化算法,是计算智能领域中的一个新的分支。它的主要特点是原理简单、调节参数少、收敛速度较快。该算法从提出之日起便引起众多学者的极大关注,并且在工程应用领域得到了广泛应用,取得了良好的效果。因此本论文围绕着粒子群优化算法及其应用,就如何提高PSO算法性能以及该算法在非线性方程组求解、多峰函数优化、路径优化、选址优化中的应用进行了深入的研究。为了解决上述问题,本文遵循文献综述—问题提出—算法应用的思路依次进行解决,具体研究工作如下：(1)文献综述部分对智能优化方法的产生、发展历史及各主要分支领域进行了详细论述。首先对计算智能这一概念的提出做了简要回顾,介绍了计算智能在数值优化领域中具有的突出优点。接着针对计算智能的三个主要分支领域：神经网络、进化计算、模糊系统分别进行了论述。然后重点介绍了进化计算领域中遗传算法、群体智能领域中粒子群优化算法并总结了粒子群算法在各工程领域的成功应用案例。(2)非线性方程组的求解问题一直是科学技术和工程应用中的常见问题。在基于最大熵法的材料定量织构分析中,对于一组数目庞大的非线性方程组的求解成为此方法得以顺利进行的关键因素。由于需要求解的变量众多并广泛分布在指数位置上,因此对此类变量的处理显得尤为困难,稍有不慎将带来数值计算“溢出”而导致整个求解过程的失败。对该类问题的传统求解方法一方面对方程组本身提出了较高的特性要求,另一方面,初始迭代值选取不当将会致使求解过程陷入局优而影响计算的正确性。本文尝试应用具有随机性和种群并行性的PSO算法来求解此类优化问题,为最大熵法在定量织构分析中提供了一种稳定求解手段。(3)电路板元器件的缺陷检测属于PCB质量控制领域中一项重要研究内容。本文针对基于机器视觉的检测方法,提出了一种多模版匹配的技术来检测PCB上具有多个方向的多元器件缺失问题,并将此类问题转化为多峰函数的优化问题,接着对比分析了各种进化算法在求解多峰函数中的不同策略。将最近提出的Species-PSO算法应用在PCB检测过程中,并着重考察了算法的不同参数设置对搜索效率的影响。为了进一步提高检测效率,提出了三种加速策略,即1)NCC—MTM存储表；2)重新初始化间隔；3)局域搜索过程。通过大量的计算仿真分析,证明了加速策略的有效性。最后与GA-MTM进行了对比测试,表明SpeciesPSO在搜索效率上优于GA-MTM.(4)针对钢铁企业的板坯轧制计划问题的解非均衡性问题,提出了基于任务均衡的多旅行商模型进行求解。再介绍了旅行商和多旅行商问题以及求解方法,然后针对多旅行商问题的四种模型及求解方法分别进行阐述。接着重点讨论了一类特殊的多旅行商问题—即任务均衡的的多旅行商问题。对任务均衡的多旅行商问题提出了一种模型描述方法,并采用“两阶段法”进行求解。最后以TSPLIB中测试数据进行仿真计算。(5)选址问题是一类被广泛研究的组合优化问题。本文首先回顾了选址问题的历史,接着介绍了各种不同类型的选址问题,然后重点讨论了无容量约束选址问题的模型及各种求解方法。随着计算硬件的不断发展,多核心处理器正逐步替代单核心处理器进入普通消费者人群,如何能够更好地利用多核心处理器的计算能力是摆在每位从事科学计算工作者面前的课题之一。本文尝试将基于OpenMP技术的并行计算策略引入多种群的PSO算法来求解无容量约束的选址问题,与传统串行算法相比：并行计算在规模更大测试问题能够表现出明显的优势。更多还原

【Abstract】 Artificial intelligence optimization techniques, abbreviated as AIOT, are booming dramatically with the fast development and extensive application of computer hardware together with software. Many researchers and engineers has introduced artificial intelligence optimization technique (AIOT) into the field of engineering optimization to solve and optimize complex industrial production process in order to obtain both the maximum economic efficiency and social benefits. Lots of research and practice have proved that production efficiency and economic benefits can be significantly increased through the application of optimization techniques including the reasonable allocation of resources and energy consumption reductionSince many engineering problems can be induced as an optimization problem under certain mathematical model, highly efficienct optimization algorithem greatly influence the quality of the solution. From a great variety of practical industrial applications, artificial intelligence optimization has been proved to be an efficient optimization tool over conventional optimization methods.By now, AIOT has played a very important role not only in all the aspects of social area but also in the industrial and agricultural production departments, e.g., structural optimization in designing mechanical systems, computer based image processing, optimization of planning and scheduling system in process industry, transportation scheduling optimization, optimization of resource configuration and territorial development.The idea of Particle Swarm Optimization (PSO) is derived from the observation of bird fish and flocks movments. PSO is a novel swarm intelligence optimization algorithm and thus boosts the new branch of computational intelliegence. It is chiefly characterized by its simplicity of implementation, fast converfence speed and few parameters to manipulation. Its emergency has provoked a wide range of responses in the field of academic world and indutrial application. This dissertation mainly concerns on the applicaton of PSO algorithm in the area of modern industry and performance enhancement in the solution of nonlinear equation system, multimodal optimization, route optimization and location optimization.The research work mainly consists of three parts and is organized by the sequence of general description of artificial intelligence optimization technique (AIOT), problem demonstration, and presenting algorithm application. Research contents in details are shown as followings:(1) Origination, development history and main subfields of AIO technique are treated minutely in this part. First, a brief review of AIO, including the concept and initiation, is introduced and its prominent advantage is also described in the filed of numeric optimization. Then, three categories of AIO are presented, namely artificial neural network, evolutionary computation, and fuzzy system, respectively. Furthermore, genetic algorithms in evolutionary computation area, particle swarm optimization in swarm intelligence emphasized. Then successful applications of PSO in different engineering areas are summarized(2) Solution to the noneliear equation systems has always been the common obstacle in scientific research and engineering application. How to obtain a satisfactory solution to large quantities of noneliear equation in a reasonable computation time plays the key role in the process of texture analysis based on maximum entropy method. As all the solution variables exits on the exponential form, mishandling to them could results in the "overflow" phenomenon. On the one hand, classic numerical solution to such problem requires the equation to satisfay characteristic. On the other hand, initial iterative value is also difficult to determine before optimizing process by classic method. This research develops an stochastical and parallel searching PSO algorithm to solve such optimization problems and provide a robust computation technique for maximum entropy method in texure analysis.(3) Defect dection in printed circuit board industry is the major reseach problem in quality control procedure.Based on machine vision detecting method, this paper proposes a multi template matching method to locate multiple components with multi-direction, and the problem is transformed to a multimodal function optimization problem. Then various strategies embedding in evolutionary algorithms for solving multimodal problems are compared and analyzed. The newly developed species based particle swarm optimization is introduced in the PCB inspection procedure. In order to improve the inspection efficiency, three acceleration strategies are proposed. The three methods are called NCC-MTM store table, re-initialization procedure, and local search respectively. From experimental test, the acceleration strategies are proved to be efficient in locating multi components. Finally, a comparison of GA-MTM and Species-PSO are conducted to show that Species-PSO exceeds GA-MTM in computation time.(4) A balanced assignment multiple travelling salesman model is proposed to solve the production plan problem of hot rolling slab batch scheduling in steel company. First, a brief introduction to TSP and MTSP problem and corresponding solutions are demonstrated, and then four MTSP models are presented. A specific MTSP model which requires balanced workload is presented and a two stage solution method is introduced to solve the balance problem. Finally, simulation verification is performed by using TSPLIB data.Location problem is a widely studied combination optimization problem. This work first reviews the history of location problem and then introduces major variants of such problems. The model and various solution techniques for uncapacitated facility location problem are emphasized in description. As the computer hardware is upgrading fast, how to fully utilize the super performance of modern multi-core processor is a big problem with high priority for scientific researchers. This dissertation proposed OpenMP based parallzation method for solving UFLP by a multi swarm particle swarm optimization. Compared with serial executive PSO, the parallelized OpenMP based multi swarm optimization excels in computation time especially in larger scale benchmark problem.更多还原