Painting by numbers

• Topic: evolutionary algorithms, unsupervised learning

• Task A:

  1. Implement breeding of two solutions in the algorithm.

  2. Try to find a good cover for the default image of a star. Try populations with 10-100 solutions. Also try changing the number of generations and see how that affects the final result.

• Task B:

  1. Try to cover the larger star or Mona Lisa images.

  2. Study the solutions. What kinds of features are easily found by the algorithm and what is more difficult?

• Template: genetic.py

• Data:

  • starman.png

  • lisa.png

• Further reading:

  • https://en.wikipedia.org/wiki/Genetic_algorithm

  • https://en.wikipedia.org/wiki/Evolutionary_algorithm

genetic.py

class genetic.Circle(x, y, r)

A circle.

Used for building an approximation of a bitmap image.

Parameters:

• x (float) – center x coordinate

• y (float) – center y coordinate

• r (float) – radius

alter()

Make a small random change in the center and radius of the circle.

covers(x, y)

Checks if the circle covers the point (x,y).

This is true, if the distance between the given point and the center of the circle is smaller than the radius of the circle.

Parameters:

• x (float) – x coordinate

• y (float) – y coordinate

Returns:

True, if circle covers the point.

Return type:

bool

is_above_line(x0, y0, k)

Checks if the center of the circle is above the line passing through point (x0,y0) with slope k, (y-y0) = k(x-x0).

Parameters:

• x0 (float) – x coordinate

• y0 (float) – y coordinate

• k (float) – slope

Returns:

True, if the center is above the given line.

Return type:

bool

is_inside_box(x0, x1, y0, y1)

Checks if the center of the circle is inside a rectangular area defined by the points (x0,y0), (x1,y0), (x0,y1), (x1,y1).

Parameters:

• x0 (float) – x coordinate of lower left corner

• y0 (float) – y coordinate of lower left corner

• x1 (float) – x coordinate of upper right corner

• y1 (float) – y coordinate of upper right corner

Returns:

True, if the center is inside the box

Return type:

bool

randomize()

Randomize the center and radius of the circle.

class genetic.Pixel(x, y, color)

A single pixel of a black-and-white bitmap image.

Parameters:

• x (int) – x coordinate

• y (int) – y coordinate

• color (int) – 0 for white and 1 for black pixels

class genetic.Solution(reference, mom=None, dad=None)

A solution to the covering problem.

The solution is a set of circles that are supposed to cover a given set of points and not cover another set of points.

The solution also has a fitness value which determines how good a solution it is. The higher the fitness the better the solution.

Typically the solution is created as the offspring of two previous solutions. If such parent solutions are not given, a completely random solution is generated.

If a reference is given, the fitness of the created solution is immediately calculated with Solution.calculate_fitness() and saved.

Parameters:

• reference (list) – an array of Pixel objects defining the points to cover and not cover

• mom (Solution) – a parent

• dad (Solution) – another parent

add_circle(x=0, y=0, r=0)

Adds a randomly placed Circle in the solution.

black(x, y)

Checks if the solution covers the point (x,y).

Returns 1 if at least one class:Circle covers the point, and 0 if none of the circles cover the point.

The name of the method refers to the color of the pixel being covered. The solution is supposed to cover all black pixels but not white ones.

Parameters:

• x (float) – x coordinate

• y (float) – y coordinate

Returns:

1, if the solution covers the point.

Return type:

int

calculate_fitness(reference)

Calcualtes the overall fitness of the solution.

The solution is good if its circles cover all the balck pixels but none of the white ones. It’s also better to have as few circles as possible. Therefore function checks each Pixel in the reference image and adds 1 to the fitness for each correctly coverd or uncovered pixel. A penalty of 0.1 is given for each circle.

Parameters:

reference (list) – an array of Pixel objects defining the points to cover and not cover

Returns:

the fitness

Return type:

float

create_random_solution()

Create the solution as a random set of Circle objects.

This is done by repeatedly calling Solution.add_circle().

crossover(mom, dad)

Randomly pick a crossover operation.

The options are Solution.crossover_line() and Solution.crossover_box().

Parameters:

• mom (Solution) – a parent

• (Solution (dad) – a second parent

crossover_box(mom, dad)

Create the solution as a crossover of two parents.

The crossover is created as follows:

• Two random points are drawn in \([0,1] \times [0,1]\).

• Define a rectangle with these points as corners.

• Take all the Circle objects of the first parent that are in the box.

• Take all the Circle objects of the second parent that are outside the box.

• Create the new solution as a combination of these Circle objects.

Parameters:

• mom (Solution) – a parent

• dad (Solution) – a second parent

crossover_line(mom, dad)

Create the solution as a crossover of two parents.

The crossover is created as follows:

• A random point is drawn in \([0,1] \times [0,1]\).

• A random slope \(k\) is drawn.

• Define a line that passes through the point at the given slope.

• Take all the Circle objects of the first parent that are above the line.

• Take all the Circle objects of the second parent that are below the line.

• Create the new solution as a combination of these Circle objects.

Parameters:

• mom (Solution) – a parent

• dad (Solution) – a second parent

draw(fig, scale, alpha=1.0)

Draws the solution as a set of circles.

Parameters:

• fig (matplotlib figure) – the figure to draw on

• scale (float) – scaling factor to change the size of the image

• alpha (float) – the alpha (opacity) of the circles to be drawn

mutate(reference)

Randomly changes the solution.

Each Circle has a 5 % chance of being changed by Circle.alter(). In addition, there is a 20 % chance a Circle is randomly added with Solution.add_circle() and a 20 % chance a Circle is removed with Solution.remove_circle(). When a circle is added, its center point will be the coordinates of a randomly chosen black pixel.

After the mutation, the fitness of the new solution is calculated with Solution.calculate_fitness().

Parameters:

reference (list) – an array of Pixel objects defining the points to cover and not cover

remove_circle(threshold=3)

Randomly removes one Circle from the solution.

Parameters:

threshold (int) – Only remove the circle if there are more Circle s than this.

genetic.animate(history, image)

Animates the simulation.

Parameters:

• history (list) – list of populations at different times

• image (array) – number array representing the image to cover

genetic.best_solution(population, already_sorted=False)

Finds the best solution in the population.

If the list of solutions is already sorted, the function only picks population[0] as the best solution. Otherwise it first calls sort_by_fitness() to sort the solutions.

Parameters:

• population (list) – a set of Solution objects

• already_sorted (bool) – if True, the best solution is assumed to be the first in population

Returns:

the best solution

Return type:

Solution

genetic.breed(population, pop_size, reference)

Fill the population with new solutions by breeding the members of the previous generation.

Breeding is done by randomly choosing two different solutions from population and combining them with Solution.crossover(). This creates offspring that may potentially combine the good traits of their parents.

In addition, the offspring are allowed to Solution.mutate() in order to add variance.

Note

This function is incomplete!

Parameters:

• population (list) – a set of Solution objects

• pop_size (int) – size of the population in the end

• reference (list) – an array of Pixel objects defining the points to cover and not cover

genetic.draw(frame, history, image)

Draws the populations.

Used for animation.

Parameters:

• frame (int) – index of the frame to draw

• history (list) – list of populations at different times

• image (array) – number array representing the image to cover

genetic.draw_population_to_file(population, reference, image, filename)

Takes an entire set of Solution objects and draws them superimposed on top of each other.

Parameters:

• population (list) – a set of Solution objects

• reference (list) – an array of Pixel objects defining the points to cover and not cover

• image (array) – number array representing the image to cover

• filename (str) – name of the file tow rite

genetic.draw_solution(image, sol)

Draws the image as a bitmap and the solution as a collection of circles.

Parameters:

• image (array) – number array representing the image to cover

• sol (Solution) – the solution to visualize

genetic.fill_population(population, pop_size, reference)

Fills the population with random solutions up to the given size.

Parameters:

• population (list) – a set of Solution objects

• pop_size (int) – the number of solutions in the populations in the end

• reference (list) – an array of Pixel objects defining the points to cover and not cover

genetic.kill_the_unfit(population, kill_percentage=0.5)

Kills a given portion of the population.

The population is first sorted via sort_by_fitness() so that the best solutions are in the beginning of the list. Then, the list is truncated from the end.

If the population is very homogenous, individuals are killed randomly so that the same solutions don’t always survive.

By default, half of the solutions are killed. This fraction can be adjusted using kill_percentage. This number must be strictly larger than 0 and smaller than 1.

Parameters:

• population (list) – a set of Solution objects

• kill_percentage (float) – The fraction of solutions to kill.

genetic.main(n_runs, n_gens, pop_size, image_file, read_from_file=False)

The main program.

Reads the image to and runs an evolutionary optimization to create a set of circles that approximates the image.

After the optimization, the solution is drawn and saved.

Parameters:

• n_runs (int) – number of optimization runs

• n_gens (int) – number of generations in a run

• pop_size (int) – population size

• image_file (str) – name of the image file

• read_from_file (bool) – if True, an existing solutions is read from best_solution.csv

genetic.mutate_all(population, reference)

Mutates all solutions in the population.

If the population becomes very homogenous, crossover operations do not change it much and mutations are unlikely to survive. Therefore one may mutate all solutions to create diversity.

Parameters:

• population (list) – a set of Solution objects

• reference (list) – an array of Pixel objects defining the points to cover and not cover

genetic.print_progress(step, total)

Prints a progress bar.

Parameters:

• step (int) – progress counter

• total (int) – counter at completion

genetic.read_image(filename=None)

Tries to read a black and white bitmap image and create an array of Pixel objects based on it.

If reading the file fails, the function returns a default array representing a star.

Parameters:

filename (str) – name of the file to read

Returns:

the image as (number array, Pixel object array)

Return type:

array, array

genetic.read_solution_from_file(reference, filename)

Reads a Solution from a file.

The file should contain the center coordinates and radii of the circles that make up the solution, separated by commas, as recorded by write_solution_to_file().

Parameters:

• reference (list) – an array of Pixel objects defining the points to cover and not cover

• filename (str) – name of the file to read

Returns:

the solution constructed from the information in the file

Return type:

Solution

genetic.run_evolution(population, reference, n_generations, kill_percentage=0.5)

Runs the evolutionary optimization algorithm.

The algorithm tries to find an optimal Solution by taking a population of solutions, killing the least fit ones with kill_the_unfit() and allowing the survivors to breed(), creating new solutions.

Parameters:

• population (list) – a set of Solution objects

• reference (list) – an array of Pixel objects defining the points to cover and not cover

• n_generations (int) – number of generations (iterations)

• kill_percentage (float) – the fraction of solutions to kill each generation

Returns:

fitness of the best solution after each generation, population history

Return type:

list, list

genetic.sort_by_fitness(population)

Sorts the population from best to worst.

The sorting is done in place by changing the given list of solutions.

After the operation, the best solution will be population[0].

Parameters:

population (list) – a set of Solution objects

genetic.write_solution_to_file(solution, filename)

Writes the center coordinates and radii of the circles of the solution to a file.

Parameters:

• solution (Solution) – the solution to record

• filename (str) – name of the file to write