[GECCO'09] Improving Genetic Algorithms Performance via Deterministic Population Shrinkage

This year the Genetic and Evolutionary Computation Conference (GECCO) took place in Montréal (Québec-Canada) where we were presenting our last work in collaboration with the Laboratoire de Vision et Systèmes Numériques de l’Université Laval in Quebec City:

• Improving Genetic Algorithms Performance via Deterministic Population Shrinkage

Despite the intuition that the same population size is not needed throughout the run of an Evolutionary Algorithm (EA), most EAs use a fixed population size.
This paper presents an empirical study on the possible benefits of a Simple Variable Population Sizing (SVPS) scheme on the performance of Genetic Algorithms (GAs). It consists in decreasing the population for a GA run following a predetermined schedule, configured by a speed and a severity parameter. The method uses as initial population size an estimation of the minimum size needed to supply enough building blocks, using a fixed-size selectorecombinative GA converging within some confidence interval toward good solutions for a particular problem. Following this methodology, a scalability analysis is conducted on deceptive, quasi-deceptive, and non-deceptive trap functions in order to assess whether SVPS-GA improves performances compared to a fixed-size GA under different problem instances and difficulty levels. Results show several combinations of speed-severity where SVPS-GA preserves the solution quality while improving performances, by reducing the number of evaluations needed for success.

Using Dissortative Mating Genetic Algorithms to Track the Extrema of Dynamic Deceptive Functions

Traditional Genetic Algorithms (GAs) mating schemes select individuals for crossover independently of their genotypic or phenotypic similarities. In Nature, this behaviour is known as random mating. However, non-random schemes − in which individuals mate according to their kinship or likeness − are more common in natural systems. Previous studies indicate that, when applied to GAs, negative assortative mating (a specific type of non-random mating, also known as dissortative mating) may improve their performance (on both speed and reliability) in a wide range of problems. Dissortative mating maintains the genetic diversity at a higher level during the run, and that fact is frequently observed as an explanation for dissortative GAs ability to escape local optima traps. Dynamic problems, due to their specificities, demand special care when tuning a GA, because diversity plays an even more crucial role than it does when tackling static ones. This paper investigates the behaviour of dissortative mating GAs, namely the recently proposed Adaptive Dissortative Mating GA (ADMGA), on dynamic trap functions. ADMGA selects parents according to their Hamming distance, via a self-adjustable threshold value. The method, by keeping population diversity during the run, provides an effective means to deal with dynamic problems. Tests conducted with deceptive and nearly deceptive trap functions indicate that ADMGA is able to outperform other GAs, some specifically designed for tracking moving extrema, on a wide range of tests, being particularly effective when speed of change is not very fast. When comparing the algorithm to a previously proposed dissortative GA, results show that performance is equivalent on the majority of the experiments, but ADMGA performs better when solving the hardest instances of the test set.

Full paper here.

P2P technology for computing tasks does not always mean P2P computing

What would you think of a Bugatti Veyron limited to a maximum speed of 20 Km/h?? mmmm… YES!! Give me back the money!!

… well, that’s roughly my feeling when I read a paper on P2P computing restricting the scalability analysis to some few nodes. Of course, the analogy is not completely fair since performing a real massively distributed (and decentralized) experiment presents some challenges that, in most of the cases so far, remain out of the scope of the state of the art research. That happens, for instance, to P2P environments applied to optimization, and more precisely to Evolutionary Computation.

Usually, you can find two different approches for P2P optimization testing, either using simulations or using a “GRID-like style” in real environments, each case presents its own advantanges and drawbacks:

• Using simulations implies a certain number of assumptions about the real environment, hence, assumption have to be correct in some sense (e.g. representing a pesimistic scenario or making clear what’s the scope of the work) and results have to be understood under such an umbrella.

• Using a real P2P environment ( we performed a study like that using a 8×2 cluster). The adventage here is that the design has to face real restrictions, as communication or evaluation times, message passing restrictions or fault tolerance. Nevertheless, there are extreme difficulties to set a real and proper environment to test a model.

When you face a real environment, you find that:

• Large number of resources are hard to grab

• Scalability is hard to study. In the case of having few nodes, no real P2P computing is going on since no conclusions about large scalability can be drawn. On the other hand, if there are some good dozens of peers, other questions such as fault tolerance arise.

In the last friday paper seminar our team was discussing the following paper that uses the “grid-like style” for testing:

• P-CAGE environment for Evolutionary Computation in P2P systems

in which the authors propose a hybrid model combining islands with cellular EAs. Every peer holds an island and every island a cellular EA. As previously commented for grid-like testing, the scalability analysis is quite poor (up to 10 peers), additionally, the algorithm yields the best performance in the five peers’ scenario, pointing to a really poor scalability of the model. Nevertheless, the fact is that P-CAGE outperforms canonical EAs making of it a valid solution based on P2P technology, just that, such a solution is not really scalable and therefore, can not be really understood as P2P computing.

To conclude, I do think that simulations can benefit the understanding of complex interactions in P2P EAs at this stage of research, preventing situations as the one shown above, afterwards, there will be time to validate the models in real environments, letting that theory meets practice.

Immigrants do all the work

Genetic Agorithms with Memory- and Elitism-based Immigrants in Dynamic Environments was the paper selected for presentation and discussion in last Friday’s seminar. The article, authored by Shengxiang Yang, was published in the last Fall edition of Evolutionary Computation and addresses evolutionary optimization in dynamic environments.

Yang proposes two Genetic Algorithms (GAs) for dynamic optimization based on Grefenstette’s classical Random Immigrants GA (RIGA). RIGA tackles (or tries to) changing optima by inserting, in each and every generation, a certain number of randomly generated individuals that replace the worst individuals in the population (or randomly selected individuals, in another version). This way, genetic novelty is constantly being introduced and the population is expected to have enough diversity to react to changes in the environments. However, RIGA suffers from a major “weakness”: the raw building-blocks introduced by the randomly generated individuals are quickly removed from the population because their fitness is usually below average. RIGA is frequently chosen as a peer-algorithm for comparison purposes in evolutionary dynamic optimization studies, but, due to this “weak spot”, it may be questioned if a Standard GA is not better suited to assess the efficiency of a new method (in fact, studies currently being developed in our lab reinforce this hypothesis). In order to improve RIGA’s performance, several alternative RIGA-based methods have been proposed in the past few years.

The two GAs described in Yang’s paper try to overcome the problem with random immigrants by inserting in the population mutated copies of the elite — Elitism-based Immigrants Genetic Algorithm (EIGA) — or mutated copies of the chromosomes kept in a memory — Memory-based Immigrants Genetic Algorithm (MIGA). Memory-based approaches for dynamic optimization use a memory to store good solutions, which are retrieved later, periodically, or when the environments changes. Memory GAs are known to improve traditional GAs performance when the dynamics of changes are cyclic, that is, the fitness function returns to previous “shapes” from time to time; on the other hand, memory schemes are not that effective when the changes are not periodic. Therefore, and as expected, MIGA outperforms other GAs when the changes are cyclic. EIGA is better when the changes in the environment are not severe. This behaviour is explained by the fact that introducing mutated copies of the best individual in the population provides the GA with means to tackle small changes because the algorithm is maintaining a kind of sub-population around the optimal solution, and small shifts in the environment are easily traceable by those near-optimal individuals.

Summarizing, the study shows that MIGA and EIGA are able to outperform other GAs under the conditions of the test set. However, there is one question that remains unanswered: what happens when changing the parameter values? For instance, diversity maintenance schemes for dynamic optimization deal with non-stationary environments by maintaining the diversity at a higher level. This means that maybe the optimal mutation probability of these algorithms is different from those of Standard GAs. Shouldn’t a proper comparison between the algorithms consider a range of possible mutation probabilities (Yang’s studies used the traditional pm = 1/l, where l is the chromosome length)? And what about population size? Isn’t population size the major bottleneck for GAs’ performance in stationary environments? Is it possible that a variation in the population size of the GA for dynamic optimization conduces the research to different conclusions? Studies currently under way will try to answer to some of these questions.

Genetic algorithm with rough set theory

Last Friday we discussed the paper “The generic genetic algorithm incorporates with rough-set theory – An application of the web services composition” of Liang and Huang.  This is the standard mixture paper: a kind of algorithm + another soft computing technique + an application of the real world = a complete paper. I am not kidding, I think that combining several techniques, and more important, using them in real applications, should be a basis of research.

Rought set theory provides a way to create a set of decission rules that can be selected in every problem with functional requirements. For example in the extensive area of web services composition. We can provide this information to a genetic algorithm to compose services avoiding constrained solutions and initial population using that decission rules. The authors also use non-functional requirements, such QoS, cost or avilability in the fitness function. They conclude that the usage of rough set in a GA could increase the convergence (but it is necessary to keep some unfeasible solutions during the process, just in case).

It is a easy-to-read paper, so probably you would like to read it instead my summary ;) Moreover, they present some ideas in the web service composition area.

The Quest for the Holy Grail

Last week’s seminar was focused on Genetic Algorithms with varying population size. Like other GA’s parameters, population size was the subject of some studies in 1990s that aimed at exploring the established notion that different stages of the search require populations with different sizes. In general, we may say that larger populations are needed in the beggining of the search, and as the search proceeds towards the end, the GA is able to work with fewer individuals. One of the main objectives of the research on dynamic population GAs was to eliminate the population size parameter and design a GA that could adapt the size independently of the number of individuals in the first generation. That way, we could not only speed up the search process but also diminish the tuning effort. (On the other hand, improvements on scalability are, in my opinion, impossible to achieve with just a plain dynamic scheme.)

Some schemes only aim at overcoming the hard task of determining an optimal population size, and they do that by mimicking the process of tuning the population size by a GA’s expert (see also bisection method, K. Sastry). The parameter-less GA (Lobo et al.) works that way by evolving simultaneous and increasingly larger populations until the convergence criterion is met. This method does not speed up a standard GA. Instead, it may slow it down, but the worst-case scenario is of such a magnitude that is well worth using the parameter-less GA to avoid the tuning of the initial population size. Other techniques try to speed up the algorithms by dynamically changing the population size during the run, in a deterministic or adaptive manner.

Back in 1994, the authors (Arabas et al.) of the Genetic Algorithm with Varying Population Size (GAVaPS) claimed that the algorithm was able to adapt its population size during the run, according to the average fitness of the population and to the quality of the best or worst solutions. However, further studies could no replicate that described behaviour. Instead, GAVaPS population easily evolved towards extinction or experienced demographic burst that would increase its size and computational effort. The Adaptive Population Size GA (APGA) (Eiben et al.) tries to overcome this problem by engaging in a traditional steady state reproduction, that is, the population only generates two offspring in each generation. Although the authors presented a study were APGA outperforms several dynamic population sizing methods, F. Lobo and C. Lima later demonstrated that the algorithm does not really adapts its population size, but instead it remains below a specific values after a certain number of generation (In addition, they show that the test set were APGA apparently excels is probably not suited to evaluate GAs with dynamic population).

PRoFIGA (Valkó) is an example of deterministic control of the population (GAVaPS and APGA are adaptive). Unfortunately, it is also an example of an extremely complex algorithm when it comes to tuning it. PROFIGA removes the population size from the usual set of parameters, but it adds six (!) parameters. One of the main guidelines to parameter control is: make it simple. If we replace a parameter by another one (or more!), then the first objective – simplify the tuning for a non-expert user – is not met.

In 2001 (at GECCO), De Jong identified some of the open problems in Evolutionary Computation. Dynamic populations was one of them. Since then, not much has been done that we could consider as major breakthrough. In fact, varying population size is a serious candidate for the title of Evolutionary Computation Holy Grail! Take for instance the self-adaptation of the optimal population size. If the algorithm starts with a smaller population than the required, it has to grow its size, but it has to add genetic diversity along the way, because the initial genetic pool will no be able to converge to a solution (if it did, then the optimal population size would be expected one, but instead a smaller population, of course). Is it possible to design an effective dynamic scheme (that is, a scheme that could start with a population with random size, an then adapt in the first generations to the proper size)? Or should we start considering other applications for dynamic population GAs, and abandon the quest the for a GA which is independent of the initial population size?

[PACT'08][PABA Workshop I] Addressing Churn in P2P EA

This week the first Workshop on Parallel Architerctures and Bioinspired Algorithms is being held in Toronto (Canada) in conjunction with the prestigious conference Parallel Architectures and Compilation Techniques (PACT).

In extension to our line of work in P2P EAs, we have presented the work:

• Addressing Churn in a Peer-to-Peer Evolutionary Algorithm

In this paper we analyse the robustness of a Peer-to-Peer (P2P) Evolutionary Algorithm (EA) subject to the following dynamics: peers leave the system independently from each other causing a collective effect known as churn. The algorithm has been designed to tackle large instances of computationally expensive problems and, in this paper, we will assess its behavior under churn. To that end, we have performed a scalability analysis in five different scenarios using the Massively Multimodal Deceptive Problem as a
benchmark.  In all cases, the P2P EA reaches the success criterion without a penalty on the response time. The key to the algorithm robustness is to ensure enough peers at the beginning of the experiment. Some of them leave but those that remain are enough to guarantee a reliable  convergence.

Magical Science! (MSc)

Last friday I returned from the First Ferguson World Tour Of Science. I was traveling around Europe in order to present some things about my research.

First we arrived at Dortmund, Germany, where the Parallel Problem Solving from Nature (PPSN 2008) was celebrated. There I presented my paper “Evolving XSLT Stylesheets for Document Transformation” that you can download from here.

You can see me in this photo that JJ took explaining my poster to a great audience:

I hadn’t any problem explaining it. Nobody came to complain about colours, XML future, or typos in the word “Conclusions”. Oh, wait, I could remember… no, nobody came.

Here you can see me doing some magical science. Mmmh, who will be these guys sitting in that table?

After that I went to Castellón (Valencia, Spain) to present my paper “Algoritmos evolutivos distribuidos sobre dispositivos Bluetooth” (in Spanish, as you can see, but you also can download from here).

I’m uploading my own photos to my Flickr account.

Just to say that it has been an awesome travel around the world! I met a lot of interesting people and learnt a lot. Yeah, I really love the researcher’s life.

The title of this post is due to today I received my MSc degree (I presented this paper in Granada, where I am a grad student).

[Europar'08] P2P Evolutionary Algorithms

This last week we were presenting in Las Palmas de Gran Canaria ( Europar conference) the following work about Peer-to-Peer Evolutionary Algorithms:

• P2P Evolutionary Algorithms: A suitable approach for tackling large instances in hard optimization problems

Next, the slides of the presentation:

Evolving Machine Microprograms

The realization of a control unit can be done using a complex circuitry or microprogramming. The latter may be considered as an alternative method of implementation of machine instructions that can reduce the complexity and increase the flexibility of the control unit. The microcode efficiency and speed are of vital importance for the computer to execute machine instructions fast. This is a difficult task and it requires expert knowledge. It would be interesting and very helpful to have automated tools that, given a machine instruction description, could generate an efficient and correct microprogram. A good option is to use evolutionary computation techniques, which have proved been effective in the evolution of computer programs. In this paper, we intend to show how evolutionary computing techniques could be used to face this problem of generating efficient microprograms. We have developed a microarchitecture simulator of a real machine in order to evaluate an individual and to assign it the fitness value (to determine whether this candidate solution correctly implements the instruction machine). The proposed method is successful in generating correct solutions, not only for the machine code instruction set, but for new machine instructions not included in such set. We have shown that our approach can generate microprogramms to execute (to schedule microinstructions) the machine level instructions for a real machine. Moreover, this evolutive method could be applied to any microarchitecture just by changing the microinstruction set and pre-conditions of each machine instruction to guide evolution.

The poster, the source code of the proposed method and the full-length paper are available for download at http://atc.ugr.es/pedro/ev-micropr