论文部分内容阅读
差分进化算法(Differential Evolution Algorithm,DE)是一种基于种群个体差异、主要解决连续性优化问题的启发式随机搜索算法。自1995年R.Storn和K.Price为求解Chebyshev多项式提出之日起,因其高效的寻优能力、无需复杂的运算及编码机制等优点而在组合优化问题的求解中得到广泛的应用。本文对基本DE算法进行了研究,同时讨论了基本DE算法存在的易早熟和陷入局部极值的不足,并针对DE算法存在的不足,对基本DE算法进行了改进和扩展,同时证明了改进的DE算法的收敛性。并将DE算法应用于求解JSP调度问题。在对基本DE算法理论研究的基础上,借鉴社会学以及生物学的一些思想,对基本DE算法进行了以下改进：(1)针对DE算法在进化后期易陷入局部最优解的问题,提出一种Memetic算法,通过引入邻域搜索算子来增强种群多样性,保证算法有效跳出局部最优解点。针对差分进化算法后期收敛较慢的不足,对缩放因子进行自适应调整,保证算法具有较高的寻优性能的同时具有较高的收敛速度。(2)分析了DE算法中控制参数对算法性能产生的影响。种群进化过程中种群多样性的急剧降低是造成算法陷入局部最优和早熟的主要原因。为保持种群多样性,本文一改基本DE算法随机初始化种群带来的弊端,对初始种群采用服从正态分布的初始化方法进行初始化,有效保证了算法朝着最优解的方向进化。并加入自适应算子对种群进行动态调节,引入memetic算法使进化过程达到全局搜索和局部搜索的平衡。(3)DE算法主要解决连续性优化问题,采用实数编码,这种编码和解码机制可以遍布整个解空间,保证了算法的寻优性能。简化后的车间调度问题仍然属于NP-hard问题,同时也是多目标约束的离散问题。本文提出的改进的LPV(Largest position value)规则,将工件的一个排序映射为搜索空间的一个解。并采用改进的DE算法执行全局搜索,采用鲍德温算子执行局部搜索。Matlab数值实验结果表明：改进的DE算法使算法性能得到了较大的改善,并能实现Job-Shop调度问题优化。