《（推荐）数学建模之智能计算》由会员分享，可在线阅读，更多相关《（推荐）数学建模之智能计算（36页珍藏版）》请在金锄头文库上搜索。
1、数学建模之智能计算（2）一、 蚁群算法 蚁群优化算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法.它由意大利学者Marco Dorigo于上世纪九十年大初期最早提出的一种源于大自然的新的仿生类算法，其灵感来源于上述所描述的蚂蚁在寻找食物过程中发现路径的行为.蚁群算法主要是借鉴蚂蚁群体之间的信息传递方法达到寻优的目的，最初有称之为蚁群优化方法，在计算机模拟仿真中由于采用了人工“蚂蚁”的概念，因此，也称蚂蚁系统（Ant System.AS）。主要讨论内容 蚁群算法基本原理 蚁群算法模型的建立 蚁群算法研究进展 基于蚁群算法的T
2、SP求解 一个实例 蚁群算法的收敛性讨论 一、基本原理1、 从真实蚂蚁到人工蚂蚁蚁群算法是一种受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。其基本原理如下图：图1 蚁群觅食路线上图表示蚂蚁觅食的线路，为蚁穴 , 为食源，从到有两条线路可走，是长路径，是短路径。蚂蚁走过一条路线以后，在地面上会留下信息素气味，后来蚂蚁就是根据留在地面上这种气味的强度选择移动的方向。图表示起始情况，假定蚁穴中有只蚂蚁，分别用表示，为食源。开始时蚁穴中蚂蚁向食源移动，由于路线和上均没有蚂蚁通过，在这两条路线上都没有信息素气味，因此蚂蚁选择这两条线路的机会均等。令蚁选择线路，蚁选择线路，假
3、定蚂蚁移动的速度相同，当蚁到达食源时，蚁还在途中，如图。蚁到达食源以后就返回，这时从返回也有两条线路选择，哪一条线路上信息素的气味重就选择哪一条。因为蚁还在途中，没有到达终点，这时在线路上靠近端处，蚁还没有留下信息素气味，所以蚁返回蚁穴的线路只有一个选择，就是由原路返回。当蚁返回时，蚁开始出发，蚁的线路选择必定是，因为这时上气味浓度比上重 (上已有蚂蚁两次通过 ) ，如图所示。当蚁到达食源时 ,蚁返回线路必然选择，如图所示。如此继续下去 ，沿线路上移动的蚂蚁越来越多，这就是巢穴到食源的最短路线，蚂蚁根据线路上留下信息素浓度的大小，确定在路线上移动的方向，蚁群向信息素浓度重的线路集聚的现象称为正
4、反馈。蚂蚁算法正是基于正反馈原理的启发式算法。蚁群觅食过程中的简单规则每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？下面详细说明：1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的
5、蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。4、移动规则： 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰
6、动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 7、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素
7、的存在，进而根据信息素的指引找到了食物。蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于上述所描述的蚂蚁在寻找食物过程中发现路径的行为。其中“信息素”在蚁群算法中期到非常重要的启示作用。 1 Colorni A, Dorigo M, Maniezzo V, etal. Distributed optimization by ant colonies . Proceedings of the 1st European Conference on
8、Artifical Life, 1991,134-1422 Dorigo M. Optimzation,learning and natural algorithms.Ph.D.Thesis, Department of Electronics, Politenico diMilano,Italy,1992 在蚁群算法中，需要定义人工蚂蚁的概念，人工蚂蚁具有双重特性，首先，它们是真实马一行维特征的一种抽象，通过对真实蚂蚁行为的观察，将蚁群行为中的智能化因素赋予人工蚂蚁；另一方面，为了解决实际问题，人工蚂蚁必须具备真实蚂蚁一些所不具备的特性。归纳起来看，它与真实蚂蚁之间主要存在下列异同 二、人工
9、蚁与真实蚁的共同特征比较1、 人工蚁与真实蚁一样，都是一个需要合作的群体问题的解决需要通过人工蚁的合作来完成，人工蚁群通过相互协调与合作从而有可能找到全局最优方案，而每只人工蚁的单独行动只可能找到局部最优解2、 人工蚁和真实蚁一样，都要完成一个共同的任务 人工蚁与真实蚁一样，都要完成一个共同的任务，即需寻找一个从源节点（巢穴）到目的节点（食物源）之间的最短路经（或最小代价），人工蚂蚁与真实蚂蚁一样都不能跳跃，必须在相邻节点之间移动，直至遍历所有可能路径，为了减少计算复杂度并寻找出最短路径，需要记录当前路径3、 人工蚁与真实蚁一样都通过使用信息素进行间接通信人工蚁与真实蚁一样都存在一种改变当前所
10、处环境的机制：真实蚂蚁在经过的路径上留下信息素，人工蚁则不断修改更新在其所经过的路径上存储的信息，是一种模拟自然界中的信息素轨迹更新的过程4、 人工蚁利用真实蚁觅食行为中的自催化机制正反馈 当一些路径上通过的蚂蚁越来越多时，路径上留下的信息素轨迹也越来越多，使得信息素强度变大，根据蚂蚁清倾向于选择信息强度大的特点，后来的蚂蚁选择该路经的概率也越高，从而增加了该路经的信息素强度，这称之为自催化过程 自催化机制利用信息素作为反馈，通过对系统演化过程中较优解的增强作用，使得问题的解向着全局最优的方向逐步接近5、 信息素的挥发机制在蚁群算法中设置一种挥发机制，类似于真实信息素的挥发，这种机制需要蚂蚁忘
11、记过去，不受过去经验的过分约束，有利于指引蚂蚁朝着新的方向搜索，避免早熟收敛6、 利用当前信息进行路径选择的随机选择策略 人工蚁于真实蚁都是利用概率选择策略实现一个节点到相邻节点的移动，选择策略只利用当前的信息去预测未来的情况，而不能利用未来的信息，因此，人工蚁与真实蚁所使用的选择策略在时间和空间上都具有局部特性 人工蚁具备一些真实蚁所不具备的特征，主要体现在下列五个方面1、 人工蚁存在于离散空间中，它们的移动实质上是有一个离散状态到另一个离散状态的转移；2、 人工蚁具有一个记录其过去自身行为的内在状态；3、 人工蚁存在于与时间无关联的环境之中人工蚁并非完全盲从，它受到问题特征的启发，例如，有
12、的问题中人工蚂蚁产生一个解后改变信息量，而在有的问题中人工蚂蚁每做一次选择便改变信息量 5、为了提升人工蚁系统的性能，改进算法效率，人工蚁可增加一些性能，如预测未来、局部优化、回溯等。在很多具体应用中，人工蚁可以在局部优化的过程中交换信息以及实行简单预测等。三、基本蚁群算法模型的建立1、蚂蚁个体的抽象 抽象出能够为建立模型起作用的真实蚁群的机理，摒弃与建立模型算法无关的因素.2、问题空间的描述蚂蚁轨迹可以看成为二维平面上的活动，其活动过程为一个状态到另一个状态的迁移，因此，利用蚁群算法求解的问题其数学模型采用图论语言来描述就显得非常自然，另一方面，在实际问题中的许多应用问题可以通过图的语言来描
13、述，这就使得蚁群算法的广泛应用成为可能.3、寻找路径的抽象把真实蚂蚁的觅食过程抽象成算法中解的构造过程，将信息素抽象成存在于图边上的轨迹，信息素的大小可以通过设置权重来体现，并根据权重的值决定走向下一个节点的概率.用任何两个节点分别表示蚂蚁的巢穴（初始节点）和食物源（终止节点），人工蚂蚁按照一定的状态转移概率从初始节点移动到邻近的节点，以此类推，最终选择行走到目标节点，从而得到问题的一个可行解.4、信息素挥发的抽象自然界中真实蚂蚁在所经过的路径上会连续不断的留下信息素，而信息素也会随着时间的推移连续不断的挥发，在人工蚁群算法中，蚂蚁完成从某一节点到相邻节点的一次移动后（相应于经过一个时间单位）
14、，进行一次信息素挥发，这有利于避免陷入局部最优的陷阱.5、启发因子的引入为了设计有效的蚁群算法，在决定蚂蚁行走方向的状态转移概率时，引入一个随机搜索的过程，即引入一个启发因子，根据所求问题空间的具体特征，给蚁群算法一个初始的引导，从而极大的增加算法的有效性，从而使蚁群算法的有效应用成为可能.为了说明蚂蚁系统模型，下面讨论基于蚁群算法的旅行商问题的解.在模型建立与求解过程中，我们需要首先引入下列符号：用表示时刻位于城市的蚂蚁数目，为蚁群中蚂蚁的总数目，为TSP问题的规模，即城市的个数.显然， ，表示t时刻路径上的信息量，是t时刻集合中元素（城市）两两连接上残留信息量的集合，在初始时刻各路经上的信
15、息量都相等，即设（常数），基本蚁群算法的寻优是通过有向图来实现的.蚂蚁在运动过程中，根据各条路经上留下的信息量决定其转移方向.此处采用禁忌表来记录蚂蚁k当前所走过的城市.集合随着进化过程作动态调整，而用来表示蚂蚁k下一步允许访问的城市位置，显然.若用表示城市和城市之间的距离，则t时刻，图中边反映由城市转移到城市的启发程度，即能见度，可以取为，是一个与时间无关的常数.在搜索过程中，蚂蚁根据各条路经上的信息量以及路径的启发信息（主要是路径长度）来计算状态转移概率，如用表示蚂蚁k在 t时刻由城市转移到城市的状态转移概率，则可以定义 (1)在上式中，与分别反映了路径轨迹与路径能见度的相对重要性. 作为信息启发式因子，反映了蚂蚁在运动过程中所积累的信息在蚂蚁运动时所起的作用，其值越大，则该蚂蚁越倾向于选择其他蚂蚁经过的路径，蚂蚁之间的协作性越强，作为启发式因子，反映了蚂蚁在运动过程中启发因素在选择路径时的受重视程度，其值越大，则该状态转移越接近贪心规则.在两种极端情形：与下，则分别退化为传统的贪心算法与纯粹的正反馈启发式方法.上述状态转移概率的计算用到t时刻各条路经上信息量的计算，下面我们讨论的计算方法.在初始时刻，可以选择（常数），蚂蚁完成一次循环后各
