My genetic algorithm won't converge/reaches local minima

Question

I've been struggling with this little project for a while and I'd really appreciate your help.

I'm trying to build a genetic algorithm for drawing pictures using transparent shapes (triangles), something like this: https://chriscummins.cc/s/genetics/, but I've tried a lot of different hyperparameters and different techniques and I can't really get any convergence like the website above does. Sometimes it'll run for a long time and it'll still get stuck in stuff like the image below, which seems like it's converged to something, since there are not many different individuals, but it's not quite there!

The algorithm works basically likes this:

• Every individual in the population is a Painting on a empty/black canvas of a fixed number of triangles.
• Fitness of an individual is calculated by doing a pixel-wise Mean Absolute Error between an individual's painting and the target image.
• I use tournament selection to select which individuals can be chosen to breed to produce the next generation's individuals.
• Crossover between two paintings is basically randomly selecting half of each parent's genes, which is their triangles.
• The mutation consists of basically applying some change to the vertices' coordinates of each triangle in the painting.
• I apply mutations to the children generation.
• The best of each generation always automatically advances to the next generation. (Elitism)

I'll attach code below, hope it's understandable, tried to document it to make it easier for people to help me out.

Here is my Triangle (Gene) class:

class Triangle:

    def __init__(self, image):
        '''
        Parameters
        ------------

        image: PIL.Image
            Image where the triangle will be drawn.

            This must be passed in order for the random triangle's vertices
            to have correct coordinates.
        '''
        self.max_width, self.max_height = image.size
        self.vertices = self.random_polygon()

        # RGBA
        self.color = Triangle.random_color()

    def __str__(self):
        return f'Vertices: {[(round(x, 2), round(y, 2)) for (x, y) in self.vertices]} | Color: {self.color}'

    def draw(self, draw_object, fill=True) -> None:
        '''
        Method to draw the polygon using a Pillow ImageDraw.Draw object

        Parameters
        ------------

        draw_object: ImageDraw.Draw
            Object to draw the image

        fill: bool
            Whether to fill the polygon or just outline it.

        '''

        if fill:
            draw_object.polygon(self.vertices, fill=self.color)
        else:
            draw_object.polygon(self.vertices, outline=self.color)

    def noise(self, ratio):
        '''Generate noise into this object'''

        def vertex_noise(vertex):
            x, y = vertex
            x = random.uniform(max(0.0, x - ratio * x), min(self.max_width, x + ratio * x))
            y = random.uniform(max(0.0, y - ratio * y), min(self.max_height, y + ratio * y))
            return (x, y)

        for i in range(3):
            self.vertices[i] = vertex_noise(self.vertices[i])

        return self

    def random_polygon(self) -> list:
        '''Generate a random triangle in the form [(x, y), (x, y), (x, y)]'''

        def random_vertex() -> tuple:
            x = random.uniform(0.0, self.max_width)
            y = random.uniform(0.0, self.max_height)
            return (x, y)

        return [random_vertex() for _ in range(3)]

    @classmethod
    def random_color(cls) -> tuple:
        '''Generate a random RGBA color tuple'''
        def _random(lower, upper):
            return random.randint(lower, upper)

        return (_random(0, 255), _random(0, 255), _random(0, 255), _random(85, 255))

    @classmethod
    def collection(cls, size, image) -> list:
        '''
        Generate collection of triangles

        Parameters
        ------------

        size: int
            Number of triangles to generate

        image: PIL.Image
            Image to use for the Triangle constructor.
            See help(Triangle) for more info.

        Return
        --------

        collection: list
            Collection of polygons.

        '''
        return [cls(image) for _ in range(size)]   

And here's the Painting (Individual) class:

class Painting:
    def __init__(self, num_objects, img):
        '''
        Parameters
        ------------

        num_objects: int
            Number of triangles in each painting (this is the DNA size).

        img: PIL.Image
            Target image that we're trying to approximate

        '''
        self.polygons = Triangle.collection(num_objects, img)
        self.target = img
        self.fitness = float('inf')

    def __lt__(self, other):
        return self.fitness < other.fitness

    def __del__(self):
        if hasattr(self, 'canvas'):
            self.canvas.close() 

    def fit(self):
        '''Fits individual's painted canvas against target image'''
        self.paint()
        self.fitness = self._error(self.canvas, self.target)   
        return self

    @classmethod
    def crossover(cls, indA, indB, ratio):
        '''
        Reproduces two painting objects and generates a painting child
        by randomly choosing genes from each parent in some given proportion.

        Parameters
        ------------

        indA: Painting

        indB: Painting

        ratio: float
            Proportion of genes to be taken from the father object.

        Return
        ---------

        child: Painting
        '''
        if len(indA.polygons) != len(indB.polygons):
            raise ValueError('Parents\' number of polygons don\'t match.')

        if indA.target != indB.target:
            raise ValueError('Parents\' target images don\'t match.')

        num_objects = len(indA.polygons)
        target = indA.target
        child = cls(num_objects, target)

        indA_ratio = int(ratio * num_objects)

        # Crossover Parents' triangles
        child.polygons = deepcopy(random.sample(indA.polygons, k=indA_ratio))
        child.polygons.extend(deepcopy(random.sample(indB.polygons, k=num_objects-indA_ratio)))

        return child

    @classmethod
    def random_population(cls, size, num_objs, img):
        '''Generates a random population of paintings'''
        return [cls(num_objs, img) for _ in range(size)]

    def mutate(self, mutation_chance, mutation_ratio):
        '''
        Applies noise to the painting objects' genes, which is basically a "mutation"

        Parameters
        ------------

        mutation_chance: float
            chance that each gene will be mutated

        mutation_ratio: float
            intensity of the mutation that will be caused in case it happens.

            The noise caused is just a small change in the polygons' vertices coordinates.

            See help(Painting.noise()) for more info.
        '''
        num_objs = len(self.polygons)

        rng = random.uniform(0.0, 1.0)

        if mutation_chance < rng:
            return self

        for i in range(num_objs):
            rng = random.uniform(0.0, 1.0)

            if mutation_chance < rng:
                continue

            self.polygons[i].noise(mutation_ratio)

        return self

    def paint(self):
        '''Paints genoma into an empty canvas.'''
        if hasattr(self, 'canvas'):
            self.canvas.close()

        # Create white canvas
        self.canvas = Image.new(mode='RGB', size=self.target.size)
        draw_obj = ImageDraw.Draw(self.canvas, mode='RGBA')

        for poly in self.polygons:
            poly.draw(draw_obj)

    @staticmethod
    def _error(canvas, target):
        '''Mean Squared Error between PIL Images'''
        r_canvas, g_canvas, b_canvas = canvas.split()
        r_target, g_target, b_target = target.split()

        def mse(a, b):
            return np.square(np.subtract(a, b)).mean()

        return (mse(r_canvas, r_target) + mse(g_canvas, g_target) + mse(b_canvas, b_target)) / 3.0

At last, this is the general flow of the algorithm itself:

def k_way_tournament_selection(population, number_of_winners, K=3):
    selected = []
    while len(selected) < number_of_winners:
        fighters = random.sample(population, k=min(number_of_winners-len(selected), K))

        selected.append(min(fighters))

    return selected

EPOCHS = 200
POP_SIZE = 100
DNA_SIZE = 100
MUTATION_CHANCE = 0.01
MUTATION_RATIO = 0.2
SELECTION_RATIO = 0.3

pop = Painting.random_population(POP_SIZE, DNA_SIZE, lisa)
initial = time()
generation_best = []

for ep in range(EPOCHS):
    pop = [p.fit() for p in pop]
    pop = sorted(pop)

    # Save Best
    best = pop[0]
    generation_best.append(deepcopy(best.canvas))
    pop = pop[1:]


    # Tournament selection
    selected = []
    selected = k_way_tournament_selection(pop, int(len(pop) * SELECTION_RATIO))
    selected.append(best)

    # Reproduce
    children = []
    while len(children) < POP_SIZE:
        indA = random.choice(selected)
        indB = random.choice(selected)

        cross = Painting.crossover(indA, indB, 0.5)
        children.append(cross)

    # Mutate
    children = [child.mutate(MUTATION_CHANCE, MUTATION_RATIO) for child in children]
    children.append(best)

    pop = deepcopy(children)

    del children
    del selected
    gc.collect()

    t = time()
    print(f'EPOCH: {ep} | SIZE: {len(pop)} | ELAPSED: {round(t - initial, 2)}s | BEST: {best.fitness}')

Answer 1

Okay so I found the major bug!

The problem is in the _error function. Whenever PIL images get converted to numpy arrays (when calling np.subtract() between two 2D numpy arrays, which are the image channels), it gets converted to a numpy array of type np.uint8 (unsigned int 8 bytes), because images are in the range [0-255], which makes sense. But when using np.subtract, if you get a negative value, then it will underflow, and your fitness function will be messed up.

In order to fix that, just cast the image channel with np.array(channel, np.int32) before doing np.subtract()