DocumentCode :
2917417
Title :
Analysis and extension of the Inc* on the satisfiability testing problem
Author :
Bader-El-Den, Mohamed ; Poli, Riccardo
Author_Institution :
Dept. of Comput. & Electron. Syst., Univ. of Essex, Colchester
fYear :
2008
fDate :
1-6 June 2008
Firstpage :
3342
Lastpage :
3349
Abstract :
Inc* is a general algorithm that can be used in conjunction with any local search heuristic and that has the potential to substantially improve the overall performance of the heuristic. The general idea of the algorithm is the following. Rather than attempting to directly solve a difficult problem, the algorithm dynamically chooses a smaller instance of the problem, and then increases the size of the instance only after the previous simplified instances have been solved, until the full size of the problem is reached. Genetic programming is used to discover new strategies for Inc*. Preliminary experiments on the satisfiability problem (SAT) problem have shown that Inc* is a competitive approach. In this paper we enhance Inc* and we experimentally test it on larger set of benchmarks, including big instances of SAT. Furthermore, we provide an analysis of the algorithmpsilas behaviour.
Keywords :
computational complexity; genetic algorithms; search problems; Inc; genetic programming; local search heuristic; satisfiability testing problem; Algorithm design and analysis; Benchmark testing; Gain; Genetic programming; Heuristic algorithms; Labeling; Random variables; Traveling salesman problems;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on
Conference_Location :
Hong Kong
Print_ISBN :
978-1-4244-1822-0
Electronic_ISBN :
978-1-4244-1823-7
Type :
conf
DOI :
10.1109/CEC.2008.4631250
Filename :
4631250
Link To Document :
بازگشت