Summery

This example shows how to implement the Tripod benchmark described by Maurice Clerc here. Be sure to check out the rest of his PSO page here. It's full of really great information.

This example also demonstrates how to set up a new Visual Studio project that uses TribesPSO.dll. This example will use Visual Studio C# 2010 Express which is available (for free!) from Microsoft. People familiar with Visual Studio can probably skip the first section of this example.

Set up a new Visual Studio project

Before you start, you'll need to install Microsoft Visual C# 2010 Express and a copy of TribesPSO.dll. This example uses revision 0.1 of TribesPSO.dll available in the downloads section. Once you have the prerequisites follow the following steps to create a new project:
  • Fire up Microsoft Visual C# 2010 Express and create a new project by clicking File->New Project...
  • For simplicity, create a console application. I am naming the project "TribesTripodBenchmark"
01 New Project.png
  • Click OK to create the project. This should create a new project containing a file called Program.cs
  • On the right in the Solution Explorer, right click on "References" and select "Add Reference"
02 Solution Explorer.png
  • In the Add Reference dialogue, select the "Browse" tab and navigate to TribesPSO.dll. Select TribesPSO.dll and press Ok
03 Add Reference.png
  • Finally, add "using TribesPSO;" to the top of Program.cs

When you're done, your Program.cs file should look something like this:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using TribesPSO;

namespace TribesTripodBenchmark
{
    class Program
    {
        static void Main(string[] args)
        {
        }
    }
}


We'll come back to Program.cs in a bit.

Implementing the Tripod Objective Function

TribesPSO does not include functions to minimize. Instead it provides an interface called IObjectiveFunction that allows us to specify our own problems to solve. The Tripod function will have to be coded so that it implements the IObjectiveFunction interface. We will then pass it to the constructor of the SearchSpace object in order to solve it. The function for the Tripod function is simple enough:
04 Tripod Formula.png
To implement the Tripod formula, we'll need to create a new file called Tripod.cs
  • Right click on the TribesTripodBenchmark project in the Solution Explorer
  • Select Add then New Item...
05 New CS File.png
  • Select in the Add New Item dialogue box select "Class" and set the name to Tripod.cs.
  • Click Add
  • Add "using TribesPSO;" to the top of the newly created Tripod.cs file.
  • Add ": IObjectiveFunction" after "class Tripod" to implement the IObjectiveFunction
  • Right click the text IObjectiveFunction and select "Implement Interface" then "Implement Interface" to have Visual Studio generate all of the methods and properties necessary to implement the interface. Alternatively, you can type them in yourself. Either way when you're done you should have something that looks like this:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using TribesPSO;

namespace TribesTripodBenchmark
{
    class Tripod : IObjectiveFunction
    {
        public int Dimensions
        {
            get { throw new NotImplementedException(); }
        }

        public double Evaluate(EuclidianVector position)
        {
            throw new NotImplementedException();
        }

        public EuclidianVector InitialGuess
        {
            get { throw new NotImplementedException(); }
        }

        public EuclidianVector MaxBounds
        {
            get { throw new NotImplementedException(); }
        }

        public EuclidianVector MinBounds
        {
            get { throw new NotImplementedException(); }
        }
    }
}

"throw new NotImplementeException();" is just a placeholder that will allow the code to compile but not run. We'll replace these stubs with actual functionality.

Dimensions

The Dimensions property tells the SearchSpace how many inputs there are to the function we're trying to minimize. For some functions this number could be anything depending on the complexity. For the Tripod problem there are only two inputs X1 and X2. Therefore the Dimensions property will always return 2.
        public int Dimensions
        {
            get { return 2; }
        }

MaxBounds

The MaxBounds property puts a maximum bound on where the default SearchSpace implementation places new particles. For the Tripod problem the max bound is X1 = 100 and X2 = 100. Implementing this property should look something like this:
        public EuclidianVector MaxBounds
        {
            get { return new EuclidianVector(100, 100); }
        }

MinBounds

The MinBounds property puts a minimum bound on where the default SearchSpace implementation places new particles. FOr the Tripod problem the min bound is X1 = -100 and X2 = -100. The implementation looks something like this:
        public EuclidianVector MinBounds
        {
            get { return new EuclidianVector(-100, -100); }
        }

InitialGuess

The InitialGuess property provides a way to make an initial guess at a problem. This can potentially speed up a minimization. For the Tripod problem we will not be providing an initial guess. Therefore this property can return null:
        public EuclidianVector InitialGuess
        {
            get { return null; }
        }

Sign(x)

Before we implement the Evaluate method, we should create a method that computes Sign(x). From the problem statement we see that Sign(x) = -1 for X <= 0 and 1 for X > 0. Implementing this method is easy:
        private double Sign(double x)
        {
            if (x <= 0) return -1;
            else return 1;
        }

Evaluate

Finally it's time to implement the Evaluate method. This method computes the value of the objective function at a point specified by the position argument. For the Tripod problem, X1 will be provided by position0 and X2 will be provided by position1. The implementation of the Evaluate method should look something like the following. I've broken it down into three steps for readability.
        public double Evaluate(EuclidianVector position)
        {
            double x1 = position[0];
            double x2 = position[1];

            double result = ((1 - Sign(x2)) / 2) * (Math.Abs(x1) + Math.Abs(x2 + 50));
            result += ((1 + Sign(x2)) / 2) * ((1 - Sign(x1)) / 2) * (1 + Math.Abs(x1 + 50) + Math.Abs(x2 - 50));
            result += ((1 + Sign(x1)) / 2) * (2 + Math.Abs(x1 - 50) + Math.Abs(x2 - 50));

            return result;
        }


That's it! Because we don't have any arguments that need to be passed into the Tripod constructor, we can let the C# compiler generate a default constructor for us. You can download the completed Tripod.cs here

Finishing Program.cs

In order to solve the Tripod problem, we need to fill in the Main method of Program.cs. This involves:
  • Creating a new instance of Tripod objective function
  • Creating a SearchSpace object
  • Calling MoveThanAdapt() on the SearchSpace object until we've found a suitably good solution OR have called MoveThanAdapt 10,000 times. My implementation looks like this:
namespace TribesTripodBenchmark
{
    class Program
    {
        const double maxError = .0001;

        static void Main(string[] args)
        {
            Tripod functionToSolve = new Tripod(); //Create a Tripod function to solve

            SearchSpace s = new SingleThreadedGaussianSearchSpace(functionToSolve); //Create a search space

            for (int n = 0; n < 10000; n++)
            {
                s.MoveThenAdapt();
                if (s.BestSolution.Error <= maxError)
                {
                    Console.WriteLine("Found solution {0} after {1} rounds", s.BestSolution.Position, n);
                    Console.Write("Press enter to exit");
                    Console.ReadLine();
                    return;
                }
            }

            Console.WriteLine("Did not find solution with error less than {0}", maxError);
            Console.Write("Press enter to exit");
            Console.ReadLine();
        }
    }
}


You'll notice that I'm using the SingleThreadedGaussianSearchSpace here. There are several implementations of SearchSpace provided by TribesPSO.dll. I'll go over the differences in a future example. Alternatively you're free to dive into the source code (which is fairly well documented) and look at the implementations for yourself.

You can get a copy of my Program.cs file here. The output should look something like this:
06 Output.png

Final Thoughts

This is toy example designed to show how to implement your own objective functions to solve. In reality you would want to run an optimization thousands or hundreds of thousands of times and collect statistics on how long the problem took to converge (if it converges at all!).

Below are some results after I modified the example program to count evaluations of the objective function. The optimization was run 10,000 times. It failed to converge in fewer than 10,000 calls to MoveThanAdapt() 82 times
07 Results.png

The default search space implementations are also taken almost verbatim from Maurice Clerc's paper "Tribes, a parameter free PSO" found on this page so the results have already been pretty well analyzed. In future examples I will show how to create particles that use your own movement strategy or how to create a new search space that uses a different adaptation strategy.

Please let me know if you have any questions or comments!

Last edited Jul 6, 2011 at 7:01 AM by pbaughman, version 22

Comments

No comments yet.