种子优化算法

种子优化算法(Seed Optimization Algorithm,SOA)是受自然界种子传播方式的启发提出的一种进化算法,通过模拟植物生存的自适应现象,逐代进化,寻找最优结果,解决复杂的优化计算问题。有点类似于分段式进化策略

算法思想

众所周知,植物种子的传播方式有很多种,其中包括散射传播,比如大部分的豆科植物就采用这种传播方式。当豆子成熟后,干燥而坚硬的外皮在太阳的照射下,发生爆裂,种子就会被弹射到植株周围,大部分种子会分布到植株的附近区域,也有个别会飞出很远或因为其他原因远离植株。然后种子就会在所降落的区域发育成长。有的会变得很茁壮,生出更多的种子,说明其所在地块很肥沃;有的可能很快被自然淘汰,说明其所在区域不适合植株生长。久而久之,会出现大量植株聚集在肥沃的地块,而贫瘠之地则不会有植株。受此启发,将待优化问题的问题域看作是土地,目标点所在的区域是最肥沃之地,根据目标函数值来确定该区域的肥沃程度,即越是背离最优目标值,其所代表的土地就越贫瘠,否则就越肥沃。一包种子被随机撒到土地上面,如果种子落到肥沃区域,其成长的概率和繁衍后代的机会就会很大;否则,就很可能被淘汰。经过多代繁衍,最终会有一颗植株生长在最富饶的土地上。经过算法抽象,将演化过程大大压缩,表现为在某几个强大植株附近大量涌现后代植株,如此循环往复,因此称该算法为种子优化算法(Seed Optimization Algorithm,SOA)。该算法与粒子群优化算法等智能算法相比,主要区别在个体的移动方式不一样,SOA中的个体对父种的响应程度更高,搜索效率也更高。

算法模型与算法实现

在种子优化算法中,种子个体用实值向量X(1:nDim)来表示,nDim的大小由问题本身决定。大量种子组成种子群体,它用sum表示,大小由初始化设定。种子被随机播撒到问题空间,其中适应度最大的几个种子称为父种,根据父种适应度的大小决定其后代的大小和分布情况。后代种子的分布以父种周边为主,父种的适应度值越大,其后代种子的数量就越多;否则,其后代种子的数量就越少,而且种子的分布更具有随机性。后代种子基本播撒方程如下所示:
Xi = Xi 若Xi为父种
= Xmb + rand()*Yi 若Xi不为父种

其中,Xmb是种子i的父种,Y(i)是父种Xmb的传播范围向量函数,根据问题的情况可进行定义和调整,表示如下:
Yi = α if i<(sum*a%)
= β if (sum*a%)<i<(sum*b%)
= γ otherwise

其中,α、β、γ都是代表位置变动的常数向量,可根据实际问题进行设置,a% ,b%是指父种周围种子的分布比例,同样可根据实际问题进行设置。

另外,部分种子的分布不遵循该方程,而是根据父种的分布,选择父种之间的中间位置进行定位,用于增强算法的全局寻优性能。

后代种子生成后,对所有种子的适应度再进行评价,选择适应度最优的种子作为父种候选。然后计算候选父种与同代其他父种的欧式距离是否满足设定的阀值,主要用来保证父种在空间上有较为合理的分布,避免算法过早收敛,提高算法的搜索效率和全局寻优性能。最后决定该种子是否作为本代的父种。

根据种子的进化方程,在生成的每个父种的传播范围内生成相应的后代种子群体。整个种子群体以此方式循环进化,直到得到理想的优化结果或一号父种(每代中的最优种子)不再变化为止。



2 Responses to “种子优化算法”

  1. AlexAxe  on 九月 29th, 2009

    Not sure that this is true:), but thanks for a post.

  2. Rufor  on 九月 19th, 2009

    Hi,
    Ugh, I liked! So clear and positively.


发表评论

You must be logged in to post a comment.