Research of Biogeography-Based Multi-Objective Evolutionary Algorithm

Introduction

Many real world problems require the simultaneous optimization of many conflicting objectives. The solutions to such problems are known as Pareto optimal set and the corresponding objective values are known as the Pareto front. For solving such problems, traditional mathematical program methods have limitations to the distribution of solutions in objective space. Evolutionary algorithms (EAs) are stochastic global search methods based on population evolution and many Pareto optimal solutions can be found in a single run. So many EAs had been developed for solving multi-objective optimization problems (MOP).

Over the past decade, a number of multi-objective evolutionary algorithms (MOEAs) have been suggested, such as Genetic algorithm for multi-objective optimization (MOGA) (Fonseca & Fleming, 1993), the Non-dominated Sorting Genetic Algorithm (NSGA) (Srinivas & Deb, 1995), the Niched Pareto Genetic Algorithm by Horn, Nafpliotis, and Goldberg (NPGA) (Horn, Nafpliotis & Goldberg, 1994). These MOEAS adopt the selection mechanisms based on Pareto ranking and fitness sharing to maintain diversity of the populations. After the algorithms mentioned above, MOEAS based on the elitism strategy were presented, such as the improved version of NSGA (NSGA-II), which is with a more efficient non-dominated sorting method, elitism and a crowded comparison operator without specifying any additional parameters for maintaining diversity (Deb, Pratap, Agarwal, & Meyarivan, 2002), the improved version of SPEA (SPEA2) (Zitzler, Laumanns, & Thiele, 2001), which is with a revised fitness assignment strategy, a nearest neighbor density estimation technique and an enhanced archive truncation method. All these MOEAs use recombination and mutation operator of GA to evaluate the population. In addition, some hybrid EAs were proposed, such as multi-objective algorithm based on particle swarm optimization (MOPSO) (Coello Coello, Pulido, & Lechuga, 2004), multi-objective algorithm based on ant colony (Zhang & Huang, 2005), multi-objective algorithm based on immune algorithm IDCMA (Jiao, Gong, Shang, et al., 2005) and Multi-objective Immune Algorithm with Non-dominated Neighbor-Based Selection (NNIA) (Gong, Jiao, Du, & Bo, 2008), a differential evolution based on double populations for solving multi-objective constrained optimization problem (Meng, Zhang, & Liu, 2008), and so on. Different evolutionary algorithms have its specific advantages for solving MOP.

In 2008, Biogeography-Based optimization (BBO) was proposed firstly by Dan Simon (Simon, 2008), which is a new stochastic search algorithm based on the principle of animal migration. BBO were compared with seven optimization algorithms and the results demonstrated its better performance for solving single objective optimization problem.

The science of biogeography can be traced to the work of nineteenth century naturalists such as Alfred Wallace (Wallace, 2005) and Charles Darwin (Darwin, 1859). In the early 1960s, Robert MacArthur and Edward Wilson began working together on mathematical models of biogeography. They were interested in mathematical models for the extinction and migration of species. Since their distinct work, biogeography has become a major area of research (Hanski & Gilpin, 1997). Mathematical models of biogeography describe how species migrate from one island to another, how new species arise, and how species become extinct. The term “island” here is used descriptively rather than literally. That is, an island is any habitat that is geographically isolated from other habitats.

In view of this, Simon presented the first paper on biogeography inspired algorithm for engineering (Simon, 2008), which is called biogeography based optimization (BBO). In his creative work, he merged the burgeoning field of biogeography with engineering in order to see how the two disciplines can be of mutual benefit. Although the idea of application of biogeography to engineering is similar to those nature inspired algorithms mentioned above, it has completely different mechanisms and process from those ones. It is again to prove the great power of nature.