A. J. Umbarkar; M. S. Joshi; P. D. Sheth

OpenMP Dual Population Genetic Algorithm for Solving Constrained Optimization Problems

Full Text (PDF, 415KB), PP.59-65

Views: 0 Downloads: 0

Author(s)

A. J. Umbarkar ^1,* M. S. Joshi ² P. D. Sheth ¹

1. Department of Information Technology, Walchand College of Engineering, Sangli, 416-416, India

2. Department of Computer Engineering, Jawaharlal Nehru Engineering College, Aurangabad, MS, India

* Corresponding author.

DOI: https://doi.org/10.5815/ijieeb.2015.01.08

Received: 10 Sep. 2014 / Revised: 25 Oct. 2014 / Accepted: 20 Nov. 2014 / Published: 8 Jan. 2015

Index Terms

Dual Population Genetic Algorithm (DPGA), Open Multiprocessing (OpenMP), Constrained Optimization Problems (COPs), High Performance Computing (HPC), Meta-heuristic Algorithms, Function Optimization

Abstract

Dual Population Genetic Algorithm is an effective optimization algorithm that provides additional diversity to the main population. It deals with the premature convergence problem as well as the diversity problem associated with Genetic Algorithm. But dual population introduces additional search space that increases time required to find an optimal solution. This large scale search space problem can be easily solved using all available cores of current age multi-core processors. Experiments are conducted on the problem set of CEC 2006 constrained optimization problems. Results of Sequential DPGA and OpenMP DPGA are compared on the basis of accuracy and run time. OpenMP DPGA gives speed up in execution.

Cite This Paper

A. J. Umbarkar, M. S. Joshi, P. D. Sheth, "OpenMP Dual Population Genetic Algorithm for Solving Constrained Optimization Problems", International Journal of Information Engineering and Electronic Business(IJIEEB), vol.7, no.1, pp.59-65, 2015. DOI:10.5815/ijieeb.2015.01.08

Reference

[1]T. Park, K. Ruy, “A Dual-Population Genetic Algorithm for Adaptive Diversity Control”, IEEE transactions on evolutionary computation, vol. 14, no.6, pp 865-883, Dec. 2010, pp 865-883. DOI:10.1109/TEVC.2010.2043362.
[2]http://openmp.org, June 2013.
[3]https://software.intel.com, June 2013.
[4]T. Park, K. Ruy, “A Dual-Population Genetic Algorithm for Balance Exploration and Exploitation”, Acta Press Computational Intelligence, 2006.
[5]T. Park and K. Ruy, “A dual population genetic algorithm with evolving diversity”, in Proc. IEEE Congress Evolutionary Computation, 2007, pp. 3516–3522. DOI: 10.1109/CEC.2007.4424928.
[6]T. Park and K. Ruy, “Adjusting population distance for dual-population genetic algorithm,” in Proc. Aust. Joint Conf. Artificial Intelligence, 2007, pp. 171–180. DOI:10.1109/TEVC.2010.2043362.
[7]T. Park, R. Choe, K. Ruy, “Dual-population Genetic Algorithm for Nonstationary Optimization”, in Proc. GECCO’08 ACM, 2008, pp.1025-1032. DOI: 10.1145/1389095.1389286.
[8]A. Umbarkar, M. Joshi, “Dual Population Genetic Algorithm (GA) versus OpenMP GA for Multimodal Function Optimization”, International Journal of Computer Applications, vol. 19, no. 64, February 2013, pp. 29-36. DOI: 10.5120/10744-5516.
[9]D. Luenberger and Y. Ye, “Linear and nonlinear programming third edition”, New York, NY: Springer, 2007. ISBN 978-0-387-74503-9.
[10]P. Boggs and J. Tolle, “Sequential quadratic programming,” Acta Numerica, vol.4, no.1, Jan. 1995, pp.1-51.
[11]C. Coello Coello, “Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: A survey of the state of the art,” Comput. Methods Appl. Mech. Eng., vol.191, no.11-12, Jan. 2002, pp.1245-1287. DOI: 10.1016/j.bbr.2011.03.031.
[12]H. Lu and W. Chen, “Self-adaptive velocity particle swarm optimization for solving constrained optimization problems” J. Global Optimiz., vol.41, no.3, Jul. 2008, pp.427-445. DOI: 10.1007/s10898-007-9255-9.
[13]S. Koziel, Z. Michalewicz, “Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization”, Evolutionary Computation, vol.7, no.1, 1999, pp.19–44. DOI: 10.1162/evco.1999.7.1.19.
[14]Z. Michalewicz, C.Z. Janikow, “Handling constraints in genetic algorithms, in: R.K. Belew, L.B. Booker (Eds.)”, In Proc. of the Fourth International Conference on Genetic Algorithms (ICGA-91), San Mateo, California, University of California, San Diego, Morgan Kaufmann Publishers, 1991, pp. 151–157.
[15]Z. Michalewicz, M. Schoenauer, “Evolutionary algorithms for constrained parameter optimization problems”, Evolutionary Computation, vol.4, no.1, 1996, pp.1–32. DOI: 10.1162/evco.1996.4.1.1.
[16]A. Homaifar, S.H.Y. Lai, X. Qi, “Constrained optimization via genetic algorithms”, Simulation, vol.62, no.4, 1994, pp.242–254. DOI: 10.1177/003754979406200405.
[17]J. Joines, C. Houck, “On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs, in: D. Fogel (Ed.)”, In Proc. of the first IEEE Conference on Evolutionary Computation, IEEE Press, Orlando, Florida, 1994, pp. 579–584.
[18]Z. Michalewicz, N. Attia, “Evolutionary optimization of constrained problems”, In Proc. of the 3rd Annual Conference on Evolutionary Programming, World Scientific, 1994, pp. 98–108. DOI: 10.1.1.141.2355.
[19]J. Richardson, M. Palmer, G. Liepins, M. Hilliard, “Some guidelines for genetic algorithms with penalty functions”, In J. D. Schaffer (Ed.), Proc. of the third International Conference on Genetic Algorithms (ICGA-89), George Mason University, Morgan Kaufmann Publishers, San Mateo, California, June, 1989, pp. 191–197.
[20]M. Schoenauer, S. Xanthakis, “Constrained GA optimization”, In S. Forrest (Ed.), Proc. of the fifth International Conference on Genetic Algorithms (ICGA-93), University of Illinois at Urbana-Champaign, Morgan Kauffman Publishers, San Mateo, California, July, 1993, pp. 573–580.
[21]D. Powell, M. Skolnick, “Using genetic algorithms in engineering design optimization with non-linear constraints”, In S. Forrest (Ed.), Proc. of the fifth International Conference on Genetic Algorithms (ICGA-93), University of Illinois at Urbana-Champaign, Morgan Kaufmann Publishers, San Mateo, California, July, 1993, pp. 424–431.
[22]Z. Michalewicz, G. Nazhiyath, “Genocop III: a co-evolutionary algorithm for numerical optimization with nonlinear constraints”, In D.B. Fogel (Ed.), Proc. of the Second IEEE International Conference on Evolutionary Computation, IEEE Press, Piscataway, NJ, 1995, pp. 647–651.
[23]K. Deb, “An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering”, vol.186, no.2–4, 2000, pp. 311–338. DOI: 10.1016/S0045-7825(99)00389-8.
[24]S. Elsayed, R. Sarker. D. Essam, "Improved genetic algorithm for constrained optimization," in Proc. of International Conference on Computer Engineering & Systems (ICCES), 2011, pp. 111-115. DOI: 10.1109/ICCES.2011.6141022.
[25]Z. Ziqiang, C. Zhihua, Z. Jianchao, Y. Xiaoguang, “Artificial Plant Optimization Algorithm for Constrained Optimization Problems”, in Proc. of Second International Conference on Innovations in Bio-inspired Computing and Applications (IBICA), 2011, pp. 120-123. DOI: 10.1109/IBICA.2011.34.
[26]B. Xiaojun, W. Jue, “Constrained Optimization Based on Epsilon Constrained Biogeography-Based Optimization”, in Proc. of 4th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC), 2012, pp. 369-372. DOI: 10.1109/IHMSC.2012.184.
[27]S. Elsayed, R. Sarker, D. Essam, “On an evolutionary approach for constrained optimization problem solving”, Applied Soft Computing, vol. 12, 2012, pp. 3208-3227. DOI: 10.1016/j.asoc.2012.05.013.
[28]W. Yong, C. Zixing, “Combining Multiobjective Optimization With Differential Evolution to Solve Constrained Optimization Problems”, IEEE Transactions on Evolutionary Computation, vol.16, 2012, pp.117-134. DOI: 10.1109/TEVC.2010.2093582.
[29]R. Rao, V. Patel, “An elitist teaching-learning-based optimization algorithm for solving complex constrained optimization problems”, International Journal of Industrial Engineering Computations, vol.3, no.4, 2012, pp. 535-560. DOI: 10.1016/j.engappai.2012.06.007.
[30]M. Campos, R. Krohling, “Hierarchical bare bones particle swarm for solving constrained optimization problems” in Proc. of IEEE Congress on Evolutionary Computation (CEC-2013), 2013, pp. 805-812. DOI: 10.1109/CEC.2013.6557651.
[31]R. Datta, M. F. P. Costa, K. Deb, A. Gaspar-Cunha, “An evolutionary algorithm based pattern search approach for constrained optimization”, in Proc. of IEEE Congress on Evolutionary Computation (CEC-2013), 2013, pp. 1355-1362. DOI: 10.1109/CEC.2013.6557722.
[32]L. Zhenyi and H. Qing, “A numerical gradient based technique and directed neighborhood structure for Constrained Particle Swarm Optimization”, in Proc. of American Control Conference (ACC), 2013, pp. 4783-4788. ISBN: 978-1-4799-0177-7.
[33]I. Sardou, M. Ameli, M. Sepasian, M. Ahmadian, “A Novel Genetic-based Optimization for Transmission Constrained Generation Expansion Planning", IJISA, vol.6, no.1, 2014, pp.73-83. DOI: 10.5815/ijisa.2014.01.09.
[34]Y. Zhu, D. Qin, Y. Zhu, X. Cao, “Genetic Algorithm Combination of Boolean Constraint Programming for Solving Course of Action Optimization in Influence Nets”, IJISA, vol.3, no.4, 2011, pp.1-7.
[35]M. Mehra, M. Jayalal, A. John Arul, S. Rajeswari, K. Kuriakose, S. Murty, “Study on Different Crossover Mechanisms of Genetic Algorithm for Test Interval Optimization for Nuclear Power Plants”, IJISA, vol.6, no.1, 2014, pp.20-28. DOI: 10.5815/ijisa.2014.01.03.
[36]D. Karaboga, B. Akay, “A modified Artificial Bee Colony (ABC) algorithm for constrained optimization problems”, Applied Soft Computing, vol.11, no.3, April 2011, pp. 3021-3031. DOI: 10.1016/j.asoc.2010.12.001.
[37]J. Paredis, “Co-evolutionary constraint satisfaction”, In Proc. of the 3rd Conference on Parallel Problem Solving from Nature, Springer-Verlag, NewYork, 1994, pp. 46–55. DOI: 10.1007/3-540-58484-6_249.
[38]I. Parmee, G. Purchase, “The development of a directed genetic search technique for heavily constrained design spaces”, In I.C. Parmee (Ed.), Adaptive Computing in Engineering Design and Control-94, University of Plymouth, Plymouth, UK, 1994, pp. 97–102.
[39]H. Myung, J. Kim, D. Fogel, “Preliminary investigation into a two-stage method of evolutionary optimization on constrained problems”, In J. McDonnell, R. Reynolds, D. Fogel (Eds.), Proc. of the fourth Annual Conference on Evolutionary Programming, MIT Press, Cambridge, MA, 1995, pp. 449–463.
[40]R. Reynolds, Z. Michalewicz, M. Cavaretta, “Using cultural algorithms for constraint handling in GENOCOP, In J. McDonnell, R. Reynolds, D. Fogel (Eds.), Proc. of the fourth Annual Conference on Evolutionary Prog., MIT Press, Cambridge, MA, 1995, pp. 298– 305. ISBN: 9780262290920
[41]J. Liang, T. Runarsson, E. Mezura-Montes, M. Clerc, P. Suganthan, C. Coello Coello, K. Deb, “Problem Definitions and Evaluation Criteria for the CEC 2006 special Session on Constrained Real-Parameter Optimization”, IEEE Congress on Evolutionary Computation (CEC-2006), IEEE, Vancouver, BC, Canada, 2006.

International Journal of Information Engineering and Electronic Business (IJIEEB)