论文部分内容阅读
Memetic算法是一种有效的进化算法,最初被视为一种改进的遗传算法,随着研究的不断深入,Memetic算法已发展成为一种由全局搜索(Global Search, LS)策略与局部搜索(Local Search, LS)策略构成的优化算法框架。在这个框架下,采用不同的搜索策略可以构成不同的Memetic算法。粒子群优化(Particle Swarm Optimization, PSO)算法是一种模拟自然界的生物活动以及群体智能的随机搜索算法。模拟退火(Simulated Annealing, SA)算法的思想来源于物理退火原理。本文通过对粒子群优化与模拟退火算法的研究与分析,针对现有Memetic算法收敛速度慢、容易陷入局部极值等不足,提出一种基于改进PSO和SA的Memetic算法(PSO-Memetic,PMemetic),并在6个典型函数优化问题上实验,与PSO算法进行比较分析,实验结果表明PMemetic算法提高了全局搜索能力、收敛速度和解的精度。最后将算法应用于智能组卷问题,取得良好效果。本文的主要工作和创新点如下:(1)根据GS策略与LS策略结合方式的不同,提出了Memetic算法框架,建立了两种策略顺序执行的S-PMemetic(Sequential Execution PMemetic, S-PMemetic)算法和交替执行的A-PMemetic(Alternative Execution PMemetic, A-PMemetic)算法。S-PMemetic算法先执行GS策略,如果能得到最优解则输出结果并结束算法,否则对产生的新群体进行局部搜索。A-PMemetic算法是GS策略与LS策略交替执行,随着算法的执行同时进化。实验结果表明S-PMemetic算法与A-PMemetic算法的各项性能指标都优于PSO算法。S-PMemetic算法在求解单峰、简单的函数时算法效率要高于A-PMemetic算法,但在求解多峰、复杂的函数时,A-PMemetic算法的性能要优于S-PMemetic算法。(2)借鉴萤火虫优化算法的局部决策域思想,提出一种带有动态邻域结构的改进PSO算法。在萤火虫优化算法中,萤火虫个体会被更亮的邻居吸引并向其运动,这些运动仅取决于萤火虫的局部(可变邻域范围内)信息和萤火虫与所选择的邻居之间的相互作用。因此,群体被分割为不相交的子群,能够使一个给定的多峰函数收敛到多个最优解。由于每个萤火虫都能被抽象为一个粒子,所以可以很方便的将该思想引入PSO算法。将改进PSO算法作为S-PMemetic算法与A-PMemetic算法的GS策略,可以有效地增强算法的执行速度与解的精度。(3)将A-PMemetic算法应用于多约束智能组卷问题。开发的教学管理系统包括教师、学生以及管理员模块,该系统的核心功能是教师与学生的互动和智能组卷功能。智能组卷可以为教师提供高质量的试卷,方便教师在线布置作业与在线考试,测试和应用表明采用A-PMemetic算法得到的试卷质量明显高于PSO算法得到的试卷,算法的可行性、有效性和实用性均得到了验证。