How could I use a Genetic Algorithm to solve this placement optimization problem?

Question

I would like to use GA to solve the following problem:

• I have a white image with resolution 100*100 that has always 50 black pixels.
• I can choose which these 50 pixels could be.
• I already have a function f(image) that according to the position of these 50 black pixels, it returns a score (I do not know what the maximum score could be).

How can I find which set of 50 pixels is approximately the best one (without having to try all possible combinations)? I am new to GA and I would like to ask how should I approach/implement such an optimization?

Answer 1

Do you have some more information about the nature of the fitness function besides that it simply scores based on 50 points? If not, there does not seem to be any reason to complicate the problem by trying to impose higher order abstractions on your encoding. This limits the benefits of a genetic algorithm, but also lowers the dimensionality by a lot. Example below is in Python.

Individuals are simply lists of coordinate pairs:

from random import SystemRandom

X_DIMENSION = 100
Y_DIMENSION = 100

N_PIXELS = 50

rng = SystemRandom()

def create_individual():
    return [
        (rng.randrange(X_DIMENSION), rng.randrange(Y_DIMENSION))
        for i in range(N_PIXELS)
    ]

A naive crossover can be implemented as a straightforward splice and join of two individuals.

def crossover(a, b):
    location = rng.randrange(1, N_PIXELS - 1)
    return a[:location] + b[location:], b[:location] + a[location:]

This is another random naive implementation, this time for mutation. It's simply replacing coordinates randomly with new coordinates. Keep in mind that the LOCATION_MUTATION_RATE is simply an artifact of this method of mutation, not the actual mutation rate of individuals in general (see MUTATION_RATE).

LOCATION_MUTATION_RATE = .1

def mutate(a):
    for i in range(N_PIXELS):
        if rng.random() < LOCATION_MUTATION_RATE:
            a[i] = (rng.randrange(X_DIMENSION), rng.randrange(Y_DIMENSION))

Here's a general outline of what the final implementation could look like. Some functions here are obviously omitted, but you can get the gist.

POPULATION_SIZE = 10000
SELECTION_RATE = .8
CROSSOVER_RATE = .2
MUTATION_RATE = .03


def main():
    population = [create_individual() for i in range(POPULATION_SIZE)]
    normalized_fitnesses = normalize_fitnesses(calc_fitnesses(population))
    print_stats(normalized_fitnesses)
    while not completion_condition(normalized_fitnesses):
        select(zip(population, normalized_fitnesses))
        replace_dead(population)
        crossover_all(population)
        mutate_all(population)
        normalized_fitnesses = normalize_fitnesses(calc_fitnesses(population))
        print_stats(normalized_fitnesses)


def calc_fitnesses(population):
    return [calc_fitness(individual) for individual in population]

Edit:

After learning that the application is RF propagation, I would say that the only big change that is required is that the mutation function should definitely just move the coordinates around randomly rather than generate new points (since selection already accomplishes this). It's also probably better in general, assuming gradients of some kind. Below is an example using different movement amounts based on the x and y dimensions. It might not be intuitive, but imagine if you were working with 20 x 1000 or something like that. Also, I would personally add in another factor besides the base amount (MUTATION_MOVEMENT_FACTOR) to increase the movement amounts based on how poorly the individual has performed relative to others (so normalized fitness).

import math

LOCATION_MUTATION_RATE = .3
MUTATION_MOVEMENT_FACTOR = .05
MOVEMENT_X = math.ceil(X_DIMENSION * MUTATION_MOVEMENT_FACTOR)
MOVEMENT_Y = math.ceil(Y_DIMENSION * MUTATION_MOVEMENT_FACTOR)

def mutate(a):
    for i in range(N_PIXELS):
        if rng.random() < LOCATION_MUTATION_RATE:
            a[i][0] += rng.randrange(-MOVEMENT_X, MOVEMENT_X)
            a[i][1] += rng.randrange(-MOVEMENT_Y, MOVEMENT_Y)

Considering that this is RF propagation, you could probably do some optimizations after performing the genetic operations to avoid wasting computation time. Taking points which are clearly too close together and merging them into one point (averaging), then generating a new point comes to mind.

Answer 2

Adding on to Alvaro's answer:

To make a population of N, each of these N objects will be a valid image, i.e, a white image with resolution 100*100 that has always 50 black pixels.

The 50 black pixels could be placed randomly (if N is large) or using any other method. This will set up the initial population of size N, with each chromosome being a 100x100 data structure (basically your image).

Since you already have a fitness function, use it to find the best individuals for the next generation.

Now to increase the population you would need "Crossover function" and/or a "Mutation function".

Mutation can be done by changing some (say k, where k < 50) black pixels position with a white pixel, something so that the chromosome does not lose its basic property but is only mutated a little from the original image.

For crossover function, take 2 images (chromosomes) and mix them to make a new chromosome, keeping in mind that each chromosome can have exactly 50 black pixels (and any other constraints). This could be done by taking 25 black pixels from each parent image, and in case they overlap (black pixel from parent 1 and black pixel from parent 2), you can put it at a random white place or you could choose the nearest empty pixel to put this black pixel.

Repeat the steps of generating the best population, crossover, mutation, generating the best population, crossover, mutation, .... until convergence, or for a set no. of iterations.

Answer 3

Your question is a little too broad for SO. But here is a summary of how GA works. The key part is that you already have a fitness function.

1. Define a population size N.
2. Define your chromosome encoding. This could be tricky.
3. Generate N chromosomes randomly.
4. Calculate fitness for each chromosome using f(image).
5. Generate the next generation performing selection (using the fitness score previously calculated) and mutation.
6. Repeat from 4 a certain number of times or if an ending criteria is met.

I hope this helps as a starting point. Probably you should check some GA examples out there, start coding and ask here some more specific questions if you need.