No. 3 (2003)
Published:
2003-09-30
ARTICLES FROM THIS ISSUE
-
Possibilistic approach to Bayes decisions
Abstract
The decision problems are considered when the prior probabilistic information about the state of nature and decision maker`s utility function are imprecisely defined. In such a case the risks (or the expected utility) of considered decisions are also imprecisely defined. We propose two-step procedure for finding the optimal decision. First, we order possible decisions using the lambda-average ranking method by Campos and Gonzalez. Then we use possibilistic possibility of dominance and necessity of strict dominance indices proposed by Dubois and Prade for the comparison of consequences of the most promising solutions.
-
Weight versus reference point multiple criteria decision making methods - analogies and differences
Abstract
In this work we shall be concerned with interactive multiple criteria decision making methods. We show how on the technical level the class of reference point methods can be reduced to the class of weight methods. Though methods from these two classes represent two different interactive decision making paradigms, the equivalence observed opens a way for a joint implementation of a pair of methods each representing a different class. This would establish a firm ground for systematic comparison of both classes of methods as well as for hybrid schemes mixing decisional tools specific for each class.
-
Application of multiple criteria evolutionary algorithms to vector optimisation, decision support and reference point approaches
Abstract
Multiple criteria evolutionary algorithms, being essentially parallel in their character, are a natural instrument of finding a representation of entire Pareto set (set of solutions and outcomes non-dominated in criteria space) for vector optimisation problems. However, it is well known that Pareto sets for problems with more than two criteria might become complicated and their representation very time-consuming. Thus, the application of such algorithms is essentially limited to bi-criteria problems or to vector optimisation problems with more criteria but of simple structure. Even in such cases, there are problems related to various important aspects of vector optimisation, such as the uniformity of representation of Pareto set, stopping tests or the accuracy of representing Pareto set, that are not fully covered by the broad literature on evolutionary algorithms in vector optimisation. These problems and related computational tests and experience are discussed in the paper. In order to apply evolutionary algorithms for decision support, it would be helpful to use them in an interactive mode. However, evolutionary algorithms are in their essence global and of batch type. Nevertheless, it is possible to introduce interactive aspects to evolutionary algorithms by focusing them on a part of Pareto set. The results of experimental tests of such modifications of evolutionary algorithms for vector optimisation are presented in the paper. Another issue related to vector optimisation problems with more than two criteria is the computational difficulty of estimating nadir points of Pareto set. The paper describes the use of diverse variants of evolutionary algorithms to the estimation of nadir points, together with experimental evidence.
-
Fair resource allocation schemes and network dimensioning problems
Abstract
Resource allocation problems are concerned with the allocation of limited resources among competing activities so as to achieve the best overall performances of the system but providing fair treatment of all the competitors. Telecommunication networks are facing the increasing demand for Internet services. Therefore, a problem of network dimensioning with elastic traffic arises which requires to allocate bandwidth to maximize service flows with fair treatment of all the services. In such applications, the so-called max-min fairness (MMF) solution concept is widely used to formulate the resource allocation scheme. This guarantees the fairness but may lead to significant losses in the overall throughput of the network. In this paper we show how multiple criteria optimization concepts can be used to generate various fair resource allocation schemes. The solution concepts are tested on the network dimensioning problem and their abilities to model various preferences are demonstrated.
-
Some variants of projection methods for large nonlinear optimization problems
Abstract
Two ideas of modifying projection methods for the case of smooth nonlinear optimization are presented. Projection methods were originally successfully used in solving large-scale linear feasibility problems. The proposed instantiations of projection methods fall into two groups. One of them is a decomposition approach in which projections onto sets are realized as optimization problems which themselves involve much portions of original problem constraints. There are two subproblems: one build with linear constraints of the original problem and the second one build with original nonlinear constraints. These approaches use special accelerating cuts so that the separation of nonlinear and linear constraints can be effective and some problem sparsity preserved. The second group bases on penalty-shifting/multiplier methods and draws from the observation that unconstrained subproblems obtained there may solve very slowly due to their nonsmooth character. Thus it is proposed to solve them with modified projection methods which inherit from conjugate gradient methods a multi-dimensional subspace in one epoche.
-
A new multiple objective dynamic routing method using implied costs
Abstract
There are advantages in considering the routing problem in integrated communication networks as a multiobjective shortest path problem, having in mind to grasp eventual conflicts and trade-offs among distinct objectives and quality of services (QoS) constraints. On the other hand the utilisation of dynamic routing methods in various types of networks is well known to have significant impact on network performance and cost, namely in overload and failure conditions. This paper presents the detailed formulation of a proposal of a multiple objective dynamic routing method (MODR) of periodic state dependent routing type, enabling to represent distinct QoS related metrics and requirements in a consistent manner. The MODR method present formulation is based on a multiple objective shortest path model with constraints and is prepared to use implied costs as one of the metrics. Alternative paths for each traffic flow are changed as a function of periodic updates of certain QoS related parameters estimated from real time measurements on the routes and trunks of the network. Such paths are computed by a specialised and efficient variant of a bi-objective shortest path constrained algorithm, developed for the MODR, enabling to incorporate flexible requirements on the QoS metrics. The architecture of the routing system is discussed together with the features of its main modules. An illustrative example of application of the MODR path calculation module to a circuit-switched type network using blocking probability and implied cost as metrics, is also presented, considering different overload conditions.
-
Implementation and performance of a new multiple objective dynamic routing method for multiexchange networks
Abstract
The paper describes new developments of a multiple objective dynamic routing method (MODR) for circuit-switched networks previously presented, based on the periodic calculation of alternative paths for every node pair by a specialised bi-objective shortest path algorithm (MMRA). A model is presented that enables the numerical calculation of two global network performance parameters, when using MMRA. This model puts in evidence an instability problem in the synchronous path computation model which may lead to solutions with poor global network performance, measured in terms of network mean blocking probability and maximum node-to-node blocking probability. The essential requirements of a heuristic procedure enabling to overcome this problem and select ``good`` routing solutions in every path updating period, are also discussed.
-
On the connections between optimal control, regulation and dynamic network routing
Abstract
he paper is devoted to studying general features of dynamic network routing problems. It is shown that these problems may be interpreted as receding horizon optimal control problems or simply regulation problems. In the basic formulation it is assumed, that the nodes have no dynamics and the only goal of the optimization mechanism is to find the shortest paths from the source to the destination nodes. In this problem the optimization mechanism (i.e. the Bellman-Ford algorithm) may be interpreted as a receding horizon optimal control routine. Moreover, there is one-to-one correspondence between the Bellman optimal cost-to-go function in the shortest path problem and the Lyapunov function in the regulation problem. At the end some results of the application of the routing optimization algorithm to an inverted pendulum regulation problem are presented.
-
Heuristic algorithms in topological design of telecommunication networks
Abstract
The paper addresses the generic topological network design problem and considers the use of various heuristic algorithms for solving the problem. The target of the optimisation is to determine a network structure and demand allocation pattern that would minimise the cost of the network, which is given by fixed installation costs of nodes and links and variable link capacity costs described by linear or concave functions. Input data for the optimisation consists of a list of potential node and link locations and their costs and a set of demands defined between the nodes. Since the problem is known to be NP-hard, the use of specialised heuristic algorithms is proposed. The presented approaches encompass original ideas as well as selected methods described in literature and their enhancements. The algorithms are based on the following ideas and methods: shifting of individual flows, local and global restoration of flows from chosen links or nodes, Yaged algorithm for finding local minima, Minoux greedy algorithm, simulated allocation and genetic algorithms. Efficiency of each of the proposed methods is tested on a set of numerical examples.
-
Optimization algorithm for reconfiguration process of the IP over optical networks
Abstract
The IP over optical (IPO) network is becoming one of the most interesting among all proposed models of transport networks nowadays. In an IPO network, the reconfiguration capability of the network could be used in order to balance the load of its network elements (NEs). Reconfiguration operations (i.e., switching in OXC nodes and rerouting in IP routers) take place in real-time. Consequently, intensive changes in NEs settings might cause failures in the existing connections in the network. For that reason, changes in NEs settings should be coordinated in a reconfiguration process. In this paper, the author has proposed an optimization method for such reconfiguration process. The mathematical model of the method including computation results has been presented. -
Contextual probability
Abstract
In this paper we present a new probability function G that generalizes the classical probability function. A mass function is an assignment of basic probability to some context (events, propositions). It represents the strength of support for some contexts in a domain. A context is a subset of the basic elements of interest in a domain - the frame of discernment. It is a medium to carry the ``probabilistic`` knowledge about a domain. The G function is defined in terms of a mass function under various contexts. G is shown to be a probability function satisfying the axioms of probability. Therefore G has all the properties attributed to a probability function. If the mass function is obtained from probability function by normalization, then G is shown to be a linear function of probability distribution and a linear function of probability. With this relationship we can estimate probability distribution from probabilistic knowledge carried in some contexts without any model assumption.
-
Decision algorithms and flow graphs; a rough set approach
Abstract
This paper concerns some relationship between Bayes` theorem and rough sets. It is revealed that any decision algorithm satisfies Bayes` theorem, without referring to either prior or posterior probabilities inherently associated with classical Bayesian methodology. This leads to a new simple form of this theorem, which results in new algorithms and applications. Besides, it is shown that with every decision algorithm a flow graph can be associated. Bayes` theorem can be viewed as a flow conservation rule of information flow in the graph. Moreover, to every flow graph the Euclidean space can be assigned. Points of the space represent decisions specified by the decision algorithm, and distance between points depicts distance between decisions in the decision algorithm.
-
A world according to artificial neural networks
Abstract
This paper presents results from a preliminary study in the field of artificial neural networks (ANN). The overall aim of our work relates to the field of cognitive science. In this wider framework we try to investigate, reason about, and model cognitive processes in order to obtain a better understanding of the major processing device involved - the human brain. In terms of content this paper presents a novel ANN learning approach. Note that throughout the paper we assume supervised learning. In contrast to the classical ANN learning approach where an ANN algorithm alters an initial random weight assignment until a reasonable solution to a problem is obtained this approach does not alter the initial random weight assignment at all, but provides a solution to the problem by transforming the actual input data. The approach is applied to perceptrons and adalines and its quality is demonstrated on simple classification problems.
-
The role of time in influence diagrams
Abstract
An influence diagram is a compact representation emphasizing the qualitative features of decision problem under uncertainty. Classical influence diagram has parameters stable in time, determined order of suggested decisions and generally is independent of time. Here we have shown some possible methods of construction of time dependent influence diagrams: with decision ordering, time-sliced segments and time consuming nodes. Such gathering of methods can help in selection of a proper solution.
-
Briefly on the GUHA method of data mining
Abstract
The paper gives brief, user-oriented, information on the GUHA method.
-
Data mining and complex telecommunications problems modeling
Abstract
The telecommunications operators have to manage one of the most complex systems developed by human beings. Moreover, the new technological developments, the convergence of voice and data networks and the broad range of services still increase this complexity. Such complex object as telecommunication network requires advanced software tools for their planning and management. Telecommunications operators collect large volumes of the data in various databases. They realize that the knowledge in these huge databases might significantly improve various organizational strategic and operational decisions. However, this knowledge is not given explicitly, it is hidden in data. Advanced methods and algorithms are being developed for knowledge extracting. In this paper we will focus on using data mining for solving selected problems in telecommunication industry. We will provide a systematic overview of various telecommunications applications.
-
The use of quantitative association rules in cellular network planning
Abstract
This paper describes the problem of planning cellular network base stations with optimization to traffic requirements. This research problem was a main incentive to add some development to the theory of association rules. The new form of quantitative and multi-dimensional association rules, unlike other approaches, does not require the discretization of real value attributes as a preprocessing step. They are discovered with data driven algorithm that gives precise and complete results and has polynomial complexity for a given dimensionality.
-
Near fields of elliptic dielectric lenses
Abstract
The focusing properties of an elliptic dielectric cylinder taken as a 2D model of dielectric lens are studied for the plane wave illumination. An algorithm based on the concept of analytical regularization is applied for the numerical solution of the corresponding wave scattering problem. Numerical results for the near-field patterns are presented.
-
A solution for increasing data rate of Doppler-RAKE system
Abstract
Doppler-RAKE detection in the CDMA system has been further developed and offers better performances in comparison to conventional RAKE detection, especially in fast-fading environments. Also, the multi-user Doppler-RAKE system works more effectively with channel coding applications. However, by means of exploring the Doppler effect, the system`s data rate is decreased. We propose a simple solution to increase the data rate for the system while keeping the Doppler gain.
