The use of randomness in local search is a widespread technique applied to improve algorithm performance. A property of noise strategies, i.e., strategies that make use of randomness, is that there is an optimal amount of randomness that enables the algorithm to achieve on optimal performance. The same property holds also for another technique introduced in local search, that is the parallel application of more than one local move. In this work, we investigate the outcome of the combination of both the techniques. We show that in the case of random 3-SAT instances a synergistic effect comes into play and the resulting technique outperforms the single ones.
Random walk and parallelism in local search / A.Roli; M.Blesa; C.Blum. - ELETTRONICO. - (2005), pp. 811-816. (Intervento presentato al convegno MIC2005 - The 6th metaheuristics international conference tenutosi a Vienna nel August 22-26).
Random walk and parallelism in local search
ROLI, ANDREA;
2005
Abstract
The use of randomness in local search is a widespread technique applied to improve algorithm performance. A property of noise strategies, i.e., strategies that make use of randomness, is that there is an optimal amount of randomness that enables the algorithm to achieve on optimal performance. The same property holds also for another technique introduced in local search, that is the parallel application of more than one local move. In this work, we investigate the outcome of the combination of both the techniques. We show that in the case of random 3-SAT instances a synergistic effect comes into play and the resulting technique outperforms the single ones.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.