Category Archives: Particle Swarm Optimization

Particle Swarm Optimization (PSO) in Matlab

Posted by on April 25, 2011 1 comment

Here is a very simple version of PSO in Matlab. PSO is a very popular, population based metaheuristic algorithm that mimics swarming behavior and swarm intelligence in order to solve optimization problems.

The code below is intended to get you started working with PSO in Matlab or Octave. Best efforts were made to keep the code clean and easy to understand. Feel free to play with it and contact me with any questions.

Click Here to Download PSO.m

Particle Swarm Optimization on the GPU using CUDA

Posted by on March 21, 2011 1 comment

I'm currently doing some research into Particle Swarm Optimization (PSO) on the GPU using CUDA. As a bit of preliminary work I am gathering previous research on the topic. Below is a list of the most recent work that I can find including a PDF and Bibtex version of all references. If you know of any further resources, please contact me.

Downloads: PDF | Bibtex

[1] G. A. Laguna-Snchez, M. Olgun-Carbajal, N. Cruz-Corts, and R. B.-F. J. A. Alvarez-Cedillo, “Comparative study of parallel variants for a particle swarm optimization,” Journal of Applied Research and Technology, vol. 7, no. 3, pp. 292–309, 2010.

[2] Y. Zhou and Y. Tan, “GPU-based parallel particle swarm optimization,” in Proceedings of the Eleventh conference on Congress on Evolutionary Computation, ser. CEC '09. Piscataway, NJ, USA: IEEE Press, 2009, pp. 1493–1500.

[3] L. Mussi, S. Cagnoni, and F. Daolio, “GPU-based road sign detection using particle swarm optimization,” in Ninth International Conference on Intelligent Systems Design and Applications, December 2009, pp. 152 –157.

[4] W. Zhu and J. Curry, “Particle swarm with graphics hardware acceleration and local pattern search on bound constrained problems,” in IEEE Swarm Intelligence Symposium, 2009. SIS ’09, April 2009, pp. 1–8.

[5] L. de P. Veronese and R. Krohling, “Swarm’s flight: Accelerating the particles using C-CUDA,” in IEEE Congress on Evolutionary Computation, 2009. CEC ’09., May 2009, pp. 3264 –3270.

[6] B. Rymut and B. Kwolek, “Gpu-supported object tracking using adaptive appearance models and particle swarm optimization,” in Proceedings of the 2010 international conference on Computer vision and graphics: Part II, ser. ICCVG’10. Berlin, Heidelberg: Springer-Verlag, 2010, pp. 227–234.

[7] C. Bastos-Filho, M. Oliveira, D. Nascimento, and A. Ramos, “Impact of the random number generator quality on particle swarm optimization algorithm running on graphic processor units,” in Hybrid Intelligent Systems (HIS), 2010 10th International Conference on, August 2010, pp. 85–90.

[8] L. Mussi, F. Daolio, and S. Cagnoni, “Evaluation of parallel particle swarm optimization algorithms within the CUDA(TM) architecture,” Information Sciences, vol. In Press, Corrected Proof, 2010.

[9] L. Mussi, S. Ivekovic, and S. Cagnoni, “Markerless articulated human body tracking from multi-view video with gpu-pso,” in Proceedings of the 9th international conference on Evolvable systems: from biology to hardware, ser. ICES’10. Berlin, Heidelberg:Springer-Verlag, 2010, pp. 97–108.

[10] Y. Tan and Y. Zhou, “Parallel particle swarm optimization algorithm based on graphic processing units,” in Handbook of Swarm Intelligence, ser. Adaptation, Learning, and Optimization, L. M. Hiot, Y. S. Ong, B. K. Panigrahi, Y. Shi, and M.-H. Lim, Eds. Springer Berlin Heidelberg, 2010, vol. 8, pp. 133–154.

[11] Y. Zhou and Y. Tan, “Particle swarm optimization with triggered mutation and its implementation based on GPU,” in Proceedings of the 12th annual conference on Genetic and evolutionary computation, ser. GECCO ’10. New York, NY, USA: ACM, 2010, pp. 1–8.

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.