Category: Evolution

WCCI (CEC) 2006 Invited Talk:
Coevolutionary Learning by Melanie Mitchell

This invited talk is about making better learning systems. The idea is evolving both “classifier” and “training set” together (co-evolving them in a competitive setting). The way that this works well is by spatial co-evolution. This “spatial” property is very important and other cases (non-spatial co-evolution or spatial evolution) did not work well. However, I should note that none of the experiments was about real classifier. One of them is designing a cellular automata to do some specific task (majority voting) and the other is fitting a tree-like structure (actually a GP tree) to some function.

She thoughts that spatial Co-evolution improves performance because:
-maintain diversity in population
-produces “arm races” with ICs targeting weaknesses in CA and CAs adapting to overcome weaknesses.

Also you may like to read a quotation. This is one for you: “Co-evolution is all about information propagation!”

Finally I asked her if it is reasonable to evolve training set for a classification task? By evolving them too, the pdf of the training set will changed, and this means that the evolved new samples may be completely different from the pdf of the test set, i.e. the classifier evolved in a way to optimize a loss function for a distribution other than “population” (or test or true) distribution.
She answered me, I did not satisfied completely by her answer.

Now, I am sitting in this big Pavillion Ballroom waiting for Marco Dorigo to start his presentation. He is going to talk about “Self-Assembling in Swarm Robotics: The Swarm-bot Experiment”.

His group has built swarm-bots (s-bots). S-bot are small robots than can connect to each other and do things that a single robot cannot do.

The technological motivation for this work is: Robustness, Flexibility, Scalability

s-robot are 12cm.
Also I found out that Khepera is pronounced as Kepera.

The simulator they developed has different levels of abstraction as the model of the robot. One important problem for them was selecting the right level of complexity for the simulation of their robot.

To design robots’ controllers, they either hand-coded behavior-based system or evolved a neural network to do so. They did all designing in the simulator and then downloaded the result to the real robot.

The evolved a NN to do collective movement of a swarm of s-bots.
They used Perceptron and evolved their parameters using a simple ES method.
I missed (or maybe it is not mentioned) the observation space of the NN.

It seems that the resulted controller can work in different situations. For instance, it is scalable, can do coordinated movement with different initial formation of robots and etc.

Then they tried to evolve a controller for more complex tasks such as hole avoidance. They used a ground-hole detector for each robot and also a microphone to detect sounds. The action space is motion AND some sound. This sound can be used to communicate with other robots.

Path Formation:

On going work:
-Functional self-assembling
-Functional shape formation
-Adaptive task allocation
-Evolution of recurrent neural nets for memory …

Finally, I asked about using ideas of learning (RL). He said that the main reason that they did not test it is the lack of resources (as each experiment takes a lot of time).
After the talk, I asked about the comparison of the reinforcement learning and evolutionary approach to design autonomous agents. He said that the main problem is that nobody is going to really compare different methods in the same robotic task because it is time-consuming (and people in the field are lazy (these are my words!)).

Well … I liked the talk. It was fun. More importantly, I really impressed by the results.

You may get more information the project’s website: Swarm-bots

A week ago, I tried some simple idea of what is called Memetic Algorithm with my friend, Ali Reza. He is working on Vehicle Routing Problem (VRP) for his MS thesis (industrial engineering) using evolutionary techniques. I told him about MA and its benefits; he became eager about the approach; we find a computer and we implemented a local search to put in the [cultural] evolution cycle. My local search was something like this:

Suppose that we have a route specified by R: c(1)c(2)…c(n) in which c(i) is the index of the ith city (or delivery position). I suggested this simple search:

For every position in the sequence, swap two adjacent cities and calculate the fitness, i.e. R: …c(i-1)c(i)c(i+1)… —> R’: …c(i-1)c(i+1)c(i)… and comparing f(R’) and f(R). If this change was better, accept it as the new individual.
This is very simple and I dare to say it is really mine. I guess someone might discovered (or used) this heuristic in their combinatorial optimization problems. However, I am not aware of such a search. Is there any in the literature?

We did not test it very much on many different problems. We have tested it in a single problem two or three times and in all cases, we got a better results comparing simple genetic algorithm. How much better?! I don’t know what amount is significant in this problem, but we reached (~)8.5 score when simple GA reached 9.5-10.

All of these has been done in less than an hour!

Mmm … As I told before, I do not believe in this type of interpretation of meme. However, I have tested it too!

I read a few papers on Memetic Algorithms recently. The idea of meme as a unit of information that reproduces itself as people exchange idea is very interesting to me. When I review the brief history of my though during these recent years, I found out that I had a similar idea about 4 years ago: an ALife setting in which individual learns and then transfer their knowledge to each other when they become close (I always like spatially-extended ALife creatures that can move in the environment). However in my opinion, the idea of meme is somehow misused or biased in the evolutionary computation community. Most of them interpret a meme as a hybridization of local search and a genetic global search. In other words, most researchers use a kind of local search after (or before) each genetic operator they made. Of course, there are many variations in the exact implementation – but most of them are actually doing so. What is the root of this trend? I am not sure, may be it is due to Moscato’s paper that shaped a new paradigm and getting out of it is difficult. But, I think it comes from this interpretation of meme: when people get idea, they change it during their lifetime, and then transfer it to others. Traditional genetic search does this transfer, but does not include a piece of “lifetime adaptation”. They interpreted this lifetime adaptation as a kind of local search and most of them followed a Lamarckian approach as “memes must be changed during its life in the individual”.
Well … I will write more about memetic algorithms.

(*): This quotation is actually a meme. Many papers refer to it when they want to define a meme. I guess only a few people actually read the Dawkins’ book. One of them is me!

Suppose that there are two populations A and B in the environment. Each population tries to evolve in order to increase its fitness which is coupled to the behavior of the other population, e.g. the performance of hunter is highly dependent on the performance of the prey. However, when A increases its fitness, B evolves in order to become fitter and then the fitness of A is not the same as before as the fitness landscape of it is highly dependent on the others’ policy. This (or something similar to this) is called Red Queen effect in co-evolutionary systems. There are many arguments about its definition and even the usefulness to consider it which you may read here.
I am not expert in co-evolution and I am not aware of the existence of the analyses regarding the dynamics of the co-evolutionary mechanisms (of course, there must be!); however, when I thought about Red Queen effect, I found this idea interesting:

We may analyze the co-evolutionary mechanism in the game theoretic framework. Red Queen effect is like not becoming stable to the Nash equilibrium in the game theory. As we do not know the model of the world (Payoff matrices and stochastic game transition probabilities) in a co-evolutionary setting, we may take a look at similar work in multi-agent reinforcement learning literature and get some inspiration. If we define rational and convergent properties as Bowling defined, we may say that the common implementation of co-evolutionary mechanism that leads to Red Queen effect is like using simple Q-learning (rational/non-convergent) in multi-agent learning. Not let we use something like Minimax-Q or Variable Learning rate Q-learning for co-evolutionary process in order to suppress the Red Queen effect.
Moreover, looking from another perspective (again game theoretic): An agent with Pure strategy may not have a Nash equilibrium but if it follows a Mixed strategy, it has. An individual in a population is certainly doing a pure strategy in most cases. What about evolving a set of strategies choosing randomly between them (evolving PDF too) to imitate evolving to a mixed strategy?!
Hmmm … don’t kill me if it is far from reality! I use my weblog exactly for this kind of conversations! Any idea about them or citing similar ideas? (I searched a little and found that R. Paul Wiegand have done some researches in this area. He used game theory to analyze the problem. I must see what he did.).

A really good news for the blogosphere is blogging of IlliGal members. IlliGAL is the genetic algorithm lab. of Illinois university in which David Goldberg is doing research and many good EC researchers have done their research in it, e.g. Erick Cantu-Paz and Martin Pelikan are from those that I know. Read their fantastic IlliGAL weblog.