Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Nicolaus Correll

Division of Labor
Division of labor takes place in three different forms


  1. Temporal polyethism The behavior of an individual is a function of it's age. Groups of similar age perform the same tasks.
  2. Worker polymorphism The behavior of an individual is a function of its morphology, morphologly similar individuels perform the same labor.
  3. Individual variability Groups that perform a task out of a set of tasks together at the same time make up a behavioral caste.


Plasticity of labor division arises from response thresholds on stimuli, which are either related to the labor itself or given by environmental conditions (i.e. temporal polyethism). If the stimuli exceeds a certain threshold, the individual switches its behavior.
The response threshold for a certain action can also be coupled with the action with a positive or negative feedback mechanism.
Posted by Nicolaus Correll at 19:06
Ant Based Control (Schoonderwoerd)
In the ABC algorithm a number of agents called ants are continouisly exploring the graph of a telephone network from random starting points to random destinations. Here, nodes in the graph (switching points) have limited capacity and will reject calls if they are overloaded.
After the ants arrival at the destinations, the chosen route becomes reinforced as a function of its "length" (number of hops). This reinforcement is in turn used by the ants to probabilisticly a suitable route to their destination of choice.
Routing tables built up in this way can then be exploited by calls that deterministically choose the route with the highest value. Hereby, the capacity limit of every switch-board on its route is decreased, making this connection less favorable for passing ants.
Posted by Nicolaus Correll at 17:12
ACS for the TSP
Ant Colony System (ACS) for the Traveling Salesman Problem (TSP)

Local pheromone update: While in AS the pheromone level on the graph is only increasing (except for evaporation), ACS explicitly diminuishes the pheromone level on every edge that is part of a tour. By this, exploration of unvisited edges is favored, and the side-effect of positive feedback that all ants stagnate on a poor initial solution reduces.

Transition rule:Different to Ant System (AS), ACS allows for tuning the rate between exploration and exploitation not only via the exponent of the heuristic (distance) and pheromone metric, but by introducing an explicit random choice between favoring the best known choice, and a probabilistic decision as in AS.

Pheromone trail update and candidate list: In contrast to AS where all ants are allowed to deploy pheromones, in ACS only the best ant of an iteration is allowed to deploy a pheromone. Also, ants are bound to choose from a limited set of neighboring cities that has been initially determined on heuristic information, for instance by choosing only n nearest cities as candiates.

In AS, the latter two improvements are picked up by Elitist AS, and maintained in Rank-Based AS and Max-Min AS.
Posted by Nicolaus Correll at 16:49
AS for the TSP
The AS algorithm can be described as follows:

  • A tour of a single ant includes every city of the TSP only once
  • During tour construction the ant chooses the next city based on a probability which is anti-proportional to the distance to the next city, and proportional to the amounts of pheromones already deployed on this path.
  • At the end of each tour, pheromones are deployed anti-proportional to the length of this tour

After every iteration (a number of ants each perform a whole tour), local search might be applied to optimize the solution.
Posted by Nicolaus Correll at 16:21
Stigmergy
Stigmergy describes coordination among individuals by communication via modifications of the environment. Here, positive feedback or triggering of behavior can be induced by a modification of the environment that was performed by

  1. The individual itself
  2. Another member of the swarm

Note that an environmental modification can also be due to perturbations of the environment.
Posted by Nicolaus Correll at 15:39
Self-Organization
Self-Organization

  1. Positive Feedback: successful actions lead to recruitment, which again yield into successful actions and thus further reinforcement.
  2. Negative Feedback: counterbalances positive feedback and limits the exponential growth induced by positive feedback by saturation, exhaustion, or competition.
  3. Exploitation and exploration: noise is a necessary condition in self-organizing systems for not only exploiting positive and negative feedback but also exploring other system states randomly.
  4. Multiple interactions: individual states are not only dependent on previous states but also on the state of other individuals.

One ore more of these basic ingredients usually yield to a system showing the following properties:

  1. Emergence of spatial/temporal patterns
  2. Multi-stabile systems
  3. Bifurcations for changes in the system
Posted by Nicolaus Correll at 15:30
Quadratic Assignment
A library of some quadratic assignment problems (QALIB) can be found here

http://www.opt.math.tu-graz.ac.at/qaplib/inst.html

For a better understanding of the quadratic assignment problem there exist some Java applets on this page

http://www-unix.mcs.anl.gov/otc/Guide/CaseStudies/qap/
Posted by Nicolaus Correll at 18:14