Auto-organizzazione...Auto-organizzazione Il principio fondamentale del successo di sistemi a...
Transcript of Auto-organizzazione...Auto-organizzazione Il principio fondamentale del successo di sistemi a...
Intelligenza e NaturaAndrea Roli
Dipartimento di Scienze - Universita degli Studi “G. D’Annunzio”
Intelligenza e Natura – p.1
Intelligenza e natura
La natura ha sviluppato tecniche “intelligenti” per risolvereproblemi. Per esempio:
Adattamento alle variazioni ambientali
Il sistema immunitario
Coordinazione tra insetti sociali (le termiti costruisconotermitai senza un progetto, le formiche muovono oggettigrandi senza un coordinatore, ecc.)
Intelligenza e Natura – p.2
Metafora naturale
I sistemi (intelligenti) basati su metafora naturale utilizzanomodelli di fenomeni e processi naturali per risolvereproblemi.
Caratteristiche:
Robustezza
Adattatività
Modelli subsimbolici
Obiettivi:
Risoluzione di problemi
Progettazione di sistemiadattativi
Simulazione
Esperimenti controllati
Intelligenza e Natura – p.3
Sistemi
Swarm intelligence
Computazione evolutiva
Reti neurali
Sistemi immunitari artificiali
Chimica artificiale
� � �
Intelligenza e Natura – p.4
Swarm Intelligence
Intelligenza e Natura – p.5
Swarm Intelligence
Intelligenza collettiva emergente in gruppi di agenti(semplici).
Prende origine da metafore e modelli del comportamento diinsetti sociali.
Formiche e ricerca di cibo, ripartizione del lavoro,riordinamento di larve.
Termiti e costruzione di nidi
Api e costruzione e disposizione di aree specifichenell’alveare.
Intelligenza e Natura – p.6
Swarm Intelligence
Proprietà delle metafore di sistemi di insetti sociali:
Elaborazione distribuita
Interazioni dirette e indirette
Agenti con semplici capacità computazionali
Flessibilità
Robustezza
Intelligenza e Natura – p.7
Swarm Intelligence
Problemi risolti con successo dagli insetti sociali:
Ricerca di cibo
Ripartizione del lavoro
Raggruppamento di oggetti
Ordinamento di larve
Costruzione di nidi
Trasporto cooperativo
Intelligenza e Natura – p.8
Auto-organizzazione
Il principio fondamentale del successo di sistemi aintelligenza collettiva è l’auto-organizzazione:
insieme di meccanismi dinamici nei quali compaionostrutture a livello globale, in seguito alle interazioni trale componenti di livello inferiore.
Caratteristiche:
Creazione di strutture spazio-temporali
Multistabilità (esistenza di più stati stabili)
Esistenza di biforcazioni a fronte di variazioni diparametri critici.
Intelligenza e Natura – p.9
Auto-organizzazione
Ingredienti:
Interazioni multiple tra agentiAgenti semplici (per esempio basati su regole)Sistemi composti da numerosi agenti
Feedback positivo (amplificazione)Amplificazione di fluttuazioni casuali e formazione distruttureRinforzo dei pattern di comportamento più “diffusi”
Feedback negativo (regolazione)SaturazioneCompetizioneEsaurimento di risorse
Intelligenza e Natura – p.10
Stigmergia
Particolare forma di comunicazione indiretta usata dagliinsetti sociali per coordinarsi.
Due individui interagiscono indirettamente quando uno diessi modifica l’ambiente e l’altro reagisce al nuovoambiente in un momento successivo.
Intelligenza e Natura – p.11
Ant Algorithms
Algoritmi ispirati al comportamento collettivo delle formichedurante la ricerca di cibo.
Applicati inizialmente a problemi di ottimizzazionecombinatoria (Dorigo 1992).
Applicati anche a problemi di routing e classificazione diinformazioni.
Intelligenza e Natura – p.12
Ant Algorithms
Meccanismi fondamentali:
1. Ogni formica deposita sul terreno una sostanza chimica(feromone) mentre cammina.
2. La scelta del percorso da seguire alla ricerca di cibo èguidata dall’intensità del feromone: più è intenso in unadirezione, maggiore sarà la probabilità di scegliere taledirezione.
3. Il feromone evapora nel tempo, quindi rimangono“marcati” solo i percorsi usati più frequentemente.
Intelligenza e Natura – p.13
Ant Algorithms
(1)(3)
(2)(4)
Intelligenza e Natura – p.14
Ant System
Applicazione al problema del commesso viaggiatore(Traveling Salesman Problem): trovare un cammino dilunghezza minima che passi per tutte le città una e unasola volta.
- Nodi � città
- Archi � collegamenti tra le città
- Pesi sugli archi � distanze tra due città
Intelligenza e Natura – p.15
Ant System
Le formiche artificiali costruiscono una soluzionemuovendosi da un nodo all’altro. Ad ogni iterazione laregola di transizione guida la scelta del nodo successivo.La regola di transizione dipende dal feromone ( �) e da unafunzione euristica ( �).
Intelligenza e Natura – p.16
Ant System
La probabilità di passare dalla città
�
alla città
�
per laformica
�
è:
� ���� ��
�
���� � � �� �� � �
���� ammissibili� �� � � � �� � � �� se
� �
ammissibili �
�
altrimenti
� e �
bilanciano l’importanza relativa di feromone e euristica.
Intelligenza e Natura – p.17
Ant System
Quando tutte le formiche (
� � �! � � � ") hanno costruito unasoluzione, si aggiorna il feromone.
� �� # $ �&% ' (*) � �� +,.-
��/ 01 ����
1 ���� �
2 0 3� se la formica
�
ha percorso l’arco
$ � � (
�
altrimenti
' è il coefficiente di evaporazione e4 � è la lunghezza del
circuito percorso dalla formica
�.
Intelligenza e Natura – p.18
Ant System
Ant System Algorithm
InitializePheromoneValues()while termination conditions not met do
for all ants 5 � 6
do798 # ConstructSolution( �, �)end for
ApplyOnlineDelayedPheromoneUpdate(){Evaporazione+ rinforzo}
end while
Intelligenza e Natura – p.19
Altri Sistemi
Ant Colony Optimization
AntNet
SwarmbotsRaccolta e raggruppamento di oggettiSpostamento di oggetti di grandi dimensioni(trasporto cooperativo)Autoassemblaggio
Intelligenza e Natura – p.20
Applicazioni
� Ottimizzazione combinatoria (es. Vehicle Routing eQuadratic assignment Problem)
� Reti di telecomunicazioni
� Distribuzione di gas in Ticino
� Clustering
Intelligenza e Natura – p.21
Riferimenti bibliografici
E.Bonabeau, M.Dorigo, G.Theraulaz. SwarmIntelligence. From natural to artificial systems. OxfordUniversity Press, 1999.
S.Camazine, J.-L.Deneubourg, N.R.Franks, J.Sneyd,G.Theraulaz, E.Bonabeau. Self-Organization inBiological Systems. Princeton University Press, 1999.
Intelligenza e Natura – p.22
Risorse in Internet
http://iridia.ulb.ac.be/ �mdorigo/ACO/ACO.html
www.swarm-bots.org
www.cs.bgu.ac.il/ �sipper/caslinks.html
www.santafe.edu
Intelligenza e Natura – p.23
Evolutionary Computation
Intelligenza e Natura – p.24
Evolutionary Computation
Inspiring principle: theory of natural selection
“Species face the problem of searching for beneficialadaptations to the environment. The knowledge that eachspecies has gained is embodied in the makeup of thechromosomes of its members.” (Davis, Genetic Algorithmsand Simulated Annealing, 1987)
Example: rabbits � � �
Intelligenza e Natura – p.25
Evolutionary Computation
Evolutionary Computation (EC) encompasses:
Genetic Algorithms
Genetic Programming
Evolution Strategies
Estimation of Distribution Algorithms
Classifier Systems
Intelligenza e Natura – p.26
Characteristics
Robustness
Adaptivity
Subsymbolic models(no explicit symbolic computation)
Intelligenza e Natura – p.27
Objectives
Problem solving
Optimization
Adaptive systems design
Simulation
Intelligenza e Natura – p.28
Some applications
� System design (e.g., airplanes, electronic circuits,mechanical elements)
� Neural network training (e.g., robotics)
� Signal processing (e.g., artificial vision)
� Optimization (discrete and continuous)
Intelligenza e Natura – p.29
More applications
� Time series analysis and forecasting (e.g., financialforecasting)
� Artificial Life (e.g., cellular automata, analysis ofcomplex adaptive systems)
� Games (e.g., Prisoner’s Dilemma)
Challenge: find a problem where EC has NOT beenapplied!
Intelligenza e Natura – p.30
Genetic Algorithms
The Metaphor
NATURAL EVOLUTION ARTIFICIAL SYSTEMSIndividual � A possible solutionFitness � Quality
Environment � Problem
Intelligenza e Natura – p.31
A bit of terminology
A population is the set of individuals (solutions)
Individuals are also called genotypes andchromosomes (if one solution � one chromosome)
Chromosomes are made of units called genes
The domain of values of a gene is composed of alleles(e.g., a binary variable/gene has two alleles)
Intelligenza e Natura – p.32
The Evolutionary Cycle
Intelligenza e Natura – p.33
The Evolutionary Cycle
POPULATION
Intelligenza e Natura – p.33
The Evolutionary Cycle
POPULATION
PARENTSSELECTION
Intelligenza e Natura – p.33
The Evolutionary Cycle
POPULATION
PARENTSSELECTION
RECOMBINATION
MUTATION
OFFSPRING
Intelligenza e Natura – p.33
The Evolutionary Cycle
POPULATION
PARENTSSELECTION
RECOMBINATION
MUTATION
OFFSPRINGREPLACEMENT
Intelligenza e Natura – p.33
Genetic operators
Mutation
Recombination
Selection
Replacement/insertion
Intelligenza e Natura – p.34
Genetic operators
� EC algorithms define a basic computational procedurewhich uses the genetic operators.
� The definition of the genetic operators specifies the actualalgorithm.
� The definition of the genetic operators depends upon the
problem at hand.
Intelligenza e Natura – p.35
Genetic Algorithms
Developed by John Holland (early ’70) with the aim of:
Understand adaptive processes of natural systems
Design robust (software) artificial systems
Intelligenza e Natura – p.36
Simple Genetic Algorithm
Derived from the natural metaphor
Very simple model
‘Programming oriented’
You can take it as a first step toward evolutionary algorithmsin general
Intelligenza e Natura – p.37
Simple Genetic Algorithm
Solutions are coded as bit strings
0 0 0 1 01 1 1 1 1
CHROMOSOME
GENE
Integer
Plan
Real
Rules
.....
GENOTYPE PHENOTYPE
Intelligenza e Natura – p.38
Example
Optimization of a function of integer variable � � � � � � � �:
binary coding � string of 7 bit
4 bits per digit � string of 12 bit
Intelligenza e Natura – p.39
Genetic operators (1)
Mutation: each gene has probability �� of being modified(’flipped’)
0 0 0 1 01 1 0 1 1
0 0 0 1 01 1 1 1 1
Intelligenza e Natura – p.40
Genetic operators (2)
Crossover: cross-combination of two chromosomes(loosely resembling human crossover)
1 1 0 01 0 0 0 1 0 1 1 0 01 0
0 1 1 1
0 1 1 1
0 0 1 00 0 0 11 10 0 0 11 1
Intelligenza e Natura – p.41
Genetic operators (3)
Selection acts in the choice of parents and produces themating pool .
� Proportional selection: the probability for an individualto be chosen is proportional to its fitness.
Intelligenza e Natura – p.42
Genetic operators (3)
Roulette wheel
50%10%
10%
25%
5%
� 0 50
��� 25
��� 10��� 10
��� 5
Intelligenza e Natura – p.43
Genetic operators (4)
Generational replacement: The new generation replacesentirely the old one.
Advantage: very simple, computationally not(extremely) expensive, easier theoretical analysis.
Disadvantage: we could loose good solutions
Intelligenza e Natura – p.44
High-level algorithm
Initialize PopulationEvaluate Populationwhile Termination conditions not met do
Select parents for matingApply crossoverApply mutationPopulation # New populationEvaluate Population
end while
Intelligenza e Natura – p.45
Termination conditions
The basic question is: when to stop?
Execution time limit reached
We are satisfied with the solution(s) obtained
Stagnation (limit: the population converged to the sameindividual)
Intelligenza e Natura – p.46
Why does it work?
Intuition:
Crossover combines good parts from good solutions(but it might also destroy � � � sometimes)
Mutation introduces diversity
Selection drives the population toward high fitness
Intelligenza e Natura – p.47
SGA: pros and cons
Pros:
Extremely simple
General purpose
Theoretical models
Cons:
Coding
Too simple genetic operators
Intelligenza e Natura – p.48
A recipe
The ingredients to prepare a GA:
Solution coding (e.g., bit strings, programs, arrays of realvariables, etc.)
Define a way of evaluating solutions (e.g., objectivefunction value, result of a program, behavior of a system,etc.)
Define recombination operators (crossover , mutation)
Define the selection and replacement/insertionmechanisms
Intelligenza e Natura – p.49
Toward less simple GA
Recombination:
Multi-point crossover (recombination of more than 2“pieces” of chromosomes)
Multi-parent crossover (an individual is generated bymore than 2 parents)
Uniform crossover (children created by randomlyshuffling the variables at each site)
Intelligenza e Natura – p.50
Multi-point crossover
111
1 0 0 0 1 0
0 1 1 1
0 0 1 01 0 0 0 0 11 1
0 0 01 1
1 1 0 01 0
Intelligenza e Natura – p.51
Multi-parent crossover
1 1 0 0
0 1 1 0
0 0 1 0
0 1 1 1
1
00 1
1 1
0 1
0 0 0
1
0 0
1 0
1 0 1 01 0
1 1 0
0 1 1
0 1 1
1 1 01 0
11
1 1 0 1 1 0
Intelligenza e Natura – p.52
Toward less simple GA
Mutation:
Learning applied to modify the chromosome
In optimization, hill-climbing or more complex localsearch algorithms can be applied
Interesting topic: Evolution & Learning,
www.cogs.susx.ac.uk/users/ezequiel/alife-page/evolearn.html
Intelligenza e Natura – p.53
Toward less simple GA
Selection:
Different probability distribution (e.g., probabilitydistribution based on the ranking of individuals)
Tournament Selection (iteratively pick two or moreindividuals and put in the mating pool the fittest)
Intelligenza e Natura – p.54
Ex: real valued variables
- Solution: � � � 5 � � 5 � � �
- Mutation: random perturbation � � � � �
, accepted if� � � � � 5 � �
- Crossover: linear combination � � � 0 � + �� �, with
� 0 ��
such that 5 � � � �
.
Intelligenza e Natura – p.55
Example: permutations
- Solution: � � $ � 0 � � � � � �� (
is a permutation of$ �! � � � � (
- Mutation: random exchange of two elements in the
�-ple
- Crossover: like 2-point crossover, but avoiding valuerepetition (see next example).
Intelligenza e Natura – p.56
Eight Queens
Place 8 queens on a
� � �
chessboard in such a way thatthe queens cannot attack each other.
Intelligenza e Natura – p.57
Eight Queens
Genotype: a permutation of the numbers 1 through 8
7 13 2 4 6 5 8
Intelligenza e Natura – p.58
Eight Queens
Mutation: exchanging two numbers
21 11 3 5 4 8 7 2 3 5 8 74 1
Intelligenza e Natura – p.59
Eight Queens
Crossover: combining two parents
7
1
8 7
5
6
8 7 6 5 4 3 2
3 5 2 6 41
8 7 6 2 4 1 3
3 5 4 2 81
Intelligenza e Natura – p.60
Eight Queens
Fitness: penalty of a queen is the number of queens it cancheck.
The fitness of the configuration is the sum of the singlepenalties.
Intelligenza e Natura – p.61
Genetic Programming
Can be seen as a ‘variant’ of GA: individuals areprograms
Used to build programs that solve the problem at hand( � specialized programs)
Extended to automatic design in general (e.g.,controllers and electronic circuits)
Intelligenza e Natura – p.62
Genetic Programming
Individuals are trees which encode programs.
>
1
+
2 IF
3 4
T 6
Fitness given by the evaluation of the program “behavior”(based upon some defined criteria)
Intelligenza e Natura – p.63
Operators
Mutation: Random selection of a subtree which issubstituted by a well formed random generated subtree
>
1
+
2 IF
3 4
6T
>
6*
1
+
2 IF
3 4
2Y
Intelligenza e Natura – p.64
Operators
Crossover: Exchange two randomly picked subtrees.
4
+
4
+
5
5>
+
2 IF
3 4
T 6
>
IF
3 4
T 6
IF
<
1
+
2
2
IF
<
1
2
Intelligenza e Natura – p.65
Operators
Selection and replacement
Fitness is evaluated depending on the application.
For assembler worms the fitness can be the memorythey occupied.
For controllers, the fitness can be the percentage ofcorrect actions
Intelligenza e Natura – p.66
The realm of GP
Black art problems. E.g.,automated synthesis of analogelectrical circuits, controllers, antennas, and other areasof design
Programming the unprogrammable, involving theautomatic creation of computer programs forunconventional computing devices. E.g.,cellularautomata, parallel systems, multi-agent systems, etc.
Intelligenza e Natura – p.67
The realm of GP
Commercially usable new inventions involving the use ofgenetic programming as an automated “inventionmachine” for creating commercially usable new inventions
Problems in computational molecular biology, includingmetabolic pathways and genetic networks
Intelligenza e Natura – p.68
Coevolution
Species evolve in the same environment
� dynamic environment
Two kinds:
Competitive
Cooperative
Intelligenza e Natura – p.69
Competitive Coevolution
� Species evolve trying to face each other
E.g., prey/predator, herbivore/plants.
Applications: ALU design for Cray computer,(pseudo-)random number generator.
Intelligenza e Natura – p.70
Cooperative Coevolution
� Species evolve complementary capabilities to survive intheir environment
E.g., host/parasite.
Applications: ‘niche’ genetic algorithms for multi-criteriaoptimization.
Intelligenza e Natura – p.71
Some references
M.Mitchell. Genetic Algorithms. MIT Press, 1999.
Z.Michalewicz. Genetic Algorithms + Data Structures =Evolution Programs, Springer, 1992.
D.E.Golberg. Genetic Algorithms in Search,Optimization and Machine Learning. Addison-Wesley,1989.
W.B.Langdon, R.Poli. Foundations of GeneticProgramming. Springer, 2001.
Intelligenza e Natura – p.72
On the Internet
EvoNet: http://www.evonet.polytechnique.fr/
www.genetic-programming.com
GALib http://lancet.mit.edu/ga/
http://www.aic.nrl.navy.mil/galist/
www.isgec.org
Intelligenza e Natura – p.73
Proposte per tesine
Alcune idee:
Progetto e implementazione di algoritmi evolutivi per:GiochiAnalisi di serie storiche e previsione finanziariaAnalisi di dinamiche cooperative/competitiveSimulazione di sistemi multi-agente
Progetto e implementazione di sistemi “swarm” per:Analisi di datiSimulazione di robot cooperativiEsperimenti di computazione emergenteSimulazione di sistemi multi-agente
Intelligenza e Natura – p.74