一种求解最大二等分问题的分散搜索算法

最大二等分问题是图论中的一个NP困难问题.本研究提出一种基于分散搜索框架的启发式算法求解最大二等分问题.该分散搜索算法采用Kernighan-Lin算法作为局部搜索算法,利用解的质量和解之间的距离构造参考集,通过两个可行解构造新的可行解.利用一些标准测试例子测试算法,实验结果与现存算法所得结果比较,表明该算法是有效的.     

一种增量式多目标优化的智能交通路径诱导方法

路径诱导是一种主动引导车辆合理分流来解决城市交通拥堵的方法.本文提出了一种基于增量搜索的多目标优化路径诱导方法.该方法首先利用图论法将复杂路网抽象为点线的赋权图,引入多目标优化变量,建立路网模型;然后在启发式搜索基础上引入增量搜索,结合全局规划和局部动态重规划,实现车辆的实时路径诱导.仿真结果表明该方法能有效地解决复杂路网中车辆的实时路径诱导问题.     

一种求解多目标优化问题的混合演化算法

提出了一种混合演化算法求解多目标优化问题.演化算法是解决多目标优化问题的有效方法,在全局优化问题中具有很好的鲁棒性,但其局部搜索性能有待改善.Hooke and Jeeves方法是一经典的局部搜索算法,将其与演化算法结合求解多目标优化问题,提高了解的收敛质量,因而从整体上提高了算法的性能,并且测试结果也说明了该算法的可行性.     

带相容性约束的车辆路径问题及其混合蚁群算法

【目的】着力设计带相容性约束的车辆路径问题的高效启发式算法。【方法】针对带相容性约束的车辆路径问题的特点,提出了一种混合蚁群算法。该算法的核心由蚁群搜索和禁忌搜索组成,对蚁群搜索的状态转移公式和信息素更新规则进行了改进,并在蚁群搜索过程中加入了一个扰动机制,同时在禁忌搜索部分采用了新的邻域结构和禁忌规则。【结果】得到了关于带相容性约束的车辆路径问题的混合蚁群算法。【结论】通过多个算例对算法进行了测试,计算结果表明该算法具有很高的求解效率。
     

结合Separator的约束满足问题树分解方法

基于树分解的回溯搜索算法, 结合separator分解算子提出一种新的搜索算法BTD⁺-MAC. 该算法在搜索时, 优先选择separator中的变量进行相容性检查和实例化, 由于树宽度的减小能提高约束传播的效率, 进而提高问题求解效率. 对几组benchmark问题进行测试, 测试结果表明, 该算法在问题求解效率上超过了MAC3rm算法和BTD-MAC算法.     

用和声搜索算法求解技术站列车解编方案

确定到达列车的解体顺序和出发列车的编组顺序(即列车解编方案)是技术站编组调机运用计划的核心问题.本文为解决该问题,构建相应的优化模型,利用结合邻域搜索的和声搜索算法进行求解,采用目标函数值评价新的和声,邻域搜索策略用于获取新的和声.最后利用算例对所设计算法的求解效率进行分析验证,表明:算法收敛速度较快,而与邻域搜索策略的结合,有利于扩展其搜索范围与提升全局搜索能力,降低对选择概率的依赖.通过对不同参数条件下计算时间的测试说明,所设计算法能够满足技术站编组列车解编方案编制的要求.     

星际转移发射机会搜索方法

针对星际探测任务发射机会搜索中,等高线图法计算量大和基于遗传算法的搜索方法难以得到精确最优解的问题,提出了一种混合搜索方法.该方法根据探测任务要求,定义待搜索目标函数,并确定搜索域;结合Lam-bert定理与Gauss算法对该问题进行降维;采用全局-局部混合搜索方法求解,解决了传统方法计算量大、计算效率低、求解最优解困难的问题.以1627 Ivar小行星的交会任务为例验证了该方法,其结果表明,采用混合搜索方法可以快速获得最优的星际转移发射机会.     

基于插入-分段的无等待流水作业调度复合启发式算法

为求解NP-难的总完工时间最小化的无等待流水作业调度问题,提出一种有效复合启发式算法.通过分析基本操作的目标增量性质,构造基于插入-分段(I-S)的邻域结构和操作,提出了基于I-S的复合启发式算法(ISCH).ISCH算法与基于比较的启发式算法(BE)、基于置换的复合启发式算法(PH1(p))、Framinan等提出的复合启发式算法(FNM)和基于可变邻域搜索的混合遗传算法(GA-VNS)的比较结果表明,ISCH算法性能最佳,其平均相对偏差的均值较BE算法降低2.04%,平均运行时间为FNM算法的18.43%.当存在时间约束时,ISCH算法的平均相对偏差较GA-VNS算法降低0.99%.该算法中,目标增量方法的选用降低了运行时间,基于I-S邻域结构的方法则提高了算法性能.     

多起始点进化算法在容量约束弧路径问题上的应用

容量约束弧路径问题(CARP)是一类NP难的组合优化问题,通常采用启发式算法求解,计算时间较长.本文在竞争模因算法基础上采用多点同时搜索,构造了多点进化算法(MSEA).算法由多个初始解开始,同时进行局部搜索与遗传进化,再将结果合并,得到最终的解.在29个基准数据集上的数值试验表明,该算法可行有效,并可以节省大量计算时间.     

具有服务优先级别的动态离散泊位调度优化

研究具有不同服务优先级别的船舶动态到达情形下的离散泊位调度问题.以泊位分派和船舶作业开始时间为决策变量,为优化码头作业效率和船公司客户满意度,以最小化船舶总在港时间与加权延迟时间之和为目标建立数学模型.采用基于修改后的先到先服务等规则的启发式算法生成初始解,以此为基础设计结合禁忌深度搜索和模拟退火算法框架的混合算法对问题进行优化求解.不同问题规模下的数据仿真试验表明,该算法可以快速、有效地解决此类问题.     

应用基因概率学习算法求解最小码覆盖问题

概述最小码覆盖问题，以及现有的几种求解最小码覆盖问题的计算机搜索算法．在基因概率学习算法(PBIL)的基础上，建立码覆盖问题的目标函数，引进启发式算子HF0，针对局部陷阱设计跳出策略，从而获得一种新的快速求解码覆盖问题的算法．     

融合启发式搜索的改进极快决策树算法在多规格货物智能混合装载中的应用

针对多规格货物装载效率较低问题,提出了一种融合启发式搜索的改进极快决策树智能装箱算法,该算法首先计算并择优选取样本信息熵,然后构建生成货物装箱决策树模型,最后基于启发式搜索方法对货物装载后的剩余空间进行合并再利用。通过保证决策树每个节点装入货物体积最大,对待装货物进行快速决策。最后,基于七组异构性逐渐增强的货物数据对算法进行仿真实验,结果表明：本算法在保证较高集装箱利用率的情况下实现了快速装箱。     

基于COM的启发式搜索算法库的设计与实现

目前启发式搜索算法都是根据具体的问题应用而设计的,在不同的领域运用时启发式搜索算法就要重新进行设计,这样浪费了大量的劳动和时间,同时正确性也难以得到保障。在对多种启发式搜索算法进行分析的基础上,根据软件复用的思想设计启发式搜索算法库,并将COM技术应用到启发式搜索算法库,从而实现启发式搜索算法库。基于COM的启发式搜索算法库实现了与具体应用领域脱离,有效的解决了启发式搜索算法开发,同时也扩大了COM技术的使用范围。     

一个新的启发式搜索算法

本文提出一个新的启发式搜索算法,它可以在搜索过程中不断改善启发函数h,使最坏复杂度降为O(N)(N是被搜索图的大小)。本文还指了L.Mcro对“无普遍最优算法”的证明中的漏洞,并给出了新的证明。     

通用启发式搜索算法库的设计

由于目前启发式搜索算法被广泛的应用,但是其设计都是针对具体问题的,在不同的领域运用时启发式搜索算法就要重新进行设计,这样浪费了大量的劳动和时间,同时正确性也难以得到保障。针对这个问题,本文通过对多种启发式算法的基础上统一建模,设计了通用的启发式搜索算法库,及通用的数据结构,并与具体问题脱离。实现了启发式搜索算法的通用性、可扩充性与易调试性。     

改进的自适应和声搜索算法

和声搜索算法是一种启发式优化算法,针对现有改进的和声搜索算法(IHS)的不足,提出了一种改进的自适应和声搜索算法(IAHS).在该算法中,采用自适应的和声保留概率、音调调节概率和音调调节步长产生新解,每次迭代产生多个新解,充分利用和声记忆库的信息.本文用了5个标准的测试函数对该算法进行测试,结果表明该算法(IAHS)有较强的寻优能力和跳出局部最优解的能力.     

基于启发式搜索的一类离散非线性系统优化控制算法

研究了输入受约束、状态饱和系统的优化控制问题，得到了此类系统渐近稳定的充分条件，同时将最优控制问题转换为最优化搜索问题依据人工智能中的启发式搜索策略，给出了启发式优化控制算法，并就此算法的渐近稳定性给出了证明，仿真结果表明算法的有效性．     

最小化加权绝对偏差的并行多机调度问题

用禁忌搜索算法（ＴＳ）求解带有最小化绝对偏差的并行多机调度问题，首先证明了它是一个ＮＰ－难题，然后用一个启发式作初始解，给出一个禁忌搜索算法，实验表明，禁忌搜索方法求解最小化加权绝对偏差问题可以获得最优解或近似最优解。     

A Beam Search-based Algorithm for Flexible Manufacturing System Scheduling

ＩｎｔｒｏｄｕｃｔｉｏｎＳｃｈｅｄｕｌｉｎｇａｓａｎｏｐｅｒａｔｉｏｎｓｐｌａｎｎｉｎｇｐｒｏｂｌｅｍｉｓｃｏｎｃｅｒｎｅｄｗｉｔｈｔｈｅａｌｌｏｃａｔｉｏｎｏｆｒｅｓｏｕｒｃｅｓｏｖｅｒｔｉｍｅｔｏｐｅｒｆｏｒｍｖａｒｉｏｕｓｔａｓｋｓ.Ｉｎａｆｌｅｘｉｂｌｅｍａｎｕｆａｃｔｕｒｉｎｇｓｙｓｔｅｍ (ＦＭＳ)ｅｎｖｉｒｏｎｍｅｎｔ,ｓｃｈｅｄｕｌ ｉｎｇｇａｉｎｓｓｐｅｃｉａｌｉｍｐｏｒｔａｎｃｅｄｕｅｔｏｔｈｅｈｉｇｈｌｅｖｅｌａｕｔｏｍａｔｉｏｎａｎｄｃｏｎｓｉｄｅｒａｔｉｏｎｓｏｆａｄｄｉｔｉ…