混合蛙跳算法

混合蛙跳算法(Shufled Frog Leaping Algorithm,SFLA)是2000年由Eusuf和Lansey提出的一种基于群体智能的后启发式计算技术(亦有称混洗蛙跳算法)。混合蛙跳算法(SFLA)是一种受自然生物模仿启示而产生的基于群体的协同搜索方法。这种算法模拟青蛙群体寻找食物时,按族群分类进行思想传递的过程,将全局信息交换和局部深度搜索相结合,局部搜索使得思想在局部个体间传递,混合策略使得局部间的思想得到交换。

在混合蛙跳算法中,群体(解集)由一群具有相同结构的青蛙(解)组成。整个群体被分为多个族群,不同的族群被认为是具有不同思想的青蛙的集合。族群中青蛙按照一定策略执行解空问中的局部深度搜索。在已定义的局部搜索迭代次数结束之后,思想在混合过程中进行了交换。局部搜索和混合过程一直持续到定义的收敛条件结束为止。全局信息交换和局部深度搜索的平衡策略使得算法能够跳出局部极值点,向着全局最优的方向进行,这也成为混合蛙跳算法最主要的特点。

混合蛙跳算法基本流程

随机生成P只青蛙(问题的解)组成初始群体,第i只青蛙表示问题的解为Xi,其中nDim表示变量的个数即解空间的维数。在生成初始群体之后,将种群内青蛙个体按适应度降序排列。然后将整个青蛙群体分成m个族群,每个族群包含n只青蛙,满足关系P=m*n。其中,第1只青蛙分入第1族群,第2只青蛙分入第2族群,第m只青蛙分入第m族群,第m+1只青蛙分入第1族群,第m+2只青蛙分入第2族群,依次类推,直到全部青蛙划分完毕。

对于每一个族群,具有最好适应度的解表示为Xb,最差适应度的解表示为Xw,而所有族群中具有全局最好适应度的解表示为Xg。然后对每个族群进行局部深度搜索,即对族群中的X循环进行更新操作,更新策略为:
D=rand()*(Xb – Xw)
Vi=Xi + D
其中,D表示移动的距离,
rand()表示0和1之间的随机数,
同时D必须满足青蛙所允许改变位置的最大值。

在经过更新后,如果得到的解Vi优于原来的解Xi,则取代原来族群中的解。如果没有改进,则用Xg取代Xb重复执行更新策略。如果仍然没有改进,则随机产生一个新的解取代原来的Xi。

重复这种更新操作,直到设定的迭代次数。

当所有族群的局部深度搜索完成后,将所有族群的青蛙重新混合并排序和划分族群,然后再进行局部深度搜索,如此反复直到满足终止条件。

混合蛙跳算法的参数有:青蛙群体数P,族群数m,混合操作前族群内的更新代数和混合迭代次数。



2 Responses to “混合蛙跳算法”

  1. Eremeeff  on 九月 16th, 2009

    http://www.cnhup.com to GoogleReader!
    Thank you
    Eremeeff

  2. XXOO  on 九月 13th, 2009

    懂了,谢谢啊


发表评论

You must be logged in to post a comment.