Decision making with multiple objectives using GAI networks

This paper deals with preference representation on combinatorial domains and preference-based recommendation in the context of multicriteria or multiagent decision making. The alternatives of the decision problem are seen as elements of a product set of attributes and preferences over solutions are represented by generalized additive decomposable (GAI) utility functions modeling individual preferences or criteria. Thanks to decomposability, utility vectors attached to solutions can be compiled into a graphical structure closely related to junction trees, the so-called GAI network. Using this structure, we present preference-based search algorithms for multicriteria or multiagent decision making. Although such models are often non-decomposable over attributes, we actually show that GAI networks are still useful to determine the most preferred alternatives provided preferences are compatible with Pareto dominance. We first present two algorithms for the determination of Pareto-optimal elements. Then the second of these algorithms is adapted so as to directly focus on the preferred solutions. We also provide results of numerical tests showing the practical efficiency of our procedures in various contexts such as compromise search and fair optimization in multicriteria or multiagent problems.     

Path planning with multiple objectives

Most path planners are designed to generate a single path that is optimal in terms of some criterion such as path length or travel time. However, for realistic terrain navigation we wish to find a path that is reasonable to execute in a given environment. Therefore we must consider several factors, such as safety, time, and energy consumption. In this article the authors investigate how to find a set of paths (as opposed to a single path) so as to permit various choices concerning multiple criteria. They present simulation results to demonstrate the feasibility of the approach and discuss an extension to navigation in time-varying scenes     

Controller design with multiple objectives

In this paper we study multi-objective control problems that give rise to equivalent convex optimization problems. We develop a uniform treatment of such problems by showing their equivalence to linear programming problems with equality constraints and an appropriate positive cone. We present some specialized results on duality theory, and we apply them to the study of three multi-objective control problems: the optimal l₁ control with time-domain constraints on the response to some fixed input, the mixed H₂/l₁ -control problem, and the l₁ control with magnitude constraint on the frequency response. What makes these problems complicated is that they are often equivalent to infinite-dimensional optimization problems. The characterization of the duality relationship between the primal and dual problem allows us to derive several results. These results establish connections with special convex problems (linear programming or linear matrix inequality problems), uncover finite-dimensional structures in the optimal solution, when possible, and provide finite-dimensional approximations to any degree of accuracy when the problem does not appear to have a finite-dimensional structure. To illustrate the theory and highlight its potential, several numerical examples are presented     

复杂网络中随机图模型研究

随着复杂网络研究的兴起,随机图成为一种重要复杂网络模型。基于完全图的生成子图的思想,得到了生成随机图的一种新算法,即用去边的方法生成随机图的算法,并用数值实验验证了加边和去边生成的随机图的统计特性（最大度、最小度、聚集系数、平均最短路径和平均度）是相近的,用去边的方法得到的图的度分布曲线在其平均度处达到峰值,随后呈指数下降,这与随机图的度分布是相同的。为了得到稀疏连通的随机图,又提出了一个不去割边的近似随机图生成算法,并从理论上说明了该算法生成的图是连通的,同时通过数值实验验证了图的连通性,并与加边随机图的统计特性进行了比较。     

Connectivity model of wireless networks via dependency links random graphs

We lay down the foundations of a new approach for finding the network connectivity in wireless networks, with special regard to the properties of dependencies between links of geometrically collocated nodes. The proposed methodology is rooted in the theory of random graphs, but we significantly extend the conventional random graph model, as in its original definition it would be too sterile to capture realistic wireless networks. A closed form expression for the network connectivity was derived by an equilateral hexagon topology introduced from the minimum set covering problem. We also analyzed the effect of boundary nodes on the connectivity of an infinitely and a finitely large network. Through a combination of mathematical proof and simulations, we have shown that our result provides a robust performance in wireless networks.     

Handling multiple objectives with biogeography-based optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which uses the cluster attribute of islands to naturally decompose the problem. The proposed algorithm makes use of nondominated sorting approach to improve the convergence ability effciently. It also combines the crowding distance to guarantee the diversity of Pareto optimal solutions. We compare the BBMO with two representative state-of-the-art evolutionary multi-objective optimization methods, non-dominated sorting genetic algorithm-II (NSGA-II) and archive-based micro genetic algorithm (AMGA) in terms of three metrics. Simulation results indicate that in most cases, the proposed BBMO is able to find much better spread of solutions and converge faster to true Pareto optimal fronts than NSGA-II and AMGA do.     

Algorithms for dense graphs and networks on the random access computer

We improve upon the running time of several graph and network algorithms when applied to dense graphs. In particular, we show how to compute on a machine with word size = (logn) a maximal matching in ann-vertex bipartite graph in timeO(n ²+n ^2.5/)=O(n ^2.5/logn), how to compute the transitive closure of a digraph withn vertices andm edges in timeO(n ²+nm/), how to solve the uncapacitated transportation problem with integer costs in the range [O.C] and integer demands in the range [–U.U] in timeO ((n ³ (log log/logn)^1/2+n² logU) lognC), and how to solve the assignment problem with integer costs in the range [O.C] in timeO(n ^2.5 lognC/(logn/loglogn)^1/4).Assuming a suitably compressed input, we also show how to do depth-first and breadth-first search and how to compute strongly connected components and biconnected components in timeO(n+n ²/), and how to solve the single source shortest-path problem with integer costs in the range [O.C] in time0 (n ²(logC)/logn). For the transitive closure algorithm we also report on the experiences with an implementation.Most of this research was carried out while both authors worked at the Fachbereich Informatik, Universität des Saarlandes, Saarbrücken, Germany. The research was supported in part by ESPRIT Project No. 3075 ALCOM. The first author acknowledges support also from NSERC Grant No. OGPIN007.     

On multistage interconnection networks with small clock cycles

In packet switching using multistage interconnection networks (MIN's), it is generally assumed that the packet movements successively propagate from the last stage to the first stage in one network cycle. Ding and Bhuyan (1994), however, have shown that the network performance can be significantly improved if the packet movements are confined within each pair of adjacent stages using small clock cycles. In this short note, we present a model for estimating the performance of multibuffered MIN's employing the approach. Using the model, the relative effectiveness of the approach is identified compared to the traditional design     

Rapidly exploring random graphs: motion planning of multiple mobile robots

Rapidly exploring random trees (RRT) and probabilistic roadmaps (PRM) are sampling-based techniques being extensively used for robot path planning. In this paper, the tree structure of the RRT is generalized to a graph structure which enables a greater exploration. Exploration takes place simultaneously from multiple points in the map, all explorations fusing at multiple points producing well-connected graph architecture. Initially, in a typical RRT manner, the search algorithm attempts to reach the goal by expansions, and thereafter furtherer areas are explored. With some additional computation cost, as compared to RRT with a single robot, the results can be significantly improved. The so-formed graph is similar to roadmap produced by PRM. However as compared to PRM, the proposed algorithm has a more judicious search strategy and is adaptable to the number of nodes as a parameter. Experimental results are shown with multiple robots planned using prioritization scheme. Results show the betterment of the proposed algorithm as compared to RRT and PRM techniques.     

Handling multiple objectives with particle swarm optimization

This paper presents an approach in which Pareto dominance is incorporated into particle swarm optimization (PSO) in order to allow this heuristic to handle problems with several objective functions. Unlike other current proposals to extend PSO to solve multiobjective optimization problems, our algorithm uses a secondary (i.e., external) repository of particles that is later used by other particles to guide their own flight. We also incorporate a special mutation operator that enriches the exploratory capabilities of our algorithm. The proposed approach is validated using several test functions and metrics taken from the standard literature on evolutionary multiobjective optimization. Results indicate that the approach is highly competitive and that can be considered a viable alternative to solve multiobjective optimization problems.     

Analysis of robust performance with multiple objectives

Performance robustness with multiple objectives of linear control systems having structured norm-bounded uncertainty is considered. In order to deal with any two objective functions Ψ₁ and Ψ₂ associated with a single feedback control system, the combined criterion Ψ[Ψ₁ ψ₂]Ψ S 1 is often used. The paper, however, considers Ψ ψ₁ Ψ 1 and Ψ W, 11 1 directly. It is shown that it is possible to assess robust performance of two objectives by a single μ test if repeated nonscalar blocks are adequately introduced in the structure of μ. In other words, a performance robustness problem with multiple objectives is proved to be equivalent to a stability robustness problem with extra repeated uncertainty blocks. This equivalence theorem is applicable to various system and norm setups including sampled-data systems.     

A new approach to model virtual channels in interconnection networks

Dealing with virtual channels has always been a critical issue in developing analytical performance models for interconnection networks. Almost all previous studies relied on a method proposed by Dally to capture the effect of virtual channels multiplexing in the performance of interconnection networks. This paper presents a new method to model the effect of virtual channel multiplexing in high-speed wormhole-switched interconnection networks. Dally's method loses its accuracy as the traffic load increases due to blocking nature of wormhole-switched networks. Our new method is based on a finite capacity queue, M/G/1/V and comparing to Dally's method achieves a higher degree of accuracy under low, moderate and high traffic loads. Furthermore, its simplicity eases its employment under different network conditions and setup. The presented model is validated by means of an event driven simulator and a detailed comparison with Dally's method is presented.     

An introduction to the multistage cube family of interconnection networks

The interconnection network in large-scale parallel/distributed supercomputer systems is a crucial component. Three networks are overviewed here. Multistage cube networks represent an important family of networks, which includes the omega, n-cube, multistage shuffle-exchange, delta, baseline, SW-banyan, and Generalized Cube. This family has been used or proposed for use in such systems as staran, pasm, Ultracomputer, the BBN Butterfly, the IBM RP3, and data-flow machines. The multistage cube topology, distributed routing control, and ability to be partitioned into independent subnetworks are examined. The Extra Stage Cube (ESC), a single-fault-tolerant multistage cube network, is described. The structure, control, and partitionability of the ESC, and how it functions when multiple faults occur, are presented. The Dynamic Redundancy (DR) network, a fault-tolerant multistage cube network that supports the incorporation of spare processors for fault tolerance, is discussed. Its structure, control, and partitionability into single-fault-tolerant subnetworks are explained.This research was supported by the Air Force Office of Scientific Research under grant F49620-86-K-0006, the Rome Air Development Center under grant F30602-83-K-0119, and the Purdue Research Foundation David Ross Grant 1985/86 no. 0857.currently with the Supercomputing Research Center, 4380 Forbes Blvd., Lanham, MD 20706 (as of June 1, 1987).currently with Computer Science Department, University of Illinois, Urbana-Champaign, IL 61801.     

Influence diagrams with multiple objectives and tradeoff analysis

Influence diagrams have been important models for decision problems because of their ability to both model a problem rigorously at its mathematical level and depict its high-level structure graphically. Once the structure and numerical details of an influence diagram have been specified, it can be evaluated to determine the optimal decision policy. However, when evaluating multiple objectives, in the past this determination was based on the assumption that utility functions that commensurate the objectives are available. This paper extends the structure and solution algorithm for influence diagrams to allow for the inclusion of noncommensurate objectives using multiobjective tradeoff analysis instead of utility theory. This eliminates the need to specify any preference information before the influence diagram is solved. The proposed multiobjective-based methodology is also useful for decision makers who either do not want to accept the assumptions of utility theory for a particular problem, or are confronted with a problem in which it is neither practical nor viable to construct a utility function. Additionally, this paper establishes the relationship between multiobjective influence diagrams and multiobjective decision trees. This relationship is important because it allows a decisionmaker to utilize the advantages of both representations. An example problem is presented to introduce both the extended multiobjective influence diagram methodology and the relationship linking multiobjective decision trees to multiobjective influence diagrams.     

Target containment control of multi-agent systems with random switching interconnection topologies

In this paper, the distributed containment control is considered for a second-order multi-agent system guided by multiple leaders with random switching topologies. The multi-leader control problem is investigated via a combination of convex analysis and stochastic process. The interaction topology between agents is described by a continuous-time irreducible Markov chain. A necessary and sufficient condition is obtained to make all the mobile agents almost surely asymptotically converge to the static convex leader set. Moreover, conditions on the tracking estimation are provided for the convex target set determined by moving multiple leaders.     

A constructive algorithm to synthesize arbitrarily connected feedforward neural networks

In this work we present a constructive algorithm capable of producing arbitrarily connected feedforward neural network architectures for classification problems. Architecture and synaptic weights of the neural network should be defined by the learning procedure. The main purpose is to obtain a parsimonious neural network, in the form of a hybrid and dedicate linear/nonlinear classification model, which can guide to high levels of performance in terms of generalization. Though not being a global optimization algorithm, nor a population-based metaheuristics, the constructive approach has mechanisms to avoid premature convergence, by mixing growing and pruning processes, and also by implementing a relaxation strategy for the learning error. The synaptic weights of the neural networks produced by the constructive mechanism are adjusted by a quasi-Newton method, and the decision to grow or prune the current network is based on a mutual information criterion. A set of benchmark experiments, including artificial and real datasets, indicates that the new proposal presents a favorable performance when compared with alternative approaches in the literature, such as traditional MLP, mixture of heterogeneous experts, cascade correlation networks and an evolutionary programming system, in terms of both classification accuracy and parsimony of the obtained classifier.     

A genetic algorithm approach to the machine-component grouping problem with multiple objectives

The formation of machine cells and component families is a problem that has engaged the attention of researchers in group technology for over a decade. This paper proposes a bi-criteria mathematical model with a solution procedure based on a genetic algorithm. Trials on a sample problem suggest that the proposed algorithm can be a powerful tool that can be gainfully employed in a cellular manufacturing environment. The algorithm is inherently parallel and is capable of super linear speed-up in multi-processor systems.     

A staff to job assignment (partitioning) problem with multiple objectives

A 0–1 goal programming (GP) model is presented, based on an actual case example, for assigning projects to engineers in order to prevent project splitting and excessive manpower requirements, complete as many preferred projects as possible and maximize profits while keeping a balanced workload. For assigning 15 projects to 6 engineers, the GP model contains 90 0–1 decision variables and 28 goals grouped into 5 priorities. This problem could not be solved with 0–1 GP codes that were readily available. It was, however, easily solved under different priority structures, in a few CPU seconds, using a heuristic 0–1 GP method. The approach is simple and naturally understood by management, and it can easily be adopted to other similar situations.