Sto imparando la meta-euristica del GRASP (Greedy Randomized Adaptive Search).
Da quanto ho capito, GRASP si basa su due fasi principali. Il primo:
Construct a initial solution based on a greedy and random strategy
e il secondo:
Construct a local search on the previous found solution
La domanda che ho è per la prima fase. Devo creare una soluzione fattibile ?
Sono autorizzato forse a creare una soluzione non fattibile nella prima fase dell'algoritmo, e quindi utilizzare la ricerca locale per trovare una soluzione fattibile ?
EDIT:
Fondamentalmente ho il problema Peso parziale parziale SAT. L'idea è che devo massimizzare la somma di tutte le clausole soft soddisfatte, mentre allo stesso tempo soddisfare tutte le clausole hard.
Quello che stavo pensando è creare una soluzione iniziale (forse irrealizzabile) che cerchi di massimizzare il numero di clausole soft soddisfatte. Successivamente, desidero utilizzare una ricerca locale per ottimizzare ulteriormente la soluzione o renderla fattibile se necessario.
Voglio sapere se questa è una strategia valida, perché la costruzione iniziale potrebbe creare una soluzione non fattibile.