智能搜索算法求解最大团问题研究

最大团问题MCP（Maximum Clique Problem）在国外得到了广泛的研究,在国内刚起步,是一类NP完全问题。传统的确定性算法不能有效地进行求解。定义了MCP;介绍了使用启发式算法求解MCP的研究进展;综述了几种典型的智能搜索算法;分析了使用这些典型算法求解MCP的基本思想;研究了这些智能算法在求解MCP时的特点及性能。     

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

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

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

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

一种求解最大团问题的并行交叉熵算法

为了提高交叉熵算法求解最大团问题(maximum clique problem,MCP)的性能,提出一种领导者-跟随者协作求解的并行策略来实现交叉熵算法,从而达到减少计算时间和保障解的质量这两方面的平衡.算法中领导者活跃在并行处理器之间采集数据,并根据当前获得信息对跟随者作出决策;受控的跟随者则主要根据领导者的决策信息自适应地调整搜索空间,完成各自的集团产生任务.采用了OpenMPI在MIMD平台上实现了该算法,并应用到MCP基准测试问题上.加速比和效率分析结果表明,算法具有很好的加速比和效率.而与其它几种当前最好的启发式算法相比,结果表明算法相对于基于种群的启发式算法有一定的性能改善.     

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

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

最大团问题的改进蚁群算法求解

为了更好的解决最大团问题,提出一种改进的蚁群算法。通过提取图的顶点信息,将图用信息素模型来表示;根据最大团问题的约束条件利用蚁群构造极大团,并进行实时的全局信息素更新和局部信息素更新,直到找到最大团。实验结果表明,算法能较好的实现最大团问题,算法性能高于通用的蚁群算法。     

求解最大团问题的并行多层图划分方法

在当今大数据环境下,针对图中节点的海量性和分析的复杂性对最大团问题的研究在速度和精度上都提出了更高要求的问题,提出求解最大团问题的并行多层图划分方法（PMGP_SMC）。首先,提出一种新的多层图划分（MGP）方法,在保持原有图的团结构不被破坏的情况下对大规模图例划分产生子图,并对规模较大的子图进行多层图划分,进一步缩小子图规模,并且应用GraphX图计算框架实现MGP,形成并行MGP（PMGP）方法;然后,依据划分后的子图规模,减少了惩罚值局部搜索算法（PBLS）的迭代次数,提出基于速度优化的PBLS（SPBLS）来求解划分后的各个子图的最大团;最后,将PMGP和SPBLS相结合形成PMGP_SMC。采用Stanford大规模数据集运行测试,实验结果表明,PMGP相比并行单层图划分方法（PSGP）,求得的最大子图规模能缩小至原来的1/100,平均子图规模能缩小至原来的1/2;PMGP_SMC相比求解最大团问题的PSGP（PSGP_SMC）,总体时间缩短至原来的1/100,并且PMGP_SMC求解最大团的精度和基于极大团枚举求解最大团问题的并行多层图划分方法（PMGP_MCE）一致。PMGP_SMC能够快速精准地求解大规模图例的最大团。     

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

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

求解流水线调度问题的万有引力搜索算法

研究了以最大完工时间为目标的流水线调度问题,使用万有引力算法求解调度问题,提出了一种最大排序规则,利用物体间各个位置分量值存在的大小次序关系,并结合随机键编码的方法产生,将物体的连续位置转变成了一个可行的调度方案;提出了一种边界变异的策略使得越界的物体不再聚集在边界上,而是分布在边界附近的可行空间内,从而增加种群的多样性;结合交换算子和插入算子提出了一种新的局部搜索算法,有效地避免了算法陷入局部最优值,进一步提高了解的质量.最后证明了算法的收敛性,并且计算了算法的时间复杂度和空间复杂度,仿真实验说明了所得算法的有效性.     

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

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

一种最大团问题的Tile自组装高效模型

Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现：模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n~2n,求解成功率由0.5n0增加至0.5n~0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.     

图的最大团与最大独立集粘贴DNA计算模型

粘贴模型(stickermodel)是DNA计算中一个很重要的模型.其主要原理就是采用单双链混合型DNA分子进行编码,其优点在于在生物操作过程中不需要DNA链的延伸,不需要生物酶的作用以及DNA链可重复使用等,因此引起了来自不同学科的学者们的广泛关注与兴趣.文中提出了一种求解图的最大团问题的DNA计算模型,该模型采用了两种基本并行计算处理思想,一种是将图分解成小的子图来处理的并行思想;另一种是进行并行生物操作.     

基于局部有限搜索的无向图近似最大团快速求解算法

无向图最大团求解是一个著名的NP-完全问题,解决该问题的经典算法基本上都采用完全精确搜索策略。鉴于NP-完全问题本身所固有的复杂性,这些算法或许仅适用于某些特殊的小规模图,对于具有大规模顶点和边的复杂图还是显得无力,难以适用。针对完全精确搜索策略下的无向图最大团求解算法的大部分时间都用于对图进行额外而无效的查找的问题,采用分划递归技术将图划分为邻接子图和悬挂子图,然后对邻接子图进行递归求解,而对悬挂子图则通过设置搜索范围控制函数进行局部有限搜索。在DIMACS数据集上将所提算法与当前主要的最大团求解算法进行对比实验,结果表明,文中提出的局部有限搜索求解策略能在75%的基准数据上获得最大团,剩下不能得到最大团的数据实际上也可以获得接近于最大团的近似最大团,但算法的平均求解时间仅为目前最大团精确求解算法的20%左右。因此,在很多最大团非精确要求的场景中,所提算法具有极高的应用价值。     

一种改进的最大团问题DNA计算机算法

随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n）,同时文中算法还具有高效的空间利用率及容错能力的优点．     

关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法,蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

MAX-SAT问题一种改进的局部搜索算法

局部搜索算法是求解大规模SAT问题的高效算法。经典的局部搜索算法有GSAT、WSAT、TSAT、NSAT等,但这些算法的初始解都是随机产生的。本文提出了用单纯形法产生“初始概率”（每个变量取1的概率）,用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束,使在局部搜索的开始阶段,满足的子句数大大增加,加快了收敛的速度。通过对不同规模的随机STA问题实例的实验表明,这些改进有效地提高了局部搜索算法求解SAT问题的效率。     

关于最大团问题的一种新算法

最大团问题是图论中重要的NP完全问题,目前求解最大团问题的方法只适合某些特殊的图,活则消耗时间长,求解效率低。该文提出了一种新的算法．蚁群算法来解决最大团问题。蚁群优化算法是一种基于自然启发的算法,是一种解决组合优化问题的有效方法。实验结果显示,算法的有效性。     

航班恢复问题的迭代局部搜索算法

在恶劣天气和机械故障等原因造成航班不能按照原计划执行时,航空公司需要采取相应的措施对航班进行恢复。本文基于经典的资源指派模型,综合考虑了调整时间、换机、联程拉直、取消航班和调机5种恢复策略,提出一种以最小化加权成本为优化目标的航班恢复模型,并设计一种迭代局部搜索算法。首先用构造-修复启发式方法构造可行解,然后从该初始解出发,在飞机路线对的邻域中进行局部搜索。当陷入局部最优后,对解进行扰动,然后从扰动后的解重新出发进行局部搜索。为了提高搜索效率,同时降低陷入局部最优解的概率,局部搜索过程采用模拟退火算法。实例结果表明,本文提出的模型及算法能够在短时间内对受到影响的大规模航班计划进行恢复。     

求解CARPSD问题的自适应局部搜索算法

针对带有随机需求的弧路径规划问题,提出一种自适应局部搜索算法。采用随机路径扫描算法产生初始种群,选出最优者作为初始解,以自适应的方式进行局部搜索,并设计2种局部搜索机制。实验结果表明,与自适应大邻域搜索算法相比,该算法的最优解得到改进,运行时间平均缩短60%。