D0I:10.13374/j.issn1001053x.1994.04.017 第16卷第4期 北京科技大学学报 Vol.16 No.4 19948 Joumal of University of Science and Technology Beijing Ag.1994 Potts--Glass模型算法的软件实现与应用 童隆恩 北京科技大学计算机系,北京100083 摘要Pots-Glas模型与算法改进了Hopfield模型与算法.本论文就Pot地-Gass模型与算法的 软件实现与应用进行了研究,并在微机BM386上用C++语言基于该算法求解了我国31个城市 TSP部,获得了目前最好的结果. 关键词人工智能/神经网络,能量函数,热力期望值 中图分类号TP18 Software Implementation and Application of Potts-Glass Model Algorithm Tong Longen Department of computer science,USTB,Beijing 100083.PRC ABSTRACT Potts-Glass model improves Hopfield model.In this article,Potts-Glass model's software implementation and its application are studied.Based on this algorithm,using IBM386,the 31-cities TSP of China has been solved with language C++. The best result by now is given. KEY WORDS artificial intelligence/neural network model,energy function,thermo- dynamic expectation value 著名的Hopfield模型求解TSP(旅行商最佳路径问题)引起了人们的兴趣u2】,经过研 究,人们发现该模型求解效率较低,得到的不是最优解。例如,国内有人应用该模型算法求 解我国31个直辖市、省会和自治区首府巡回闭合路径最短距离,在400个解中的最优解为 21777km,如果将全部城市按辐射形分成3部分后,求得最短距离为15904kmI).其原因是: (I)该模型对问题的描述方法不合理,Hopfield网络描述求解问题是采用置换矩阵(W×N), 也就是需用W×N个神经元构成Hopfield网络,每个神经元的状态有2种,因此问题空间为 2',它远远大于TSP问题本身的合法总路径数N!(包括重复,显然需要改进这种问题的 描述方法; (2)求解N×N个微分方程组在模拟计算时效率太低,因此应避免求解微分方程组, Peterson和Soderberg提出的Pots一Glass模型较好地解决了上述问题,我们在对该模型 1993-09-02收稿 第一作者男58岁:副教授
第 卷 第 期 年 月 北 京 科 技 大 学 学 报 呢 一 模型 算法 的软件实现 与应用 童 隆 ,恩 北京 科 技大 学 计算 机系 , 北 京 《 摘要 一 场朋 模型 与算法 改 进 了 模型 与算法 本论 文就 一 留 模 型 与 算 法 的 软件 实现 与应用 进行 了 研究 , 并在微机 上 用 十 语言基于 该算法 求解 了我 国 个城市 飞 部 , 获得 了 目前最好 的结果 关键词 人工智 能 神经 网络 , 能量 函 数 , 热力期望值 中图分类号 冲 州 加肌 肠 ” 夕 乙刀” 朗 , , , 叫 , 一 ‘ 闭 血, , 、 沈 十 , , 一 而 著名 的 模 型 求 解 旅 行 商 最 佳 路 径 问题 引起 了人们 的兴趣 ’ , ’ 】 , 经 过研 究 , 人们 发 现该模 型求解 效率 较低 , 得 到 的不是 最 优 解 例 如 , 国 内有 人 应用该模型算法求 解 我 国 个直辖市 、 省 会和 自治 区首 府 巡 回 闭合路 径 最 短 距 离 , 在 个 解 中 的 最优解 为 , 如果将全部城市按辐射形分成 部分后 , 求得最短距离为 巧 如 ’ 其原 因是 该模型对问题的描述方法不合理 网络描述求解间题是采用置换矩阵 叼 , 也就是 需 用 个神经元构成 网络 , 每 个 神 经元 的状 态有 种 , 因此 间题 空 间 为 吸 它 远 远 大 于 问 题 本 身 的 合 法 总 路 径 数 包括 重复 , 显然 需 要 改进这 种 问题 的 描述方法 求 解 个 微 分 方 程 组 在 模 拟 计 算 时效 率 太 低 , 因 此 应 避 免 求 解 微 分 方 程 组 巧旧 和 飞 提 出 的 一 别骆 模 型 较 好 地 解 决 了 上 述 问 题 我 们 在 对 该 模 型 卯 一 的 一 收稿 第 一作者 男 岁 副教授 DOI :10.13374/j .issn1001-053x.1994.04.017
Vol.16 No.4 童隆恩:Pots一Glass模型算法的软件实现与应用 383. 算法进行系统论证的基础上,用C+语言具体实现了该算法,并用于求解我国3!个城市的 TSP问题. 1Pot地-Glass模型与算法I 1.1 Potts-Glas模型的理论基础 它是基于旋转玻璃理论·该理论是用来描述物体中磁场变化规律的一种新理论,在此理 论中认为磁场中的基本元素是磁偶极子(dipole)或称旋转子(spin),在旋转子i所处位 置的总磁场满足下式: h=∑W,Sj 式中:W,一为磁偶极子相互间的作用力;S,一为j处的原子, 在实际情况下,磁偶极子之间的作用力W,正比于偶极子之间距离,的1/r.一般情况 下,W,值的大小和符号均为随机分布,因此称此物体是一块自旋玻璃(Spin-glass),它 的状态可以对应于神经网络中大量随机的模式· 12概念转换 Pots-Glass模型采用一种分级的神经元表示法取代Hopfield模型置换矩阵概念, 如果用一个神经元素表示S,(i=1,2,…,N),该神经元S,的输出可由一个N维矢量(单 位矢量S,=(0,0,1,…,0)来描述,其中S.=0或1,因此S自动满足下述约束条件: ∑S=1 这时的问题空间为N,死然仍大于N!,但已远小于2w(Hopfield模型求解问题空间), 即大大减小了冗余, 物理学家在描述N态磁场Pots-Glass模型时,采用了矢量形式的S变量,当这些磁场 中的W态旋转子分别取得一定值时,整个系统取得最小能量,所以应用Hopfield网络求解 TSP映射到物理模型上,当神经元Spin取得代表合法路径值时,能量函数取得极小值. 1.3Pot地-Glass模型能量函数 其能量函数为: 6=z4,.5+号2,+号223,- 式中第一项称为惩罚项,限制路径长度,第二项限制每个城市只访问一次,第三项限制 每次只访问一个城市,上式可进一步写成: E=24,5.5,号22s品+号25)+a-N 为了搜寻这样一个随机系统的最小能量状态,必需对Pots-Glass模型采用平均场估计 法求出S,的热力期望值·
童 隆恩 一 模 型算法 的软件实现 与应用 算 法进行 系 统论 证 的基 础 上 , 用 语言具体 实现 了该算法 , 并用 于 求解 我 国 个 城 市 的 飞 问题 讹 一 模型与算法 月 饱州 肠岛 模型 的理论基础 它是基于 旋转玻璃 理 论 该理 论是 用 来 描述 物 体 中磁 场变 化规律 的一种 新 理 论 在 此 理 论 中认 为磁 场 中的基 本 元 素 是 磁 偶 极 子 或 称 旋 转 子 , 在 旋 转 子 所 处 位 置 的总磁 场满足 下 式 一 艺 月了 式 中 城 、 一 为磁偶 极 子 相 互 间的作 用 力 凡一 为 处的原 子 在 实 际情 况 下 , 磁偶 极 子 之 间 的作 用 力 , 正 比于 偶极 子 之 间距 离 的 ’一般 情 况 下 , 代 ,值 的大小 和符号均 为 随 机 分 布 , 因 此 称 此 物 体 是 一 块 自旋 玻 璃 一 , 它 的状态可 以 对应于 神 经 网络 中大量 随机 的模 式 概念转换 一 模 型 采用 一 种 分级 的神经 元 表示 法取 代 模 型置 换矩 阵概念 如果 用一 个神经元 素表示 ‘ 二 , , … , 位矢 量 一 , , , … , 来 描 述 , 其 中 凡 , 该神经元 民的输 出可 由一 个 维矢 量 单 或 , 因此 昆 自动满 足 下 述 约束条 件 艺 ,二 这 时 的 问题 空 间 为 “ , 死 然 仍 大 于 , 但 已 远 小 于 “ ’ 模 型 求 解 问题 空 间 , 即大大减 小 了冗余 物理 学 家在 描述 态磁 场 一 模 型 时 , 采用 了矢 量 形 式 的 变 量 当这 些 磁 场 中的 态旋转子分别 取 得 一定 值 时 , 整 个 系 统 取 得 最 小 能量 , 所 以 应 用 网 络 求解 ” 映射到物理模 型上 , 当神经 元 取 得 代表合法路 径 值 时 , 能量 函数取 得 极 小 值 艺 一 · ﹃ 一 乙 一 肠 模型 能 函数 其 能量 函数为 一 艺艺 ‘, ‘ 。 , “ 矛 。 ,一 , 万 今命 式 中第 一项称 为惩 罚项 , 限 制路 径 长度 , 第 二 项 限制每 个城 市 只 访 问一 次 , 第 三 项 限 制 每次只访 问一 个城 市 上 式 可 进 一步 写成 二 艺艺试 , 。 。 。 ‘ · “ ,一 ,一 万 今令 誉冬军 ‘ ’ 李 , 一 。 、 为 了搜 寻这 样 一 个 随机 系 统 的最 小 能量 状态 , 必 需 对 一 模 型 采 用 平 均 场 估 计 法求 出 、 的热力 期 望 值
·384 北京科技大学学报 1994年No.4 在统计物理学中下式很有用: Z=eBF=∑e-BEIs1 【S) 式中F称为Helmholtz自由能量,该式称为正规分割函数,用来计算各种物理量的平均值. 为了求出S,的热力期望值,可以将上式改写并引入delta函数及辅助变量4,V: (i=1~,且利用delta函数性质f(,)=f(ydxd(x-x),则上式可写成下式: Z-0,)e-66s76S-) =周Ja,)尝)6we-w 由于1c=Π0父e、引进一局部分割函数:Zu)=e=e,则有: zjma∫尝)ewre =de)∫n驶)ew-ua 令: g(4,wwy…Dw)=-E(e…vw)/T-∑4,+∑hZu) 为求函数极值,求如下偏导: 是-宁恶40 00, 胫-+和0 9=-,+Z)0u, o 于是有如下结果: Ses Fw(u,)是signoid函数f(x)= 乞1+tan的x)户。的一般形式 ex F(u)满足∑F联u)=1. va表示角标为i的Spin指向x的概率,v,是S,的热力期望值,即: 号∑S,e-Es) v,=>z
北 京 科 技 大 学 学 报 蒸岭 年 在 统计物理 学 中下式很 有 用 一 “ 艺 一 ’ “ ‘“ , 式 中 称 为 止 自由能量 , 该式 称 为正规分 割 函 数 , 用来计算各种 物 理 量 的 平 均值 为 了 求 出 的 热 力 期 望 值 , 可 以 将 上 式 改 写 并 引 人 函 数 及 辅 助 变 量 伙 , ‘一 ,一 , “ “ 用 。 函 数” 质 , 一 丁 , · ‘ 一 , 贝”上式 可 写成 下 式 一 艺 。 。 ‘ 。 一 一 ,‘ · 。 ‘ 一 , 百 ‘ , 一 。 粤 。 · · ‘ 一 ‘ 一 ‘ ‘ 一 ‘ ‘ 乙兀 ‘ 由于 菩早 “ · ’ 艺 一 “ ‘ , 引进一 局 部分 割 函 数 艺 · “ 艺 一 ’ , 则 有 白 · 一 丁 。 一 丁 。 会 一 ” , 一 不 “ ” 厂一 、 厂一 认 、 一 ‘产 ” ‘ ’ ’产丽 ’ “ 一 乙 ’ “ ’ “ “ ’ “ 一 令 “ “ ” 今 ’ “ ‘ “ ” 令 ,… 、 ,… 、 一 石 ,… 、 一 艺 “ ‘ 。 艺 为求 函数极值 , 求如 下偏 导 口 日 二一 一 二二 ,犷 一 一 “ 了 爵一, 命 箫一, 命 靴 “ 一 ” 于 是有如下结果 日 一 下 百百 ” ‘ 一 户 “ 恤 艺 一 “ 艺 · ’ 、 , 是 , 函 数 一 冬 二 一斗下 的一 般形 式 乙 一 叫卜 一 了菩 · “ “ 、 ’ “ 、 “ ,一 、 万万“ 一 “ 落飞 丁 心 满足 艺嵘 一 ‘。 表示 角标 为 的 指 向 的概 率 , ‘ 是 ‘ 的热力期望 值 , 即 。 ,二 , 奋石 “ 一 一
Vol.16 No.4 童隆恩:Pots-Glas模型算法的软件实现与应用 385. 因此得到最后结果: via=FN(u) .=号-g63] (A) 利用上式在一固定T值下求得稳态时的各参数,T值不断减小, 2Pots-Glass模型算法的软件实现 2.1(A)式的迭代计算,在迭代计算前,要预先设置两个初始值 )对spm变量S.设置初始值:S,=1+01).(武中为噪声), (2)设置初始温度T·在退火机制中,开始设定一较高的初始温度值,然后逐渐下 降,一直到达局部最小点,根据Peterson和Soderberg的意见I),Tc按下式设置: Tc N max (B-A.B+d+1.3No, 式中A,B为(A)式中的系数,d为各城市距离的算术平均值,o:为其均方差. 2.2迭代计算的结束条件,其结束条件在下列两种情况下选择 (1)当Spm变量的变化量小于常数5时,结束条件为:IV.(+1)-V.109时表明阿络 已接近合理解,此时的温度也应比T。低得多, 2.3软件实现的程序流程图 设置Spin变量初始值S 软件实现的程序流程图如图1所示, 设置退火温度初始值Tc 3应用实验 进行选代计算 在32次实验中有2次结果为15501km,每次求解 否 满足结束条件否? 时间近15mim.其31个城市最佳闭合路径是: 是 北京→哈尔滨→长春·沈阳·天津·济南· 结束计算,输出结果 石家庄·太原·西安·郑州·武汉·长沙·南昌 →合肥→南京→上海→杭州→台北→福州→广州 图1Pos一Gas算法流程 →海口→南宁→贵阳→昆明→成都→拉萨→乌鲁 Fig.1 Algorithm flow chart of Potts 木齐→西宁→兰州→银川→呼和浩特→北京.(参 -Glass model
童 隆恩 匕 一 岛 模 型 算法 的软件实现 与 应用 因此得到 最后 结果 、夕 , ‘ 寿 。 · 一 专卜军 ·, ·了 一 ,· ,一 ” 不 ,· 利 用上 式在 一 固定 值下 求得稳态 时 的各参数 , 值不 断减小 一 模型 算法 的软件实现 式的迭 代计算 , 在迭代计算前 , 要预先设置两个初始值 对 , 变量 ‘ 设置 初 始值 ‘ 。 一 令 , 式 中 为噪声 丫 设 置 初 始 温 度 几 在 退 火 机 制 中 , 开 始 设 定 一 较 高 的 初 始 温 度 值 , 然 后 逐 渐 下 降 , 一直到 达局部 最小 点 根 据 和 电 的意见 【’ , 按 下 式设置 式 中 , 为 式 中的系数 , 尧 责 · 一 , 了 ‘ · , 为各城市距 离 的算术平均值 , 。 为其均方差 迭 代计算的结束条件 , 其结束条件在下 列两种情况下选择 当 变量 的变 化量小于 常数 。 时 , 结 束条 件 为 令艺 十 一 汉 工丫 区 根据多 次试验 , 占 较 为合适 饱和 度 粉大 于 一 常数 时 , 结束 条 件 为 低 得 多 。 一 责勒加 即 当叮 时表 明 网络 已 接近合理解 , 此 时 的温 度 也 应 比 软件实现 的程序流 程 图 软件 实现 的程 序流程 图如 图 所示 设置 变量 初 始值 气 设置退 火温度初 始值 」 应用 实验 进行迭 代计算 在 次 实验 中有 次结果 为 巧 , 每 次求解 时 间近 其 个城 市 最佳 闭合 路 径 是 北 京 哈尔滨 长春 沈 阳 天 津 济南 石家庄 太原 西 安 郑州 武 汉 长 沙一 南 昌 合肥 南京 上 海 杭 州 台北 福 州 广州 海 口 南宁 贵 阳 昆 明 成 都 拉 萨 乌鲁 木 齐 西 宁 兰 州 银 川 呼和 浩 特 北京 参 互‘ 一蔽结束条件否 结 束计算 , 输 出结 果 图 瑰 成妇 一 岛 算法流程 琢目加 加 成 哎 一 困 侧川目
·386 北京科技大学学报 1994年No.4 见图2) 图2按照Hopficld模型(a)和Pos一Gas模型(b)计算的闭合路径 Fig.2 The path of 31 cities of China by Hopfield model algorithm (a) and by Potts-Glass model algorithm (b) 4结论 (l)Pots-Glass算法是对Hopfield模型与算法的重大改进,因而使进一步扩大Hopfield 网络算法的应用成为可能 (2)Pot地Glass算法的具体应用实验结果(并经查询检索)表明是目前最好的结果· 参考文献 1 Sreeram V B.Aiyer Mahesan Nahesan.Frank Fallside.A Theoritical Investigation into the Performance of the Hopfield Model.IEEE Trans Neural Network,1990,1(2) 2杨行峻,郑君里.人工神经网络.北京:高等教育出版社、1992.98~110 3新蕃等.神经网络与神经计算机原理应用.成都:西南交通大学出版社,1991.375~376 4 Moller B.Reinhardt J.Neural Networks An Introduction.New York:Springer-Verlag,1990 5 Peterson C.Parallel Distributed Approaches to Combinatorial Optimization Benchmark Studies on Travelling Salesman Problem.Neural Computation,1990(2):26~269
北 京 科 技 大 学 学 报 刃 年 见 图 图 按照 呷云如 模型 和 又妇 一 岛 模型 计算的闭合路 径 瑰 犯 声 垃留 加皿 哪云刘 洲划 晓洲如 回 勿 妞朽 气 绍 圳把 吻喇如 结论 一 算法是 对 模 型 与算法 的重大 改进 , 网络算法 的应 用 成 为可 能 州 算法 的具体 应 用 实验结果 并 经查 询检 索 因而 使进一 步扩 大 表 明是 目前 最 好 的结果 参 考 文 献 芜 , 界 长 ” 帐 , 田七淦 尸 联, 司 俗石乎 反】 浏 巧 ’ 们 , 明〕 , 杨 行 峻 , 郑君 里 人工 神经 网络 北 京 高等教 育 出版社 , 卯 一 靳蕃等 神经 网络 与神经计算 机 原理 应 用 成都 西 南交通大学 出版社 , 卯 一 , 址祖川 司 认。 ℃心 一 己 , 塑灭 晓旧 恤 司 乏 朋叹 酮 此 】】 巴 切甩 肋 , 刃叉 一