See also: Particle swarm optimization for function optimization

A short introduction to my idea of improving the algorithm  - further studies have to be done before a full-article can be provided.

The general rule for updating the particles velocity is:

In the literature two options are common:

• gBest is the current best solution of the swarm or
• gBest is the best solution the swarm found so far

The latter lets the algorithm converge faster but the possibility to get stuck (or trapped) in a local optimum raisen. The first option is the classic approach and the exploration of the search-space is higher.

In my proposed improvement there’s added another term in the equation for updating the velocity:

In this formula c3 is the acceleration coefficient giving the tendency to follow the best solution found so far – aBest (absolute Best), r3 is a even distributed random number in the interval 0 to 1 and x the current position. When c3 = 0 the term vanishes and so the equation is equal to the general rule. c3 = 1 & c2 = 0 goes to the second option. Therefore it’s possible to take the advantages of both option into account. Starting with c3 = 1 to converge fast in the first iterations and then decrease c3 towards 0 so the exploration increases, thus avoiding getting stucked in local optima.
For a static approach I suggest to choose c3 = 0.5.

As mentioned above further investigation have to be done – I’m going to post updates until the article is ready.

 

Happy coding

As promised in the previous post I've writte an article at codeproject: Particle swarm optimization for function optimization

There exists other fascinating algorithms for optimizing functions such as:

• ant colony optimization (discrete problems)
  
• genetic algorithms (continous and discrete problems)
  
• simulated annealing (continous and discrete problems)
• great deluge algorithm (continous and discrete problems)
• artificial immune system (similar to a genetic algorithm)
  

If picked out of these the particle swarm because for me it's really impressive to watch the particles exploring the search space - hey it's artificial life ;)

On performance considerations simulated annealing is my favorite.
 It's so fast that I can't provide a video for minimizing functions. But when you're familiar to the traveling salesman problem than you know how long the classic combinatorial approch takes. When a computer would take one hour for 30 cities then it would take 40 days for 32 cities. Incredible that a computer needs so long. Watch the video and see how simulated annealing finds the solution for 500 (yes really 500) cities within seconds. I haven't used the classic simulated annealing algorithm, but instead an improved version of mine. Therefore I won't show the code right now - maybe later, now it's may baby ;)
  

The next video shows the same problem - but wiht 100 cities only - with a genetic algorithm (GA) on the left side and simulated annealing (SA) on the right side. You may wonder why SA is by times faster than the GA. The most obvious reason is that SA uses one solution-vector whereas GA uses on vector for each chromosome. A the population used consists of 1000 chromosomes. Thus the GA needs to store 1000 times the solution vector which reduces the speed. When compared by iterations/generations the GA is the one that needs less cycles. Oh, I've stuck to writing - now the video...
  

I can't promise but I've planned to produce a series of posts concerning computational intelligence. Coverd will be:

• evolutionary algorithms
• other meta heuristic approches
• neural networks
• training of neural networks

Hoping that I find time to do this.


Happy coding

While playing around with particle swarms I've created a small application that visualizes how the swarm searches for a global minimum in function R² -> R. It fascinated me looking on the behaviour of the artificial swarm.

The video shows how a particle swarm searches for the global minimum. Every yellow dot is a particle and the red dot shows the global minimum found so far.
The function plot colors  high values in red while low values are blue. So the swarm should find the global minimum in a deep blue region. Severel cycles are shown.

Unter http://www.mycsharp.de/wbb2/thread.php?threadid=75886 führe ich eine interessante Diskussion (oder Monolog? ;) über die Performance von C# im Vergleich mit Fortran 95.

Weiterführende Betrachtung basierend auf diesem Artikel sind in Thomas Enzinger's blog zu finden.

Happy coding ;)