《蚁群算法在0-1整数规划问题中的应用研究》由会员分享，可在线阅读，更多相关《蚁群算法在0-1整数规划问题中的应用研究（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附录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) 上信息素的增量。kij表示第 k 只蚂蚁在本次迭代中留在边(ij) 上的信息素量。如果蚂蚁 k 没有经过边(ij)，则kij的值为0。kij表示为： (1. 4)其中，Q 为正常数，Lk 表示第 k 只蚂蚁在本次周游中所走过路径的长度
