The International Arab Journal of Information Technology (IAJIT)


An Efficient Parallel Version of Dynamic Multi- Objective Evolutionary Algorithm

Multi-Objective Optimization Evolutionary Algorithms (MOEAs) belong to heuristic methods proposed for solving Multi-objective Optimization Problems (MOPs). In fact, MOEAs search for a uniformly distributed, near-optimal, and near- complete Pareto front for a given MOP. However, several MOEAs fail to achieve their aim completely due to their fixed population size. To overcome this shortcoming, Dynamic Multi-Objective Evolutionary Algorithm (DMOEA) [20] was proposed. Although DMOEA has the distinction of dynamic population size, it still suffers from a long execution time. To deal with the last disadvantage, we have proposed previously a Parallel Dynamic Multi-Objective Evolutionary Algorithm (PDMOEA) [10] to obtain efficient results in less execution time than the sequential counterparts, in order to tackle more complex problems. This paper is an extended version of [10] and it aims to demonstrate the efficiency of PDMOEA through more experimentations and comparisons. We firstly compare DMOEA with other multi-objective evolutionary algorithms Non-Dominated Sorting Genetic Algorithm (NSGA-II) and Strength Pareto Evolutionary Algorithm (SPEA-II), then we present an exhaustive comparison of PDMOEA versus DMOEA and discuss how the number of used processors influences the efficiency of PDMOEA. As experimental results, PDMOEA enhances DMOEA in terms of three criteria: improving the objective space, minimizing the computational time, and converging to the desired population size. Finally, the paper establishes a new formula relating the suitable number of processes, required in PDMOEA, and the number of necessary generations to converge to the optimal solutions.

[1] Barker B., “Message Passing Interface (MPI),” Workshop: High Performance Computing on Stampede, Ithaca, vol. 262, 2015.

[2] Belaiche L. and Kahloul L., “The Optimal Process Planning for Reconfigurable Manufacturing Systems,” in Proceeding of the International Conference on Mathematics and Information Technology, Adrar, pp. 309-316, 2017.

[3] Belaiche L., Kahloul L., Benharzallah S., and Hafidi Y., “Multi-objective Optimization-Based Approach for Throughput Maximization in Reconfigurable Manufacturing Systems,” in Proceeding of the 5th International Symposium on Innovation in Information and Communication Technology, United States, pp. 1-8, 2018.

[4] Belaiche L., Kahloul L., Benharzallah S., and Hafidi Y., “Bi-Objective Framework For Planning A Supply Chain Process in Reconfigurable Manufacturing Systems,” IFAC-PapersOnLine, vol. 52, no. 13, pp. 1675-1680, 2019.

[5] Czarnul P., Parallel Programming for Modern High Performance Computing Systems, Chapman and Hall/CRC, 2018.

[6] Dagostino D., Pasquale G., and Merelli I., “A Fine-Grained Cuda Implementation of the Multi- Objective Evolutionary Approach Nsga-Ii Potential Impact for Computational and Systems Biology Applications,” in Proceeding of the International Meeting on Computational Intelligence Methods for Bioinformatics and Biostatistics, Cambridge, pp. 273-284, 2014.

[7] Deb K., Multi-objective Optimization Using Evolutionary Algorithms, John Wiley and Sons, 2001.

[8] Deb K., Pratap A., Agarwal S., and Meyarivan T., “A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-2,” IEEE Transactions on Evolutionary Computation, vol. 6, n. 2, pp. 182-197, 2002.

[9] González-Álvarez D., Vega-Rodríguez M., and Rubio-Largo Á., “A Hybrid Mpi/Openmp Parallel Implementation of Nsga-Ii for Finding Patterns in Protein Sequences,” Journal of Supercomputing, vol. 73, no. 6, Pp. 2285-2312, 2017.

[10] Grid M., Belaiche L., Kahloul L., and Benharzallah S., “Parallel Dynamic Multi- Objective Optimization Evolutionary Algorithm,” in Proceeding of the International Arab Conference on Information Technology, Muscat, pp. 1-6, 2021.

[11] Gropp W., Lusk E., and Skjellum A., Using MPI: Portable Parallel Programming with the Message-Passing Interface, MIT Press, 1999.

[12] Gropp W., Tutorial on Mpi: The Message Passing Interface, Argonne National Laboratory, 1995.

[13] Houimli M., Kahloul L., and Khalgui M., “Multi- Objective Optimization and Formal Specification Of Reconfigurable Manufacturing System Using Adaptive NSGA-II,” in Proceeding of the 1st International Conference on Embedded and Distributed Systems, Oran, pp. 1-6, 2017.

[14] Lowenthal D., Freeh V., and Andrews G., “Using Fine-Grain Threads and Run-Time Decision Making in Parallel Computing,” Journal of Parallel and Distributed Computing, vol. 37, no. 1, pp. 41-54, 1996.

[15] Lu H. and Yen G., “Dynamic Population Size in Multiobjective Evolutionary Algorithms,” in Proceeding of the Congress on Evolutionary Computation, Honolulu, pp. 1648-1653, 2002.

[16] Mitchell M., an Introduction to Genetic Algorithms, MIT Press, 1998.

[17] Santander-Jiménez S. and Vega-Rodríguez M., “Applying Openmpbased Parallel Implementations of Nsga-Ii and Spea2 To Study Phylogenetic Relationships,” in Proceeding of the IEEE International Conference on Cluster Computing, Madrid, pp. 305-313, 2014.

[18] Tan K., Lee T., and Khor E., “Evolutionary Algorithms with Dynamic Population Size and Local Exploration for Multiobjective Optimization,” IEEE Transactions on Evolutionary Computation, vol. 5, no. 6, pp. 565- 588, 2001.

[19] Torki F., Kahloul L., Hamani N., Belaiche L., and Benharzallah S., “Products Scheduling in Reconfigurable Manufacturing System Considering the Responsiveness Index,” in Proceeding of the 22nd International Arab Conference on Information Technology, Muscat, pp. 1-6, 2021. An Efficient Parallel Version of Dynamic Multi-Objective Evolutionary Algorithm 431

[20] Yen G. and Lu H., “Dynamic Multiobjective Evolutionary Algorithm: Adaptive Cell-Based Rank and Density Estimation,” IEEE Transactions on Evolutionary Computation, vol. 7, no. 3, pp. 253-274, 2003.

[21] Zitzler E., Laumanns M., and Thiele L., “SPEA2: Improving the Strength Pareto Evolutionary Algorithm,” TIK-report, vol. 103, 2001.