263 — Solving Sudoku with Ant Colony Optimisation

Lloyd & Amos (1805.03545)

Read on 10 May 2018
#machine-learning  #AI  #sudoku  #math  #ants  #insect  #ant-colony-optimization  #map-coloring  #graph-traversal  #graph-theory  #graphs  #optimization  #np-hard 

Ant colony optimization (ACO) is a family of algorithms in which individual, simple automaton agents navigate a graph according to a naïve, simple ruleset — and out of which complex emergent behaviors solve a more complex task.

ACOs are great for tasks that don’t have clear graph-traversal answers, such as complex mathematical challenges or challenges of prohibitively large graph-scale.

Sudokus are NP-complete, and can be represented as a graph traversal, or map-coloring problem, where peers — cells that are prohibited by the rules of sudoku from having the same value — are connected to non-peers (all other cells).

Ants are each given a copy of the puzzle, onto which they attempt to “fix” as many values as possible. They drop “pheromone” when they have high confidence of having made a correct value fixation, and which attracts ants on further iterations to attempt the same initial steps. This value is normalized to the global highest-pheromone-concentration but gradually “evaporated,” which prevents the algorithm from converging on a local maximum (“stagnation”).

Using biology to solve complex problems is becoming increasingly popular, and I’ve read a bit about similar methods in the past ([#91], [#6]). This motion-coordination work is particularly exciting as we get closer to high-speed multi-core hardware.