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

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 1. Calculate the fitness of every individual base on the overlaping area are and area outside the box.

2. I then order the individuals by their fitness

3. 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.

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

5. Then repeat for n generations

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

• I already did that with 8 circles. But still no solution – scottbear Mar 26 '18 at 20:37
• Why are you use? See the next link: math.stackexchange.com/questions/2548513/… – e42d3 Mar 27 '18 at 19:46
• My idead is using a GA to do it, the goal is other shapes – scottbear Mar 28 '18 at 0:06

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.

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.

• Your algorithm for the single point isn't very clear to me. Could you expand on that? – Discrete lizard Mar 28 '18 at 13:54
• @Discretelizard - single point - one from the standard crossover techniques. I swap coordinates between the two parent organisms and create new children. See en.wikipedia.org/wiki/… – e42d3 Mar 28 '18 at 17:19
• How many crossover should I do? I mean how many generations for everyone n circles. – scottbear Mar 28 '18 at 17:55
• – e42d3 Mar 28 '18 at 19:48
• I have done all that but still not converging to a solution – scottbear Mar 29 '18 at 0:53