Decentralized Genetic Algorithms and Multiobjective Optimization

Last friday we were discussing the issues of decentralization and multiobjective optimization in Genetic Algorithms, in more detail:

  • Decentralizing GAs is a radical way of parallelizing GAs in which the parallel infraestructure is devoid of any central server. Hence, individuals have no global but local information provided by the neighbourhood.
  • Multiobjective GAs are GAs optimizing several conflicting objectives. In such a way the output of the GA is not a single but a set of solutions (usually named pareto-front) and it is based on some criterion of dominance.

Matching both issues is not straightforward since inserting a new solution within the set of solutions requires of a global comparison through the pareto-front and, talking about a decentralized GA, the pareto-front should be decentralized in advance. The consequence is that there are few works tackling such challenge. One of them is the paper A Cellular Genetic Algorithm for Multiobjective Optimization by Nebro et al.which can be considered as an step towards, although not a definitive solution to decentralized multiobjective optimization. The authors propose:

  • A decentralized GA: the Cellular Genetic Algorithm in which every individual is a single process.
  • An external archive (and centralized) to store the non-dominated solutions.
  • A simulation of the parallel environment.

In spite of the drawback of having a centralized archive which does not allow a real parallel/decentralized execution, results show to be algorithmically competitive against the state of the art algorithms NSGA-II and SPEA2. Therefore, one of the possible reading from the paper is that decentralized GAs are promising, although there is no a pure decentralized GA for Multiobjective optimization yet.

2 thoughts on “Decentralized Genetic Algorithms and Multiobjective Optimization

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s