基于遗传禁忌混合策略的二叉判定图最小化算法研究

提出了一种新的动态启发式二叉判定图（BDD）最小化算法．该算法将遗传算法的全局搜索能力和禁忌搜索的邻域搜索策略相结合来寻找BDD的最优变量排序，以实现BDD结点规模最小化．实验结果表明该算法性能优于其它启发式算法．     

实值化学反应优化算法

化学反应优化（CRO）是近年来提出的一个基于种群的元启发式算法,而实数编码化学反应优化（RCCRO）是CRO的一个变体,针对该算法存在的不足提出了一个新的实值化学反应优化（RVCRO）算法求解全局数值优化问题。该算法改进了传统CRO的框架和搜索模式,将控制参数从8个减少到5个;采用一组常用的基准函数来测试其性能,比较结果表明,该算法在最终误差值和收敛速度方面,性能有较大提升。     

基于混合遗传算法的资源受限的运输任务调度

在利用串行调度启发式方法解决资源受限的运输任务调度问题（RCTTSP）的基础之上,提出了一种混合遗传算法（HGA）。该算法通过对运输任务执行优先次序进行基因编码,利用串行调度方法获得初始种群,并在遗传个体调度目标值与适应值确定的过程中使用了局部搜索启发式规则,从而充分地结合了遗传算法的全局搜索与启发式方法的局部搜索能力。首先对RCTTSP进行了描述,给出了混合遗传算法的基本原理,然后针对测试案例进行实现,并与单纯使用串行调度方法进行了比较。结果显示,该混合遗传算法能有效地改进调度效果。     

量子行为粒子群优化算法的布局问题研究

基于多边形扫描转换的启发式底左（HBL）算法，将量子行为的粒子群算法（QPSO）应用于布局问题——二维不规则多边形优化排样，给出了该问题的粒子构造方法及其布局优化过程。通过与模拟退火遗传算法（SAGA）进行布局优化比较，验证了该算法求解布局优化问题的有效性。     

求解PDPTW问题的快速启发式算法

提出了一种解决有时间窗口装卸货问题（PDPIW）的快速启发式算法．该算法基于局域搜索和随机扰动的思想，以减少车辆数目为主要目标，采用了启发式的搜索方法并加入了随机扰动以跳出局部最小点。该算法可以在很短的时间内显著地提高解的质量，这是仅以减少总路程为主要目标的局域搜索和现代启发式算法不能达到的。对标准算例的测试和与禁忌搜索算法计算结果的比较，表明该算法对于求解此类有时间窗口装卸货问题比传统的启发式算法在计算速度和减少车辆数目上更具优势。     

一种启发式的汉语词性标注算法

描述了一种启发式的汉语词性标注算法,并采用该算法实现了一个基于统计模型的汉语词性标注系统。该算法将反向动态规划和正向Ａ＾＊解码算法相结合。初步的开放测试表明,该系统的词性标注正确率为９５．８８％（小标记集）和９７．９５％（大标记集）,性能优于Ｖｉｔｅｒｂｉ算法。     

轧制单元数确定问题的研究

建立了确定轧制单元数的一种新的聚类模型，开发出一种有效的两阶段算法（启发式算法和模拟退火算法）求解此问题。仿真结果表明了该算法的有效性。     

车辆路径问题（VRP）算法研究

车辆路径问题（VRP）是图论中的NP问题,目前求解这类问题的算法可分为：精确算法、经典启发式算法和现代启发式算法三类;对这三类算法中最具代表性的几种算法进行了分析指出了其适用范围和场合、存在的问题以及改进的方案;最后,对其研究前景进行了展望。     

单台批处理机总加权完成时间最小化的启发式算法

批处理机总加权完成时间最小化问题的复杂性目前还没有确定，因此有必要研究该问题的启发式算法．基于对该问题最优解性质的分析，提出了工件分批的最优性质．分别基于WSPT规则和SPT规则对工件进行总排序，利用工件最优分批性质进行分批，提出了两种启发式算法（简称WSPTS和SPTS）．为了检验算法的性能．将提出的算法与此问题的基准算法和常规算法进行了比较，结果表明，启发式算法WSPTS要优于其他的算法，而SPTS算法的性能最优．     

云环境下超启发式能耗感知调度算法

能耗感知调度的研究对云计算数据中心的可持续发展有着重要意义。能耗感知调度是一个NP难的多目标优化问题,目前云环境下的任务调度算法较少考虑能耗问题,且不能实现对能耗的灵活管理,随机搜索算法是一种解决该问题的有效途径,但其计算开销大,收敛速度慢。将异构云环境下的能耗感知调度问题定义为一个带约束的问题,即在一定的完成时间下优化系统能耗,以实现对能耗的灵活管理。此外,提出了基于在线学习的超启发式算法（OLHH）,该算法结合电压调节技术,在设计了简单高效的启发式策略集的基础上,引进超启发式算法,并采用在线学习的方式跟踪启发式策略的表现,实现对启发式策略的合理管理,从而达到提高算法的收敛性能的目的。模拟实验表明,该算法能够实现系统能耗的灵活管理,且比传统的随机搜索算法有着更好的收敛性能。     

Bandwidth-delay-constrained least-cost multicast routing based on heuristic genetic algorithm

We present an heuristic genetic algorithm for the quality of service (QoS) multicast routing that depends on: (1) bounded end-to-end delay and link bandwidth along the paths from the source to each destination, and (2) minimum cost of the multicast tree, where the link delay and the link cost are independent metrics. The problem of computing such a constrained multicast tree is NP-complete. We show by experiments that our proposed genetic algorithm is efficient and effective.     

免疫组播路由选择算法

研究了带宽延时受限、费用最小的QoS组播路由问题，并提出了一种解决该问题的免疫算法．免疫算法的核心在于免疫算子的构造，而它又是通过接种疫苗和免疫选择两个步骤来完成的．根据QoS组播路由问题，给出了免疫疫苗选取与免疫算子构造的具体方法．将免疫算法应用于组播路由选择，是通过在基于遗传算法的组播路由选择的基础上引入免疫算子来实现的．该算法采用的进化算子简便、高效．仿真实验表明，该算法不仅有效可行，而且较好地解决了标准遗传算法中出现的退化现象，提高了收效速度和搜索能力．     

一个快速的时延有界低代价多播路由算法

基于ＱｏＳ的多播路由算法需要在满足每个个体ＱｏＳ需求的同时,又能高效管理网络资源,提出了一种满足端端时延限制的低代价多播路由算法。算法使用一个修改的Ｓｔｅｉｎｅｒ树近似算法先构建时延有界的低代价多播树,再通过最小时延路径与其它尚不在多播树的且结点相连。     

分布式蚁群QoS组播路由算法

为寻找满足带宽、延迟等约束的最小代价组播路由树的QoS组播路由,提出一种分布式蚁群优化算法。在蚂蚁行动过程中形成组播树的森林。若在某步结束时森林中仅剩1棵树,则蚂蚁达到目标,停止行动。仿真实验结果表明,该算法在结果和收敛速度方面都有良好的表现。     

WDM全光网络中实时组播的分布式路由与波长分配算法

在WDM网络中，由于每条链路上可用波长是动态变化的，在考虑波长转换延迟的条件下，实现实时组播连接的路由与波长分配是十分困难的．假定WDM网络中每条链路有多根光纤，只有部分结点具有波长转换器且波长转换时间是不可忽略的，据此提出了一种用于建立实时组播连接的分布式路由与波长分配算法．该算法以Prim最小生成树算法为基础，生成一棵满足给定延迟时限的最小成本树．当最小成本树不能包括所有目的结点时，对剩余目的结点生成一棵最短延迟树，然后合并两棵树得到一棵组播树．波长分配使用最少波长转换和负载平衡策略．     

A new scalable multicast routing algorithm for interactive real-time applications

Quality of service (QoS) provisioning generally assumes more than one QoS measure that implies that QoS routing can be categorized as an instance of routing subject to multiple constraints: delay jitter, bandwidth, cost, etc. We study the problem of constructing multicast trees to meet the QoS requirements of real-time interactive applications where it is necessary to provide bounded delays and bounded delay variation among the source and all destinations while keeping overall cost of the multicast tree low. The main contribution of our work is a new strategy for constructing multiconstrained multicast trees. We first derive mathematically a new delay-variation estimation scheme and prove its efficiency. Thereafter, we propose a simple and competitive (in terms of running time) heuristic algorithm, for delay and delay variation constrained routing problem based on the proposed delay-variation estimation scheme and using the Extended Prim-Dijkstra tradeoffs’ algorithm. Our contribution also extends previous works in providing some properties and analyses of delay bounded paths satisfying delay variation constraints. Extensive simulation results show that our algorithm outperforms DVDMR in terms of multicast delay variation with the same time complexity as DVDMR.     

Delay-Constrained,Low-Cost Multicast Routing in Multimedia Networks

Support for multimedia applications is a major objective of future high speed networks. Multimedia applications are usually resource intensive, have stringent quality of service (QoS) requirements, and in many cases involve large multicast groups. Multicasting enables these applications to scale to a large number of users without overloading the network and server resources. This paper focuses on developing low-cost, delay-bounded multicast trees to support the QoS requirements of multimedia applications. The approach taken in the development of the multicast trees is to decouple the cost optimization from bounding the delay by first building a low-cost tree and then handling any delay violations that may occur in the tree. Three new heuristics are proposed. The first two heuristics, delay-constrained low-cost inexpensive multicasting (SLIM) and SLIM+, use the least-cost path between the multicast nodes to incrementally build a multicast tree that satisfies the delay requirements of the multicast nodes. Their complexity is O(n³), where n is the number of nodes in the network. The third heuristic, K-SLIM, builds a set of k shortest paths and uses these paths in an attempt to further reduce the cost of the multicast tree without violating the delay requirements of the multicast nodes. Its time complexity is O(kn³ log(n)), where k, a user-defined parameter, denotes the number of shortest paths to be considered. Our simulation results show that K-SLIM on average outperforms other well-known heuristics. The results also show that SLIM+ produces low-cost, delay-bounded trees with an average cost close to the average cost of the trees produced by K-SLIM but with much lower processing overhead.     

基于免疫遗传算法的多约束QoS组播路由选择方法

以具有精英保留的免疫遗传算法（IGAE）为基础,提出了一种新的用来求解带宽、时延、时延抖动受限,费用最小的QoS组播路由选择问题的方法。首先采用预处理机制,将网络结构中不满足带宽约束的链路去掉,利用Dijkstra第k最短路径算法建立编码空间的备选路径集;然后采用基于路径的树结构编码来随机产生初始群体,使种群中的每个个体都代表组播路由问题的一个候选解;最后利用IGAE算法对种群进行优化,最终求得满足QoS要求的组播路由。仿真实验结果表明,该算法具有较好的性能,能以较快的速度搜索到满足QoS要求的费用最小的组播树。     

MANET中基于遗传算法的QoS多播路由协议

随着多媒体业务的普及,如何为MANET多播路由提供QoS保障成为研究热点。提出了一种带宽和时延受限的QoS多播路由协议,它利用遗传算法搜索满足QoS要求的最优多播树。仿真结果表明该协议收敛速度快,寻径成功率高,它为移动网络中具有QoS保障的多播通信提供了一种有效途径。     

一种时延约束的多点到多点组播路由启发式算法

多点到多点组播路由是组播研究领域内的一个重要问题。当单棵共享组播树不能满足时延约束时,需要建立多棵共享组播树,但同时又会增加管理开销。因此,如何尽量减少共享组播树的个数成为关键问题。本文提出了一种启发式算法DCMMHA,用来解决时延约束的多共享组播树问题(DCMSMT),该问题已被证明为NP完全问题。本文算法按照特定规则生成候选中心列表,在不违反时延约束条件下,将源节点和目的节点加入共享树,并且对已选择中心进行更新。仿真实验将DCMMHA算法同其它四种同类算法进行比较,结果表明本文的算法所获得的中心数最少,显著降低了共享树的管理开销。