Self-organizing algorithms
Márk Jelasity, Spring Semester, 2009, Szeged, Hungary
Introduction|
Emergence of Paths, Ant Colony Optimization|
Division of Labor, Task Allocation|
Evolution, Stochastic Optimization|
Complex Networks|
PageRank
Reading
Papers for presentations
Abstract
Self-organization refers to the process, when a property of a system
emerges from the simple and local interaction of a large number of
components.
Examples include the morphological development and regeneration of
multicellular biological organisms, path creation and task allocation
in social insects, market mechanisms, and so on.
Most importantly, these systems are not designed or controlled in a
top-down manner by some external entity such as an agent or template.
Instead, they are based on internal, bottom-up mechanisms.
These bottom-up self-organizing mechanisms are interesting from an engineering
point of view, because they often make
it possible
to both increase the robustness and scalability of systems compared
to central control, and also to greatly simplify the components of
the system reducing the cost of deployment.
Besides, central or hierarchical control is often simply not an option due
to the inherent decentralization of a system.
Examples include sensor and mobile ad hoc networks.
During this course we will look at a number of ideas that can be
considered a promising source of new algorithms, mostly for
decentralized and networked systems, that achieve self-organization.
We will mainly look at biological inspiration reviewing topics
from swarm intelligence and evolutionary computing, but we also
discuss related topics such as complex networks and importance
ranking.
Lecture slides
Reading material
- Scott Camazine,
Jean-Louis Deneubourg, Nigel R. Franks, James Sneyd, Guy Theraulaz, and Eric
Bonabeau.
Self-Organization in Biological Systems, chapter 13, pages
217–255.
Princeton University Press, 2001.
- Eric Bonabeau, Marco
Dorigo, and Guy Theraulaz.
Swarm Intelligence: From Natural to Artificial Systems, chapter 2,
pages 25–107.
Santa Fe Institute Studies in the Sciences of Complexity. Oxford University
Press, 1999.
- Mitchel Resnick.
Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel
Microworlds, chapter Artificial Ants, pages 59–68.
Complex Adaptive Systems. The MIT Press, 1997.
Reading material
Reading material
- Hans-Georg Beyer and
Hans-Paul Schwefel.
Evolution strategies: A comprehensive introduction.
Natural Computing, 1(1):3–52, 2002.
(doi:10.1023/A:1015059928466)
- B. Freisleben and P. Merz.
A genetic local
search algorithm for solving symmetric and asymmetric traveling salesman
problems.
In Proceedings of IEEE International Conference on Evolutionary
Computation (ICEC'96), pages 616–621, Nagoya, Japan, 1996.
(doi:10.1109/ICEC.1996.542671)
- Thomas S. Ray.
Evolution, ecology, and
optimization of digital organisms.
Technical Report 92-08-042, Sante Fe Institute, 1992.
Large and distributed self-managing systems inevitably involve complex
networks, either explicitly designed, or unexpected (emergent),
if the system is not centrally controlled.
We review some of the basic models of complex networks and their main
properties.
Reading material
- Réka Albert and Albert-László Barabási.
Statistical mechanics of
complex networks.
Reviews of Modern Physics, 74(1):47–97, January 2002.
- R. Milo,
S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and U Alon.
Network motifs: Simple building blocks of complex networks.
Science, 298:824–827, 2002.
- Mark E. J. Newman.
Random graphs as models of
networks.
In Stefan Bornholdt and Heinz G. Schuster, editors, Handbook of Graphs
and Networks: From the Genome to the Internet, chapter 2. John Wiley,
New York, NY, 2002.
- Jon Kleinberg.
The small-world
phenomenon: An algorithmic perspective.
In Proc. 32nd ACM Symposium on Theory of Computing, 2000.
Also appears as Cornell Computer Science Technical Report 99-1776 (October
1999).
(doi:10.1145/335305.335325)
Lecture slides
Reading material
- Scott Camazine,
Jean-Louis Deneubourg, Nigel R. Franks, James Sneyd, Guy Theraulaz, and Eric
Bonabeau.
Self-Organization in Biological Systems.
Princeton University Press, 2001.
- Eric Bonabeau, Marco
Dorigo, and Guy Theraulaz.
Swarm Intelligence: From Natural to Artificial Systems.
Santa Fe Institute Studies in the Sciences of Complexity. Oxford University
Press, 1999.
- Mitchel Resnick.
Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel
Microworlds.
Complex Adaptive Systems. The MIT Press, 1997.
- Lars Backstrom,
Cynthia Dwork, and Jon Kleinberg.
Wherefore art
thou R3579X? Anonymized social networks, hidden patterns, and structural
steganography.
In Proceedings of the 16th International Conference on World Wide Web
(WWW07), pages 181–190. ACM New York, NY, USA, 2007.
(doi:10.1145/1242572.1242598)
- Matthew J.
Salganik, Peter Sheridan Dodds, and Duncan J. Watts.
Experimental study of inequality and unpredictability in an artificial cultural
market.
Science, 311(5762):854–856, February 2006.
(doi:10.1126/science.1121066)
- David
Liben-Nowell, Jasmine Novak, Ravi Kumar, Prabhakar Raghavan, and Andrew
Tomkins.
Geographic routing in social networks.
Proceedings of the National Academy of Sciences,
102(33):11623–11628, 2005.
(doi:10.1073/pnas.0503018102)
Jelasity Márk
Sun Apr 12 22:48:05 CEST 2009