Evolution Algorithm to solve Nonograms

Question

I want to try to solve nonograms using Evolutionary Algorithm. I represent fitness as amount of constraints that satisfy the board. For example board 10X10 got 20 constraints ( 10 left, 10 top)

So my maximum Fitness is 20.

My main problem is that algorithm in most cases stuck in local maximum( with 15-18 fitness) and i don't know how i can prevent it or jump in right direction.

Still sometimes algorithm manage to solve the puzzle.

I use simple crossover( x rows from first individual + y rows from second) And mutation that change 1 random cell.

Any ideas for better mutations or other techniques that can help me with local maximum problem?

Many thanks!

Answer 1

(adding on Sisnett's good answer)

Any ideas for better mutations or other techniques that can help me with local maximum problem?

You can adopt the standard mutation / crossover operators, probably the problem representation and fitness function have to be improved.

Here I'm just setting out an example. More details and a possible C++ implementation (based on the Vita framework) can be found on Github.

Individual representation

A candidate solution (i.e. an individual of the GAs population) can be encoded as a sequence of integers.

Consider the following problem:

. # # # . . . .  3
# # . # . . . .  2 1
. # # # . . # #  3 2
. . # # . . # #  2 2
. . # # # # # #  6
# . # # # # # .  1 5
# # # # # # . .  6
. . . . # . . .  1
. . . # # . . .  2
1 3 1 7 5 3 4 3
2 1 5 1

the pattern can be encoded (column-order) as:

COLUMN (zero-based indexing)
| 0  |  1  |  2  |  3  | 4| 5| 6| 7|

{1, 2, 0, 2, 0, 0, 0, 0, 4, 4, 2, 2}

 ^  ^                          ^  ^
 |  |                          |  +-- last block (size 3)
 |  |                          +----- second to last block (size 4)
 .  .                          .  .
 .  .                          .  .
 .  .                          .  .
 |  +-------------------------------- second block (size 2)
 +----------------------------------- first block (size 1)

where each number represents the distance of a block from the first allowed placing position. In total there are 12 blocks on 8 columns.

The encoding by column is an arbitrary choice. The same pattern could be represented (row-order) as:

{1, 0, 0, 1, 1, 2, 1, 2, 0, 0, 0, 4, 3}

This time there are 13 blocks on 9 rows.

Depending on the problem structure (i.e. number and type of the clues) one approach could be better than the other (from a performance point of view).

Anyway it's always possible to:

1. swap row and column clues
2. solve the resulting problem
3. transpose the solution matrix to get the solution of the original problem

---

Note that the representation allows invalid individuals. Consider the following column:

.
.
.
.
1
2

The only solution is {0,0}:

#
.
#
#
1
2

but the representation also allows {0,1}, {0,2}, {0,3}, ... {3,2}, {3,3}.

To "keep it simple" invalid integers can be mapped to a valid range (e.g. via the modulo operator) thus creating a separation between the genotype (the list of integers) and the phenotype (the real position of blocks on the board).

This is very similar to the Grammatical Evolution scheme in which the objects the search algorithm operates on and what the fitness evaluation function interprets are distinct.

Fitness function

First of all you need a decoding function that, given the genome, returns a true/false matrix.

With the proposed representation column constraints (i.e. column clues) are already satisfied. The fitness function measures the performance of an individual considering only row-clues.

E.g.

Solution:                Candidate solution:
                         {1,2,0,2,0,0,0,0,4,4,2,0}

. # # # . . . .  3       . # # # . . . #  3 1    <-- ERROR
# # . # . . . .  2 1     # # . # . . . #  2 1 1  <-- ERROR
. # # # . . # #  3 2     . # # # . . # #  3 2
. . # # . . # #  2 2     . . # # . . # .  2 1    <-- ERROR
. . # # # # # #  6       . . # # # # # .  5      <-- ERROR
# . # # # # # .  1 5     # . # # # # # .  1 5
# # # # # # . .  6       # # # # # # . .  6
. . . . # . . .  1       . . . . # . . .  1
. . . # # . . .  2       . . . # # . . .  2
1 3 1 7 5 3 4 3          1 3 1 7 5 3 4 3
2 1 5 1                  2 1 5 1

the block on the last column is misplaced:

ROW  CORRECT  WRONG     DELTA
0     [3]     [3,1]     |3-3| + |0-1| = 1
1     [2,1]   [2,1,1]   |2-2| + |1-1| + |0-1| = 1
3     [2,2]   [2,1]     |2-2| + |2-1| = 1
4     [6]     [5]       |6-5| = 1

FITNESS = -sum(delta_i) = -4

The fitness function computes the distance between the correct and wrong sequences, matching elements by order and taking their absolute difference.

Notes

GAs tend to produce good but sub-optimal solutions and this behaviour is acceptable only for some combinatorial optimization problems.

The proposed representation is good enough to detect biases in low-order schemas and, combining information, eventually converges (I've played with 30x30 nonograms).

There are further improvements but this should be a good starting point.

Answer 2

The problem here is GA is not very good for constraint satisfaction problem as for example i give a board that is satisfied by only one configuration and GA as we know will try different permutations to get to the solution . The probability that you get to solution in permutation is (1/2^100) for 10X10 nonograms so it is very low probability that you get the solution even if you skip the local minimum. GA is very useful for optimization problems like knapsack or TSP where you have a solution but need to improve it.

Solution :-

Use Mixed integer and constraint programming

Answer 3

I disagree with the previous response, GA's are really good with constraint satisfacti and while is true there is only 1 answer in 2^100 options, you're not doing a random search so the 1/2^100 probability is not entirely correct.

The important thing to keep in mind when talking about GA is that they 'build up' the solution, by probing the search space and seeing how good different options are. I think your main issue is your fitness, having only 20 values for fitness makes it really hard for the Algorithm to differentiate between a 'good' solution from a 'good++' solution, and that's why you end up in 15-18 range.

Creating GOOD fitness function is one of the hardest problems in GA design, and usually require several attempts to get it right, let see an example to explain what I mean.

Take the 2x2 Nonogram.

  2 1
2|_|_|
1|_|_|

The solution:

  2 1
2|X|_|
1|_|_|

would get 0 points from your fitness function, because it satisfies 0 constraints.

The solution:

  2 1
2|_|_|
1|_|X|

Would get 2 points from your fitness function, but as you might have already realized, the first one is 'a step' towards the solution, the second one is going to get stuck right there. Clearly your fitness function requires a little revisiting and tuning, so you can take the solutions that are 'heading the right way' and build on them (by mutation or crossover, which by how you describe them I think are fine).

Answer 4

This is a python code solving a nonogram table. this is it:

import numpy as np
from itertools import product
from datetime import datetime

row_constraints = ([7,2], [5,1], [3], [15], [2], [15], [1], [1], [13], [3,1,1,1], [1,3,1,3], [1,3,3], [1,1,1], [1,1,1],\
               [1,6], [1,8,1], [1,2,2,1], [2,2,2], [4,3], [14])
column_constraints = ([8], [6,1,1], [4,1,2,4,2], [2,1,1,3,5], [2,1,1,1,1,3], [1,1,1,1,2,2,2], [1,1,1,1,3,3,1], \
                   [1,1,3,3,1], [1,1,1,2,1,1], [1,1,1,2,1,1], [1,1,3,3,1], [1,1,1,2,3,1], [1,1,1,2,2,2], [1,1,1,1,2,3], [2,1,1,3,5])



def is_valid_solution(new_solution, list_of_cols_to_check, list_of_rows_to_check, col_or_row):

    if col_or_row == 'row':
        for col in list_of_cols_to_check:
            arr = new_solution[:, col]
            if get_list_of_strip_sizes(arr, 20) != column_constraints[col]:
                return False
    else:
        for row in list_of_rows_to_check:
            arr = new_solution[row, :]
            if get_list_of_strip_sizes(arr, 15) != row_constraints[row]:
                return False

    return True


def get_list_of_strip_sizes(arr, length):
    list_of_strips = []
    i = 0
    while i < length:
        while i < length and arr[i] == 0:
            i += 1

        if i == length:
            return list_of_strips

        strip_length = 0
        while i < length and arr[i] == 1:
            i += 1
            strip_length += 1

        list_of_strips.append(strip_length)

        if i == length:
            return list_of_strips


def is_legal_product_setting(potentially_legal_line, constraints):
    for index in range(1, len(potentially_legal_line)):
        if(potentially_legal_line[index] <= potentially_legal_line[index-1] + constraints[index-1]):
            return False
    return True



def create_lines_with_constraints(length=15, constraints=[]):
    list_of_ranges = []
    min_value = 0
    max_value = length - sum(constraints) - len(constraints) + 1
    for constraint in constraints:
        list_of_ranges.append(range(min_value, max_value + 1))
        min_value += constraint + 1
        max_value += constraint + 1

    list_of_legal_lines = []
    for potentially_legal_line in product(*list_of_ranges):

        # skip illegal products
        if is_legal_product_setting(potentially_legal_line, constraints) == False:
            continue

        # get blanks
        line = np.zeros(length)
        for index, start_position in enumerate(potentially_legal_line):
            for cell in range(start_position, start_position + constraints[index]):
                line[cell] = 1

        list_of_legal_lines.append(line)

    return list_of_legal_lines


def add_new_line(col_or_row, index, line_length, constraint, list_of_cols_to_check, list_of_rows_to_check, list_of_potential_solutions):
    new_list_of_valid_solutions = []

    potential_new_lines = create_lines_with_constraints(length=line_length, constraints=constraint)

    for solution in list_of_potential_solutions:

        for potential_new_line in potential_new_lines:

            if col_or_row == 'col':
                before = np.reshape(solution[:, 0:index], (20, index))
                inject = np.reshape(potential_new_line, (20, 1))
                after_dim = 15 - index - 1
                after = np.reshape(solution[:, index + 1:], (20, after_dim))
                new_solution = np.concatenate([before, inject, after], axis=1)
            else:
                before = np.reshape(solution[0:index, :], (index, 15))
                inject = np.reshape(potential_new_line, (1, 15))
                after_dim = 20 - index - 1
                after = np.reshape(solution[index + 1:, :], (after_dim, 15))
                new_solution = np.concatenate([before, inject, after], axis=0)

            if is_valid_solution(new_solution, list_of_cols_to_check, list_of_rows_to_check, col_or_row):
                new_list_of_valid_solutions.append(new_solution)

    return new_list_of_valid_solutions
def main():
    # initial solution a solution is a matrix

    list_of_potential_solutions = [np.zeros((20, 15), dtype=int)]

    list_of_cols_to_check = []
    list_of_rows_to_check = []
    list_of_lines_to_check = [('row', 3), ('col', 0), ('row', 5), ('col', 1), 
                              ('row', 8), ('col', 2), ('row', 19), ('col', 3), 
                              ('row', 15), ('col', 10), ('row', 0), ('col', 14), 
                              ('row', 10), ('col', 6), ('row', 4), ('col', 5), 
                              ('row', 1), ('col', 13), ('row', 9), ('col', 4), 
                              ('row', 7), ('col', 7), ('row', 11), ('col', 12), 
                              ('row', 18), ('col', 11), ('row', 2), ('col', 8), 
                              ('row', 17), ('col', 9), 
                              ('row', 16), ('row', 13), ('row', 12), ('row', 14), ('row', 6)]
    for cell in list_of_lines_to_check:

        if (cell[0]=='col'):
            col_index = cell[1]
            list_of_cols_to_check.append(col_index)
            list_of_potential_solutions = add_new_line('col', col_index, 20, column_constraints[col_index], list_of_cols_to_check, list_of_rows_to_check, list_of_potential_solutions)
        else:
            row_index = cell[1]
            list_of_rows_to_check.append(row_index)
            list_of_potential_solutions = add_new_line('row', row_index, 15, row_constraints[row_index], list_of_cols_to_check, list_of_rows_to_check, list_of_potential_solutions)

        print([cell, len(list_of_potential_solutions), datetime.now().hour, datetime.now().minute, datetime.now().second])

    print(list_of_potential_solutions)



if __name__ == "__main__":
    main()

That's it!