2010-12-30 3 views
7

Per gli algoritmi genetici di solito geni simboleggiato in questo modo:Come rappresentare una pianificazione per il problema degli orari in Algoritmi genetici?

PARENT1: 101101010101001001001001110011100110101011101101 
PARENT2: 010100111011010101110101001001101011001010010110 

in modo incrociato, le mutazioni possono essere fatto con questo rappresentazioni come come:

scegliere un punto di crossover:

PARENT1: 1011010101010010 01001001110011100110101011101101 
PARENT2: 0101001110110101 01110101001001101011001010010110 

Eseguire crossover produrre un bambino:

CHILD: 1011010101010010 01110101001001101011001010010110 

che poi diventa, un intero cromosoma nuova:

CHILD: 101101010101001001110101001001101011001010010110 

Il mio problema è come rappresentare un gene programma settimanale in Java?

esempi sono presi da questo articolo: http://secretgeek.net/content/bambrilg.pdf

sto recepiscono questo problema degli orari in Java e vogliono rappresentare

FIGURE 10: An Entire University Timetable 

in Java.

+0

Non correlato alla domanda, ma se si dispone di disponibilità per utilizzare Matlab e si dispone di – Nishant

+0

Non correlato alla domanda, ma se si dispone di disponibilità per utilizzare Matlab e non si dispone di alcun vincolo per utilizzare Java. Suggerisco di andare a Matlab. Nella mia esperienza personale, Matlab ha una fantastica serie di strumenti per GA e Soft Computing. vale la pena esplorare. – Nishant

+0

@Nishant Devo eseguire l'impeachment in Java. – kamaci

risposta

2

Il seguente codice potrebbe darti un'idea di come affrontare il problema. Una soluzione (che sarebbe l'orario universitario) consiste in una serie di stanze singole. Queste singole stanze hanno ciascuna una matrice 2dimensionale, dove le colonne sono i giorni e le righe sono le ore. Ho impostato le ORE a 16, poiché penso che di notte non ci saranno lezioni. Quindi Hour Hour 1 sarebbe la prima ora del giorno ... probabilmente dalle 7 alle 8 del mattino. I valori dell'array mostrano quale classe è prenotata.

public class SingleRoom { 
    static final int DAYS = 7; 
    static final int HOURS = 16; 
    . . . 
    private int[][] timetable = new int[DAYS][HOURS]; //0 would say room is not booked, >0 indicates the booked class (english advanced (12), object oriented programming (139), etc..) 
} 

public class Solution { 
    static final int AVAILABLE_ROOMS = 26; 
    . . . 
    private SingleRoom[] university_timetable = new SingleRoom[AVAILABLE_ROOMS];  
} 

mutazioni:

cambio di classe di mutazione - modificare la classe ad un'altra classe casuale o a zero = nessuna prenotazione

interruttore on/off di classe - se un'ora ad un giorno in una stanza specifica è prenotato, spegnilo se non è prenotato, accendilo con una classe casuale questo è per dare all'algoritmo la possibilità di non prenotare ore, poiché nella mutazione classe cambia lo 0 ha una bassa probabilità da scegliere

vincoli: dopo aver creato le soluzioni, verificare tutti i vincoli e mantenere le soluzioni valide le nuove soluzioni valide devono essere inserite nella popolazione (di soluzioni), se sono migliori ad altre soluzioni già presenti nella popolazione o se migliorano la diversità della popolazione

Ma nel documento a cui ci si riferisce è abbastanza buono descritto come implementare un GA per questo problema (inizia con pagina 16).

Ho scritto un framework java generico per l'algoritmo di ottimizzazione multi-obiettivo mPOEMS (Ottimizzazione del prototipo multiobiettivo con fasi evolute di miglioramento), che è un GA che utilizza concetti evolutivi.

È possibile trovare il codice here, potrebbe dare un'idea come affrontare il problema:

Le soluzioni che si possono trovare con questo algoritmo sono stati confrontati in un lavoro scientifico di state-of-the- algoritmi artistici SPEA-2 e NSGA, ed è stato dimostrato che l'algoritmo di è comparabile o addirittura migliore, a seconda delle metriche che si prendono per misurare le prestazioni.

Lo puoi trovare here.

Ulteriori risorse: mia tesi che si applica questo quadro di riferimento per il problema di selezione dei progetti: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

La documentazione del quadro: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS carta di presentazione: http://portal.acm.org/citation.cfm?id=1792634.1792653

realtà con un po 'di entusiasmo si potrebbe facilmente adattare il codice della struttura generica alle proprie esigenze.

Scrivi questa GA nel tuo lavoro o come studente?

+0

Non ho potuto avere un tempo per rispondere a questo commento. Cercherò di trovare una soluzione secondo i tuoi consigli. Lo sto implementando per la scuola e non per lavoro. – kamaci

+0

Hai suggerito un array bidimensionale per l'orario (riga, colonna). È logico cambiarlo in un array. Intendo, ad esempio, la definizione di diversi indici per lunedì 7 alle 8 AM, lunedì 8-9 AM, ...., martedì 7 alle 8, martedì 8-9.00, .... così via? – kamaci

+0

Le offerte di mutazioni sono silenziose, ma che dire dei crossover? – kamaci