Potts－Glass模型算法的软件实现与应用

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.1<6 根据多次试验，δ=0.01较为合适· (②)饱和度大于一倍数时，结束条件为：月=六公≥09.即当1>09时表明阿络 已接近合理解，此时的温度也应比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

北 京 科 技 大 学 学 报 刃 年 见 图 图 按照 呷云如 模型 和 又妇 一 岛 模型 计算的闭合路 径 瑰 犯 声 垃留 加皿 哪云刘 洲划 晓洲如 回 勿 妞朽 气 绍 圳把 吻喇如 结论 一 算法是 对 模 型 与算法 的重大 改进 ， 网络算法 的应 用 成 为可 能 州 算法 的具体 应 用 实验结果 并 经查 询检 索 因而 使进一 步扩 大 表 明是 目前 最 好 的结果 参 考 文 献 芜 ， 界 长 ” 帐 ， 田七淦 尸 联， 司 俗石乎 反】 浏 巧 ’ 们 ， 明〕 ， 杨 行 峻 ， 郑君 里 人工 神经 网络 北 京 高等教 育 出版社 ， 卯 一 靳蕃等 神经 网络 与神经计算 机 原理 应 用 成都 西 南交通大学 出版社 ， 卯 一 ， 址祖川 司 认。 ℃心 一 己 ， 塑灭 晓旧 恤 司 乏 朋叹 酮 此 】】 巴 切甩 肋 ， 刃叉 一