蚁群算法报告

蚁群算法报告学院:专业:学号:姓名:目录第一部分：蚁群算法原理介绍..................................................................31.1蚁群算法的提出.................................................................................31.2蚁群算法的原理的生物学解释.........................................................31.3蚁群算法的数学模型.........................................................................31.4蚁群算法实现步骤.............................................................................5第二部分：蚁群算法实例--集装箱码头船舶调度模型...........................62.1集装箱码头船舶调度流程图.............................................................62.2算例与MATLAB编程的实现..............................................................62.2.1算法实例........................................................................................62.2.2Matlab编程...................................................................................8第三章：MATLAB优化设计工具箱简介............................................143.1MATLAB优化工具箱.........................................................................143.1.1优化工具箱功能：.....................................................................153.2MATLAB优化设计工具箱中的函数................................................153.2.2方程求解函数.............................................................................153.2.3最小二乘（曲线拟合）函数.....................................................163.2.4使用函数.....................................................................................163.2.5大型方法的演示函数................................................................163.2.6中型方法的延时函数................................................................163.4优化函数简介...................................................................................173.4.1优化工具箱的常用函数................................................................173.4.2函数调用格式.............................................................................173.5模型输入时所需注意的问题...........................................................19第一部分：蚁群算法原理介绍1.1蚁群算法的提出蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现于人类的日常生活环境中。受到自然界中真实蚁群集体行为的启发，意大利学者M.Dorig。于20世纪90年代初，在他的博士论文中首次系统地提出了一种基于蚂蚁种群的新型优化算法—蚁群算法}28}(AntColonyAlgorithm,ACA)，并成功地用于求解旅行商问题，自1996年之后的五年时间里，蚁群算法逐渐引起了世界许多国家研究者的关注，其应用领域得到了迅速拓宽。1.2蚁群算法的原理的生物学解释据观察和研究发现，蚂蚁倾向于朝着信息激素强度高的方向移动。因此蚂蚁的群体行为便表现出了一种信息激素的正反馈现象。当某条路径上经过的蚂蚁越多，该路径上存留的信息激素也就越多，以后就会有更多的蚂蚁选择它。这也就是说，在蚂蚁搜寻食物的过程中，对于较短的路径，在单位时间内经过的蚂蚁数量越多，那么该路径上信息激素强度越高。由于信息激素强度较高，则可以吸引更多的蚂蚁沿相同的路径进行搜索，这又使该路径上的信息激素强度增大。而对于距离较长的路径，由于单位时间内经过的蚂蚁数量较少，该路径上信息激素强度较低，并且随着信息激素的挥发，该路径信息激素强度逐渐减弱，不再吸引蚂蚁沿这条路径运动。蚂蚁个体之间就是通过信息激素的间接通信来相互协作形成正反馈，进行路径的最优选择，从而达到搜索食物的目的。1.3蚁群算法的数学模型将TSP问题(travelingsalesmanproblem)作为实例，简单的TSP描述过程为:假设有n座城，某个旅者自一城开始，依次经过各城市后回到出发远点，问题就是找到一条距离最小的走法。假设bi(t)代表t时位置是i的蚂蚁数量，Ʈij(t)代表t时路线((i,j)的所包含的信息量，n代表TSP问题的大小，m则代表蚁群中所有蚂蚁数,那么1()nitmbt;{|,}ijiiccC则为t时C集合里元素(城市)相互连接lij上的遗存的信息数量的合集。在开始时各路线上的信息数量相等，假设Ʈij(0)=const，最基本的蚁群算法求解最优是经有向的图断(C,L,)来达到的。蚂蚁k(k=1,2,...m)，运动的过程中，其转移方向是依据每条路线上的信息数量。我们利用禁忌表tabuk(k=1,2,...,m)来代表蚂蚁k已经经过的城市，随着tabuk进化过程变化，集合也做出动态的改变。在蚂蚁搜索前进的过程，依据各路线上包含的信息以及路线下的启发式信息，用来算出状态转移下的概率。()kijPt代表t时下蚂蚁k经城市i运动到城市j时的状态转移下的概率。k0()()()jallowed()()kkijikijijiksallowedttPttt否则若(1)式（1）中，allowedk=C-tabuk代表k蚂蚁要到下一个城市时允许选择的元素;α代表信息的启发式的因素，代表运动路线的重要程度，代表了蚂蚁不断地运动积累信息，在后续的蚂蚁移动过程中的作用，它数值较大，说明这个蚂蚁容易于选择别的蚂蚁所走过的路线，这些蚂蚁的协作运动越强;β代表的是期望的启发因素，代表清晰度下的比较的重要程度，反映了蚂蚁在移动中累计的启发式的信息，代表这个蚂蚁在选择路线过程中的重要性，它的数值大，那么这种状态的转移概率，比较与贪心规则相近似；ηik(t)代表是启发式函数:ikij1t=d（）（2）式(2)中，dij代表的是邻近两个元素之间距离，对于蚂蚁来说，dij值越小，那么nik(t)值就越大，()kijPt值也越大。显然，这个启发式的函数代表的是蚂蚁自城市i到城市j的期望度。如果残留的信息素太多，要使残留的信息素不掩盖启发式的信息，当这个蚂蚁完成一个元素或走完n个所有的城市，也就是说蚂蚁一个旅程完成，需要更新残留的信息。这是仿效人类的大脑记忆下的特点提出的信息更新的模式，也就是说我们的大脑存储的新信息后，原先存储的旧的信息会伴随时间的推进，不断被我们逐渐的淡化，到最后甚至是忘记。因此，t+n时在路线((i,j)的信息调整规则如下:()(1)()()ijijijtntt(3)1()()mkijijktt(4)式(4.3)中,ρ系数代表的是信息挥发，那么1-ρ因子代表的是信息的残留，为避免信息的过多累积，ρ系数的取值的范围:0,1;()ijt代表这次循环过程中路线(i,j)上信息的增加数量，原先的时间(0)0ij,1()mkijkt代表的是k蚂蚁，它旅行过程中在路线(i,j)上的留存下来的信息。不同的信息更新的模式下，有不同的三种模型，对整体的信息而言，也就是蚂蚁走完一个循环后所有路线上的信息的更新，选择求TSP时较为准确的模型，于是，选择ant-cycle模型:,()0,K(i,j)kKijQLt若第只蚂蚁在本次循环中经过否则式(4.5)中Q代表信息素的强度，此强度在一定范围内影响的是算法收敛快慢,Lk代表蚂蚁在这次旅程中所走路线的总长度。1.4蚁群算法实现步骤以TSP为例，蚁群算法的具体实现步骤如下:1)初始化各参数:令Ʈij(0)=C(C为常数)，ΔƮij=0,迭代次数IT=0,最大迭代次数为IT_M，计时器t=0，设置α,β,ρ,Q的值，将m只蚂蚁随机放在n个城市上，把蚂蚁k(k=1,2,...，m)。目前所处城市设为禁忌表Tk的第一个元素;2)开始循环，蚂蚁k(k=1,2,...,m)根据式((3-2)状态转移概率选择下一城市，并将选择过的城市j加入到禁忌表Tk，直到禁忌表中包含所有城市n;3)计算蚂蚁k(k=1,2,...,m)遍历所有城市的总路径长度Lk，比较所有蚂蚁找到的路径，选择一条最短路径，根据特定的公式更新路径上的信息素浓度;4)重新迭代，IT=IT+1;5)判断是否满足条件:判断迭代次数IT_ITM且所有蚂蚁选择同一条路径。满足的话输出最短路径，否则清空禁忌表Tk，跳转到步骤2);6)得到结果，程序结束。流程图如下：开始初始化各参数：IT=0，t=0各路径上的信息素为0，设置α,β,ρ,Q，将m只蚂蚁放在n座城市上IT³IT_M根据公式求出蚂蚁K状态转移概率选择下一个城市，并将选择的城市加入禁忌表TK中禁忌表包含所有城市？计算选择出蚂蚁走过的而一条最佳路径，根据公式更新路径上的信息素浓度，保留禁忌表中的第一个元素，清空其他元素，IT=IT+1输出结果，得到最短路径NYYN结束第二部分：蚁群算法实例--集装箱码头船舶调度模型2.1集装箱码头船舶调度流程图程序开始1.计算俩个船舶之间的时间间隔2.初始化信息素3.设置相关参数和变量设置迭代次数IT_COUNT=0设置蚂蚁计数Ant-count=0为当前蚂蚁随机分配出发的泊位蚂蚁按照某种规则选择船舶当蚂蚁走过船舶数量计算蚂蚁走过的路径，更新信息素IT_COUNT=迭代次数输出最优路径程序结束NN图2.1集装箱码头船舶调度流程图2.2算例与matlab编程的实现2.2.1算法实例设定种群大小N=5,船舶数量vesselNumber=8，泊位数量berthNumber=3,每个泊位上有3台岸桥，岸桥的平均卸货速度为35箱/小时，蚁群算法中α=1，β=2.5，ρ=0.85，COUNTmax=20通过MATLAB编程实现以下:Step1蚁群初始化，设时间的计数器t=0，初始迭代的次数ITCOUNT=