Abstract
Inc (star) 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 algorithm's behaviour.
| Original language | English |
|---|---|
| Title of host publication | Evolutionary Computation, 2008. CEC 2008. (IEEE World Congress on Computational Intelligence). IEEE Congress on |
| Place of Publication | Hong Kong |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 3342-3349 |
| Number of pages | 8 |
| ISBN (Print) | 9781424418220 |
| Publication status | Published - Jun 2008 |
| Event | 2008 IEEE World Congress on Computational Intelligence - Hong Kong Duration: 1 Jun 2008 → 6 Jun 2008 |
Conference
| Conference | 2008 IEEE World Congress on Computational Intelligence |
|---|---|
| Period | 1/06/08 → 6/06/08 |
Keywords
- Genetic Programming
- SAT
- Combinatorial Optimization