Sistemi Processi Organizzativi: Appunti delle Lezioni

Chi offre di più vince: la ricchezza del vincitore diminuisce di una certa quantità, che viene

sommata al classificatore che ha emesso la stringa. Il classificatore vincente genera la stringa

contenuta nella sua regola di azione e la emette nel sistema (tale stringa potrà poi essere classificata

a sua volta). Se più classificatori vincono l’asta perché fanno la stessa offerta, tutti loro ricevono la

stessa stringa e tutti loro trasferiscono la quantità offerta al classificatore che ha generato la stringa.

Se più classificatori hanno emesso la stessa stringa e questa riceve delle offerte, l’ammontare

complessivo viene diviso tra essi.

Sergio Malavolti 17

Appunti delle Lezioni di Sistemi e Processi Organizzativi. 2005-06

Scienze di Internet

Problema: quello che stiamo facendo è come dire che stiamo esaminando alcuni (pochi) punti della

funzione e stiamo restituendo il massimo tra questi. Ma se il massimo della funzione fosse lontano

da questi punti, come facciamo per esplorare una fetta molto significativa del dominio?

Abbiamo due possibili soluzioni.

• Mutazione casuale: consiste nel modificare a caso alcune cifre dei classificatori (queste

modifiche devono però essere graduali e non troppo drastiche, in modo da non spostarci a

casaccio).

• Cross-over: Spezzare a coppie i classificatori con ricchezza elevata e ricombinare fra loro le

regole di condizione e le regole di azione (per questa operazione è richiesto solamente che le

coppie di regole siano spezzate nel medesimo punto; non importa a che altezza e non

importa nemmeno che sia lo stesso per tutti i classificatori, anzi, di solito il punto di cross-

over è scelto a caso).

Il secondo metodo è preferibile perché riproduce i vantaggi della riproduzione sessuata: se infatti la

coppia di classificatori è strutturata in modo che una delle due metà delle stringhe è quella che

maggiormente porta “ricchezza”, allora una delle quattro combinazioni raggiungerà una ricchezza

molto elevata e così facendo sarà molto probabile avvicinarsi al massimo assoluto.

Sergio Malavolti 18

Appunti delle Lezioni di Sistemi e Processi Organizzativi. 2005-06

Scienze di Internet

6. La Teoria Evolutiva e il Modello NK

La teoria evolutiva, inizialmente esposta da Darwin, teorizza l’evoluzione delle specie per

variazioni minime in modo tale da mantenerle nel punto di massima fitness. Punto importante di

questa teoria è che la selezione non agisce sul singolo individuo, bensì sui gruppi e sulle specie.

Il modello NK si propone di studiare la dipendenza della fitness di una specie (adattabilità a

sopravvive nell’ecosistema) dalla presenza di altre specie.

Esempio: la sopravvivenza dei predatori dipende molto dalla disponibilità di prede da cacciare.

6.1 Il modello NK

Non è un modello realistico, tuttavia la sua semplicità ci permette di capire gli aspetti fondamentali

della teoria evolutiva.

Nel modello ciascuna specie è dotata di un genoma, cioè un vettore numerico formato da zeri e uno;

gli elementi del menoma sono chiamati geni e il loro valore binario assunto è chiamato allele. Una

mutazione della specie consiste dunque nel cambiamento di uno o più alleli.

In generale un menoma composto da ‘N’ geni può assumere 2^N configurazioni; ad esempio, un

genoma con 2 geni sarà 00, 01, 10, 11, ovvero 4 configurazioni.

Chiamiamo ora ‘K’ il numero di geni del genoma da cui la fitness di una gene dipende; fatto questo,

assegnamo ad ogni configurazione delle fitness casuali comprese tra zero e uno, in modo che tali

valori rispettino i legami di dipendenza con i ‘K’ geni. Ad esempio, supponendo che K=1 e che la

fitness del gene 1 dipenda dal suo allele e dall’allele del gene 2 ma non dall’allele del gene 3, il

valore della fitness del gene 1 nelle configurazioni 000 e 001 dovrà essere il medesimo.

La grandezza che ci interessa misurare è la fitness media del genoma, definita come la media delle

fitness dei suoi geni; ogni configurazione ha la sua media. Se riportiamo sui vertici di un solido (con

3 geni otteniamo 8 vertici, quindi un cubo) le configurazioni degli alleli con la loro rispettiva fitness

media, messe in modo tale che si può passare ad uno dei vertici adiacenti tramite la mutazione di un

singolo gene, si può notare che:

• Per K=0 c’è un solo vertice di massimo raggiungibile da qualsiasi configurazione del

sistema.

• Per K=N-1 c’è un alto numero di massimi “locali”.

L’evoluzione ha lo scopo di “portare” un organismo verso la configurazione di alleli con fitness

media massima; in questo processo il pericolo maggiore è rimanere intrappolati in un massimo

locale. E’ quindi importante capire come varia la fitness media al variare di N e K.

I dati ci mostrano che, indipendentemente da N, per k=2 o poco più elevato, la fitness media è di

norma più alta, Ciò suggerisce che i sistemi evolutivi abbiamo da guadagnare dall’avere K>0, ma

che il suo valore deve essere comunque piccolo.

6.2 Al margine del caos

La presenza di parti della rete i cui elementi rimangano fissi è dovuta alla presenza di strutture

forzanti. La funzione OR può implementare delle strutture forzanti sul valore 1, la funzione AND

può implementare delle strutture forzanti sul valore 0.

Sergio Malavolti 19

Appunti delle Lezioni di Sistemi e Processi Organizzativi. 2005-06

Scienze di Internet

La transizione dei valori di K per i quali tutti gli elementi della rete sono congelati, e valori di K in

corrispondenza dei quali si osservano dinamiche caotiche è molto brusca ed ha luogo intorno a

K=2. Nella fase liquida intermedia la rete presenta delle isole di elementi in dinamica caotica

separate da muri di elementi fissi su 0 o su 1. Nonostante la fase liquida sia sottile, in molte

circostanze le reti booleane tendono a portarsi proprio su di essa. Sembra cioè che le capacità

computazionali di una rete siano massima ai margini del caos.

Tutti i sistemievolutivi operano nella sottile fascia ai margini del caos nella quale il comportamento

innovativo e mutante è confinato in isole separate da muri di agenti il cui comportamento non varia

nel tempo.

6.3 Coevoluzione.

Nella realtà i sistemi evolutivi coevolvono attraverso relazioni di adattamento reciproco. Prendiamo

in considerazione S specie, ognuna composta da N elementi. Ognuno di essi è caratterizzato da un

valore binario che è funzione dei valori assunti da K elementi all’interno della propria specie e da C

elementi appartenenti ad ognuna delle altre specie.

Per coppie di specie l’equilibrio viene raggiunto in breve tempo se K>C, tardi o mai se K<C.

Prese in considerazione S=2 specie di N=24 individui facendoli interagire a diversi K e C per 250

generazioni si può osservare che per C elevati:

I payoff sono maggiori se anche K è elevato

La rete con K più elevato ottiene payoff maggiori

La rete con K più basso ottiene payoff maggiori se gioca con una rete che ha un K elevato

Non si riesce a raggiungere un equilibrio se SC>K.

Sergio Malavolti 20

Appunti delle Lezioni di Sistemi e Processi Organizzativi. 2005-06

Scienze di Internet

7. Analisi Matematica delle Reti

I modelli ad agenti possono essere visti come grafi in cui i nodi sono gli agenti e gli archi sono le

comunicazioni fra di essi; analizzando matematicamente questi grafi è possibile osservare che le reti

sociali hanno interessanti caratteristiche. Vediamo quali.

7.1 Componente gigante connessa

Dati ‘N’ nodi di un grafo, si considerino tutte le possibili coppie di nodi; ciascuna coppia ha una

probabilità ‘p‘ di essere collegata con un arco. Il grafo casuale così ottenuto è detto Grafo di Erdos.

−

n 1

∑ −

pn ( n 1

)

p i

In tale grafo il numero di archi mediamente presenti è pari a: E = → .

2

=

i 1

La caratteristica più interessante del Grafo di Erdos è che se p > 1/n, cioè se è lecito aspettarsi che

dalla generazione casuale del grafo ogni nodo è molto probabile che sia connesso ad un altro nodo,

Se

quasi tutti i nodi fanno parte di un’unica componente connessa detta Componente Gigante.

esprimiamo la probabilità ‘p’ come c/n, allora questa componente riesce a “tenere il passo” delle

dimensioni del grafo all’aumentare di ‘n’ quando c>1.

Questo per dire che, oltre una certa soglia di interazione fra agenti, quasi tutti saranno connessi

(direttamente o indirettamente) gli uni con gli altri.

7.2 Topologia a mondo piccolo

Le reti di conoscenze umane sono strutturate in modo tale che, se

rappresentate su un grafo, nessun nodo non è lontanissimo dall’altro.

Ciò significa che con qualsiasi persona sconosciuta abbiamo una

catena di conoscenze che non ci è nota, ma che non è lunghissima.

Da qui l’espressione “Mondo Piccolo”. Le topologie di rete a mondo

piccolo hanno le seguenti caratteristiche:

• Agglomerati di nodi con molte connessioni locali fra loro.

• Relazioni sparse a lunga distanza.

Vediamo di dare una definizione quantitativa di questi aspetti. siano:

Per la prima caratteristica facciamo uso di un coefficiente di agglomerazione;

• i = nodo considerato.

• E = archi presenti nell’insieme di nodi direttamente collegati ad ‘i’.

• Vi = numero di nodi direttamente collegati ad ‘i’; il numero massimo di archi possibili è

−

Vi (

Vi 1

)

dato da 2 Ei

Coefficiente di agglomerazione del nodo: C(i) = −

Vi (

Vi 1

)

2

Esempio. Ei = 5; Vi = 5; c(i) = 5/(5(5-1)/2) → 5/10 → 1/2 → 0,5 n

∑ C Vi

( )

=1

i

= media di tutti i nodi →

Coefficiente di agglomerazione del grafo C(g) = n

Sergio Malavolti 21

Appunti delle Lezioni di Sistemi e Processi Organizzativi. 2005-06

Scienze di Internet

Per la seconda caratteristica facciamo uso della lunghezza del cammino caratteristico del grafo,

definito come la sommatoria delle lunghezze dei cammini minimi di tutte le possibili coppie di nodi

m n

∑∑ Di , j

= =

i 1 j 1 con i≠j

diviso n(n-1) . In Formula: L(g) = .

−

n ( n 1

)

I grafi a mondo piccolo hanno un grande C(g) e un piccolo L(g)

I grafi locali hanno un grande C(g) e un grande L(g)

I grafi casuali hanno un piccolo C(g) e un piccolo L(g)

7.3 Le reti scalabili

Definiamo la connettività di un nodo generico V

come il numero di archi ad esso collegati.

Chiamiamo quindi K i valori della connettività

possibili del