再上一篇:8. 2  集成 TDMA 通信系统的数据吞吐量最大化
上一篇: 第 9 章  点模式匹配
主页
下一篇:9. 3  进化程序设计
再下一篇: 第 10 章  多处理器调度
文章列表

9. 2  模拟退火框架

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

把 PPM 问题置于模拟退火框架内求解需要一个编码方案(一种表示点模式的方法)、一个合适的代价函数、为生成新的指派(构形或状态)的扰动规则、接受规则、冷却流程和收敛准则。一旦确定了框架,PPM 问题就可以用第4章所讨论的模拟退火方法加以求解。

9.2.1  编码方案

为了找到最佳指派,描述模式点之间指派的数据结构在以下方面构成最理想的表示:

・ 它是在问题定义域中的一个简单和直接的标记与指派,并且是模式点的一种最紧凑表示(最小存储/暂存空间)。

・ 在展开完备的解空间时,具有稳健性且不存在非法指派的可能性,在不完备模式集情况下,具有自然预防零标记的能力。

一个点模式用结点(即不同的点坐标的标记)组成的符号串来编码,从而形成搜索/解空间。一个码是两个点集合之间的一个指派。符号串中每一个单元的单元号相当于模型点集中的某个点,其值表示指派给这一点的被观测点。假设有m个模型点和n个被观测点。这样,一个码由m 个单元组成,其中的每一个单元可以取从0到n之间的任一个整数(0值表示没有一个被观测点能够与一个模型点匹配)。因此,符号串中的单元位置值(相应于模型点)与赋予此单元的数值(相应于被观察点),在每一个单元值唯一的约束下(除了“0”以外,两个单元不能有相同的数值),给出了从模型点到一个被观测点的匹配指派。例如考虑以下的12个单元的指派:

#第89页-

5 7 2 0 9 1 4 3 10 12 11 6 `

从左边算起的单元位置表示模型点标号;如第6个单元对应于第6个模型点。相应地,第

1个模型点被指派到第 5个被观测点,第2个到第7个,第3个到第2个,第4个未被指

派,第5个到第9个,等等。这样,每个码(指派)类似于液体的状态。

9.2.2  能量函数

代价函数或目标函数应能反映不适当指派所造成的误差,并对不完全的匹配给以惩

罚。一个好的指派应产生小的匹配误差,反之亦然。(9.11)式中所定义的匹配误差是代价

函数的一种合适选择。从统计力学的角度看,一个解的代价类似于第4章所讨论的物质的

一种状态的能量。

9.2.3  扰动规则

扰动规则可采用不同的机制。一个用于求解TSP 问题的成对改变的产生机制能够类

似地在此得到应用。这里对此机制略加变化。我们从9.2.1节所给的符号串的例子继续

讨论。首先在范围1到m(模型点的数量)和范围1到n(被观测点的数量)随机地产生两

个整数,例如“3”和“6”。第1个随机数表示符号串的这样一个单元位置,其值将被代表被

观测点的第2个随机数所取代。因此,第3个位置的单元值被置换为“6”。由于单元值只

能是唯一的,因此原来单元值是“6”的第12个位置上的值要被置换成第3个位置原来的

数值“2”。这样置换后新的符号串就成为

5 7 6 0 9 1 4 3 10 12 11 2 `

9.2.4  接受规则

这个规则用于决定接受还是丢弃下一个搜索结点。能得到较低代价的指派总是被接

受的,而为了避免陷入局部最小值,一个较高能量的新的指派有时也被接受。我们采用与

(4.28)式类似的接受规则。必须注意,当温度降低时,接受概率趋近于0,从而使得在低温

时,具有较高代价状态的指派的接受概率大大减小。这就是为什么一个其局部最小值的代

价与全局最小值的代价接近相等的搜索空间,有时可以在很低的温度下得到与最优值很

接近的解。

9.2.5  冷却流程

第4章中所讨论的冷却流程是模拟退火技术中重要的一环。可以采用不同的冷却流

程。我们可以预先启发式地确定一个最大搜索次数(即状态转移的总数),使温度在这最终

情况下的值为0。冷却流程中的温度是线性下降的,那么温度按下式

T = T0 1- (n nmax) (9.13)

降低,式中T0= 1选为起始温度,n表示第n次的搜索试验,nmax表示这种搜索试验的最大

#第90页-

搜索次数。

9.2.6  停止准则

当得到一个最优解(匹配误差^ ≈0)或者当冷却流程的温度 不能再降低(即 达

ε T T到0)时,退火过程自然终止。