再上一篇:3. 2  连续霍氏网
上一篇:3. 3  按内容联想的存储器
主页
下一篇:3. 5  习题
再下一篇: 第 4 章  模拟退火和随机机
文章列表

3. 4  组合最优化

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

霍氏网稳定状态的确定是运用迭代式的更新方式使霍普费尔德能量函数最小化而得

#第20页-

到的。只要一个最优化问题的约束条件和代价可被转化为霍氏网中适当的霍普费尔德能

量函数,从而将这一问题映射到霍氏网的框架之中,霍氏网可以很自然地用于解决组合优

化问题。下面我们通过为几个著名的问题构造霍普费尔德能量函数来展示霍氏网解决优

化问题的能力。

3.4.1  旅行商问题

旅行商问题(TSP)可以如下表述: 给定一组N 个城市和它们两两之间的直达距离,

找出一个闭合的旅程,使每个城市刚好经过一次且总的旅行距离最短。N 城市TSP 的解

答由访问这N 个城市的一个次序表给出。要把这个问题映射到霍氏网的框架中去,只需

用一个旅程表作为网络的终止状态。在霍普费尔德与坦客(Tank)[86]所采用的表示方法

中,一个旅程的城市次序由一组神经元的终止状态代表。例如,对一个N 城市问题,网络

需要 2 个神经元,其中每个神经元代表一个城市在旅程表中的位置。因为有 个城市,

N N

每个城市又有N 个可能的位置,所以要有N× N 个神经元。一个途经6个城市(A,B,C,

D,E,F)的TSP 路径可被表示如下:

1 2 3 4 5 6 0

A 0 1 0 0 0 0 0

B 0 0 0 1 0 0 0

C 0 0 0 0 1 0 0

D 1 0 0 0 0 0 0

E 0 0 1 0 0 0 0

F 0 0 0 0 0 1 0

在这个例子中,每一个城市都有6种可能的位置(从第一个被访问到最后一个被访问),因

此要用到36个神经元。在上面给出的网络状态(路径)中,D市是第一个被访问的,A市第

二,…,而F 市最后。这一路径总的旅程距离为dDA+ dAE+ dEB+ dBC+ dCF+ dFD,其中dXY

表示从X市到Y市的直达距离。总之,TSP 可被方便地用一个正方矩阵表示,矩阵中每个

元素代表一个城市和它在旅程表上的位置。

霍普费尔德和坦客为TSP 设计了如下能量函数以表示网络的状态:

E = A sXisXj + B sXisXj

2∑∑∑ 2∑∑∑

X i j≠i i X Y≠X

C 2

+ ∑∑sXi- N (3.22)

2 X i

+ D dXYsXi(sY,(i+ 1) + sY,(i- 1))

2∑∑∑

X Y≠X i

其中 , , 和 都是正常数①(或将约束的优化问题转化为无约束的优化问题的拉格朗

A B C D

日参数)。下角标的取值范围由N 限定,其中X 或Y是一个城市的名称,而i则是该城市

① 注意不要将这些常数混同于城市名。

#第21页-

在一个旅程表中的位置。参数N 通常选用比城市数N 稍大一些的值。(3.22)式的前三项对应于TSP 的约束条件,而最后一项则对应于TSP 的代价函数。假定网络到达了一个稳定状态,且在这一状态下所有神经元的取值均为“1”或“0”。当且仅当矩阵中每一行最多只有一个神经元处于激活状态(输出为1)下,第一项才为零。换句话说,这一项只在每个城市被访问的次数不能多于一次的约束条件得到满足时才为零。第二项当且仅当每一列最多只有一个神经元处于激活状态时为零。也就是说,这一项只在旅程表中每个位置上不能有多于一个城市的约束条件得到满足时才为零。即使前两项都为零,也未必能得到合乎要求的解答,因为有可能所有神经元都处于抑制状态(输出0)。为此,第三项被引入,并促使稳定状态至少给出符合TSP 要求的完整旅程。这三项与最后一项合在一起,倾向于旅行距离短的旅程。一个满足约束条件的网络状态的总能量直接与旅行距离成正比。这使得具有最小能量的状态与最短路径相对应。

定义

wXi,Yj = - AδXY(1- δij) - Bδij(1- δXY) - C- DdXY(δj,i+ 1+ δj,i- 1) (3.23)TSP 的霍普费尔德能量函数,(3.22)式可被表述如下:

1 C 2

E = - ∑∑∑∑wXi,YjsXisYj - C∑∑NsXi+ N (3.24)

2 X Y i j X i 2

注意上式具有与(3.8)式给出的原始霍普费尔德能量函数相似的形式,但却又有下列不同之处:

(1) 因为网络是二维的,每个变量都有两个下标,而且求和符号也相应增加一倍。

C 2

(2) 增加了一项 N 。因为这是个常数项,它对优化过程没有影响。可以证明(3.24)

2

式事实上也是一个李雅普诺夫函数。

(3) 若忽略上述常数项,则外来输入(激活)为IXi= CN。

TSP 在二值Sigmoid非线性和零阈值条件下的连续霍氏网实现步骤可归纳如下:

(1) 初始化网络中的神经元,如sXi= 0.5+ v,其中v是一个很小的随机数。

(2) 在每次扫描① 时重复下列步骤:

① 随机抽取一个在此次扫描中尚未更新的神经元。

② 计算

+ - d

uXi= uXi+ Δt - - E

dsXi (3.25)

= u-i+ Δt wXi,YjSYj- + cN

∑∑

Y j

其中Δt 一般是一个很小的值。

③sXi=+ sgm0,β(uXi)。+

(3) 若到达稳定状态,停止; 否则转回第(2)步,进入下一次扫描。

[86] -

① 霍普费尔德和坦客 采用了稍许不同但却更加复杂的初始化程序。一个附加项- Δtu 被引入(3.25)式,但

Xi

在Δt很小时可忽略。

#第22页-

3.4.2  二分图问题

给定一个有一组N 个(偶数)节点和一组两两节点之间连线的一般图,二分图问题的目的是要将节点分为相等的两组,且令跨越这两组之间的连线最少。这一问题的解答可被应用于VLSI(超大规模集成电路)的布线设计。例如,图3.5给出了一个图的两种不同的二分方式,一个有两条跨越连线(此为最小值),另一个则有七条。

图3.5  二分图示例

图的连接方式可由如下连接性矩阵表示:

0 1 1 0 0 0 0 0 0 0

1 0 0 1 0 0 0 0 0 0

1 0 0 1 1 0 0 0 0 0

0 1 1 0 1 0 0 0 0 0

C= 0 0 1 1 0 1 0 0 0 1 (3.26)

0 0 0 0 1 0 1 0 0 1

0 0 0 0 0 1 0 1 0 1

0 0 0 0 0 0 1 0 1 1

0 0 0 0 0 0 0 1 0 1

0 0 0 0 1 1 1 1 1 0

其中[ ]ij= ij= 1  若第i个节点与第j 个节点相连

C c 0  否则

注意C是一个对称矩阵。记两个分区为CA 和CB,且定义一个在节点i处的神经元为

1 若i∈CA

si= - 1 若i∈CB (3.27)二分图问题由此可被转化为下列最小化问题:

在∑si= 0前提下,最小化- ∑∑cijsisj (3.28)

i i j≠i

其中第一项是代价项,且为所有不同节点对的代价之和。最小化代价项相当于试图把每一个节点对的两个节点都放在同一个分区里从而避免出现跨越分区的连线,而约束条件则迫使分区具有相同的大小。

#第23页-

为将这一问题映射到霍氏网的框架中去,我们需要定义一个适当的霍普费尔德能量函数把最小代价和约束条件结合到一起。该函数可证明是李雅普诺夫函数,即

1 α 2

E= - ∑∑sisjcij + ∑si (3.29)

2 i j≠i 2 i

= Na - 1 sisjwij (3.30)

2 2∑∑

i j≠i

其中N 是节点数,α是一个常数(拉格朗日参数),且wij= cij- α。因此,每个神经元的净输入为

+ d -

ui = - - E = wijsj (3.31)

dsi ∑

j≠i

而更新规则为

s+ = sgn wijsj- (3.32)

∑j≠i

3.4.3  N 皇后问题

N 皇后问题即在一个N× N 的国际象棋棋盘上放置N 个国际象棋皇后并使它们互不构成威胁。换句话说,棋盘上不能有多于一个皇后位于一条水平、垂直、或对角(45°或- 45°)线上。图3.6是一个8 8棋盘上符合要求的8皇后布局。为将N 皇后问题的约束条件映射到霍氏网的框架中,可将棋盘上的每个位置用一个神经元来表示。当一个棋盘上的位置被放上一个皇后时,相应的神经元“兴奋”; 否则神经元处于“抑制”状态。因此,需要一个具有N× N 个神经元的霍氏网来解决这一问题。

记神经元为sij,其中下角标i和j 分别表示该神经元

在棋盘上所处的行和列。鉴于每一行、列或对角线上

都只能有一个皇后,这一问题的约束条件可以映射为

如下能量函数:

A 2 B 2

E = ∑ ∑sij - 1 + ∑ ∑sij - 1

2 i j 2 j i

+ A+ B sij(1- sij)

2 ∑∑

i j

+ C sij(si+ k,j+k + si+k,j- k)

2∑∑∑

i j k≠0

(3.33) 图3.6  8皇后问题的一个正确摆法其中,A,B和C是拉格朗日参数。式中第一项在每行

只有一个皇后时为零; 第二项在每列只有一个皇后时为零; 第三项使每个神经元收敛到“1”或“0”; 第四项在每个对角线只有一皇后时为零。可以证明(3.33)式是一个李雅普诺夫函数。因此网络的神经元按下式迭代更新:

+ - d

uij = uij + Δt - - E

dsij

- - -

= uij - Δt A ∑sij - 1 + B ∑sij - 1

#第24页-

+ A+ B(1- 2sij- ) + C (si+k,j+k- + s-+k,j- k) (3.34)

2 ∑

k≠0

sij = sgm0,β(uij)+ (3.35)其中Δt 通常是一个很小的常数。