The past few years have seen several variants of Evolutionary Algorithms (EAs) applied to solving Sudoku puzzles. Given that EAs with simple components do not work properly, considerable efforts have gone into designing ad-hoc evolutionary operators that profit from a knowledge of the problem. In this paper, we show that one of the main reasons for the improper behavior of EAs when dealing with difficult Sudoku puzzles is the appearance of premature convergence. Memetic algorithms with readily available genetic operators can be used to solve the hardest known Sudoku puzzles when general and well-known methods for avoiding premature convergence are incorporated. Among the approaches tested, a recently proposed method that is based on adopting multi-objective concepts for the solution of single-objective problems has shown remarkable performance. To our knowledge, the methods presented in this paper are the first EAs capable of solving the three Sudoku puzzles that are regarded as the most difficult ones known to date.

The Traveling Salesman Problem (TSP) is one of the most well-known NP-hard combinatorial optimization problems. In order to deal with large TSP instances, several heuristics and metaheuristics have been devised. In this paper, a novel memetic scheme that incorporates a new diversity-based replacement strategy is proposed and applied to the largest instances of the TSPLIB benchmark. The novelty of our method is that it combines the idea of transforming a single-objective problem into a multi-objective one, by considering diversity as an explicit objective, with the idea of adapting the balance induced between exploration and exploitation to the various optimization stages. In addition, the intensification capabilities of the individual learning method incorporated in the memetic scheme are also adapted by taking into account the stopping criterion. Computational results show the clear superiority of our scheme when compared against state-of-the-art schemes. To our knowledge, our proposal is the first evolutionary scheme that readily solves an instance with more than 30,000 cities to optimality.

Comparing the performance of different evolutive Multi-Objective algorithms is an open problem. With time, many performance measures have been proposed. Unfortunately, the evaluations of many of these performance measures disagree with the common sense of when a non-dominated set is better than another. In this work we present a benchmark that is helpful to check if a performance measure actually has a good behavior. Some of the most popular performance measures in literature are tested. The results are valuable for a better understanding of what performance measures are better.

In an Estimation of Distribution Algorithm (EDA) with an infinite sized population the selection distribution equals the search distribution. For a finite sized population these distributions are different. In practical EDAs the goal of the search distribution learning algorithm is to approximate the selection distribution. The source data is the selected set, which is derived from the population by applying a selection operator. The new approach described here eliminates the explicit use of the selection operator and the selected set. We rewrite for a finite population the selection distribution equations of four selection operators. The new equation is called the empirical selection distribution. Then we show how to build the search distribution that gives the best approximation to the empirical selection distribution. Our approach gives place to practical EDAs which can be easily and directly implemented from well established theoretical results. This paper also shows how common EDAs with discrete and real variables are adapted to take advantage of the empirical selection distribution. A comparison and discussion of performance is presented.

An open problem in multiobjective optimization using the Pareto optimality criteria, is how to evaluate the performance of different evolutionary algorithms that solve multi-objective problems. As the output of these algorithms is a non-dominated set (NS), this problem can be reduced to evaluate what NS is better than the others based on their projection on the objective space. In this work we propose a new performance measure for the evaluation of non-dominated sets, that ranks a set of NSs based on their convergence and dispersion. Its evaluations of the NSs agree with intuition. Also, we introduce a benchmark of test cases to evaluate performance measures, that considers several topologies of the Pareto Front.

There are several studies on the desirable properties that a performance measure for evolutionary multiobjective algorithms must have. One of these properties is called "compatibility and completeness". There is a theorem that proves that in the general case, it is not possible to create a unary comparison method with the property mentioned before. Many important conclusions have been derived from this theorem, so its correctness is fundamental for future research. In this work we demonstrate that under practical conditions, the theorem mentioned before does not hold.

This paper presents a theoretical definition for designing EDAs called Elitist Convergent Estimation of Distribution Algorithm (ECEDA), and a practical implementation: the Boltzmann Univariate Marginal Distribution Algorithm (BUMDA). This proposal computes a Gaussian model which approximates a Boltzmann distribution via the minimization of the Kullback Leibler divergence. The resulting approach needs only one parameter: the population size. A set of problems is presented to show advantages and comparative performance of this approach with state of the art continuous EDAs.

We introduce the PESO+ algorithm (Particle Evolutionary Swarm Optimization Plus) for the solution of single objective constrained optimization problems. A novel feature introduced by PESO+ is an external archive to store and retrieve "tolerant" particles found at past tolerance values. This technique is aimed to preserve particles that otherwise would be lost after the adjustment of the tolerance of equality constraints. Also, two perturbation operators, "c-perturbation" and "m-perturbation" are described. The goal of these operators is to keep diversity and to prevent premature convergence. The constraint handling technique is based on feasibility and summation of constraint violations. All experimental results are reported as required by the organizers of the special session on "Constrained Real Parameter Optimization" at CEC2006.

A new approach based on Estimation Distribution Algorithms for constrained multiobjective shape optimization is proposed in this article. Pareto dominance and feasibility rules are used to handle constraints. The algorithm uses feasible and infeasible individuals to estimate the probability distribution of evolving designs. Additionally, correlation among problem design variables is used to improve exploration. The design objectives are: minimum weight and minimum nodal displacement. Also, the resulting structures must fulfill three design constraints: a) maximum permissible Von Misses stress, b)connectedness of the structure elements, and c) small holes are not allowed in the structure. The finite element method is used to evaluate the objective functions and stress constraint.

In this paper, we introduce PASSSS (PAS/sup 4/), the Pareto archived and dominance selection with shrinkable search space evolutionary computation algorithm. The main contribution of this paper is a diversity control mechanism embedded into the selection operator of an evolutionary algorithm that can be used (with little or no modification) to solve both single-objective and multi-objective optimization problems. We present a detailed description of the PAS/sup 4/ algorithm, and illustrate its capabilities by solving several engineering design problems and some test functions from a well-known benchmark in evolutionary optimization. Additionally, PAS/sup 4/ is also used to solve continuous and discrete multiobjective engineering optimization problems.

We introduce inverted and shrinkable Pareto archived evolutionary strategies, IS-PAES. This is an evolutionary algorithm for multiple objective optimization with constraint handling. IS-PAES inherits from PAES the use of an adaptable grid to keep diversity, but here this grid can grow and shrink dynamically until the constraints are met. We propose a novel approach to select a mixture of promising individuals. Several examples of the literature are used to show the potential of ISPAES.

Parametric image segmentation consists of finding a label field that defines a partition of an image into a set of nonoverlapping regions and the parameters of the models that describe the variation of some property within each region. A new Bayesian formulation for the solution of this problem is presented, based on the key idea of using a doubly stochastic prior model for the label field, which allows one to find exact optimal estimators for both this field and the model parameters by the minimization of a differentiable function. An efficient minimization algorithm and comparisons with existing methods on synthetic images are presented, as well as examples of realistic applications to the segmentation of Magnetic Resonance volumes and to motion segmentation.

A new Bayesian formulation for the image segmentation problem is presented. It is based on the key idea of using a doubly stochastic prior model for the label field, which allows one to find exact optimal estimators by the minimization of a differentiable function. Comparisons with existing methods on synthetic images are presented, as well as realistic applications to the segmentation of magnetic resonance volumes, to motion segmentation, and to edge-preserving filtering.

Automatic three-dimensional (3-D) segmentation of the brain from magnetic resonance (MR) scans is a challenging problem that has received an enormous amount of attention lately. Of the techniques reported in the literature, very few are fully automatic. In this paper, we present an efficient and accurate, fully automatic 3-D segmentation procedure for brain MR scans. It has several salient features; namely, the following. 1) Instead of a single multiplicative bias field that affects all tissue intensities, separate parametric smooth models are used for the intensity of each class. 2) A brain atlas is used in conjunction with a robust registration procedure to find a nonrigid transformation that maps the standard brain to the specimen to be segmented. This transformation is then used to: segment the brain from nonbrain tissue; compute prior probabilities for each class at each voxel location and find an appropriate automatic initialization. 3) Finally, a novel algorithm is presented which is a variant of the expectation-maximization procedure, that incorporates a fast and accurate way to find optimal segmentations, given the intensity models along with the spatial coherence assumption. Experimental results with both synthetic and real data are included, as well as comparisons of the performance of our algorithm with that of other published methods.

We present a new algorithm for the efficient estimation of piecewise parametric models for image segmentation. This algorithm permits the simultaneous estimation of: the number of models; the parameters for each model and the regions where each model is applicable. It is based on Bayesian estimation theory, and is theoretically justified by the use of a specific cost function that decreases at every iteration and by a new model for the posterior marginal distributions which is amenable to the use of fast computational methods.