求解TSP问题的改进混合蛙跳算法.pdf

口,口计算机工程与应用,
求解问题的改进混合蛙跳算法
张敬敏,马丽,李媛媛
, ,
石家庄经济学院信息工程学院,石家庄
,,,
, ,. —
.,,:—.
: —.
.
,“
’’“”.“”—
.“”—
.
, .
:;;——
;;
摘要:针对问题的特点,设计了一种求解问题的改进的混合蛙跳算法。该算法改进了子种群青蛙个
体优化的方式,而不仅是对最坏个体进行优化,这种方式可以有效提高算法的收敛速度。提出了青蛙个体翻
转时依赖于全局最优解的“导优”概率和依赖于子种群局部最优解的“导次优”概率,进一步提高了算法寻找最
优解的能力。在多个上的实验结果表明,该算法是可行有效的。
关键词:组合优化问题;旅行商问题;混合蛙跳算法;概率;
文章编号:——文献标识码: 中图分类号:
引言流行的智能算法主要有遗传算法、郭涛算法、蚁
旅行商问题, 群算法。、粒子群优化算法。、免疫算法、量子遗
又称货郎担问题,是一个著名的组合优化问题,也是传算法等。
一个典型的、易于描述却难于处理的完全问题。混合蛙跳算,
由于该问题的实际模型在路径、网络、分配、基因测最早是由和于年提出,源
序和机器人控制等方面有着广泛的应用,故长期以于对青蛙觅食行为的研究,具有概念简单,参数少,
来一直吸引着许多领域的研究人员对其算法改进的计算速度快,全局寻优能力强,易于实现等特点,并
关注。求解问题传统的方法有穷举搜索法、贪心且简单易用,已在多个领域取得了成功。然而,和其
法、动态规划法等,这些方法都面临着这样一个共他智能优化算法一样,同样存在易收敛到局部
同的问题,即当问题的规模Ⅳ大到一定程度时,问题最优的问题。本文对混合蛙跳算法进行了改进,将
的计算量极大地超出了机器所能允许的极限。现代每次迭代时,仅对每个子种群的最坏个体进行优化,
基金项目:国家自然科学基金;河北省科技计划项目.,.。
作者简介:张敬敏一,女,副教授,主要研究方向为智能优化计算、算法设计和数据库等;马丽一,女,讲师;李嫒嫒
一,女,讲师。—:.
收稿日期:—修回日期:——
:...—...
计算机工程与应用
改为对排序后的每个子种群中的后%的个体进行第个子群体,第只青蛙进入第个子群体,一直分
优化,并且提出了“导优”概率和“导次优”概率,加快配下去,直到第只青蛙进入到第个子群体。然后,
了收敛速度,并避免了早熟现象。的多个问第升只青蛙又进入到第个子群体,第什只青蛙进
题实验表明了该算法的可行陛和有效性。入到第个子群体,这样循环分配下去,直到所有青
蛙分配完毕。
问题描述. 求解问题的改进的混合蛙跳算法
问题可以简单描述为:已知个城市,。, 将混合蛙跳算法中每代进化时仅仅对子种群最
,,⋯,,以及任意两个城市之间的距离:,, 坏个体进行优化的操作,改为对排序后的每个子种
求一条经过中所有城市一次且仅一次的闭合路径群中的后%的个体进行优化,这种方式,可以有效
”一
⋯,,使得总行程∑,⋯,最小。提高算法的收敛速度,并通过设置合适的“导优”和
“导次优”概率,进一步提高算法寻找最优解的能
力。具体步骤如下。
Ⅳ
. 编码方法的初始种群。设置“