Algoritmo di schedulazione speciale (espansione pattern)

Question

Domanda
Pensi che gli algoritmi genetici vale la pena provare per il problema al di sotto, o dovrò colpire questioni locali-Minimi?

Credo che forse gli aspetti del problema è grande per una messa a punto stile generatore / fitness-funzione. (Se hai pasticciato un progetto simile mi piacerebbe sentire da voi, e non fare qualcosa di simile)

Grazie per qualche consiglio su come strutturare le cose con le unghie e questo diritto.

Il problema
Sto cercando un buon algoritmo di schedulazione da utilizzare per il seguente problema del mondo reale.

Ho una sequenza con 15 slot simile (le cifre possono variare da 0 a 20):

2 2 2 2 2 2 2 2 2 2 2 2 2 2 2

(E vi sono in totale 10 differenti sequenze di questo tipo)

Ogni sequenza deve espandersi in una matrice, in cui ogni slot può prendere 1 posizione.

1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1
0 0 1 1 0 0 0 1 1 1 0 0 0 1 1 

I vincoli sulla matrice è che:

• [row-wise, cioè orizzontalmente] Il numero di quelle vincolate, deve essere o 11 o 111
• [row-wise] La distanza tra due sequenze di 1 deve essere di almeno 00
• La somma di ogni colonna deve corrispondere dell'array originale.
• Il numero di righe della matrice deve essere ottimizzato.

L'array deve quindi allocare una delle 4 matrici differenti, che possono avere un diverso numero di righe:

A, B, C, D

A, B, C e D sono i dipartimenti del mondo reale. Il carico deve essere posizionato ragionevolmente equo nel corso di un periodo di 10 giorni, per non interferire con altri obiettivi di reparto.

Ciascuna matrice viene confrontata con l'espansione di 10 differenti sequenze originali in modo da avere:

A1, A2, A3, A4, A5, A6, A7, A8, A9, A10
B1, B2, B3, B4, B5, B6, B7, B8, B9, B10
C1, C2, C3, C4, C5, C6, C7, C8, C9, C10
D1, D2, D3, D4, D5, D6, D7, D8, D9, D10

Alcuni punti su questi possono essere riservati (non so se dovrei fare semplicemente riservato / non riservata o la funzione-based). Le macchie riservati potrebbero essere incontri e altri eventi

La somma di ogni riga (ad esempio tutte le funzionalità del A) deve essere approssimativamente lo stesso entro il 2%. cioè somma (A1 a A10) dovrebbe essere approssimativamente uguale (B1 tramite B10) ecc

Il numero di righe può variare, in modo da avere, per esempio:

A1: 5 righe A2: 5 righe A3: 1 fila, quando tale singola riga potrebbe ad esempio essere:

0 0 1 1 1 0 0 0 0 0 0 0 0 0 0

etc ..

problema Sub *

I'de essere molto felici di risolvere solo una parte del problema. Per esempio potendo ingresso:

1 1 2 3 4 2 2 3 4 2 2 3 3 2 3

E ottenere un allineamento appropriato di sequenze con 1 e 0 minimizzato il numero di righe seguenti vincoli th sopra.

Answer 1

sotto-problema tentativo soluzione

Bene, ecco un'idea. Questa soluzione non si basa sull'utilizzo di un algoritmo genetico, ma qualche idea potrebbe essere utilizzato in corso in quella direzione.

vettori Base

Prima di tutto, si dovrebbe generare cosa penso di come i vettori di base. Per esempio, se la sequenza fosse 3 numeri a lungo piuttosto che 15, i vettori della base potrebbe essere:

v1 = [1 1 0]

v2 = [0 1 1]

v3 = [1 1 1]

Qualunque soluzione lunghezza della sequenza 3 sarebbe una combinazione lineare di questi tre vettori usando solo numeri interi positivi. In altre parole, la soluzione generale sarebbe

a*v1 + b*v2 + c*v3

dove a, b e c sono interi positivi. Per la sequenza [1 2 1], la soluzione è v1 = 1, v2 = 1, v3 = 0. Quello che prima vuole fare è trovare tutte le possibili vettori di base di lunghezza 15. Dal miei calcoli approssimativi Penso che non ci sono da qualche parte tra 300-400 vettori di base di lunghezza 15. posso darvi alcuni consigli verso la generazione di loro se si vuole.

Trovare le soluzioni

Ora, ciò che si vuole fare è sorta questi vettori di base per le loro somme / grandezze. Poi nella ricerca per la soluzione, si inizia con i vettori di base che hanno le più grandi somme. Si comincia con i vettori che hanno le più grandi somme perché portano ad avere meno righe totali. Abbiamo anche un array, veccoefs, che contiene una voce per il coefficiente lineare per ogni vettore base. All'inizio della ricerca della soluzione, tutti i veccoefs sono 0.

Quindi, prendiamo il primo vettore base (quello con la più grande somma / grandezza) e sottrarre questo vettore dalla sequenza fino a quando non sia creiamo un risultato irrisolvibile (con un 0 1 0 in esso per esempio) o uno qualsiasi dei numeri nel risultato è negativo. Salviamo il numero di volte in cui si sottrae il vettore in veccoefs. Usiamo il risultato dopo aver sottratto il vettore base dalla sequenza come sequenza per il prossimo vettore base. Se ci sono solo zeri a sinistra nel risultato, allora ci fermiamo il ciclo.

Non sono sicuro della efficienza / accuratezza di questo metodo, ma potrebbe almeno dare qualche idea.

Altre soluzioni possibili

Un'altra idea per risolvere questo è quello di utilizzare i vettori di base e formare il problema come un'ottimizzazione / minimo problema quadrati. Si forma una matrice di vettori di base in modo tale che il problema di fondo sarà minimizzando Sum [(Ax - b) ^ 2] dove A è la matrice di vettori di base, b è la sequenza di ingresso, ed x sono i coefficienti vettore base. Tuttavia, si vuole anche ridurre al minimo il numero di righe, in modo da poter aggiungere un termine come x ^ T * x per la funzione di minimizzazione dove x ^ T è la trasposta di x. La parte più difficile, a mio parere è trovare termini differenziabili aggiungere che incoraggerà coefficienti interi vettoriali. Se si può pensare a un modo per farlo, quindi l'ottimizzazione potrebbe benissimo essere un buon modo per fare questo.

Inoltre, si potrebbe prendere in considerazione una metropoli-tipo di soluzione Monte Carlo. Si potrebbe scegliere a caso se aggiungere un vettore, rimuovere un vettore, o sostituire un vettore ad ogni passo. Il vettore da aggiungere / rimosso / sostituito verrebbe scelto casualmente. La probabilità di questo cambiamento per essere accettato sarebbe un rapporto delle idoneità delle soluzioni prima della modifica e dopo la modifica. L'idoneità potrebbe essere pari alla differenza tra l'attuale soluzione e la sequenza, quadrato e sommati, meno il numero di righe / vettori di base coinvolti nella soluzione. Si avrebbe bisogno di mettere in costanti appropriate per per vari termini per cercare di ottenere il tasso di accettazione del 50% circa. I tipo di dubbio che questo funzionerà molto bene, ma ho pensato che si dovrebbe comunque considerare quando alla ricerca di possibili soluzioni.

Answer 2

GA può essere applicato a questo problema, ma non sarà compito 5 minuti. Hai bisogno di mettere parecchie cose insieme, senza sapere quale implementazione di ciascuno di essi è la cosa migliore.
Quindi:

1. Soluzione rappresentazione - come si intende rappresentare possibile soluzione? Utilizzando matrice sembra essere più semplice. Utilizzando collezione di un array dimensionale è possibile anche. Ma si dispone di alcuni vincoli, quindi forse il concetto supergenica vale la pena considerare?
2. È necessario utilizzare gli operatori di mutazione / di crossover corretti per data rappresentazione gene.
3. In che modo si far rispettare vincoli sulle soluzioni? Distruggere quelli che non sono corretto? Che cosa se contengono informazioni preziose? Forse farli rimanere nella popolazione, ma aggiungere un po 'di rigore per il fitness, in modo che contribuiranno alla prole, ma non andrà in prossime generazioni?

In ogni caso penso che GA può essere applicato a questo problema. Ne vale la pena? Di solito non sono GA algoritmo migliore, ma sono algoritmo decente se altri falliscono. Vorrei andare con GA, proprio perché sarebbe più divertente, ma vorrei cercare soluzione alternativa (nel caso).

P.S. intuizione personale: stavo risolvendo N Queens problema, per 70