2
$\begingroup$

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: Result generation 1000

Now I am getting this: enter image description here

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

Random circles

  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.

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

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.

$\endgroup$
  • 1
    $\begingroup$ Your algorithm for the single point isn't very clear to me. Could you expand on that? $\endgroup$ – Discrete lizard Mar 28 '18 at 13:54
  • $\begingroup$ @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/… $\endgroup$ – e42d3 Mar 28 '18 at 17:19
  • $\begingroup$ How many crossover should I do? I mean how many generations for everyone n circles. $\endgroup$ – scottbear Mar 28 '18 at 17:55
  • $\begingroup$ See researchgate.net/post/… $\endgroup$ – e42d3 Mar 28 '18 at 19:48
  • $\begingroup$ I have done all that but still not converging to a solution $\endgroup$ – scottbear Mar 29 '18 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.