Emergent Intelligence
By ai-depot | August 16, 2002
Optimizing the Ant System
Optimizing the Ants Colony
Genetic Algorithms provide an adaptive optimization technique based on the natural process of evolution. A population of individuals representing possible solutions for a given problem is submitted to the Darwinian principle of "survival of the fittest" over consecutive generations. The most successful individuals will propagate their characteristics through genes that will be recombined in the creation of new individuals. As the population evolves adapting to their environment through mutation and natural selection, better results can be obtained.
Since the agents are created at the beginning with random characteristics it is possible that they are not adapted to a specific environment and it could take too much time for a good result to emerge or they could even not find a solution. The performance of the system can be incredibly improved by applying the Genetic Algorithms concepts of selection, crossover, mutation.
The foundations of Genetic Algorithms such as selection, crossover and mutation can be better understood looking at the practical example we’ve been discussing.
Selection
competition: Successful individuals in this environment are those that can either collect a large amount of food (workers) or find alternative routes to the food source (explorers). By collecting food, an agent is increasing the pheromone level over a good route and thereby influencing other agents. By exploring the environment, an agent can find different and maybe shorter routes to the food source. Natural selection will allow these individuals to produce offspring and thereby propagate their characteristics. Similarly to the natural process, the evolution occurs because the new generation of individuals will sometimes be better then the parents.
extinction: Agents that get lost within the environment can not help at all. For example an agent that keeps traveling between two nodes using just one edge is useless to the colony. Also if it keeps walking in circles. These individuals will be eliminated from the population.
Offspring
crossover: New offspring are created based on the characteristics of the successful individuals. Since there are two types of individuals that are necessary to the colony, two new individuals will be created at each evolutive cycle. One of them will be descendant of the two most successful workers and the other one will be descendant of the best two explorers. Genes representing the characteristics of the parents will be combined to compose a new chromosome which will originate a new individual. This combination is inspired by the biological process known as crossing over. Each characteristic of the new individual will come from one of the parents at random. The following figure shows two possible examples of descendants created with crossover combinations:
mutation: After the crossover there is a low probability that a mutation occurs. This will change one of the characteristics of the individual at random. Mutation can maintain diversity within the population.
Migration
Migration will introduce a completely random new individual to the population. The effect is similar to the mutation because it will increase the diversity within the environment.
Implementation
The same topics will be covered considering now the implementation details which are very simple.
Selection
The most successful worker is the one that collected the most food. A counter will be added to the Ant class and will be incremented every time the agent reaches the nest bringing food. At each selection process, the agents with higher counter value will be considered the most successful. The agents will also need to count how many times they have been on the same route. Low values of this counter will indicate successful explorers while higher values will indicate agents that are lost in the environment.
Offspring
crossover: In order to perform a crossover operation, a new constructor will be added to the Ant class that will take two references to Ant objects as parameters. The new instance will be created by combinating the parents characteristics. Take a look at the following figure to see how the crossover can be implemented. A chromosome is composed of three genes representing one characteristic each. The new chromosome can be filled with zeros or ones with the same probability. For each gene, 0 means that the characteristic will be inherited from the mother and 1 from the father.
mutation: another method will be used to perform mutation. This method can be called after the crossover as an event with low probability to occur.
migration
A completely new individual can be created by assigning a random value to alfa, beta and gamma. This can be implemented as the default constructor of the Ant class.
After including the new properties and methods the Ant class should look like the one bellow:
class Ant
{
private:
float alfa; // Indicates the Ant’s pheromone sensibility
float beta;
float gamma;
bool HaveFood; // Indicates if the Ant is carrying food
int FoodCollected; // Amount of food collected by this Ant
public:
Ant(); // Default ctor: completely new individual
Ant(Ant *Father, Ant *Mother); // Crossover constructor
float GetTendency(int PheroLevel); // Evaluates tendency of choosing route
void PickFood(); // Pick food when in the food source
void LeaveFood(); // Leave food when in the nest
void PutPheromone(); // Increase pheromone level of route
void Walk(); // Walk one more step
void Mutation(); // Perform mutation
// interface and auxiliary methods and properties omitted:
// . . . (check full source code for details)
};
Tags: none
Category: tutorial |
