论文部分内容阅读
摘要：集合覆盖问题已被证明是一个NP完全问题，现在所有的NP完全问题，没有多项式时间算法求解。目前为集合覆盖问题的主要的近似算法，复杂或大型集合覆盖问题，现有的算法很难达到理想的优化效果。
蚁群算法是基于群体智能的进化算法为基础的小说，关注个体的蚂蚁之间的合作，利用信息素正反馈机制，具有很强的寻找更好的解决方案的能力。蚁群算法已成功地应用在许多复杂的优化问题，其优化能力提供了一种新的思路来解决集合覆盖问题。蚁群算法具有耗时长、易陷入局部最优解的缺点。
关键词：NP完全问题 蚁群算法 群体智能
第一章研究背景
集合覆盖问题是一个NP问题，NP问题是计算机算法理论最深刻的问题，因为所有的NP完全问题，没有多项式时间算法求解。集合覆盖问题是非常广泛的，许多学者提出了优化算法的集合覆盖问题。这些算法的近似算法，根据具体问题的特点设计的，特别是问题可以得到较为理想的优化结果。
第二章 蚁群算法
2.1蚂蚁的基本习性
蚂蚁是一种最古老的社会性昆虫，其起源可以追溯到100000000年前，大约相同的恐龙时代。像人类一样，悄悄地与我们的星球亿蚂蚁数以百万计，几乎占据了所有可居住的土地，只有永恒的雪不信的南北足。虽然有成千上万的蚂蚁，但没有一个是生活，是生活在群体中，建立了自己独特的蚂蚁社会。虽然单个蚂蚁是相对简单的，但整个殖民地的代表是作为社会组织机构的高度，可以完成比在许多情况下，蚂蚁个体能力复杂的任务。蚂蚁社会个人从事不同的劳动，组织可以在劳动分工执行个体。蚂蚁的社会成员的组织分工除外，和相互通信和信息传输。蚂蚁有一个独特的信息系统，包括视觉信号，语音通信和更多的无声的语言是独特的，即多收集系统包括一个组合，天线信号和代理不同的化学物质作用，煽动其他人。控制自己的蚂蚁独特的环境的能力，是获得社会行为在其不断发展的高级形式的过程。
2.2蚂蚁的觅食策略
在自然界中，蚂蚁的食物来源是随机分布在鸟巢周围。经过仔细观察，我们可以发现，经过一段时间后，蚂蚁可以从蚁巢到食物源的最短路径中找到。单个蚂蚁的能力和智慧是非常简单的，但它们之间相互配合，分工，两个工人和王后的合作是不可能有足够的命令筑巢，觅食，完成迁移能力，如打扫巢穴的复杂的行为，如觅食的蚂蚁可以通过相互的合作关系的食物来源和巢形成路径几乎是直的。
2.3蚁群算法的思想起源
蚁群算法基本模型最初是由意大利学者提出dorig M等于在法国，在1991日举行的第一届欧洲人工生命会议上，巴黎：1992 dorig M在他的博士论文中进一步阐述了蚁群算法的核心理念。蚁群算法是受自然界中真实蚂蚁的集体行为而提出的，它的很多观点都来源于真实的蚂蚁，所以定义算法的人工蚂蚁和蚂蚁都很相似，但也有真正的蚂蚁的特点没有；
1）人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个状态的转换货
2）人工蚂蚁具有一个记忆其本身过去行为的内在状态参数
3）人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问题中人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每做出一步选择就更改信息量，但无论哪种方法，信息量的更新并不是随时都可进行的。
4）人工蚂蚁存在于一个与时间无关联的环境之中。
为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工蚂蚁可在局部优化过程中相互交接信息，还有一些改进蚂蚁算法中的人工蚂蚁可实现简单预测。
第三章 基于蚁群算法的集合覆盖问题求解
3.1集合覆盖问题描述
集合覆盖问题是一个最优化问题，它模型化了许多资源选择
问题，已经被证明是NP难度的。集合覆盖问题是一个实例（X，F）由一个有穷集X 和一个X的子集族F构成，且X的每一个元素属于F中的至少一个子集：
我们说S∈F覆盖了它的元素。这个问题的目的是要找到一个最小规模子集C属于F，使其所有成员覆盖X的所有成员：
我们说任何满足方程的C覆盖X。图3.1是集合覆盖的一个例子，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}；
用矩阵的，第i（1≤i≤12）行表示有穷集S中的第i个元素，第j（1≤j≤5）列表示子集Sj.矩阵元素Cij=1表示子集Sj包含集合S中的第i个元素，可称j列覆盖了i行政反之，表示子集Si不包含集合S中的元素，j列不覆盖i行。按上述方法例1的集合覆盖模型可以抽象成如图3.2的矩阵形式，本文称此矩阵为覆盖矩阵C。
例1中的集合覆盖问题转换成图3.2所示覆盖矩阵形式后，在集合覆盖问题中通常定义5维布尔向量y=（y1，y2，…，y5）T，yj=1（1≤j≤5）表示第j列被选中，yj=0表示第j列被排除。从而集合覆盖问题的优化可按以下等价的方式描述：
为例1中的各子集Sj配一个权重值wj，则带权重的集合覆盖问题可以用如下数学方式描述：
满足：C.Y≥1，Y∈{0，1}5.
在很多实际问题中，为了更好的利用具体问题的有效信息，一般考虑把能反映问题特性的信息量作为权重值，然后对带权重的集合覆盖模型进行优化。
集合覆盖问题模型有极其广泛的应用，在实际问题中经常会遇到，目前优化集合覆盖问题的一些近似算法，对于复杂的或规模较大的集合覆盖问题的优化效果不太理想。
参考文献：
[1]M.R Garey and DS Johnson.Computer and Intractability：A Guide to the Theory of NP-Completemess.San Francisco：W.H.Freeman，1979.
[2] Christian Plessl and Marco Platzner.Custom Computing Machines for Set Covering Problem.10th Annual IEEE Symposium on Field-Programmable Custom Computing machines（FCCM’02），2002.
蚁群算法是基于群体智能的进化算法为基础的小说，关注个体的蚂蚁之间的合作，利用信息素正反馈机制，具有很强的寻找更好的解决方案的能力。蚁群算法已成功地应用在许多复杂的优化问题，其优化能力提供了一种新的思路来解决集合覆盖问题。蚁群算法具有耗时长、易陷入局部最优解的缺点。
关键词：NP完全问题 蚁群算法 群体智能
第一章研究背景
集合覆盖问题是一个NP问题，NP问题是计算机算法理论最深刻的问题，因为所有的NP完全问题，没有多项式时间算法求解。集合覆盖问题是非常广泛的，许多学者提出了优化算法的集合覆盖问题。这些算法的近似算法，根据具体问题的特点设计的，特别是问题可以得到较为理想的优化结果。
第二章 蚁群算法
2.1蚂蚁的基本习性
蚂蚁是一种最古老的社会性昆虫，其起源可以追溯到100000000年前，大约相同的恐龙时代。像人类一样，悄悄地与我们的星球亿蚂蚁数以百万计，几乎占据了所有可居住的土地，只有永恒的雪不信的南北足。虽然有成千上万的蚂蚁，但没有一个是生活，是生活在群体中，建立了自己独特的蚂蚁社会。虽然单个蚂蚁是相对简单的，但整个殖民地的代表是作为社会组织机构的高度，可以完成比在许多情况下，蚂蚁个体能力复杂的任务。蚂蚁社会个人从事不同的劳动，组织可以在劳动分工执行个体。蚂蚁的社会成员的组织分工除外，和相互通信和信息传输。蚂蚁有一个独特的信息系统，包括视觉信号，语音通信和更多的无声的语言是独特的，即多收集系统包括一个组合，天线信号和代理不同的化学物质作用，煽动其他人。控制自己的蚂蚁独特的环境的能力，是获得社会行为在其不断发展的高级形式的过程。
2.2蚂蚁的觅食策略
在自然界中，蚂蚁的食物来源是随机分布在鸟巢周围。经过仔细观察，我们可以发现，经过一段时间后，蚂蚁可以从蚁巢到食物源的最短路径中找到。单个蚂蚁的能力和智慧是非常简单的，但它们之间相互配合，分工，两个工人和王后的合作是不可能有足够的命令筑巢，觅食，完成迁移能力，如打扫巢穴的复杂的行为，如觅食的蚂蚁可以通过相互的合作关系的食物来源和巢形成路径几乎是直的。
2.3蚁群算法的思想起源
蚁群算法基本模型最初是由意大利学者提出dorig M等于在法国，在1991日举行的第一届欧洲人工生命会议上，巴黎：1992 dorig M在他的博士论文中进一步阐述了蚁群算法的核心理念。蚁群算法是受自然界中真实蚂蚁的集体行为而提出的，它的很多观点都来源于真实的蚂蚁，所以定义算法的人工蚂蚁和蚂蚁都很相似，但也有真正的蚂蚁的特点没有；
1）人工蚂蚁存在于一个离散的空间中，它们的移动是从一个状态到另一个状态的转换货
2）人工蚂蚁具有一个记忆其本身过去行为的内在状态参数
3）人工蚂蚁不是完全盲从的，它还受到问题空间特征的启发。例如有的问题中人工蚂蚁在产生一个解后改变信息量，而有的问题中人工蚂蚁每做出一步选择就更改信息量，但无论哪种方法，信息量的更新并不是随时都可进行的。
4）人工蚂蚁存在于一个与时间无关联的环境之中。
为了改善算法的优化效率，人工蚂蚁可增加一些性能，如预测未来、局部优化、回退等，这些行为在真实蚂蚁中是不存在的。在很多具体应用中，人工蚂蚁可在局部优化过程中相互交接信息，还有一些改进蚂蚁算法中的人工蚂蚁可实现简单预测。
第三章 基于蚁群算法的集合覆盖问题求解
3.1集合覆盖问题描述
集合覆盖问题是一个最优化问题，它模型化了许多资源选择
问题，已经被证明是NP难度的。集合覆盖问题是一个实例（X，F）由一个有穷集X 和一个X的子集族F构成，且X的每一个元素属于F中的至少一个子集：
我们说S∈F覆盖了它的元素。这个问题的目的是要找到一个最小规模子集C属于F，使其所有成员覆盖X的所有成员：
我们说任何满足方程的C覆盖X。图3.1是集合覆盖的一个例子，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}；
用矩阵的，第i（1≤i≤12）行表示有穷集S中的第i个元素，第j（1≤j≤5）列表示子集Sj.矩阵元素Cij=1表示子集Sj包含集合S中的第i个元素，可称j列覆盖了i行政反之，表示子集Si不包含集合S中的元素，j列不覆盖i行。按上述方法例1的集合覆盖模型可以抽象成如图3.2的矩阵形式，本文称此矩阵为覆盖矩阵C。
例1中的集合覆盖问题转换成图3.2所示覆盖矩阵形式后，在集合覆盖问题中通常定义5维布尔向量y=（y1，y2，…，y5）T，yj=1（1≤j≤5）表示第j列被选中，yj=0表示第j列被排除。从而集合覆盖问题的优化可按以下等价的方式描述：
为例1中的各子集Sj配一个权重值wj，则带权重的集合覆盖问题可以用如下数学方式描述：
满足：C.Y≥1，Y∈{0，1}5.
在很多实际问题中，为了更好的利用具体问题的有效信息，一般考虑把能反映问题特性的信息量作为权重值，然后对带权重的集合覆盖模型进行优化。
集合覆盖问题模型有极其广泛的应用，在实际问题中经常会遇到，目前优化集合覆盖问题的一些近似算法，对于复杂的或规模较大的集合覆盖问题的优化效果不太理想。
参考文献：
[1]M.R Garey and DS Johnson.Computer and Intractability：A Guide to the Theory of NP-Completemess.San Francisco：W.H.Freeman，1979.
[2] Christian Plessl and Marco Platzner.Custom Computing Machines for Set Covering Problem.10th Annual IEEE Symposium on Field-Programmable Custom Computing machines（FCCM’02），2002.