Resolution of a Combinatorial Problem using Cultural Algorithms

Alberto Ochoa, Julio Ponce, Arturo Hernández, Liang LiJournal of Computers 2009 · DOI

TL;DR

This paper tackles the challenging combinatorial optimization problem of solving Japanese puzzles (nonograms) using a novel Cultural Algorithm. By adapting an evolutionary algorithm with a belief space and local search, they demonstrate a robust method for reconstructing complex puzzle solutions, even those notoriously difficult for purely logical approaches.

What Problem Does This Paper Address?

Japanese puzzles, also known as nonograms, are logic puzzles where players fill in cells on a grid based on numerical clues for rows and columns, revealing a hidden image. While seemingly simple, these puzzles represent a constrained combinatorial optimization problem. Finding the optimal solution, especially for complex puzzles, can be computationally intensive and often requires intricate logical deduction or brute-force methods. Existing approaches might struggle with puzzles that have unique solutions but are difficult to derive through purely logical means, or those that require significant "branching" in deduction. This paper aims to provide a more systematic and robust computational approach to solving these puzzles by leveraging bio-inspired algorithms.

Methods

The core of the paper is the adaptation of a Cultural Algorithm (CA) to solve Japanese puzzles. CAs are a type of bio-inspired algorithm that, in addition to a population of candidate solutions, maintain a "belief space" representing collective knowledge or learned heuristics.

Here's a breakdown of their approach:

  • Cultural Algorithm Framework: They use a CA structure that involves a population of candidate puzzle solutions and a belief space. The belief space stores learned information that guides the evolution of the population.
  • Evaluation Function: A key contribution is the definition of an objective function that quantifies the deviation of a candidate solution from the puzzle's row and column constraints. This function measures the difference between the desired number of black (filled) and white (empty) cells and their actual count in each line. A crucial aspect is defining this deviation in terms of "bitflip operations" – the minimum number of cell changes needed to satisfy a line's description. This is computed efficiently using dynamic programming.
  • Network Flow for Constraints: To ensure that candidate solutions always adhere to the prescribed row and column projections (i.e., satisfy the puzzle's basic rules), they employ a network flow model. This model maps the puzzle to a directed graph where flow through arcs represents cell states, guaranteeing that any generated solution is valid.
  • Crossover and Mutation Operators: They design specialized crossover and mutation operators. The crossover operator mixes features from two parent solutions, aiming to preserve local structures. The mutation operator uses a similar principle, distorting small parts of an image while ensuring adherence to constraints via network flow and local search.
  • Local Search (Hillclimbing): After crossover and mutation, a local search (stochastic hillclimb) is applied. This step refines candidate solutions by iteratively swapping black and white cells to improve the evaluation function, pushing solutions towards local optima. This is a key component of the CA's belief space update.

Datasets

Not discussed in the paper. The paper uses example Japanese puzzles for demonstration and evaluation, including a 20x20 puzzle known for its unique solution.

Key Insights and Ideas

  • Japanese Puzzles as Constrained Optimization: The paper frames Japanese puzzles not just as logic games but as formal constrained combinatorial optimization problems, making them amenable to algorithmic solutions.
  • Bitflip Distance for Evaluation: Defining the "distance" of a line's solution to its description using the minimum bitflip operations is an intuitive and effective way to create an evaluation function that captures the essence of the puzzle's constraints.
  • Belief Space for Heuristics: The use of a Cultural Algorithm's belief space allows the system to learn and incorporate heuristics derived from successful solutions, guiding the search more effectively than a standard evolutionary algorithm.
  • Network Flow for Constraint Satisfaction: Employing network flow to guarantee that all candidate solutions satisfy the puzzle's projections is a powerful technique for maintaining feasibility throughout the evolutionary process.
  • Synergy of Evolution and Local Search: The combination of evolutionary operators (crossover, mutation) with local search (hillclimbing) creates a robust search strategy that can explore the solution space broadly and then refine promising candidates.

Key Results

The authors successfully implemented their Cultural Algorithm and tested it on a 20x20 Japanese puzzle known to have a unique solution. The algorithm reconstructed the image perfectly. While the reconstruction process took 80 minutes on a Pentium IV 2.4 GHz processor after 27 epochs, the authors highlight this as a very positive result. They note that the reconstructed image, while different from the original, adhered to nearly all line descriptions, and that this particular puzzle is notoriously difficult to solve using purely logical reasoning, often requiring significant "branching."

Limitations and Future Work

  • Computational Time: The 80-minute runtime for a single 20x20 puzzle, while deemed positive given the difficulty, indicates that computational efficiency for larger or more complex puzzles might be a limitation.
  • Future Work: The authors suggest future research should include a detailed analysis of the algorithm's performance on puzzles of varying difficulty levels and different types (e.g., puzzles with more than two colors). They also note that the fact their evolutionary algorithm can solve these puzzles, for which it wasn't specifically designed, demonstrates its versatility.

Summary updated

Abstract

Many problems involve not structured environments which can be solved from the perspective of Bioinspired Algorithms (Cultural Algorithms). In this paper, a proposed algorithm is used to resolve a famous game known as Japanese puzzles, which are analyzed for obtain the optimal solution. The authors show that Japanese Puzzles are constrained combinatorial optimization problems, which can be solved using Cultural Algorithms. Other features, such the use of a belief space involve many proposed solutions and local search heuristics; can also be taught using these puzzles.
BibTeX
@article{ochoa2009resolution,
  author = {Alberto Ochoa and Julio Ponce and Arturo Hernández and Liang Li},
  title = {{Resolution of a Combinatorial Problem using Cultural Algorithms}},
  journal = {Journal of Computers},
  year = {2009},
  doi = {10.4304/jcp.4.8.738-741},
}
Figure