Evolutionary Rough Parallel Multi-Objective Optimization Algorithm

• Autorzy: Maulik U. , Sarkar A.
• Języki publikacji: EN

Abstrakty

EN

A hybrid unsupervised learning algorithm, which is termed as Parallel Rough-based Archived Multi-Objective Simulated Annealing (PARAMOSA), is proposed in this article. It comprises a judicious integration of the principles of the rough sets theory and the scalable distributed paradigm with the archived multi-objective simulated annealing approach. While the concept of boundary approximations of rough sets in this implementation, deals with the incompleteness in the dynamic classification method with the quality of classification coefficient as the classificatory competencemeasurement, the time-efficient parallel approach enables faster convergence of the Pareto-archived evolution strategy. It incorporates both the rough set-based dynamic archive classification method and the distributed implementation as a two-phase speedup strategy in this algorithm. A measure of the amount of domination between two solutions has been incorporated in this work to determine the acceptance probability of a new solution with an improvement in the spread of the non-dominated solutions in the Pareto-front by adopting rough sets theory. A complexity analysis of the proposed algorithm is provided. An extensive comparative study of the proposed algorithm with three other existing and well-known Multi-Objective Evolutionary Algorithms (MOEAs) demonstrate the effectiveness of the former with respect to four existing performance metrics and eleven benchmark test problems of varying degrees of difficulties. The superiority of this new parallel implementation over other algorithms also has been demonstrated in timing, which achieves a near optimal speedup with a minimal communication overhead.

Słowa kluczowe

EN

amount of domination; archive; multi-objective optimization; parallel algorithms; rough set theory; simulated annealing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 99, nr 1
• Strony: 13--27
• Opis fizyczny: Bibliogr. 33 poz., tab., wykr.

Twórcy

autor

Maulik U.

autor

Sarkar A.

• Dept of Computer Sc. and Engg, Jadavpur University Kolkata-700032, India,

Bibliografia

• [1] Alba, E., Nebro, A. J., Luna, F.: Advances in Parallel Heterogeneous Genetic Algorithms for Continuous Optimization, International Journal of Applied Mathematics and Computer Science, 14(3), 2004, 101-117.
• [2] Bandyopadhyay, S., Pal, S. K., Aruna, B.: Multi-objective GAs, quantitative indices and pattern classification, IEEE Transactions on Systems, Man and Cybernetics-B, 34(5), 2004, 2088-2099.
• [3] Bandyopadhyay, S., Saha, S., Maulik, U., Deb, K.: A Simulated Annealing Based Multi-objective Optimization Algorithm: AMOSA, IEEE Transaction on Evolutionary Computation, 12(3), 2008, 269-283.
• [4] Camara, M., Ortega, J., Toro, F. J.: Parallel Processing for Multi-objective Optimization in Dynamic Environments, IEEE International Parallel and Distributed Processing Symposium, 2007, IPDPS 2007, 0, March.
• [5] Coello, C., Veldhuizen, D. V., Lamont, G.: Evolutionary algorithms for solving multi-objective problems, Kluwer Academic Publishers, Boston, 2002.
• [6] Cullar, D. E., Karp, R. M., Patterson, D., Sahay, A., Santos, D. D., Schauser, K. E., Subramonian, R., von Eicken, T.: LogP : A practical model of parallel computation, Communications of the ACM, 39(11), 1996, 78-85.
• [7] Deb, K.: Multi-objective optimization using evolutionary algorithms, John Wiley and Sons Ltd, England, 2001.
• [8] Deb, K., Pratap, A., Agarwal, S.,Meyarivan, T.: A fast and elitist mutiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computation, 6(2), 2002, 182-197.
• [9] Dhillon, I. S., Modha, D. S.: A Data-Clustering Algorithm on Distributed Memory Multiprocessors, Proceedings of Large-scale Parallel KDD Systems Workshop, ACM SIGKDD, 1759, August 1999, 245-260.
• [10] Durillo, J. J., Nebro, A. J., Luna, F., Alba, E.: Solving Three-Objective Optimization Problems Using a new Hybrid Cellular Genetic Algorithm, Parallel Problem Solving from Nature - PPSN X (G. Rudolph, T. Jensen, S. Lucas, C. Poloni, N. Beume, Eds.), 5199, Springer, 2008.
• [11] Gawrys, M., Sienkiewicz, J.: RSL - The Rough Set Library - Version 2.0, 1994.
• [12] Groll, L., Jakel, J.: A new convergence proof of fuzzy c-means, IEEE Trans. Fuzzy Syst., 13, 2005, 717-720.
• [13] Hernández-D´ıaz, A. G., Santana-Quintero, L. V., Coello, C. A. C., Caballero, R., Luque, J. M.: A new proposal for multi-objective optimization using differential evolution and rough sets theory, GECCO (M. Cattolico, Ed.), ACM, 2006, ISBN 1-59593-186-4.
• [14] Kalyanaraman, A., Aluru, S., Brendel, V.: Space and time efficient parallel algorithms and software for EST clustering, IEEE Transactions on Parallel and Distributed Systems, 14(12), December 2003, 1209-1221.
• [15] Kalyanaraman, A., Aluru, S., Kothari, S., Brendel, V.: Efficient clustering of large EST data sets on parallel computers, Nucleic Acids Research, 31(11),March 2003, 2963-2974.
• [16] Kirkpatrick, S., Gelatt, C., Vecchi, M.: Optimization by simulated anealing, Science, 220, 1983, 671-680.
• [17] Likas, A., Vlassis, N., Verbeek, J. J.: The global k-means clustering algorithm, Pattern Recognition, 36, 2003, 451-461.
• [18] Lin, W., Wu, Y., Mao, D., Yu, Y.: Attribute Reduction of Rough Set Based on Particle Swarm Optimization with Immunity, WGEC '08: Proceedings of the 2008 Second International Conference on Genetic and Evolutionary Computing, IEEE Computer Society,Washington, DC, USA, 2008, ISBN 978-0-7695-3334-6.
• [19] Luna, F., Nebro, A. J., Alba, E.: Observations in Using Grid-enabled Technologies for Solving Multiobjective Optimization Problems, Parallel Computing, 32(5-6), June 2006, 377-393.
• [20] Luna, F., Nebro, A. J., Alba, E.: Parallel EvolutionaryMultiobjective Optimization, in: Parallel Evolutionary Computations (N. Nedjah, L. de Macedo, E. Alba, Eds.), vol. 22 of Studies in Computational Intelligence, chapter 2, Springer, 2006, 33-56.
• [21] Nebro, A. J., Luna, F., Talbi, E.-G., Alba, E.: Parallel Multiobjective Optimization, in: Parallel Metaheuristics (E. Alba, Ed.),Wiley, 2005, 371-394.
• [22] Pacheco, P.: Parallel programming with MPI, Morgan Kaufmann, 1997.
• [23] Pawlak, Z.: Rough Sets, Theoretical Aspects of Reasoning About Data, Kluwer, Dordrecht, The Netherlands, 1991.
• [24] Schaffer, J. D.: Multiple objective optimization with vector evaluated genetic algorithms, Proceedings of The First International Conference on Genetic Algorithms (J. J. Grefensttete, Ed.), Lawrence Erlbaum, Hillsdale, NJ, 1987.
• [25] Schott, J. R.: Fault tolerant design using single and multi-criteria geneic algorithms, Ph.D. dissertation, 1995.
• [26] Smith, K., Everson, R., Fieldsend, J.: Dominancemeasures for muti-objective simulated annealing, Proceedings of the 2004 IEEE Congress on Evolutionary Computation (CEC'04), 2004.
• [27] Smolinski, T. G., Buchanan, R., Boratyn, G. M., Milanova, M., Prinz, A. A.: Independent component analysis-motivated approach to classificatory decomposition of cortical evoked potentials, Proceedings of The Third Annual Conference of the MidSouth Computational Biology and Bioinformatics Society, 7(Suppl 2), BMC Bioinformatics, March 2006.
• [28] Srinivas, N., Deb, K.: Multiobjective function optimization using nondominated sorting genetic algorithms, Evolutionary Computation, 2(3), 1995, 221-248.
• [29] Stoffel, K., Belkoniene, A.: Parallel k/h-Means Clustering for Large Data Sets, Lecture Notes In Computer Science - Proceedings of the 5th International Euro-Par Conference on Parallel Processing, Springer-Verlag London, UK, 1685, 1999, 1451 - 1454.
• [30] Suman, B.: Study of the self-stopping PDMOSA and performance measure in multiobjective optimization, Computers and Chemical Engineering, 29(5), April 2005, 1131-1147.
• [31] Tarjan, R. E.: Efficiency of a good but not linear set union algorithm, J. ACM, 22(2), 1975, 215-225.
• [32] Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: Empirical results, Evolutionary Computation, 8(2), Summer 2000, 173-195.
• [33] Zitzler, E., Thiele, L.: Multiobjective optimization using evolutionary algorithms - A comparative case study, in: Parallel Problem Solving From Nature,V (A. E. Eiben, T. Back, M. Schoenauer, H. P. Schwefel, Eds.), Springer-Verlag, Berlin, Germany, 1998, 292-301.