Algoritmi genetici e utilizzi concreti.

Originariamente inviato da Dev-01

Ciao +m+,
Da quello che mi pare di aver capito, il problema è noto (tipo il "problema del sacco") e si tratta di trovare (a "circa" tentativi) i parametri in ingresso di una funzione (che poi è quella di fitness) che consentano di riuscire a riempire il suddetto sacco il più possibile utilizzando le varie combinazioni di oggetti disponibili...

Quindi si potrebbe dichiarare anche un range di accettabilità? Del tipo +-3(%)?

Potrei ad esempio (e tanto per capirci) definire una soluzione pari a 1 miliardo ed impostare l'algoritmo per sapere fra i numeri primi quali posso addizionare senza ripetizioni in modo da avvicinarmi il più possibile alla cifra stabilita e possibilmente entro un determinato range?

In realtà no, ma ti stai avvicinando.
Non hai nessuna garanzia con questi metodi euristici, quindi in sostanza lo lanci, aspetti, poi vedi.
Magari cambi un pochino i parametri, lanci di nuovo, aspetti di vedere se migliora.
Eventualmente lanci n thread diversi in parallelo per vedere quale set di parametri ti dà una soluzione migliore
Rammenta che usando un generatore pseudocasuale, ogni esecuzione porta a una popolazione ed una soluzione diversa

Leggevo di convergenza prematura degli "individui" che, dopo x generazioni, cominciavano a somigliarsi... (che poi è la causa dell'utilizzo degli algoritmi di mutazione).

Non farti prendere per il naso: non c'è praticamente nulla di similitudine tra una popolazione "vera" e un AG, che è una banalizzazione estrema.
Comunque sì, la mutazione ha la stessa funzione della "ricottura", cioè è come dare un "colpetto" col dito a una lancetta di un misuratore sperando che si muova da sola nella direzione giusta

Consentimi, ti prego, un'altra domanda: se noi selezioniamo la soluzione che maggiormente si appresta alla migliore, perchè si parla di minimi e di minimi locali? E locali in che senso?

Data una certa funzione e un certo intervallo possono esistere più minimi, che sono quindi minimi locali (cioè il minimo in un certo intervallo o meglio spazio, visto che usualmente le variabili sono multimensionali e quindi sono spazi, non intervalli).

Le funzioni analitiche di ottimizzazione (che poi alla fin fine sono tutte basate su derivate, discesa del gradiente e cugini vari) cercano IL minimo, cioè il minimo dei minimi, il minimo assoluto.
Ma questo non è banale, quando le funzioni sono "brutte" tipo questa

Qual'è il minimo? E come fai a "beccarlo"? Non è facile, finisci facilmente per andare a "rotolare" verso minimi locali, ma non il minimo globale

Leggevo inoltre che, per un migliore funzionamento dell'algoritmo, è meglio che individui con valore di fitness simile (in particolare quelli con valori più alti) siano situati vicini tra loro... è per via del crossover? Considerando il solo valore di fitness la interpreto come una affermazione non tanto sensata, o almeno non indispensabile...

Sì.
In teoria, mooolto in teoria, gli individui "migliori" si accoppieranno tra di loro "figliando" individui ancora migliori.
Ovviamente la semplificazione degli AG è talmente grande che in pratica non funziona affatto così bene come in teoria.

E grazie 1000 per l'apprezzatissimo codice.

Se ti piazzo un DPE o un granulare poi vedi

Non immaginarti che un "vero" genetico funzioni così, con codifica binaria, perchè la risoluzione è troppo bassa (ridicola, anzi).
Si adottano strategie varie per "zoomare" (cioè riscalare) mantenendo un numero ragionevole di alleli.
Comunque per l'ambito didattico inizi ad "inquadrare"

Ciao +m+,

scusa se rispondo con una settimana di ritardo.

Comunque per l'ambito didattico inizi ad "inquadrare"

Beh, grazie per l'incoraggiamento, è già qualcosa.

Qual'è il minimo? E come fai a "beccarlo"? Non è facile, finisci facilmente per andare a "rotolare" verso minimi locali, ma non il minimo globale

Ok, ho capito... ed ho capito come fare pure a tenerne traccia per la generazione di un eventuale grafico di controllo.
Quello che ancora non mi è chiaro è questo:

Una volta trovato il minimo (i minimi locali) che te ne fai? Come li utilizzi?

E, soprattutto, questi valori potrebbero essere utili al fine di "rimodellare" la funzione e/o perfezionare l'approccio al problema?

Se la funzione di fitness è quella che verifica la "bontà" del risultato ottenuto, in quale misura essa è identificabile col reale problema da affrontare? Cioè: lo rappresenta in tutto o in parte? E' possibile utilizzare più funzioni per determinare una soluzione anche parziale?

Capisco che sto esagerando con le richieste ma l'argomento è interessante e tu mi stai dando una mano incredibile facendomi fare dei balzi in avanti in breve tempo con la tua esperienza in materia: grazie per la generosità.

Chiariamo.
La funzione di fitness è quella da minimizzare, che si presuppone essere GIA' la soluzione del problema, non è quindi che la cambi.

Immagina di dover trovare il minimo della funzione a 3 variabili abs(x+y-z): metterai come funzione di fitness f(x,y,z)=abs(x+y-z).
In questo caso sono... cavoli tuoi scrivere la funzione di fitness: essa rappresenta canonicamente proprio il problema che vuoi risolvere.

Lanciando il genetico troverai una soluzione, diciamo
x1,y1,z1 con un valore f1 della funzione di fitness (un minimo locale).
rilanciando otterrai
x2,y2,z2 con valore f2
...
x3,y3,z3 con valore f3

Ora piglierai il minimo di f1,f2,f3 (supponiamo f2), quindi saprai che i parametri migliori che hai
trovato sono x2,y2 e z2

Modellerai in 3 cromosomi rispettivamente le variabili x,y e z.

Ok, il cerchio si è chiuso.

Mi hai chiarito tutti i dubbi che avevo in partenza, anzi, ho ottenuto molto di più di quello che speravo.

Avendo i concetti di base chiari mi sarà più facile dedicarmici.

Ti ringrazio infinitamente per la disponibilità e la cortesia.

Alla prossima...