一种求解最大团问题的化学反应算法

最大团问题是在给定的一个图中寻找一个顶点数最大的顶点子集S,使得S中任意2个顶点都相邻,是一个著名的NP完全问题.提出一种带有局部搜索策略的化学反应算法求解最大团问题.为了提高算法的性能,在化学反应算法的分子碰撞阶段引入分子亲和度,使得碰撞后的分子倾向于得到对应于最大团较大的分子.将不相交的Golomb尺问题转化为最大团问题实例,通过求解最大团问题,得到若干不相交的Golomb尺问题的新结果.     

基于分治策略和蚁群算法的最大团问题的研究

最大团问题是经典的NP-hard问题,对该问题求解方法的研究在理论上、实践上都具有一定的意义.蚁群算法已成功地求解出许多组合优化难题.通过使用分治法,将图分解成子图,对各子图应用蚁群算法求解,提出一种求解最大团问题的蚁群算法.它减小了问题的求解规模,使求解变得容易,且实验取得了较好的结果.     

基于DNA计算的最大权团问题设计

介绍了最大团和最大权团的概念和国内外学者运用DNA计算解决最大团的研究成果;结合前人运用质粒、二进制、粘贴模型等方式进行DNA计算操作的原理,设计了新的用于解决最大权团问题的算法步骤,大大提高了算法效率,实现了最大团和最大权团的同步求解,对市场分析、方案选择等领域有一定的意义。     

一种求解最大独立集的自学习进化算法

为了求解最大独立集问题,通过对求解最大团问题EA/G算法的分析,从初始解选取、种群的构成、遗传策略等方面对EA/G算法进行了改进,提出了自学习进化算法,并在DIMACS基准图上进行了大量的实验.实验结果表明,该算法运算结果比EA/G算法所求结果有很好的改善.     

基于Q0-1规划模型用分枝定界法求解最大团问题

搜索图的最大团是经典的NP-难题。通过运用二次0-1规划模型（简称Q0-1规划模型）寻得最大团问题的解法,所用的分枝定界法建立在此模型之上。通过一个命题推导出图的最大团求解问题与一类特殊Q0-1规划的等价性,借助于求解一般Q0-1规划的分枝定界法推演出求最大团问题的分枝定界规则,从而将图论中的经典问题转化成代数问题加以解决,并给出实例说明该算法的有效性。     

华中科技大学学报(自然科学版) 2017年 第45卷 总目次

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.     

基于Spark的多策略蚁群算法求解最大团问题

社会网络分析目前是数据挖掘领域的研究热点之一,凝聚子群是测量社会网络结构的重要指标,而最大团结构是社会网络中最紧密的凝聚子群,最大团问题的研究也成为社会网络分析的一个重要角度.随着大数据的发展,图中节点的丰富性和边结构的复杂性对求解最大团问题提出了更高的要求.为此提出了一种基于Spark的多策略蚁群算法求解最大团的算法.首先,该算法利用多条件选点策略扩大搜索空间,增加可行解的多样性,避免了陷入局部最优解;然后,采取一个局部搜索策略来提高该算法的精度和收敛速度;最后,在Spark分布式平台上并行地实现了该算法,验证了算法的并行性,证明该算法提高了算法处理大规模社区网络的执行效率.     

大规模稀疏图的极大团枚举算法

将最大团求解算法融入到极大团枚举算法中,提出了两种带极大团下限的极大团枚举算法及多种预处理筛选策略,通过迭代将不可能包含在极大团中的部分点与边删除,使得搜索空间大幅减小.在搜索策略上,将求解最大团问题的贪心染色算法、增量MaxSAT推理算法与极大团枚举算法相融合,并结合最佳筛选策略,提出了染色-关键点融合算法BKFC(Bron-Kerbosch with filtering and coloring)和基于增量MaxSAT推理的枚举算法BKFS(Bron-Kerbosch with filtering and MaxSAT).结果表明:在多个大型算例上,BKFC算法平均时间仅为加入预处理的改进经典算法的68.8%;由于经典算法无法在大型算例上运行,在小数据测试中,BKFC算法平均时间仅为没有预处理策略的经典算法的2.2%.     

求解非线性整数规划全局最优解的填充函数法

提出了一个填充函数,用来求解严格路径连通域上的非线性整数规划全局最优解问题。探讨了该填充函数的理论性质,提出了相应的求解算法,并进行了算例测试。测试结果表明该算法令人鼓舞。     

求解置换流水车间调度问题的布谷鸟算法

分析了布谷鸟算法的优化机理和特点,针对最小化最大完工时间的置换流水车间调度问题,采用基于最小位置值规则的随机键编码方式,应用布谷鸟算法进行求解.通过选取的标准算例对算法进行了仿真测试,并与萤火虫算法和粒子群算法进行对比,测试结果表明了该算法求解置换流水车间调度问题的有效性和优越性.该方法可作为解决流水线生产调度问题的一种有效方法.     

竞争决策算法原理及其应用

全面阐述竞争决策算法的基本概念、原理、算法流程、特点,给出了常用的竞争力函数、决策函数、初始状态、资源交换规则,并以示例来说明该算法的原理、特点及应用。研究内容进一步完善了竞争决策算法的基本理论,在应用方面则降低了算法应用的难度。     

基于快速下界估算的瓶颈旅行商问题竞争决策算法

利用数学推导和证明得出了一个瓶颈旅行商问题下界快速估算法,在此基础上利用竞争决策算法(新型优化思想)的通用模型,给出了一种瓶颈旅行商问题的竞争决策算法,经过大量数据测试和验证,并将求解结果与下界相比较,部分结果与下界相同．     

符号差类运输问题的多项式时间算法

给出符号差类运输问题的一个多项式时间算法,并证明该算法的时间复杂性是Ｏ（ｍｎ＾２＋ｍ＾２ｎ）。     

基于离散粒子群算法的近似最大连通分量抽取

无向图中的最大连通分量抽取(Maximum Clique Problem,MCP)是一种具有重要应用价值的组合优化问题,已被证明属于NP问题．传统的深度优先、分枝限定等算法可以处理规模较小的MCP问题,所以提出处理大规模MCP问题的算法是非常必要的．粒子群优化算法是一种基于群智能的演化计算技术,离散粒子群算法(DiscretePSO)是其中解决离散编码的算法．提出了一种基于离散粒子群算法的近似连通图的抽取算法,通过定义连通图编码、合法随机初始化过程,编码校正算法使得DPSO能够解决最大连通图的抽取问题．为验证其效果及效率,将该算法与RAClique进行了比较．实验结果表明,该算法在解决此类问题时,执行的速度受节点规模变化不大,效率略优于RAClique其他算法．     

一种基于DNA自组装模型求解最大团问题的算法

基于tiles理论模型和已有DNA自组装模型,结合最大团问题给出基于DNA自组装模型的算法设计,得到具体设计初始分子、规则分子和检测分子所需的DAE块种类.在此基础上采用荧光标记和凝胶电泳生物操作提出了一种求解最大团问题算法.该算法设计tiles的种类为Θ(n2+|E|),其生物操作复杂性为Θ(1).此算法降低了实验的复杂度,而且保证了实验的易操作性和结果的准确性。     

遗传算法求解最大团问题研究

最大团问题是NP难解的,用遗传算法求解的关键是如何设计有效的评估函数.首先从理论上分析编码规则及适应函数对个体进化的影响,提出个体基因适应函数和个体适应函数多重评估方法,并设计求解算法.数值实验表明,算法具有较好的通用性和较高的性能.     

基于对称模糊数和最优h值线性回归模型的质量功能展开研究

模糊线性回归参数h决定模糊系数的可能性分布,影响模型的系统可靠性.分析了含有参数p的对称模糊数的模型,得出质量功能展开中具有最优h值的函数关系.当参数p给定时,考虑系统模糊性和系统隶属度两个因素,依据模糊线性回归模型系统可靠性最大的原则,得到最优h值;并将该理论应用于质量功能展开的实例,选取有代表性的3个p值,分别对应二次根型、三角型和抛物型对称模糊数进行讨论,得到对应的最优h值.在最优h值的前提下,分析对应的系统模糊性和可靠性的变化规律,通过对比分析,得到系统可靠性最大的函数关系.     

A dynamic programming algorithm on Project-Gang investment decision-making

The investment decision-making of Project-Gang, the projects that are associated with one another on economy and technique, is studied. In order to find out the best Scheme that can make the maximum profit, a dynamic programming algorithm on the investment decision-making of Project-Gang is brought forward, and this algorithm can find out the best Scheme of distributing them resources to then Items in the time ofO(m ² n). Foundation item: Supported by the Programming of the National Ministry of Education (96JAQ630015) Biography: Xu Xu-song (1945-), female, Professor, research direction: complexity science & project management, complexity science & capital Market.     

对流方程的样条子域精细积分(SSPI)格式

针对对流方程第一类初边值问题,基于子域精细积分的思想,结合三次样条函数逼近,提出一个含参数α(α>0)无条件稳定的样条子域精细积分(SSPI)格式,并进行数值实验.SSPI格式求解对流方程有效,而且局部截断误差为O(ατ2 τ2 h4).SSPI格式不仅能够求解对流方程的第一类边值问题,而且能够求解第二类、第三类初边值问题,是一种有效的算法.