7 February 2005
(category : Teaching)
Division of labor takes place in three different forms

Temporal polyethism The behavior of an individual is a function of it's age. Groups of similar age perform the same tasks.

Worker polymorphism The behavior of an individual is a function of its morphology, morphologly similar individuels perform the same labor.

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
(category : Teaching)
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 switchboard on its route is decreased, making this connection less favorable for passing ants.
Posted by Nicolaus Correll at
17:12
(category : Teaching)
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 sideeffect 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 RankBased AS and MaxMin AS.
Posted by Nicolaus Correll at
16:49
(category : Teaching)
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 antiproportional 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 antiproportional 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
(category : Teaching)
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
 The individual itself
 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
(category : Teaching)
SelfOrganization
 Positive Feedback: successful actions lead to recruitment, which again yield into successful actions and thus further reinforcement.
 Negative Feedback: counterbalances positive feedback and limits the exponential growth induced by positive feedback by saturation, exhaustion, or competition.
 Exploitation and exploration: noise is a necessary condition in selforganizing systems for not only exploiting positive and negative feedback but also exploring other system states randomly.
 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:
 Emergence of spatial/temporal patterns
 Multistabile systems
 Bifurcations for changes in the system
Posted by Nicolaus Correll at
15:30
10 January 2005
(category : Teaching)
A library of some quadratic assignment problems (QALIB) can be found here
http://www.opt.math.tugraz.ac.at/qaplib/inst.html
For a better understanding of the quadratic assignment problem there exist some Java applets on this page
http://wwwunix.mcs.anl.gov/otc/Guide/CaseStudies/qap/
Posted by Nicolaus Correll at
18:14