15055893
On the convergence of a class of estimation of distribution algorithms
We investigate the global convergence of estimation of distribution algorithms (EDAs). In EDAs, the distribution is estimated from a set of selected elements, i.e., the parent set, and then the estimated distribution model is used to generate new elements. In this paper, we prove that: 1) if the distribution of the new elements matches that of the parent set exactly, the algorithms will converge to the global optimum under three widely used selection schemes and 2) a factorized distribution algorithm converges globally under proportional selection.
7426259
Modelling the Population Distribution in Multi-objective Optimization by Generative Topographic Mapping
Under mild conditions, the Pareto set of a continuous multi-objective optimization problem exhibits certain regularity. We have recently advocated taking into consideration such regularity in designing multi-objective evolutionary algorithms. Following our previous work on using Local Principal Component Analysis for capturing the regularity, this paper presents a new approach for acquiring and using the regularity of the Pareto set in evolutionary algorithms. The approach is based on the Generative Topographic Mapping and can be regarded as an Estimation of Distribution Algorithm. It builds models of the distribution of promising solutions based on regularity patterns extracted from the previous search, and samples new solutions from the models thus built. The proposed algorithm has been compared with two other state-of-the-art algorithms, NSGA-II and SPEA2 on a set of test problems.
16148368
A model-based evolutionary algorithm for bi-objective optimization
The Pareto optimal solutions to a multi-objective optimization problem often distribute very regularly in both the decision space and the objective space. Most existing evolutionary algorithms do not explicitly take advantage of such a regularity. This paper proposed a model-based evolutionary algorithm (M-MOEA) for bi-objective optimization problems. Inspired by the ideas from estimation of distribution algorithms, M-MOEA uses a probability model to capture the regularity of the distribution of the Pareto optimal solutions. The local principal component analysis (local PCA) and the least-squares method are employed for building the model. New solutions are sampled from the model thus built. At alternate generations, M-MOEA uses crossover and mutation to produce new solutions. The selection in M-MOEA is the same as in non-dominated sorting genetic algorithm-II (NSGA-II). Therefore, MOEA can be regarded as a combination of EDA and NSGA-II. The preliminary experimental results show that M-MOEA performs better than NSGA-II.
1722915
A Hybrid Estimation of Distribution Algorithm for CDMA Cellular System Design
While code division multiple access (CDMA) is becoming a promising cellular communication system, the design for a CDMA cellular system configuration has posed a practical challenge in optimisation. The study in this paper proposes a hybrid estimation of distribution algorithm (HyEDA) to optimize the design of a cellular system configuration. HyEDA is a two-stage hybrid approach built on estimation of distribution algorithms (EDAs), coupled with a K-means clustering method and a simple local search algorithm. Compared with the simulated annealing method on some test instances, HyEDA has demonstrated its superiority in terms of both the overall performance in optimisation and the number of fitness evaluations required.
16216432
A Multiobjective Differential Evolution Based on Decomposition for Multiobjective Optimization with Variable Linkages
Although a number of multiobjective evolutionary algorithms have been proposed over the last two decades, not much effort has been made to deal with variable linkages in multiobjective optimization. Recently, we have suggested a general framework of multiobjective evolutionary algorithms based on decomposition (MOEA/D) [1]. MOEA/D decomposes a MOP into a number of scalar optimization subproblems by a conventional decomposition method. The optimal solution to each of these problems is a Pareto optimal solution to the MOP under consideration. An appropriate decomposition could make these individual Pareto solutions evenly distribute along the Pareto optimal front. MOEA/D aims at solving these scalar optimization subproblems simultaneously. In this paper, we propose, under the framework of MOEA/D, a multiobjective differential evolution based decomposition (MODE/D) for tackling variable linkages. Our experimental results show that MODE/D outperforms several other MOEAs on several test problems with variable linkages.
29533358
On the discrete-time dynamics of a PCA learning algorithm
Abstract We propose a principal component analysis algorithm based on our previous work and analyze its deterministic discrete-time (DDT) system. We prove that its DDT system is always bounded for the small constant learning gain and can almost always deliver a principal component. The difference between Oja's algorithm and our proposed algorithm cannot be observed from their corresponding deterministic continuous-time systems.
3992721
Error minimization in approximate range aggregates
Histogram techniques have been used in many commercial database management systems to estimate a query result size. Recently, it has been shown that they are very effective to support approximation of query processing especially aggregates. In this paper, we investigate the problem of minimizing average errors of approximate aggregates using histogram techniques. Firstly, we present a novel linear-spline histogram model that is more accurate than the existing models. Secondly, we propose a novel histogram construction technique for minimizing such average errors, which is shown to generate a near optimal histogram. Our experiment results demonstrate that the new histogram construction techniques lead to a great accuracy improvement on the existing techniques.
27094711
An approach to multiple attribute decision making based on fuzzy preference information on alternatives
This paper investigates the multiple attribute decision making problem with preference information on alternatives, in which multiple decision makers give their preference information in three forms, i.e., preference orderings, utility values and fuzzy preference relation. A new approach is presented to make use of both the decision makers' social fuzzy preference relation on alternatives and decision matrix to form an optimization model. The optimization model can be used to determine the attribute weights and rank the alternatives. The approach provides a new way to reflect the decision makers' social preference information and the decision matrix. Finally, an example is used to illustrate the proposed approach.
14103418
Front Tracking: A Parallelized Approach for Internal Boundaries and Interfaces
Internal boundaries and interfaces are an important part of many fluid and solid modeling problems. Front Tracking contains a general interface framework, closely related to the non-manifold geometry used in CAD solid modeling packages, to support numerical simulation of such fluid problems. It can thus be considered to be a systematic application of the ideas of computational geometry to computational fluid dynamics. It is based on the principle that finite differences behave best when applied to differentiable functions, and that weak derivatives of nondifferentiable functions can be replaced by regularized expressions such as jump conditions. Front Tracking offers superior resolution for fluid problems with important discontinuities and interfaces, and in some cases, it has provided the unique method to obtain correct answers. Here we present Computer Science issues which have contributed to the success of Front Tracking: software design and organization — modularity, data structures and data hiding.
35872608
On the Performance Analysis of Network-Coded Cooperation in Wireless Networks
Cooperative communication is a powerful technology combating fading in wireless medium. In contrast to conventional cooperation (CC) which allows the relay to simply process and forward what it has heard, network-coded cooperation (NCC) endows network coding capability with the relay, i.e., allows the relay to first encode the data it has received from different sources and then forward the network-coded data to corresponding destinations. In this paper we systematically investigate the performance of NCC in terms of diversity-multiplexing tradeoff as well as exact system outage behavior. Under the assumption (denoted as A) that each destination can reliably overhear the data from other sources, we prove the diversity-multiplexing tradeoff of NCC outperforms that of CC. Moreover, we derive the close form of the system outage probability of NCC as a function of signal-to-noise ratio (SNR). The analytical and numerical results show that by requiring less bandwidth cost, NCC offers a similar or even reduced system outage probability compared with CC, and achieves the same full diversity order as CC at high SNR. Finally we discuss the performance of NCC in case the assumption A is removed. For a wireless network composed of N s-d pairs and a single relay, although there is a certain system outage probability increase for NCC, it still provides the same full diversity order of 2 as CC at high SNR, and has a diversity-multiplexing tradeoff superior to CC.
18316669
On Linear-Spline Based Histograms
Approximation is a very effective paradigm to speed up query processing in large databases. One popular approximation mechanism is data size reduction. There are three reduction techniques: sampling, histograms, and wavelets. Histogram techniques are supported by many commercial database systems, and have been shown very effective for approximately processing aggregation queries. In this paper, we will investigate the optimal models for building histograms based on linear spline techniques. We will firstly propose several novel models. Secondly, we will present efficient algorithms to achieve these proposed optimal models. Our experiment results showed that our new techniques can greatly improve the approximation accuracy comparing to the existing techniques.