Author Archives: Robert Green - Page 2

Artificial Immune Optimization on the GPU using CUDA

Posted by on April 13, 2011 No comments

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

Downloads: PDF | Bibtex

[1] J. Zhao, Q. Liu, W. Wang, Z. Wei, and P. Shi, “A parallel immune algorithm for traveling salesman problem and its application on cold
rolling scheduling,” Information Sciences, vol. 181, no. 7, pp. 1212 – 1223, 2011.
[2] J. Li, L. Zhang, and L. Liu, “A Parallel Immune Algorithm Based on Fine-grained Model with GPU-Acceleration,” in Foruth International
Conference on Innovative Computing, Information, and Control, 2009, pp. 683–686.

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.

Particle Swarm Optimization on the GPU using CUDA

Posted by on March 21, 2011 3 comments

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.

Moore's vs. May's

Posted by on March 18, 2011 No comments

I just read Doublas Eadline's post at  Linux Magazine and found it really fascinating. The best tidbit to chew on is:

This is where all the hardware excitement meets the cold reality of parallel programming. We are all familiar with “Moore’s Law” (the transistor density doubles every two years). Many people have probably not heard of “May’s Law.” (for the purist, you can substitute “trend” for “law”). In any case, David May states his law as follows, “Software efficiency halves every 18 months, compensating for Moore’s Law.” Think about it. Every new generation of hardware

Moore's Law - The number of transistors on a chip doubles roughly every 2 years

May's Law - Software efficiency halves every 18 months, compensating for Moore’s Law.

Chew on that.

Clever Algorithms

Posted by on February 15, 2011 1 comment

An excellent new book available at http://www.cleveralgorithms.com/

Installing the MATLAB plug-in for CUDA in Ubuntu 10.04

Posted by on October 13, 2010 9 comments

I had previously installed CUDA and CUDA SDK on my computer running Ubuntu 10.04. Matlab is also installed on the computer, and some of the students are currently using libSVM for data classification research. One of the major problems that we are having is that the data sets are so large that libSVM is simply too slow to use. The solution - let's add cuSVM to the installation so they can speed up their code easily.

I planned on following the instructions here where the first step is "Download Matlab plug-in for Cuda (Version 1.1) from http://developer.nvidia.com/object/matlab_cuda.html". Along the way I decided that I would not only download the Matlab plug-in for Cuda, but that I would install and test it as well. Though, along the way I ran into a couple of issues. Here are the steps that I followed:

  1. Download the Matlab plug-in for CUDA and extract it
  2. Open the Makefile for editing
  3. Add a line at the very beginning of the file that specifies the current directory. In my example this is: 
    CWD=/path/to/my/home/directory/Matlab_Cuda_1.1
  4. If you are on a 64-bit system (as I am), make sure that line 6 reads as : 
    INCLUDELIB  = -L$(CUDAHOME)/lib64 -lcufft  -Wl,-rpath,$(CUDAHOME)/lib64
  5. Change line 11 (export Matlab=/usr/local/matlab) so that it matches your Matlab installation. In my case this was /opt/Matlab
  6. On lines 38, 45, and 52 you will find references to a script called nvopts.sh. When I first ran this Makefile, I continually got errors telling me that nvopts.sh did not exist. How to fix this? Add the correct path to the nvopts.sh reference. I did this by following the instructions in step 3 and then I adjusted lines 39, 46, and 53 to read as follows: 
    $(NVMEX) -f $(CWD)/nvopts.sh $(INCLUDEDIR) $(INCLUDELIB)
  7. Save the Makefile
  8. Open the file called nvmex
  9. Comment out lines 1448-1454. Just in case I have the line numbers slightly wrong, these lines read like this: 
    if [ "$compile_only" != "1" ]; then
    if [ "$gateway_lang" = "C" ]; then
    	files="$files $MATLAB/extern/src/mexversion.c"
    else
        files="$files $MATLAB/extern/lib/$Arch/version4.o"
    fi
fi

    and should now look like

    #if [ "$compile_only" != "1" ]; then
#    if [ "$gateway_lang" = "C" ]; then
#    	files="$files $MATLAB/extern/src/mexversion.c"
#    else
#        files="$files $MATLAB/extern/lib/$Arch/version4.o"
#    fi
#fi
  10. Save nvmex
  11. In the case that your paths are not set properly (mine are not) open up nvopts.sh. Make sure that the call to nvcc on lines 56, 87 and 164 are set correctly. I changed these from 
    CC='nvcc'

    to

    CC='/usr/local/cuda/bin/nvcc'
  12. Save nvmex
  13. Open the terminal in the directory where your Makefile is and type 'make all'. Enjoy!

NS-2 and Classifiers

Posted by on September 29, 2010 2 comments

I am currently adding a custom classifier to NS2 for some research. To start, I thought that I would build a small model and install a classifier just to see how things worked. Easy? No, nothing with NS2 is easy, simple, or clean (at least this is the impression that I am left with). I started with a section of code that looked like:

#Create two nodes
set n0 [$ns node]
set n1 [$ns node]
set n2 [$ns node]
 
set clsfr [new Classifier/Hash/Dest 32]
set rm1 [new RtModule/Base]
$n1 insert-entry $rm1 $clsfr
 
#Create a duplex link between the nodes
$ns duplex-link $n0 $n1 1Mb 10ms DropTail
$ns duplex-link $n1 $n2 1Mb 10ms DropTail
 
#Create a UDP agent and attach it to node n0
set udp0 [new Agent/UDP]
$ns attach-agent $n0 $udp0
 
# Create a CBR traffic source and attach it to udp0
set cbr0 [new Application/Traffic/CBR]
$cbr0 set packetSize_ 500
$cbr0 set interval_ 0.005
$cbr0 attach-agent $udp0
 
#Create a Null agent (a traffic sink) and attach it to node n1
set null0 [new Agent/Null]
$ns attach-agent $n2 $null0

Apparently the problem with this code is the order in which things are added. If you run this code, the following error (or something similar will be produced):

--- Classfier::no-slot{} default handler (tcl/lib/ns-lib.tcl) ---
	_o19: no target for slot -1
	_o19 type: Classifier/Hash/Dest
content dump:
classifier _o19
	0 offset
	0 shift
	2147483647 mask
	0 slots
	-1 default
---------- Finished standard no-slot{} default handler ----------

This error is a common error in NS2 that appears to be cause because things are not connected correctly. The problem with the above example is that the nodes are not properly connected before the new routing module and classifier are added. The proper implementation should look like:

#Create two nodes
set n0 [$ns node]
set n1 [$ns node]
set n2 [$ns node]
 
#Create a duplex link between the nodes
$ns duplex-link $n0 $n1 1Mb 10ms DropTail
$ns duplex-link $n1 $n2 1Mb 10ms DropTail
 
set clsfr [new Classifier/Hash/Dest 32]
set rm1 [new RtModule/Base]
$n1 insert-entry $rm1 $clsfr
 
#Create a UDP agent and attach it to node n0
set udp0 [new Agent/UDP]
$ns attach-agent $n0 $udp0
 
# Create a CBR traffic source and attach it to udp0
set cbr0 [new Application/Traffic/CBR]
$cbr0 set packetSize_ 500
$cbr0 set interval_ 0.005
$cbr0 attach-agent $udp0
 
#Create a Null agent (a traffic sink) and attach it to node n1
set null0 [new Agent/Null]
$ns attach-agent $n2 $null0
 
#Connect the traffic source with the traffic sink
$ns connect $udp0 $null0

Essentials of Metaheuristics

Posted by on August 10, 2010 No comments

For anyone who is interested in learning the basics of metaheuristics in a concise and clear manner, I suggest that you check out Sean Luke's Essentials of Metaheuristics.

Omnet++ 4.1, MiXiM, and IEEE 802.15.14

Posted by on July 12, 2010 2 comments

If anyone is having trouble compiling (no makefiles) or finding (not in the downloaded source) the IEEE 802.15.14 examples that go along with MiXiM like I did, I suggest the following steps:

  1. Check out the source using the command 
     svn co https://mixim.svn.sourceforge.net/svnroot/mixim mixim
  2. Move the contents of the trunk directory into the omnetpp-4.1/samples/MiXiM/ directory
  3. Change directories to omnetpp-4.1/samples/MiXiM/examples/ieee802154Narrow
  4. Build the project using the command 
    opp_makemake -f -O out -L../../out/gcc-debug/base -L../../out/gcc-
debug/modules -L../../out/gcc-debug/tests/testUtils -lmiximbase -
lmiximmodules -I../../modules/utility -I../../base/messages -I../../
base/utils -I../../base/modules -I../../base/phyLayer -o
ieee802154Narrow
  5. Change directories to omnetpp-4.1/samples/MiXiM/examples/ieee802154A
  6. Build the project using the command 
    opp_makemake -f -O out -L../../out/gcc-debug/base -L../../out/gcc-
debug/modules -L../../out/gcc-debug/tests/testUtils -lmiximbase -
lmiximmodules -o ieee8021514a

Now everything should work!

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.