Category Archives: Ant Colony Optimization

Ant Colony Optimization on GPU using CUDA

Posted by on April 11, 2011 No comments

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

Downloads: PDF | Bibtex

[1] J. Li, X. Hu, Z. Pang, and K. Qian, “A Parallel Ant Colony Optimization Algorithm based on Fine-Grained Model with GPU-Acceleration,” Internation Journal of Innovative Computing, Information, and Control, vol. 5, no. 11(A), November 2009.

[2] Y.-S. You, “Parallel ant system for traveling salesman problem on GPUs,” in Proceedings of GECCO 2009, 2009.

[3] S. Sanci, “A Parallel Algorithm for Flight Route Planning on GPU using CUDA,” Master’s thesis, Middle East Technical University,
Turkey, 2010.

[4] J. M. Cecilia, J. M. Garca, M. Ujaldon, A. Nisbet, and M. Amos, “Parallelization strategies for ant colony optimisation on GPUs,”
Computing Research Repository, pp. –1–1, 2011.

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.