Dual Population Genetic Algorithm for Solving Constrained Optimization Problems

Full Text (PDF, 486KB), PP.34-40

Views: 0 Downloads: 0

Author(s)

A. J. Umbarkar 1,* M. S. Joshi 2 P. D. Sheth 1

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

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

* Corresponding author.

DOI: https://doi.org/10.5815/ijisa.2015.02.05

Received: 27 Jun. 2014 / Revised: 1 Oct. 2014 / Accepted: 10 Nov. 2014 / Published: 8 Jan. 2015

Index Terms

Dual Population Genetic Algorithm, DPGA, Population Diversity, Metaheuristic Algorithms, Function Optimization, Constrained Optimization Problems, COPs

Abstract

Dual Population Genetic Algorithm is an effective optimization algorithm that provides additional diversity to the main population. It addresses the premature convergence problem as well as the diversity problem associated with Genetic Algorithm. Thus it restricts their individuals to be trapped in the local optima. This paper proposes Dual Population Genetic Algorithm for solving Constrained Optimization Problems. A novel method based on maximum constrains satisfaction is applied as constrains handling technique and Dual Population Genetic Algorithm is used as meta-heuristic. This method is verified against 9 problems from Problem Definitions and Evaluation Criteria for the Congress on Evolutionary Computation 2006 Special Session on Constrained Real-Parameter Optimization problem set. The results are compared with existing algorithms such as Ant Bee Colony Algorithm, Differential Evolution Algorithm and Genetic Algorithm that have been used for solving same problem set. Analysis shows that this technique gives results close to optimum value but fails to obtain exact optimum solution. In future Dual Population Genetic Algorithm can produce more efficient solutions using alternative constrains handling technique.

Cite This Paper

A. J. Umbarkar, M. S. Joshi, P. D. Sheth, "Dual Population Genetic Algorithm for Solving Constrained Optimization Problems", International Journal of Intelligent Systems and Applications(IJISA), vol.7, no.2, pp.34-40, 2015. DOI:10.5815/ijisa.2015.02.05

Reference

[1]T. Park, K. Ruy, “A Dual-Population Genetic Algorithm for Adaptive Diversity Control”, IEEE transactions on evolutionary computation, vol. 14, no. 6, 2010 DOI:10.1109/TEVC.2010.2043362
[2]K. Tang, K. Mang et.al, “Genetic Algorithm and their applications”, IEEE Signal Processing Magazine, pp.213-216, 1996. DOI: 10.1109/79.543973
[3]Applications of Genetic Algorithms, http://www.informatics.indiana.edu/ fil/CAS/PPT/Davis/sld029.html, 12th August, 2013.
[4]http://www.scribd.com/doc/211328880/Ga-Constraint, 31st August, 2014.
[5]T. Park, K. Ruy, “A Dual-Population Genetic Algorithm for Balance Exploration and Exploitation”, Acta Press Computational Intelligence, 2006.
[6]T. Park and K. Ruy, “A dual population genetic algorithm with evolving diversity”, in Proc. IEEE Congr. Evol. Comput., pp. 3516–3522, 2007, DOI: 10.1109/CEC.2007.4424928.
[7]T. Park and K. Ruy, “Adjusting population distance for dual-population genetic algorithm,” in Proc. of Aust. Joint Conf. Artif. Intell., pp. 171–180, 2007. DOI: 10.1109/TEVC.2010.2043362.
[8]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
[9]A. Umbarkar, M. Joshi, “Dual Population Genetic Algorithm (GA) versus OpenMP GA for Multimodal Function Optimization”, International Journal of Computer Applications, 64(19):29-36, February 2013. DOI: 10.5120/10744-5516
[10]D. Luenberger and Y. Ye, “Linear and nonlinear programming third edition”, New York, NY: Springer, 2007. ISBN 978-0-387-74503-9
[11]P. Boggs and J. Tolle, “Sequential quadratic programming,” Acta Numerica, vol.4, no.1, pp.1-51, 1995.
[12]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, pp.1245-1287, Jan. 2002. DOI: 10.1016/j.bbr.2011.03.031.
[13]H. Lu and W. Chen, “Self-adaptive velocity particle swarm optimization for solving constrained optimization problems”, J. Global Optimiz., vol.41, no.3, pp.427-445, Jul. 2008. DOI: 10.1007/s10898-007-9255-9.
[14]S. Koziel, Z. Michalewicz, “Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization”, Evolutionary Computation, vol.7, no.1, pp.19–44, 1999. DOI: 10.1162/evco.1999.7.1.19
[15]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, pp. 151–157, 1991.
[16]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, pp. 579–584, 1994.
[17]K. Deb, “An efficient constraint handling method for genetic algorithms, Computer Methods in Applied Mechanics and Engineering”, vol.186, no.2–4, pp. 311–338, 2000. DOI: 10.1016/S0045-7825(99)00389-8.
[18]I. Sardou, M. Ameli, M. Sepasian, M. Ahmadian, “A Novel Genetic-based Optimization for Transmission Constrained Generation Expansion Planning", IJISA, vol.6, no.1, pp.73-83, 2014. DOI: 10.5815/ijisa.2014.01.09
[19]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
[20]D. Karaboga, B. Akay, “A modified Artificial Bee Colony (ABC) algorithm for constrained optimization problems”, Applied Soft Computing, vol.11, no.3, pp. 3021-3031, 2011. DOI: 10.1016/j.asoc.2010.12.001
[21]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
[22]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.