Il mio compito è utilizzare l'euristica di ricerca locale per risolvere il problema dello zaino multidimensionale a scelta multipla , ma per farlo devo prima trovare una soluzione fattibile per iniziare.
Ecco un esempio di problema con quello che ho provato fino ad ora.
Problema
L1 L2 L3
RESOUCES : 8 8 8
GROUPS:
G1:
11.0 3 2 2
12.0 1 1 3
G2:
20.0 1 1 3
5.0 2 3 2
G3:
10.0 2 2 3
30.0 1 1 3
Strategie di ordinamento
Per trovare una soluzione fattibile di partenza per la mia ricerca locale ho deciso di ignorare la massimizzazione dei guadagni e provare solo ad adattare i requisiti delle risorse.
Ho deciso di ordinare le scelte (strategie) in ciascun gruppo confrontando la loro "distanza" dall'origine dello spazio multidimensionale, quindi calcolando SQRT(R1^2 + R2^2 + ... + RN^2) . Sentivo che questa era una soluzione acuta poiché in qualche modo privilegiava quelle scelte con riduci gli usi più vicini tra loro (ad esempio R1: 2 R2: 2 R3: 2 < R1: 1 R2: 2 R3: 3) anche se la somma totale è lo stesso.
Farlo e selezionare la scelta migliore da ciascun gruppo si è rivelato sufficiente per trovare una soluzione fattibile per molti [30] problemi di benchmark diversi, ma ovviamente sapevo che era solo fortuna. Quindi mi è venuto in mente il problema presentato sopra che ordina in questo modo:
L1 L2 L3
RESOUCES : 8 8 8
GROUPS:
G1:
12.0 1 1 3 < select this
11.0 3 2 2
G2:
20.0 1 1 3 < select this
5.0 2 3 2
G3:
30.0 1 1 3 < select this
10.0 2 2 3
E non è fattibile perché la risorsa è R1: 3, R2: 3, R3: 9 .
La soluzione facile è scegliere una delle seconde scelte migliori nel gruppo 1 o 2, quindi ho bisogno di un qualche tipo di iterazione (ricerca locale [?]) per trovare la soluzione fattibile di partenza per la mia soluzione di ricerca locale.
Ecco le opzioni che ho trovato
Opzione 1: scelte iterate
Ho provato a trovare un modo per ripetere tutte le scelte con un ordine specifico, qualcosa come
G1 G2 G3
1 1 1
2 1 1
1 2 1
1 1 2
2 2 1
...
credendo che le soluzioni fattibili non saranno così lontane dall'irraggiungibile con cui inizio e quindi il numero di iterazioni si manterrà piuttosto basso.
Ha senso? Se sì, come posso ripetere le scelte (combinazioni raggruppate) di ciascun gruppo mantenendo "il più vicino possibile" alla precedente iterazione?
Opzione 2: modifica il termine di confronto
Ho provato a pensare a come trovare una variabile migliore per ordinare le scelte. Ho pensato a come una risorsa "preziosa" si basa sulla domanda e l'offerta, in modo che una domanda più strong di una risorsa più preziosa ti spingerà verso il basso nell'elenco, ma questo non è stato di alcun aiuto.
Ho anche pensato che probabilmente non ci sarà una variabile di confronto che mi assicurerà una soluzione fattibile al primo colpo.
C'è una tale variabile? In caso contrario, c'è un criterio di classificazione migliore comunque?
Opzione 3: implementa qualsiasi algoritmo di risoluzione veloce sub-ottimale noto
Purtroppo non sono riuscito a trovare nessuno di questi algoritmi online. Qualche suggerimento?
Modifica
NOTA: Ho aggiornato la descrizione precedente usando le etichette L1 L2 L3 per i limiti delle risorse problema al posto di R1 R2 R3 che ora indicano i requisiti delle risorse di ciascuna strategia (scelta)
Considerando l'input di @J Trana, ho deciso di provare un algoritmo genetico per l'installazione del problema.
Questo sembrava abbastanza adatto alla struttura del problema poiché ogni gruppo è un gene, ogni soluzione è un cromosoma e ogni strategia è un allele.
Ho anche modificato l'espressione della distanza per adattarla meglio a limiti di risorse eterogenei, quindi ora la distanza è: SUM(Rn/Ln) che dovrebbe dare una distanza inferiore (cioè una priorità più alta) a quelle strategie con porzioni di risorse inferiori.
Dato che questa parte è pensata solo per la risoluzione dell'inizializzazione, ho scelto le funzioni genetiche che ricadono:
Fitness
// if solution is feasible, that's just enough, it has the greatest fitness possible
if(solution.isFeasibleInProblem()) return Integer.MAX_VALUE;
ArrayList<Integer> consumptions = new ArrayList<Integer>();
for(Integer limit : problem.resourceLimits){
consumptions.add(0);
}
// add the resources consumptions from each group
for(Group g : genes){
for(int i = 0; i < g.currentSelectedSolution.resourceRequirements.size(); i++){
consumptions.set(i, consumptions.get(i) + g.currentSelectedSolution.resourceRequirements.get(i));
}
}
ArrayList<Double> subFitnesses = new ArrayList<Double>();
// each subFitness is the ratio between the total limit and the actual consumption
// this way if the consumption is < limit subFitness is greater than 1 (rises the fitness), else it is less than 1 and lowers the fitness
for(int j = 0; j < consumptions.size(); j++){
double subFitness = problem.limits.get(j) / consumptions.get(j);
subFitnesses.add(subFitness);
}
double fitness = 1;
for(Double sF : subFitnesses){
fitness *= sF;
}
return fitness;
Quindi i requisiti delle risorse inferiori al limite aumentano l'idoneità, laddove i requisiti superiori al limite riducono l'idoneità.
Mutation
Per la funzione di mutazione ho scoperto che le soluzioni praticabili contengono strategie a distanza ridotta e considerando che soluzioni molto in basso nella lista di distanza ordinata rallenta l'evoluzione perché la maggior parte delle volte queste mutazioni hanno effetti negativi.
public void mutate(int strategyIndex, double mutationIntensity){
// if there's no choice, don't mutate
if(this.strategies.size() <= 1) return;
... here I'd need something that keeps in the first positions of the list
but eventually, with higher mutation intensities, goes to greater indexes...
selectStrategy(newStrategyIndex);
}
La soluzione di cui sopra funziona molto bene per la maggior parte dei benchmark, ma ce ne sono 2, con molte scelte per gruppo e molte risorse per scelta, che semplicemente non troveranno una soluzione fattibile.
Come potrei implementare l'algoritmo di mutazione in modo che quei 2 benchmark si convertano in una soluzione fattibile? C'è qualche miglioramento che posso inserire nella mia funzione di fitness o nella strategia che ordina di accelerare il percorso di risoluzione?