启发式算法求解最大团问题研究

最大团问题(maximum clique problem,MCP)是图论中的一个经典组合优化问题,也是一类NP完全问题,在国际上已有广泛地研究,国内研究刚刚起步.给出了最大团问题的基本定义和其数学描述;阐述了该问题的研究进展;分析和研究了求解该问题的各种典型启发式算法,包括算法的介绍、算法求解最大团问题的基本思路、特点及性能;最后介绍了测试这些启发式算法性能的测试基准图.     

一种求解最大团问题的自适应过滤局部搜索算法

提出了一种求解最大团问题的自适应过滤局部搜索算法AF-RLS(adaptive filtered-reactive local search).该算法通过构建独立集约束,优选出有希望的邻域移动方向来提高局部搜索趋向最优解的概率;并在比较分析两种不同逃逸策略的逃逸能力和逃逸代价的基础上,提出了基于问题解空间结构自适应设置...     

基于蚁群算法求解最大团问题

最大团问题是一种典型的NP完全问题, 是图论中一个经典的组合优化问题.研究将蚁群算法应用于求解最大团问题,提出一种求解最大团问题蚁群算法.通过定义最大团问题蚁群算法中的各元素,并改进了蚂蚁搜索解的方法,有效地改善蚁群算法易于过早地收敛于局部最优解的缺陷.仿真实验表明,图中的顶点数较多时,也取得了较好的结果.     

最大团问题研究进展及算法测试标准

定义了最大团问题,分析和研究了使用启发式算法求解最大团问题的进展,介绍了当前求解最大团问题的典型启发式算法,最后给出了测试这些启发式算法性能的测试基准图.     

最大团问题的改进遗传算法求解

最大团问题是组合优化中经典的NP完全问题,该问题的枚举算法只适用于求解中小规模的图。提出了基于遗传算法的最大团问题求解算法,引入概率模型指导变异产生新的个体,并结合启发式局部算法搜索最大团。经算例测试,获得了较好的效果。     

一种基于匹配交叉求解最大团问题的Memetic算法

针对基于适应值的选择交叉机制在优化具有欺骗性的最大团问题中性能退化的问题,提出一种新的基于匹配交叉的Memetic算法.该算法提出交叉匹配度的概念,用来估计两个体交叉所能获得的最佳适应值.通过匹配度的计算对交叉方向的选择进行控制,保证了交叉操作以较大的概率生成新的优良模式.在40个最大团问题标准算例上的测试结果表明,新算法优于目前在最大团问题求解中性能最好的多阶段动态局部搜索算法.     

低度图的最大团求解算法

在图的最大团问题中,当图的顶点数不大于阈值m时,很容易求解其最大团问题,求解算法的时间复杂度为O(d)。给出一种求解低度图的最大团的确定性算法。该算法通过对图按顶点逐步分解实现分别计算,较好地解决低度图的最大团问题。算法时间复杂度为O(d•n3)。其中,n表示图的顶点数,图中顶点的最大度小于m或者图可以通过逐个删除度小于m的顶点而使所有顶点的度都小于m。     

最大团问题降阶算法

最大团问题是找出给定图中的一个最大结点子集合,使得子集合中的任意两点之间都有边相连,最大团问题是一个著名的NP-难题,在很多领域中都有着广泛的应用.本文在研究最大团问题数学性质的基础上给出该问题的一个初步降阶方法;在初步降阶的基础上给出一个求解最大团问题的上、下界方法;最后将降阶方法和上下界方法结合起来形成一个全新的降阶算法,该算法不仅可以单独使用,还可以与其它算法结合起来使用达到更好的效果.在文中还介绍了本算法和其它各类算法的优缺点,最后通过多个示例来进一步说明算法的原理及应用情况.     

求解最大团问题的均匀设计抽样免疫遗传算法

针对遗传算法在最大团求解中保持群体多样性能力不足、早熟、耗时长、成功率低等缺陷,依据均匀设计抽样理论对交叉操作进行重新设计,结合免疫机理定义染色体浓度设计克隆选择策略,提出求解最大团问题的均匀设计抽样免疫遗传算法。仿真算例表明,该算法在解的质量、收敛速度等各项指标上均有提高,与DLS-MC、QUALEX等经典搜索算法相比,对部分算例能得到更好解。     

求解图着色问题的最大最小蚁群搜索算法

针对图着色问题在传统的启发式蚁群算法的基础上提出了一种最大最小蚂蚁系统搜索算法,最大最小蚁群系统将正反馈、分布式计算特点与启发式算法思想有效的结合起来,可以改进信息素更新策略和引入了信息素平滑机制,使得加快了求解的收敛速度,又有效的避免了启发式算法易陷入局部最优。通过给中国地图着色的仿真实验结果表明,方法对图着色问题的求解是可行、有效的;并通过大量的实验证明了算法在求解的效率和求解的稳定性方面优于传统的蚁群算法。     

求解SAT问题的分级重排搜索算法

局部搜索法在ＳＡＴ问题上的成功运用已引起越来越广泛的重视,然而,它在面对不可满足问题例时的局限性不能不被考虑．分级重排搜索算法ＭＳＲＡ（ｍｕｌｔｉ－ｓｔａｇｅｓｅａｒｃｈｒｅａｒｒａｎｇｅ－ｍｅｎｔａｌｇｏｒｉｔｈｍ）正是为克服局部搜索法的不完备性而提出的,准确地讲,它是几种算法在思想上的集成,但为明确起见,把其最典型的分级重排过程作为名称．分级重排搜索算法在求解ＳＡＴ问题时,能表现出优于单一求解策略（如局部搜索法或回溯算法）的明显特性．由于可根据约束条件的强弱来估计ＳＡＴ问题例的可满足性,因此能够以此来确定更有效的求解策略．     

多因素问题的启发式搜索算法MFRA

本文新定义了一类多因素启妇式搜索问题，提出了适于此类问题求解的启发式搜索算法ＭＦＲＡ。文中研究了算法ＭＦＲＡ的可采纳性质，单调限制性质和比较性质等。基于算法ＩＤＡ的思想，提出了ＭＦＲＡ的改进算法ＭＦＲＡ－ＩＤＡ，这一算法具有线性存储空间这一重要特性。     

结合遗传算法和设禁搜索求解可重构制造系统的生产计划问题

针对可重构制造系统的生产计划问题提出了一种采用遗传算法与设禁搜索相结合的方法.文中将该类问题用含有模糊数的整数规划问题进行建模,算法采用遗传算法作为算法的框架结构,将设禁搜索和模糊规则结合在种子的变异过程之中.通过数学仿真,可以得到一个很满意的结果.     

基于单纯形算子的混合遗传算法

通过遗传算法（GA）与传统单纯形搜索法相结 合,并基于对遗传算法算子计算结构的调整,提出一种针对非线性规划问题的新算法——基 于单纯形算子的混合遗传算法（HGA）,仿真结果验证了这种新算法的有效性和合理性．     

一种混合局部搜索算法的遗传算法求解旅行商问题

针对遗传算法容易产生早熟现象以及局部寻优能力较差的缺点,提出一种求解旅行商问题的高效混合遗传算法。该算法首先用加权最近邻法产生初始种群,对种群中相同的个体,用K-近邻法产生新的个体代替相同的个体,然后淘汰适应性较差的个体,用交叉操作产生新的个体,最后,对部分个体进行3-opt优化变异,对种群中优秀个体用改进的Lin-Kernighan算法进行优化。对TSPLIB中部分实例的仿真结果表明,所提出的混合局部搜索算法的改进遗传算法在求解TSP问题时可以高效地获得高质量的解。     

基于链接相似度Web挖掘算法的研究与改进

在Web挖掘分类模式基础上,研究和分析了基于链接分析的Web结构挖掘算法HITS(Hyperlink induced topic Search)。针对HITS算法在获取拓展集处理过程中只考虑基于根集网页链接出、入网页,不考虑出、入网页相似度的不足之处,提出了一种改进的DS-HITS(Document Similarity hyperlink induced topic search)算法。该算法在拓展集处理过程中引进多种反映网页相似度的权值,从而使获取的网页在核心和权威值方面明显得到改进。最后,基于Webla开源项目初始数据,对比了DS-HITS算法和HITS算法的搜索结果。     

一种基于启发式搜索的论文元数据提取算法

随着大量的科研论文以电子文档的形式出现, 为了高效地检索这些科研文献资料,从中精确地抽取这些论文头部的元数据信息显得十分有必要.在条件随机场模型的基础上,提出了一种启发式搜索算法来对论文头部的元数据信息进行提取.该算法首先利用文本分块技术和特征提取规则来对文本进行预处理,然后结合条件随机场概率模型利用启发式搜索来进行元数据的提取.实验结果表明,在相同概率模型的基础上,该算法有着较好的性能,在精确度和召回率方面都有了明显的提高.     

一种混合智能算法用于求解含保序约束的JSP

针对车间调度中计算复杂度问题,提出将神经网络嵌入遗传算法中,在初始化序列时考虑到工件中工序的加工顺序,采用基于保序的方法来对染色体进行交叉和变异。实验仿真表明,该算法能够获得比较理想的加工序列,在指定的代数内能够收敛于优值。