散射搜索法介绍

散射搜索法(Scatter search, SS)作为一种新兴的演化算法已成功应用到很多领域,如分配、图论、商业软件以及线性排序等问题,目前已成为组合优化问题求解的一个有效方法。

散射搜索法在结构上一般包括5个部分:

(1)多样解生成

由于SS的基本机制是参考集组合生成新解,因此参考集中一般不允许存在两个相同的解,这样在初始化时必须保持种群的多样性。对实数编码的优化问题,常用受控的随机方法和频率记忆方法。

(2)新解改进

改进方法一般是用在散射搜索法的多样性初始解和组合方法产生的新解进行改进。如可以采取梯度下降法和Nelder-Mead 直接搜索法(复合形法)等多种方法。

(3)参考解集更新

参考集是散射搜索法的核心。若参考集缺乏多样性,即使通过组合和改进方法,也不会产生更好解,因为多样性为子集生成方法提供了基本结构。因此,现有SS应有中一般把参考集(RefSet)分为两部分:优质解参考集(RefSet1)和多样性解参考集(RefSet2)。设参考集Refset的数目为b=b1+b2,其中b1和 b2分别是RefSet1和RefSet2中参考解的数量。具体构造方法参阅相关文献。参考集的更新方法一般有动态和静态两种。

(4)子集生成

子集是SS组合的基础。一般的子集生成方法是包含2个解的子集生成法,即对参考集中b个解进行两两组合,构成解对(Pairs),则共有b(b-1)/2个子集。以此基础,则可以衍生出其它子集生成方法。目前实验表明,SS的搜索能力相当程度上取决于解对的组合。

(5)参考解的组合法

组合方法一般取决于所要解决问题的特点。不少优化问题可以采取线性组合法。

Scatter search的基本过程是,首先利用多样性解生成法生成多样性初始解,并用新解改进法对每一个解进行改进,加入初始种群P;根据解质量(目标函数值优劣)和多样性指标,从P选择若干个解构成初始参考集(RefSet)。然后利用子集生成法从RefSet中系统化生成一系列子集,对这些子集中的解利用组合法策略化地生成新的解,然后利用新解改进法对该新解进行改进,进而利用该解对参考集进行更新,反复执行上述过程,直到满足结束准则。



发表评论

You must be logged in to post a comment.