Benchmarking provides an essential ground base for adequately assessing and comparing evolutionary computation methods and other optimization algorithms. It allows us to gain insights into strengths and weaknesses of different existing techniques, and consequently design more efficient optimization approaches. The need for good benchmarking practices opens up a broad range of complementary research questions, arising as a byproduct of challenges encountered when optimization methods are assessed. From the selection of representative benchmark problem instances, different algorithms, and suitable performance metrics, over efficient experimentation, to a sound evaluation of the benchmark data, these research questions lie at the core of establishing a well-designed and standardized benchmarking procedure.

The particle swarm optimization (PSO) algorithm has been the object of many studies and modifications for more than 25 years. Ranging from small refinements to the incorporation of sophisticated novel ideas, the majority of modifications proposed to this algorithm have been the result of a manual process in which developers try new designs based on their own knowledge and expertise. However, manually introducing changes is very time consuming and makes the systematic exploration of all the possible algorithm configurations a difficult process. In this article, we propose to use automatic design to overcome the limitations of having to manually find performing PSO algorithms. We develop a flexible software framework for PSO, called PSO-X, which is specifically designed to integrate the use of automatic configuration tools into the process of generating PSO algorithms. Our framework embodies a large number of algorithm components developed over more than 25 years of research that have allowed PSO to deal with a large variety of problems, and usesirace, a state-of-the-art configuration tool, to automatize the task of selecting and configuring PSO algorithms starting from these components. We show thatiraceis capable of finding high-performing instances of PSO algorithms never proposed before.

The performance assessment of multi-objective heuristic algorithms is one of the most significant contributions from the evolutionary optimization algorithms community. By contrast, performance assessment in the context of many-objective optimization is still a challenging, open research field. Recent advances have demonstrated disagreements between Pareto-compliant performance metrics, and indicated that reference fronts produced by benchmark generators of Pareto-optimal fronts could be further improved. In this work, we investigate these reference fronts with the help of multi-dimensional visualization techniques and Pareto-monotonic archivers. Interestingly, reference fronts produced by benchmark generators for DTLZ and WFG continuous optimization problems show significant issues, even when only three objectives are considered. Furthermore, given that input solution sets for five-objective problems are not high-quality, archivers are unable to output reasonable approximation fronts. We conclude that the performance assessment of EMO algorithms needs to urgently address reference front generation.

A recent comparison of well-established multiobjective evolutionary algorithms (MOEAs) has helped better identify the current state-of-the-art by considering (i) parameter tuning through automatic configuration, (ii) a wide range of different setups, and (iii) various performance metrics. Here, we automatically devise MOEAs with verified state-of-the-art performance for multi- and many-objective continuous optimization. Our work is based on two main considerations. The first is that high-performing algorithms can be obtained from a configurable algorithmic framework in an automated way. The second is that multiple performance metrics may be required to guide this automatic design process. In the first part of this work, we extend our previously proposed algorithmic framework, increasing the number of MOEAs, underlying evolutionary algorithms, and search paradigms that it comprises. These components can be combined following a general MOEA template, and an automatic configuration method is used to instantiate high-performing MOEA designs that optimize a given performance metric and present state-of-the-art performance. In the second part, we propose a multiobjective formulation for the automatic MOEA design, which proves critical for the context of many-objective optimization due to the disagreement of established performance metrics. Our proposed formulation leads to an automatically designed MOEA that presents state-of-the-art performance according to a set of metrics, rather than a single one.

Early works on external solution archiving have pointed out the benefits of unbounded archivers and there have been great advances, theoretical and algorithmic, in bounded archiving methods. Moreover, recent work has shown that the populations of most multi- and many-objective evolutionary algorithms (MOEAs) lack the properties that one would desire when trying to find a bounded Pareto-optimal front. Despite all these results, many recent MOEAs are still being proposed, analyzed and compared without considering any kind of archiver assuming their additional computational cost is not justified. In this paper, we investigate the effect of using various kinds of archivers, improving over previous studies in several aspects: (i) the parameters of MOEAs with and without an external archiver are tuned separately using automatic configuration methods; (ii) we consider a comprehensive range of problem scenarios (number of objectives, function evaluations, computation time limit); (iii) we employ multiple, complementary quality metrics; and (iv) we study the effect of unbounded archivers and two state-of-the-art bounded archiving methods. Our results show that both unbounded and bounded archivers are beneficial even for many-objective problems. We conclude that future proposals and comparisons of MOEAs must include archiving as an algorithmic component.

Research on multi-objective evolutionary algorithms (MOEAs) has produced over the past decades a large number of algorithms and a rich literature on performance assessment tools to evaluate and compare them. Yet, newly proposed MOEAs are typically compared against very few, often a decade older MOEAs. One reason for this apparent contradiction is the lack of a common baseline for comparison, with each subsequent study often devising its own experimental scenario, slightly different from other studies. As a result, the state of the art in MOEAs is a disputed topic. This article reports a systematic, comprehensive evaluation of a large number of MOEAs that covers a wide range of experimental scenarios. A novelty of this study is the separation between the higher-level algorithmic components related to multi-objective optimization (MO), which characterize each particular MOEA, and the underlying parameters-such as evolutionary operators, population size, etc.-whose configuration may be tuned for each scenario. Instead of relying on a common or "default" parameter configuration that may be low-performing for particular MOEAs or scenarios and unintentionally biased, we tune the parameters of each MOEA for each scenario using automatic algorithm configuration methods. Our results confirm some of the assumed knowledge in the field, while at the same time they provide new insights on the relative performance of MOEAs for many-objective problems. For example, under certain conditions, indicator-based MOEAs are more competitive for such problems than previously assumed. We also analyze problem-specific features affecting performance, the agreement between performance metrics, and the improvement of tuned configurations over the default configurations used in the literature. Finally, the data produced is made publicly available to motivate further analysis and a baseline for future comparisons.

In this paper, we present results on the automatic tuning of an adaptive traffic light controller. The traffic light controller is inspired by some swarm intelligence techniques and uses numerical values that are adapted by the principles of stigmergy to estimate queue lengths. These estimates are used in a probabilistic mechanism that switches between traffic light control strategies and determines phase lengths. This traffic light controller adapts through this specific mechanism to the current traffic situation but to define its behavior more than 100 parameters are used. To determine appropriate parameter settings, we therefore explored the automatic configuration of this traffic light controller. The main focus in this article is to examine whether the controller parameters require adaptation to major time-varying changes to reach best possible performance. We propose a strategy to deal with such changes and experimentally evaluate the impact limited re-tunings have on the controller performance.

The Success History-based Adaptive Differential Evolution algorithm with Linear Population Size Reduction (L-SHADE) is a highly competitive continuous optimizer. In this paper, we extend L-SHADE towards handling mixed variable optimization problems, where some of the variables may be categorical, ordinal, integer or continuous. For handling the discrete variables, we consider three different options. The first is to adapt the mechanism for handling categorical variables introduced in an earlier proposed ant colony optimization algorithm, called ACOMVto use it with L-SHADE (L-SHADEMV). The second is to apply a simpler scheme that relies on the mechanisms how ant colony optimization algorithms traditionally tackle discrete problems (L-SHADEACO). The third is to introduce a mechanism that exploits the ideas of DE within the generation of new values for the categorical variables, by introducing specific rules to be applied in the mutation (L-SHADERULE). We use an automatic algorithm configuration tool for optimizing the algorithms' parameters to allow an unbiased comparison of the three schemes. The performance of the proposed algorithms was evaluated on artificial mixed-variable optimization problems and compared with L-SHADE that incorporates a simple rounding scheme to handle categorical variables, which is used as a baseline method. The experimental results show that all three categorical handling methods outperform the baseline and L-SHADEACOis the best performing scheme in terms of accuracy and robustness.

The population-based ant colony optimization algorithm (P-ACO) differs from other ACO algorithms because of its implementation of the pheromone update. P-ACO keeps track of a population of solutions, which serves as an archive of solutions generated by the ants' colony. Pheromone updates in P-ACO are only done based on solutions that enter or leave the solution archive. The population-based scheme reduces considerably the computation time needed for the pheromone update when compared to classical ACO algorithms such as Ant System. In this work, we study the behavior of P-ACO when solving the traveling salesman and the quadratic assignment problem. In particular, we investigate the impact of a local search on P-ACO parameters and performance. The results show that P-ACO reaches competitive performance but that the parameter settings and algorithm behavior are strongly problem-dependent.

Over the recent years, several tools for the automated configuration of parameterized algorithms have been developed. These tools, also called configurators, have themselves parameters that influence their search behavior and make them malleable to different kinds of configuration tasks. The default values of these parameters are set manually based on the experience of the configurator's developers. Studying the impact of these parameters or configuring them is very expensive as it would require many executions of these tools on configuration tasks, each taking often many hours or days of computation. In this work, we tackle this problem using a meta-tuning process, based on the use of surrogate benchmarks that are much faster to evaluate. This paper studies the feasibility of this process using the popular irace configurator as the method to be meta-configured. We first study the consistency between the real and surrogate benchmarks using three measures: the prediction accuracy of the surrogate models, the homogeneity of the benchmarks and the list of important algorithm parameters. Afterwards, we use irace to configure irace on those surrogates. Experimental results indicate the feasibility of this process and a clear potential improvement of irace over its default configuration.

This paper presents a new variant of the Artificial Bee Colony (ABC) algorithm, which is called “Self-adaptive Search Equation-based Artificial Bee Colony” (SSEABC) algorithm. SSEABC integrates three strategies into the canonical ABC algorithm. The first strategy is a self-adaptive strategy that determines appropriate search equations for a given problem instance by discarding dominated ones from a pool comprising a large number of randomly generated search equations. The second is an incremental population size strategy, which is based on adding new food sources located around the best-so-far food source position after a predefined number of iterations. This helps to increase convergence speed. The third strategy is competitive local search selection; it decides on which is the most effective local search procedure by comparing the performance of Mtsls1 and IPOP-CMA-ES in a competition phase and applying the winner local search to the best food source position for the rest of the iterations. The SSEABC algorithm is tested on the CEC 2014 numerical optimization problems and very competitive results are obtained.

Multiobjective evolutionary algorithms (MOEAs) are typically proposed, studied, and applied as monolithic blocks with a few numerical parameters that need to be set. Few works have studied how the algorithmic components of these evolutionary algorithms can be classified and combined to produce new algorithmic designs. The motivation for studies of this latter type stem from the development of flexible software frameworks and the usage of automatic algorithm configuration methods to find novel algorithm designs. In this paper, we propose an MOEA template and a new conceptual view of its components that surpasses existing frameworks in both number of algorithms that can be instantiated from the template and flexibility to produce novel algorithmic designs. We empirically demonstrate the flexibility of our proposed framework by automatically designing MOEAs for continuous and combinatorial optimization problems. The automatically designed algorithms are often able to outperform six traditional MOEAs from the literature, even after tuning their numerical parameters.

In this paper, we apply a generalized artificial bee colony (ABC-X) algorithm to the learning-based real-parameter optimization competition at the 2015 Congress on Evolutionary Computation. The main idea underlying the ABC-X algorithm is to provide a flexible, freely configurable framework for artificial bee colony (ABC) algorithms. From this framework, one can not only instantiate known ABC algorithms but also configure new, previously unseen ABC algorithms that may perform even better than known ABC algorithms. One key advantage of a configurable algorithm framework is that it is adaptable to many different specific problems without requiring necessarily an algorithm re-design. This is relevant if in the application problem repeatedly instances of the problem need to be solved regularly. This situation arises in many practical settings e.g. in power control or other application areas: Routinely a sequence of specific instances of a more general continuous optimization problem arise and these instances have to be solved repeatedly (possibly for an infinite horizon) in the future: in this case the instances of the problem in the sequence will share similarities as they arise from a same source. This is also the situation that is targeted by the learning-based real-parameter optimization competition and which we have also described in our own earlier research.

We present a thorough empirical investigation of the scaling behaviour of state-of-the-art local search algorithms for the TSP; in particular, we study the scaling of running time required for finding optimal solutions to Euclidean TSP instances. We use a recently introduced bootstrapping approach to assess the statistical significance of the scaling models thus obtained and contrast these models with those recently reported for the Concorde algorithm. In particular, we answer the question whether the scaling behaviour of state-of-the-art local search algorithms for the TSP differs by more than a constant from that required by Concorde to find the first optimal solution to a given TSP instance.

The benchmark functions and some of the algorithms proposed for the special session on real parameter optimization of the 2005 IEEE Congress on Evolutionary Computation (CEC'05) have played and still play an important role in the assessment of the state of the art in continuous optimization. In this article, we show that if bound constraints are not enforced for the final reported solutions, state-of-the-art algorithms produce infeasible best candidate solutions for the majority of functions of the IEEE CEC'05 benchmark function suite. This occurs even though the optima of the CEC'05 functions are within the specified bounds. This phenomenon has important implications on algorithm comparisons, and therefore on algorithm designs. This article's goal is to draw the attention of the community to the fact that some authors might have drawn wrong conclusions from experiments using the CEC'05 problems.

In this paper, we introduce ACOMV: an ant colony optimization (ACO) algorithm that extends the ACORalgorithm for continuous optimization to tackle mixed-variable optimization problems. In ACOMV, the decision variables of an optimization problem can be explicitly declared as continuous, ordinal, or categorical, which allows the algorithm to treat them adequately. ACOMVincludes three solution generation mechanisms: a continuous optimization mechanism (ACOR), a continuous relaxation mechanism (ACOMV-o) for ordinal variables, and a categorical optimization mechanism (ACOMV-c) for categorical variables. Together, these mechanisms allow ACOMVto tackle mixed-variable optimization problems. We also define a novel procedure to generate artificial, mixed-variable benchmark functions, and we use it to automatically tune ACOMV's parameters. The tuned ACOMVis tested on various real-world continuous and mixed-variable engineering optimization problems. Comparisons with results from the literature demonstrate the effectiveness and robustness of ACOMVon mixed-variable optimization problems.

In this article, we benchmark a new hybrid algorithm for continuous optimization on the 28 functions for the CEC 2013 special session and competition on real-parameter optimization. Our algorithm makes a loose coupling of (i) IPOP-CMA-ES, an advanced evolution strategy with covariance matrix adaptation integrated with an occasional restart strategy and increasing population size, and (ii) an iterated local search (ILS) algorithm that repeatedly applies a different local search from CMA-ES to perturbations of previous high-quality solutions. The central idea of the hybrid algorithm is to let IPOP-CMA-ES and ILS compete in an initial competition phase and then the winner of the two algorithms is deployed for the remainder of the computation time. A cooperative element between the two algorithms is implemented through a solution exchange from IPOP-CMA-ES to ILS. Hence, one may classify this algorithm as a loosely coupled cooperative-competitive algorithm for continuous optimization. We compare the computational results of this hybrid algorithm to the default version and a tuned version of IPOP-CMA-ES to illustrate the improvement that is obtained through this hybrid algorithm. This comparison is interesting since IPOP-CMA-ES is a state-of-the-art algorithm which somehow has become a standard benchmark to compare against for any new algorithmic proposals for continuous optimization. Our computational results show that the proposed hybrid algorithm performs significantly better than the default and tuned IPOP-CMA-ES variants on the problems of dimension 30 and 50. Thus, these results also indicate that the hybrid algorithm reaches very high performance on the CEC 2013 benchmark set.

Image registration is a fundamental step in combining information from multiple images in medical imaging, computer vision and image processing. In this paper, we configure a recent evolutionary algorithm for medical image registration, r-GA, with an offline automatic parameter tuning technique. In addition, we demonstrate the use of automatic tuning to compare different registration algorithms, since it allows to consider results that are not affected by the ability and efforts invested by the designers in configuring the different algorithms, a crucial task that strongly impacts their performance. Our experimental study is carried out on a large dataset of brain MRI, on which we compare the performance of r-GA with four classic IR techniques. Our results show that all algorithms benefit from the automatic tuning process and indicate that r-GA performs significantly better than the competitors.

Automated algorithm configuration methods have proven to be instrumental in deriving high-performing algorithms and such methods are increasingly often used to configure evolutionary algorithms. One major challenge in devising automatic algorithm configuration techniques is to handle the inherent stochasticity in the configuration problems. This article analyses a post-selection mechanism that can also be used for this task. The central idea of the post-selection mechanism is to generate in a first phase a set of high-quality candidate algorithm configurations and then to select in a second phase from this candidate set the (statistically) best configuration. Our analysis of this mechanism indicates its high potential and suggests that it may be helpful to improve automatic algorithm configuration methods.

Reverse engineering is the problem of inferring the structure of a network of interactions between biological variables from a set of observations. In this paper, we propose an optimization algorithm, called MORE, for the reverse engineering of biological networks from time series data. The model inferred by MORE is a sparse system of nonlinear differential equations, complex enough to realistically describe the dynamics of a biological system. MORE tackles separately the discrete component of the problem, the determination of the biological network topology, and the continuous component of the problem, the strength of the interactions. This approach allows us both to enforce system sparsity, by globally constraining the number of edges, and to integrate a priori information about the structure of the underlying interaction network. Experimental results on simulated and real-world networks show that the mixed discrete/continuous optimization approach of MORE significantly outperforms standard continuous optimization and that MORE is competitive with the state of the art in terms of accuracy of the inferred networks.

Multiobjective optimization problems are problems with several, typically conflicting, criteria for evaluating solutions. Without any a priori preference information, the Pareto optimality principle establishes a partial order among solutions, and the output of the algorithm becomes a set of nondominated solutions rather than a single one. Various ant colony optimization (ACO) algorithms have been proposed in recent years for solving such problems. These multiobjective ACO (MOACO) algorithms exhibit different design choices for dealing with the particularities of the multiobjective context. This paper proposes a formulation of algorithmic components that suffices to describe most MOACO algorithms proposed so far. This formulation also shows that existing MOACO algorithms often share equivalent design choices, but they are described in different terms. Moreover, this formulation is synthesized into a flexible algorithmic framework, from which not only existing MOACO algorithms may be instantiated, but also combinations of components that were never studied in the literature. In this sense, this paper goes beyond proposing a new MOACO algorithm, but it rather introduces a family of MOACO algorithms. The flexibility of the proposed MOACO framework facilitates the application of automatic algorithm configuration techniques. The experimental results presented in this paper show that the automatically configured MOACO framework outperforms the MOACO algorithms that inspired the framework itself. This paper is also among the first to apply automatic algorithm configuration techniques to multiobjective algorithms.

The usage of preference models in algorithms for multi-objective optimization has recently received an increasing attention by the research community. Motivated by this trend, we experimentally study the impact that the integration of preference models into evolutionary multi-objective search algorithms has on performance. In this article, we consider three preference models, ranging from rather simple to more complex ones; these are (i) reference point, (ii) guided dominance, and (iii) Promethee II. As a benchmark problem we consider multi-objective traveling salesman problem instances of various sizes and with a varying number of objectives.

The automatic configuration of algorithms is a dynamic field of research. Its potential for producing highly performing algorithms may change the way we design algorithms. So far, automatic algorithm configuration tools have almost exclusively been applied to configure single-objective algorithms. In this paper, we investigate the usage of automatic algorithm configuration tools to improve multi-objective algorithms. In fact, this is the first article we are aware of where state-of-the-art multi-objective optimizers are configured in an automatic way. This automatic configuration is done for five variants of multi-objective flow-shop problems. Our experimental results show that we can reach at least the same and often a better final quality than a recently proposed state-of-the-art algorithm for these problems.

Winner of the best paper award in the ant Colony Optimization and swarm intelligence track

The Quadratic Assignment Problem (QAP) is a prominent NP-hard combinatorial optimization problem that arises in many real world applications. Solving the QAP to optimality is a very challenging task, and due to this, the QAP is mostly tackled by Stochastic Local Search (SLS) algorithms. Different SLS algorithms, however, achieve different levels of performance when tackling instances of different type, structure, or size. This holds true also for the QAP, where to date, no single SLS algorithm can be said to be the “best” approach for solving the QAP. Here we study the relationship between the relative performance of SLS algorithms for solving a class of real-life like Quadratic Assignment Problem instances and instance size. Experimental results show that population-based metaheuristic algorithms perform very well for solving this class of instances, compared to single point search approaches, and that their relative performance is relatively stable.

Incremental social learning (ISL) was proposed as a way to improve the scalability of systems composed of multiple learning agents. In this paper, we show that ISL can be very useful to improve the performance of population-based optimization algorithms. Our study focuses on two particle swarm optimization (PSO) algorithms: a) the incremental particle swarm optimizer (IPSO), which is a PSO algorithm with a growing population size in which the initial position of new particles is biased toward the best-so-far solution, and b) the incremental particle swarm optimizer with local search (IPSOLS), in which solutions are further improved through a local search procedure. We first derive analytically the probability density function induced by the proposed initialization rule applied to new particles. Then, we compare the performance of IPSO and IPSOLS on a set of benchmark functions with that of other PSO algorithms (with and without local search) and a random restart local search algorithm. Finally, we measure the benefits of using incremental social learning on PSO algorithms by running IPSO and IPSOLS on problems with different fitness distance correlations.

MAX-MIN Ant System (MMAS) is an ant colony optimization (ACO) algorithm that was originally designed to start with a very explorative search phase and then to make a slow transition to an intensive exploitation of the best solutions found during the search. This design leads to a rather slow initial convergence of the algorithm, and, hence, to poor results if the algorithm does not run for sufficient time. This article illustrates that varying the parameter settings of MMAS while solving an instance may significantly improve the anytime search behavior of MMAS. Even rather simple pre-scheduled variations of the parameter settings that only depend on the number of iterations or the computation time show improvement over fixed parameter settings. The degree of improvement, however, is not uniform across problems. In particular, the improvement is very strong in the traveling salesman problem (TSP) but small, if at all noticeable, in the quadratic assignment problem (QAP). This paper also presents an adaptive parameter variation specifically designed for the TSP. The experimental results show that the pre-scheduled variations are comparable to the proposed adaptive variation in terms of the anytime behavior of MMAS.

Over the last few years, there have been a number of proposals of ant colony optimization (ACO) algorithms for tackling multiobjective combinatorial optimization problems. These proposals adapt ACO concepts in various ways, for example, some use multiple pheromone matrices and multiple heuristic matrices and others use multiple ant colonies.

Particle swarm optimization (PSO) is a swarm intelligence technique originally inspired by models of flocking and of social influence that assumed homogeneous individuals. During its evolution to become a practical optimization tool, some heterogeneous variants have been proposed. However, heterogeneity in PSO algorithms has never been explicitly studied and some of its potential effects have therefore been overlooked. In this paper, we identify some of the most relevant types of heterogeneity that can be ascribed to particle swarms. A number of particle swarms are classified according to the type of heterogeneity they exhibit, which allows us to identify some gaps in current knowledge about heterogeneity in PSO algorithms. Motivated by these observations, we carry out an experimental study of two heterogeneous particle swarms each of which is composed of two kinds of particles. Directions for future developments on heterogeneous particle swarms are outlined.

The identification of performance-optimizing parameter settings is an important part of the development and application of algorithms. We describe an automatic framework for this algorithm configuration problem. More formally, we provide methods for optimizing a target algorithm’s performance on a given class of problem instances by varying a set of ordinal and/or categorical parameters. We review a family of local-search-based algorithm configuration procedures and present novel techniques for accelerating them by adaptively limiting the time spent for evaluating individual configurations. We describe the results of a comprehensive experimental evaluation of our methods, based on the configuration of prominent complete and incomplete algorithms for SAT. We also present what is, to our knowledge, the first published work on automatically configuring the CPLEX mixed integer programming solver. All the algorithms we considered had default parameter settings that were manually identified with considerable effort. Nevertheless, using our automated algorithm configuration procedures, we achieved substantial and consistent performance improvements.

During the last decade, many variants of the original particle swarm optimization (PSO) algorithm have been proposed. In many cases, the difference between two variants can be seen as an algorithmic component being present in one variant but not in the other. In the first part of the paper, we present the results and insights obtained from a detailed empirical study of several PSO variants from a component difference point of view. In the second part of the paper, we propose a new PSO algorithm that combines a number of algorithmic components that showed distinct advantages in the experimental study concerning optimization speed and reliability. We call this composite algorithm Frankenstein's PSO in an analogy to the popular character of Mary Shelley's novel. Frankenstein's PSO performance evaluation shows that by integrating components in novel ways effective optimizers can be designed.

The fully informed particle swarm optimization algorithm (FIPS) is very sensitive to changes in the population topology. The velocity update rule used in FIPS considers all the neighbors of a particle to update its velocity instead of just the best one as it is done in most variants. It has been argued that this rule induces a random behavior of the particle swarm when a fully connected topology is used. This argument could explain the often observed poor performance of the algorithm under that circumstance.

In recent years, much attention has been devoted to the development of metaheuristics and local search algorithms for tackling stochastic combinatorial optimization problems. This paper focuses on local search algorithms; their effectiveness is greatly determined by the evaluation procedure that is used to select the best of several solutions in the presence of uncertainty. In this paper, we propose an effective evaluation procedure that makes use of empirical estimation techniques. We illustrate this approach and we assess its performance on the probabilistic traveling salesman problem. Experimental results on a large set of instances show that the proposed approach can lead to a very fast and highly effective local search algorithm.

SCOPUS: ed.j

We prove some convergence properties for a class of ant colony optimization algorithms. In particular, we prove that for any small constant /spl epsiv/ > 0 and for a sufficiently large number of algorithm iterations t, the probability of finding an optimal solution at least once is P*(t) /spl ges/ 1 - /spl epsiv/ and that this probability tends to 1 for t/spl rarr//spl infin/. We also prove that, after an optimal solution has been found, it takes a finite number of iterations for the pheromone trails associated to the found optimal solution to grow higher than any other pheromone trail and that, for t/spl rarr//spl infin/, any fixed ant will produce the optimal solution during the tth iteration with probability P /spl ges/ 1 /spl epsiv//spl circ/(/spl tau//sub min/, /spl tau//sub max/), where /spl tau//sub min/ and /spl tau//sub max/ are the minimum and maximum values that can be taken by pheromone trails.