启发式爬山法

时间：2014-06-23 06:43:05 阅读：464 评论：0 收藏：0 [点我收藏+]

爬山法是一种局部搜索算法，也属一种启发式方法。但它一般只能得到局部最优，并且这种解还依赖于起始点的选取。现在有各种版本的爬山法，下面给出的是一种简单迭代爬山法。

开始时，当前解的所有可能邻域都被考虑，并且将且有最好评估值eval_r(vn)的串vn与当前串vc作比较。如果eval_r(vc)比eval_r(vn)差，则新串vn就成为当前串；否则，则没有可能再进行局部改进：该算法已经达到局部最优或者全局最优（变量local=TRUE).

在这种情况下，算法的下一次迭代（t←t+1）随机选取一个新的当前串来执行.

procedure 迭代爬山法

begin

t ← 0

初始化 best

repeat

local ← FALSE

随机选取一个当前点vc

评估vc

repeat

在vc的邻域中选择所有新点

从这个新点的集合中找到使评估函数eval的值最优的点vn

if eval（vn）好于 eval（vc）

then vc ← vn

else local ← TRUE

until local

t ← t+1

if vc 好于 best

then best ← vc

until t = MAX

end

启发式爬山法,布布扣,bubuko.com

原文：http://www.cnblogs.com/csxf/p/3799573.html

踩

(0)

评论一句话评论（0）

分享档案

更多>