【作者】 李望移；

【导师】 郑金华；

【作者基本信息】 湘潭大学 ， 控制理论与控制工程， 2010， 硕士

【摘要】 优化问题广泛存在于科学研究和工程应用领域,研究其求解方法一直富有吸引力与挑战性。枚举法、基于梯度的搜索算法、牛顿法等传统的优化算法虽然具有数学基础完善、可靠性强和比较成熟等特点,但这些传统的优化方法具有计算复杂、对目标函数的导数连续性要求高等特点,同时,在面对离散、无导数、高度病态的优化问题时,传统方法常常也难以求得全局最优化解。近年来,以遗传算法和粒子群算法为代表的进化算法为求解此类复杂的优化问题提供了新的思路和方法。遗传算法具有智能性、不需求导或其他辅助知识等优点,粒子群算法则不需要借助问题的特征信息,设置参数较少,目前它们已成为求解优化问题的有效方法。但由于算法存在早熟收敛、易陷入局部最优的缺点,有时算法并不能满足实际应用的需求,因此设计求解优化问题的有效算法是非常有现实意义的。为此,论文选择遗传算法和粒子群优化算法这两种进化算法为研究对象,研究用其求解优化问题。论文的主要研究内容包括下几个部分:(1)分析了优化问题、遗传算法和粒子群算法的研究现状,阐述了遗传算法的基本原理和流程、构成要素等,介绍了粒子群算法的原理和步骤、基本特征等。(2)提出了一种改进的遗传算法——基于引导交叉的遗传算法(Leading Crossover Genetic Algorithm, LCGA):当两父代个体相似度较低时执行等位交叉操作产生新个体,父代个体相似度较高时则采用异位交叉的方法产生新个体。同时,用此改进的遗传算法对多个测试函数进行计算机模拟求解,将其与传统遗传算法的计算结果进行了对比,取得了令人满意的结果,验证了该策略的有效性。(3)将LCGA应用于背包问题的求解,采用贪婪修补方法来处理约束问题,结果表明LCGA算法比传统的遗传算法能够更加有效快捷地找到最优解,验证了LCGA算法的有效性和优越性。(4)提出了一种改进的自适应粒子群算法(New Adaptive Particle Swarm Optimizer, NAPSO)。在NAPSO算法中,惯性权值采取自适应调整的方式,并且在算法运行过程中,通过判断粒子群是否出现停滞现象来自适应地采取不同的速度和位置更新公式,以此来保持种群的多样性,从而以提高算法摆脱局部极值和局部搜索的能力。然后针对优化问题的测试函数进行了实验,并与传统的粒子群算法进行比较,验证了NAPSO求解函数优化问题的优势。本文的研究进一步丰富和完善了GA和PSO的理论和应用。更多还原

【Abstract】 Optimization problems exist in science research and engineering application, it is attractive and challenging to research the solving method. The traditional optimization algorithms such as enumeration method, search algorithms based on grads, Newton method etc, have the characteristics of a perfect mathematical foundation, reliability, maturation. But the traditional optimization algorithms have the complex computation and have the strict demand to the continuity of objective function. At the same time, it is difficult to search the global optimum when the optimization problem is dispersed, no derivative, severe pathological. In recent years, Evolutionary computation, such as Genetic Algorithms, Particle Swarm Optimizer, provides new ideas and means for solving optimization problems. Genetic Algorithm has the merits of intelligence, not requiring differential coefficient or other assistant information. And Particle Swarm Optimizer is not need the problem’s character information and not need to set many parameters. Genetic Algorithms and Particle Swarm Optimizer are effective methods to solve optimization problems. At the same time, algorithms exit some shortcomings, such as premature convergence, easily falling into local optimal solution. So optimization algorithms can not meet the needs of practical application. Then, designing effective algorithms for solving optimization problems is of practical significance.In this paper, it chooses Genetic Algorithm and Particle Swarm Optimizer as research objects, and research on solving kinds of optimization problems. The main contents of paper as follows:(1) The paper analysis optimization problems, Genetic Algorithm, Particle Swarm Algorithm, and elaborate the basic principles, basic processes, elements and the application of Genetic Algorithm, introduces the principles, basic steps and the basic characteristics of Particle Swarm Algorithm.(2) The paper proposes an improved Genetic Algorithm (Leading Crossover Genetic Algorithm, LCGA). It executes the same location crossover in order to generate new individual when two father individuals have the low similarity. Otherwise, when two father individuals have the high similarity, Genetic Algorithm executes different location crossover to get new individual. Then five different test functions are used to test the improved Genetic Algorithm. The simulation results show that the strategy is feasible and effective. (3) LCGA is applied to solving the knapsack problem which uses the method of greedy repair to handle constraints. The results show that Lead Crossover Genetic Algorithm finds optimal solution more effectively and more quickly than traditional Genetic Algorithm. It verifies the validity and superiority of LCGA.(4) The paper introduces an adaptive Particle Swarm Optimizer (New Adaptive Particle Swarm Optimizer, NAPSO). New Adaptive Particle Swarm Optimizer adaptively adjusts the inertia weight, and adopts different velocity and position formula according to judge whether there is stagnation of particle swarm in the run of algorithm. It will maintain the diversity of population, and improve the ability to out of local optimum and local search. Then, the proposed algorithm has been applied to a set of benchmark problems and compared with the traditional optimization algorithms. The results show the advantage of solving function optimization problems. The research will further enrich and improve the theory and application of Genetic Algorithm and Particle Swarm Optimizer.更多还原