论文部分内容阅读
在科学研究、现实生活中往往存在着许多优化问题,通常分为连续型优化问题和离散型优化问题。而离散型问题形式简单,有许多连续型问题不具备的特点与优势,因此常将连续型问题转化为离散型问题进行研究。离散烟花算法(discrete fireworks algorithm,DFWA)是北京大学谭营教授继2010年开创性论文“Fireworks algorithm for optimization”后提出的一种解决离散问题的群智能算法,并应用于旅行商问题(Travelling salesman problem,TSP)。随着烟花算法的不断改进,其在连续优化问题中已经表现出了出色的寻优能力,但离散烟花算法在路径优化问题方面的研究还很缺乏。因此针对其易陷入局部最优、选择策略随机性较大等局限性,本文提出一种基于改进选择策略的离散烟花算法,研究工作主要包括:(1)针对离散烟花算法的精英选择策略的不稳定性,提出利用确定性选择和随机选择相结合。改进算法将备选种群内的父代烟花剔除,只在子代火花种群中进行选择,并且将轮盘赌策略改进为多轮轮盘赌增加了选择次数与精度。由于均匀变异操作只接受更优的解,因此一定程度上增大了选择到优质种群的概率。新的选择策略不仅能够增强算法前期的全局搜索速度,提高了寻优能力。(2)通过动态参数来调整子代的选择数目。迭代前期子代数目随着迭代次数的增加和增大因子来适当增加子代数目,扩大搜索范围,而由迭代次数影响的参数使得适应度较小的个体更容易被选择,在迭代的中后期最优解已经趋于稳定,则不需要过多的子代进行重复操作,而适当增加适应度较大的个体被选概率可以防止算法搜索过程中出现早熟。(3)为了验证改进算法的实用性,本文将其应用于TSP问题中,在模拟的34个地点进行实验,将路径距离之和作为适应度函数,并和遗传算法、蚁群算法进行对比。进一步验证所提改进离散烟花算法的性能,在Matlab R2016a软件上将该算法应用到TSP标准数据集中进行测试,并与GA、PSO和ACO各运行50次,从算法收敛性、稳定性以及精度进行对比。(4)延伸该算法的应用空间,本文针对多旅行商问题进行了分析,以单一原点和多原点分别有无闭合回路这四种情况进行数学建模,将改进算法应用于MTSP中。其过程主要包括对四种MTSP情况建立数学模型,编制仿真程序,进行对比实验验证算法性能。