【作者】 高芳；

【导师】 崔刚；

【作者基本信息】 哈尔滨工业大学 ， 计算机系统结构， 2008， 博士

【摘要】 随着科学技术的发展,国民经济和国防科技等领域的生产过程越来越离不开优化设计,尤其是大量的高、精、尖产品,更需要性能非常优越的优化方法。粒子群算法具有原理简单、参数少、易实现及收敛速度快等特点,该方法对于不同类型问题具有较广泛的适应性,并很快在多个领域被有效地应用。粒子群算法作为一种新的智能算法,存在着迭代初期易出现早熟、迭代后期收敛速度变慢等问题,在应用拓展上也依赖于具体问题。为此,本文对粒子群优化算法进行了深入的理论分析,面向连续优化问题和组合优化问题,针对算法所存在的问题提出几种相应的改进新算法,并将其应用到具体工程实践中。在单目标连续优化方面,本文提出将多种群思想引入到粒子群优化算法中,提出了一种双层多种群粒子群优化新算法,该算法实现粒子群优化算法的群体拓展和双并行运行机制,这样可以针对性地提高粒子群算法的全局搜索能力,同时采用不同粒度的多子群并行机制和种群间的双向最优信息流动也提高了该算法的局部搜索能力。通过对多个多峰、欺骗性典型函数的测试验证了上述算法的有效性,进一步通过对机器人结构参数的优化实例验证了本算法的实用性。粒子群算法后期收敛速度较慢的主要原因是群体中各个个体极值更新缓慢。为此本文提出一种粒子位置择优更新的粒子群算法。利用粒子位置的可择优更新,就是使每个粒子在每步迭代时都可以从3个备选点中选择最佳点进行更新,增加了粒子找到更好位置的概率,提高了个体极值乃至全局极值的更新速率,以极小的时间代价提高了算法的效能。通过六个典型测试函数和移动机器人路径规划的实例对该算法的实用性和有效性进行了验证。多目标约束优化一直是优化领域中的瓶颈问题,除需处理多个目标外,还存在着约束处理影响计算效率的问题。粒子群算法只保留最优信息,对邻近最优点的不可行解缺乏智能性的判断和保留机制,在解决多目标优化问题中效果不理想。而文化算法由于具有基于文化的信仰空间和群体空间的双并行机制,特别适合处理约束优化问题。为此本文提出一种求解多目标约束优化问题的双层次进化的文化粒子群算法。新算法在群体空间采用改进的粒子群算法,并采用直接比较法处理约束条件,避免了传统罚函数方法存在的缺点。在算法迭代过程中随时调整不可行解参数,使解集中不可行解保持在一定的比例范围内,维持了种群的多样性,进一步避免算法陷入“早熟”,提高了算法全局搜索能力。信仰空间接收群体空间中的精英粒子,并采用了交叉操作和小生境Pareto竞争策略保证所产生的最优解集能够均匀地分布在Pareto前沿。最后采用两个测试函数和一个工程减振器的优化设计实例对此算法进行了验证,测试和实例计算表明该算法是一种快速、有效的多目标优化方法。组合优化问题具有广泛的应用背景,它的目标是寻找解空间中离散状态的最优组合。离散粒子群算法为求解这类问题提出了一种新方法,本文针对基本离散粒子群优化算法存在的易于陷入局部最优解、求得的解的精度不高的缺点,提出了两种具体改进新算法:以典型的01背包问题为研究对象,基于生物病毒机制和宿主与病毒基于感染操作等思想,提出一种解决单目标组合优化问题的病毒协同进化离散粒子群优化新算法。该算法利用病毒的水平感染和垂直传播能力提高粒子群算法的性能。实验证明,病毒感染操作成功地增强了对解空间的局部搜索功能,使求解精度明显优于其它几种算法。以典型的虚拟企业中的伙伴选择问题为应用背景,研究将离散粒子群算法应用到多目标组合优化问题。基于改变粒子速度策略提出了粒子速度阈值可调的离散粒子群优化新算法。该算法通过引入随迭代过程逐步变小的适应性可调速度阈值参数来平衡全局搜索能力和局部搜索能力之间的矛盾,提高算法的性能。更多还原

【Abstract】 With the development of science and technology,the production process in national economy and defense science and technology field needs optimization design. Especially there will be a large number of high, precise, advanced products in aeronautics and astronautics fields in great need of more ascendant optimization methods. Particle Swarm Optimization (PSO) algorithm has the advantages of simple theory, less parameters, easy realization and quick convergence. Meanwhile it has the widespread adaptivity for different types of functions and has been applied in many fields.However, because PSO algorithm is a new arisen intelligent algorithm, it has the drawbacks of easy premature in initial iteration stages, and slowed-down converging speed in final stages and so on. Furthermore, the application expansion of PSO algorithm depends more on specific problems. Therefore this thesis mainly focuses on the deep theoretical analysis on PSO algorithm. Aiming at solving continuous and combination optimization problems, this thesis discussed the improving strategies to overcome the above drawbacks, put forwards a series of new algorithms and applied them into specific engineering practices.In terms of single-objective continuous function optimization, this thesis introduces the multi-swarm idea into PSO algorithm and put forward a two-layer multi-swarm particle swarm algorithm. This algorithm realized the swarm size expansion and the dual parallel-running mechanism, so it can purposefully enhance the algorithm global search ability. Meanwhile the different granularity multi-subswarms parallel mechanism and dual direction optimal information flow between subswarms also increases the algorithm local search ability. Tests on multimode and fraudulent typical functions verified the effectiveness of the above algorithm. An application Example of robot structure parameters optimization is further completed to testified its feasibility.Theory analysis and simulation tests in this paper show that the slow updating rate of individual best is one main cause for the slow converging speed in the later iteration stage of PSO algorithm. Therefore this thesis put forwards a vector position selecting-best updating PSO algorithm. In this algorithm, the position of each particle can be updated in a selectable way, namely each particle can select the best one from three candidate points as the new position, which can heighten the probability of finding much better position and increase the updating rate of individual best and global best. It consequently raises the algorithm performance with less computing time cost. By means of six test functions and an application example of mobile robot path planning, the feasibility and effectiveness of the algorithm is verified.Multi-objective constrained optimization has still been the bottle-neck problem in optimization field. Besides handling multiple objectives, it also has the problem that its constraint handling will affect the computing efficiency. PSO algorithm only keeps the optimal information and lacks of the intelligent judgment and reservation mechanism for the unfeasible solutions adjacent to the optimum,so it cannot get a satisfactory results in multi-objective optimization. Cultural algorithms are particularly fit for the constrained optimization problem because of its culture-based dual parallel mechanism of belief space and population space. Therefore this thesis put forward a dual level evolutionary cultural particle swarm algorithm for multi-objective constrained optimization problems. This new algorithm takes the improved particle swarm algorithm as its population space. It uses a direct comparison method to handle constraint conditions which can avoid the demerits of traditional penalty function method. Moreover, an adjustable parameter is regulated in a real-time way during the iteration process to keep unfeasible solutions within a certain proportion range and to maintain the diversity of the whole swarm. Therefore the evolutionary process in population space can avoid the premature problem and increase the global search ability. The belief space accepts the elitist particles from the population space. A crossover operation and niche Pareto competition strategy are further executed to ensure that the optimal set can be distributed uniformly on the Pareto frontier. Two test functions and an application example of engineering damper optimization design are finally presented to verify this algorithm,test and experiment results show this algorithm is a quick and effective multi-objective optimization method.Combination optimization problem has many extensive application backgrounds, and its objective is to find the optimal combinations of discrete status in the solution space. The discrete particle swarm algorithm presents a new solution for this kind of problems. This thesis considered the prime discrete particle swarm disadvantages of easily trapped local optimum and low solution precision, and put forward two specific new improved algorithms as follows.Taking the typical 0-1 knapsack problem as the research objective, this thesis put forwards a new virus co-evolutionary particle swarm algorithm for single objective combination problem based on bio-virus mechanism and infection based operation between host and virus. This algorithm utilizes the virus horizontal infection and vertical propagation ability to enhance its performance. Experiments show that the virus infection operation strengthens the local search ability in the solution space and the solving precision obviously outperforms several other algorithms.Taking the partner selection problem in virtual enterprise as the application background, this thesis discuss to apply discrete particle swarm algorithm into multi-objective combination optimization field. A new speed threshold adjustable discrete particle swarm algorithm is put forward based changing particle speed. By means of an adaptively adjustable speed threshold parameter to decrease with the iteration process, this algorithm can balance the contradiction between global search and local search, so it can heighten the computing performance.更多还原