9512.net
甜梦文库
当前位置:首页 >> >>

进化策略与蚁群算法融合的求解旅行商问题


2 0 11年 1月 第 18 卷第 1 期
文章编号 : 1671 7848( 2011) 01 0083 04

控 制 工 程 Contro l Eng in eering o f China

Jan. 2 0 1 1 Vo.l 18 , No . 1

进化策略与蚁群算法融合的求解旅行商问题
丛 爽, 贾亚军
230026) ( 中国科学技术大学 自动化系 , 安徽 合肥



要 : 针对进化策略收敛速度 快但容 易陷入早 熟收敛 以及最 大最 小蚂 蚁系统 求解 能力

强但收敛速度较慢的特点 , 将进化策 略与最 大最小 蚂蚁系 统融 合 , 并利 用最 大最小 蚂蚁 系统 求出每一步迭代的最优解 , 再对迭代 出最优 解进行进 化策略 中的变 异操 作来 加快解 的收 敛速 度 。 将所提出的算法应用到中国旅行商问题 ( CTSP ) 的实际应用中 , 其结果显示出优 越性 。 关 键 词 : 进化策略 ; 蚁群算法 ; 最大最小蚁群系统 ; 中国旅行商问题 中图分类号 : TP 273 文献标识码 : A

Traveling Salesm an Prob le m Based on Integration of Evo lution Strategies and Ant ColonyA lgorithm
CONG Shuang, JIA Ya jun
( D epart m en t of A u tom ation, U n ivers ity of S cien ce and Technology of Ch ina, H efei 230026 , Ch ina)

Abstrac t : T o the proble m that the evo lution strateg ies converge fast , prone to pre m ature convergence , as we ll as the max m in ant sy s te m has good so lving ability , but converges slo w ly , the m ax m in ant syste m is comb ined w ith the evo lution strateg ies are comb ired. The m ax m in ant syste m is used to ca lculate the opti m al so lution o f each iteration, and a m utate operation is put on the iterative opti m al so lu tion to speed up the convergence rate o f so lutions . T he comb ination a lgo rithm is applied into the Chinese trave ling salesm an prob lem. T he super ior ity of the proposed algorithm is showed by the results . K ey word s : evo lution strateg ies; ant co lony algor ithm; m ax m in ant sy stem; Ch inese trave ling salesm an proble m

1 引


[ 1 3]

年来不断有学者提出了许多改进算法 , 如带精英策 略的蚂蚁系统 ( ASelite ), 蚁群系统 ( ACS), 最大 - 最小蚂 蚁系统 ( MMAS)等。 针对进化策略和最大最小蚂蚁系统各自的优缺 点 , 本文将进化策略与最大最小蚂蚁系统融合 , 利 用 MMAS 生成迭代最优解 , 对迭代最优解采用进化 策略中的变异操作 , 并将其应用到中国旅行商问题 ( CTSP )中。

[ 5]

20 世纪 60 年代初, 德国的 Rechenberg 等人提 出了进化策略 , 其优点是 : 具有大范围全局搜 索的能力; 并行算法 ; 搜索使用适应度函数作为评 价函数 , 过程简单。但它同时也有自身的缺点 : 对 于系统中上一代解的信息利用不够 , 当求解到一定 范围时往往做大量无用的冗余迭代 , 即容易陷入早 熟收敛 , 求最优解效率较低。 蚁群算法是一种基于种群的模拟进化启发式算 法。它是在对自然界中真实蚁群的集体行为研究的基 础上, 于 20世纪 90 年代由意大利学者 Dorigo 等人首 [ 4 5] 先提出。其优点是 : 蚁群算法作为对蚁群觅食行 为的抽象, 体现了群体行为的分布式特征; 它是一种 自组织算法; 它是一种正反馈的算法。蚁群算法在解 决一些小规模的 T SP 问题时表现尚可令人满意。但随 着问题规模的扩大, 由于初期信息素的匮乏, 很难在 可接受的循环次数内找到最优解, 收敛速度较慢。近

2 不同算法求解 TSP 问题的描述
1) 进化策略求解 TSP 问题 用进化策略求解 T SP问题的步骤可以概括如下 : 编码与初始群体的生成 采用巡回旅行路线 所经过的各个城市的顺序排列来表示每个个体的编 码串。例如对于一个 10 个城市的 TSP: 2- 5- 34- 1- 7- 6- 9- 8 , 表示从城市 2 出发依次经过城 市 5 , 3 , 4 , 1 , 7 , 6 , 9 , 8 , 然后返回城市 2 的一 条路径。这种编码方式满足 T SP 问题的约束条件 ,

收稿日期 : 2008 10 29; 收修定稿日期 : 2009 10 10 基金项目 : 国家自然科学基金资助项目 ( 61074050) 作者简介 : 丛 爽 ( 1961 ) , 女 , 山东文登人 , 教授 , 博士生导师 , 主要从事神经网络 , 模糊系统 , 智能控制 , 运动控制 , 量子控 制等 方面的教学与科研工作。

? 84?









第 18 卷

保证了每个城市经过且只经过一次 , 在任何一个城 市子集中不形成回路。 城市位置及距离矩阵和适应度函数的确定 城市的位置用城市的坐标 , 用一个 N ! 2 的矩阵 a 存储。城市之间的距离矩阵使用一个 N !N 矩阵 D 存储, D ( i, j )表示城市 i和城市 j 的距离: 2 2 D ( i, j) = sqrt( (X i - X j ) + ( Yi - Yj ) ) ( 1) 本文使用的适应度函数 fitn ess为 lenm in fitness( i, 1 ) = ( 1- ( ( len ( i , 1) lenm ax lenm in + 0 01) ) ) ( 2) 式中, lenm ax 和 lenm in分别表示最大和最小路径长度。 用距离总和 len( i, 1) 来衡量适应度。距离总和 越大, 适应度越小, 进而探讨求解结果是否最优。 ? 通过选择和变异产生子代个体 进化策略的 选择是一种确定性的选择, 即完全根据个体适应度 来选择。本文采用 ( + ) - ES, 即在 个父代和 个子代中选取适应度最高的 个个体作为下一代 的父代。对于 T SP 问题 一般取 1 , 根据问题的 规模适当选取。若 过小 , 子代个体多样性少, 容 易陷入局部最优解; 过大 , 算法收敛较慢。 #算法终止条件 判断算法是否需要终止的准 则一般有规定迭代次数, 规定最小偏差 , 观察适应 度变化三种方法。本文采用规定迭代次数的终止方 法。 2) 蚁群算法求解 TSP 问题的基本描述 蚁群算法求解 T SP问题的模型 蚂蚁能在没 有任何提示下找到从其巢穴到食物源的最短路径 , 根本原因是蚂蚁在寻找食物源时 , 能在其走过的路 上释放一种特殊的分泌物: 信息素 , 后来的蚂蚁选 择该路径的概率与当时这条路径上信息素的强度成 正比。当一定路径上通过的蚂蚁越来越多时, 其留 下的信息素轨迹也越来越多 , 后来蚂蚁选择该路径 的概率也越 高, 从而更增 加了该路径 的信息素 强 度 , 吸引更多的蚂蚁 , 形成一种正反馈。通过这种 正反馈机制 , 蚂蚁最终可以发现最短路径。 以求解 n 个城市的 T SP 问题为例 初始时刻 , 各条路 径 上 的 信息 素 量 相 等 , 设 初 始 信 息 素 为 , 2 , ?, m )在运 ij ( 0 ) = C (C 为常数 )。蚂蚁 k ( k = 1 动过程中根据各条 路径上的信息 素量决定转移 方 向。在 t 时刻 , 蚂蚁 k 在城市 i选择城市 j 的转移概 k 率 P ij ( t) 为
! ij m

为了满足蚂蚁必须经过所有 n 个不同城市这个 约束条件, 为每只蚂 蚁都设 计了一 个禁忌 表 ( tabu list) 。禁忌表记录了在 t时刻蚂蚁已经走过的城市 , 不允许该蚂蚁在本次循环中再经过这些城市。经过 n 个时刻, 完成一次循环, 各条路径上信息素量根据 下式调整: , t+ 1 ) ( 4) ij ( t+ 1 ) = ? ij ( t) + % ij ( t % ij ( t, t + 1 ) =
k ij

%

n

% ij ( t, t + 1 )
k

( 5)

k= 1

式中, % ( t, t+ 1 )表示第 k 只蚂蚁在时刻 ( t, t+ 1 ) 留在路径 ( i , j )上的信息素量; % ij ( t, t+ 1 )表示本次 循环路径 ( i , j )的信息素量增量; ( 1- ?)为信息素轨 迹衰减系数。 最大 最小蚂蚁系统 ( M ax M in An t System ) 通过实验发现标准蚁群算法在求解过程中极易发生 早熟收敛, 为此 , Stutzle 等人提出了最大 最小蚂 蚁 [ 6] 系统 (MMAS) , 与标准蚁群算法有 3 点不同 : a)信息素更新方式不同 每次循环后只对本次 循环最优解或到目前为止找出最优解的一只蚂蚁进 行信息素更新 , 而在标准蚁群算法中 , 对所有蚂蚁走 过路径都进行信息素更新, 其信息素更新方式为 best ij ( 6) ij ( t+ 1 ) = ? ij ( t ) + % best best be st 式中 , % ij = 1 /f ( s ), f ( s )为迭代最优解或者全 局最优解, 在 MMAS 中用迭代最优解。 b) 为避免搜索的停滞, 在每个解的元素 ( 在 TSP 中是每条边 ) 上的信息素轨迹量的值域范围被限制 在 [ m in, m ax ]区间内 , 其上下限更新方式为 1 ( 7) m ax = opt ( 1- ?) f ( s )
1

( t) ?ij ( t)
! is
k

#

P ij ( t) =

k

s& allow ed

%

( t ) ?is ( t)

#

, j&

a llow edk ( 3)

0 式中, !为信息素在蚂蚁路径选择时所起的作用 ; # 为启发信息在蚂蚁选择路径中的作用。

( 8) 1 ( n - 2) (P b es t ) n c) 为了使蚂蚁在初始阶段能够更多地搜索新 的解决方案, 将信息素轨迹初始化为 m ax ( 0) 。 运用最大最小蚂蚁算法求解 TSP 问题的算法流 程如下 : Step 1 指定出发城市 , 并将 m 只蚂蚁平均分 布在 n 个城市上 , 一般选取 m = n。 Step 2 各城市间的信息素初始化为 m ax, m ax 按式 ( 7) 确定, 其中 , f bes t为 任意一组蚂蚁按贪婪法 (即蚂蚁总是访问下个离自己最近的城 市 ) 生成 的 一个解。 Step 3 置迭代次数 itera tion = 1 : NC m ax 。 Step 4 对于第 i只蚂蚁 , 随机生成其访问 的 城市数 , 并将已访问城市的禁忌表清零 , 将指定出 发城市加入已访问城市的禁忌表。 Step 5 若蚂蚁没有访问完指定城市数 , 则蚂 蚁按照式 ( 3) 确定 的概率选择访问的下一个城市 , 并将该城市加入 已访问城市 表, 否则回 到出发 城
m in

=

2

m ax

( 1- (P bes t ) n )

第 1期 市。



爽等: 进化策略与蚁群算法融合的求解旅行商问题

? 85?

S tep 6 若所有蚂蚁都完成访问 , 本次迭代完 成 , 求取本次迭代的最优解, 按式 ( 7), 式 ( 8) 更新 。 m ax, m in, 否则返回 Step 4 S tep 7 iteration = iteration + 1 , 若迭代 次数已 满 , 结束本次实验, 否则按照式 ( 6) 更新城市间的 信息素 ij , 判 断信息素是否在范围 [ m in, m ax ] 内 , 若 ij ( t ) > m ax , 则可以设置 ij ( t) = m ax; 若 ij ( t ) < 。 m ax, 则设置 ij ( t ) = m i n。返回 Step 3 3) 进化策略与最大最小蚂蚁算法的融合 最 大 - 最小蚂蚁系统具有很强的发现较好解的能力 , 不容易陷入局部最优。由于蚁群中各个体的运动是 随机的 , 虽 然通过信息交 换能够向着 最优路径 进 化 , 但在进化的初级阶段, 各个路径上信息量相差 不明显 , 通过信息正反馈, 使得较好路径上的信息 量逐渐增大 , 需要经过较长一段时间, 才能使得较 好路径上的信息量明显高于其他路径上的信息量 , [ 7 8] 这就导致了该算法需要较长的收敛时间 。 为了克服计算时间较长的缺陷 , 受进化策略中 变异操作的启发 , 提出最大最小蚂蚁算法与进化策 略融合。具体做法为 , 每次循环中 , 利用最大最小 蚂蚁算法产生迭代最优路径后, 对迭代最优路径进 行变异操作。融合算法求解 TSP 问题的算法流程前 六步与最大最小蚂蚁系统完全一致, 改进点如下: S tep 7 对于迭代最优解所对应的路径进行变 异操作 , 产生 个新的路径, 若新路径中有路径长 度小于迭代 最优解, 则用 新路径取代 迭代最优 路 径 ; 否则保持迭代最优路径不变。 S tep 8 iteration = iteration + 1 , 若迭代 次数已 满 , 结束本次实验, 否则按照式 ( 6) 更新城市间的 信息素 ij , 判 断信息素是否在范围 [ m in, m ax ] 内 , 返回 Step 3 。

目前解决 TSP 问题的方法主要分为精确算法和 近似算法 2大类。常用的精确求解方法有分支定界 法 , 线性规划 , 动态规划和穷举法等。这些算法都 存在计算量大的缺点 , 难以应用到大规模问题中。 近似算法又分为巡回路径构造算法, 巡回路径优化 算法和智能算法。其中 , 智能算法的研究最为引人 注目, 包括模拟退火, 遗传算法, 差分演化, 蚁群 算法等。目前对于 CTSP 问题 , 模拟退火求得的解 为 15 567 km , 改 进 的 遗 传 算 法 求 得 的 解 为 [ 11 ] 15 404 km , 差 分 演 化 算 法 求 得 的 解 为 15 404 km 。模拟退火算法具有质量高 , 初值鲁 棒性强 , 通用易实现的优点 , 但收敛速度较慢 ; 遗 传算法最显著的优点是隐并行性和全局搜索, 但在 实际应用中易出现早熟收敛 , 另外对初始种群很敏 感 , 初始种群的选择常常直接影响解的质量和算法 效率; 差分演化算法收敛速度快 , 同事种群多样性 大幅度减少, 但存在早熟收敛, 易陷入局部最优等 问题。 2) 进化策略求解 CTSP 问题 的实验结果分 析 本文测试采用 M atlab7 0 为编程工具, 在 CPU 为 Inte l Core2 Duo 2 10 GH z , 内存为 1 96 GB, 操作系 统为 W indow s XP ( SP2) 的计算机上对 CTSP 求解。 根据前文中的进化策略求解 TSP 问题的步骤 , 首先初始化各个参数 , 父 代个数取 = 1, 子代 个 数取 = 30 , 适应度函数系数取 m = 2 , 初始化 路 径数取 n = 200 , 最大迭代次数取 C = 500 。使用函 数 randper m ( 31) 产生一个 1 ! 31 的矩阵 ( 31 为城市 个数 )为一个随机路径。利用 n !N 矩阵存储 n 个 随机群体产生初始群体。根据式 ( 1) 计算出每条随 机路径的长度 , 选取其中最短的一条路径作为初始 路径 , 然后经过逆转变异操作产生 个后代, 根据 式 ( 2) 计算出子代的适应度 , 并与父代个体比较 , 取适应度最高的一个作为下一迭代的父代个体 , 即 完成了一次迭代, 重复上述操作 , 直到达到最大迭 代次数。 在上述参数条件下进行了 10 次寻优计算 , 实 验结果 , 见表 1 。
表 1 进化策略实验结果 Tab le 1 Exp er i m en ta l resu lts of evolution strategies
收敛代数 实验次数 路径长度 65 54 80 85 71 15 899 4 2 4 6 8 10 15 415 16 001 15 983 16 235 15 949 68 5 收敛代数 72 69 59 58 72
[ 12 ] [ 10 ]

3 中国 31个省会城市 TSP 问题的求解及其 实验结果分析
1) 中国旅行商问题 ( CTSP ) 的描述 T SP 问题 的数学描 述为 : 对于 城市 V = { v1, v2, ?, vn } 的一个访 问顺序 为 T = { t1, t2, ?, tn }, 其中 , ti = V ( i = 1 , ?, n}, 而且 tn+ 1 = t1, 则问题为 求 m in
i= 1 T & &

%

n

d t i t i+ 1 , 其中, & 为这 n 个城 市不重复 排

实验次数 路径长度 1 3 5 7 9 15 865 16 543 15 774 15 404 15 825 平均值

列的所有可能的回路。 中国 31 个省会城市的 TSP 问题 , 即中国旅行 商问题 ( CTSP ) 是一个典型的对称 TSP 问题 , 它可 以简单表述为, 求一条从任意省会城市出发经过中 国 31 个省会城市最后又回到出发城市的最短回路。 这是一个中等规模的 T SP问题, 可能存在的路径有 32 ( 31- 1) ! /2= 1 326 ! 10 条。

? 86?









第 18 卷

最好解为 15 404 , 收敛代数为 85 代 , 这也是 目前公布的中国 31 个省会城市的最优解 , 最差解 为 16 543 , 平均值为 15 889 4 。在迭代 500 次情况 下 , 收敛代数都在 100 代以内, 说明该算法收敛速 度很快。但同时也看到 10 次实验中得到最优解的 次数只有 1 次, 成功率较低 , 且最好解与最差解相 差比较大, 表现出算法容易早熟收敛, 所得解的质 量不高。 3) 最大最小蚂蚁系统求 解 CT SP 问题实验 及 结果分析 基于上述所述的 MMAS 解决 TSP 问题 的具体步骤 , 首先 初始化 各个参 数, 取 蚂蚁数 m 等于城市数 n = 31 , != 1 , #= 3, ?= 0 3 , 信息素 - 4 轨迹量上限的初始值设为 m ax ( 0) = 6 6 ! 10 , 下 限初始值为 m in ( 0) = 2 5 ! 10 , P bes t = 0 05 , 最 大迭代次数为 2 000 。利用函数 randper m 将 31 只蚂 蚁随机分布在 31 个城市上 , 31 只蚂蚁根据概率选 择式 ( 6) 选择下一座城市, 并将已经访问的城市添 加到禁忌表中 , 当 31 只蚂蚁 都完成各 自选择后 , 计算出每条蚂蚁经过的路径长度 , 选择其中一条最 短路径 , 即迭代最优解。根据式 ( 6) 更新信息素轨 迹 , 根据式 ( 3) 更新概率选择公式。然后 Step 8 中所 述对更新后的信息素轨迹进行限界 , 清空禁忌表 , 本次迭代完成。重复上述操作, 直到达到最大迭代 次数。 为了同进化策略进行比较 , 同样进行了 10 次 优化计算, 实验结果 , 见表 2 。
-6

略中变异操作的启发, 将最大最小蚂蚁算法与进化 策略融合。首先利用最大最小蚂蚁系统产生迭代最 优解, 具体步骤和初始参数设置同 3)。然后对 迭 代最优路径进行 30 次逆转变异操作 , 将得到的 30 个子代路径与父代相比 , 取其中最短的一条作为新 的迭代最优路径。根据式 ( 6) 更新信息素轨迹 , 根 据式 ( 3) 更新概率选择公式。然后 Step 8 中所述对 更新后的信息素轨迹进行限界, 清空禁忌表, 本次 迭代完成。重 复上述 操作 , 直到达 到最大 迭代 次 数。 同样进行了 10 次优化计算, 结果 , 见表 3 。
表 3 融合算法实验结果 Table 3 Exp eri m ental results of comb ination algorithm
实验次数 路径长度 1 3 5 7 9 15 404 15 409 15 426 15 404 15 409 平均值 收敛代数 实验次数 路径长度 440 349 850 105 476 15 428 3 2 4 6 8 10 15 404 15 404 15 426 15 593 15 404 362 1 收敛代数 304 493 91 264 249

表 2 最大最小蚂蚁系 统实验结果 Tab le 2 E xper i m en ta l re su lts of m ax m in an t system
实验次数 路径长度 1 3 5 7 9 15 404 15 404 15 426 15 497 15 409 平均值 收敛代数 实验次数 路径长度 987 1 274 658 795 475 15 442 8 2 4 6 8 10 15 426 15 593 15 409 15 404 15 456 759 1 收敛代数 435 482 693 1007 785

从表 3中可以看出 , 改进算法在 10 次计算中 有 5 次得到最优解 15 404 , 成功率为 50 % , 且其 他解 也 都 在 15 409 ~ 15 593 之 间, 平 均 值 为 15 428 3与最优解很接近, 且每次都能得到较好的 解 ; 算法的收敛速度也很快 , 基本上在 500 代之前 都可以收敛到较好的解 , 这说明加入变异操作后 , 算法的搜索时间大大减少, 是一种效率较高的改进 算法。 融合算法求解 CTSP的最优路径图, 如图 1所示。

由表 2可以看出, 在迭代次数为 2 000的情况下, 10次运算中有 3次找到最优解 15 404 , 找到最优解概 率为 30 % , 且其余解大部分也在 15 409~ 15 593 之 间, 从平均值也可以看出, 最优解与平均值差异较 小, 且总能找到较好的解。但与进化策略相比, 算法 运行速度较慢, 得到最优解时收敛代数大多在 800代 后, 这说明算法需要较长的搜索时间, 对于大规模优 化问题, 这将是一个很大的障碍。 4) 融合算法求解 CTSP 问题实验及结果分 析 为了解 决最大最小蚂蚁系统计算时间较长的 缺 陷 , 同时利用其能够找到最优解的能力 , 受进化策

图 1 融合算法求解 CTSP 的最优路径图 Fig 1 The best rou te m ap of CT SP

CTSP 的最优路径如下: 北京 - 哈尔滨 - 长春 - 沈阳 - 天津 - 济南 - 合 肥 - 南京 - 上海 - 杭州 - 台北 - 福州 - 南昌 - 武汉 长沙 - 广州 - 海口 - 南宁 - 贵阳 - 昆明 - 成都 - 拉 萨 - 乌鲁木齐 - 西宁 - 兰州 - 银川 - 西安 - 郑州 - 石 家庄 - 太原 - 呼和浩特 - 北京。 (下转第 137页 )

第 1期

于莲芝等 : 微小气动机器人移动 FS M 建模与控制
f 循环结束 时 q( f = q = ( x0 , q1 , 0 )

? 137?

采用该机器人的电 气实验控制 系统 , 基于 有限状态机程序控制算法对机器人移动状态进行了 实验研究 , 验证了上述控 制算法的可 行性和有 效 性 , 基于有限状态机的控制程序可实现机器人运动 的高效率控制, 在对机器人进行前进或后退的方向 改变时 , 可根据机器人所处的运动状态按前进或后 退的状态转换顺序自动进行转换。

[ 11]

4 结



根据所设计的气动机器人的移动机理 , 分析了 机器人移动一个步距在一个运动周期内的运动状态 和状态之间的转换关系, 建立了机器人移动的有限 状态机模型并给出了单个行波的控制算法 , 实验研 究表明依此控制算法可对所设计的移动机器人进行 有效的控制。基于有限状态机模型控制算法适应于 多单元体组成的运动机构的控制, 模型简单, 控制 算法有效可行。 参考文献 ( R eferences):
[ 1] [ 2] h ttp : / /www 2 . ccw. com. cn /02 / 0207 / b / 0207b02_7 . asp 胡小平 , 陈 国良 , 黄 之初 , 等 . 微 操作 机器 人控 制 系统 研究 [ J] . 机 械设 计 , 2007, 24 ( 2) : 18 21 . ( H u X iaop ing, G eng Gu o liang, H uang Zh ichu , et al. S tudy of m icro operation robot control system [ J] . Journal of M ach in e D esign , 2007 , 24( 2) : 18 21 . ) Y evtusbenko N, Zhankova S , V etrovaM. M u lt i com ponent d ig ital ci

[ 3]

rcuit opt i m izat ion by solv ing FS M equ at ions [ C ] . Belek , A ntalya , Tu rkey : E urom icro Symposium on D igital System s D esign , 2003 . [ 4 ] Chen S P, W angM S , H uang Y, et a l . M an m ach ine in terface of develop ing intelligen t toys based on tree structu re[ C] . Belingham: I CM I T2005 , Contro l System and R obot ics , P roceed ings of SPI E, 2005 . [ 5 ] 王明顺 . 机器人程序设计中的状 态转换方 法 [ J] . 东北 大学学 报 , 2008 , 29 ( 2 ) : 166 169 . ( W ang M ingshun . S tate trans ition m ethod for robot p rogram des ign [ J] . Journal of N orth eastern un i versity , 2008, 29( 2 ) : 166 169. ) [ 6 ] 于莲芝 , 颜国正 , 王祥瑞 . 用于呼吸道直接监测的柔性微机器 人系统 [ J] . 机器人 , 2006, 28 ( 3 ) : 269 274. ( Y u L ianzh , i Y an G uozh eng, W ang X iangru.i A f lex ib le M icro robot system for d irect m on itoring in hum an trachea [ J ] . R otot , 2006 , 28 ( 3 ): 269 274 . ) [ 7 ] Y u L Z, Y an G Z, M a G Y, e t a l . A n active endoscopy rob ot ic sys te m for direct tracheal inspection[ J] . Jou rnal of Shanghai J iaotong U n ivers ity, 2007 , 12 ( 2) : 159 163 . [ 8 ] 蒋宗礼 , 姜守旭 . 形式语言 与自动机 理论 [ M ] . 北京 : 清华大 学出版社 , 2003. ( Jiang Zongl. i For m al language and autom ation theory[ M ] . Be ijing: T singhu aU n ivers ity Press , 2003 . ) [ 9 ] Chen I M, Y an G. G ait generation for inchw or m like robot locomo tion us ing fin ite state model[ C ] . ShangH a: i Proc of 1999 IEEE I nt Con f on R obotics & A utom ation , 1999 . [ 10 ] 张浩水 , 曹志强 , 周超 , 等 . 集成任务 级与运动 级协的多 机器人 仿真系统 [ J] . 系统仿真学报 , 2009 , 21 ( 6) : 1579 1582 . [ 11] 于莲芝 , 颜国正 , 昝鹏 , 等 . 气动机器人电 气控制系统设计 [ J] . 测控技术 , 2007, 26( 1) : 33 36 . ( Y u L ian zh , i Y an G uozh eng , Zan Peng, et a l. D es ign of the electro pneum atic Pressu re con trol system for pneum atic robot[ J] . M easu r m ent & Con trol techn ology, 2007 , 26( 1 ) : 33 36. ) [ 12 ] 刘晓华 , 罗 杰 . 基 于网 络模 型 的综 合多 速率 采样 预测 控制 器 [ J] . 控制工程 , 2009 , 16( 6) : 666 669 . ( L iu X iaohua, Luo Jie .A Com pre h ensive M u lti rate Pred ictive C on troller Based on N et w orked M odel[ J] . Contro l Eng ineering of Ch ina, 2009, 16 ( 6 ) : 666 669 .

( 上接第 86页 )

4 结



[ 7]

本文分析了进化策略和最大最小蚂蚁系统在解 决 TSP 问题上的各自特点, 并结合两者的优缺点提 出了一种融合算法。 针对中国旅行商的具体应用结果表明 , 融合后 的算法比进化策略和最大最小蚂蚁系统具有更强的 全局最优解搜索能力和较快的收敛速度 , 是一种效 率较高的改进算法。 参考文献 ( R eferences):
[ 1] [ 2] BeyerH G, S chw efel H P. Evo lut ion strategies- A com prehens ive in trodu ct ion [ J] . N atura l Compu ting, 2002 , 1( 1 ): 3 52. N u rnbergH T, Beyer H G. The dynam ic of evolut ion strategies in th e opt i m ization of traveling sa les m an prob lem [ J] . Proceed ings of th e 6th In ternational Con ference on Evolu tionary Programm ing, 1997 , ( 4 ) : 349 360 . 云庆夏 . 进 化算 法 [ M ]. 北 京 : 冶金 工 业出 版 社 , 2000 . ( Y un Q ingxia . Evolu tionary algorithm [ M ] . B eijing: M etallu rgical Indus try Press , 2000 . ) 王正志 , 薄 涛 . 进化 计算 [ M ] . 长 沙 : 国 防科 技大 学出 版社 , 2000 . ( W ang Zhengzh , i Bo Tao. E volu tionary com pu tat ion [ M ] . Changsha : N at ion al U n iversity of D efense T echnology Press , 2000 . ) 李士勇 . 蚁群算法及其应用 [ M ] . 哈尔滨 : 哈尔滨 工业大学出 版社, 2004. ( L i Sh iyong. A n t colony algorith m s w ith app lications [ M ]. H ar b in: H arb in Inst itu te of Technology Press , 2004. ) 段海 滨 . 蚁 群 算法 原 理 及其 应 用 [ M ] . 北京 : 科 学 出版 社 ,

2005 . ( D uan H aibin . A n t colony algorith m s theory and app lica tions [M ]. Beijing: S cien ce Press , 2005 . ) 丁建立 , 陈增强 , 袁著祉 . 遗传算法与蚂蚁算 法的融合 [ J] . 计 算机研究 与发展 , 2003 , 40 ( 9 ) : 1531 1536 . ( D ing Jian l, i Ch en Zengq iang, Y uan Zhuzh.i O n th e com b ination of gen et ic algorithm and an t a lgorithm [ J] . Journal of Com puter R esearch and D evelop m ent , 2003, 40( 9) : 1531 1536 . ) 吴庆洪 , 张纪会 , 徐心 和 . 具有 变异 特性的 蚁群算 法 [ J] . 计算 机研究与发展 1999 , 36( 10 ): 1240 1245 . ( W u Q inghong, Zhang Jihu , i X u X inhe. A n an t colony algorith m w ith m utat ion features [ J] . Jou rnal of Com puter R esearch and D evelopm ent , 1999 , 36 ( 10) : 1240 1245 . ) 赵云涛 , 王京 , 刘金 珠 . 一类 用于连 续域寻 优的蚁 群算法 [ J] .

[ 8]

[ 9]

控制工 程 , 2008 , 15 ( 3 ) : 242 244 . ( Zhao Y un tao , W ang Jing, Liu Jinzhu . An i m p roved an t colony algorithm for cont inuous doma ins [ J] . C ontrol Eng ineering of Ch in a , 2008 , 15( 3 ): 242 244 . ) [ 10 ] 李敏 , 吴浪 , 张 开碧 . 求 解旅行 商问题 的几种 算法的 比较 研究 [ J] . 重庆邮 电大 学学 报, 2008, 20 ( 5 ): 525 528. ( Li M in , Wu Lang, Zhang K aib.i Com parative study of several algorith m s for traveling sa les m an prob lem [ J] . Journal of Chongqing U n iversity of Posts and Telecomm un ications , 2008, 20( 5) : 525 528. ) [ 11 ] 王攀 , 商海 燕 . 基 于混 合遗 传 算法 的中 国旅 行商 问题 满意 解 [ J] . 航 空 计算 技 术 , 2000, 30 ( 1 ) : 19 21 . ( W ang Pan , Shang H aiyan. S at isfactory solu tion hybrid genet ic algorith m of ch ina trav el ing sales m an p rob lem [ J] . A eronau tical C om pu t ing Techn ique, 2000 , 30 ( 1) : 19 21 . ) [ 12 ] 罗中良 , 易明珠 , 刘小 勇 . 最 优化问题 的蚁群混 合差分进 化算 法研究 [ J] . 中山大学学报 ( 自然科学版 ) , 2008 , 47 ( 3 ) : 33 35 . ( Luo Zhongliang , Y iM ingzhu, L iu X iaoyong. O n ant colony hyb ird d iferent ial evolut ion for opt i m izat ion prob lem s[ J]. ACTA S cien tia ru m N atu ralium U n iversitat is Sunyatsen,i 2008 , 47( 3 ): 33 35. )

[ 3]

[ 4]

[ 5]

[ 6]


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图