蚁群算法在TSP问题中的应用研究

蚁群算法在TSP问题中的应用研究刘援农（株洲市芦淞区董家段南方公司工学院湖南株洲412002）摘要：随着计算机技术的发展，各种算法技术也不断在更新，特别是在模仿社会性动物行为领域产生很多智能算法。主要介绍蚁群算法，阐述其工作原理和特点及使用它求解TSP问题的具体实现。关键词：蚁群算法；TSP；群体智能中图分类号：TP273文献标识码：A文章编号：1671－7597（2011）0710108－01目前，在大力发展生物启发式计算研究的背景下，社会性动物如蚁其中表示两城市间的距离。群、蜂群、鸟群等的自组织行为引起了人们的广泛关注，许多学者对这种每只蚂蚁在走完一步或者完成一次对N个城市遍历后，都需要对信息行为进行数学建模并用计算机对其进行仿真，这就产生了所谓的“群集智素进行更新处理。设表示t+n时刻后在路径（i，j）上残留的信能”（swarmintelligence，简称SI）。息素量，其计算表达式为：社会性动物的妙处在于：个体行为简单，但是集体协作工作能体现出一些复杂的智能行为，而在这些行为当中，又以蚁群在觅食过程中总能找到一条从蚁巢到食物源的最短路径最为引人注目。受其启发，意大利学者M.Dorigo，V.Maniezzo和A.Colorni而于20世纪90年代初提出了一种新型各条路径的信息素会逐渐挥发，用参数表示信息素的残留因的智能优化算法——蚁群算法。该算法最初被用于求解著名的旅行商问题子，为防止信息素无限累积，的取值范围是[0，1）。表示t时（TravelingSalesmanProblem，简称TSP）并获得了较好的效果。刻在城市i，j之间路径上的信息素增量，表示第k只蚂蚁在本次循环中在城市i，j之间路径上留的信息量。在计算的时候，采用蚁周1蚁群算法原理模型计算法，即：蚂蚁是群体动物，它们没有视觉但是可以通过集体配合劳动找到从巢穴到食物源的最短路径。仿生学家经过大量研究后发现，蚂蚁在搜索食物时个体之间能通过在路径上留下的气味来进行信息传递，这种气味称作信息素（pheromone）。在蚂蚁边运动边留下信息素，并且可以根据嗅到的信息素的浓度来进行前进路径的选择。蚂蚁总是倾向于沿着信息素浓度高3算法实现流程的方向来移动，而路径上的信息素会随着时间的推移而逐渐挥发。信息素强弱指导蚂蚁行进，于是当一条路径上走过的蚂蚁越多，信息素浓度就会begin越强烈，后来的蚂蚁选择该路径的概率就越大。这种群体行为构成了一种算法初始化：假定有n个城市节点，m只蚂蚁。令（-信信息正反馈现象，蚂蚁就是通过这种反馈机制来进行信息交流，最终快速息素初始值为一常数），=0，NC=0；（NC是循环计数器，是城找到食物。市i，j之间路径上的初始化信息素2使用蚁群算法求解TSP问题TSP问题的描述是：有n个城市，一个旅行商从其中一个城市出发，在访问完其余城市各一次且仅有一次后回到原城市，要找到一条最短的巡回路径。用蚁群算法来求解TSP问题：浓度，在初始时刻任意两城市间的信息素浓度相同，设置=const，其中const表示一常量。蚂蚁k（k=1，2，…，m）在运动过程中，根据各条路径上的信息量来决定转移方向，用禁忌表（k=1，2，…，m）来表示蚂蚁k当前已经走过的城市。在蚂蚁行进过程中用来计算在t时刻从城市i选择移动到城市j的概率，的计算表达式为：在式（1）中，表示i与j两城市之间路径的信息素浓度，表示蚂蚁k下一步允许选择的城市的集合。参数表示启发因子，反映了信息素对蚂蚁选路的重要程度；代表启发式因子，反映了启发信息对于蚂蚁选路的重要程度。为启发函数，表示两城市的能见度，与两城市间的距离相关，其表达式如下：量，是每次循环后蚂蚁在城市i，j之间路径上上留下的信息素总量。）While（NC）（表示设置的循环次数）{for（k=1；k=m；k++）初始化蚂蚁Ants[k]的起始城市位置和搜索禁忌表；while（存在不属于搜索禁忌表中的城市）{应用公式（1）选择下一城市j；蚂蚁Ants[k]移动到城市j，修改蚂蚁k搜索禁忌表；应用公式（3）修改最新路径上的信息素量；}NC=NC+1；}输出最小长度路径；end4结论与展望蚁群算法虽然在解决TSP问题时候具有较强的鲁棒性，但是存在着蚂蚁个体运动随机性缺陷，特别是当蚂蚁数量较多时，搜索时间会比较长。另外，在搜索过程中容易出现路径过早集中到局部最优解，导致算法停滞、早熟。因此，在解决TSP问题时，可以与其他算法例如遗传算法结合来改善蚁群算法性能，这些有待进行更进一步的研究。参考文献：假设有m只蚂蚁占据了n个城市，其中表示在t时刻位于i城市的蚂蚁数，则有关系。表示城市i与j之间在t时刻的信息素（1）（2）（3）（4）（5）2108（下转第114页）2114文件，并依据点云的特征。做出一些辅差异显示出来，分析曲面与点云之间的序的制作，生成粗精加工程序。由于数控助的基准，以便把零件点云进行方位对差异值，从而检测逆向扫描测量的精确机床的加工过程中要避免使机床发生碰齐，为提取截面线做准备。点云数据中性。撞，同时还需避免产生过切或错误的刀具含有许多杂点，因此需把杂点过滤掉，轨迹，为此须进行刀位验证，来判断刀具并对点云数据进行数据平滑、数据清轨迹是否连续、进退刀、走刀路线是否合理、补齐遗失点等优化处理，删除不必理。加工过程的动态图形仿真验证采用实要的数据点，适当降低点云的密度，可体造型技术建立零件的毛坯、夹具和刀具以加快计算机处理的速度，构建零件对在加工过程中的实体模型，使用快速布尔称基准面等。得到零件的光顺曲线网格运算。最后采用真实感图形显示技术，把图形如图3所示。图4在Pro/E软件中完成的三维造型加工过程动态地显示出来，动态仿真显示特征线的提取是整个模型重构的关建立零件的三维模型后，针对零件刀具加工轨迹。将生成NC加工的G代码键。根据零件的外形特点，划分出二次上需加工的部位增加1.5m左右的加工余输入三轴（或五轴）加工中心对模具进行曲面的区域，如内孔、凹槽、平面、圆量，将孔位封起。压铸模实体模型还要加工；对模具电极进行处理，生成电极加柱面等。并对零件点云进行分割，把这考虑收缩率，一般为5‰，运用Pro/E可以工程序，对模具电极进行加工等。些二次曲面拟合构造内孔、凹槽、平面自动增加收缩率，也可通过改变比例来4.5模具结构优化及改进使用陶瓷模精密铸造方法通过增加或圆柱面，也可直接做出特征。平面可实现。进行外观修整，如圆角、倒角、2.2％尺寸增加率所得的主模型（蜡型成以用三点或两相交直线来确定，孔或圆拔模角等处理后，得到零件压铸模实体型模）-射蜡-组树-沾浆与淋砂-脱蜡与柱面则以截面线和矢量来确定．通过测模型，如图5所示。烧成，再进行浇注，得到零件铸造毛量实体模型并结合扫描数据生成。对于坯。将前面创建好的在Pro/E软件中完成自由曲面．需构造出曲面的特征线。先的三维造型汇入Pro/E的Manufacturing模对零件点云做出必要截面线，然后剔除块，建立新的Pro/NC文件，对毛坯进行截面点云的杂点进行必要的光顺，最后加工。根据加工结果与零件的三维数据把截面点云拟合成曲线，以便构造自由进行比对，针对比对结果对模具相对特曲面。征部位进行有效改进和处理，使修改后所加工的产品更加符合客户要求。5结束语图5在Pro/E软件中完成的压铸模实利用三维激光扫描抄数作为获取空体模型间三维数据的手段，组合使用逆向工程4.4模具结构设计与制造压铸模实体模型建成后，可进一步软件对获取测量数据进行处理、三维数作模具分型设计，生成型模凹槽、侧抽及字化模型的构建、模具的检测和修改均镶件等，以便进行模具的结构设计：①推起到了很好的成效，此应用使产品的消图3经过处理的光顺曲线网格图出机构设计；②溢流槽、排气口设计；③化吸收和二次开发工作准确快捷。逆向打开Pro/E软件，针对处理完成的点浇口、流道设计；④抽芯机构及位设计；工程结合CAD/CAM技术和NC机床对模云数据，通过刨建曲面、曲面编辑得到⑤模具常规零件设计等。应用Pro/E软件具设计制造起到很大的促进作用，缩短完整曲面，并进行布尔运算，在的Assmbly和Modei模块进行模具设计，生了产品开发周期，并且实现了产品原型Pro/PART模块下完成零件的三维实体造成模具的型芯和型腔。使用干涉检测，仿设计生产与模具设计制造的系统集成，型，如图4所示。真靠模开起顺序。运用Pro/E所提供的加使其在今后的模具开发中发挥更大的作完成零件的三维造型后，将利用Pro/E工模块Pro/Manufacturing对模具型腔进用。软件重构的三维造型读入Imageware软件行处理，将压铸模实体模型汇入Pro/E软中。比较分析最终重构的三维造型和扫件的Manufacturing模块中进行NC加工程E-works描的点云之间的偏差，通过使用云图将[1]李志伟，基于群集智能的蚁群优化算法研究[J].计算机工程与设计，[4]秦玲，蚁群算法的改进与应用，扬州：扬州大学硕士学位论文，2004.2003.8.[5]BonabeauE，DorigoM，TheraulazG.Inspirationfor[2]KennedyJ，EberhartRC.Swarmintelligence[M].SanFrancisco：optimizationfromsocialinsectbehavior.Nature，2000，406（6）.MorganKaufmann，2001.[3]张宗永、孙静、谭家华，蚁群算法的改进及其应用[J].上海交通大学作者简介：报，2002，36（11）.刘援农，男，讲师，主要从事数学与应用数学方面的教学与研究。（上接第108页）