A label-setting algorithm for finding a quickest path

The quickest path problem is to find a path to send a given amount of data from the source to the destination with minimum transmission time. To find the quickest path, existing algorithms enumerate non-dominated paths with distinct capacity, and then determine a quickest path by comparing their transmission time. In this paper, we propose a label-setting algorithm for finding a quickest path by transforming a network to another network where an important property holds that each subpath of a quickest path is also a quickest path. The proposed algorithm avoids enumerating non-dominated paths whose transmission time is greater than the minimum transmission time. Although the computational complexity of the proposed algorithm is the same as that of existing algorithms, experimental results show that our algorithm is efficient when a network has two or more non-dominated paths.     

一种路径测试数据自动生成方法

适应值函数的设计是决定测试数据生成质量和效率的关键,为此提出一种重叠路径结构,对程序路径进行描述,并设计基于遗传算法全路径比较的路径测试数据生成适应值函数。为测试数据生成算法定义生成时间期望的综合性能评价指标,以该指标与对照组算法进行比较实验。结果显示,该适应值函数能较好地平衡算法收敛性和消耗时间之间的矛盾。     

System reliability for a multistate flow network with multiple joint minimal paths under time constraint

The uncertainty of transmission time for a multistate flow network is the main issue when the quickest path problem is applied to such a network. A variant of quickest path problem focusing on the probability of complete transmission instead of finding the quickest path is studied in this paper. In transmission process, a congestion phenomenon may happen when there are joint arcs in minimal paths (MPs). That is, the some arcs are shared by some of MPs. Based on Monte Carlo Simulation, an algorithm is developed to assign the flows through MPs for evaluating the system reliability, the probability that the data can be sent within a time constraint. Experiments are performed to verify the approximate system reliability value obtained from the proposed algorithm is close to the real one. Furthermore, the experiments about CPU time of the algorithm and the characteristics of the variants of quickest path problem are also displayed.     

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

Submodular function minimization is a polynomially solvable combinatorial problem. Unfortunately the best known general-purpose algorithms have high-order polynomial time complexity. In many applications the objective function is locally defined in that it is the sum of cost functions (also known as soft or valued constraints) whose arities are bounded by a constant. We prove that every valued constraint satisfaction problem with submodular cost functions has an equivalent instance on the same constraint scopes in which the actual minimum value of the objective function is rendered explicit. Such an equivalent instance is the result of establishing optimal soft arc consistency and can hence be found by solving a linear program. From a practical point of view, this provides us with an alternative algorithm for minimizing locally defined submodular functions. From a theoretical point of view, this brings to light a previously unknown connection between submodularity and soft arc consistency.     

Solution of minimax problems using equivalent differentiable functions

A method is proposed for the solution of minimax optimization problems in which the individual functions involved are convex. The method consists of solving a problem with an objective function which is the sum of high powers or strong exponentials of the separate components of the original objective function. The resulting objective function, which is equivalent at the limit to the minimax one, is shown to be smooth as well as convex. Any efficient nonlinear programming method can be utilized for solving the equivalent problem. A number of examples are discussed.     

软件测试路径选择优化模型及其进化求解

路径测试是一种非常重要且应用广泛的结构测试方法, 已有路径生成方法的测试效率不高、测试开销较大, 且易生成冗余测试路径. 针对以上问题, 主要研究路径选择问题的优化模型及其进化求解方法, 目的在于: 在不降低测试覆盖率的前提下, 减少冗余路径的数量, 降低测试消耗. 首先, 以多条路径作为决策变量, 基于该决策变量包含的边数和路径数, 建立多目标优化模型; 然后, 采用多目标进化算法求解该模型, 得到目标路径集. 将所提方法应用于7个基准测试程序, 并与其他算法比较. 实验结果表明, 相比其他算法, 所提方法能够在保证测试充分性的条件下, 降低测试消耗, 从而提高测试效率.     

Bicriterion linear programming

Basically leaning on the concept of “best” compromise, the technique seeks the optimal solution by fair relaxations of the objectives commensurate with their degrees of importance until the optimum feasible compromise is reached. The concept is made operational by deriving a linear constraint (referred to as the compromise constraint) to be added into the original set. An offspring of both objective functions, the compromise constraint cuts the original feasible region and forces both objectives to settle on a common point along this added restriction. The resulting singular equivalent of the bicriterion problem optimizes any one of the two objective functions and their equivalent sum (referred to as the supergoal) subject to the new set of constraints. Post optimality analysis is employed to minimize the computational effort usually done by a computer. A very attractive feature of this new practical technique is its ability to search for the optimum in any point in the feasible region, even other than the vertices of the convex set.     

On the performance of multiple-objective genetic local search onthe 0/1 knapsack problem - a comparative experiment

Multiple-objective metaheuristics, e.g., multiple-objective evolutionary algorithms, constitute one of the most active fields of multiple-objective optimization. Since 1985, a significant number of different methods have been proposed. However, only few comparative studies of the methods were performed on large-scale problems. We continue two comparative experiments on the multiple-objective 0/1 knapsack problem reported in the literature. We compare the performance of two multiple-objective genetic local search (MOGLS) algorithms to the best performers in the previous experiments using the same test instances. The results of our experiment indicate that our MOGLS algorithm generates better approximations to the nondominated set in the same number of functions evaluations than the other algorithms     

基于烟花爆炸优化算法的测试数据生成方法

针对面向路径覆盖的测试数据生成问题,提出基于烟花爆炸优化算法的测试数据生成方法。首先使用关键点路径表示法表示路径,由理论路径、易覆盖路径和不可行路径得出难覆盖路径,并记录难覆盖路径邻近的易覆盖路径及其测试数据。这些测试数据将作为部分初始烟花以利用其提供的启发信息,其余初始烟花则随机生成。接着根据个体的适应度值设计自适应策略的爆炸半径以提高收敛速度,对爆炸产生的越界火花则使用边界值测试的思想进行修正。与加了启发信息的自适应爆炸半径的烟花算法（NFEO算法）、烟花爆炸优化（FEO）算法、F-method、NF-method等七种基于优化的测试数据生成算法进行了仿真对比实验,实验结果表明：所提算法在测试数据生成时间和迭代次数上都最优。     

The set of efficient solutions for multiple objective shortest path problems

This paper considers an extension of the usual scalar valued shortest path problem to one in which there are m objective functions and for which we wish to find the efficient set of policies and paths. The paper discusses some of the deficiencies involved in the use of weighting factor methods to determine the efficient sets with respect to the original pure paths and policies. The main result is that if we wish to find which original paths are efficient with respect to the convex extensions of such sets, then they may be obtained exactly by the weighting factor method with minimisation restricted to the original pure policies, and such optimising policies will be jointly efficient in the convex extension, and hence in the original pure set. The paper also discusses linear programming and dynamic programming computational aspects.     

Multiple-criterion shortest path algorithms for global path planning of unmanned combat vehicles

We consider a multiple-criterion shortest path problem with resource constraints, in which one needs to find paths between two points in a terrain for the movement of an unmanned combat vehicle (UCV). In the path planning problem considered here, cumulative traverse time of the UCV, risk level, and (communication) jamming level associated with the paths are limited to be less than or equal to given limits. We propose a modified label-correcting algorithm with a new label-selection strategy to find Pareto-optimal solutions for the multiple objectives of minimizing the traverse time, risk level, and jamming level related to the paths. In addition, we develop a path planning algorithm based on the label-correcting method to solve problems with a single objective within a reasonably short time. For evaluation of the performance of the proposed algorithms, computational experiments are performed on a number of instances, and results show that the proposed algorithms perform better than existing methods in terms of a computation time.     

An Optimal Control-Based Formulation to Determine Natural Locomotor Paths for Humanoid Robots

In this paper we explore the underlying principles of natural locomotion path generation of human beings. The knowledge of these principles is useful to implement biologically inspired path planning algorithms on a humanoid robot. By 'locomotion path' we denote the motion of the robot as a whole in the plane. The key to our approach is to formulate the path planning problem as an optimal control problem. We propose a single dynamic model valid for all situations, which includes both non-holonomic and holonomic modes of locomotion, as well as an appropriately designed unified objective function. The choice between holonomic and non-holonomic behavior is not accomplished by a switching model, but it appears in a smooth way, along with the optimal path, as a result of the optimization by efficient numerical techniques. The proposed model and objective function are successfully tested in six different locomotion scenarios. The resulting paths are implemented on the HRP-2 robot in the simulation environment OpenHRP as well as in the experiment on the real robot.     

网络中多节点故障定位的探测路径选择算法

针对现有故障定位技术不能满足多节点故障定位的要求,尤其当网络中存在大量故障节点时,提出了一种基于主动探测的探测路径选择算法。该算法主要包括用于故障检测的贪婪路径选择算法和用于故障定位的禁忌链路搜索算法。在故障检测阶段,使用贪婪路径选择算法迭代地选择具有最小权重的探测路径覆盖网络中的节点。在故障定位阶段,使用禁忌链路搜索算法多次生成候选路径集以选择最合适的探测路径来解决多节点故障定位问题。在随机网络拓扑和真实网络拓扑上的仿真结果表明,与现有的节点故障定位算法相比,探测路径选择算法具有更高的成功定位率和更低的探测成本。     

基于节点概率的路径覆盖测试数据进化生成

路径覆盖是软件测试领域重要的测试方法之一.为了提高路径覆盖测试效率,在采用遗传算法进化生成路径覆盖的测试数据过程中,利用被测程序条件语句的相关性判定不可达路径,除路径中必经节点外,其他节点在不可达路径中出现的概率越大,穿越该节点的个体就具有越高的穿越度,在进化过程中应得到保护.提出了根据个体的穿越度设计适应度函数方法,从而提高测试数据的生成效率.将所提方法应用于基准程序和工业用例,并与同类方法比较可知,该方法生成路径覆盖的测试数据具有较高的效率.     

On the sure criticality of tasks in activity networks withimprecise durations

The notion of the necessary criticality (both with respect to path and to activity) of a network with imprecisely defined (by means of intervals or fuzzy intervals) activity duration times is introduced and analyzed. It is shown, in the interval case, that both the problem of asserting whether a given path is necessarily critical and the problem of determining an arbitrary necessarily critical path (more exactly, a subnetwork covering all the necessarily critical paths) are easy. The corresponding solution algorithms are proposed. However, the problem of evaluating whether a given activity is necessarily critical does not seem to be so easy. Certain conditions are formulated which, in some situations (but not in all possible situations), allow the necessary criticality of activities to be evaluated. The results obtained for networks with interval activity duration times are generalized to the case of networks with fuzzy activity duration times. Two effective algorithms for calculating the degree of necessary criticality of a fixed path, as well as an algorithm for determining the paths that are necessarily critical to the maximum degree, are proposed.     

Transmission reliability of k minimal paths within time threshold

The quickest path problem involving two attributes, the capacity and the lead time, is to find a single path with minimum transmission time. The capacity of each arc is assumed to be deterministic in this problem. However, in many practical networks such as computer networks, telecommunication networks, and logistics networks, each arc is multistate due to failure, maintenance, etc. Such a network is named a multistate flow network. Hence, both the transmission time to deliver data through a minimal path and the minimum transmission time through a multistate flow network are not fixed. In order to reduce the transmission time, the data can be transmitted through k minimal paths simultaneously. The purpose of this paper is to evaluate the probability that d units of data can be transmitted through k minimal paths within time threshold T. Such a probability is called the transmission reliability. A simple algorithm is proposed to generate all lower boundary points for (d, T), the minimal system states satisfying the demand within time threshold. The transmission reliability can be subsequently computed in terms of such points. Another algorithm is further proposed to find the optimal combination of k minimal paths with highest transmission reliability.     

Solving the fuzzy shortest path problem using multi-criteria decision method based on vague similarity measure

Many researchers have focused on the fuzzy shortest path problem in a network with non-deterministic information due to its importance to various applications. The goal of this paper is to select the shortest path in multi-constrained network using multi-criteria decision method based on vague similarity measure. In our approach, each arc length represents multiple metrics. The multi-constraints are equivalent to the concept of multi-criteria based on vague sets. We propose a similarity measure of vague sets in which the positive constraints and the negative constraints are defined. Furthermore, the procedures are developed to obtain the “best” and “worst” ideal paths. We evaluate similarity degrees between all candidate paths and two ideal paths with the proposed similarity measure. Through comparing the relative degrees of paths, it is shown that the path with the largest relative degree is the shortest path. Finally, we conduct two sets of numerical experiments—using Matlab to verify the feasibility and correctness of the proposed algorithm and developing a routing decision simulation system (RDSS) to demonstrate that the proposed approach is reasonable and effective.     

基于改进遗传模拟退火算法的WSN路径优化算法*

为了更好地解决无线传感器网络（WSN）数据传输的路径优化问题,降低数据传输的能量消耗,提出了一种基于改进遗传模拟退火算法（SAGA）的WSN路径优化算法。首先根据优化目标建立数学模型,然后设计了种群的编码方式,并对遗传算法中的适应度函数、交叉算子、变异算子进行改进,使算法能够更加有效地避免陷入局部搜索;接着根据旧种群和新种群每个对应个体的不同进化程度提出了一种新的Metropolis准则,使模拟退火算法的跳变更具有规律性。实验结果显示：与其它路径优化算法相比,该算法不仅能生成更节能的数据传输路径,而且优化时间也大大降低。所以该算法是一种高效的路径优化算法。     

一种基于非线性长度的多约束路由算法*

满足多个约束的QoS路由问题已经被证明是NP完全问题。在分析了多种路由算法的基础上,设计了一种高效的多约束路由算法。该算法采用非线性路径长度计算方法。为提高算法的成功率,在节点的松弛过程中设计了节点动态路径长度计算,允许节点作多次松弛。为提高算法的执行效率,在节点正向松弛和反向估计过程中引入了受控路径的思想,使算法得到了优化。大量仿真表明,该算法在最短路径获取和路由发现成功率方面都有高效的表现。     

A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates

This paper presents a bicriterion analysis of time/cost trade-offs for the single-machine scheduling problem where both job processing times and release dates are controllable by the allocation of a continuously nonrenewable resource. Using the bicriterion approach, we distinguish between our sequencing criterion, namely the makespan, and the cost criterion, the total resource consumed, in order to construct an efficient time/cost frontier. Although the computational complexity of the problem of constructing this frontier remains an open question, we show that the optimal job sequence is independent of the total resource being used; thereby we were able to reduce the problem to a sequencing one. We suggest an exact dynamic programming algorithm for solving small to medium sizes of the problem, while for large-scale problems we present some heuristic algorithms that turned out to be very efficient. Five different special cases that are solvable by using polynomial time algorithms are also presented.