Ant System: Self Adaptation

• pheromone and cost sensitivities should vary during search:

  • avoid premature convergence;
  • speed up search considerably.

• Explorers encode sensitivity values:

  • fitness of encoding is cost of route;
  • new agents are created with and use genetically-manipulated values for route finding.

Previous slide

Next slide

Back to first slide

View graphic version

Each agent has its own cost and pheromone sensitivity. At the beginning, all the agents have random values. When an agent returns, its set of parameters is stored. Its parameters are linked to the cost of the path found. This cost will have the same role as the fitness function of a GA. When creating a new agent, the sets of all of the last returning agents is considered. An intermediate population of parameters is created: each set has a probability of being chosen proportional to its ftness. Random factors (mutations) are also added to the population.

Random fluctuations in range [-0.25, 3] for pheromone sensitivity; [-0.125, 1.5] for cost sensitivity. The negative values allow agents to flee the main trail and therefore explore new routes.

If the routes prove to be short, the parameter settings will be retained in the returning population. Otherwise, they will die away.

The adaptive system proved much more efficient than the static system. Routes which took up to 30 seconds to emerge, emerged in 2-3 seconds with adaptive settings.

This approach is somewhat different to a conventional GA in that in this algorithm we are trying to avoid convergence of the population because it tends to lead to local optima. It is, perhaps, closer to the work on co-evolving populations because the environment of the agents is modified by their actions.