Genetic algorithm for pareto optimum-based route selection

A quality of service (QoS) or constraint-based routing selection needs to find a path subject to multiple constraints through a network. The problem of finding such a path is known as the multi-constrained path(MCP) problem, and has been proven to be NP-complete that cannot be exactly solved in a polynomial time. The NPC problem is converted into a multiobjective optimization problem with constraints to be solved with a genetic algorithm. Based on the Pareto optimum, a constrained routing computation method is proposed to generate a set of nondominated optimal routes with the genetic algorithm mechanism. The convergence and time complexity of the novel algorithm is analyzed. Experimental results show that multiobjective evolution is highly responsive and competent for the Pareto optimum-based route selection. When this method is applied to a MPLS and metropolitan-area network, it will be capable of optimizing the transmission performance.     

公交网络车费设定问题的Stackelberg博弈模型

对城市公交网络系统车费的合理设定问题进行了研究分析,考虑到乘客对公交收费变动会作出相应的反应,从而改变网络上乘客的流量分布,运用Ｓａｃｋｅｌｂｅｒｇ博弈理论,将这一问题描述为一个两级数学规则问题,在一定的公交网络收费结构下,乘客在网络上的流量分布可由随机用户平衡分配模型进行估计,鉴于两级规划问题的非凸性,提出了基于灵敏度分析的启发式算法,最后,给出一个仿真算例说明本文提出的模型和算法的合理性。     

Optimizing on multiple constrained QoS multicast routing algorithms based on GA

With the rapid development of Internet, mobile networks and high-performance networking technology,multiple constrained QoS multicast routing optimization in networks with uncertain parameters has become a very important research issue in the areas of networks and distributed systems. It is also a challenging and hard problem to the next generation Internet and high-performance networks, and has attracted the interests of many people. This paper discusses the multiple constrained QoS multicast routing problem, which may deal with the delay, delay jitter,bandwidth and packet loss metrics, and describes a network model for researching the routing problem. The paper mainly presents multiple constrained QoS multicast routing algorithm (MCQMRA), a QoS multicast routing policy for Internet,mobile network or other high-performance networks, which is based on the genetic algorithm (GA) and can provide QoS-sensitive paths in a scalable and flexible wayin the network environment with uncertain parameters. The MCQMRA can also optimize the network resources such as bandwidth, delay, packet loss metrics and can converge to the optimal or near-optimal solution within few iterations, even for the network environment with uncertain parameters. Simulation results show that MCQMRA is an available approach to QoS multicast routing decision.     

Distributed QoS multicast routing protocol in ad hoc networks

1 .INTRODUCTIONMobile ad hoc networks ( MANET) , also calledthe infrastructureless mobile network or self-or-ganized network,consists of a collection of mobilenodes sharing a wireless channel without any cen-tralized control or established communication back-bone .ad hoc networks have no fixed routers ;allnodes are capable of movement and can be connect-ed dynamically in an arbitrary manner . Usually ,these nodes act as both end systems and routers atthe same ti me . Nodes of these netwo…     

基于改进型能量函数和瞬态混沌神经网络的TSP问题研究

针对传统神经网络在搜索NP类问题的解时易陷于局部最优点的不足,提出了一种基于改进型能量函数(IEF)和瞬态混沌神经网络(TCNN)的优化模型,将此应用于旅行商问题(TSP)的求解,并和传统神经网络优化方法进行了比较。仿真研究结果表明,该论文所提出的方法在解的可行性以及全局最优解的获取能力方面都有很大优势,收敛速度和准确度也令人满意。     

拥挤交通网络中组合的交通出行、OD、路径分配与收费定价模型

提出交通网络中出行选择、讫点选择、路径选择和道路收费定价的组合模型。模型被表示为两层规划,低层表示出行选择、讫点选择和路径选择的随机均衡模型,预测驾驶员对道路收费模式如何响应;上层确定最优道路收费,以达到网络出行费用最小。     

考虑交叉口延误和通行能力优化疏散救援路线的最小费用流模型

疏散交通路线的确定是应急计划的重要内容．以往有关最佳疏散交通路线的研究没有充分考虑交叉口延误和通行能力等因素，若疏散路线经过城市内拥挤路段，忽略交叉口的这些特性会导致结果不尽合理。将交叉口分方向延误和通行能力作为节点权重，用点权网络表示疏散涉及到的道路网，建立了点权交通网络中的最小费用流模型描述城市内事故地点至接收点的人群及其产生的车流的疏散路线问题；设计了求解这种最小费用流的最小费用路算法，通过求解点权交通网络中的最小费用流，得出事故地点至安全接收地点的最佳疏散交通路线及相应的疏散流量。最后以一个数值算例说明了模型和算法的具体应用。     

Finding Key Node Sets in Complex Networks Based on Improved Discrete Fireworks Algorithm

Finding out the key node sets that affect network robustness has great practical significance for network protection and network disintegration. In this paper, the problem of finding key node sets in complex networks is defined firstly. Because it is an NP-hard combinatorial optimization problem,discrete fireworks algorithm is introduced to search the optimal solution, which is a swarm intelligence algorithm and is improved by the prior information of networks. To verify the effect of improved discrete fireworks algorithm(IDFA), experiments are carried out on various model networks and real power grid.Results show that the proposed IDFA is obviously superior to the benchmark algorithms, and networks suffer more damage when the key node sets obtained by IDFA are removed from the networks. The key node sets found by IDFA contain a large number of non-central nodes, which provides the authors a new perspective that the seemingly insignificant nodes may also have an important impact on the robustness of the network.     

动态模糊语义网及其并行执行

本文讨论了动态模糊语义网的概念及其在曙光１０００并行机上的实现问题。如何将模糊结点最优分配到并行多处理机的处理器上的问题是ＮＰ完全型的。本文提出了一种基于模拟退火思想的算法解决了模糊结点的分配问题，并在曙光１０００并行机上对结果进行了验证。     

基于决策图贝叶斯的多目标QoS组播路由算法

随着实时组播通信需求的不断增长，要求网络能够提供更加严格高效的QoS(Quality of Service)路由保证，需要设计一个能够同时满足不同QoS约束的高效组播路由算法。此问题可归结为图论中的NP(Non-Polymenital)问题，一般方法是把多个QoS参数加权合并为一单目标函数进行优化。提出了一种基于决策图贝叶斯的多目标QoS组播路由算法，算法在不需做预处理的情况下可对多个不同的QoS参数同时进行优化。仿真结果表明，所提出的算法能够快速收敛于一组满足不同QoS约束的非支配解。     

城市应急最优路径算法

提出一种应用于城市应急系统的改进的最优路径搜索算法。它利用道路等级的分层方法,建立优化的层次化路网模型;在此基础上,利用分级搜索技术,解决起始节点和目标节点由低层到高层的最优路径;同时,在高层路网上采用提出的结合道路状况的启发式A＊优化搜索算法进行搜索,得到完整的优化路径。最后通过实际路网的应用验证了提出方法的有效性。     

最优信号控制条件下城市交通离散网络设计问题的备用能力模型

将备用能力的概念与城市交通离散网络设计问题结合在一起,一方面通过对路口的信号进行最佳设置使交通网络可以容纳最大的交通需求量;另一方面,通过在交通网络中添加新的路段来提高整个交通网络的通行能力.给出了最优信号控制条件下城市交通离散网络设计问题备用能力的优化模型及其启发式求解算法.最后,通过一个简单的算例,说明该算法是可行并且有效的.     

Multi-facility ordered median problems in directed networks

This paper uses a finite dominating set (FDS) to investigate the multi-facility ordered median problem (OMP) in a strongly connected directed network. The authors first prove that the multi-facility OMP has an FDS in the node set, which not only generalizes the FDS result provided by Kalcsics, et al. (2002), but also extends the FDS result from the single-facility case to the multiple case, filling an important gap. Then, based on this FDS result, the authors develop an exact algorithm to solve the problem. However, if the number of facilities is large, it is not practical to find the optimal solution, because the multi-facility OMP in directed networks is NP-hard. Hence, we present a constant-approximation algorithm for the p-median problem in directed networks. Finally, we pose an open problem for future research.     

Modeling genetic regulatory networks: a delay discrete dynamical model approach

Modeling genetic regulatory networks is an important research topic in genomic research and computational systems biology.This paper considers the problem of constructing a genetic regulatory network(GRN) using the discrete dynamic system(DDS) model approach.Although considerable research has been devoted to building GRNs,many of the works did not consider the time-delay effect. Here,the authors propose a time-delay DDS model composed of linear difference equations to represent temporal interactions among significantly expressed genes.The authors also introduce interpolation scheme and re-sampling method for equalizing the non-uniformity of sampling time points.Statistical significance plays an active role in obtaining the optimal interaction matrix of GRNs.The constructed genetic network using linear multiple regression matches with the original data very well.Simulation results are given to demonstrate the effectiveness of the proposed method and model.     

Algorithmof communication network reliability combining links,nodes and capacity

1 .INTRODUCTIONWhen communication networkis studied macroscopi-cally,exchange nodes ,links and transmission capaci-ty are the most i mportant parameters .If all these pa-rameters are consideredtogether ,the performancein-dex of communication network can be objectivelyshown.In Refs .[1 ,2] the reliabilityindex of a com-munication network whichintegrates the capacity andthe connection reliability of the links is defined.InRef .[1] ,the reliabilityindexis defined as the trans-mission probab…     

基于数据库信息构建贝叶斯网络的GA方法

主要论述了以现实存在的大量数据库信息为基础构建贝叶斯网络 (BayesianNetworks ,BN)的主要问题。讨论了不确定性知识的图形表示方法 ,以及如何利用专家知识指导属性的排序与选择。鉴于网络结构的复杂度随论域中结点个数的增加呈指数上升 ,如何寻找最佳贝叶斯网络就成为NP -Hard难题 ,应用遗传算法 (GeneticAlgorithms,GA)给出了最佳贝叶斯网络设计的一种新方法 ,并进行了实例计算。     

卫星网络的数学模型和路由算法研究

对卫星网络路由算法研究中存在的问题进行了分析.建立了卫星网络的多约束数学模型,该模型表示了多约束条件下的最小代价问题.在数学模型研究的基础上,对多约束路由算法进行研究,得到一种多约束切换最优路由算法.该算法能够有效地降低路径的切换概率,能够提高计算效率,通过分析表明该算法具有较好的性能.     

多车场满载货运车辆优化调度的网络流算法

探讨在一般条件下的多车场满载的VSP问题。建立了它的网络流模型，并给出了一个基于该网络流最优解的启发式算法。该算法的一个明显特征是，对每一条行车路线的确定总是基于一修改后的网络流模型的最优解，大大提高了算法结果的优化质量。同时，与其它同类算法相比，其算法设计也明显偏优。     

Improved ant colony optimization algorithm for the traveling salesman problems

Ant colony optimization (ACO) is a new heuristic algorithm which has been proven a successful technique and applied to a number of combinatorial optimization problems.The traveling salesman problem (TSP) is among the most important combinatorial problems.An ACO algorithm based on scout characteristic is proposed for solving the stagnation behavior and premature convergence problem of the basic ACO algorithm on TSP.The main idea is to partition artificial ants into two groups: scout ants and common ants.The common ants work according to the search manner of basic ant colony algorithm,but scout ants have some differences from common ants,they calculate each route's mutation probability of the current optimal solution using path evaluation model and search around the optimal solution according to the mutation probability.Simulation on TSP shows that the improved algorithm has high efficiency and robustness.     

基于混合遗传算法的物流配送车辆调度优化问题求解方法

物流配遥车辆调度优化问题是一个NP-hard问题,随着问题规模的扩大,若单纯地应用精确算法将很难获得最优解.首先对物流配送车辆调度问题进行了深入分析并建立了优化数学模型;然后,根据模型把问题的解决合理地划分为两个阶段,将遗传算法的全局搜索能力和C-W节约启发式算法的局部搜索能力有机结合,由此构造出一种混合遗传算法;最后,通过一个应用实例的分析验证了此算法寻优的有效性.