启发式进货规划求解Steiner树问题

求解Steiner树对通信网络点对多点路由优化问题有重要意义,已被证明是NP－complete的。通过把图形简化技术、进货规划方法和KMB启发式上结合,提出了一种求解Steiner树问题的新方法,提高了算法的效率,仿真结果表明,本算法是有效的,性能优于传统的启发式算法。     

一种基于最小路径的多播路由优化算法

信息物理融合系统(Cyber-Physical Systems,CPS)底层是传感器、控制器和执行器等异构节点构成的无线自组网络,不同节点之间需要通过通信网络传送给感兴趣目标节点,传统的无线自组织网络一般采用单播或广播技术,但是这些往往实时性不高,通信开销大,不利于在CPS中受限节点间通信.该文针对信息物理融合系统中无线多播路由问题构建网络模型,演化为最小路径问题,数学模型为约束Steiner最小树问题,并针对该NP难问题通过启发式算法求解,再通过贪婪思想构建一种最小路径多播路由算法.最后通过与uCast以及SenCast等经典的多播路由算法仿真比较,得出其算法在实时性以及能耗等方面性能优异.     

差分进化算法在电力系统环境经济调度中的应用

以求解环境经济调度(EED)这一复杂的多目标约束优化问题为背景,研究了一种改进的多目标差分进化算法(EMODE),该算法依据多目标优化问题的特点重新设计了差分进化算法(DE)的进化算子并引入自适应二次变异算子来有效避免DE存在的"早熟"收敛现象;同时,针对EED问题约束条件复杂且难以处理这一问题,依据不同类型约束的特点提出一种启发式的约束处理方法.将EMODE应用到某电力系统的多目标环境经济调度中,仿真计算结果以及与其他求解方法的对比分析表明,EMODE可以有效兼顾全局收敛性和Pareto非劣调度方案的多样性,具有较高的效率以及鲁棒性.     

基于记忆策略的动态分解约束多目标进化算法

针对现有面向多目标优化问题的约束处理方法存在求解效率不足,基于分解策略的多目标进化算法受到约束限制导致求解性能低的问题,提出一种基于记忆策略的动态分解约束多目标进化算法.本文首先引入具有记忆功能的归档集,改进基于短暂忽略非容许解的约束处理方法,提高算法的求解鲁棒性.然后结合基于分解的多目标进化算法,设计一种动态分配搜索...     

基于进化算法的多目标生产排序研究进展

利用多目标进化算法求解复杂生产排序问题是近10 a来发展迅速的研究方向.首先调查了国内外采用进化算法求解多目标生产作业排序的研究现状,分别对3类不同策略的多目标进化算法设计思想进行分析,在总结各类方法优劣的基础上,给出了进一步研究的趋势展望.     

时延约束的最小费用路由选择算法

如何找到效率高、性能优的路由算法成为了一个热点。QoS路由算法的实质就是求解多约束整数规划问题，这类问题通常都是NP-hard问题。针对满足两个度量的路由选择，利用Lagrange松弛和剪切网络的方法，给出了一个从源点到宿点满足给定时延门限值求解最小费用路由的启发式算法。仿真结果表明了算法是有效的。     

基于并行量子遗传算法的QoS组播路由方法

通信网络时延受限且满足带宽要求的最小代价组播树问题是NP完全问题,传统方法难以求解,一般采用启发式方法求解.提出了一种基于并行量子遗传算法的服务质量(QoS)组播路由算法,算法中将各个子群体独立地并行进化,并通过相邻子群体间的信息交换实现克服早熟,避免局部收敛的目的,还提出了一种新的动态旋转角调整策略,使算法具有更好的种群多样性和全局寻优能力.仿真实验表明,新算法在求解性能上优于遗传算法(GA)和采用静态旋转角的量子遗传算法(QGA).     

基于客户满意度的车辆路径问题的混合蝙蝠算法

车辆路径问题对现实有着良好的指导意义,自提出以来便吸引了企业界和学术界的广泛关注。然而,传统车辆路径问题仅仅将车辆行驶里程最短作为目标,忽视良好的客户体验对于企业的重要性。考虑客户满意度这一目标,建立以客户满意度和车辆行驶里程最短为目标的多目标优化模型,根据车辆路径问题的具体特征,改变基本蝙蝠算法的编码方式。为克服基本蝙蝠算法求解精度低、易陷入局部最优的缺陷,加入贪婪随机自适应启发式算法提高求解精度,引入病毒进化机制以增强蝙蝠算法跳出局部最优的能力。算例分析表明:病毒进化混合蝙蝠算法相比于基本蝙蝠算法,在求解精度上有较大幅度提高,是一种有效求解车辆路径问题的方法。     

采用多目标差分进化的移动Ad Hoc网络节能路由算法

为了在节点的能量消耗和最优路由之间找到一个平衡,根据多目标差分进化算法原理,提出一种基于多目标差分进化的移动Ad Hoc网络节能路由算法.该算法把路由代价和网络生存时间作为2个优化目标,采用适应值变换的约束处理技术、非支配排序和拥挤距离技术进行优化.在优化过程中,提出适合差分进化算法的变异、交叉和选择策略.结果表明:该算法在网络生存时间和最优路由方面具有较好的优势,并保证了较高的包传递率.     

基于免疫原理的动态多播路由算法

为了避免传统启发式算法在求解多播路由问题时存在的过早收敛问题,提出了一个新的动态多播路由免疫算法(DCOMIA),此算法利用克隆选择和基因库的思想改善了群体的多样性,并评估了二进制串表示的候选个体.同时,提出了一个改进了的动态约束多播路由问题(MDCMR),试验结果表明:此算法求解该动态多播问题是高效的.     

八角形斯坦纳树问题的文化基因算法

针对多端线网互连问题,提出以超大规模集成电路物理设计中布线阶段应用较多的斯坦纳树为切入点,采用一种基于种群的全局搜索和基于个体的局部启发式搜索相结合的文化基因算法,对八角形斯坦纳树的结构进行优化,从而进一步缩减线长. 使用Prim算法预处理取得初始种群,并重新修改了原本的文化基因的编码以及相关操作,以便可以处理八角形斯坦纳树构建这一离散问题,利用八角形结构,使其能在全局范围内,快速收敛并全局寻优. 实验结果表明,所提算法能获得较好拓扑的八角形斯坦纳树,快速得到多端线网最优或者较优的布线结果,缩减布线的线长.     

基于Logistic回归模型和凝聚函数的多示例学习算法

实时多媒体网络中,带延迟与延迟抖动约束的斯坦利树问题是一个研究热点.这种带约束的斯坦利树被证明是NP-完全问题.提出了一种基于禁忌搜索的带延迟与延迟抖动约束最小代价组播路由算法.实验结果表明,该算法对于实际网络是有效的.这种方法使得IP组播把数据同时发送到组成员时有效地利用了网络资源.

Abstract：

The delay and delay variation-bounded Steiner tree problem is animportant multicast routing issue in real-time multimedia networks.Such a constrained Steiner tree problem is known to be NP-complete.A multicast routing algorithm is presented,which is based on tabu search to produce routing trees having a minimal network cost under delay and delay variation constraints.The approach makes IP multicast utilize resources efficiently in delivering data to a group of members simultaneously.     

基于网络编码的多源多核点光组播路由算法

针对现有多源组播网络编码路由方法的链路代价、波长消耗等性能受目的节点数目变化影响过大的问题,提出一种基于网络编码的多核组播路由算法。该算法通过选取多个核点构造编码子图,并将为目的节点选择的核心节点设为解码节点,以减小目的节点数量对编码子图大小的影响。结果表明,在目的节点较多的多源网络中,该算法能有效地减少网络总链路代价和波长资源消耗。     

一种求解QoS路由问题的半定规划算法

QoS路由的主要问题是求源节点到目的节点满足QoS多个约束的优化问题。由于半定规划在求解组合优化问题和NP-完全问题时具有收敛速度快,迭代步数少等优点。本文基于QoS路由问题的线性整数规划网络模型,利用半定规划方法研究了时延约束的代价最小问题。把QoS路由的一般模型松弛为半定规划的标准形式,利用半定规划内点方法进行求解,然后利用随机扰动方法得到原问题的近似最优解.数值试验表明了算法的有效性。     

基于遗传优化的WSNs多源单汇路由算法

针对无线传感器网络中的多源单汇路由问题,综合考虑无线传感器网络中链路带宽、延迟和路径节点最小剩余能量三种度量,建立了多源单汇路由问题的系统模型,将其转化为求解多约束最小Steiner树问题,已知该问题是NP难的问题,给出了基于遗传优化的求解算法,采用基于备选路径集的整数序列编码表示一棵生成树,设计相应的交叉和变异算子,以及对非法染色体进行修复的机制,最后在遗传算法的计算过程中选择合理的适应度函数,找到一棵满足多约束的能耗趋于最小且状态稳定Steiner树.理论分析和数值试验结果表明所提出的遗传求解算法收敛速度快、可靠性高,为无线传感器网络中的多源单汇路由提供了一种新的有效途径.     

离散萤火虫算法在车载网的应用

车载自组织网(Vehicular ad hoc network,VANET)是移动自组织网络之一,具有节点变动迅速、拓扑结构灵活、通信能力要求较高的特点。为提高车载自组织网络的可靠性,实现数据的安全共享和快速交互,将离散萤火虫(DFA)算法应用求解车载网络中具有服务质量约束的多播路由问题。根据VANET的路由特点,将该问题转化为延迟成本最小化约束优化问题,并将车载网络路径时延转化为萤火虫的荧光素值,然后将该算法用4个实例进行测试,并与Dijkstra最短路径算法、粒子群优化算法进行比较。研究结果表明:离散萤火虫算法性能更佳,可有效解决VANET中Steiner minimum tree(SMT)问题,成功取得最优路径。该算法在一定程度上稳定了网络拓扑结构,能够实时更新节点信息。     

基于遗传算法的路由选择问题的研究

针对多目标优化问题,应用免疫遗传算法的基本思想,提出了一种求解满足带宽-时延约束多组播路径问题的两层遗传算法。在算法中设计了一种基于节点连接路径的具有树状结构的染色体表示方法及可以实现树状染色体交叉和变异的算子。数值实验结果表明,文中提出的算法可以有效找到多组播路由问题的优化解。     

Backtracking Routing Mechanism for Improving Link Failure Recovery

Failure-insensitive routing is a good mechanism to avoid packet dropping and disconnection of forwarding when some links fail,but multiple failure links may bring routing loop for the mechanism. Backtracking routing algorithm based on inverse shortest path tree rooted at destination is presented. The feasible restoration routing is obtained through searching from the start of the failure link and tracing back to the leaves of the shortest path tree with the destination as the root. The packets are forwarded from the mounted point with smaller sequence to the mount point with bigger sequence to decrease the possible of loop in case of multi-failures. The simulations and analysis indicate that backtracking routing algorithm improves the network survivability especially for large network,at the cost of the computation complexity in the same order as failure insensitive routing.