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