Porting the Particle Swarm
I had an idea that I might do something with particle swarm optimization .. another of the “nature inspired” pantheon of randomized algorithms which explore the possible solution space in a semi-greedy manner .. always the trade-off that : greed versus patience and investment (even if we are only talking computer cycles). And I thought differential evolution might do something for me too .. possibly it still will. The application has something to do with optimum positioning of labels in a 2D/3D visualization.
I won’t bore you with the algorithmic details. If you know the area (scatter search, squeaky wheel optimization, tabu search, simulated annealing and the dreaded genetic algorithms) then you will know what I am talking about - otherwise do a bit of googling on particle swarms and why swarms are not flocks and you will have a good time.
Now my point is porting. And OOP. And whether there really is a way forward, and whether legacy code should have a silver stake driven through its heart
These algorithms PSO (Particle Swarm Optimization) and DE (Differential Evolution) are usually touted as “simple - just a few lines of code”.
Yes, well we have all been there and done that, haven’t we?. It’s such a simple algorithm that we/you can do it in your sleep, right? Yeah, right. Reminds me of the first time I implemented a multidimensional scaling algorithm (”just a few lines of code”)
But being ever optimistic, I found me some code - a more or less standard PSO (Particle Swarm Optimization) implementation in C. Why C one might ask?.. or Fortran for that matter?
And why are modern algorithms being implemented in Dead Languages?
And it is 12 TWELVE pages of code. Of which 90% is either housekeeping or workarounds for the language deficiencies.
So, I thought I would port it from C to maybe Delphi or C#. With the aid of a language translation tool. Like C2Pas or somesuch.
yeah, in your/my dreams
I guess you know it didn’t work?
Well, you’d be right.. a half a dozen tools just made a mess of it. Nothing compilable, nothing remotely approaching compilable. Nothing sensible, nothing that if I could have got a working exe out of it would I have had any confidence in at all.
So, What am I Gunna Do?
Simple. An Informed and Literate Complete Rewrite. In a Living Language
The algorithm is good. The Quick Fix isn’t. A bit of thought and an elegant rewrite that puts all the housekeeping and service classes out of sight and out of mind, and we will be back to where we started.
James Kennedy said,
December 25, 2007 @ 11:23 pm
The code you are complaining about comes from the very first paper ever written on the topic, more than ten years ago. It has some historical value to researchers, in that it shows how far the field has progressed since those primitive times. It was not posted on the Internet to provide source code to anyone.
There are plenty of people doing current research with particle swarms, coding it in every language from Python to C++ to Java to SAS and Matlab. In a perfect OO world we could grab objects and connect them to our system and they would work; it is likely that you could find such objects on the Internet for particle swarms. Your annoyance here though is unjustified. The paper you linked to was one that introduced the research community to a new algorithm, within weeks of its discovery, and the algorithm has undergone important refinement and revision since then. You should have spent a little effort to search for what you wanted, instead of complaining that the first thing you found didn’t work for you.
Jim Kennedy
John Aitchison said,
December 26, 2007 @ 8:38 am
Fair enough. Please accept my apologies for any offense.
In my defense, let me say that there was no annoyance with the paper nor any attempt to “diss” the algorithm, and my post was directed at the unsatisfactory nature of porting as opposed to rewriting, and an element of frustration in having to wrestle with C.
The code that I was “complaining about” was actually the “Standard PSO 2006″
http://www.particleswarm.info/Standard_PSO_2006.c . As its function is to act as a “reference standard” for researchers, there is certainly a justification for coding it in C.
http://www.particleswarm.info/ says
I did do some research for an appropriate Delphi version and only found one commercial product, and several papers that said that they had implemented the PSO algorithm in Delphi (but no readily accessible code). A quick search for PSO in C# was unproductive. As you say there are matlab versions.
For others reading this post, there is a listing of some of the PSO software here.
http://www.particleswarm.info/Programs.html (note the .info TLD).
Also the PSO homepage is at http://www.cis.syr.edu/~mohan/pso/http://www.cis.syr.edu/~mohan/pso/
If I get the Delphi version going, anyone who is interested can contact me for a copy - but be aware it will not look much like the “standard” , because of the nature of the languages.
John Aitchison said,
December 27, 2007 @ 11:55 am
For those interested in PSO (Particle Swarm Optimization) and DE (Differential Evolution), you might be interested in visiting this site
Experimental and Agent-Based Computational Economics
http://www1.webng.com/economics/
Amongst other material there ..
1. Global Optimization by Differential Evolution and Particle Swarm Methods: Evaluation on Some Benchmark Functions
2. Construction of Composite Indices -Alternatives to the Indices Obtained by the Principal Components Analysis
3. Computing the Nearest Correlation Matrix from a given Invalid Correlation Matrix
Sandro Saitta said,
February 24, 2008 @ 11:32 pm
Regarding global optimization, an interesting algorithm is the one developed by Raphael and Smith in 2003 in our lab: PGSL (Probabilistic Global Search Lausanne)
John Aitchison said,
February 26, 2008 @ 7:24 pm
Thanks, I had a look at PGSL .. for those interested it is at
http://itc.scix.net/data/works/att/w78-2000-708.content.pdf
and
http://www.geocities.com/bennyraphael/PGSL/PGSL4.html (including a link to the C source)
Interestingly, it claims to work very well on problems involving large numbers of variables.