论文研究-基于改进PSO和Tabu的混合算法 .pdf

所需积分/C币:9 2019-08-16 14:25:09 399KB .PDF
1
收藏 收藏
举报

基于改进PSO和Tabu的混合算法,李勇刚,邓艳青,针对粒子群优化(PSO)算法在优化过程中容易早熟和局部寻优能力差,禁忌搜索(TS)算法依赖于初始解等问题,研究两者的优势和不足�
山国武花论文在丝 禁忌搜索变异粒子群算法 算法思想 算法容易早熟收敛且局部寻优能力较弱,因为当全局最优位置处于某个局部最优点 时,其巨大的吸引力使得其亡粒子快速聚集到局部最优点,粒子群表现出强烈的趋同性,造 成早熟,故早熟收敛往往是由于种群多样性匮乏或陷入局部最优导致的。故在整个搜索过程 中,以线性递增的概率对最优粒孓实施随杋扰动,可以维持种群的多样性和增强全局搜索能 丿。是一种局部搜索能丿很强的优算法,利用其较好的记忆能丿,可以较快地收敛于 最优路径上,但算法初期会由于信息素赍乏,导致收敛速度低,得到的解质量也不髙。如果 在搜索后期引入,可以提高局部开发能力 采用两阶段的优化策略:第一阶段利甪加入随机扰动的算法进行全局搜索,待全局 搜索收敛到一定程度后,即搜索到最优解可能岀觋的区域后;第二阶段利用算法进行精 细的局部搜索,在得到算法提供的优良初始解的情况下,充分利用算法的较强“爬山” 能力,求精解效率晑地特点,使算法快速收敛到全局最优解。 算法充分利用算法的快速性和随机性,全空间地搜索最优解可能存在的 区域,和禁忌搜索算法的记忆功能及爬山能力强的特点,解决算法陷入局部最优的问题。而 改进算法能够提供最优解所在大致的位置,可以弥补对初始解的依赖性的缺点。 关键参数 ()禁忌搜索开始准则 在进行全局搜索时,种群在最近的代内适应度值的相对变化率如果小于阈值£,表明 种群收敛到了一定程度,这时算法开始进行局部搜索,寻求最优解。故定义为 E ()的邻域函数 邻域是指从当前解经过移动能够到达的所有解的集合。釆用互换操作( )邻域结 构,,即随机交换两个点的位置,所产生的新的个体组成此个体的邻域 ()禁忌表 本文禁忌表的规模采用 为粒了群的大小,对禁忌衣的更新采用“先进先出” 规则。 ()释放准则 采用 ”准则,即选取目前适应度最优的粒了,解禁该粒了并更新种群历史 最优解。 算法描述 算法的计算步骤如下 步骤随机产生初始种群,设定每个粒」的位置和速度,种群规模,粒子维数,禁忌长度, 最大迭代次数等。计算每个粒子的适应度值,并将每个粒子的设置为当前位置, 设置为群体中最好粒子的当前位置,置棼忌表为空 步骤根据和更新所有的粒子的速度和位置。 山国武花论文在丝 步骤计算当前的,如果<,则按照式对种群最好粒子进行扰动,得到新 的位置和速度。如果新粒子的适应度值优于,则选取新粒子的位置为 相 应速度也进行更新 步骤判断当前的适应度值变化率是否小于阙值E,若没有则转到步骤;否则进行下一步。 步骤用当前解的邻域函数产生·定数目的邻域解,进行禁忌搜索,并从中选取适应虔最好 的若干候选解。 步骤判断是否冇满足特赦准则的候选解,若有,则用满足特赦淮则的最佳候选解替代当前 解,并用与之对应的禁忌对象替代最早进入禁忌表的对象,同时用该候选解替代的历 史最优解,然后转步骤;否则进行下一步。 步骤判断候选解对应的各对象的鍫忌凨性,选择候选解集中非禁忌对象对应旳最仹状态替 代当前解,同时将对应的禁忌对象替代最早进入禁忌表的禁忌对象元素。 步骤判断是否达到最大迭代次数或满足收敛条件:若为杳,转到步骤。若淸足条件,输 出,算法运行结束。 仿真实验 为了测试木文所提出的改进 算法的寻优性能,采用三组经典基准函数 和 进行测试分析。第一个为单峰值函数,后一个为多峰值函数,所有 数的理论最小值均为。所有试验中,种群大小取为,搜索空间维数设为。测试函数定 义如下: 函数: 所数: ∑∏x+6 固定迭代次数下的收敛精度 设置最大迭代次数是次,每个算法都重复运行次。表反映了四个算法的优化结 果的比较。图和图反映的是四个算法在两种测试函数中寻优时,迭代次数与适应度的关系 曲线。 表优化结果的对比 山国武花论文在丝 Rosenbrock函数 TSRPPSO 200 400 600 800 1000 1200 1400 1600 1800 2000 达代次数 函数寻优曲线 ricwank函数 PSO RPPSO TSPSO TSRPTSO 00 1600 18002000 迭代次数 图2 函数寻优曲线 分析上述图表可知,在粒子的搜索过程中,在随权扰动、禁忌表的作用下 算法优化的效果明显比其他算法好。迭代了次以后曲线趋于直线,说明其发生了早 熟收敛,陷入了局部最优,且无法再跳出; 改善了的局面,却在后期陷入局部最 优,因为加入随杋扰动虽然维持了种群多样性,一定程度上缓解了早熟的趋势,但后期的局 部搜索能力不够,且其信息共亨机制是单向的,直接飞过全局最优解进入另一个局部最优, 或在几个局部最优之间来回跳动,无法靠近局部最优。 算法对于两种函数的改进效果 并不明显,这是因为对初始解的依赖性导致的。 算法在刚开始寻优时性能较稳, 山国武花论文在丝 然后进入适应值强烈振荡阶段。这是由于引入禁忌搜索算法,最优粒了会被加入禁忌表,引 起的适应值的反复振荡算法持续不断地向全局最优解靠近,在经过加入随机扰动的进 行大范围搜索后,基本确定最优解所在位置进行大致区域,利用其较强的”爬山”能力,使 其可以跳出局部最优,达到精度较高的全局最优值 禁忌表长度对算法的影响 禁忌表是禁忌搜索算法的核心,禁忌表的大小在很大程度上影响着搜索速度和解的质 量,可有助」识别岀曾搜索过的区域。为了测试禁忌表的长度对算法性能的影响,通过选取 不同的禁忌衣长度对 函数进行寻优,分析禁忌表长度对收敛精度的影响。定义全局 最优解即找到函数值为“小于”,则在这个收敛精度下经过次独立运行后参数见表。 其中:成功率达到精度的运行次数总试验次数。 表2禁忌表长度对算法的影响 禁忌表长度最小收敛代数平均选代次数成功率 从表可以看出:当禁忌表长度为时,搜索成功率较高,这是因为禁忌表长度太小,那 么搜索过程可能进入死循环,整个搜索将围绕着相冋的几个解徘徊;禁忌表长度太大,太多 的当前最优值被禁忌,可能会跳过好的解,不会改进解的效果,因而好的禁忌表长度是尽可 能小但又能避免进入循环。本文禁忌表长度值采用=√,即取 结论 本文结合禁忌搜索算法和粒了群算法各自的优点,提出了种基于禁忌搜索的随机扰动 粒了群算法( ),在随机扰动和禁忌搜索的作用下,算法能够很好地在局部搜索 和仝全局搜索之间进行转换,改善了采用单一搜索策略很难兼顾全局搜索和局部搜索的局面 实验结果表明了 算法的优化结果好于其它算法,能有效避免算法的早熟收 敛,并且收敛精度有所提高 参考文献 徐宁,李春光几和现代优化算法的比较研究系统工程与电子技术

...展开详情
试读 6P 论文研究-基于改进PSO和Tabu的混合算法 .pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
抢沙发
一个资源只可评论一次,评论内容不能少于5个字
weixin_39841365 如果觉得有用,不妨留言支持一下
2019-08-16
上传资源赚积分or赚钱
    最新推荐
    论文研究-基于改进PSO和Tabu的混合算法 .pdf 9积分/C币 立即下载
    1/6
    论文研究-基于改进PSO和Tabu的混合算法 .pdf第1页
    论文研究-基于改进PSO和Tabu的混合算法 .pdf第2页

    试读结束, 可继续阅读

    9积分/C币 立即下载 >