Genetic Algorithms with AjAgents and Concurrency and Coordination Runtime (CCR)

9 Replies

In previous post, I wrote about my C# example AjAgents:

Agents using Concurrency and Coordination Runtime (CCR)

and about some ideas to explore:

Agents in a Grid

Now, I extended my example AjAgentsCCR-0.1.zip implemented two new projects. One is a console project AjAgents.Genetic01, and the other is WinForms onw, AjAgents.WinGenetic01:

The basic idea is to run a genetic algorithm using agents, that send messages using CCR ports. Then, each agents process its incomming messages, and post outcomming message to other agents, in a “parallel” way. The problem I modeled is the classical Travelling Salesman Problem. According to Wikipedia:

If a salesman starts at point A, and if the distances between every pair of points are known, what is the shortest route which visits all points and returns to point A?

The Windows form is simple:

The Genoma class represents the travel (a list of Points and a distance value):

    class Genoma
    {
        public List<Point> travel = new List<Point>();
        public int value;
    }

    class Point
    {
        public int x;
        public int y;
    }

But the interesting point, is the lunch of the run. First, the agents are created and connected:

            best = new BestSoFar();
            evaluator = new Evaluator();
            mutator = new Mutator();
            collector = new Collector();

            evaluator.Collector = collector;
            collector.Mutator = mutator;
            collector.Evaluator = evaluator;
            collector.BestSoFar = best;
            mutator.Evaluator = evaluator;

Then, a initial genoma is created:

            Genoma genoma = new Genoma();
            Random rnd = new Random();

            for (int k = 0; k<40; k++)
                {
                    Point pt = new Point();
                    pt.x = rnd.Next(12);
                    pt.y = rnd.Next(12);

                    genoma.travel.Add(pt);
                }

            genoma.value = evaluator.CalculateValue(genoma);

The BestSoFar agent can raise an event. The form is listening to that event, to refresh the best travel drawing. The program sends the genoma to the mutator agent, many times:

            best.NewBest += BestGenoma;

            for (int k = 0; k < 60; k++)
            {
                mutator.Post("Mutate", genoma);
            }

Note the use of the Post method. Every agent implements that method, that invokes a method in the agent, but using a CCR port to invoke the target method. So, the method is executed in a “parallel way”, possibly in a thread from the CCR thread pool.

A simple diagram to explain the interactions between the agents:

The mutator sends each genoma to the Evaluator. This agent calculate the value assigned to that genoma. Then, it sends the genoma to a Collector. This is a new idea, for this example: instead of having a population class, the collector receives genomas, and then when it has n or more, evaluates the best ones, and post them to a Mutator, so the process continues. There is no population concept, or, at least, not the standard population found in other implementations. The best genoma detected by the Collector is informed to the BestSoFar agent. A typical method, from Collector class:

        void ProcessList(List<Genoma> list)
        {
            list.Sort(comparer);

            bestsofar.Post("Process",list[0]);

            evaluator.Post("Evaluate",list[0]);
            evaluator.Post("Evaluate",list[1]);

            for (int k = 0; k < 4; k++)
            {
                mutator.Post("Mutate",list[k]);
                mutator.Post("Mutate",list[k]);
            }
        }

I must improve the genetic algorithm. Now, it’s using only mutation, and it has no crossover operator. Then, its result is not optimal: it can reach a local minimum, but it could not be the best solution. But the basis of this example, is to show how AjAgents and CCR can be used in an “proof of concept” example.

Conclusions

One can see each agent as a “little cell” or “little organism” that reacts to incoming messages, and sends outcomming messages to other agents. Each agent is loosly coupled with the others. In these examples, the agents were created by code, but it’s clear that they could be created and related using dependency injection frameworks, as Spring.NET or the new Unity Application Block from Microsoft.

Instead of using only CCR ports, I could write the agents as DSS Service components (see Microsoft Robotics Studio for more information), so the algorithm could be “gridified”, and each agents is located in a transparent way to others.

But this is another story….;-)

Incidentally, yesterday this post announced the new version of Microsoft Robotics Developer Studio 2008:

http://blogs.msdn.com/msroboticsstudio/archive/2008/04/09/microsoft-robotics-developer-studio-2008-ctp-april-available.aspx

The third new feature, mentioned in that post, could be a great feature for these ideas about “miniagents”:

Support for creating applications that run on multiple DSS nodes using Visual Programming Language and DSS Manifest Editor. This makes it much simpler to create applications that run across nodes, either on the same machine or across the network. When an application containing multiple nodes is to be started, VPL creates individual deploy packages for each node and fires them up across the network.

Ooooohhh!…. 😉 😉

Angel “Java” Lopez
http://www.ajlopez.com/