天津财经大学
本科毕业论文
中文题目： 优化算法的MATLAB实现技巧
英文题目：
院系名称： 专业班级： 学 号： 姓 名： 指导教师：
20XX年 x月 x 日
内容摘要
目 录
第1章 引言 ............................... 错误！未定义书签。 1.1 1.2 1.3
现代优化计算方法 ................. 错误！未定义书签。 MATLAB概述 ....................... 错误！未定义书签。 旅行商问题 ....................... 错误！未定义书签。
第2章 禁忌搜索算法的基本思想 ............. 错误！未定义书签。 2.1 2.2 2.3
相关概念介绍 ..................... 错误！未定义书签。 局部搜索算法 ..................... 错误！未定义书签。 禁忌搜索算法 ..................... 错误！未定义书签。
第3章 MATLAB实现TSP问题的实现技巧 ....... 错误！未定义书签。 3.1 3.2
重要概念的定义 ................... 错误！未定义书签。 算法中的方法选择问题 ............. 错误！未定义书签。
3.3 MATLAB实现技巧 ................... 错误！未定义书签。 第4章 结果分析 ........................... 错误！未定义书签。 4.1
................................. 错误！未定义书签。
4.2 ............................... 错误！未定义书签。 五、 总结与展望 ........................... 错误！未定义书签。 5.1 5.2
总结 ............................. 错误！未定义书签。 前景展望 ......................... 错误！未定义书签。
第1章 引言
1.1 现代优化计算方法
现代优化计算方法（简称优化算法）是一门交叉学科，是以人类等生物的行为方式或物质的运动形态为背景，运用数学抽象方法建立算法模型，再通过计算机的运算来求解组合最优化问题。优化算法涉及到了人工智能、分子运动，遗传学、动物学、神经系统和统计力学等学科的概念和理论，以模型的抽象为其关键点，以数学理论为基础。比较常见的有禁忌搜索、模拟退火、遗传算法、蚁群优化和人工神经网络等算法，这些算法主要是解决优化问题中的难解问题。自20世纪80年代以来计算机的蓬勃发展，这些算法借助计算机得到了快速发展和广泛应用。
1.2 MATLAB概述
MATLAB是matrix和laboratory两个词的组合，意为矩阵实验室，是由美国MathWorks公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境。MATLAB可以进行矩阵运算、绘制数据和函数、实现算法、创建用户界面、连接其他编程语言的程序等操作，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的问题解决方案，代表了当今国际科学计算软件的先进水平。
1.3 旅行商问题
旅行商问题，即TSP问题（Travelling Salesman Problem），是数学领域中的著名问题之一。问题概述为：假设有一个旅行商人要拜访n个城市，他必须选择拜访n个城市所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是：所要求得的路径路程为所有路径之中的最小值。
文章主要是运用禁忌搜索算法解决TSP问题，详细讲解算法的MATLAB实现技巧，并对算法的优化性能进行分析。首先介绍了禁忌搜索算法的基本思想，以此可以了解算法自身的特点和优势，然后运用禁忌搜索算法解决TSP问题，通过MATLAB实现，最后对优化结果进行分析，拟提出今后研究的方向。
第2章 禁忌搜索算法的基本思想
禁忌搜索算法是优化算法中比较常见的算法，本章先介绍禁忌搜索算法的相关概念，而后将以TSP问题为例介绍局部搜索算法，最后通过局部搜索算法发展到禁忌搜索算法。 2.1 相关概念介绍 2.2 局部搜索算法 2.3 禁忌搜索算法 概念：禁忌搜索算法（tabu search）是局部邻域搜索算法的推广，是人工智能在组合最优化中的一个成功应用。Glover在1986年首先提出这个概念。用一个禁忌表记录已经达到过的局部最优，或达到局部最优的一些过程，在后续搜索
中避免或有选择的搜索这些点或过程。算法体现了集中和扩散两个策略：
（1）集中：体现在局部搜索。从一点出发在这点的邻域内寻找更好的解以达到局部最优。
（2）扩散：通过对禁忌表中点的禁忌，达到一些没有搜索的点，从而实现更大区域的搜索。
第3章 MATLAB解决TSP问题的实现技巧
本章我们将以中国31省会城市的TSP问题为例，运用禁忌搜索算法解决。选取算法实现中重要部分的MATLAB代码进行详细分析。若需要完整注释代码，请参照附录。 3.1 重要概念的定义
从第2章中我们了解到，禁忌搜索算法中有几个重要的概念：禁忌表、禁忌表长度、候选解集合、候选集个数、最好候选解集合、最好候选解个数以及所求的最优解、最优值。
在后述程序中我们进行如下定义： 概念 禁忌表 禁忌长度 候选集个数 候选解集合 命名 TabuList TabuLength CandidateNum Candidates 作用 用来记录该次循环不能交换的禁忌元素的此时禁忌长度 用合理的方法确定的不能执行交换的长度 即全部邻域解的个数，预设一个充分大的数 用来记录此时全部候选解的集合 用合理的方法确定一个每次进入循环的候选解个数 每次循环从候选解集合中用合理的方法筛选出最有可能成为最优解的解集合 用来记录当前执行结果的最优解，即该问题当前的最小路径 用来记录当前最优解对应的最优值，即该问题当前的最小路径长度 最好候选解个数 BestCandidateNum BestCandidate 最好候选解集合 最优解 最优值 BSF BestL 3.2 算法中的方法选择问题
在用MATLAB解决TSP问题时，还有一些算法中如何选择和实现的问题，如下： 问题1：选择什么为禁忌的对象？ 问题2：禁忌的长度如何选取？ 问题3：候选集合如何选取？ 问题4：终止原则怎样给出？ 问题5：如何利用更多的信息？ 这些问题会在本章中一一解决。
3.3 MATLAB实现技巧 我们先来简单分析这个问题，我们的目标是求解中国31个省会城市的TSP问题，即我们需要给定31个城市的位置坐标数据，然后通过编程运算，返回出最优解和最优值。
明确了数据输入和结果输出，我们就开始解决这个问题。首先用MATLAB建立一个函数文件，函数名命名为TabuSearch（禁忌搜索），这个函数有两个返回参数，分别命名为BestShortcut和theMinDistance，即该问题的最短路径（最优解）和最小距离（最优值）。（对应代码行4） 首先定义一个Clist矩阵用于记录城市坐标数据，然后定义一个城市数目变量CityNum，调用MATLAB中的size命令CityNum=size(Clist,1)，求该TSP问题的规模，即城市数目，本题中为31。后期若所求城市数量和城市位置坐标发生改变，则只需对Clist中的数据进行修改。（对应代码行8到15） 初始化一个行列均为CityNum的全零矩阵dislist（即31*31矩阵），用于记录31个城市中每两个城市之间的距离。运用数学中两点间距离公式，通过两层循环计算相应两个位置上的距离并将结果记录到dislist矩阵中。（对应代码行16到23）
现在我们要对3.1.1中定义的一些重要概念进行初始化。（对应代码行24到32） 将禁忌表TabuList初始设定为城市数目阶零向量（即31*31矩阵），后续禁忌对象将填入