A general framework for statistical performance comparison of evolutionary computation algorithms

This paper proposes a statistical methodology for comparing the performance of evolutionary computation algorithms. A twofold sampling scheme for collecting performance data is introduced, and these data are analyzed using bootstrap-based multiple hypothesis testing procedures. The proposed method is sufficiently flexible to allow the researcher to choose how performance is measured, does not rely upon distributional assumptions, and can be extended to analyze many other randomized numeric optimization routines. As a result, this approach offers a convenient, flexible, and reliable technique for comparing algorithms in a wide variety of applications.     

Selection intensity in cellular evolutionary algorithms for regular lattices

In this paper, we present quantitative models for the selection pressure of cellular evolutionary algorithms on regular one- and two-dimensional (2-D) lattices. We derive models based on probabilistic difference equations for synchronous and several asynchronous cell update policies. The models are validated using two customary selection methods: binary tournament and linear ranking. Theoretical results are in agreement with experimental values, showing that the selection intensity can be controlled by using different update methods. It is also seen that the usual logistic approximation breaks down for low-dimensional lattices and should be replaced by a polynomial approximation. The dependence of the models on the neighborhood radius is studied for both topologies. We also derive results for 2-D lattices with variable grid axes ratio.     

How evolutionary algorithms are applied to statistical natural language processing

Statistical natural language processing (NLP) and evolutionary algorithms (EAs) are two very active areas of research which have been combined many times. In general, statistical models applied to deal with NLP tasks require designing specific algorithms to be trained and applied to process new texts. The development of such algorithms may be hard. This makes EAs attractive since they offer a general design, yet providing a high performance in particular conditions of application. In this article, we present a survey of many works which apply EAs to different NLP problems, including syntactic and semantic analysis, grammar induction, summaries and text generation, document clustering and machine translation. This review finishes extracting conclusions about which are the best suited problems or particular aspects within those problems to be solved with an evolutionary algorithm.     

An extension of Geiringer's theorem for a wide class of evolutionary search algorithms

The frequency with which various elements of the search space of a given evolutionary algorithm are sampled is affected by the family of recombination (reproduction) operators. The original Geiringer theorem tells us the limiting frequency of occurrence of a given individual under repeated application of crossover alone for the classical genetic algorithm. Recently, Geiringer's theorem has been generalized to include the case of linear GP with homologous crossover (which can also be thought of as a variable length GA). In the current paper we prove a general theorem which tells us that under rather mild conditions on a given evolutionary algorithm, call it A, the stationary distribution of a certain Markov chain of populations in the absence of selection is unique and uniform. This theorem not only implies the already existing versions of Geiringer's theorem, but also provides a recipe of how to obtain similar facts for a rather wide class of evolutionary algorithms. The techniques which are used to prove this theorem involve a classical fact about random walks on a group and may allow us to compute and/or estimate the eigenvalues of the corresponding Markov transition matrix which is directly related to the rate of convergence towards the unique limiting distribution.     

Cloud-based evolutionary algorithms: An algorithmic study

This paper presents a cloud-computing based evolutionary algorithm using a synchronous storage service as pool for exchange information among population of solutions. The multi-computer was composed of several normal PCs or laptops connected via Wifi or Ethernet. In this work the effect of how the distributed evolutionary algorithm reached the solution when new PCs was added was tested whether that effect also translates to the algorithmic performance of the algorithm. To this end different (and hard) problems was addressed using the proposed multi-computer, analyzing the effects that the automatic load-balancing and synchronization had on the speed of algorithm successful, and analyzing how the number of evaluation per second increases when the multi-computer includes new nodes. The measure used for the analysis was number of evaluation per second which was increased when the multi-computer includes new nodes. The algorithm solved the proposed problems and it was viable to run it in homogeneous or heterogeneous platforms. The experiments includes two problems and different configuration for the distributed evolutionary algorithm in order to check the results of the algorithm for several rates of information exchange with the selected storage service. Results shows that the system is viable with homogeneous or heterogeneous nodes and there is no significative differences for the synchronous storage services we have tested. But when the problem is harder, and the threads of the algorithm does not stop for each information exchange (migration of individual from one population to another one), the differences of using a specific service became significative in terms of success of the algorithm.     

Performance assessment of foraging algorithms vs. evolutionary algorithms

The class of foraging algorithms is a relatively new field based on mimicking the foraging behavior of animals, insects, birds or fish in order to develop efficient optimization algorithms. The artificial bee colony (ABC), the bees algorithm (BA), ant colony optimization (ACO), and bacterial foraging optimization algorithms (BFOA) are examples of this class to name a few. This work provides a complete performance assessment of the four mentioned algorithms in comparison to the widely known differential evolution (DE), genetic algorithms (GAs), harmony search (HS), and particle swarm optimization (PSO) algorithms when applied to the problem of unconstrained nonlinear continuous function optimization. To the best of our knowledge, most of the work conducted so far using foraging algorithms has been tested on classical functions. This work provides the comparison using the well-known CEC05 benchmark functions based on the solution reached, the success rate, and the performance rate.     

A tool for multiobjective evolutionary algorithms

This paper introduces a software tool based on illustrative applications for the development, analysis and application of multiobjective evolutionary algorithms. The multiobjective evolutionary algorithms tool (MOEAT) written in C# using a variety of multiobjective evolutionary algorithms (MOEAs) offers a powerful environment for various kinds of optimization tasks. It has many useful features such as visualizing of the progress and the results of optimization in a dynamic or static mode, and decision variable settings. The performance measurements of well-known multiobjective evolutionary algorithms in MOEAT are done using benchmark problems. In addition, two case studies from engineering domain are presented.     

A study of drift analysis for estimating computation time of evolutionary algorithms

This paper introduces drift analysis and its applications in estimating average computation time of evolutionary algorithms. Firstly, drift conditions for estimating upper and lower bounds of the mean first hitting times of evolutionary algorithms are presented. Then drift analysis is applied to two specific evolutionary algorithms and problems. Finally, a general classification of easy and hard problems for evolutionary algorithmsis given based on the analysis.     

Seeding the initial population of multi-objective evolutionary algorithms: A computational study

Most experimental studies initialize the population of evolutionary algorithms with random genotypes. In practice, however, optimizers are typically seeded with good candidate solutions either previously known or created according to some problem-specific method. This seeding has been studied extensively for single-objective problems. For multi-objective problems, however, very little literature is available on the approaches to seeding and their individual benefits and disadvantages. In this article, we are trying to narrow this gap via a comprehensive computational study on common real-valued test functions. We investigate the effect of two seeding techniques for five algorithms on 48 optimization problems with 2, 3, 4, 6, and 8 objectives. We observe that some functions (e.g., DTLZ4 and the LZ family) benefit significantly from seeding, while others (e.g., WFG) profit less. The advantage of seeding also depends on the examined algorithm.     

A case study on using evolutionary algorithms to optimize bakery production planning

The production of bakery goods is strictly time sensitive due to the complex biochemical processes during dough fermentation, which leads to special requirements for production planning and scheduling. Instead of mathematical methods scheduling is often completely based on the practical experience of the responsible employees in bakeries. This sometimes inconsiderate scheduling approach often leads to sub-optimal performance of companies. This paper presents the modeling of the production in bakeries as a kind of no-wait hybrid flow-shop following the definitions in Scheduling Theory, concerning the constraints and frame conditions given by the employed processes properties. Particle Swarm Optimization and Ant Colony Optimization, two widely used evolutionary algorithms for solving scheduling problems, were adapted and used to analyse and optimize the production planning of an example bakery. In combination with the created model both algorithms proved capable to provide optimized results for the scheduling operation within a predefined runtime of 15 min.     

A comparative study of many-objective evolutionary algorithms for the discovery of software architectures

During the design of complex systems, software architects have to deal with a tangle of abstract artefacts, measures and ideas to discover the most fitting underlying architecture. A common way to structure such complex systems is in terms of their interacting software components, whose composition and connections need to be properly adjusted. Along with the expected functionality, non-functional requirements are key at this stage to guide the many design alternatives to be evaluated by software architects. The appearance of Search Based Software Engineering (SBSE) brings an approach that supports the software engineer along the design process. Evolutionary algorithms can be applied to deal with the abstract and highly combinatorial optimisation problem of architecture discovery from a multiple objective perspective. The definition and resolution of many-objective optimisation problems is currently becoming an emerging challenge in SBSE, where the application of sophisticated techniques within the evolutionary computation field needs to be considered. In this paper, diverse non-functional requirements are selected to guide the evolutionary search, leading to the definition of several optimisation problems with up to 9 metrics concerning the architectural maintainability. An empirical study of the behaviour of 8 multi- and many-objective evolutionary algorithms is presented, where the quality and type of the returned solutions are analysed and discussed from the perspective of both the evolutionary performance and those aspects of interest to the expert. Results show how some many-objective evolutionary algorithms provide useful mechanisms to effectively explore design alternatives on highly dimensional objective spaces.     

Design of graph-based evolutionary algorithms: a case study for chemical process networks

This paper describes the adaptation of evolutionary algorithms (EAs) to the structural optimization of chemical engineering plants, using rigorous process simulation combined with realistic costing procedures to calculate target function values. To represent chemical engineering plants, a network representation with typed vertices and variable structure will be introduced. For this representation, we introduce a technique on how to create problem specific search operators and apply them in stochastic optimization procedures. The applicability of the approach is demonstrated by a reference example. The design of the algorithms will be oriented at the systematic framework of metric-based evolutionary algorithms (MBEAs). MBEAs are a special class of evolutionary algorithms, fulfilling certain guidelines for the design of search operators, whose benefits have been proven in theory and practice. MBEAs rely upon a suitable definition of a metric on the search space. The definition of a metric for the graph representation will be one of the main issues discussed in this paper. Although this article deals with the problem domain of chemical plant optimization, the algorithmic design can be easily transferred to similar network optimization problems. A useful distance measure for variable dimensionality search spaces is suggested.     

A novel evolutionary approach for optimizing content-based image indexing algorithms.

Optimization of content-based image indexing and retrieval (CBIR) algorithms is a complicated and time-consuming task since each time a parameter of the indexing algorithm is changed, all images in the database should be indexed again. In this paper, a novel evolutionary method called evolutionary group algorithm (EGA) is proposed for complicated time-consuming optimization problems such as finding optimal parameters of content-based image indexing algorithms. In the new evolutionary algorithm, the image database is partitioned into several smaller subsets, and each subset is used by an updating process as training patterns for each chromosome during evolution. This is in contrast to genetic algorithms that use the whole database as training patterns for evolution. Additionally, for each chromosome, a parameter called age is defined that implies the progress of the updating process. Similarly, the genes of the proposed chromosomes are divided into two categories: evolutionary genes that participate to evolution and history genes that save previous states of the updating process. Furthermore, a new fitness function is defined which evaluates the fitness of the chromosomes of the current population with different ages in each generation. We used EGA to optimize the quantization thresholds of the wavelet-correlogram algorithm for CBIR. The optimal quantization thresholds computed by EGA improved significantly all the evaluation measures including average precision, average weighted precision, average recall, and average rank for the wavelet-correlogram method.     

A diversity preserving selection in multiobjective evolutionary algorithms

In this paper, an efficient diversity preserving selection (DPS) technique is presented for multiobjective evolutionary algorithms (MEAs). The main goal is to preserve diversity of nondominated solutions in problems with scaled objectives. This is achieved with the help of a mechanism that preserves certain inferior individuals over successive generations with a view to provide long term advantages. The mechanism selects a group (of individuals) that is statistically furthest from the worst group, instead of just concentrating on the best individuals, as in truncation selection. In a way, DPS judiciously combines the diversity preserving mechanism with conventional truncation selection. Experiments demonstrate that DPS significantly improves diversity of nondominated solutions in badly-scaling problems, while at the same time it exhibits acceptable proximity performance. Whilst DPS has certain advantages when it comes to scaling problems, it empirically shows no disadvantages for the problems with non-scaled objectives.     

小生态进化技术综述

进化计算存在的遗传漂移现象使种群均匀地收敛于单一的优良解,导致早熟收敛或可选优良解的丢失,小生态技术是一种形成和维持稳定子种群、抑制遗传漂移的并行进化技术。系统地综述了小生态技术研究的主要成果,归纳了存在的问题,指出了进一步的研究方向。     

Antiviral therapy using a fuzzy controller optimized by modified evolutionary algorithms: a comparative study

Hepatitis is usually caused by a viral infection or metabolic diseases. Hepatitis type B virus (HBV) infection is among the most common causes of hepatitis and can result in serious liver diseases. Several dynamic models have been developed to mathematically describe the HBV infection and antiviral therapy. In addition, different control strategies have been reported in the literature to deal with optimal antiviral therapy problem of infectious diseases. In this paper, a set of optimized closed-loop fuzzy controllers are employed for optimal treatment of basic HBV infection. To optimize the proposed scheme, five modified and modern optimization algorithms are investigated. After designing the controller, some parameters of the HBV infection model are considered to be unknown, and the robustness of the optimized controller is studied. Experimental results show that the covariance matrix adaptation–evolution strategy-based optimized closed-loop fuzzy controller has the best performance in terms of total cost of an objective function defined based on maximization of uninfected target cells, minimization of free HBVs and minimization of drug usage. In addition, the execution time of this optimization algorithm is only 8 % more than the execution time of imperialist competition algorithm as the investigated algorithm with the best convergence speed.     

A statistical analysis of certain iterative learning control algorithms

Iterative learning control (ILC) is a technique used to improve the tracking performance of systems carrying out repetitive tasks, which are affected by deterministic disturbances. The achievable performance is greatly degraded, however, when non-repeating, stochastic disturbances are present. This paper aims to compare a number of different ILC algorithms, proposed to be more robust to the presence of these disturbances, first by a statistical analysis and then by simulation results and their application to a linear motor. New expressions for the expected value and variance of the controlled error are developed for each algorithm. The different algorithms are then tested in simulation and finally applied to the linear motor system to test their performance in practice. A filtered ILC algorithm is proposed when the noise and desired output spectra are separated. Otherwise an algorithm with a decreasing gain gives good robustness to noise and achievable precision but at a slower convergence rate.     

A novel population initialization method for accelerating evolutionary algorithms

Population initialization is a crucial task in evolutionary algorithms because it can affect the convergence speed and also the quality of the final solution. If no information about the solution is available, then random initialization is the most commonly used method to generate candidate solutions (initial population). This paper proposes a novel initialization approach which employs opposition-based learning to generate initial population. The conducted experiments over a comprehensive set of benchmark functions demonstrate that replacing the random initialization with the opposition-based population initialization can accelerate convergence speed.     

A survey: hybrid evolutionary algorithms for cluster analysis

Clustering is a popular data analysis and data mining technique. It is the unsupervised classification of patterns into groups. Many algorithms for large data sets have been proposed in the literature using different techniques. However, conventional algorithms have some shortcomings such as slowness of the convergence, sensitive to initial value and preset classed in large scale data set etc. and they still require much investigation to improve performance and efficiency. Over the last decade, clustering with ant-based and swarm-based algorithms are emerging as an alternative to more traditional clustering techniques. Many complex optimization problems still exist, and it is often very difficult to obtain the desired result with one of these algorithms alone. Thus, robust and flexible techniques of optimization are needed to generate good results for clustering data. Some algorithms that imitate certain natural principles, known as evolutionary algorithms have been used in a wide variety of real-world applications. Recently, much research has been proposed using hybrid evolutionary algorithms to solve the clustering problem. This paper provides a survey of hybrid evolutionary algorithms for cluster analysis.     

A constraint-guided method with evolutionary algorithms for economic problems

This paper presents an evolutionary algorithms based constrain-guided method (CGM) that is capable of handling both hard and soft constraints in optimization problems. While searching for constraint-satisfied solutions, the method differentiates candidate solutions by assigning them with different fitness values, enabling favorite solutions to be distinguished more likely and more effectively from unfavored ones.We illustrate the use of CGM in solving two economic problems with optimization involved: (1) searching equilibriums for bargaining problems; (2) reducing the rate of failure in financial prediction problems. The efficacy of the proposed CGM is analyzed and compared with some other computational techniques, including a repair method and a penalty method for the problem (1), a linear classifier and three neural networks for the problem (2), respectively. Our studies here suggest that the evolutionary algorithms based CGM compares favorably against those computational approaches.