机器学习课程论文_计算机软件及应用_it计算机_专业资料

机器学习课程论文_计算机软件及应用_it计算机_专业资料 机器学习(论文) 机 器 学 习 (课程论文) - 1 - 李亚龙 E201102016 基于蚁群算法的TSP问研究 摘 要 本文研究了基于蚁群算法解决TSP问题的原理，算法流程以及用Microsoft Visual Studio 2008程序的仿真。论文首先简单回顾了蚁群算法的历史、发展以及应用，然后详细介绍了基本蚁群算法的原理，包括基本蚁群算法的行为描述和机制原理。其次从基本蚁群算法的系统学特征出发，讨论它具有分布式，自组织，正反馈等特征。接着引出了基本蚁群算法解决的TSP问题，先讨论了组合优化问题，然后从TSP问题的定义，实用价值，理论意义的角度对TSP问题进行阐述。并且重点运用Microsoft Visual Studio 2008 的仿真方法，实现了基于蚁群算法的仿真，给出了求解TSP问题的数学模型，实现步骤，描述了蚁群算法的优缺点。论文最后以Microsoft Visual Studio 2008仿真实验为基础，对蚁群算法的主要参数进行了详细的讨论，并且给出了优化的参数选择，解决了算法中存在的不足。论文实现了基于蚁群算法对TSP问题的求解和仿真。 关键字:蚁群算法，组合优化，信息素，TSP问题 - 2 - 机器学习(论文) 目 录 摘 要 .......................................................................................................................................... 2 第1章 绪论 .............................................................................................................................. 4 1.1 蚁群算法概况 ..................................................................................................................... 4 1.2 论文的主要内容 ................................................................................................................. 4 第2章 基本蚁群算法简介 ...................................................................................................... 6 2.1 基本蚁群算法的原理 ......................................................................................................... 6 2.1.1 蚁群行为描述 .................................................................................................................. 6 2.1.2 基本蚁群算法的机制原理 .............................................................................................. 8 2.2 基本蚁群算法的系统学特征 ............................................................................................. 9 2.2.1 分布式 .............................................................................................................................. 9 2.2.2 自组织 ............................................................................................................................ 10 2.2.3 正反馈 ............................................................................................................................ 10 第3章 组合优化以及TSP问题简介 ...................................................错误～未定义书签。 3.1 组合优化简介 ...................................................................................错误～未定义书签。 3.1.1 引言 ................................................................................................错误～未定义书签。 3.1.2 组合优化问题 ................................................................................错误～未定义书签。 3.1.3 NP完全问题 ...................................................................................错误～未定义书签。 3.2 TSP问题简介.....................................................................................错误～未定义书签。 3.2.1 TSP问题的定义..............................................................................错误～未定义书签。 3.2.2 TSP的实用价值..............................................................................错误～未定义书签。 3.2.3 TSP问题的理论意义......................................................................错误～未定义书签。 3.3 基本蚁群算法的数学模型 ...............................................................错误～未定义书签。 第4章 基本蚁群算法求解TSP ............................................................................................ 15 4.1 基本蚁群算法求解TSP的实现流程 .............................................................................. 15 4.1.1 基本蚁群算法的实现步骤 ............................................................................................ 15 4.1.2 基本蚁群算法的结构流程 ............................................................................................ 15 4.2 关键参数介绍 ................................................................................................................... 17 4.3 不同参数设置的试验 ....................................................................................................... 17 4.3.1 信息素挥发度的设置 .................................................................................................... 17 4.3.2 蚁群数量的设置 ............................................................................................................ 17 4.3.3 启发式因子的设置 ........................................................................................................ 17 4.4 不同参数设置的试验结果和结论 ................................................................................... 18 4.4.1 信息素挥发度的选择设置 ............................................................................................ 18 4.4.2 启发式因子的选择设置 ................................................................................................ 21 结论与展望 .............................................................................................................................. 26 - 3 - 李亚龙 E201102016 第1章 绪论 蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。 1.1 蚁群算法概况 M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是:通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征[1]，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。 蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及在有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。 以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究[2]。美国五角大楼正在资助关于群智能系统的研究工作-群体战略(Swarm Strategy)，它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。 多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通[5]等领域。蚁群算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域已经获得成功的应用，其中最成功的是在组合优化问题中的应用。 1.2 论文的主要内容 因为蚁群算法有很多种,并且TSP问题是蚁群算法众多解决问题中的经典问题,所以 - 4 - 机器学习(论文) 具有很大的随意性。虽然蚁群算法的选择性很多，但是所有的算法都是基于最基本的蚁群算法，并且基本蚁群算法也可以很好的解决TSP问题，以及说明参数选择问题。所以本文以基本蚁群算法为基础，重点讨论了基本蚁群算法如何解决TSP问题。 第1章主要介绍了蚁群算法的历史、发展、应用，对蚁群算法原理的核心—信息素作了简单的描述。 第2章对基本蚁群算法的原理进行了介绍，包括基本蚁群算法的行为描述，机制原理。同时探讨了基本蚁群算法的系统学特征。 第3章对组合优化以及TSP问题的定义，实用价值，理论意义进行了描述。并且介绍了基本蚁群算法求解TSP问题的数学模型。 第4章首先介绍了基本蚁群算法的实现步骤和结构流程，然后讨论了蚁群算法中主要参数对于蚁群算法的全局搜索能力以及收敛性的影响，并做了相应仿真实验加以验证。 - 5 - 李亚龙 E201102016 第2章 基本蚁群算法简介 2.1 基本蚁群算法的原理 2.1.1 蚁群行为描述 根据仿生学家的长期研究发现:蚂蚁虽然没有视觉，但运动时会通过在路径上释放出一种特殊的分泌物——信息素来寻找路径。当它们碰到一个还没有走过的路口的时，就随机的挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快的重新找到最优路径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群行为找出最优路径。这里用人工蚂蚁觅食图来描述蚁群搜索原理。 图 2.1 人工蚂蚁觅食模拟 - 6 - 机器学习(论文) 图 2.2 人工蚂蚁觅食模拟 图 2.3 人工蚂蚁觅食模拟 - 7 - 李亚龙 E201102016 图2.1中，设A点是蚁巢，D点是食物源，EF之间区域是障碍物。由于障碍物的存在，蚂蚁只能经由A经E或F到达D，或由D到达A，各点之间的距离如图2.1所示。假设每个时间单位有30只蚂蚁由A到达D点，有30只蚂蚁由D到达A点，蚂蚁过后留下的信息量为1。为了方便起见，设该物质停留时间为1。在初始时刻，由于路径BF、FC、BE、EC上均无信息存在，位于A和D的蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择BE、FC、BE、EC，如图2.2所示。经过一个时间单位后，在路径BFC上的信息量是路径BEC上的信息量的2倍。又经过一段时间，将有20只蚂蚁由B、F和C点到达D，如图2.3所示。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BFC，最终将会完全选择BFC，从而找到由蚁巢到食物源的最短路径。 2.1.2 基本蚁群算法的机制原理 模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入，该算法基于以下基本假设: 1.蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对其周围的局部环境产生影响。 2.蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上 是其 基因的适应性表现，即蚂蚁是反应型适应性主体。 3(在个体水平上，每只蚂蚁仅根据环境做出独立选择;在群体水平上，单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段:适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择;时间越长，信息量会越小;在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求的问题的每一方面都有详尽的认识。自组织本质上体现了从无序到有序的动态演化，其逻辑结构如下图所示。 - 8 - 机器学习(论文) 蚁群活动规划 蚂蚁个体A信息素蚂蚁个体B信息素信息素更新管理的增量构建的增量构建 信息素决策点问题表达 组合优化问题 图 2.4 基本蚁群算法的逻辑结构 由图2.4可见，先将具体的组合优化问题表述成规范的格式，然后利用蚁群算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化的最优解。 2.2 基本蚁群算法的系统学特征 基本蚁群算法在系统学上表现以下三个特征:分布式，自组织，正反馈。三者表现出一个整体，相辅相成。 2.2.1 分布式 自然界中的真实蚁群行为也出现了分布式。当蚁群需要完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体的的缺陷而受到影响。 蚁群算法作为对蚁群觅食行为的抽象，也体现了群体行为的分布式特征。每只人工蚂蚁在问题空间的多个点同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。 具体到不同的优化问题而言，蚁群算法体现出的分布式特征就具有了更加现实的意义。因为所有的仿生优化算法均可看做按照一定规则的问题解空间搜索最优解的过程，所以搜索点的初始选取就直接关系到算法求解结果的优劣和算法寻优效率。当求解许多复杂问题时，从一点出发的搜索受到局部特征的限制，可得不到所求问题的满意解;而 - 9 - 李亚龙 E201102016 基本蚁群算法则可看做是一个分布式的多智能系统，它在问题空间的多点同时独立地进行解搜索，不仅使得算法具有较强的全局搜索能力，也增加了算法的可靠性。 2.2.2 自组织 基本蚁群算法的另一个重要特征是自组织。自组织的概念是随着系统科学的发展而建立起来的。通常把系统论中的组织行为分为自组织和他组织两大类[4]。其根本区别在于组织力或组织指令是来自于系统内部还是来自于系统外部，前者称为自组织，而后者即为他组织。如果系统在获得时间的、空间的或者功能的结果过程中，没有外界的特定干预，则称为系统是自组织的。 从抽象意义上讲，自组织就是在没有外界作用下使得系统从无序到有序的进化过程。基本蚁群算法体现了这一过程，以蚁群优化为例，当算法开始的初期，单只人工蚂蚁无序地寻找解，经过一段时间的算法演化，人工蚂蚁越来越趋向于寻找到接近最优解的一些解，这恰恰体现了从无序到有序的自组织进化。 自组织大大增强了算法的鲁棒性[5](在这里可以理解为算法抗干扰性,就是指不是针对具体问题算法也同样可以求解,极大的体现了蚁群算法的抗干扰能力)，传统的算法都是针对某一具体问题而设计的，这往往建立在对该问题有了全面清晰认识的基础上，通常很难适应其他问题。而自组织的蚁群算法不需要对待求解问题的所有问题的所有方面都有所认识，因而较容易应用到一类问题中。 2.2.3 正反馈 反馈是控制论中的重要概念，它代表信息输入对输出的反作用。在系统学上认为，反馈就是把系统现在的行为作为影响系统未来行为的原因。反馈分正反馈和负反馈两种，前者指的是以现在的行为去加强未来的行为，而后者则是以现在的行为去削弱未来的行为。 由自然界中真实蚂蚁的觅食行为可见，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息素的堆积，而信息素的堆积却是一个正反馈的过程，对于基本蚁群算法而言，初始时在环境中存在完全相同的信息量，给系统一个微小的扰动，使得各个边上的信息量大小不同，蚂蚁构造的解就存在了优劣。算法采用的反馈方式是在较优解经过的路径留下更多的信息素，更多的信息素又吸引了更多的蚂蚁，这个正反馈的过程使得初始值不断地扩大，同时又引导整个系统向着最优解的方向进化。 单一的正反馈或者负反馈存在于线形系统之中，是无法实现系统的自我组织的。自组织系统通过正反馈和负反馈机制，它体现于蚁群算法在构造问题解的过程中用到了概率搜索技术，通过该技术增加了生成解的随机性。随机性的影响就在于接受了解在一定程度上的退化，另一方面又使得搜索范围得以在一段时间内保持足够大。这样正反馈缩小搜索范围，保证算法朝着最优解的方向进行;而负反馈保持搜索范围，避免算法过早收敛于不好的结果。恰恰是在正反馈和负反馈共同作用影响下，基本蚁群算法得以自组织地进化，从而得到问题在一定程度上的满意解。 - 10 - 机器学习(论文) 第3章 组合优化以及TSP问题简介 3.1 组合优化简介 3.1.1 引言 伴随计算机技术的飞速发展，计算机正日益成为人们解决问题的不可或缺的重要工具。但在实践中人们发现，存在这样一类问题，运用精确的算法在多项式时间内无法找到问题的最优解，这类问题称为组合优化问题。这类问题通常随着问题规模的扩大，问题空间呈现组合爆炸特征，求解问题的空间、时间复杂度将呈指数级增长，使用常规的方法求解，在现有条件下是无法实现的，属于NP完全问题。TSP问题就是其中最经典问题之一。因此利用仿生进化算法，在较短的时间内，求得问题的满意解，就成为研究的重点。 3.1.2 组合优化问题 组合优化问题的目标是从组合问题的可行解中求出最优解。在现实世界里存在大量组合优化问题，其中许多问题如旅行商问题、图着色问题、分配问题、调度问题、布线问题及路由选择问题等，至今没有找到有效地多项式算法，这些问题己被证明是NP完全问题。 优化问题有三个基本要素:变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的限制称为约束，表示可行衡量的函数称为目标函数。组合优化问题就是在给定的约束条件下，求目标函数最优值的问题。组合优化问题的一个实例可以表示为一个对偶(S，f)，其中解空间S为可行解目标函数f是一个映射，定义为: fSR:, 求目标函数最小值问题称为最小化问题，记为: min(),fiiS, 求目标函数最大值问题称为最大值问题，记为: max(),fiiS, 显然，只要改变目标函数的符号，最小化问题与最大化问题就可以等价转换。使目标函数最优值的解称为最优解(整体最优解)。设(S，f)是组合优化问题的一个实例，iS,fifi()(),imin(),fiiS,aptaptaptiS,,若: (对所有的成立)，称为最小化问题的最优解。 优化问题在工程中有着广泛的应用，其涉及的问题是在一组限制条件下求解问题的最好(或最优)解的问题。按照人类认知问题的特点，最优化问题很自然的被划分为两类:一类是连续变量的问题，另一类是离散变量的问题。对于离散变量问题来说，一般是寻找离散事件的最优编排，分组，次序或筛选等。不难看出这些问题的解的个数是有限的。通常把这类问题称为组合最优化问题，而研究用数学方法来求解这些问题就被称为组合最优化。 - 11 - 李亚龙 E201102016 3.1.3 NP完全问题 按照计算复杂性理论研究问题求解的难易性，可把问题分为P类、NP类和NP完全类。 定义一:对于判定问题D，存在一个多项式P(t)，使得对其每一输入规模为n的实例，可以在P(n)时间内求得最优解，此类问题称为P(Polynomial)问题。其它的则是NP(Non一Polynomial)问题。 假如一个问题是P问题，我们通常认为它是“简单的”，而NP问题，通常认为它是“复杂的”。NP问题是指可在多项式时间里检验的问题，至今尚未找到多项式时间算法。 LNP,定义二:若问题,所有NP问题都可以经过多项式计算时间转化为L，则L称为NP完全问题。 如果NP完全类问题中有一个问题能用多项式确定性算法解决，则其他所有的NP完全类问题都能用多项式确定性算法来解决，很多问题被证明为NP完全问题，如TSP问题，NP完全问题也是检验仿生算法有效性和可靠性的有效平台。 3.2 TSP问题简介 3.2.1 TSP问题的定义 TSP问题的英文名(traveling salesman problem),中文译为旅行商问题。问题的定义很简单，即为一个旅行商要走访N个城市，每个城市必须经过一次且只能经过一次，最后回到出发的城市就算是完成了一次旅行，问如何能找到一条最短的路径。其相应的数 ccC,,Cccccc,{,,,,...}ij1234n学描述如下:设有一个城市集合，其每对城市间的距离为 ，ccccc,,,,...,，，dccZ(,),,,,,,1234n，，，，，，，，，，ii。求一条经过C中每个城市正好一次的路径，使 n,1 dccdcc,,，，，，，,,,,,，，，，iin，11，，，，i,1得最小。 3.2.2 TSP的实用价值 TSP问题广泛的存在于许多领域，而且问题规模(城市的数目)都很大。比如说，电路板钻孔问题，X射线结晶学问题，VLSL(超大规模集成电路)制造问题等等。总之，凡是可以抽象成为遍历全部城市一次且仅一次，求代价最小的路径的问题，都可以当作TSP问题来解决。 3.2.3 TSP问题的理论意义 同实用价值相比，TSP问题的理论意义更加重大。事实上，该问题是作为所有组合优化问题的范例而存在的[11]。它己经成为并将继续成为测试新算法的标准问题。这是因为，TSP问题展示了组合优化的所有方面。它从概念上来讲非常简单，但是其求解的难度是很大的。如果针对TSP问题提出的某种算法能够取得比较好的实算效果，那么对其进行修改，就可以应用于其它类型的组合优化问题并取得良好的效果。基于上述原因，该问题吸引了许多不同领域的研究者。 - 12 - 机器学习(论文) 3.3 基本蚁群算法的数学模型 ,t，，ij设为t时刻路径(i,j)上的信息量，n表示TSP规模，m为蚁群中蚂蚁的总数 ,0,const，，ij目。在初始时刻各条路径上的信息量相等，并设。 (k=1,2,…,m)在运动过程中，根据各条路径上的信息量决定其转移方向，蚂蚁k tabukm,1,2,...,，，tabukk这里用禁忌表来记录蚂蚁k当前所走过的城市，集合随着进化过程作动态调整。在搜索过程中，蚂蚁根据各条路径上的信息量及路径的启发信息来计 kpt，，ij算状态转移概率。表示在t蚂蚁k由城市i转移到城市j的状态转移概率 ,,，，,,tt ，，，，，，,ijik，，，，,,,tt ，，，，，，，，,,isis,，，，，,sallowedk,k, pt，，,ij , ,0, allowedk式中，表示蚂蚁k下一步允许选择的城市;α为信息启发式因子，表示轨迹的相对重要性，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时的所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强;β为期望启发式因子，表示能见度的相对重要性，反映了蚂蚁在运动过程中启发信息在蚂蚁 ,t，，ij选择路径中的受重视程度，其值越大，则该状态转移概率越接近于贪心规则;为启发函数，其表达式如下: ,td,1 ，，ijij k,tptd，，，，ijijij式中，表示相邻两个城市之间的距离。对蚂蚁k而言，越小，则越大，也就越大。显然，该启发函数表示蚂蚁从城市i转移到城市j的期望程度。 为了避免残留信息素过多引起残留信息淹没启发信息，在每只蚂蚁走完一步或者完成对所有n个城市遍历(也即一个循环结束)后，要对残留信息进行更新处理。这种更新策略模仿了人类大脑记忆的特点，在新信息不断存入大脑的同时，存储在大脑中的旧信息随着时间的推移逐渐淡化，甚至忘记。由此，t+n时刻在路径(i,j)上的信息量可按如下规则进行调整 ,,,,tntt，,,，,1 ，，，，，，，，ijijij mk ,,,,,tt，，，，,ijijk,1 式中，ρ表示信息素挥发系数，则1-ρ表示信息素残留因子，为了防止信息的无限 ,,,,0,1;t，，，,ij积累，ρ的取值范围为:表示本次循环中路径(i,j)上的信息素增量， k,,,,,00,t，，，，ijij初始时刻表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。 根据信息素更新策略的不同，Dorigo M提出了三种不同的基本蚁群算法模型，分别 k,,t，，ij称之为Ant-Cycle模型、Ant-Quantity模型及Ant-Density模型，其差别在于求法的不同。 - 13 - 李亚龙 E201102016 在Ant-Cycle模型中 Q如果第只蚂蚁在时间到之间经过边(，)ktt+1ij,kL,,k,,,ij0否则, ,Lk式中，Q表示信息素强度，它在一定程度上影响算法的收敛程度;表示第k只蚂蚁在本次循环中所走过路径的总长度。 在Ant-Quantity模型中 Q如果第只蚂蚁在时间到之间经过边(，)ktt+1ij,ijd,,k,,,ij0否则 , ,在Ant-Density模型中 Q如果第只蚂蚁在时间到之间经过边(，)ktt+1ij,k,,,,ij0否则, 后两个中利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素;而第一个公式中利用的是整体信息，即蚂蚁完成一次循环后更新所有路径上的信息素，在求解TSP时性能较好，因此通常采用第一个公式作为蚁群算法的基本模型。 - 14 - 机器学习(论文) 第4章 基本蚁群算法求解TSP 4.1 基本蚁群算法求解TSP的实现流程 4.1.1 基本蚁群算法的实现步骤 以TSP为例，基本蚁群算法的具体实现步骤如下: NNccmax(1)参数初始化。令时间t=0和循环次数=0，设置最大循环次数，将m只 ,tconst,，，ij蚂蚁置于n个城市上，令每条边(i,j)的初始化信息量，其中const表示常 ,,,00，，ij数，且初始时刻。 NN,，1cc(2)循环次数。 (3)蚂蚁的禁忌表索引号k=1 kk,，1(4)蚂蚁数目。 (5)蚂蚁个体根据状态转移概率公式计算的概率选择城市j。 (6)修改禁忌表指针，即选择好之后将蚂蚁移动到新的城市，并把该城市移动到该蚂蚁个体的禁忌表中。 )若集合C中的城市未遍历完，即k=蚂蚁总数m, Y 信息量更新 满足结束条件, Y 输出程序计算结果 结束 图 4.1 基本蚁群算法的程序结构流程 - 16 - 机器学习(论文) 4.2 关键参数介绍 蚁群算法中α、β、ρ等参数对算法性能有很大的影响。α值的大小表明留在每个结点上的信息量受重视的程度，α值越大，蚂蚁选择以前经过的路线的可能性越大，但过大会使搜索过早陷于局部最小解;β的大小表明启发式信息受重视的程度，β值越大，蚂蚁选择离它近的城市的可能性越大;ρ表示信息素的保留率，如果它的值取的不恰当，得到的结果会很差。 4.3 不同参数设置的试验 蚁群算法中信息启发式因子α、期望启发式因子β、挥发系数ρ、蚂蚁数目m的设置值的不同会对蚁群算法的全局搜索能力和收敛速度产生很大的影响，接下来会对不同参数的设置对蚁群算法性能的影响进行描述，然后给出实验结果和结论。 4.3.1 信息素挥发度的设置 在蚁群算法中，人工蚂蚁是具有人类记忆功能的，随着时间的推移，以前留下的信息将要逐渐消逝。在算法模型中用参数ρ表示信息消逝程度(或称信息素挥发度)，而ρ?1就是信息素保留系数。蚁群算法存在着收敛速度慢、易于陷入局部最优等缺陷。而信息素挥发度ρ的大小直接关系到蚁群算法的全局搜索能力及其收敛速度:由于信息素ρ的存在，当要处理的问题规模比较大时，会使那些从来未被搜索到的路径(可行解)上的信息量减小到接近于0，因而降低了算法的全局搜索能力，而且当ρ过大时以前搜索过的路径被再次选择的可能性过大，也会影响到算法的随机性能和全局搜索能力;反之，通过减小信息素挥发度ρ虽然可以提高算法的随机性能和全局搜索能力，但又会使算法的收敛速度降低。关于蚁群算法中信息素挥发度ρ对算法性能的影响及其在实际应用中的选择，可以通过计算机仿真实验来分析和确定。 4.3.2 蚁群数量的设置 蚁群算法是一种随机搜索算法，通过多个候选解(可行解的一个子集)组成的群体的进化过程来寻求最优解，在该过程中既需要每个个体的自适应能力，更需要群体的相互协作。蚁群在搜索过程中之所以表现出复杂而有序的行为，个体之间的信息交流与相互协作起着至关重要的作用。对于TSP问题，单个蚂蚁在一次循环中所经过的路径，表现为问题可行解集中的一个解，m只蚂蚁在一次循环中所经过的路径，则表现为问题解集中的一个子集。显然;子集越大(即蚁群数量多)可以提高蚁群算法的全局搜索能力以及算法的稳定性;但蚂蚁数目增大后，会使大量的曾被搜索过的解(路径)上的信息量的变化比较平均，信息正反馈的作用不明显，搜索的随机性虽然得到了加强，但收敛速度减慢;反之，子集较小(即蚁群数量少)，特别是当要处理的问题规模比较大时，会使那些从来未被搜索到的解(路径)上的信息量减小到接近于0，搜索的随机性减弱，虽然收敛速度加快，但会使算法的全局性能降低，算法的稳定性差，容易出现过早停滞现象。 4.3.3 启发式因子的设置 ,t，，ij信息启发式因子α反映蚂蚁在运动过程中所积累的信息量(即残留信息量)在指导蚁群搜索中的相对重要程度，期望值启发式因子β反映蚂蚁在运动过程中启发信息 ,ij(即期望值)在指导蚁群搜索中的相对重要程度。期望值启发式因子β的大小反映了蚁群在路径搜索中先验性、确定性。β因素作用的强度，其值越大，蚂蚁在某个局部点上选择局部最短路径的可能性越大，虽然搜索的收敛速度得以加快，但蚁群在最优路径的 - 17 - 李亚龙 E201102016 搜索过程中随机性减弱，易于陷入局部最优;而信息启发式因子α的大小则反映了蚁群在路径搜索中随机性因素作用的强度，其值越大，蚂蚁选择以前走过的路径的可能性越大，搜索的随机性减弱，当α值过大也会使蚁群的搜索过早陷于局部最优。蚁群算法的全局寻优性能，首先要求蚁群的搜索过程必须有很强的随机性;而蚁群算法的快速收敛性能，又要求蚁群的搜索过程必须要有较高的确定性。因此，两者对蚁群算法性能的影响和作用是相互配合、密切相关的。 4.4 不同参数设置的实验结果和结论 本文采用缺省参数设置为1=α、5=β、5.0=ρ,蚂蚁的数目总是设置为城市的总数目，即初始时刻每个城市放置一个蚂蚁。实验中所有TSP问题数据来源于Eli51城市问题(这是蚁群算法解决TSP问题的经典城市数据)。 4.4.1 信息素挥发度的选择设置 按照以上的实验描述，在其他参数不变的情况下，使信息素挥发系数的变化为 。信息素挥发系数对性能影响仿真结果如图4.2~4.6和表4.1所示: ,,0.1,0.3,0.5,0.7,0.9,, (1)=2，=5，=0.1，NcMax=10 ,,, 图 4.2 选择不同信息素挥发度结果图1 ,,(2)=2，,=5，=0.3，NcMax=10 - 18 - 机器学习(论文) 图 4.3选择不同信息素挥发度结果图2 (3)=2，=5，=0.5，NcMax=10 ,,, 图 4.4选择不同信息素挥发度结果图3 ,(4),=2，=5，=0.7，NcMax=10 , - 19 - 李亚龙 E201102016 图 4.5选择不同信息素挥发度结果图4 (5)=2，=5，=0.9，NcMax=10 ,,, 图 4.6选择不同信息素挥发度结果图5 表4.1 信息素挥发度对算法性能的影响 挥发系数 最优路径长度 搜索循环次数 0.1 581.651 10 0.3 599.786 10 0.5 610.637 10 0.7 600.225 10 0.9 599.741 10 - 20 - 机器学习(论文) 由仿真实验不难看出，在其他参数相同的情况下，信息素挥发度ρ的大小对蚁群算法的收敛性能影响极大，特别是当ρ很小时，由于路径上的残留信息占主导地位，信息正反馈的作用相对较强，搜索的随机性减落，因而蚁群算法的收敛速度加快;而在ρ比较大时，由于信息正反馈的作用占主导地位，搜索的随机性增强，全局搜索能力增强，但收敛速度太慢。因而关于蚁群算法的信息素挥发度ρ的选择，必须综合全局搜索能力和收敛速度两项性能指标，由图可知在，算法的性能比较稳定和一致，搜索的全,,0.1 局性和收敛速度比较好。 4.4.2 启发式因子的选择设置 关于蚁群算法中启发式因子α及β对算法性能的影响及其在实际应用中的选择，也可以通过计算机仿真实验来分析和确定。在其它参数不变的情况下，取启发式因子α和β不同数值的组合。启发式因子α和β对算法性能影响的仿真结果如图4.7~4.13和表4.2所示。 (1)=0.1，=0.5，=0.1，NcMax=10 ,,, 图 4.7 选择不同启发式因子结果图1 ,(2)=0.1，=1，=0.1，NcMax=10 ,, - 21 - 李亚龙 E201102016 图 4.8 选择不同启发式因子结果图2 (3)=0.2，=2，=0.1，NcMax=10 ,,, 图 4.9 选择不同启发式因子结果图3 ,(4),=0.3，=3，=0.1，NcMax=10 , - 22 - 机器学习(论文) 图 4.10 选择不同启发式因子结果图4 (5)=1.0，=4，=0.1，NcMax=10 ,,, 图 4.11 选择不同启发式因子结果图5 ,(6),=5.0，=8，=0.1，NcMax=10 , - 23 - 李亚龙 E201102016 图 4.12 选择不同启发式因子结果图6 (7)=10.0，=10，=0.1，NcMax=10 ,,, 图 4.13 选择不同启发式因子结果图7 表4.2 启发式因子α和β的不同组合对算法性能的影响 α β 最优路径长度 搜索循环次数 0.1 0.5 589.779 10 0.1 1 607.497 10 0.2 2 584.608 10 0.3 3 588.935 10 1.0 4 603.768 10 5.0 8 589.151 10 10.0 10 595.219 10 从仿真实验不难看出，蚁群算法中启发式因子α及β的不同选取对算法性能有极大的 - 24 - 机器学习(论文) 影响:差的搜索结果且出现过早停滞(α及β均过大时);对于过大的α值，相当于给予路径上的信息素在蚂蚁的搜索过程中的重要性给予充分的重视，蚂蚁完全依赖信息素的引,,ijij导进行搜索，如果此时期望信息的启发式因子β相对比较大，则将导致局部最优路径上,ij 的信息正反馈作用极强，算法必然会出现过早收敛的现象。当问题规模较大时，在这种情况下所搜索到的通常是局部最优解。差的搜索结果但不出现过早停滞(α和β均过小时):对于过小的α值，相当于对路径上的信息素在蚂蚁的搜索过程中的重要性未予足够重视，,ij 蚂蚁完全依赖期望信息的引导进行搜索，如果此时期望信息的启发式因子β相对也较,,ijij 小，则将导致蚁群陷入了纯粹的、无休止的随机索中(即不停滞)，在这种情况下所进行的搜索一般也很难找到最优解。在本问题中，β取2左右，α取0.1到0.3之间的值为宜，蚁群算法均能获得较好的搜索结果，并且性能非常接近。 - 25 - 李亚龙 E201102016 结论与展望

工作总结

关于社区教育工作总结关于年中工作总结关于校园安全工作总结关于校园安全工作总结关于意识形态工作总结

蚁群算法解决TSP问题只是解决了众多组合优化问题的一种，但就是围绕着TSP问题的解决才有了蚁群算法的发展和创新。它涉及了仿生学，程序设计学，计算机科学仿真技术多个学科，是信息处理领域的一项前沿技术。本文的前期工作是介绍了基本蚁群算法的原理和蚁群算法的机制原则，其中也详细介绍了组合优化问题。 本文的重点是利用蚁群算法解决TSP问题，并利用Microsoft Visual Studio 2008成功进行了仿真。其中重点讨论了如何通过选择合理的参数配置使蚁群算法性能得到提高，并用大量的仿真实验结果予以证明。 总的来说，本文有两个难点，基本蚁群算法原理的理解，与利用Microsoft Visual Studio 2008进行仿真实验解决TSP问题。 技术展望 蚁群算法发展至今，人们已经针对不同的具体问题提出了许多不同类型的改进蚁群算法模型，但这些改进的蚁群算法模型往往普适性不强，同时基本蚁群算法模型也不能直接应用于解决所有的优化问题。另外，自然界中的真实蚁群还有许多其他的智能行为，用逆向思维和发散思维开发不同的蚂群算法模型是一条新的发展思路。基于此，今后可以从以下几个方面对其模型进行改进。 1、设计一种通用的蚁群算法普适性模型。 2、进一步研究自然蚁群行为，提出更加智能化的蚁群混合行为模型。 3、摆脱传统模型框架，开发新的蚁群算法模型。 因此，关于蚁群算法理论及其应用的研究必将是一个长期的研究课题。相信随着人们对仿生智能系统理论及应用研究的不断深入，蚁群算法这一新兴的仿生优化算法必将展现出更加广阔、更加引人注目的发展前景。 - 26 -