分布式蚁群算法在求解np问题中应用探究

《分布式蚁群算法在求解np问题中应用探究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分布式蚁群算法在求解NP问题中应用探究　　摘要：集合覆盖问题已被证明是一个NP完全问题，现在所有的NP完全问题，没有多项式时间算法求解。目前为集合覆盖问题的主要的近似算法，复杂或大型集合覆盖问题，现有的算法很难达到理想的优化效果。蚁群算法是基于群体智能的进化算法为基础的小说，关注个体的蚂蚁之间的合作，利用信息素正反馈机制，具有很强的寻找更好的解决方案的能力。蚁群算法已成功地应用在许多复杂的优化问题，其优化能力提供了一种新的思路来解决集合覆盖问题。蚁群算法具有耗时长、易陷入局部最优解的缺点。关键词：NP完全问题蚁群算法群体智能第一章研究背景集合覆

2、盖问题是一个NP问题，NP问题是计算机算法理论最深刻的问题，因为所有的NP完全问题，没有多项式时间算法求解。集合覆盖问题是非常广泛的，许多学者提出了优化算法的集合覆盖问题。这些算法的近似算法，根据具体问题的特点设计的，特别是问题可以得到较为理想的优化结果。第二章蚁群算法2.1蚂蚁的基本习性6蚂蚁是一种最古老的社会性昆虫，其起源可以追溯到100000000年前，大约相同的恐龙时代。像人类一样，悄悄地与我们的星球亿蚂蚁数以百万计，几乎占据了所有可居住的土地，只有永恒的雪不信的南北足。虽然有成千上万的蚂蚁，但没有一个是生活，是生活在群体中，建立了自己

3、独特的蚂蚁社会。虽然单个蚂蚁是相对简单的，但整个殖民地的代表是作为社会组织机构的高度，可以完成比在许多情况下，蚂蚁个体能力复杂的任务。蚂蚁社会个人从事不同的劳动，组织可以在劳动分工执行个体。蚂蚁的社会成员的组织分工除外，和相互通信和信息传输。蚂蚁有一个独特的信息系统，包括视觉信号，语音通信和更多的无声的语言是独特的，即多收集系统包括一个组合，天线信号和代理不同的化学物质作用，煽动其他人。控制自己的蚂蚁独特的环境的能力，是获得社会行为在其不断发展的高级形式的过程。2.2蚂蚁的觅食策略在自然界中，蚂蚁的食物来源是随机分布在鸟巢周围。经过仔细观察，我

4、们可以发现，经过一段时间后，蚂蚁可以从蚁巢到食物源的最短路径中找到。单个蚂蚁的能力和智慧是非常简单的，但它们之间相互配合，分工，两个工人和王后的合作是不可能有足够的命令筑巢，觅食，完成迁移能力，如打扫巢穴的复杂的行为，如觅食的蚂蚁可以通过相互的合作关系的食物来源和巢形成路径几乎是直的。62.3蚁群算法的思想起源蚁群算法基本模型最初是由意大利学者提出dorigM等于在法国，在1991日举行的第一届欧洲人工生命会议上，巴黎：1992dorigM在他的博士论文中进一步阐述了蚁群算法的核心理念。蚁群算法是受自然界中真实蚂蚁的集体行为而提出的，它的很多观

5、点都来源于真实的蚂蚁，所以定义算法的人工蚂蚁和蚂蚁都很相似，但也有真正的蚂蚁的特点没有；1）人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个状态的转换货2）人工蚂蚁具有一个记忆其本身过去行为的内在状态参数3）人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问题中人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每做出一步选择就更改信息量，但无论哪种方法，信息量的更新并不是随时都可进行的。4）人工蚂蚁存在于一个与时间无关联的环境之中。为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优化、回退等，这些行

6、为在真实蚂蚁中是不存在的。在很多具体应用中，人工蚂蚁可在局部优化过程中相互交接信息，还有一些改进蚂蚁算法中的人工蚂蚁可实现简单预测。6第三章基于蚁群算法的集合覆盖问题求解3.1集合覆盖问题描述集合覆盖问题是一个最优化问题，它模型化了许多资源选择问题，已经被证明是NP难度的。集合覆盖问题是一个实例（X，F）由一个有穷集X和一个X的子集族F构成，且X的每一个元素属于F中的至少一个子集：我们说S∈F覆盖了它的元素。这个问题的目的是要找到一个最小规模子集C属于F，使其所有成员覆盖X的所有成员：我们说任何满足方程的C覆盖X。图3.1是集合覆盖的一个例子，

7、C的规模被定义为它所包含的集合数，而不是这些集合中的元素数。容易看出上式中最小解集规模为3，分别是S3、S4、S5。为了便于用数学工具来描述集合覆盖问题，通常将集合覆盖模型抽象成矩阵形式来表示。例1设S={0，1，2，3，4，5，6，7，8，9，10，11}；S1={0，1，2，3，4，5}；S2={4，5，7，8}；S3={0，3，6，9}；S4={1，4，7，10}；S5={2，5，8，11}；6用矩阵的，第i（1≤i≤12）行表示有穷集S中的第i个元素，第j（1≤j≤5）列表示子集Sj.矩阵元素Cij=1表示子集Sj包含集合S中的第i个元

8、素，可称j列覆盖了i行政反之，表示子集Si不包含集合S中的元素，j列不覆盖i行。按上述方法例1的集合覆盖模型可以抽象成如图3.2的矩阵形式，本文称此矩