Genetic algorithm - fit max circles inside box - what chromossomes?

Question

I am using a genetic algorithm to fit the max number of circles into a box. Right now my cromossomes are both coordinates of the each circle. I am not sure how to crossover and mutate the x and y coordenates in order not for the to converge but to keep a distance.

Can someone please shed some light? Thank you

This is where I am getting at:

Now I am getting this:

But there is the last ball always overlaps. I think my problem is with the crossover.

So far and by gathering all the ideas here this is what I have reached: Given a fixed number of circles (easier to explain) this is what I am doing.

1. Create a random set of circles for each individual in the population

2. Calculate the fitness of every individual base on the overlaping area are and area outside the box.

3. I then order the individuals by their fitness

4. Do a cross over. For that I am using a cumulative sum to choose randomly but with priorities which individuals are likely to go through to the next generation based on the fitness. The fittest have a higher probability of being chosen.

5. After choosing them indivudals I am aplying the crossover to I randomly choose the chromosse to which I do the single point cross over.

6. Then repeat for n generations

I am doing this but not getting to any convergion in terms of solution.

Answer 1

You can define chromosome as array - coordinates of the center of a circle - [(x1,y1), (x2, y2),..,(xn,yn)] One required condition for every circle- no intersection between sides of rectangle and circle - the circle must be inside the rectangle.

Start from one circle (n=1) and create population with chromosomes of size 1 [(x1,y1)].

Your fitness function - number of intersections between circles - for n=1 fitness function always return 0.

You continue with 2 circles: and generate population of chromosomes [(x1,y1), (x2,y2)]. For every chromosome you calculate fitness - number of intersection between circles.

Crossover:

You can use different algorithm to generate new population:

1) Single point.

First point - from first chromosome, second point from second chromosome.

For example, two chromosomes with coordinates:

[(x11,y11), (x12, y12)]

[(x21,y21), (x22, y22)]

Crossover - two chromosomes:

[(x21,y21),(x12,y12)],

[(x11,y11),(x22,y22)]

For n>2:

[(x11,y11),(x12,y12), (x13,y13),..,(x1n,y1n)]

[(x21,y21),(x22,y22), (x23,y23),..,(x2n,y2n)]

Crossover:

[(x21,y21),(x12,y12), (x13,y13),..,(x1n,y1n)]

[(x11,y11),(x22,y22), (x23,y23),..,(x2n,y2n)]

etc.

See https://en.wikipedia.org/wiki/Crossover_(genetic_algorithm) about crossover algorithms.

Mutation:

For every chromosome from population choose randomly some circle and change coordinates.

New population:

select chromosomes with minimal fitness value.

If you found out chromosome with fitness value is 0 - increment n (number of circles) and repeat this procedure: create population with chromosomes with size n, etc.