Category Archives: Genetic Algorithms

Genetic Algorithms on GPU using CUDA

Posted by on April 13, 2011 3 comments

Some references for GA on GPU. If you know of any further resources, please contact me.

Downloads: PDF | Bibtex

[1] Q. Yu, C. Chen, and Z. Pan, “Parallel genetic algorithms on programmable graphics hardware,” in Lecture Notes in Computer Science
3612. Springer, 2005, p. 1051.

[2] P. Pospichal and J. Jaros, “GPU-based Acceleratino of the Genetic Algorithm,” in Proceedings of GECCO 2009, 2009.

[3] A. Munawar, M. Wahib, M. Munetomo, and K. Akama, “Hybrid of genetic algorithm and local search to solve max-sat problem using NVIDIA CUDA framework,” Genetic Programming and Evolvable Machines, vol. 10, pp. 391–415, 2009.

[4] S. Debattistic, N. Marlat, L. Mussi, and S. Cagnoni, “Implementatino of a Simple Genetic Algorithm within the CUDA Architecture,” in Proceedings of GECCO 2009, 2009.

[5] S. Zhang and Z. He, “Implementation of parallel genetic algorithm based on cuda,” in Advances in Computation and Intelligence, ser. Lecture Notes in Computer Science, Z. Cai, Z. Li, Z. Kang, and Y. Liu, Eds. Springer Berlin / Heidelberg, 2009, vol. 5821, pp. 24–30.

[6] S. Tsutsui and N. Fujimoto, “Solving quadratic assignment problems by genetic algorithms with gpu computation: a case study,” in Proceedings of the 11th Annual Conference Companion on Genetic and Evolutionary Computation Conference: Late Breaking Papers, ser. GECCO ’09. New York, NY, USA: ACM, 2009, pp. 2523–2530.

[7] P. Vidal and E. Alba, “A multi-gpu implementation of a cellular genetic algorithm,” in 2010 IEEE Congress on Evolutionary Computation (CEC), July 2010, pp. 1–7.

[8] ——, “Cellular genetic algorithm on graphic processing units,” in Nature Inspired Cooperative Strategies for Optimization (NICSO 2010), ser. Studies in Computational Intelligence, J. Gonzlez, D. Pelta, C. Cruz, G. Terrazas, and N. Krasnogor, Eds. Springer Berlin/Heidelberg, 2010, vol. 284, pp. 223–232.

[9] R. Arora, R. Tulshyan, and K. Deb, “Parallelization of binary and real-coded genetic algorithms on GPU using CUDA,” in IEEE Congress on Evolutionary Computation, 2010, pp. 1–8.

[10] N. Fujimoto and S. Tsutsui, “A highly-parallel tsp solver for a gpu computing platform,” in Proceedings of the 7th international conference on Numerical methods and applications, ser. NMA’10. Berlin, Heidelberg: Springer-Verlag, 2011, pp. 264–271.

Monte Carlo Simulation, State Space Pruning, and Meta-Heuristics

Posted by on July 5, 2010 1 comment

I haven't posted here in quite a while, mainly because I've been so busy and also because I didn't have the time to complete a proper post. As this blog is mainly about my professional career and academic interests, let me start by sharing some of my most recent work.

I have spent quite a bit of time pursuing an area of research concerned with State Space Pruning for Monte Carlo  Simulation (MCS) when calculating Reliability Indices for Power Systems. This is a necessity due to the curse of dimensionality. Simply stated, in a power system with 32 generators one finds themselves with a need to examine 2^{32} states. Expand this to a larger system and suddenly the state space size explodes. In this work we've used Genetic Algorithms (GA), Repulsive Binary Particle Swarm Optimization (RBPSO), and Ant Colony Optimization (ACO) in order to reduce MCS time and iterations before convergence. In all cases we have used a binary representation (each bit represents a generator's on/off state) with a DC Optimal Power Flow (DCOPF) that has been tailored to minimize load curtailment instead of cost. The algorithms are customized in order to server our particular needs (specifically generating states in which there is no load curtailment quickly). We have had a rather good success rate over two different test systems: IEEE-RTS79 and IEEE-RTS96. For those not familiar with them, these two test systems are designed specifically for reliability testing (RTS = Reliability Testing System). RTS-79 came first and RTS-96 (for the most part) is simply 3 RTS-79 that are connected to each other with minor changes. The table below shows a brief comparison between the two systems.

Generators Buses Lines Capacity Load
RTS-79 32 24 38 3405 2850
RTS-96 99 73 120 10215 8550



The details of the remainder of the work can be found by contacting me or checking out the papers that we have produced. This work has produced four three papers that have been either accepted or submitted so far that include:

  1. R. Green, L. Wang, Z. Wang, M. Alam, and C. Singh, “Power System Reliability Assessment Using Intelligent State Space Pruning Techniques: A Comparative Study” Submitted to 2010 Conference on Power System Technology, Hangzou China, October 2010.
  2. R. Green, L. Wang, M. Alam, and C. Singh, “State space pruning for Reliability Evaluation using Binary Particle Swarm Optimization,” Submitted to Hawaii International Conference on System Sciences,University of Hawaii at Manoa, January 2011.
  3. R. Green, L. Wang, and C. Singh, “State space pruning for power system reliability evaluation using genetic algorithms,” IEEE Power & Energy Society General Meeting 2010, Minneapolis, MN, July 2010.
  4. R. Green, Z. Wang, L. Wang, M. Alam, and C. Singh, “Evaluation of loss of load probability for power systems using intelligent search based state space pruning,” The 11th International Conference on Probabilistic Methods Applied to Power Systems, Singapore, June 2010

Some further resources for this work that may be helpful to others include:

  1. Matpower Formulation of IEEE-RTS79 [IEEE-RTS79 MatPower]
  2. Matpower Formulation of IEEE-RTS96 [IEEE-RTS96 MatPower]
  3. DCOPF for RTS79 in LP_Solve format [RTS-79 DC Optimal Power Flow]
  4. DCOPF for RTS96 in LP_Solve format [RTS-96 DC Optimal Power Flow]

As well as some references:

  1. Joydeep Mitra and Chanan Singh. Incorporating the dc load flow model in the decomposition-simulation method of multi-area reliability evaluation. IEEE Transactions on Power Systems, 11(3):1245-1254, Aug 1996.
  2. Chanan Singh and Joydeep Mitra. Composite system reliability evaluation using state space pruning. IEEE Transactions on Power Systems, 12(1):471-479, 1997.
  3. Joydeep Mitra and Chanan Singh. Pruning and simluation for determination of frequency duration indices of composite power systems. IEEE Transactions on Power Systems, 14(3):899-905, 1999.
  4. M. Wall. GAlib: A C++ library of genetic algorithm components. Mechanical Engineering Department, Massachusetts Institute of Technology, 1996.
  5. Lingfeng Wang and Chanan Singh. Stochastic combined heat and power dispatch based on multi-objective particle swarm optimization. International Journal of Electrical Power & Energy Systems, 30(3), 2007.
  6. Lingfeng Wang and Chanan Singh. Population-based intelligent search in reliability evaluation of generation systems with wind power penetration. IEEE Transactions on Power Systems, 23(3):1336-1345, May 2008.
  7. Lingfeng Wang and Chanan Singh. Reliability-constrained optimum placement of reclosers and distributed generators in distribution networks using an ant colony system
    algorithm. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, 38(6), 2008.
  8. Chanan Singh and Lingfeng Wang. Role of artificial intelligence in the reliability evaluation of electric power systems. Turkish Journal of Electrical Engineering & Computer Science,
    16(3):189-200, 2008.
  9. David E. Goldberg. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Professional, 1 edition, Jan 1989.
  10. Genetic algorithm, 2009. [ Wikipedia: Genetic Algorithms ]
  11. Ray D. Zimmerman, E. M.-S. Carlos, and Deqiang Gan. MATPOWER: A MATLAB Power System Simulation Package, Version 3.1b2, User's Manual. Technical report, Power Systems Engineering Research Center, 2006. [ Matpower ]
  12. Michel Berkelaar, Kjell Eikland, and Peter Notebaert. lp_solve : Open source (mixed-integer) linear programming system. 2004.
  13. IEEE Committee Report. IEEE reliability test system. IEEE Transactions on Power Apparatus and Systems, PAS-98(6):2047-2054, 1979.
  14. C. Grigg, P. Wong, P. Albrecht, and et al. The IEEE reliability test system-1996. IEEE Transactions on Power Systems, 14(3):1010-1020, 1999.
  15. Final report on research project 2473-10. Technical report, EPRI, 1987.
  16. M.V.F Pereira and N.J. Balu. Composite generation/transmission reliability evaluation. Proceedings of the IEEE, 80(4):470-491, apr 1992.
  17. Roy Billinton and Wenyuan Li. Reliability Assessment of Electric Power Systems using Monte Carlo Methods. Plenum, New York; London, 1994.
  18. J. Kennedy and R. Eberhart. Particle swarm optimization. In Neural Networks, 1995. Proceedings., IEEE International Conference on, volume 4, August 2002.
  19. Del, G. K. Venayagamoorthy, S. Mohagheghi, J. C. Hernandez, and R. G. Harley. Particle swarm optimization: Basic concepts, variants and applications in power systems. Evolutionary Computation, IEEE Transactions on, 12(2):171-195, 2008.
  20. D. K. Agrafiotis and W. Cedeño. Feature selection for structure-activity correlation using binary particle swarms. Journal of Medicinal Chemistry, 45:1098-1107, 2002.
  21. A. Moraglio, C. Di Chio, and R. & Poli. Geometric particle swarm optimization. In Proceedings of the European conference on genetic programming
    (EuroGP)    , volume 4445, pages 125-136, 2007.
  22. R. Green, L. Wang, and C. Singh. State space pruning for power system reliability evaluation using genetic algorithms. In Proceedings of the IEEE PES General Meeting, Minneapolis, MN, July 2010.
  23. R. Green, Z. Wang, L. Wang, M. Alam, and C. Singh. Evaluation of loss of load probability for power systems using intelligent search based state space pruning. In Proceedings of the 11th International Conference on Probabilistic Methods Applied to Power Systems, Singapore, June 2010.
  24. R. Green, L. Wang, M. Alam, and C. Singh. State space pruning for reliability evaluation using binary particle swarm optimization. Jan 2011.
  25. J. Kennedy and R.C. Eberhart. A discrete binary version of the particle swarm algorithm.In IEEE International Conference on Systems, Man, and Cybernetics, volume 5, pages 4104-4108, 1997.
  26. Riccardo Poli, James Kennedy, and Time Blackwell. Particle swarm optimization. Swarm Intelligence, 1(1):33-57, June 2007.
  27. C. K. Mohan and B. Al-Kazemi. Discrete particle swarm optimization. Indianapolis, IN, 2001. Purdue School of Engineering and Technology.
  28. R. Eberhart and James Kennedy. A new optimizer using particle swarm theory. In Proceedings of the Sixth International Symposium on Micro Machine and Human Science, pages 39-43, 1995.
  29. M. Dorigo. Optimization, Learning and Natural Algorithms. PhD thesis, Politecnico di Milano, Italy, 1992.
  30. Thomas Stützle and Holger H. Hoos. Max-min ant system. Future Gener. Comput. Syst., 16(9):889-914, 2000.
  31. Min Kong and Peng Tian. A binary ant colony optimization for the unconstrained function optimization problem. In CIS (1), pages 682-687, 2005.
  32. Onay Urfalioglu. Robust estimation of camera rotation, translation and focal length at high outlier rates. Computer and Robot Vision, Canadian Conference, 0:464-471, 2004.
  33. T. Krink, J. S. Vesterstrom, and J. Riget. Particle swarm optimisation with spatial particle extension. In CEC '02: Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, pages 1474-1479, Washington, DC, USA, 2002. IEEE Computer Society.
  34. T. Krink, J. S. Vesterstrom, and J. Riget. Particle swarm optimisation with spatial particle extension. In CEC '02: Proceedings of the Evolutionary Computation on 2002. CEC '02. Proceedings of the 2002 Congress, pages 1474-1479, Washington, DC, USA, 2002. IEEE Computer Society.
  35. J. Riget and J.S. Vesterstrøm. A diversity-guided particle swarm optimizer - the arpso. Technical report, 2002.