一种改进的基于教与学的优化算法求解旅行商问题
2015-01-22何湘竹
何湘竹
(中南民族大学 电子信息工程学院，武汉 430074)
一种改进的基于教与学的优化算法求解旅行商问题
何湘竹
(中南民族大学 电子信息工程学院，武汉 430074)
提出了一种改进的基于教与学的优化算法(TLBO)求解旅行商(TSP)问题，阐述了TLBO算法的基本思想和求解步骤，给出了算法流程，针对算法在解决大规模问题时易陷入局部最优的缺陷，引入混沌搜索机制对其进行了改进.着重研究了改进后的TLBO算法求解TSP问题的求解结果和性能分析，通过benchmark实例进行了仿真实验，结果表明：与诸如遗传算法和粒子群优化算法等已有启发式算法相比，改进后的TLBO算法在求解TSP问题时性能更为优越，从而为TSP问题的求解找到了一条新途径.
旅行商问题；NP完全；传统优化算法；启发式算法；TLBO算法；混沌搜索
旅行商问题(TSP)是图论中一个经典问题，同时也是一典型的组合优化问题，许多诸如网络路由选择、物流车辆路线规划等实际工程问题都是TSP的扩展应用， TSP的研究不仅具有重要的理论价值更具有实际工程意义[1].
但由于TSP的NP难属性，致使诸如线性规划、动态规划等传统的优化算法在求解该问题时效率低下，尤其随着城市规模的增加，会出现组合爆炸现象[2].因此很多启发式算法应运而生，较为代表的有遗传算法(GA)[3-4]、粒子群优化算法(PSO)[5]、蚁群算法[6]等，这些算法寻找问题的近似最优解来取代最优解，既高效灵活又可修改或微调以适用于求解多种具体问题，被证实比经典算法性能更加优越并因此获得广泛应用.
基于教与学的优化(TLBO)算法是一个受课堂知识传授现象启发而来的新智能算法，它于2010年由Rao等人首次提出，其最大的特点是算法运行不需要特殊的控制参数，从而克服了许多启发式算法参数过多的缺陷.TLBO算法自问世以来，不仅在理论研究上取得了一系列的成果，而且在各应用领域也备受关注[7-9].但试验结果表明对于大的benchmark函数，TLBO算法易陷入局部最优[10].对“早熟”现象分析后发现：问题的原因是解缺少多样性.针对该缺陷，考虑到混沌搜索机制具有随机性和各态遍历的特点，将其引入对解产生扰动增加其多样性，从而改善算法在整个解空间的全局搜索能力.
本文在对TSP问题进行数学建模的基础上，在深入分析TLBO算法的基本思想和流程之后，将混沌搜索机制引入TLBO对算法进行改进，并将改进后的算法用于TSP问题的求解，给出了详细的求解步骤.对TSPLIB中的benchmark实例仿真实验结果表明，改进后的TLBO算法在求解TSP问题上表现良好，性能优越，从而为TSP求解找到了一条新的途径.
1 TSP问题建模
一个具有n个顶点的图G，常常可以表示为G=
经过每一个城市一次的回路称为哈密顿圈(HC)，距离最短的HC称为最优哈密尔顿圈(OHC)，在图论中，TSP问题指在带权图G中找到OHC，G中的顶点和边分别代表城市和路线.具体描述如下：对于一个具有n个顶点的无向带权图G=(V, E, D)，V={v1,…,vn}为代表城市的顶点集，E=[eij]n×n为表示城市之间连接公路的边集，D={dij|(vi,vj)∈E且vi≠vj, dij>0}代表城市vi和vj之间的距离的集合.设：
(1)
则TSP问题的数学模型如下：
(2)
(3)
其中式(2)为目标函数，式(3)表示目标函数必须满足的约束条件：任一城市vi被遍历到且仅被遍历1次，任一可能的遍历序列中必须包含所有的顶点.
2 TLBO算法
2.1 算法思想
TLBO算法是Rao于2010年提出的一种新自然启发式算法，该算法基于老师对于一个班级学生成绩的影响来实现，TLBO算法不需要具体控制参数，和其它如GA和PSO之类的算法相比，实现更为简单且性能更好.
TLBO算法模拟课堂教学过程，认为一个好老师可以使整个班级学生的平均成绩提高.班级中成绩最好的学生被选择模拟老师，从而使整个班级的成绩往自身方向提高，此时再产生新老师，循环执行上述过程直到发现最优解.算法中种群被看作一组学生，不同的设计变量被类比为提供给学生的不同学科，学生的成绩类比为适应值，老师被认为是目前所获得的最优解.
2.2 算法步骤
TLBO算法由两部分组成：老师阶段和学生阶段.
2.1.1 老师阶段
此阶段模拟学生向老师学习的过程，在这个阶段中老师试图将整个班级学生的平均成绩Mi提高到自身水平Mnew，现有平均值和新的平均值之间的差值为：
Difference_Meani=ri(Mnew-TFMi).
(4)
其中TF是教学因子，它决定了平均值被改变的程度，一般取1或2，是启发式中重要的一步，由公式(5)以相同的概率随机确定，ri是一个在[0,1]范围内取值的随机数.
TF=round[1+rand(0,1){2-1}].
(5)
由平均值差Difference_Meani，根据公式(6)更新已知解：
Xnew,i=Xold,i+Difference_Meani.
(6)
2.1.2 学生阶段
在此阶段所有学生通过互相影响来获取知识.一个学生随机地与另一学生交流来提高其知识水平.学生总是能从更有知识的另一方那里学到新东西.这一阶段的学习现象可以用数学公式(7)和(8)表示.
在第i次迭代中，考虑两个不同的学生Xi和Xj(i≠j):
Xnew,i=Xold,i+ri(Xi-Xj),if f(Xi) (7) Xnew,i=Xold,i+ri(Xj-Xi),if f(Xj) (8) 如果Xnew的函数值更为理想，则接受它. TLBO的具体实现步骤如下： 第1步：初始化优化问题的种群、设计变量以及迭代次数，并对种群进行评价； 第2步：选出每一个科目成绩最好的学生作为该科目的老师并计算各科目所有学生的平均成绩； 第3步：根据式(4)利用教学因子TF计算目前平均值和最好平均值之间的差值； 第4步：根据式(6)在老师帮助下的更新每位学生的知识； 第5步：根据式(7)和(8)利用其它学员的知识更新每位学生的知识； 第6步：重复第2步到第5步直到算法终止条件满足. 2.3 算法流程图 算法的流程图如图1所示. 3.1 混沌搜索 混沌是非线性动态系统中存在的确定却类似随机的一个过程，具有非周期、不收敛和约束的特点，且对初始条件和参数十分敏感.混沌的天性使其具有明显的随机性和不可预测性，但同时却拥有规则的元素.从数学角度理解，混沌是一个简单的确定性动态系统的随机性状态，且混沌系统可以看作随机源[11]. 混沌映射是一个在混沌状态下运行的离散的动态系统： xk+1=f(xk),0 (9) 其中，混沌序列{xk:k=0,1,2,…}可以作为随机序列的扩频序列，且被证明易于快速产生和保存，即便对非常长的序列，也只需要保存少数几个函数(混沌图)和极少的参数(初始条件)，而无需存储整个序列[12]. 在本文中，r个混沌变量由如下Logistic映射获得： (10) 3.2 改进的TLBO算法 将混沌搜索引入TLBO算法，改进后的TLBO算法其伪码如图2所示. 以下仿真实验开发环境为ADMPhenom(tm)ⅡX2B59 处理器3.40GHz，开发软件为Matlab2013.为了测试改进的TLBO算法求解TSP问题的性能，我们选择了http://www.crpc.rice.edu/softlib/tsplib/上的具有14个城市的TSP标准问题，该benchmark问题常被用来验证比较算法的性能，14个城市的坐标信息见表1. 我们将GA、PSO、改进后的TLBO算法分别用于求解该benchmark问题，为了保证实验结果的有效性，三种算法的种群数均设置为100个，最大迭代次数设置为600次，每种算法独立运行20次.改进后TLBO算法的性能分析见表2. 从实验结果可以看出，TLBO算法在规定的迭代次数内得到了最优解，这证明了算法求解TSP问题的有效性.为了更好分析TLBO算法的求解效率和收敛特性，给出了三种算法的收敛曲线比较图(图3所示)，从图中可以看出，与GA和PSO算法相比，改进TLBO算法只经过很小的迭代次数(128次)便得到了最优解，收敛速度更快，这主要得益于TLBO算法的教师和学生阶段以及引入的混沌搜索机制，在保证算法的全局搜索能力的同时加强了算法的局部搜索速度. 文中采用了一种改进的基于教与学的优化算法(TLBO)来求解旅行商问题.该算法是一种基于种群的新智能算法，主要分为两个阶段：教师阶段和学生阶段，其最大的优点是除了种群大小和迭代代数等一般控制参数之外，算法运行不需要其它特殊控制参数，但在大规模问题求解时易陷入局部最优，本文引入混沌搜索机制对其改进.实验表明，改进后的TLBO算法在求解TSP问题上与其它已有的启发式算法如遗传算法和粒子群算法相比，性能更加优越，从而为旅行商问题的求解提供了一种有效的手段. [1] 赵秋实． 混合遗传算法解决旅行商问题的研究[D]．南宁: 广西大学，2013． [2] Wang Y． The hybrid genetic algorithm with two local optimization strategies for traveling salesman problem[J]．Computers & Industrial Engineering， 2014， 70:124-133． [3] Liu Y H． Different initial solution generators in genetic algorithms for solving the probabilistic traveling salesman problem[J]． Applied Mathematics and Computation，2010，216( 1) : 125-137． [4] 杜明，王江晴． 一个基于遗传算法的TSP 问题解决方案[J]． 中南民族大学学报: 自然科学版，2007，26( 1) : 77-79． [5] Chen S M，Chien C Y． Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques[J]． Expert Systems with Applications，2011，38( 12) :14439-14450． [6] 程满中，王江晴． 基于群集智能的蚁群算法研究[J]．中南民族大学学报: 自然科学版，2006，25 ( 4 ) :73-76． [7] Rao R V，Savsani V J，Vakharia D P． Teaching - learning-based optimization: a novel method for constrained mechanical design optimization problems[J]． Computer-Aided Design，2011，43( 3) : 303-315． [8] Rao R V，Savsani V J，Vakharia D P． Teaching - learning-based optimization: an optimization method for continuous non-linear large scale problems [J]． Information Sciences，2012，183( 1) : 1-15． [9] Togˇ an V． Design of planar steel frames using teaching - learning based optimization[J]． Engineering Structures， 2012，34: 225-232． [10] Huang J，Li X，Gao L． A new hybrid algorithm for unconstrained optimisation problems[J]． International Journal of Computer Ap plications in Technology，2013， 46( 3) : 187-194． [11] Alatas B． Chaotic bee colony algorithms for global numerical optimization [J]． Expert Systems with Applications，2010，37( 8) : 5682-5687． [12] Heidari-Bateni G，McGillem C D． A chaotic directsequencespread-spectrum communication system[J]．IEEE Transactions on Communications，1994，42( 234) :1524-1527． Teaching-Learning Based Optimization Algorithm He Xiangzhu (College of Electronics and Information, South-Central University for Nationalities, Wuhan 430074, China) This paper introduced an improved teaching-learning based optimization algorithm into traveling salesman problem, it illustrated the main ideas and the procedure of TLBO, to overcome the shortage of being trapped into local optimum when facing large scale problems, the chaos search mechanism was introduced to improve the performance of TLBO. The paper focused on the result and performance analysis of solving the traveling salesman problem with improved teaching-learning based optimization algorithm, experimental results of some typical benchmarks demonstrated that compared with other heuristic algorithms like GA and PSO, the improved TLBO algorithm achieved a good performance while requiring a much less computation, thus can be served as a new method to solve TSP problem. traveling salesman problem; NP complete; traditional optimization algorithm; heuristic algorithm; teaching-learning based optimization; chaos search 2015-03-20 何湘竹(1974-), 女, 副教授，研究方向：优化算法，E-mail：xzhe@mail.scuec.edu.cn 国家重点基础研究发展计划项目(973计划项目)(2011CB706804)；教育部中央高校基本科研业务费专项(CZQ12002) TP391 A 1672-4321(2015)04-0089-053 TLBO算法改进
4 实验结果
5 结语
for Traveling Salesman Problem
