Abstract
Sudoku Evolution is a program written for the comparison of metaheuristics. The main aim of the underlying project was to implement a program capable of comparing algorithms related to artificial intelligence. Four population-based approaches were chosen, genetic algorithms (GA), geometric particle swarm optimization (GPSO), Bee Colony Optimization (BCO), artificial immune system (AIS) with somatic hypermutation as well as two algorithms, simulated and quantum annealing (SA & QA), based on probabilistic local search. All of them were implemented based on the work of Alberto Moraglio. He provides a general geometric framework for evolutionary algorithms. Crossover and mutation operators are representation-independent and defined as functions of a metric distance in the search space. Sudoku was used as the testbed for comparison. It is especially interesting as it is a combinatorial and NP-complete problem where valid grids have only one solution. This makes them interesting for optimization algorithms. The algorithms were compared on nine Sudokus with 3 different difficulty ratings. Each of them was executed ten times with preliminary tuned parameters. They were compared based on the average fitness value achieved over all grids and the number of successful solving attempts. SA and GPSO were the best approaches followed by QA and BCO.
| Original language | English |
|---|---|
| Title of host publication | 2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC |
| Publisher | IEEE |
| Pages | 173-185 |
| Number of pages | 13 |
| ISBN (Print) | 9781424444601, 9781424444595 |
| DOIs | |
| Publication status | Published - 23 Oct 2009 |
| Externally published | Yes |
| Event | 1st International IEEE Consumer Electronic Society's Games Innovation Conference - London, United Kingdom Duration: 25 Aug 2009 → 28 Aug 2009 Conference number: 1 |
Publication series
| Name | |
|---|---|
| ISSN (Print) | 2166-6741 |
| ISSN (Electronic) | 2166-675X |
Conference
| Conference | 1st International IEEE Consumer Electronic Society's Games Innovation Conference |
|---|---|
| Abbreviated title | ICE-GiC 09 |
| Country | United Kingdom |
| City | London |
| Period | 25/08/09 → 28/08/09 |
Fingerprint
Cite this
}
Sudoku Evolution : Solving Sudoku with AI-related Algorithm. / Jilg, Johannes; Carter, Jenny.
2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC. IEEE, 2009. p. 173-185 5293614.Research output: Chapter in Book/Report/Conference proceeding › Conference contribution
TY - GEN
T1 - Sudoku Evolution
T2 - Solving Sudoku with AI-related Algorithm
AU - Jilg, Johannes
AU - Carter, Jenny
PY - 2009/10/23
Y1 - 2009/10/23
N2 - Sudoku Evolution is a program written for the comparison of metaheuristics. The main aim of the underlying project was to implement a program capable of comparing algorithms related to artificial intelligence. Four population-based approaches were chosen, genetic algorithms (GA), geometric particle swarm optimization (GPSO), Bee Colony Optimization (BCO), artificial immune system (AIS) with somatic hypermutation as well as two algorithms, simulated and quantum annealing (SA & QA), based on probabilistic local search. All of them were implemented based on the work of Alberto Moraglio. He provides a general geometric framework for evolutionary algorithms. Crossover and mutation operators are representation-independent and defined as functions of a metric distance in the search space. Sudoku was used as the testbed for comparison. It is especially interesting as it is a combinatorial and NP-complete problem where valid grids have only one solution. This makes them interesting for optimization algorithms. The algorithms were compared on nine Sudokus with 3 different difficulty ratings. Each of them was executed ten times with preliminary tuned parameters. They were compared based on the average fitness value achieved over all grids and the number of successful solving attempts. SA and GPSO were the best approaches followed by QA and BCO.
AB - Sudoku Evolution is a program written for the comparison of metaheuristics. The main aim of the underlying project was to implement a program capable of comparing algorithms related to artificial intelligence. Four population-based approaches were chosen, genetic algorithms (GA), geometric particle swarm optimization (GPSO), Bee Colony Optimization (BCO), artificial immune system (AIS) with somatic hypermutation as well as two algorithms, simulated and quantum annealing (SA & QA), based on probabilistic local search. All of them were implemented based on the work of Alberto Moraglio. He provides a general geometric framework for evolutionary algorithms. Crossover and mutation operators are representation-independent and defined as functions of a metric distance in the search space. Sudoku was used as the testbed for comparison. It is especially interesting as it is a combinatorial and NP-complete problem where valid grids have only one solution. This makes them interesting for optimization algorithms. The algorithms were compared on nine Sudokus with 3 different difficulty ratings. Each of them was executed ten times with preliminary tuned parameters. They were compared based on the average fitness value achieved over all grids and the number of successful solving attempts. SA and GPSO were the best approaches followed by QA and BCO.
KW - Algorithms
KW - Artificial immune system
KW - Artificial intelligence
KW - Bee colony optimization
KW - Geometric particle swarm optimization
KW - Quantum annealing
KW - Sudoku
UR - http://www.scopus.com/inward/record.url?scp=74349119413&partnerID=8YFLogxK
U2 - 10.1109/ICEGIC.2009.5293614
DO - 10.1109/ICEGIC.2009.5293614
M3 - Conference contribution
AN - SCOPUS:74349119413
SN - 9781424444601
SN - 9781424444595
SP - 173
EP - 185
BT - 2009 International IEEE Consumer Electronics Society's Games Innovations Conference, ICE-GiC
PB - IEEE
ER -