Algoritmi genetici

lug
2009
11

scritto da | on , | Nessun commento

Lo studio della natura può venire in aiuto nella risoluzione di problemi logistici, infatti questo metodo di ricerca e ottimizzazione si ispira ai principi darwiniani che regolano l’evoluzione delle specie viventi.

L’algoritmo partendo da una insieme di possibili soluzioni (individui), detta popolazione iniziale, esegue n iterazioni incrociando gli individui e selezionando quelli migliori che costituiranno la generazione successiva. La successione di iterazioni evolve verso una soluzione del problema, tale evoluzione è ottenuta tramite una ricombinazione del materiale genetico degli individui e attraverso una mutazione casuale nella popolazione. Gli individui vengono selezionati in base ad una funzione fitness impostata in base al problema da risolvere.

Le possibile soluzioni del problema vengono codificate attraverso una struttura (una stringa) detta gene. L’algoritmo procede attraverso queste operazioni:

1 generazione di un numero di geni in maniera casuale

2 creazione di una sequenza di nuove generazioni

A per ogni individuo si calcola la funzione fitness

B si ordinano gli individui sulla base dei valori della funzione

C si scelgono gli individui più promettenti come genitori

D si genera una popolazione dall’incrocio dei genitori selezionati

E  si effettuano delle mutazioni in maniera casuale

3 l’algoritmo si interrompe quando viene verificato uno dei criteri d’arresto.

Esempi di utilizzo degli algoritmi genetici sono la risoluzione del problema dello zaino (ad esempio per l’ottimizzazione del carico di un vettore o per l’ottimizzazione di un magazzino automatico) o quello del commesso viaggiatore (ad esempio l’organizzazione dei viaggi o i problemi di routing relativi al picking). Gli algoritmi genetici si rivelano utili nella risoluzione di problemi di ottimizzazione non lineare che presentano un “paesaggio” di soluzioni possibili abbastanza articolato, inoltre è possibile interrompere l’algoritmo in qualsiasi momento ottenendo una soluzione comunque ottimale.

Per implementare un algoritmo genetico in Access o Excel è necessario procurasi una libreria di funzioni che implementi gli algoritmi genetici.

ALLEGATI

algoritmi genetici04
Titolo: algoritmi genetici04 (0 click)
Etichetta:
Filename: algoritmi-genetici04.pdf
Dimensione: 1 MB
algoritmi genetici03
Titolo: algoritmi genetici03 (0 click)
Etichetta:
Filename: algoritmi-genetici03.pdf
Dimensione: 2 MB
algoritmi genetici02
Titolo: algoritmi genetici02 (0 click)
Etichetta:
Filename: algoritmi-genetici02.pdf
Dimensione: 439 kB
algoritmi genetici01
Titolo: algoritmi genetici01 (0 click)
Etichetta:
Filename: algoritmi-genetici01.pdf
Dimensione: 4 MB

Lascia un Commento

News