蚁群算法在0

《蚁群算法在0》由会员分享，可在线阅读，更多相关《蚁群算法在0（30页珍藏版）》请在装配图网上搜索。

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附录

2、20致谢26蚁群算法在 0-1 整数规划问题中的应用研究摘要:群智能算法是一种新兴的人工智能方法，已成为越来越多研究者的关注焦 点。蚁群算法是群智能算法的一个重要的分支，是意大利学者 M. Dorigo 通过模 拟蚁群觅食行为提出的。本文系统介绍了蚁群算法的背景、原理、模型的建立及 对蚁群算法参数的合理设定，给出了其参数设定的基本原则及算法的实现过程。 同时提出了蚁群算法在单目标 0-1 整数规划问题中的应用，利用蚂蚁在整数空间 内运动，同时在路径上留下激素，以此引导搜索方向，建立了新的模型算法，并 引入实例进行求解验证，证明了本文新模型算法的合理性和相比其他方法的优越 性。本文还提出了蚁群算

3、法在多目标 0-1 规划以及一般整数规划中的应用，仿照 在单目标0-1 规划中的思想，改进算法，建立模型并求解，成功证明本文的蚁群 算法，不仅可用于基本的0-1 规划问题，而对多目标0-1 规划问题同样适用，更 为重要的是，算法还能求解非线性形式的一般整数规划问题。本文在加深对整数 规划相关知识的理解的同时，又拓宽了将蚁群算法与整数规划问题相结合来解决 实际问题的思想。关键词：蚁群算法；整数规划；0-1 规划；非线性整数规划Ant colony algorithm in the application of 0-1integerprogrammingAbstract： Swarm intell

4、igence algorithm is a new method of 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 bac

5、kground of the ant colony algorithm, 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,

6、the use of ants in the integer space 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 pre

7、sents ant colony algorithm in multi-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

8、 0-1 programming problem also applies, 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 solv

9、e practical problems thinking.Key words: ant colony algorithm; Integer programming; 0-1 programming; Nonlinear integer programming第1 章 绪论算法(Algorithm)是一系列解决问题的清晰指令，算法代表着用系统的方 法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间 内获得所要求的输出。算法可大致分为基本算法、数据结构的算法、数论与代 数算法、计算几何的算法、图论的算法、动态规划以及数值分析、加密算法、 排序算法、检索算法、随机化算法、并行算法

10、。1.1 蚁群算法的背景蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成 群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了 一些学者的注意。意大利学者M.Dorigo, V.Maniezzo等人在观察蚂蚁的觅食习 性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这 种群体协作功能是通过一种遗留在其来往路径上的叫做信息素(Pheromone)的挥 发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之 一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发 现，整个蚁群就是通过这种信息素进行相互协作，形成

11、正反馈，从而使多个路径 上的蚂蚁都逐渐聚集到最短的那条路径上。这样，M.Dorigo等人于1991年首先 提出了蚁群算法1。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。 这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间 简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与 旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。 同时，该算法还被用于求解 Job-Shop 调度问题、二次指派问题以及多维背包问 题等，显示了其适用于组合优化类问题求解的优越特征。1.2 蚁群算法的基本思想现实生活中单个蚂蚁的能力和智力非常简单，但它们

12、能通过相互协调、分工、 合作来完成筑巢、觅食、迁徙、清扫蚁穴等复杂行为，尤其是蚂蚁有能力在没有 任何可见提示的条件下找到从蚁穴到食物源的最短路径，并且能随环境的变化而 变化地搜索新的路径，产生新的选择。这是因为蚂蚁在其走过的路上会分泌一种 信息素，其他的蚂蚁能够感知这种物质的存在和强度，并以此指导自己的运动方 向，使其倾向于朝着信息素强度高的方向移动。蚁群算法就是从自然界中真实蚂 蚁觅食的群体行为中得到启发而提出的。在蚁群算法中，为了实现对真实蚂蚁的 抽象，提出了人工蚁的概念2。 人工蚁和真实蚂蚁有如下相同点：（1）人工蚁和蚂蚁一样，是一群相互合作的个体，每个蚂蚁都能建立一种 解决方案，整个蚁

13、群相互合作在全局范围内找出问题的较优的解决方案。（2）人工蚁和真实蚂蚁有着公共的任务，寻找最优路径。（3）人工蚁和真实蚂蚁一样也通过使用信息素进行间接通讯。（4）人工蚁和真实蚂蚁的觅食行为都是一种正反馈过程。（5）在蚁群算法中存在一种信息素的挥发机制，类似于真实世界中的情况。（6）不预测未来状态概率的状态转移策略。人工蚁的策略是充分利用了局 部信息，而没有前瞻性的预测未来的状态。1.3 蚁群算法基本原理为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁 群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁 在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰

14、到一个还没有走过 的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息 素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候选 择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激 索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整 个蚁群会找出最优路径。蚁群算法可以表述如下：初始时刻，各条路径上的信息素量相等，设Tjj（O）=C (C为常数)，蚂蚁k (k=l,2,3,m)在运动过程中根据各条路径上的信息量 决定转移方向。蚂蚁系统所使用的转移规则被称为随机比例规则，在时刻t,蚂 蚁k从城市i选择城市j的转移概率pk (t)为

15、：ijP k ( t )= ij( t )工t (t) k 耳卩isisu (t) ijs G J k( i)0,if j G Jk (i)otherwise(1.1)其中，Jk(i)= 1, 2，n tabuk表示蚂蚁k下一步允许选择的城市。列表 tabuk记录了蚂蚁k在本次迭代中已经走过的城市，不允许该蚂蚁在本次循环中 再经过这些城市。当所有n座城市都加入到tabuk中时，蚂蚁k便完成了一次 周游，此时蚂蚁k所走过的路径便是TSP问题的一个可行解。(1.1)式中的n ij 是一个启发式因子，被称为能见度因子。在as算法中，n ij通常取城市i与 城市j之间距离的倒数。a和0分别反映了在蚂蚁

16、的运动过程中已积累的信息 和启发信息的相对重要程度。当所有蚂蚁完成一次周游后，各路径上的信息素根 据(1-2)式更新。t C+n)= (1-p) *t (t)+At(1. 2)ijijija t = a t kijijk = 1其中p (0 P 1)表示路径上信息素的挥发系数, t ij表示本次迭代边(ij)上信息素的增量。 t 代中留在边(ij)上的信息素量。t k 表示为：ij(1. 3)1-p表示信息素的持久系数; kij 表示第 k 只蚂蚁在本次迭 如果蚂蚁k没有经过边(ij),则Atkij 的值为 0。At k =ijQL，K0，若蚂蚁在本次周游中经过边否则ij(1. 4)其中， Q

17、 为正常数， Lk 表示第 k 只蚂蚁在本次周游中所走过路径的长度。M. Dorigo 提出了 3 种 AS 算法的模型4， 式 (1.4) 称为蚁周系统，另两 个模型分别称为蚁量系统和蚁密系统，其差别主要在 (1. 4) 式，即：在蚁量系统模型中为：rQAt k = d ijij0,蚂蚁在时刻t和t+1经过边 i j否则(1. 5)在蚁密系统模型中为：At kij蚂蚁k在时刻t和t+l经过边ij否则(1. 6)AS 算法实际上是正反馈原理和启发式算法相结合的一种算法。在选择路径时， 蚂蚁不仅利用了路径上的信息素，而且用到了城市间距离的倒数作为启发式因子 实验结果表明，蚁周系统模型比蚁量系统和

18、蚁密系统模型有更好的性能。这是因 为蚁周系统型利用全局信息更新路径上的信息素量，而蚁量系统和蚁密系统模型 使用局部信息。 AS 算法的时间复杂度为 O(NC*n2*m) ，算法的空间复杂度为 S(n)=O(n2)+O(n*m),其中NC表示迭代的次数，n为城市数，m为蚂蚁的数目。第二章 单目标 0-1整数规划问题的蚁群算法2.1 单目标 0-1 规划问题整数规划是决策变量有整数要求的数学规划问题，有着许多重要的实际应用 背景，如在研究人力分配问题时，如果决策变量表示分派到某项工作的人数时， 就不能取非整数值。同样，如果决策变量代表购买大型设备，如大型发电机，飞 机等高值物品，小数表示也是不合理

19、的，此外，一类需要回答是或者否的决策变 量，无法取连续值，只能取离散的整数值或者二进制的 0 或者 1。在求解整数规划时，若可行域是有界的，可以使用穷举法，列出所有可行的 整数组合，然后比较他们的所有目标函数值，确定最优解。但是对于大型问题而 言，组合数很大，使用穷举法几乎是不可能的。0-1 规划是一种特殊的整数线性规划，其中变量要么取 0，要么取 1，故也被 称作0-1 变量。现实生活中的许多问题都可以化作0-1 规划，如航班的安排，工 作任务的分配，地址的选定等，通常都是用 0-1变量来描述的。0-1 规划的数学模型可以表示为：nmin Z = c xiii=1nax b , i = 1,

20、2,m.s. t. ij j ij=1x 6 0,1 , j = 1,2,n.j2.2 经典方法求解隐枚举法4是求解 0-1规划问题的经典方法，它是对穷举法的改进，其原理 是通过增加过滤性条件并做一些技术处理，使得在求解过程中可以自动舍弃许多 不可能称为最优解的试探解，从而大大减少计算工作量。隐枚举法简单实用，易于计算机计算，但是存在两个明显的缺陷：(1)与穷举法相比，隐枚举法所减少的计算量的程度强烈的依赖于给定的具 体问题，简而言之，可构造特殊例子，使得使用隐枚举法求解时，计算量一点也 不减少，以至于等同于穷举法。(2)随着决策变量个数 N 的增大，隐枚举法计算量将急剧的增加，也就是说， 隐

21、枚举法存在着规模“爆炸”的问题，实际上，求解整数规划的任何一种精确型 方法都存在这一问题，这是由于整数规划问题本身的 NP 难性质所决定的。 【算法源程序见附录】2.3 用蚁群算法的求解对于0-1问题，记m=蚂蚁的个数，nij =不同变量组合的差异程度，Ti=变量i 为1时的轨迹强度，=蚂蚁k于变量i上留下的单位长度轨迹信息素数量，采 用Ant-Density (蚁密系统)模型：Tk Q，若i被选中，i= 0，其他Pikj =蚂蚁 k 的转移率。轨迹强度更新方程为：Tnew =iiik于是，求解 0-1 规划的蚁群算法主要思想叙述为：步骤1.nc 0 (nc为迭代步数或搜索次数)；各参数初始化

22、；步骤 2.设置每个蚂蚁对应各变量的初始组合；对每个蚂蚁计算对应变量组合 的最小值；计算变量组合的差异；计算转移概率是否进行组合交换；若交换，则 将组合i用j代替，增加j各变量的信息素；步骤 3.计算各蚂蚁的目标函数值，记录当前最好解；步骤 4.按照更新方程修改轨迹强度；步骤 5.置Ajj 0； ncnc+1；步骤6.若ncv预定迭代次数且无退化行为，则转步骤2；步骤 7.输出当前最好解。【算法源程序见附录】2.4 实例求解及分析假设有一个徒步旅行者，有n种物品可供选择后装入背包中，已知第i种物 品的重量为卩千克，使用价值为R，这位旅行者本身所能承受的总重量不能超过 V千克，问该旅行者如何选择

23、这n种物品的件数，使得总的使用价值最大。这就 是著名的背包问题，背包问题是一类典型的整数规划问题；类似的问题有货物运 输中的最优载货问题、工厂里的下料问题、银行资金的最佳信贷问题等。设气为旅行者选择第i (i=l,2, n)种物品的件数，则背包问题的数学模 型为：nmax Z = p xiii=1n3.X 0且为整数，i = 1,2,ni若气只取0或者1,则成为0-1问题。背包问题的描述有很多种形式，其中，一般的整数背包问题可在有界的前提 下化成为等价的 0-1 问题，因此这里仅考虑最基本的 0-1 背包问题。求解0-1 背包问题，目前已经有多种计算方法，如动态规划，回溯法和分支 定界法等，但

24、是这些精确型方法都是指数级别的，根本无法解决真正的实际问题。24.1 用回溯算法求解回溯法4是一种在问题解空间中做系统搜索的方法，这个空间必须至少包含 问题的一个解(可能是最优解)，其典型的组织方法是图或者树，一旦定义了解 空间的组织方法，即可按照深度优先的办法从开始节点进行搜索，回溯算法的一 个有趣特性是在搜索执行的同时产生解空间，在搜索器件的任何时刻，仅保留从 开始节点到当前节点的路径，但是由于解空间的大小通常是最长路径长度的指数 或者阶乘，所以如果要存储全部解空间的话，再多的空间也不够用，本质上而言， 回溯算法仍是一种枚举法，当问题规模较大时，其指数级别的时间复杂度是难以 令人接受的。【

25、算法源程序见附录】2.42 用蚁群算法的求解对上述实例，记5=（-fi（目标函数差值），其中，目标函数f的形式可转化 为：n=1 pixi - M|m嶼0,V- n=i 屮|M 为一充分大的正数，即把原约束方程作为罚函数9项加入原目标函数中。 转移概率定义为：T.n.p. = LJJ_ijk Tk nik其中，Tj理解为蚂蚁j的领域吸引强度。更新强度方程为：Tnew = pTold +kiATk优化过程借助蚂蚁从其初始状态（0或1的位置点）开始的不断移动来进行， 当比0时，蚂蚁i按概率pij从i状态移至j状态，即相应的x变为1-x； 当nij -0时, 蚂蚁i维持原状态，具体算法按2.3所述步

26、骤求解。将蚁群算法与回溯算法进行数值计算比较，各Pi，卩 在1-100内随机生成， V 选用两种形式： v = o.5 n=i 卩 v = o.8 n=i 卩这里给出两个数值算例以及结果，其中参数Q=1. 算例 1 n=10， V=269，W=95,4,60,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所示：，:Vg 具1的：、1 V I *； 加 如 4 :G1g.wI&-

27、22uL3C4J-5Pr起!a a 日in屮 kEjj t:n uont While：J.： Z7? 阿酉刖1越0B= 1S4 厨磁葡0 車19 &貝质超10閒硯 Mi 215=000603 臬.149.EimfiElia 康=Z34 阿酉刖1越0 皐.戲斗 245.01(100 臬.足弓.闻図诃阳013 巣；123 目0EUB闇H 臬.222b00OC09 迭代枚纵52艮隹遍历轴品选择2- 10- ?- - 7- t- E- 4-5 3- 1- ia 111 a o O 1L1规划匣料品数据打印,-10-265卩1HT石 UIC21-4 ul-GO uMl-32_295 阳013网013扌戈

28、至I29S .买|3芒2T5嗯園酉曲1也 实R丞: 25.U0Uti0 实际 29E.nfianfi 实险; 壬吗0圜0实陆 2T5创邑頤叩目閉 实P示; 29G.Q0aDe 卖曉 29S.实阿2T5嗯園酉曲1也 实R丞: 25.U0Uti0 实际 29E.nfianfi 实险; 2?5.0000601 实阿: 创EI0EJJEI的 实H示 25 E10000 ：)-图2.1运行结果值标目1200 20 30 40 50 60 70 80 90 100 110 120 130 140 150迭代次数图 2.2 收敛性态 1算例 2 n=20，V=878， W=92,4,43,83,84,68,

29、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，运行蚁群算法，只需 148 次迭代后就可 得到最优值1018，运行结果如图 2.3 所示，平均收敛性态（每次迭代次数下运行 10轮）如图 2.4 所示：|一|區年4殆;吹捋寻 4J3E1 生“汕工：咚鼻 邃好瞅礬1018.0000001018.0000001018-003330 1018-003330 MW丽的丽 MW丽的丽 101Sb.9999 101Sb.

30、9999環503；灵搜寻 二 1018.009990 豈优.解为 1町氛朋丽胴找到一B.Ja.JrnjJrnjJrnrzfnpHpflp nrLi - 畀号ELh 号Eh.BhHhsh 孚皑 壬 口士 口士口士 EQ-HD+ID-H 口士口军 纟 l 纟 Lr-i-= JM-_Ji=旨斤 寻IW1W寻穿寻寻所 aoiw.ww.理解BB&日百000 &73： 日百 000 01010000 7理玄.01010000 21-鬥乌日000 7Er?.0Hfi000 695.866666 729b0GG000 721-006000 ;尺把：|仲41规划原韧品数据打印n=a9,U=8?SwIllS wC

31、ZJ- w(3J wM W3 w(51-81 wGJ=68 w(?J-2 W2 wt? J-6 wll0M4 w 113=12 u121-IB wI13II=Sfe uCldl-03 wI151=2S uClt l-9t wll? = uClBw【l爭-1呻M2Q卫plill-44 p2 3-46 p!3-M p4I-?2 pt5J-91p 1.71-75 PE：&-35 pL9J- p10j=4pll-78 p23=40 p13=77 pCi4K5 plSJ6 pC16J-17 p171=75 pS=29 plJ=?5 p20=63己仃号 Ike彳 匸。c口ritinllg.I, -C:Ll

32、l4eriLinDesld：DpEiM；:S36SO-15B12DeibijgZffraTaOne.ejce图 2.3 运行结果值标目o o o o O 505059 9 8 8 7700650600IIIIIIIII55020406080100120140160180200迭代次数图 2.4 收敛性态 2各迭代次数上的最好，最差和平均结果如表 2.1 所示表 2.1 迭代结果迭代次数最差运行结果最好运行结果平均运行结果140684960010788926887508871024902100979102499615099510241015200100910241022这里给出的蚁群算法，不仅可

33、用于基本的 0-1 规划问题，对多目标0-1 规划 问题同样适用，更为重要的是，算法还能求解非线性形式的一般整数规划问题， 这对已有的许多经典方法来说是无能为力的。第三章 多目标 0-1整数规划问题及其求解3.1 问题概述多目标 0-1 规划是从一维背包问题10的 0-1整数规划为原型，进而发展为多 个目标，多个约束的，如实际应用中的投资决策等问题，都可以归结为这类模型。设变量Xj为0-1变量，则一般的多目标0-1线性规划数学模型可写成：n n nmaX Z = c1X ,c2X , ,ck X j jj jj jj=1j=1j=1na.x b,i = 1,2,ms. t.ij j ij=1x

34、 6 0,1 ,j = 1,2,nj由于多目标意义下，使得所有目标都达到最佳化的最优解往往并不存在， 所以一般所要求的都是非劣解(non-dominated solution),也称有效解或Pareto 解。为对上述多目标模型进行求解，首先将问题转化为无约束形式，一般可采 用罚函数的方式，取和的形式，和平方的形式以及乘积形式等，为方便起见，这 里使用较为简单的和函数形式，令罚函数为：mnf =|minP0, bi a”尊 |i=1j=1则前述多目标0-1规划模型就可以转化为如下的无约束问题：nnnmaxZ = cix Mf,c2x Mf ,ckx Mfj jj jj jj=1j=1j=1其中，

35、 M 为充分大的正数。3.2 用蚁群算法的求解在蚁群算法中，有关参数，变量设定以及搜索思想同单目标0-1规划，具体 应用中，以转移概率来决定蚂蚁的移动位置，在判断解的优劣程度时按随机原则 选择一个目标，并按Pareto非劣性质保留有效解，为改善优化效果，算法加入了领域搜索机制,实现细节见附录源代码： 为检验算法效果,对大量实例进行了计算测试,获得了较好的效果,下面 给出两个算例以及有关结果：算例分析 1maxZ = 10x +14x +21x +42x ,11234max Z = 30x + 15x + 20x + 18x2 1 2 3 48x + 11x + 9x + 18x 3412342

36、x + 2x + 7x + 14x 111234s. t. 9x + 6x + 3x + 6x 141234Xj 6 0,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 所示234-5678? 9 9 Q- nJ s 5 Q- 9 0 Tu 4 q 4- 4- 4- -4 4 w E 岁 f7ir.rJa-Fgh,lnoa-T7h1h,Bo6-T7a-nrl,l一EL=35Zl-35 紀T弓Zl=35Zl-35Zl=35 #：Zl-35 辛Z1 站 Z1=35Z2=35Z2-35

37、还35Z=35Z2*35K=35Z2-35!K-35Z2=35 找V ：Z1=21 Z2W0 ：Z1-31 Z2-50 f：Zl-31 ZS-50_ ：Z1=31 说书0 ：Z1-31 E2-S0_ ：Z1=21 说=20 ：Z1-3S E2-35:El-14 Z2M5所需迭代衣数弓求得的非劣解为g i i eWi-flJLBl-8 alBHlJ-11l0-2 aCIHi-!2J0J=9 aI2HlJ=6目标国数馒：2aI0H2J=? aJIJJ-10l1J2J-? i13-Ha12121=3 aI2E3J=6目标函数系数三p|0=10 pEl=14 p21=21 pE03=42 plJ01=

38、30 u1JL11-15 plH21=20 :MlU卬】1EJhESta contiiniLie.图 3.1 运行结果其中的参数设定为a =p =1, p =0.7, Q二random（lOO）, 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,maxZ = 6x +3x +2x +8x +7x +2x ,3 1234583x + 4x

39、+ 8x + 4x + 7x + 6x + 5x + 2x + 6x 37,23456789105x1+8x2+6x4+9x6+5x7+6x8+3x9+5x1024,s. t. 9x + 4x + 3x + 6x + 6x + 9x + 6x + 5x + 6x + 3x 43,123456789102x + 3x + 3x + 6x + 3x+ 8x + 4x + 6x 31,12345789x 6 0,1 ,j= 1,2,10i用蚁群算法解得非劣解为：(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,

40、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,17),X=1,0,1,0,1,0,1,1,1,1;(8)Z=(28,30,14),运行结果如图 3.2 所示X=0,1,1,0,1,0,1,1,1,1;&0】0】血 =*b) m=*a;elsem=*b;return m;class projectpubli

41、c: project();int n;/问题规模int t i;/找到最优解所需迭代次数int choiceci tycoun t;/物品选择状况Ant antsantcount; double bestlengthMAX_NC;void ini tmap();/初始化城市间的信息素void print();void upda teinfor();/更新信息素void pu tan tt oci ty();/将蚂蚁随机的放在各个点上void searchbes tt our();/开始寻找最优路径 double length;void SaveBes tTour toFile(int nc,d

42、ouble leng th);/将最优结果存入 文件 ;void project:SaveBestTourtoFile(int nc,double length)/将最优结果存 入文件ofstream out(result.txt);/ios:ate 扌旨向文件末尾 filebuf:sh_write 以写的方式打开文件for(int i=0;inc;+i) outi+1 lengthin;out最优解为：lengthnc-l找到最优解所需迭代次数： ti; outn 物品选择情况： n;for(i=0;icitycount;+i)outchoicei ; outnO-l规划原数据打印n; ou

43、tn=n V=Vnw=; for(i=0;icitycount;i+)outwi ;outnp=; for(i=0;icitycount;i+) outpi ;outnV;/读入 n 和 Vw=new intn;p=new intn;for (int i=0;iwi; besttraveli=0;choicei=-1;for (i=0;ipi;多目标 0-1 规划求解的部分代码：#include iostream.h#include stdio.h#include math.h#include stdlib.h#include fstream.h#include time.h#define antcount 2 /蚂蚁总数#define citycount 10 /问题规模#d