一种遗传算法在集合覆盖问题中的应用研究

组合优化问题中的遗传算法优化策略研究随着数字化和自由化程度的不断提升，数据信息与大数据应用的范围也越来越广泛，越来越多的计算问题变得越来越复杂，解决这些复杂问题需要更为先进的方法。

组合优化问题是这些计算问题当中非常重要的一个类别，大量的现实世界中的问题，如资源的分配、路径的规划、任务的调度等等，都会被转化成组合优化问题来进行描述。

遗传算法是组合优化问题中一个非常重要且有效的优化策略。

本文将对遗传算法在组合优化问题中的优化策略进行研究和探究，主要分为以下几个方面：首先，简述组合优化问题的基本概念，介绍组合优化问题在实践应用中的重要性和难点；其次，介绍遗传算法作为组合优化问题的一种优化策略，对其优点和缺点进行分析；然后，详细介绍遗传算法的基本过程和原理，并提出针对组合优化问题的遗传算法优化策略，包括变异算子、交叉算子等等；最后，对遗传算法在组合优化问题中的应用进行深入探究，并给出实例。

一、组合优化问题的基本概念组合优化问题是指一类求解最佳组合的问题。

其中组合是指在许多元素中选取某些元素，而优化是指在这些元素中找到最佳的组合方案。

组合优化问题广泛应用于人工智能、运筹学、排队论、生产管理等领域。

如旅行商问题、背包问题、最大团问题、最大匹配问题、最小割问题等都是组合优化问题。

组合优化问题的难点在于空间搜索和计算时间。

由于搜索空间通常是指数级别的，如旅行商问题的搜索空间为(N-1)!/2，其中N代表城市的个数。

因此搜索时间会非常长，但是很难保证能够找到全局最优解。

这是应该采用一些高效的优化算法。

二、遗传算法作为组合优化问题的一种优化策略相比于传统的优化算法，遗传算法是一种复杂且难以理解的算法。

遗传算法是一类通过模拟自然界演化过程进行优化搜索的算法，它是基于生物遗传进化过程而产生的一套优化算法。

它通过模拟基因，以及基因的交叉、变异等过程，从而搜索出最优的解。

遗传算法的优点在于可以解决大型复杂的问题，搜索空间大，到达全局最优解的可能性比较高。

络生命 周期 达 到最 大 ， 且 也 证 明该 问题 是 Ｎ 并 Ｐ—
Ｃ ｍ ｌｅ的 问 题 ， 提 出 以线 性 规 划 （ ｉｅｒＰｏ ｏ ｐｅ ｔ 并 Ｌｎａ ｒ．
关于覆 盖 问题 研 究 已有 大 量 文 献 报 道 ， 文
ｇ ｍ ｉ ，Ｐ 为基础的启发式演算法与集 中式算 ｒ ｍｎ Ｌ ） ａ ｇ 法。文献［ ］ ４ 对覆盖提出连通性要求 即不仅要满足 覆盖要 求同时还要 满足连通 性 ， 同样该 问题 同属
（ ｕ ｅ ｅｓ ｎＢ ａ ｃ ， ｉｎ ｘ ｒ ｖ ｃ ｌ ｌ ｔｉ Ｐ ｗ ｒＣ ． Ｎａ ｃ ａ ｇ３０ ９ ， ｈｎ ） Ｓ ｐ ｒＴ ｎｉ ｒｎ ｈ Ｊａ ｇｉ ｏ ｉ ｉ ｅ ｒ ｏ ｅ ｏ ， ｎ ｈｎ ３０ ６ Ｃ ｉａ ｏ Ｐ ｎ ａＥ ｃ ｃ
Ａｂ ｔ ａ ｔ Ｃ ｖ ｒ ｇ ｏ ｔ ｌｉ ｔ ｅ ｏ ｅ ｏ ｆ ｃ ｖ ａ ｓｔ ｘ ｅ ｄ ｔ ｅ ｌ ｅｉ ｆｗ ｒ ｌ ｓ ｅ ｓ ｒｎ ｔ ｒ ｓｒ ｃ ： ｏ ｅ ａ ｅ ｃ ｎ ｒ ｈ ｎ ｆｅ ｅ ｔ ｅ ｗ ｙ ｏ ｅ ｔｎ ｈ ｉ ｔ ｏ ｓ ｉ ｆ ｍｅ ｏ ｉ ｅ ｓ ｓ ｎ ｏ ｅｗｏ ｋ ｅ
Ｃｏ ｅａ ｅｏ ｔ ｚ ｔ ｎｂ ｓｄｏ ｅ ｅａｇ ｒ ｈ ＧＡ）ｎ ｖ ｒｇ ｐｉ ａｉ ａｅ ｎ ｇ ｎ ｌｏｉ ｍ（ ｍｉ ｏ ｔ ｉ
ｗｉ ｅ ｅ ｓ ｓ ｎ ｏ ｅ ｗｏ ｋ ｒ ｌｓ ｅ ｓ ｒ ｎ ｔ ｒ
Ｚ ＨＯＮＧ ｕ ｐ ｎ Ｙｏ — ｉ ｇ，ＨＥ Ｗ ｅ —ｉ ｉｌ，Ｗ ＡＮＧ ａ ｇ ｈ ａ ｇ，Ｗ ＡＮＧ —ｈ ｎ Ｇｕ ｎ — ｕ ｎ Ｚｉｚ ａ
ａ ｏ ｔｍ ｂ ｓｄ ｏ ｅ ｅ ａｇｒ ｍ （ Ａ） ｈ ｓｂ ｅ ｒｐｓｄ ａｄ ｒａｉ ｄ ｉ ｄｔｉ ｈｏ ｇ ｅ ｌ ｒｈ ａｅ ｎ ｇｎ ｌ ｉ ｇｉ ｏｔ ｈ Ｇ ａ ｅｎ ｐｏ ｏｅ ｎ ｅｌｅ ｎ ｅ ｌ ｚ ａ ．Ｔ ｒｕｈ ｔ ｈ

2013，49（17）1引言集合覆盖问题是组合最优化和理论计算机科学中的一类典型问题，它要求以最小代价将某一集合利用其若干子集加以覆盖。

在现实生产生活中，集合覆盖问题有着众多应用场合，如物流配送、道路定向、工程调度、设施选址、VLSI 设计、网络安全等[1-2]。

遗憾的是，集合覆盖问题在算法复杂性上属于NP-困难问题[3]，即它不存在多项式时间精确算法，除非P=NP 。

因此，近似算法成为求解集合覆盖问题的一个有效途径，其中以Chvátal 的贪心算法[4-5]最为简洁。

后来，学者们又陆续提出过一些近似程度更好的近似算法[6]。

近似算法固然是多项式时间算法，但返回的往往不是最优解，这在许多实际领域当然是不能令人满意的。

事实上，在实际计算中，如果问题的规模相对较小，那么利用一般的线性规划或整数规划方法还是可以较为快速地得到其最优解的。

随着计算机科技的迅猛发展，特别是LINGO 、MATLAB [7-9]等高性能计算软件的成功研发与广泛应用，即便在问题的规模相当大时，人们也仍然能够迅速地求得其最优解。

2问题与模型设基集S ={e 1 e 2 e n }，S 1 S 2 S m 是S 的一族子集，若J Í{1 2 m }，且j ÎJS j =S ，则称{}S j j ÎJ为S 的一个集合覆盖。

问题：求S 的一个基数最小的集合覆盖，其中基数定义为集合中元素的数目。

事实上，{}S jj ÎJ为S 的一个集合覆盖，意指S 中的每一元素都至少含于某一集合S j (j ÎJ )中，即被S j“覆盖”住。

对每一子集S j (j =1 2 m )，引入决策变量：x j ={1 j ÎJ0 否则则可建立如下集合覆盖问题的0-1规划模型IP ：min åj =1mx j s.t.åj :e i ÎS jx j 1 i =1 2 nx j =0 1 j =1 2 m其中约束条件“åj :e i ÎS jx j 1 i =1 2 n ”确保S 中的每一元素e i 都至少被集合覆盖S j (j ÎJ )中的某一集合覆盖住。

DNA遗传算法的集成研究与应用作为进化计算最重要的一个分支, 遗传算法在许多领域已经获得大量的研究但发展到现在仍然存在很多缺陷。

遗传算法进化到后期, 种群中的个体相似度较高,无法对解空间做进一步的搜寻, 导致算法早熟收敛。

遗传算法的局部搜索能力较弱, 在最优解附近需要花费较长时间才能得到问题的全局最优解。

而且, 传统遗传算法一般采用二进制编码方式, 这种编码方法不能表达丰富的生物遗传信息, 在计算模型中无法反映遗传信息对生物体生长、发育的调制作用,尤其是起关键控制作用的DNA编码机制。

自从Adleman提出DNA计算理论开始,基于DNA计算的智能系统开始引起研究人员的注意, 它能够更好的反映生物体的遗传信息, 从而建立功能更强、效率更高的智能计算模型。

受此启发, 研究者们开始尝试进一步分析和模仿生物遗传信息的调控功能, 建立分子水平上的遗传信息模型。

基于这种思想,学者们提出了DNA®传算法。

这种算法将遗传算法与DNA计算相结合,在DNA S码方式的基础上对种群中的个体进行遗传操作，从而更好地模拟生物的遗传机理和遗传信息表达机制。

DNA S传算法的结构与一般遗传算法基本上类似,主要区别在于DNA S传算法采用DNA S码方式，并基于这种编码方式发展众多的生物遗传操作模拟进化过程,得到问题的解。

由于DNA®传算法是建立在遗传算法的框架上，因而继承了传统遗传算法的诸多优点, 具有优良的全局搜索性能及隐性并行性等。

但与传统遗传算法相比，DNA遗传算法在编码方式上有较大的改进，更适合于表达复杂知识, 方法灵活, 编码精度高。

丰富的编码及译码特性, 使得种群可以在变异概率低的情况, 仍保持一定水平的多样性。

同时由于引入复杂的基因级的操作, 可以发展更多更有效的遗传操作算子如倒位、分离、异位等, 进一步丰富遗传操作。

本文在前期大量工作的基础上, 对DNA遗传算法及应用开展了更进一步的研究,主要研究工作如下：(1)提出了一种新颖的三联核苷酸编码的DNA遗传算法-GA-TNE+DRO依据生物进化机制,通过模拟DNA在氨基酸水平上的繁殖过程来模拟DNA分子的遗传操作，在解空间中创建新的个体。