⑥变异,以一定概率从群体中随机选取若干个体,对于选中的个体随机选取某一位进行取反运算;
⑦对产生的新一代群体返回步骤③在进行评价、交叉、变异,不断的循环,使群体中个体的适应度和平均适应度不断提高,直至最优个体的适应度达到某一限值,或最优个体适应度和群体的平均适应度不再提高,则迭代结束。流程如图3.2所示:
图3.2 遗传算法流程图
3.3 粒子群算法
3.3.1 粒子群算法简介
粒子群算法[1],也称粒子群优化算法(Particle Swarm Optimization),缩写为 PSO,是近年来发展起来的一种新的进化算法。PSO算法属于进化算法的一种,和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质,但它比遗传算法规则更为简单,它没有遗传算法的“交叉”(Crossover) 和“变异”(Mutation) 操作,它通过追随当前搜索到的最优值来寻找全局最优。其理论基础主要包括以下几个基本步骤:①刺激的评价;②与临近的比较;③对领先紧邻的模仿。
PSO模拟鸟群的捕食行为,设想这样一个场景:一群鸟在随机搜索食物,在这个区域里只有一块食物,所有的鸟都不知道食物在那里,但是他们知道当前的位置离食物还有多远,那么找到食物的最优策略是什么呢?最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO从这种模型中得到启示并用于解决优化问题。PSO中,每个优化问题的解都是搜索空间中的一只鸟,我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value),每个粒子还有一个速度决定他们飞翔的方向和距离,然后粒子们就追随当前的最优粒子在解空间中搜索。
3.3.2 粒子群算法流程
PSO 初始化为一群随机粒子(随机解),然后通过迭代找到最优解。在每一次迭代中,粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解,这个解叫做个体极值 。另一个极值是整个种群目前找到的最优解,这个极值是全局极值 。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居,那么在所有邻居中的极值就是局部极值。
假设将第 个粒子表示为 ,它经历过的最好位置(有最好的适应值)记为 ,也称为 .在群体中所有粒子经历过的最好位置的索引号用符号 表示,即 也称为 .粒子 的速度用 表示。对每一代,其第 文根据如下方程变化:
其中, 为惯性权重,通过设置适当的值,以协调算法的“勘探”和“开采”能力,较大的 值可以增强“勘探”能力,但不利于“开采”,反之亦然。可以在优化开始的时候,设置较大的 值,随着迭代次数的增加,逐渐减小 的值,从而兼顾算法“勘探”和“开采”的能力。 和 学习因子,也称为加速常数,为了保证算法收敛,必须使 。 和 为两个在[0,1]范围内的随机函数。基本粒子群优化算法的流程图如图3.3所示:
通过前面的分析,总结PSO一般步骤:
①设置参数并随机初始化微粒位置和速度信息,尽可能靠近优化问题的搜索空间;
②根据式(3.1)及(3.2)更新每个微粒的速度和位置;
③由评价函数计算每一粒子的评价函数值;
④根据评价函数值更新 和 ;
⑤满足结束条件则停止(结束条件通常由迭代次数控制),否则转步骤②。
图3.3 粒子群优化算法流程图
3.3.3 PSO与其他算法的比较
对模糊神经网络的研究,大都是基于算法的创新、改进和完善,少有综述性的文献对它进行概述,使初接触这一领域的人往往无所适从,很难在短时间内理解模糊神经网络的概念,也很难实际应用它。它的优势在于可以处理一些传统方法不能处理的例子,例如不可导的节点传递函数或者没有梯度信息存在。但是缺点在于:在某些问题上性能并不是特别好;网络权重的编码而且遗传算子的选择有时比较麻烦。最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文,研究表明PSO 是一种很有潜力的神经网络算法,PSO速度比较快而且可以得到比较好的结果。 MATLAB基于粒子群的列车运行过程优化(8):http://www.youerw.com/tongxin/lunwen_9618.html