Friday , March 29 2024

Balanced Explore-Exploit clustering based Distributed Evolutionary Algorithm for Multi-objective Optimisation

Mariem GZARA
Multimedia Information systems and Advanced Computing Laboratory (MIRACL)
route Tunis Km 3; B.P. 1030, Sfax, 3018

Abdelbasset ESSABRI
Laboratoire de Gestion Industrielle et d’Aide à la Décision (GIAD)
route de l’aérodrome Km 4.5 BP 1088, Sfax, 3018

Abstract: Most parallel evolutionary algorithms for single and multi-objective optimisation are motivated by the reduction of the computation time and the resolution of larger problems. Another promising alternative is to create new distributed schemes that improve the behaviour of the search process of such algorithms. In multi-objective optimisation problems, more exploration of the search space is required to obtain the whole or the best approximation of the Pareto Optimal Front. In this paper, we present a new clustering-based parallel multi-objective evolutionary algorithm that balances between the two main concepts in metaheuristics, which are exploration and exploitation of the search space. The proposed algorithm is implemented and tested on several standard multi-objective test functions using a network of multiple computers.

Keywords: Parallel computing, multi-objective optimisation, evolutionary algorithms.

>>Full text
CITE THIS PAPER AS:
Mariem GZARA, Abdelbasset ESSABRI, Balanced Explore-Exploit clustering based Distributed Evolutionary Algorithm for Multi-objective Optimisation, Studies in Informatics and Control, ISSN 1220-1766, vol. 20 (2), pp. 97-106, 2011. https://doi.org/10.24846/v20i2y201102

1. Introduction

Evolutionary Algorithms (EAs) are stochastic search metaheuristics that have been used successfully to solve many optimisation problems such as scheduling, routing, etc [2, 17, 23, 14, 15]. EAs are population based metaheuristics that perform well global search by exploring simultaneously different regions of the search space. They are therefore less attracted to local optima and are suitable to solve Multi-Objective Optimisation problems (MOP) where a set of non-dominated solutions is sought. This is in contrast to the single-objective optimisation problems where a unique optimum is sought. Several algorithms are proposed to adapt EAs to MOPs, including NSGA-II [9, 25], SPEA-II [28], NPGA-II [20]. These algorithms can be divided into two categories: the non-Pareto and the Pareto Multi-Objective Evolutionary Algorithms (MOEAs). The concept of Pareto dominance is used to rank the population in such a way that all non-dominated individuals in the population are assigned the same cost. Pareto elitist MOEAs maintain another population than the current one, which permits to keep the Pareto-optimal solutions found during the search. This external population participates in the process of selection. Thus, elitism permits a better intensification of the search. Among these algorithms, SPEA-II [28] and NSGA-II [25] have powerful search mechanisms and obtained good results. SPEA-II [28] and NSGA-II [25] use similar concepts; such as Pareto selection, elitism and diversification techniques that are proved to be efficient to characterise the Pareto Optimal Front (POF). A state of the art on MOEAs is given in [13, 8, 7].

Despite their success in solving several real-world MOPs [11, 16], these algorithms require large computational times and memory. Several parallel schemes are proposed to overcome this problem. Another motivation is to exploit parallelism to best explore the search space and to discover new ways to direct the search. In the single-objective case, parallel EAs exploit the inherent parallelism in evolutionary computation where crossover, mutation, selection and fitness evaluation can be easily distributed. Whereas, in the multi-objective case, many parallel schemes focus on how to divide the population on the objective or/and the decision space where each process will concentrate on a specific region of the search space.

One of the most difficult issues in designing metaheuristics for the resolution of both single-objective and multi-objective problems is how to balance between exploration and exploitation of the search space. For example, in evolutionary computation a high rate of conventional mutation (high diversification) makes the search process looks like a random exploration. While a high rate of crossover without mutation leads to a premature convergence. In Parallel Multi-Objective Evolutionary Algorithms (PMOEAs), the parallelism can be exploited to direct the search toward more exploration or more exploitation through the mechanisms of collecting, dividing and redistributing the global population or a subset of individuals among the available processors. In this paper, we propose a new parallel evolutionary algorithm for multi-objective optimisation that is called “Balanced Explore Exploit clustering based Distributed Evolutionary Algorithm for multi-objective optimisation” (BEEDEA). This algorithm is based on dividing the search space by clustering algorithms then redistributing the individuals such that both global search and local search will be performed. To test the BEEDEA, we use the benchmark functions of Zitzler [27] on a network of several computers. Experimental results have shown that the BEEDEA performs a good balance between exploration and exploitation of the search space and it is more efficient to characterise the POF than a classic island model parallel MOEA without migration.

The paper is organised as follows. Section 2 reviews the literature on existing PMOEAs. Section 3 describes the proposed parallel MOEA. Section 4 presents numerical results. Section 5 concludes the paper and outlines future research directions.

REFERENCES

  1. ALBA, TOMASSINI, M., Parallelism and Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation, Vol. 6(5), 2002, pp. 443-462.
  1. MAHMOOD, A., A Hybrid Genetic Algorithm for Task Scheduling in Multiprocessor Real-Time Systems, Studies in Informatics and Control, Vol. 9(3), June 2000.
  2. BRANKE, J., H. SCHMECK, K. DEB, M. REDDY, Parallelizing Multi-objective Evolutionary Algorithms: Cone Separation, Congress on Evolutionary Computation, IEEE, 2004, pp. 1952-1957.
  3. BRANKE, J., T. KAU LER, H. SCHMECK, Guidance in Evolutionary Multiobjective Optimization, Advances in Engineering Software, vol. 32(6), 2001, pp. 499-508.
  4. CANTÚ-PAZ, E., A Survey of Parallel Genetic Algorithms, technical report, Illlinois Genetic Algorithms Lab., 1997.
  5. DE TORO, F., J. ORTEGA, J. FERNANDEZ, A. DIAZ, PSFGA: A Parallel Genetic Algorithm for Multiobjective Optimization, Proceedings of the 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, IEEE, 2002, pp. 384-391.
  6. DEB, K., Multi-Objective Optimization Using Evolutionary Algorithms, John Wiley & Sons, 2001.
  7. DEB, K., Multiobjective Optimization using evolutionary algorithms, Wiley, Chichester, UK, 2001.
  8. DEB, K., A. PRATAP, S. AGARWAL, T. MEYARIVAN, A Fast and Elitist Multiobjective Genetic Algorithm: NSGA -II, IEEE Transactions on Evolutionary Computation, vol. 6(3), 2002, pp. 182-197.
  9. DEB, K., P. ZOPE, A. JAIN, Distributed Computing of Pareto-optimal Solutions with Evolutionary Algorithms, In C.M. Fonseca, P.J. Fleming, E. Zitzler, K. Deb, and L. Thiele, editors, Evolutionary Multi-criterion Optimization, volume 2632 of LNCS, Springer, 2003, pp. 534-549.
  10. ERICKSON, M., A. MAYER, J. HORN, The Niched Pareto Genetic Algorithm 2 Applied to the Design of Groundwater Remediation Systems, In Eckart Zitzler, Kalyanmoy Deb, Lothar Thiele, Carlos A. Coello Coello, and David Corne, editors, First International Conference on Evolutionary Multi-Criterion Optimization, Springer-Verlag, Lecture Notes in Computer Science No. 1993, 2000, pp. 681-695.
  11. ESSABRI, A., M. GZARA, T. LOUKIL, Parallel Multi-Objective Evolutionary Algorithm with Multi-front Equitable Distribution, The fifth International Conference on Grid and Cooperative Computing (GCC 2006). Changsha (China), IEEE, 21-23 October. 2006, pp. 241-244.
  12. FONSECA, C. M., P. J. FLEMING, Genetic Algorithms for Multiobjective Optimization: Formulation, Discussion and Generalization, Proceedings of the Fifth International Conference on Genetic Algorithms, ICGA-93, San Francisco, CA, Morgan Kaufmann, 1993, pp. 416-423.
  13. FOURMAN, M. P., Compactation of Symbolic Layout using GAs, In Genetic Algorithms and their Applications: Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Lawrence Erlbaum, 1985, pp. 141-153.
  14. GOLDBERG, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley, 1989.
  15. HAJELA, P., C. LIN, Genetic Search Strategies in Multicriterion Optimal Design, Structural Optimization, 4, 1992, pp. 99-107.
  16. HARBAOUI, D., R. KAMMARTI, M. KSOURI, P. BORNE, A Genetic Algorithm for the Multi-Pickup and Delivery Problem with Time Windows, Studies in Informatics and Control, vol. 18(2), 2009.
  17. HIROYASU, T., M. KANEKO, M. MIKI, A Parallel Genetic Algorithm with Distributed Environment Scheme, Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, vol. 2, 2000, pp. 619-625.
  18. HIROYASU, T., M. MIKI, S. WATANABE, Distributed Genetic Algorithms with a New Sharing Approach in Multiobjective Optimization Problems, 1999 Congress on Evolutionary Computation, Washington, D.C., July 1999, pp. 69-76.
  19. HORN, J., N. NAFPLIOTIS, D. E. GOLDBERG, A Niched Pareto Genetic Algorithm for Multiobjective Optimization, in Proceedings of the 1st IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Computation, Piscataway, vol. 1, 27-29 Jun 1994, pp. 82-87.
  20. http://www.lifl.fr/OPAC/guimoo.
  21. KAMIURA, J., T. HIROYASU, M MIKI, S WATANABE, T. SAKODA, MOGADES: Multi-Objective Genetic Algorithm with Distributed Environment Scheme, Intelligent Systems Design and Applications (ISDA), 2002.
  22. KAMMARTI, R., S. HAMMADI, P. BORNE, M. KSOURI, A New Hybrid Evolutionary Approach for the Pickup and Delivery Problem with Time Windows, SMC (2), 2004, pp. 1498-1503.
  23. SCHAFFER, D., Multiple Objective Optimisation with Vector Evaluated Genetic Algorithm, Proceedings of the First International Conference on Genetic Algorithm, 1985, pp. 93-100.
  24. SRINIVAS, N., K. DEB, Multiobjective Optimization using Nondominated Sorting in Genetic Algorithms, Evolutionary Computation, vol. 2(3), MIT Press, Cambridge, 1995, pp. 221-248.
  25. STREICHERT D., H. ULMER, A. ZELL, Parallelization of Multi-objective Evolutionary Algorithms using Clustering Algorithms, Conference on Evolutionary Multi-Criterion Optimization (EMO 2005), LNCS series, V. 3410, SPRINGER, Guanajuato, Mexico, 9-11 March, 2005, pp. 92-107.
  26. ZITZLER, E., E. DEB, L. THIELE, Comparison of Multiobjective Evolutionary Algorithms: Empirical Results, Evolutionary Computation Journal, vol. 8(2), 2000, pp. 125-148.
  27. ZITZLER, E., M. LAUMANNS, L. THIELE, Spea2: Improving the Performance of the Strength Pareto Evolutionary Algorithm, in technical report 103, Computer Engineering and Communication Networks Lab (TIK), Swiss Federal Institute of Technology (ETH) Zurich, 2001.
  28. ZITZLER, E., THIELE, L., Multiobjective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach, IEEE Transactions on Evolutionary Computation, Vol. 3(4), 1999, pp. 257-271.