再上一篇:5. 3  稳定性
上一篇:5. 4  均场网的参数
主页
下一篇: 第 6 章  遗 传 算 法
再下一篇:6. 2  一个示例
文章列表

5. 5  二分图示例

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

二分图问题已在3.4.2节介绍过。用均场变量改写能量函数,(3.30)式变为

E(v) = Nα- 1 wijvivj (5.20)

2 2∑∑

i j≠i

其中N 是节点数,α是一个拉格朗日参数,而wij= cij- α。因此

d -

- E(v) = - wijvj (5.21)

dvi ∑

j≠i

且每个温度下的松弛过程变为

+ 1 dE(v) 1 -

vi = tanh - = tanh ∑wijvj (5.22)

T dvi T

j

解决二分图问题的均场退火算法① 可归纳如下:

(1) 根据问题设定参数:

・ 构造(5.20)式给出的能量函数;

・ 确定拉格朗日参数α;

・ 确定临界温度或起始温度Tc;

・ 在每个温度下,当

1 + -

∑©¦i - vi ©¦< ε1 (5.23)

N i

时转移(迭代)停止。也就是说,算法在两次迭代间神经元取值平均差小于 ε1 时达到热平衡。

・ 定义降温函数Tk+ L= βTk,其中β一般接近于1,且Tk是在第k次降温的温度。

・ 定义停止准则

所有神经元的取值无一例外地都在[- 1,- 1]或[δ1,1]的范围内;

1 ©¦i©¦≥ε2 ,即全部神经元中的100 2%几乎达到其稳态值{- 1,1}。

∑ ε

N i

(2) 初始化vi= rand(- ,δ),i= 1,2,…,N。其中rand(- ,δ)随机生成分布于- δ和δ之间且©¦©¦ 1的数值。

(3) 重复下列操作直至满足停止准则

・ 在每个温度下展开松弛过程直至达到平衡态:

+ 1 -

vi = tanh ∑wijvj

T j

・ 降温。

① -3

有些参数可以凭经验设定,例如,α= 1,β= 0.9,Tc= 1,ε1= 10 ,ε2= 0.9,δ= 0.2,δ1= 0.8。

#第47页-

5. 6  习题

5.1  在均场等式的实际应用中,可能只需要适当选择一个参数T。研究这一情况并为3.4.1节所介绍的TSP 选择一个适当的T。这会使均场退火退化为一个简单的霍氏网吗?

5.2  对于一个同时应用均场近似方法和鞍点扩展方法的二值网络,推导出它的均场等式。

5.3  求出< sisj> 。

5.4  用均场退火求解习题3.5中的二分图问题,并试验相关参数不同取值对解答的影响。

5.5  用均场退火重复习题3.6给出的20皇后问题。

5.6  用均场退火重复习题3.7描述的霍普费尔德实验。

#第48页-