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.


Introduction

Lecture slides


Emergence of Paths, Ant Colony Optimization

Reading material


Division of Labor, Task Allocation

Reading material


Evolution, Stochastic Optimization

Reading material


Complex Networks

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

Lecture slides


PageRank

Reading material


Reading


Additional papers


Valid XHTML 1.0! Jelasity Márk
Sun Apr 12 22:48:05 CEST 2009