再上一篇:4. 2  模拟退火
上一篇:4. 3  随机机
主页
下一篇: 第 5 章  均 场 退 火
再下一篇:5. 2  鞍点展开
文章列表

4. 4  习题

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

4.1  用模拟退火算法求解一个TSP 的最小旅程距离。TSP 的距离矩阵如下:

0 1 2 3 4 5

1 0 6 1.5 2.5 0.5

D= 2 6 0 0.5 0.2 1.2

3 1.5 0.5 0 0.4 4.4

4 2.5 0.2 0.4 0 5.1

5 0.5 1.2 4.4 5.1 0

采用二交换机制,以(4.24)式定义代价函数,定义从旅程Ξi到Ξj 的转移的接受率为

[f(Ξ)- f(Ξ)]+

- j i

e T

转移机制通过比较接受概率与一个来自均匀分布的随机变量的数值而实现。假定TS=10,起始旅程为Ξ1= (2,1,4,3,5,6)。二交换机制中用到的城市X 和Y以及为最初5个可能转移而生成的随机数由下表给出。填入表中空项,亦即找出新旅程、新旅程的代价和每个旅程的接受率,并决定是否接受转移。

建议旅程 随机数 代价 接受 接受

X Y ( ) 概率 转移?

f Ξi

Ξ1= (2,1,4,3,5,6) — — — — —Ξ2 1 5 0.2

Ξ3 1 6 0.7

Ξ4 2 3 0.5

Ξ5 6 5 0.6

Ξ6 3 4 0.4

4.2  考虑一个组合优化问题,它的解答空间大小为©¦©¦ 6,等价函数f (i)= i,其中i= 1,2,…,6。应用模拟退火算法,并假定从一个解答生成另一个解答的概率在整个解答空间上均匀分布。进一步假定从一个解答到另一个解答的转换遵守麦绰泼里斯准则。找出模拟退火算法在T= 5时的马尔科夫链转移矩阵。

4.3  分别应用模拟退火、波尔兹曼机、高斯机和柯西机求解第3章中给出的霍普费尔德10城市TSP。

4.4  推导(4.50)式中的ui和σu。

4. 5  选择一个适当的c使得(4.50)式尽可能地接近(4.32)式。(4.32)式中ui=∑wijsj + Ii,而(4.50) 式中ui= ∑wijsj + Ii+ η。提示: 尝试c= 2/π。

j≠i j≠i

#第40页-

4.6  找出(4.52)式定义ui的概率密度函数。

4.7  证明(4.54)式。

#第41页-