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

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

无线Mesh回程网的跨层优化快速算法

针对时分多址(TDMA)模式下无线Mesh回程网的路由及调度的跨层优化问题,提出了两种跨层优化的快速算法.首先在以最短系统调度时间为目标的跨层优化模型的基础上,提出了一种基于极大团搜索的快速最优算法,该算法通过Bron-Kerbosch极大团搜索算法列举出网络中所有极大并发传输模式,简化了跨层优化模型,从而可以用线性规划方法最小化系统调度时间,极大提高了运算的速度.仿真结果表明,与经典的列生成最优算法相比,该算法的运算时间缩短了99%以上.根据无线Mesh回程网的流量特点,文中还提出了一种基于链路权重分类的快速启发式算法,该算法能以较大的概率筛选出含有较大权重链路的极大并发传输模式.仿真结果表明,对于35节点的网络,该算法得到的次优结果相对于最优的平均偏离率在0.5%以下,平均运算时间仅为极大团最优算法的2.5%左右.     

基于改进马群算法的进场航班调度优化

进场航班调度优化问题是终端区管理效率提升中的关键问题,可以将其转化为组合优化问题求解.马群算法作为新型群智能算法,其收敛速度和寻优能力在高维函数优化问题中得到验证,为将其优势运用于进场航班调度问题中,基于排列编码,提出交换和翻转行为结合的并行2-opt搜索的启发式搜索策略和新型概率融合个体生成的进化策略.在OR-Library案例上的仿真结果表明,改进后的马群算法能够进一步提升进场航班运行效率,此算法在小规模算例中收敛速度和精度超过现有算法,在大规模算例中也能够有较好的结果,与当前最好结果最大差距仅为1.15%.     

快速挖掘最大频繁项目集的新算法

针对关联规则下最大频繁项目集的特性,提出了一种快速挖掘最大频繁项目集的新算法MMFI(miningmaximumfrequentitemsets)。该算法摆脱了传统的经典算法Apriori及其变种情况下的自底向上的搜索策略,利用集合枚举树(set enumerationtree)的变形结构采取了自顶向下的新的搜索方式,并通过其独特的启发式判断策略、候选项目集的生成策略等,大大减少侯选项目集的生成,从而降低了CPU搜索时间,提高了挖掘效率。     

一种求解矩形packing问题的智能枚举算法

矩形packing问题有许多工业应用,如码头货物装载,木材下料,超大规模集成电路（VLSI）布局设计,新闻排版等。国内外已提出了许多求解此问题的算法,如：遗传算法,模拟退火算法以及启发式算法等。在目前已有研究的基础上,提出了一种智能枚举算法,该算法的关键在于设计一种快速有效的枚举策略。用Hopper和Turton提出的21个矩形packing实例对所提出的算法性能进行了实算测试,平均面积未利用率为0.04%,平均计算时间为277.69 s,并求得了其中18个实例的最优解。实算结果表明：该算法对求解矩形packing问题是行之有效的。     

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

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

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

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

求解置换流水车间调度问题的Memetic算法

针对以最小化最大完工时间为目标的置换流水车间调度问题,建立了0-1型混合整数线性规划模型。在对模型进行Benders分解的基础上,提出了问题的求解策略,进而设计了一种Memetic调度算法,并探讨了基于组合规则的种群初始化方法和混合遗传操作。为了提高算法的搜索效率,采用了更加高效的适应度值计算方法以及两种邻域搜索方法。最后,基于Benchmark算例的仿真实验结果表明了该算法的有效性,可以找到26个算例中的17个最优解(65.38%),且其平均相对误差的均值仅为0.88%。     

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

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

一种布谷鸟-交叉熵混合优化算法及其性能仿真

为了提高布谷鸟搜索算法在求解复杂优化问题时的收敛速度和搜索精度,基于交叉熵方法,构建了一种新的布谷鸟-交叉熵混合优化算法.该算法将基于模型的交叉熵随机优化算法和基于种群的布谷鸟搜索进行有机融合,采用协同演化策略,既提升了混合算法收敛速度,又改善了其全局优化能力.对经典测试函数和PID控制器整定问题的仿真结果表明,新算法具有全局搜索能力强、求解精度高和鲁棒性好等特性,是一种求解复杂优化问题的可行和有效算法.     

基于多开端策略的改进布谷鸟搜索算法研究

针对传统布谷鸟搜索(Cuckoo Search,CS)算法在迭代后期寻优速度慢、易陷入局部最优等缺点,提出一种多开端调节布谷鸟搜索(Multi-start Adjustable Cuckoo Search,MACS)算法。改进算法引入多开端、飞行尺度和发现概率动态调节、反向学习等策略,能够有效消除Lévy-flights策略的固有缺陷,从而平衡全局、局部搜索能力,并利用经典算例验证改进算法的优越性。仿真结果表明,改进算法在求解质量及收敛速度等方面较传统CS算法、PSO算法均有一定程度的提高。     

基于改进粒子群的柔性作业车间调度问题优化研究

主要针对柔性作业车间调度问题进行求解,利用改进粒子群算法作为求解方法,以最小化最大完工时间(C_max)作为该问题的求解目标.在算例的选取上,选用作业车间调度问题的8*8经典算例和柔性作业车间调度问题的Brandimarte算例对提出的算法进行验证.改进粒子群算法由遗传算法和粒子群算法构成,遗传算法具有较好的全局搜索能力,但搜索过程中收敛的精度不高,粒子群算法由于其寻优特性,在搜索过程中速度较快,但容易陷入局部最优,综合考虑两者的优缺点,将遗传算子引入粒子群算法中,采用交叉搜索的方式,调整惯性权重以及变异的方式使粒子进化,当粒子群进化到一定程度后,对部分粒子进行变异处理从而避免算法陷入局部最优解,同时可以提高粒子群算法的收敛精度.依据柔性作业车间调度问题的特点,在经过多次变换种群规模以及迭代次数后,求解出最适合柔性作业车间调度问题的最优解.     

带预估选择的Memetic算法求解多星测控资源调度问题

针对当前多星航天测控资源调度系统模型描述复杂、求解算法不适合大型算例的问题,利用系统约束条件的二元化特点建立了多星测控资源调度系统在一类特殊图上的最大独立集模型,进而针对该模型解空间结构多峰密布、欺骗性强的问题,提出了一种带预估选择机制的改进型Memetic算法.在分析交叉操作可达域的基础上,设计了一种能快速预估交叉操作最大收益的预估算子,通过预估运算,每个个体从几个待选交叉对象中可选择出最有利的一个对象,以在有希望区域间实现搜索的转移.大型Benchmark算例上的仿真结果表明,所提预估选择机制能减弱原模型欺骗性的影响,使Memetic算法的性能平均提高了17%.     

自学习策略和Lévy飞行的正弦余弦优化算法

针对正弦余弦算法（SCA,sine cosine algorithm）局部搜索能力差的缺陷,提出自学习策略和Lévy飞行的正弦余弦优化算法（SCASL,sine cosine optimization algorithm with self-learning strategy and Lévy flight）。首先,提出正弦余弦算法自学习策略和非线性权重因子,使搜索个体记忆自身历史最优位置,在寻优过程中指导搜索个体更新位置,提高SCA的局部搜索能力;算法寻优后期,当搜索陷入局部最优时,采用基于Lévy飞行的停滞扰动策略使算法跳出局部最优,提高SCA的局部最优规避能力。基于13个经典基准测试函数对算法性能进行测试的实验结果表明,SCASL相比标准SCA和较新的优化算法SSA,VCS,WOA,GSA,具有更高的计算效率,收敛精度以及更强的局部最优规避能力。求解无人作战飞机航迹规划的仿真结果表明,在有6个敌方威胁源的战场环境中,相比SCA,SCASL求解得到的飞行航迹具有更小的航迹代价。综上,所提出的SCASL具有较强的寻优能力。     

快速求解粒球粗糙集约简的属性划分方法

传统邻域粗糙集需指定半径或通过搜索方式找出适用于问题求解的半径,这在数据预处理过程中会带来极大的时间消耗。而粒球粗糙集方法则能够依据数据分布,自适应地生成合适的粒结构。以粒球的纯度为度量准则,粒球粗糙集方法亦为属性约简问题的研究引入新的思路。利用前向贪心搜索求解约简时,需尝试计算每一个候选属性被加入约简池后所引起的粒球纯度的变化,这为算法的执行效率带来了严峻挑战。为解决这一问题,在前向贪心搜索进程中提出了属性划分策略,其本质是将所有属性划分成不同的组,从而能够压缩候选属性的搜索空间,以达到快速求解约简的目的。使用了10组UCI数据集,最终的实验结果说明,相较于传统邻域粗糙集约简以及基于纯度的粒球粗糙集约简,引入属性划分策略后,能够极大地提升粒球粗糙集约简求解的时间效率。     

光学分子影像手术导航系统中图像融合算法研究

手术中肿瘤的精确定位一直是国际上的研究热点及挑战性问题.对光学分子影像手术导航系统中的图像融合算法进行了研究,对图像数据进行预处理后,利用梯度信息确定荧光图像兴趣点,缩小配准点的搜索区域.配准过程采用穷尽搜索策略,以平均绝对差(MAD)、均方差(MSD)和归一化积相关(NPROD)作为相似性度量,并利用域法修正的方法对兴趣点坐标进行修正,避免了因兴趣点过度偏离图像中心而导致配准失败.该算法将32组图像数据的平均配准时间从原始算法的539.384 s缩短到43.200 6 s(MAD),46.685 3 s(MSD)及85.978 6 s(NPROD).采用这3种相似性度量算法的融合效果均优于原始算法.     

用改进遗传算法求解电力系统负荷恢复

对系统恢复过程中最后一个阶段的负荷恢复问题进行了研究.考虑系统恢复过程中负荷对电力需求优先级的不同,将电力系统的负荷恢复问题建模为多约束条件的组合优化问题,并用改进的遗传算法对问题进行求解.在选择策略中采用稳态策略、精英策略和重叠种群策略,提高了遗传算法搜索的遍历性并使算法具有群体爬山性.将各种约束条件与目标函数融合在一起,建立一种偏序关系来处理负荷恢复中的约束条件.求解的过程满足了系统的约束条件,不会出现系统的越限.算例结果表明了算法的有效性.     

改进蚁群算法求解单行设施布局问题

针对单行设施布局问题已有算法结构复杂、对算法参数有较大依赖性、求解效果欠佳的问题, 提出一种改进的蚁群算法。该算法采用基于目标函数值的自适应等级划分策略, 实现了信息素增量优胜劣汰、改进信息素的更新规则。通过简化状态转移概率函数, 降低计算量和算法对参数的依赖性, 引入精英候选集, 提高优良设备的选择概率。同时, 采用基于插入式邻域结构的爬山寻优算法作为局部搜索进行深度搜索。仿真结果表明, 求解28 个大规模的测试例子时, 该算法总的平均运行时间分别为混合遗传算法的14%, Lin-Kernighan 算法的5%, 分散搜索算法的50%, 说明该算法可在短时间内较稳定地得到高质量的近优解, 性能优越于其他算法。     

基于PCGPS算法的UCAV自主攻击可投放区快速解算

无人作战飞机（UCAV）可投放区解算的实时性和精确性直接制约着UCAV自主攻击水平。针对传统可投放区求解过程中存在求解速度慢、实用性受限等缺点,提出了一种基于并行混沌模式搜索（PCGPS）策略的快速算法。该算法综合了并行混沌搜索算法的全局最优搜索能力和广义模式搜索算法的局部精确搜索能力,将混沌变量映射到可投放区边界范围内,并利用并行混沌搜索算法搜索初步最优值作为广义模式搜索的初值,再利用广义模式搜索算法进行局部精确搜索,得到全局最优可投放区边界值。在此基础上,研究了UCAV投弹方式、投弹速度和投弹高度对可投放区边界的影响。数字仿真表明,该算法搜索精度高、速度快,具有快速解算自主攻击可投放区能力。     

贝叶斯网络结构学习的双重K2算法

贝叶斯网络源于人们对人工智能领域不确定性问题的研究,是进行不确定问题推理和数据分析的重要工具。结构学习是贝叶斯网络研究的核心内容,K2算法是结构学习的经典算法之一。为解决K2算法学习效果强烈依赖于节点序的问题,本文提出一种新的混合结构学习算法：双重K2算法。该算法首先将节点信息作为初始节点序,通过K2算法的搜索策略得到初始网络结构;然后在初始网络结构上利用拓扑排序得到修正后的节点序;最后K2算法通过修正后的节点序学习得到最优的网络结构。通过实验验证,在精度和效率上,双重K2算法效果优于其它经典算法。