大学科研成果论文(9)

《大学科研成果论文(9)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、FUJIANAGRICULTUREANDFORESTRYUNIVERSITY科研成果论文论文题目:蚁群效应及其应用学院：计算机与信息学院专业年级：电子信息工程2010级学号：姓名：指导教师、职称：2012年11月15曰蚁群效应及其应用摘要：蚁群效应：减掉工作流程中的多馀。蚂蚁的组织与分工合作能力一直是人类学习的对象，因此对蚁群的研宂和学d有助于提高人们的工作效率。关键词：蚁群效应；效率；组织；管理-V什么是蚁群效应蚂蚁的世界一直为人类学与社会学者所关注，它们的组织体系和快速灵活的运转能力始终是人类学习的楷

2、模。蚂蚁有严格的组织分工和由此形成的组织框架，而它们的组织框架在具体的工作情景中有相当大的弹性，比如它们在工作场合的自我组织能力特别强，不耑要任何监督就可以形成一个很好的团队而有条不紊地完成工作任务。蚁群效应是人们从蚂蚁群体的组织和分工中总结岀来的灵活的组织建设和运转方式。蚂蚁有严格的组织分工，但它们的分工能够迅速根据环境作出调整。比如，蚂蚁发现食物后，如果有两只蚂蚁，它们会分别走两条路线冋到巢穴，边走边释放出一种它们自己才能识别的激素做记号，先冋到巢穴者会释放更重的气味，这样同伴就会走最近的路线去搬运食

3、物。一只蚂蚁搬食物往冋走时，碰到下一只蚂蚁，会把食物交给它，自己再回头；碰到上游的蚂蚁时，将食物接过来，再交给下一只蚂蚁。这种充满弹性、以“效率”为中心的组织和分工就是蚁群效应。1.1蚁群工作方式蚂蚁做事很讲宄流程，但它们对流程的认识是直接指向于工作效率的。比如，蚂蚁发现食物后，如果有两只蚂蚁，它们会分别走两条路线回到巢穴，边走边释放出一种它们自己才能识别的激素做记号，先回到巢穴者会释放吏重的气味，这样同伴就会走最近的路线去搬运食物。1.2蚁群工作特点蚂蚁做事有分工，但它们的分工是有弹性的。一只蚂蚁搬食物

4、往冋走时，碰到下一只蚂蚁，会把食物交给它，自己再冋头；碰到上游的蚂蚁时，将食物接过来，再交给下一只蚂蚁。蚂蚁要在哪个位置换手不一定，惟一固定的是起始点和0的地。二、蚁群算法的TSP问题求解2.1TSP问题旅行商问题是个著名的NP问题:一个商人要到若干城市推销物品，从1个城市出发，要到达其他各城市一次，而且最多一次，最后又回到第一个城市，寻找一条最短路径!4=（111，112，113,..上11）,使得下列目标函数最小：/(/)=d(h2為+1)Wd>1）上式屮hi为城市号（值为1至卟之间的自然数），d（

5、hi，hj）表不城市i和城市j之间的距离。若把每个城市看成是图上的节点，则TSP问题就是在有n个节点的完全图上寻找一条花费最少的哈密顿回路2.2蚁群算法(ACA)模型我们用求解平面上n个城市的TSP问题来说明蚁群算法模型。假如将m只蚂蚁放到给定的n个城市中，构造一个人工的蚁群系统，其中每只蚂蚁的行动应当符合下述要求：1)每只蚂蚁根据路径上的生物信息素的浓度，以一定概率来选取下一个城市；2)蚂蚁不能在本次遍历中选取已走过的城市作为下一个城市;3)蚂蚁完成一个遍历后，就更新蚂蚁所经过路径上的信息素浓度。蚂蚁选

6、择下一个城市的概率主要是以下两点来决定：(1)Tij(t)是指在t时刻城市i和城市j之间的路径上生物信息素浓度；当然初始时，各条路径上的生物信息素浓度是相同的，设Tij(O)=c(C为常数)，用来模拟真实蚂蚁的生物信息素。(2)r)ij是指蚂蚁从城市i转移到城市j的启发信息，这个启发信息是根裾具体问题给出的，比如：TSP问题中一般取nij=ioo/dij(dij—般指城市ij之间的距离)。这样，t时刻位于城市i的蚂蚁k选择城市j为下一城市的概率的计算公式如公式2所示：(2)其屮：(X是信息素因子，表示路径

7、的相对重要性，反映生物信息素对蚂蚁的移动影响，该伉越大，则该蚂蚁越趋向于选择生物信息素浓度大的路径，蚂蚁之间协作性越卨。p是启发因子，表示启发值的相对性，表明启发信息对蚂蚁选择城市的影响程度，该值越大，则状态转移概率越接近于贪婪规则。allowk=(0,l,2,3，...，n-l)-tablek表示蜗蚁1<下个可以选择的城市。tablek用于记录第k只赐蚁已走过的城市，该表随着算法的进行做动态调整。Pkij(t)是指在t时刻第k只蚂蚁由城市i到城市j的选择儿率。蚂蚁完成所有城市的遍历后，生物信息素按照如公

8、式3的方法来更新：+l

9、=其中：Aiij(t)是蚁群在路径(i,j)上散发信息素之和，定义如公式4:mArv(/)=VAr；k=lq是信息素挥发因子，1-q是生物信息素的留存系数，q的取值范围是0和1之间。2.3实现步骤算法初始时，蚂蚁均匀分布在n个城市屮，从t=0时刻开始搜索，当t=n时全部蚂蚁走完所有的城市，完成第一轮遍历。然后更新路径上的生物信息素，再把禁忌表tablek淸空。然后开始下一轮遍历，在达到设賈的最大遍历次数