购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

3.1 禁忌搜索算法的原理和实现步骤

1.禁忌搜索算法的原理

禁忌搜索算法是解决组合优化问题的另一种优化方法。该算法是局部搜索算法的推广,其特点是采用禁忌技术,即用一个禁忌表记录下已经到达过的局部最优点,在下一次搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点。该算法可以克服爬山算法全局搜索能力不强的弱点。

在禁忌搜索算法中,首先按照随机方法产生一个初始解作为当前解,然后在当前解的邻域中搜索若干个解,取其中的最好解作为新的当前解。为了避免陷入局部最优解,这种优化方法允许一定的下山操作(使解的质量变差)。另外,为了避免对已搜索过的局部最优解的重复,禁忌搜索算法使用禁忌表记录已搜索的局部最优解的历史信息,这可在一定程度上使搜索过程避开局部极值点,从而开辟新的搜索区域。

2.禁忌搜索算法的实现步骤

用禁忌搜索算法求解组合优化问题时,其实现步骤如下(以目标函数求最小为例)。

第一步:选定一个初始解x now ;令禁忌表H=φ。

第二步:若满足终止准则,转第四步;否则,在x now 的邻域N(x now )中选出满足禁忌要求的候选集Can_N(x now ),转第三步。

第三步:在Can_N(x now )中选一个评价值最好的解x best ,令x now =x best ,更新禁忌表H,转第二步。

第四步:输出计算结果,停止。

禁忌搜索算法的第二步中,x now 的邻域N(x now )中满足禁忌要求的解包括两类,一类是那些没有被禁忌的解,另一类是可以被解除禁忌的解。 ysUFplM+m6L29E5PYmDrXyjsZyyDEllQkKHTe0LkwYZi/KWD7Zlj/uLFQXYOOyRT

点击中间区域
呼出菜单
上一章
目录
下一章
×