《蚁群算法在0-1整数规划问题中的应用研究 毕业论文.docx》由会员分享，可在线阅读，更多相关《蚁群算法在0-1整数规划问题中的应用研究 毕业论文.docx（31页珍藏版）》请在三一文库上搜索。
1、华北科技学院毕业论文目 录蚁群算法在0-1整数规划问题中的应用研究II摘要IIABSTRACTIII第1章 绪论11.1蚁群算法的背景11.2 蚁群算法的基本思想21.3 蚁群算法基本原理2第二章 单目标0-1整数规划问题的蚁群算法52.1单目标0-1规划问题52.2经典方法求解52.3用蚁群算法的求解62.4实例求解及分析724.1用回溯算法求解72.42用蚁群算法的求解8第三章 多目标0-1整数规划问题及其求解113.1 问题概述113.2用蚁群算法的求解11第四章 一般整数规划问题及其求解144.1问题阐述144.2用蚁群算法的求解14第五章 总结17参考文献19附录20致谢26蚁群算法
2、在0-1整数规划问题中的应用研究摘要:群智能算法是一种新兴的人工智能方法，已成为越来越多研究者的关注焦点。蚁群算法是群智能算法的一个重要的分支，是意大利学者M. Dorigo通过模拟蚁群觅食行为提出的。本文系统介绍了蚁群算法的背景、原理、模型的建立及对蚁群算法参数的合理设定，给出了其参数设定的基本原则及算法的实现过程。同时提出了蚁群算法在单目标0-1整数规划问题中的应用，利用蚂蚁在整数空间内运动，同时在路径上留下激素，以此引导搜索方向，建立了新的模型算法，并引入实例进行求解验证，证明了本文新模型算法的合理性和相比其他方法的优越性。本文还提出了蚁群算法在多目标0-1规划以及一般整数规划中的应用，
3、仿照在单目标0-1规划中的思想，改进算法，建立模型并求解，成功证明本文的蚁群算法，不仅可用于基本的0-1规划问题，而对多目标0-1规划问题同样适用，更为重要的是，算法还能求解非线性形式的一般整数规划问题。本文在加深对整数规划相关知识的理解的同时，又拓宽了将蚁群算法与整数规划问题相结合来解决实际问题的思想。关键词：蚁群算法；整数规划；0-1规划；非线性整数规划Ant colony algorithm in the application of 0-1integer programmingAbstract：Swarm intelligence algorithm is a new method o
4、f artificial intelligence, has become more and more researchers attention. Ant colony algorithm is an important branch of swarm intelligent algorithm, is an Italian scholar m. Dorigo simulation ant colony foraging behavior.This paper systematically describes the background of the ant colony algorith
5、m, principles, model and ant colony algorithm parameters set reasonable, given the fundamental principles of its parameter settings and algorithm implementation process. While the ant colony algorithm proposed in 0-1 integer programming problems in the application, the use of ants in the integer spa
6、ce movement, while leaving the path hormones, to guide the search direction, established a new model algorithm and introduce examples solving have proved in this paper a new model algorithm is reasonable and superiority compared to other methods. This paper also presents ant colony algorithm in mult
7、i-objective 0-1 integer programming planning and general application, modeled in 0-1 planning ideas, improved algorithms, models and solutions, successfully demonstrated this ant colony algorithm used not only the basic problem in 0-1 programming for multi-objective 0-1 programming problem also appl
8、ies, more importantly, the algorithm can solve nonlinear integer programming problem in general form. In this paper, integer programming knowledge to deepen understanding, they also broadened the ant colony algorithm combined with integer programming problem to solve practical problems thinking.Key
9、words: ant colony algorithm; Integer programming; 0-1 programming; Nonlinear integer programming III第27页 共26页 第1章 绪论算法（Algorithm）是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。算法可大致分为基本算法、数据结构的算法、数论与代数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法。1.1蚁群算法的背景蚁群算法的由来：蚂蚁是地球上
10、最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。这样，M
11、.Dorigo等人于1991年首先提出了蚁群算法1。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。1.2 蚁群算法的基本思想现实生活中单个蚂蚁的能力和智力非常简单，但它们能通过相互协调、分工、合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其是蚂蚁有能力
12、在没有任何可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随环境的变化而变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂蚁觅食的群体行为中得到启发而提出的。在蚁群算法中，为了实现对真实蚂蚁的抽象，提出了人工蚁的概念2。人工蚁和真实蚂蚁有如下相同点：（1）人工蚁和蚂蚁一样，是一群相互合作的个体，每个蚂蚁都能建立一种解决方案，整个蚁群相互合作在全局范围内找出问题的较优的解决方案。（2）人工蚁和真实蚂蚁有着公共的任务，寻找最优路径。（3
13、）人工蚁和真实蚂蚁一样也通过使用信息素进行间接通讯。（4）人工蚁和真实蚂蚁的觅食行为都是一种正反馈过程。（5）在蚁群算法中存在一种信息素的挥发机制，类似于真实世界中的情况。（6）不预测未来状态概率的状态转移策略。人工蚁的策略是充分利用了局部信息，而没有前瞻性的预测未来的状态。1.3 蚁群算法基本原理为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓
14、度越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。蚁群算法可以表述如下：初始时刻，各条路径上的信息素量相等，设ij(0) = C（C 为常数），蚂蚁k（k=1,2,3,m）在运动过程中根据各条路径上的信息量决定转移方向。蚂蚁系统所使用的转移规则被称为随机比例规则，在时刻 t，蚂蚁 k 从城市i选择城市j 的转移概率(t)为： (1.1)其中，Jk(i)= 1，2，n tabuk 表示蚂蚁 k 下一步允许选择的城市。列表tabuk记录了蚂蚁 k
15、 在本次迭代中已经走过的城市，不允许该蚂蚁在本次循环中再经过这些城市。当所有 n 座城市都加入到tabuk中时，蚂蚁 k 便完成了一次周游，此时蚂蚁 k 所走过的路径便是 TSP 问题的一个可行解。(1.1)式中的ij 是一个启发式因子，被称为能见度因子。在 AS 算法中，ij 通常取城市 i 与城市 j 之间距离的倒数。和分别反映了在蚂蚁的运动过程中已积累的信息和启发信息的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根据（1-2）式更新。 (1. 2) (1. 3)其中(0 1)表示路径上信息素的挥发系数，1- 表示信息素的持久系数；ij表示本次迭代边 (ij) 上信息素的增量。
16、kij表示第 k 只蚂蚁在本次迭代中留在边(ij) 上的信息素量。如果蚂蚁 k 没有经过边(ij)，则kij的值为0。kij表示为： (1. 4)其中，Q 为正常数，Lk 表示第 k 只蚂蚁在本次周游中所走过路径的长度。M. Dorigo 提出了 3 种 AS 算法的模型4， 式 (1.4) 称为蚁周系统，另两个模型分别称为蚁量系统和蚁密系统，其差别主要在 (1. 4) 式，即：在蚁量系统模型中为： (1. 5) 在蚁密系统模型中为： (1. 6)AS算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时，蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子。实验结
17、果表明，蚁周系统模型比蚁量系统和蚁密系统模型有更好的性能。这是因为蚁周系统型利用全局信息更新路径上的信息素量，而蚁量系统和蚁密系统模型使用局部信息。AS 算法的时间复杂度为O(NC*n2*m) ，算法的空间复杂度为S(n)=O(n2)+O(n*m) ，其中 NC 表示迭代的次数，n为城市数，m为蚂蚁的数目。第二章 单目标0-1整数规划问题的蚁群算法2.1 单目标0-1规划问题整数规划是决策变量有整数要求的数学规划问题，有着许多重要的实际应用背景，如在研究人力分配问题时，如果决策变量表示分派到某项工作的人数时，就不能取非整数值。同样，如果决策变量代表购买大型设备，如大型发电机，飞机等高值物品，小
18、数表示也是不合理的，此外，一类需要回答是或者否的决策变量，无法取连续值，只能取离散的整数值或者二进制的0或者1。在求解整数规划时，若可行域是有界的，可以使用穷举法，列出所有可行的整数组合，然后比较他们的所有目标函数值，确定最优解。但是对于大型问题而言，组合数很大，使用穷举法几乎是不可能的。0-1规划是一种特殊的整数线性规划，其中变量要么取0，要么取1，故也被称作0-1变量。现实生活中的许多问题都可以化作0-1规划，如航班的安排，工作任务的分配，地址的选定等，通常都是用0-1变量来描述的。0-1规划的数学模型可以表示为：minZ=i=1ncixi s.t.j=1naijxj bi ,i=1,2,
19、m.xj 0,1 ,j=1,2,n.2.2经典方法求解隐枚举法4是求解0-1规划问题的经典方法，它是对穷举法的改进，其原理是通过增加过滤性条件并做一些技术处理，使得在求解过程中可以自动舍弃许多不可能称为最优解的试探解，从而大大减少计算工作量。隐枚举法简单实用，易于计算机计算，但是存在两个明显的缺陷：(1)与穷举法相比，隐枚举法所减少的计算量的程度强烈的依赖于给定的具体问题，简而言之，可构造特殊例子，使得使用隐枚举法求解时，计算量一点也不减少，以至于等同于穷举法。(2)随着决策变量个数N的增大，隐枚举法计算量将急剧的增加，也就是说，隐枚举法存在着规模“爆炸”的问题，实际上，求解整数规划的任何一种
20、精确型方法都存在这一问题，这是由于整数规划问题本身的NP难性质所决定的。【算法源程序见附录】2.3用蚁群算法的求解对于0-1问题，记m=蚂蚁的个数，nij=不同变量组合的差异程度，i=变量i为1时的轨迹强度，ik=蚂蚁k于变量i上留下的单位长度轨迹信息素数量，采用Ant-Density（蚁密系统）模型：i=kQ，若i被选中，0， 其他 Pijk=蚂蚁k的转移率。轨迹强度更新方程为：inew=iold+kik于是，求解0-1规划的蚁群算法主要思想叙述为：步骤1.nc 0（nc为迭代步数或搜索次数）；各参数初始化；步骤2.设置每个蚂蚁对应各变量的初始组合；对每个蚂蚁计算对应变量组合的最小值；计算变
21、量组合的差异；计算转移概率是否进行组合交换；若交换，则将组合i用j代替，增加j各变量的信息素；步骤3.计算各蚂蚁的目标函数值，记录当前最好解；步骤4.按照更新方程修改轨迹强度；步骤5.置ij0；ncnc+1；步骤6.若nc0时，蚂蚁i按概率pij 从i状态移至j状态，即相应的x变为1-x；当ij0时，蚂蚁i维持原状态，具体算法按2.3所述步骤求解。 将蚁群算法与回溯算法进行数值计算比较，各pi，i 在1-100内随机生成，V选用两种形式：（1） V=0.5i=1ni（2） V=0.8i=1ni这里给出两个数值算例以及结果，其中参数=0.7，Q=1.算例1 n=10，V=269，W=95,4,6
22、0,32,23,72,80,62,65,46P=55,10,47,5,4,50,8,61,85,87运行回溯法可求得最优值295；运行的蚁群算法，只需52次迭代后就可得最优值295，运行结果如图2.1所示，平均收敛性态（每种迭代次数下运行10轮）如图2.2所示：图2.1运行结果图2.2收敛性态1算例2 n=20，V=878， W=92,4,43,83,84,68,92,82,6,44,32,18,56,83,25,96,70,48,14,58 P=44,46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63运行回溯法可得到最优值为1018
23、，运行蚁群算法，只需148次迭代后就可得到最优值1018，运行结果如图2.3所示，平均收敛性态（每次迭代次数下运行10轮）如图2.4所示：图2.3运行结果图2.4 收敛性态2各迭代次数上的最好，最差和平均结果如表2.1所示表2.1迭代结果迭代次数最差运行结果最好运行结果平均运行结果140684960010788926887508871024902100979102499615099510241015200100910241022这里给出的蚁群算法，不仅可用于基本的0-1规划问题，对多目标0-1规划问题同样适用，更为重要的是，算法还能求解非线性形式的一般整数规划问题，这对已有的许多经典方法来说是
24、无能为力的。第三章 多目标0-1整数规划问题及其求解3.1 问题概述多目标0-1规划是从一维背包问题10的0-1整数规划为原型，进而发展为多个目标，多个约束的，如实际应用中的投资决策等问题，都可以归结为这类模型。设变量xj为0-1变量，则一般的多目标0-1线性规划数学模型可写成：maxZ=j=1ncj1xj,j=1ncj2xj,j=1ncjkxjs.t.j=1naijxjbi,i=1,2,mxj0,1, j=1,2,n由于多目标意义下，使得所有目标都达到最佳化的最优解往往并不存在，所以一般所要求的都是非劣解（non-dominated solution），也称有效解或Pareto解。为对上述多
25、目标模型进行求解，首先将问题转化为无约束形式，一般可采用罚函数的方式，取和的形式，和平方的形式以及乘积形式等，为方便起见，这里使用较为简单的和函数形式，令罚函数为：f=i=1m|min0,bi-j=1naijxj|则前述多目标0-1规划模型就可以转化为如下的无约束问题：max Z=j=1ncj1xj-Mf,j=1ncj2xj-Mf,j=1ncjkxj-Mf其中，M为充分大的正数。3.2用蚁群算法的求解在蚁群算法中，有关参数，变量设定以及搜索思想同单目标0-1规划，具体应用中，以转移概率来决定蚂蚁的移动位置，在判断解的优劣程度时按随机原则选择一个目标，并按Pareto非劣性质保留有效解，为改善优
26、化效果，算法加入了领域搜索机制，实现细节见附录源代码：为检验算法效果，对大量实例进行了计算测试，获得了较好的效果，下面给出两个算例以及有关结果：算例分析1maxZ1=10x1+14x2+21x3+42x4,maxZ2=30x1+15x2+20x3+18x4s.t.8x1+11x2+9x3+18x4342x1+2x2+7x3+14x4119x1+6x2+3x3+6x414xj0,1, j=1,2,4用蚁群算法解得非劣解为：（1）Z=（35,35），X=0,1,1,0，（1）Z=（31,50），X=1,0,1,0，运行结果如图3.1所示图3.1运行结果其中的参数设定为=1，=0.7，Q=rando
27、m(100)，Ants=2，而每个单目标情形下的最优解分别为Z1=35，X=0,1,1,0;Z2=50, X=1,0,1,0.算例分析2maxZ1=4x3+5x4+7x7+6x8+5x9+6x10,maxZ2=9x1+4x2+6x5+9x6+6x7+5x8+6x9+3x10,maxZ3=6x1+3x2+2x3+8x4+7x5+2x8,s.t. 3x2+4x3+8x4+4x5+7x6+6x7+5x8+2x9+6x1037,5x1+8x2 +6x4+ 9x6+5x7+6x8+3x9+5x1024,9x1+4x2+3x3+6x4+6x5+9x6+6x7+5x8+6x9+3x1043,2x1+3x2+
28、3x3+6x4+3x5 +8x7+4x8+6x9 31,xi0,1, j=1,2,10用蚁群算法解得非劣解为：(1)Z=(12,40,16), X=1,1,0,0,1,1,1,0,1,0;(2)Z=(20,30,28), X=1,1,1,1,1,0,0,1,1,0;(3)Z=(21,29,17), X=1,0,1,0,1,0,0,1,1,1;(4)Z=(21,23,25), X=1,0,1,1,1,0,0,1,0,1;(5)Z=(22,21,22), X=0,1,1,1,1,0,1,1,0,0;(6)Z=(28,20,19), X=0,0,1,1,1,0,1,1,0,1;(7)Z=(28,27
29、,17), X=1,0,1,0,1,0,1,1,1,1; (8)Z=(28,30,14), X=0,1,1,0,1,0,1,1,1,1;运行结果如图3.2所示图3.2运行结果其中参数设定同例1.【算法源程序见附录】第四章 一般整数规划问题及其求解4.1问题阐述整数规划问题是运筹学中一个重要的内容，在工业，商业，运输，经济管理和军事等许多领域都有着广泛的应用，如决策变量为人数，机器台数，商店个数等，就要求其取值均为整数。对于规模较小的整数规划问题，常用的精确求解方法有割平面法12和分支定界法13。割平面法最早由Gomory于1985年提出，故又称为gomory割平面法。其基本思想是：不断增加限性
30、约束条件，将原规划问题的可行域切掉一部分，使得切割掉的部分只包含非整数解，直到最后得到的可行域有一个整数坐标的极点签好是问题的最优解为止。分支定界法则是20世纪60年代初由LandDoig和Dakin等人提出，可用于求解纯整数或混合的整数规划问题，该方法灵活且便于用计算机求解，其核心思想就是“分支”和“定界”，但不管是割平面法，还是分支定界法，随着问题规模的增大，都将变得不可取。为此，多年来人们设计了各种启发式算法来应对实际工作的需要。这里，蚁群算法作为一种新型智能优化算法，不仅可用于求解经典的整数规划问题，还能处理一般的非线性整数规划问题。4.2用蚁群算法的求解一般的无约束整数规划13问题可
31、描述为min f(x1,x2,xn),s.t.aixibi,i=1,2,nxiZ, i=1,2,n其中，Z为整数空间，ai,bi(i=1,2,n)为整数，li=bi-ai+1为xi可能取的个数。可行解空间如图4.1所示，其中xi有li个节点，每个变量取一个值就构成空间一个解，选取n个变量构成n级决策问题，第i级有li个节点，开始时m个蚂蚁在第1级，第j级中选择第i个节点的转移概率定义为pij=iji=1liij这里，ij理解为第j级中第i个节点的吸引强度。x1 x2 x3 xn11113332222 3 . . . . . . . .l1l2l3ln 图4.1轨迹更新方程为：ijnew=ijo
32、ld+Qf其中f为目标函数，表示强度的衰减系数，一般取0.5-0.9左右，Q为一正常数。蚁群算法初始化时，各路径的信息素取相同值，让蚂蚁以等概率选择路径，这样使蚂蚁很难在短时间内从大量的杂乱无章的路径中，找出一条比较好的路径，所以收敛速度很慢。假如在初始化时就给出启发性的信息量，这样就可以加快收敛速度。改进的方法是产生大量的路径（如100条），从中选择比较优的（如30条），使这些路径留下信息素（与路径长度和成反比），各路径的信息量就不同，以此引导蚂蚁进行选择路径。蚂蚁每次周游结束后，无论蚂蚁搜索到的结果如何都将赋予相应的信息量，比较差的解也将留下信息素，这样就干扰后续的蚂蚁进行寻优，造成大量的
33、无效的搜索。改进的方法是，只有比较好的解才留下信息素，即只有当路径小于给定的值才留下信息素。于是，解一般整数规划的蚁群算法主要思想可叙述如下：步骤1. nc0(nc为循环次数)；各参数初始化；步骤2.将m个蚂蚁至于第一级位置；步骤3.对每个蚂蚁，按转移概率pij选择该级中一个节点，每个蚂蚁走遍n个节点；步骤4.计算目标函数值； 对f小于给定值的路径；按更新方程修改吸引强度； ncnc+1；步骤5.若nc预定的循环次数，则停止运行，按ij选择节点；否则转步骤2.用蚁群算法求解整数规划得参数设定与求解0-1规划问题大致类似，具体实验结果不在罗列。此外，算法不仅可求解线性整数规划，还可求解非线性情况
34、下的无约束整数规划以及一般的有约束整数规划问题（可通过罚函数法来处理约束）.第五章 总结在本文的最后,我将对我的论文给予概括性的总结.本论文主要由三大部分组成.首先详细介绍了蚁群算法.在看过相关书籍及许多相关论文后,我对该算法有了相当程度的认识,在经过老师的点拨后,我细心学习了该算法,本文第一部分主要讲解了蚁群算法的基本思想,原理,适用领域,参数设定及相关技术实现问题,从这几方面让读者清晰的了解该算法.论文的第二部分主要讲解了蚁群算法在0-1整数规划问题的应用，建立新了的模型算法，并引入实例进行求解验证，证明了本文新模型算法的合理性。该问题模型的改进是0-1整数规划问题的一大突破,虽然现在已有
35、很多方法求解出0-1问题的近似解,但该算法从另一新的角度解决该问题,经实践检验, 通过改变各参数我们可以直观的看到结果的变化过程,并可以寻到最优近似解.相比其他方法确实得到了很优化的仿真结果，比如第二章用运行回溯法可求得最优值295；运行的蚁群算法，只需52次迭代后就可得最优值295.论文的第三部分主要讲了蚁群算法在多目标0-1规划以及一般整数规划中的应用，仿照在0-1规划中的思想，改进算法，建立模型并求解成功证明本文的蚁群算法，不仅可用于基本的0-1规划问题，对多目标0-1规划问题同样适用，更为重要的是，算法还能求解非线性形式的一般整数规划问题，这对已有的许多经典方法来说是无能为力的。在完成
36、该论文的过程中，让我对最优化问题的方法和理论的发展也有了深入的了解，而最优化问题的解决也是现代社会的重要技术问题，直接推动科学技术的发展。现代优化的方法主要有随机实验法，禁忌搜索算法，遗传算法，神经网络算法，模拟退火算法还有本论文介绍的蚁群算法，这几个算法在解决实际问题中都有其各自的优点和缺陷，当然蚁群算法也有其不足，但是该算法质量高，初值鲁棒性强，简单、通用、易实现，这些非常适合现代的发展，通过研究该算法的发展历程可以看出其适用范围的广泛及其不断改进的优越性，现在蚁群算法已迎来了其应用和发展的高峰期，我想在以后的发展中，不仅会更加广泛的应用到我们的生活中，而且还会应用到更高层的科技领域。该篇
37、论文从选题到完成，我学到了很多知识，同时也看到自己有很多不足，而这篇论文也有一些不足之处，比如缺乏一种简单明了的介绍方式能让读者很容易的接受该理论知识，在应用时，涉及到代码编程问题，一般非专业人士不太容易看懂，在以后的研究中，我想尽力研究该算法的实现，用一种简单的面向对象的模型使得可以方便的解各类优化问题。蚁群算法是一种通用、高效、健壮、可行的拟物型随机近似算法, 并且可以较容易地并行实现以进一步提高运行效率, 适合求解大规模组合优化问题特别是完全问题, 因此具有很大的实用价值。同时由于其讨论涉及随机分析、理论、渐近收敛性、统计分析方法和并行算法等学科, 所以其研究还具有重要的理论意义。此外,
38、 对蚁群算法作一些局部或策略上的修改, 还可得到一些推广或变异形式。参考文献1 段海滨.蚁群算法原理及其应用M.北京：科学出版社,20052 李士勇.蚁群算法及其应用法M.哈尔滨：哈尔滨工业大学出版社,20043 张光澄,王文娟等.非线性最优化计算方法M.北京：高等教育出版社,20064 马良,朱刚,宁爱兵.蚁群优化算法M.北京：北京科学出版社,20085 张光澄,王文娟等.非线性最优化计算方法M.北京：高等教育出版社，20056 冉启康,张振宇,张立柱.常用数学软件教程M.北京：人民邮电出版社,20087 谭尚旺,张德龙.一类整数规划的图论解法J.石油大学学报:自然科学版,2003, 27(
39、 2): 124- 129.8 冯振笑,柯越华.整数规划的交集及交集余集解法J.石油大学学报:自然科学版,2001,25(2):122-125.9 孟志青,胡奇英,杨晓琪.一种求解整数规划与混合整数规划非线性罚函数方法J.控制与决策,2002,17(3):310-314.10 黎青松,周双贵,杜文.用群论方法求解整数规划问题的初步探讨J.西南交通大学学报,2000,35(4):417-420.11 张亮,王继阳.MATLAB与C+混合编程M.北京：人民邮电出版社,200812 李宏,焦永昌,张莉.一种求解混合整数规划的混合进化算法J.控制与决策,2008,23(10):1098-1102.13
40、 高尚,杨静宇.非线性整数规划的蚁群算法J.南京理工大学学报, 2005,29(增刊):120-123.附录0-1整数规划求解的部分代码：#define antcount 5 /蚂蚁总数#define citycount 20 /问题规模#define MAX_NC 500 /最大迭代次数#define Q 1.0 /信息素强度#define alpha 1.0 /启发因子#define beta 5.0 /期望启发因子#define pou 0.7 /挥发因子#define M 100 /惩罚因子int besttravelcitycount;int V;/约束上限int *w,/*物品重量*/*p;/使用价值double random(double m)/获得随机数/srand( (unsigned)time( NULL );double p=(double)rand()/(double)RAND_MAX)*m;return p;class Antprivate:double probcitycount;/选择城市的概率int allowedcitycitycount;/没有走过的城市int k_city;/记录第k只蚂蚁