A MODIFIED DEMPSTER-SHAFER THEORY FOR MULTICRITERIA OPTIMIZATION

Abstract

A new methodology, based on a modified Dempster-Shafer (DS) theory, is proposed for solving multicriteria design optimization problems. It is well known that considerable amount of computational information is acquired during the iterative process of optimization. Based on the computational information generated in each iteration, an evidence-based approach is presented for solving a multiobjective optimization problem. The method handles the multiple design criteria, which are often conflicting and non-commensurable, by constructing belief structures that can quantitatively evaluate the effectiveness of each design in the range 0 to 1. An overall satisfaction function is then defined for converting the original multicriteria design problem into a single-criterion problem so that standard single-objective programming techniques can be employed for the solution. The design of a mechanism in the presence of seven design criteria and eighteen design variables is considered to illustrate the computational details of the approach. This work represents the first attempt made in the literature at applying DS theory for numerical engineering optimization.     

一种结合网络编码的路径代价衡量方法

针对无线路由协议中的路径代价衡量问题,结合网络编码改善无线节点信息互换的思想,提出了一种结合网络编码的路径代价衡量方法--RMNC,其核心思想是利用流量参数反映信息流的网络编码"搭乘"程度和逐节点计算路径的代价.通过将传输流流量参数和路径中节点左右链路信息流流量参数进行运算,获得路径上的各个节点的传输代价;网络中某一条路径的代价等于组成这条路径的节点传输代价之和,通过比较不同路径的逐节点计算代价值,获得最短路径.分析和模拟测试结果表明,RMNC可以有效地获得结合网络编码的最短路径,达到提高传输性能的目的.尽管传输延时有所增加,但可以接受,方法可行.     

A priori least expected time paths in fuzzy,time-variant transportation networks

Dynamics and fuzziness are two significant characteristics of real-world transportation networks. To capture these two features theoretically, this article proposes the concept of a fuzzy, time-variant network characterized by a series of time-dependent fuzzy link travel times. To find an effective route guidance for travelers, the expected travel time is specifically adopted as an evaluation criterion to assess the route generation process. Then the shortest path problem is formulated as a multi-objective 0–1 optimization model for finding the least expected time path over the considered time horizon. Different from the shortest path problem in dynamic and random networks, an efficient method is proposed in this article to calculate the fuzzy expected travel time for each given path. A tabu search algorithm is designed for the problem to generate the best solution under the framework of linear weighted methods. Finally, two numerical experiments are performed to verify the effectiveness and efficiency of the model and algorithm.     

Configuring wide area computer networks

Summary Modern computer networks consist of wide area backbone networks which serve as major highways to transfer large volumes of communication traffic between access points, and local access networks which feed traffic between the backbone network and end user nodes. The topological design of wide area computer communication networks consists of selecting a set of locations for network control processors (NCPs) placement, deciding on backbone links and their capacities to connect the NCPs, linking end user nodes to the NCPs and selecting routes for routing messages between communicating end user pairs. This paper presents some of the problems faced by network designers starting from the capacity assignment problem, moving to routing and capacity assignment, followed by the topological design and capacity assignment problem; the last problem presented is the topological design and capacity expansion over time. The problems are complex combinatorial optimization problems, which require developing new solution procedures. The paper presents the problems and discusses models and solution procedures. The paper concludes with a discussion and directions for further research.This research was partially supported by a Dean's grant for faculty research at the Owen Graduate School of Management, Vanderbilt University, Nashville, TN 37203, USA.     

Load balancing in the provisioning of hose model virtual private networks with multi-path routing

Load balancing in the provisioning of virtual private network (VPN) service in the hose model is studied. Single-path routing and tree routing for the hose model tend to aggregate bandwidth reservations on a small number of links, thus leading to congestion problems in service provider networks. If the link capacity is depleted as a result of improper routing, all future non-VPN traffic will be blocked. We propose a novel multi-objective multi-path (MOMP) routing linear program with the maximum fraction of traffic on a path (MFTP) constraint to solve the problem. The MOMP routing algorithm is able to reduce the bandwidth reservation on the most loaded link by as much as 50%, thus effectively alleviating the potential congestion problems in service provider network. The MFTP constraint provides a guarantee of the availability of multiple paths for each VPN endpoint pair. Further reduction of the bandwidth reservation can be achieved depending on the MFTP value. This is highly significant.     

自组网中一种基于跨层负载感知的蚁群优化路由协议

将蚁群优化和跨层优化方法结合起来,提出了一种基于跨层负载感知和蚁群优化的路由协议(CLAOR)。协议将整个路径中各节点MAC层的总平均估计时延和节点队列缓存的占用情况结合起来,共同作为路由选择和路由调整的重要度量标准进行按需路由发现和维护,通过拥塞节点丢弃蚂蚁分组以及借助部分兼具蚂蚁功能的数据分组实现正常路由表的维护等方法,减少了控制开销,增加了算法的可扩展性,较好地解决了自组网中现有基于蚁群优化的路由协议中普遍存在的拥塞问题、捷径问题和引入的路由开销问题。仿真结果表明,CLAOR在分组成功递交率、路由开销以及端到端平均时延等方面具有优良性能,能很好地实现网络中的业务流负载均衡。     

Q-Learning Based Routing Protocol for Congestion Avoidance

The end-to-end delay in a wired network is strongly dependent on congestion on intermediate nodes. Among lots of feasible approaches to avoid congestion efficiently, congestion-aware routing protocols tend to search for an uncongested path toward the destination through rule-based approaches in reactive/incident-driven and distributed methods. However, these previous approaches have a problem accommodating the changing network environments in autonomous and self-adaptive operations dynamically. To overcome this drawback, we present a new congestion-aware routing protocol based on a Q-learning algorithm in software-defined networks where logically centralized network operation enables intelligent control and management of network resources. In a proposed routing protocol, either one of uncongested neighboring nodes are randomly selected as next hop to distribute traffic load to multiple paths or Q-learning algorithm is applied to decide the next hop by modeling the state, Q-value, and reward function to set the desired path toward the destination. A new reward function that consists of a buffer occupancy, link reliability and hop count is considered. Moreover, look ahead algorithm is employed to update the Q-value with values within two hops simultaneously. This approach leads to a decision of the optimal next hop by taking congestion status in two hops into account, accordingly. Finally, the simulation results presented approximately 20% higher packet delivery ratio and 15% shorter end-to-end delay, compared to those with the existing scheme by avoiding congestion adaptively.     

OSPF routing with optimal oblivious performance ratio under polyhedral demand uncertainty

We study the best OSPF style routing problem in telecommunication networks, where weight management is employed to get a routing configuration with the minimum oblivious ratio. We consider polyhedral demand uncertainty: the set of traffic matrices is a polyhedron defined by a set of linear constraints, and a routing is sought with a fair performance for any feasible traffic matrix in the polyhedron. The problem accurately reflects real world networks, where demands can only be estimated, and models one of the main traffic forwarding technologies, Open Shortest Path First (OSPF) routing with equal load sharing. This is an NP-hard problem as it generalizes the problem with a fixed demand matrix, which is also NP-hard.     

Non-linear game models for large-scale network bandwidth management

The design of dynamic Label-Switched Paths (LSP’s) in MultiProtocol Label Switched (MPLS) networks is an NP-hard optimization problem. An LSP is a logical path between two nodes in the network. This path has a pre-reserved amount of bandwidth that defines its size. The LSP design problem consists of determining the number of these logical links and configuring the physical path and the size of each LSP. This paper presents an optimization model based on game theory. In this approach, connection requests are modeled as competitive players in a noncooperative game context. The transport network bandwidth constitutes the resource for which optimization is sought. The outcome of this optimization is a set of LSPs upon which the competing connections are routed.     

Efficient Routing Protection Algorithm in Large-Scale Networks

With an increasing urgent demand for fast recovery routing mechanisms in large-scale networks, minimizing network disruption caused by network failure has become critical. However, a large number of relevant studies have shown that network failures occur on the Internet inevitably and frequently. The current routing protocols deployed on the Internet adopt the reconvergence mechanism to cope with network failures. During the reconvergence process, the packets may be lost because of inconsistent routing information, which reduces the network’s availability greatly and affects the Internet service provider’s (ISP’s) service quality and reputation seriously. Therefore, improving network availability has become an urgent problem. As such, the Internet Engineering Task Force suggests the use of downstream path criterion (DC) to address all single-link failure scenarios. However, existing methods for implementing DC schemes are time consuming, require a large amount of router CPU resources, and may deteriorate router capability. Thus, the computation overhead introduced by existing DC schemes is significant, especially in large-scale networks. Therefore, this study proposes an efficient intra-domain routing protection algorithm (ERPA) in large-scale networks. Theoretical analysis indicates that the time complexity of ERPA is less than that of constructing a shortest path tree. Experimental results show that ERPA can reduce the computation overhead significantly compared with the existing algorithms while offering the same network availability as DC.     

Flooding-limited for multi-constrained quality-of-service routing protocol in mobile ad hoc networks

Multi-constrained quality-of-service (QoS) routing is used to find routes in a network to satisfy multiple independent QoS constraints. This problem is considered to be NP-complete, and most existing QoS routing algorithms are based on maintaining a global network state at every node. A multi-constrained, flooding-limited, QoS routing method to deal with limited available resources and minimum computation in a dynamic environment is proposed. The solution is based on decomposition of a routing area and a restriction in the exchange of routing information. It reduces the size of the control messages, restricts the amount of routing information, minimises the overhead from the flooding of control traffic and decreases the complexity of path selection. It is also proved that the flooding-limited-path heuristic can achieve very high performance by maintaining entries in each node, which indicates that the performance of the limited-path heuristic is not sensitive to the number of constraints. Simulation results show that this protocol provides better performance than other protocols, especially with regards to end-to-end delay, throughput and packet loss.     

An approach to machining process optimization

Optimization is rightly claimed to be the most significant factor distinguishing the modern approach to machining processes from the orthodox one. Practical results can be obtained from the application of mathematical modelling and optimization techniques.

The paper presents a procedure for solution of machining process optimization problems, with the use of theory of graphs and Bellman's optimum principle.

The finite graph G=(N, A) (where -N denoted a set of nodes and A the set of arcs) here presents the set of feasible solutions. Each are represents a corresponding machining operation and each path the feasible machining process.

A number can be associated with each are : the increment of criterion for optimality. Using the optimum principle we can find the shortest possible path in the graph, thus solving given problems of choice for the optimal machining process.

There is a variety of ways in which the performance criterion can be formulated. In this paper only those performance measures having sufficient economical justification are considered. We may minimize the costs of machining processes, or optimize economical effectiveness of capital engaged.

The method presented can be applied with every additive criterion, as well as with some non-additive ones. A practical example illustrates the field of possible application of this method.     

Integrated optimization of machine product design and process design

In order to attain the true integration of computer-aided design and computer-aided manufacturing not only is a smooth flow of information required, but also decision making for both product design and process design must be synthesized. In this paper an integrated design process is proposed in which decisions concerning both product design and process design are simultaneously made. According to the proposed design procedures, an integrated optimization problem is formulated. This optimization is expressed as a multiobjective optimization problem which produces many Pareto optimum solution sets corresponding to combinations of materials used for parts. The algorithm for solving the problem is also presented. The proposed method is applied to designing a cylindrical co-ordinate robot, thereby demonstrating the effectiveness of conducting a simultaneous process through product design and process design.     

Quantized hopfield networks for reliability optimization

The use of neural networks in the reliability optimization field is rare. This paper presents an application of a recent kind of neural networks in a reliability optimization problem for a series system with multiple-choice constraints incorporated at each subsystem, to maximize the system reliability subject to the system budget. The problem is formulated as a nonlinear binary integer programming problem and characterized as an NP-hard problem. Our design of neural network to solve efficiently this problem is based on a quantized Hopfield network. This network allows us to obtain optimal design solutions very frequently and much more quickly than others Hopfield networks.     

Sequential algorithms for structural design optimization under tolerance conditions

A deterministic optimization usually ignores the effects of uncertainties in design variables or design parameters on the constraints. In practical applications, it is required that the optimum solution can endure some tolerance so that the constraints are still satisfied when the solution undergoes variations within the tolerance range. An optimization problem under tolerance conditions is formulated in this article. It is a kind of robust design and a special case of a generalized semi-infinite programming (GSIP) problem. To overcome the deficiency of directly solving the double loop optimization, two sequential algorithms are then proposed for obtaining the solution, i.e. the double loop optimization is solved by a sequence of cycles. In each cycle a deterministic optimization and a worst case analysis are performed in succession. In sequential algorithm 1 (SA1), a shifting factor is introduced to adjust the feasible region in the next cycle, while in sequential algorithm 2 (SA2), the shifting factor is replaced by a shifting vector. Several examples are presented to demonstrate the efficiency of the proposed methods. An optimal design result based on the presented method can endure certain variation of design variables without violating the constraints. For GSIP, it is shown that SA1 can obtain a solution with equivalent accuracy and efficiency to a local reduction method (LRM). Nevertheless, the LRM is not applicable to the tolerance design problem studied in this article.     

Optimization of measurement processes under metrological provision for complex technological systems

A dynamic problem of optimizing a selection of measured quantities and measuring devices is formulated. For a class of linear dynamic objects, an optimal controller of the measurement processes is designed. An example of solving an optimization problem for metrological provision of a testing equipment is presented.Translated from Izmeritel'naya Tekhnika, No. 8, pp. 3–5, August, 1994.     

Optimization of actively controlled structures using goal programming techniques

The problem of design of actively controlled structures subject to restrictions on the damping parameters of the closed-loop system is formulated and solved as a multiobjective optimization problem. The purpose of control is to effectively suppress structural vibrations due to initial excitation. The cross-sectional areas of the members are treated as design variables. The structural weight and the controlled system energy are considered as objective functions for minimization. The goal programming approach is used for the solution of the multiobjective optimization problems. The procedure is illustrated through numerical simulations using two-bar and twelve-bar truss structures.     

Optimal flow path design of unidirectional AGV systems

This paper describes an alternative formulation of the AGV flow path layout (FPL) problem which was first formulated by Gaskins and Tanchoco (1987) as a zero-one integer programming problem. A computationally efficient procedure is proposed which is based on the branch-and-bound technique. An algorithm for satisfying the reachability condition for nodes in the AGV flow path network is also presented. A simple illustrative example is discussed to demonstrate the procedure, and a more complex problem is also given.     

The complexity of routing in hierarchical PNNI networks

We study the complexity of computing a route in a hierarchical PNNI network, with H levels of hierarchy, in which N nodes are grouped into clusters at each level. We determine cluster sizes that minimize an upper bound on the total time for all the path computations required to compute a route. Our model casts the problem as a nonlinear convex optimization problem, and employs nonlinear duality theory. We derive explicit closed form upper bounds on the minimum total path computation time, as a function of N, for H=2 and H=3, and show how the upper bound, and the optimal cluster sizes, can be computed for any H. We provide a conjecture on the complexity of PNNI routing for any H, and use this conjecture to determine the limit of the complexity as H→∞. We also prove that the minimum total path computation time is a non-increasing function of H. Our results provide counterexamples to a claim by Van Mieghem that a related top-down hierarchical routing method has lower computational complexity.