【摘 要】
：
最大独立集问题(Maximum Independent Set problem,MIS)是图论中经典的组合优化问题.该文综述了国内外学者对此问题的研究成果,包括该问题的应用背景,界的估计,求解的难点及
论文部分内容阅读
最大独立集问题(Maximum Independent Set problem,MIS)是图论中经典的组合优化问题.该文综述了国内外学者对此问题的研究成果,包括该问题的应用背景,界的估计,求解的难点及现代优化算法的设计.通过对遗传算法的研究,并模拟了生物个体的成长机制,该文提出了一种新的启发式算法——成长算法(Grown-Up Algorithm,简称GUA).该算法将组合最优化问题解的演进分为诞生和成长两个阶段,诞生阶段产生一个近似解,成长阶段让这个近似解象生物个体一样成长为一个满意解,并且诞生和成长均在确定性和随机性的双机制作用下演进变化.与遗传算法相比,其主要特点是利用诞生算子强化了遗传算法的初始化过程,利用成长算子使解的进化有了定向的机制.该文主要研究了GUA在MIS问题中的应用,详细探讨了诞生算子和成长算子的构造,算法的效能分析等,并在DIMACS图上进行了测试,取得了良好的效果,表明了GUA有效的运行机制,值得进一步研究.
其他文献
本文首先介绍凸体几何的发展历史和主要分支。本硕士论文主要以对偶Brunn-Minkowski理论中的基本事物：相交体和混合相交体为研究对象，利用几何分析的渐进理论、局部理论和积分
该文对其原因进行分析,并提出一种局部回溯的策略,不但考虑了所选属性和已入选属性集之间的相关性,而且对未入选属性集之间的相关性也加以考虑.对于本质上不重要的属性,即使
该文分成两部分.第一部分对有理插值样条有关问题进行了分析,并在此基础上构造了一种带参数的分母为线性的四次有理插值样条.事实上,这种有理插值样条曲线是C连续的四次多项
具有奇异系数的抛物方程是近年来在核物理、气体动力学、流体力学、边界层理论、非线性场和光学等实际问题中提出的一类重要方程,数值分析和求解该类方程具有重要意义,许多专
本文对两类全局优化算法(填充函数法和区间算法)作了比较深入的研究,在此基础上对这些算法作了进一步的推广和应用,取得了较为满意的结果,主要内容如下:在已有的填充函数法的
图论中，决定图的不变量的取值范围和极值图是一个非常重要并且活跃的研究课题.一般来说，对于多种图类(特别是树类)，关于子树个数的极大（小）值的图恰好对应一些化学指数(如 Wiener
本文首先对数据包络分析(DEA)理论，方法和应用进行了探讨，介绍了基本DEA模型、DEA有效性理论以及DEA方法的基本思想，在此基础上，详细分析了DEA方法的特点和优越性；其次，本文探讨了