打孔机生产效能的提高(1)

1、2012年“深圳杯”全国大学生数学建模夏令营承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： D 我们的参赛报名号为（如果赛

2、区设置报名号的话）： 所属学校（请填写完整的全名）： 天津农学院 参赛队员 (打印并签名) ：1. 王柔玉 2. 张润芳 3. 刘东洋 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2012年“深圳杯”全国大学生数学建模夏令营编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：打孔机生产效能的提高摘 要过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的

3、30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。因此提高打孔机的生产效能是降低印刷线路板成本的最主要途径。本文通过实现刀具转换最优顺序的前提下，运用蚁群算法找到最优线路，及最短距离。使行进成本和刀具转换成本均达到最低，以此减少打孔机总打孔成本。问题一：单钻头进行作业时，首先根据钻头上各个刀具的分布，结合各孔型对刀具的具体要求，经过分析找到了刀具转换次数最少并能完成各孔型对刀具加工次序特殊要求的换刀顺序：d-c-b-a-h-g-f-e-c。然后运用蚁群算法，在整个区域内分别计算出十种孔型的最优路线和最短路径，再分别计算行进时间，及作业成本。然后与刀具转换时间和成本及两孔型之间钻头

4、移动时间和成本进行汇总分析，所得最后数值则为所求。其具体对过孔加工顺序按蚁群算法得出的加工顺序进行。问题二：双钻头作业时，由于两个钻头独立工作，两个钻头可以同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。但为了避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm，为保证这一要求本文将整个电路板按过孔分布的密集程度划分为四个区域，首先让两个钻头在一、四两个对角线区域内单独工作，加工完毕后在分别转向三、二两个区域。换刀方案保持不变，仍然利用蚁群算法找出各个区域内的最优路径和最短路线，再分别计算出行进时间，行进成本。最后将四个区域的总时间、总成本进行汇总得出结果即为

5、问题二的结果。其具体对过孔加工顺序一就按蚁群算法对个区域所得出的加工顺序进行。将问题一的结果与问题二的行进成本、换刀成本、行进时间、换刀总时间进行比较分析，计算出生产效能不同。同时结合问题一、问题二的结果分析打孔机的两钻头合作间距对作业路线和生产效能产生的影响。最后根据遗传算法对整个计算进行检验、分析及总结。关键字： 最优刀具转换 蚁群算法 遗传算法 生产效能提高一、问题的提出及研究意义 1.1 问题背景过孔是印刷线路板（也称为印刷电路板）的重要组成部分之一，过孔的加工费用通常占制板费用的30%到40%，打孔机主要用于在制造印刷线路板流程中的打孔作业。一般打孔机上有8种刀具，a，b，c，d，e

6、，f，g，h，依次排列呈圆环状，如图1所示： bcdefgha图1：某种钻头上8种刀具的分布情况而且8种刀具的顺序固定，不能调换。在加工作业时，一种刀具使用完毕后，可以转换使用另一种刀具。相邻两刀具的转换时间是18 s，例如，由刀具a转换到刀具b所用的时间是18s，其他情况以此类推。作业时，可以采用顺时针旋转的方式转换刀具，例如，从刀具a转换到刀具b；也可以采用逆时针的方式转换刀具，例如，从刀具a转换到刀具h。将任一刀具转换至其它刀具处，所需时间是相应转换时间的累加，例如，从刀具a转换到刀具c，所需的时间是36s（采用顺时针方式）。为了简化问题，假定钻头的行进速度是相同的，为180 mm/s，

7、行进成本为0.06元/mm，刀具转换的时间成本为7元/min。刀具在行进过程中可以同时进行刀具转换，但相应费用不减。而孔的类型对刀具具有一定的要求，不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，有的孔型需要多种刀具及规定的加工次序来完成，如孔型C需要刀具a和刀具c，且加工次序为a，c。表1列出了10种孔型所需加工刀具及加工次序（标*者表示该孔型对刀具加工次序没有限制）。表1：10种孔型所需加工刀具及加工次序孔型ABCDEFGHIJ所需刀具aba, cd, e*c, fg, h*d, g, fhe, cf, c一块线路板上的过孔全部加工完成后，再制作另一线路板。但在同一线路板上的过孔不要

8、求加工完毕一个孔，再加工另一个孔，即对于须用两种或两种以上刀具加工的过孔，只要保证所需刀具加工次序正确即可为提高打孔机效能，现在设计一种双钻头的打孔机（每个钻头的形状与单钻头相同），两钻头可以同时作业，且作业是独立的，即可以两个钻头同时进行打孔，也可以一个钻头打孔，另一个钻头行进或转换刀具。为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm（称为两钻头合作间距）。为使问题简化，可以将钻头看作质点。1.2 需要解决的问题1.2.1 单钻头作业给出单钻头作业的最优作业线路（包括刀具转换方案）、行进时间和作业成本。1.2.2针对附件1的数据，给出双钻头作业时的最优作业线路、

9、行进时间和作业成本，并与传统单钻头打孔机进行比较，其生产效能提高多少。1.2.3研究打孔机的两钻头合作间距对作业路线和生产效能产生的影响。1.3研究意义过孔的加工费用通常占制板费用的30%到40%。提高打孔机的生产效能对降低印刷线路板成本起着至关重要的作用。二、问题分析打孔机的生产效能主要取决于以下几方面：（1）单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假定对于同一孔型钻孔作业时间都是相同的。（2）打孔机在加工作业时，钻头的行进时间。（3）针对不同孔型加工作业时，刀具的转换时间。问题一分析：本题要求提高打孔机在传统单钻头作业时的工作效能，即降低刀具转换成本和钻头行进成本。由

10、于不同的刀具加工不同的孔型，有的孔型只需一种刀具来完成，有的孔型需要多种刀具及规定的加工次序来完成，本题中有8种刀具，相比较于孔的两千多坐标来说，确定刀具的转换顺序比较简单，所以应先确定刀具的最短转换顺序，再运用模型计算出最有路径和最短路线。打孔机是打完一个电板之后再按照原来的最优线路进行下一个电板，所以在打完一个电板的最后一个点之后，钻头应回到起始点，对于每种刀具而言，每个孔型的每个坐标只需加工一次，然后返回到出发点即可。根据以上分析，该问题与旅行商问题相似，可以采用蚁群算法、遗传算法和模拟退火算法进行求解。由于本题的数据比较小，而蚁群算法又具有局部搜索速度快、收敛性良好的优点，所以本文采用

11、蚁群算法对本问题的最优线路和最短路径进行求解，用遗传算法对蚁群算法进行优化和检验。问题二分析：在双钻头作业时，两个钻头独立工作，且为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm，所以考虑将一块电路板根据孔的密集程度划分出四个不同的区域：一区（x<0,y>4x105），二区（x>0,y>4x105），三区（x<0,y<4x105），四区（x>0,y<4x105）(单位：1/100mil)。如图四。第一个钻头工作路线为先打一区再换到三区工作，第二个钻头先打四区再打二区，使两个钻头的距离始终保持大于等于3cm。每个区域的刀

12、具转换顺序与问题一相同，一就运用蚁群算法分别计算出各个区域的最短路线和最优路径，再根据已知的钻头行进速度180mm/s和换刀时间计算出总的时间及成本。三、模型的基本假设1、单个过孔的钻孔作业时间，这是由生产工艺决定，为了简化问题，这里假设对于同一孔型钻孔作业时间都是相同的。2、在计算两孔之间距离时，为了简化问题，这里假设打孔机的钻头看作一个质点。3、为了计算行进费用，需要计算行进时间，为了简化问题，这里假设打孔机的行进是一个匀速运动。四、符号定义和说明五、模型建立与求解根据以上对问题的分析，打孔机的生产效能主要取决于钻头的行进时间和刀具转换时间，加工总费用=刀具行进费用+刀具转换费用。对此，我

13、们建立优化模型单钻头工作时刀具转换顺序为：d-c-b-a-h-g-f-e-c，成本为： 钻头运行成本的计算运用基于蚁群算法。5.1问题一模型的建立与求解5.1.1.模型原理 研究表明,蚂蚁具有找到蚁巢与食物之间最短路径的能力。这种能力是靠其在所经过的路径上留下一种挥发性分泌物pheromone (称为信息素,该物质随着时间的推移会逐渐挥发消失)来实现的。蚂蚁在一条路上前进时，会留下挥发性信息素，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比.。对于一条路径,选择它的蚂蚁越多，则在该路径上蚂蚁所留下的信息素的强度就越大，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈。通过这种

14、正反馈，蚂蚁最终可以发现最短路径。5.1.2蚁群系统模型为模拟蚁群系统的寻径方法,我们定义如下参数:蚁群中蚂蚁的数量；:路径的能见度；:时刻在路径上的信息量；为:蚂蚁在本次循环中留在路径上的信息量；:蚂蚁在时刻由位置转移到位置的概率；:轨迹的相对重要性；:能见度的相对重要性；:信息素的持久性,表示信息素的衰减度. 初始时刻,设所有路径上的信息素都相等，(是一个常数) . 蚂蚁在运动过程中, 根据各条路径上的信息素的大小以一定的概率决定转移方向, 表示为:其中是常数,表示蚂蚁循环一周所释放的总信息量.表示第只蚂蚁在本次循环中所走路径的长度,它体现了全局范围内的最短路径,能够提高系统搜索的收敛速度

15、. 参数、可以用实验方法确定其最优组合.停止条件可以用固定循环次数或者当进化趋势不明显时便停止计算. . 5.1.2模型的建立对于钻头的行进费用：其中，当表示在得到的最优路径上；当表示不在得到的最优路径上。问题一中确定刀具转换顺序为d-c-b-a-h-g-f-e-c,然后每个刀具将需要打的点操作完毕后再转换到下一个刀具，如d刀具，需要打D、G两类孔型，将这两类的点的坐标集合在一起，然后放入蚁群算法中的城市坐标，在matlab中运行得出最优路径和最短路线，然后转换到c刀具进行相同的操作，然后依次按刀具运行。对于转换刀具时从一类刀具打出的最后一个点与下一个刀具的第一个点的距离，同样利用运用公式进行

16、计算。5.1.3 模型的求解由于需要打的孔的数量相对较多，不能想像点的整个分布情况，所以先运用matlab软件做出散点图分析点的分布，如图2将各种刀具所需坐标点集合后导入到蚁群算法代码中，计算出最优路线和最短路径。运行后的结果为（由于数据较多，故以b、c刀具为例）。 图2 b刀具最短路径优化结果 图3 b刀具平均路径与最短路径图4 c刀具最短路径优化结果 图5 b刀具平均路径与最短路径表1：最终最短路径运行结果（单位：1/100mil）刀具dcbah最短路线6.0092e+0063.8716e+0061.1399e+0071.2039e+0073.1221e+006刀具gfec最短路线3.25

17、45e+0066.8748e+0066.0012e+0068.9880e+006 表2：c刀具打孔顺序（表中数字为代码中打孔的点坐标的顺序号码）677068366367374303254253252251250249248247239240241242243244245246201316242963034018419319619039419939620020419823838816916316415313714914711111511912312712813213614214414615215114514314113513112412011611214815013815411411812212

18、111711312512613013414013913312933733927427528528429329529829930230137821339921421621037938292969338382877773696132031931831731632232332432532646363328271718165384234158344155343309297300332338217400201218231109106101315255257259261262264263265267269270268266260258256868833614972353851561661571593861

19、602361673463473493483503523543563583603623643653633613593573553533513911721771811782902802892912942762731613871621682372772822923695763626066566559368757678919094837980858481645455523732505158717274899598212398211215209171175390176180342105278287288279711174389170173179341345232931494842454140393822

20、440422723022837037122540322322622927210310499321286283220401232219202333334328331281271304100102105327329335330221402203222233183189195393188475320539720820720637737619439218218718619239519119718525222115941263811101071082192630830730630531031131231338138037537343443534372314表3：b刀具打孔顺序66366212027066

21、467667969670878077078677178277276078378476176278577377476376477575475575675775877327237287397437296896906846826726738182612792937767167065912312212112451324224321767467568673673774473824321141151161171191121961901951941931924124454845045095275595605114964764744854875245254934864714584604654664594534

22、164104304283863853843834074234054084094064545355344724634804734905294424364384374754895283963973983993803813603533263223052782772452302712813153253483173062722692802392192181991861851841871281291301311321261271891884328454423221776768765745727692678677685740741769591622002202212102092052042012032612

23、792822623383373354224214515415965315325304704694684674414404474463883763753873743573473162752462242472252482262492272502282512292522763002942992982973023563553543523513502021481189080463697777796543217151312141654535556578485831521531591511581571561551541491651911401341361461601671641701611471381131

24、331049186141150166197211212273274311310309222223175171174182145144181172178101941029596979899696058212519117817667677357347136976806607872271271070670570370069372641427611144841940437837035936636738237740342441743347747850651451651555456658359057956756256356456559359250548850150250359559451751851948

25、248146451250850739237936228434636539041342542642740039137236434937338939341443545037126023725923623525823425523323223128318317617717918017323866726571626864706374343531103848308751742730888913710010512513511010614214310710810910373678775313932340240143944445651049949850057055252152049455855758158058

26、661258454958557657758252352249541843442046147949753353653753853952655356157236835833631932132046269869966943232775653701198411555474577255402630473179328431667668665666681702688683492442562402572412532642662672902962912922892932681691682953343443333433323423313413303403293392852652632862872883454525

27、566016166176145985885976066136156086035895715876216266396466576546556436306256276336286346296356316246206106006025995745755455465515505445434494294153953943613693634554436456446476526616406236196096426416486506516586566386326226186116045915785693183243123032542132062142072152082163013083133073145239

28、3318748747749750746778203751504075975268757356848354260749149260572470970469569171178778873363663754754816370764969429720721714717718719716715根据以上运行结果，又知，计算得：运行成本为元总成本元行进时间=996.2255/0.06/180=86.43197,换刀时间为18*9=162s,总时间=86.43197+162=248.432s5.2 问题二模型的建立与求解5.2.1 模型的建立 设计双钻头打孔机，两钻头可以同时作业并且两钻头作业相互独立，要使印

29、刷线路板的过孔的总费用最小，与第一个问题模型相同，只要使两个钻头行进费用、作业费用之和最小，则为最优作业方案。若钻头1打孔时钻头2打孔，记孔与孔之间的距离为5.2.1 模型的求解由于两个钻头工作是相互独立的，且合作间距不小于3cm。因此在解决双钻头最优作业方案时，我们在单钻头作业的基础上，根据点的密集程度将整个电板划分为四个区域 ，如图6图6 电路板四个区域 根据图四可知过孔没有分布在分界线上，并且一区到三区最近的点和四区到二区的最近的点的距离大于3cm，所以，人工控制钻头1在一区工作的同时，钻头2在其对角区域四区进行打孔，以保证两个钻头的距离不小于3cm。当钻头1在一区工作完毕开始进入三区，

30、钻头2在四区工作完毕后进入二区，使两钻头依旧在对角进行工作。将附件1中的点通过matlab进行编程筛选，将每个区域的点单独存放，同样运用和问题一相同的蚁群算法分别运行出各个区域的最优路线，最短路径，最后计算出钻头1和钻头2总的运行成本，并求出各自的时间，较大的那个即为最终的运行时间。运行结如下：表4：一区运行最短路线刀具dcbah最短路线961270125350021691001988100643380刀具gfec最短路线017039009426402084600表5：二区运行最短路线刀具dcbah最短路线1839200111440020758002765600873430刀具gfec最短路线

31、78808021344022550002677600表6：三区运行最短路线刀具dcbah最短路线169420088388045123003727100887980刀具gfec最短路线374820146160014170001932600表7：四区运行最短路线刀具dcbah最短路线1480500127350027444003933400708650刀具gfec最短路线392010189500015097002121900运用excel进行成本的运算，结果如下表（除去换区所用的刀具转换时间、成本及换区行进成本、时间）。区域行进成本换刀成本行进时间换刀时间成本合计时间合计三区280.007818.9

32、25.92665162305.9344187.9266一区213.46718.919.76547162232.367181.7655钻头1493.474837.845.69211324538.3014369.6921二区255.647918.923.6711162274.5479185.6711四区262.615918.924.31629162281.5159186.3163钻头2518.263837.847.98739324556.0638371.9874合计1011.73975.693.67956481094.365371.9874换区距离：类型距离类型距离一区到二区336442.2三区到

33、一区121285.8一区到三区419054.3三区到二区895228.7一区到四区431537.7三区到四区338306.9二区到一区665767.5四区到一区385366.5二区到三区620286.4四区到二区611092.5二区到四区468398.7四区到三区396803.2由上表可以看出，钻头1从三区到一区进行转换，钻头2从二区到四区进行转换的路线最短，距离为589684.5（1/100mil）成本为589684.5x0.00025x0.06=8.986792元，换区时刀具转换成本为2x18/60x7=4.2元所以总成本=1094.365+8.986792+4.2=1107.551792

34、 元。换区行进时间：0.660963 s，换刀时间：36s总时间=371.9874+36+0.660963=408.6484s5.2.3两钻头合作间距对作业路线和生产效能产生的影响通过计算结果显示打孔机的两钻头为避免钻头间的触碰和干扰，在过孔加工的任何时刻必须保持两钻头间距不小于3cm，这一距离对打孔机的作业路线和生产效能起到一点的制约作用。不利于打孔机的最短线路优化，制约钻头走刀路线，增大作业路线行程 ，不能对提高打孔机的生产效能起到一个很好的辅助作用。经过研究及生产实际经验表明，两钻头的最短间距如能小于3cm，将极大优化打孔机的作业线路，提高生产效能。具体数值将结合具体刀具类型做特殊分析，

35、本文暂不做讨论。六、模型的评价与改进 结合本题实际情况，对蚁群模型进行评价并作出改进： 6.1优点 1.根据最优的刀具转换顺序，蚁群算法不仅能够智能的搜索出打孔的最优线路，还能计算出每个刀具运行的最短路径。 2.蚁群算法是一种基于种群的进化算法, 具有本质并行性, 易于并行实现。如在第二问中，双钻头的打孔机两钻头可以同时作业，且作业是独立的。以此来进一步提高打孔机的生产效能。3. 蚁群算法很容易与多种启发式算法结合, 以改善算法的性能。虽然蚁群算法具有很强的全局寻优能力, 在很多领域获得了广泛的应用.6.2缺陷( 1) 与其他的寻优算法相比教, 蚁群算法的搜索时间过长。( 2) 算法开始时,

36、信息素的作用不明显, 需要经过较长的一段时间才会显现出较好路径上的信息素优势。( 3) 蚁群算法的执行过程中容易出现停滞现象,不利于发现更好的解。6.3改进 从本题来看，蚁群算法从在的最大缺点就是在搜索空间和时间性能上的矛盾, 易出现过早收敛于非全局最优解以及计算时间过长，因此，该模型的改进主要是要从其自身算法、遗传算法与聚类思想相结合, 以克服其需要较长的计算时间、收敛速度慢等缺陷。参考文献1 姜启源，邢文训，谢金星，杨顶辉.大学数学实验，北京：清华大学出版社，2005.2杨启帆，何勇，谈之奕. 数学建模竞赛，杭州：浙江大学出版社，2005.3朱道元.数学建模案例精选，北京：科学出版社，20

37、03.4韩中庚.数学建模方法及其应用，北京：高等教育出版社，2005.5肖人彬，陶振武.孔群加工路径规划问题的进化求解 J计算机集成制造系统,2005,11(5)：682689 6王霄PCB 数控钻孔最佳走刀路线的建模与求解J计算机辅助设计与图形学学报,2001,13(7)：590593 7姜昌华,胡幼华一种求解旅行商问题的高效混合遗传算法J计算机工程与应用，2004。40(22)：6770 8丁建立, 陈增强, 袁著祉. 基于自适应蚂蚁算法的动态最优路由选择J. 控制与决策, 2003, 18(6): 7512-753 9田贵超，黎明，韦雪洁.旅行商问题（TSP）的几种求解方法J.计算机仿真

38、，2006.23（8）：153-157. 10李擎，张伟，尹怡欣，等.一种用于最优路径规划的改进遗传算法J. 信息与控制，2006，35（4）：444-447.附录一、蚁群算法%蚁群算法求解TSP问题的matlab程序 clear all close all clc %初始化蚁群 m=630;%蚁群中蚂蚁的数量，当m接近或等于城市个数n时，本算法可以在最少的迭代次数内找到最优解 C=;%城市的坐标矩阵 Nc_max=200;%最大循环次数，即算法迭代的次数，亦即蚂蚁出动的拨数（每拨蚂蚁的数量当然都是m） alpha=1;%蚂蚁在运动过程中所积累信息（即信息素）在蚂蚁选择路径时的相对重要程度，a

39、lpha过大时，算法迭代到一定代数后将出现停滞现象 beta=5;%启发式因子在蚂蚁选择路径时的相对重要程度 rho=0.5;%0<rho<1,表示路径上信息素的衰减系数（亦称挥发系数、蒸发系数），1-rho表示信息素的持久性系数 Q=100;%蚂蚁释放的信息素量，对本算法的性能影响不大 %变量初始化 n=size(C,1);%表示TSP问题的规模，亦即城市的数量 D=ones(n,n);%表示城市完全地图的赋权邻接矩阵，记录城市之间的距离 for i=1:n for j=1:n if i<j D(i,j)=sqrt(C(i,1)-C(j,1)2+(C(i,2)-C(j,2)

40、2); end D(j,i)=D(i,j); end end eta=1./D;%启发式因子，这里设为城市之间距离的倒数 pheromone=ones(n,n);%信息素矩阵,这里假设任何两个城市之间路径上的初始信息素都为1 tabu_list=zeros(m,n);%禁忌表，记录蚂蚁已经走过的城市，蚂蚁在本次循环中不能再经过这些城市。当本次循环结束后，禁忌表被用来计算蚂蚁当前所建立的解决方案，即经过的路径和路径的长度 Nc=0;%循环次数计数器 routh_best=zeros(Nc_max,n);%各次循环的最短路径 length_best=ones(Nc_max,1);%各次循环最短路径

41、的长度 length_average=ones(Nc_max,1);%各次循环所有路径的平均长度 while Nc<Nc_max %将m只蚂蚁放在n个城市上 rand_position=; for i=1:ceil(m/n) rand_position=rand_position,randperm(n); end tabu_list(:,1)=(rand_position(1:m)'%将蚂蚁放在城市上之后的禁忌表，第i行表示第i只蚂蚁，第i行第一列元素表示第i只蚂蚁所在的初始城市 %m只蚂蚁按概率函数选择下一座城市，在本次循环中完成各自的周游 for j=2:n for i=1:

42、m city_visited=tabu_list(i,1:(j-1);%已访问的城市 city_remained=zeros(1,(n-j+1);%待访问的城市 probability=city_remained;%待访问城市的访问概率 cr=1; for k=1:n%for循环用于求待访问的城市。比如如果城市个数是5，而已访问的城市city_visited=2 4,则经过此for循环后city_remanied=1 3 5 if length(find(city_visited=k)=0 city_remained(cr)=k; cr=cr+1; end end %状态转移规则* q0=0.

43、5; if rand>q0 for k=1:length(city_remained) probability(k)=(pheromone(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; position=find(probability=max(probability); to_visit=city_remained(position(1); end else for k=1:length(city_remained) probability(k)=(pheromo

44、ne(city_visited(end),city_remained(k)alpha*(eta(city_visited(end),city_remained(k)beta; end probability=probability/sum(probability); pcum=cumsum(probability); select=find(pcum>=rand); to_visit=city_remained(select(1); end tabu_list(i,j)=to_visit; %* end end if Nc>0 tabu_list(1,:)=routh_best(N

45、c,:);%将上一代的最优路径（最优解）保留下来，保证上一代中的最适应个体的信息不会丢失 end %记录本次循环的最佳路线 total_length=zeros(m,1);%m只蚂蚁在本次循环中分别所走过的路径长度 for i=1:m r=tabu_list(i,:);%取出第i只蚂蚁在本次循环中所走的路径 for j=1:(n-1) total_length(i)=total_length(i)+D(r(j),r(j+1);%第i只蚂蚁本次循环中从起点城市到终点城市所走过的路径长度 end total_length(i)=total_length(i)+D(r(1),r(n);%最终得到第i只蚂蚁在本次循环中所走过的路径长度 end length_best(Nc+1)=min(total_length);%把m只蚂蚁在本次循环中所走路径长度的最小值作为本次循环中最短路径的长度 position=find(total_length=length_best(Nc+1);%找到最短路径的位置，即最短路径是第几只蚂蚁或哪几只