0
$\begingroup$

I am using a genetic algorithm to find the best way to pack circles inside a box without each touching the others and filling as much space as possible. My doubt is if an individual from a generation must be a circle or all the circles.

Can anyone help me on how would I go from here? Thank you

Improve this question
$\endgroup$
4
  • $\begingroup$ @Juho but then in the crossover two fit individuals (not touching) they would get closer each time. What would be the genome of each? $\endgroup$
    – scottbear
    Mar 26, 2018 at 17:30
  • 2
    $\begingroup$ Sorry, I meant that each individual should be a candidate solution. It is up to you to pick an encoding of a solution (i.e., how to specify the location/sizes of individual circles). $\endgroup$
    – Juho
    Mar 26, 2018 at 17:40
  • $\begingroup$ @Juho my problem is that if I have two parents and merge cross them over, the child is likely to be inbetween them which is not ideal. Converging problems make sense for me, but diverging like this on doesnt $\endgroup$
    – scottbear
    Mar 26, 2018 at 17:43
  • $\begingroup$ I might not be understanding you, but it's actually good that you also get solutions that are less fit. This is a built-in mechanism whose point is to explore the search space and avoid local optimums. $\endgroup$
    – Juho
    Mar 26, 2018 at 17:48

2 Answers 2

Reset to default
1
$\begingroup$

In genetic algorithms, each individual should be a candidate solution to the problem. You're trying to find a packing of circles into the box, so each individual should be a complete packing that specifies the location of all the circles.

Improve this answer
$\endgroup$
2
  • $\begingroup$ That way how would the genome of each individual be? $\endgroup$
    – scottbear
    Mar 26, 2018 at 17:37
  • $\begingroup$ @scottbear, that's a separate question. There are many possibilities; there is no one right answer, and it's up to you to pick something. If you have a new question, please post it separately using the 'Ask Question' button, but I suggest you first think about it, come up with some possible approaches, try them, and then tell us in the question what you have already tried and why you rejected those approaches. $\endgroup$
    – D.W. ♦
    Mar 26, 2018 at 17:41
0
$\begingroup$

A few people hear are pointing out that in a GA, individuals should be complete solutions to the problem. That's generally true, but there are evolutionary methods that do the opposite. Within the field of Learning Classifier Systems, the two approaches corresponding to your question are called the Michigan approach (each individual is only one rule or circle) and the Pittsburgh approach (each individual encodes the entire set of rules or circles). Currently, Michigan approaches (namely XCS and its variants) dominate the field, so there is evidence that you can craft such algorithms successfully. More generally, there are coevolutionary methods that have similar ideas.

The only restrictions you really have on an evolutionary method is that you need to be able to go from genotype to fitness value in some way, and you need some ability to perform transformations on the genotype like mutation and/or recombination. Mutation and crossover don't necessarily give you trouble whether or not you have one circle per individual or one solution per individual. The only issue is how do you assign fitness to one circle? If you solve that problem, then you can build algorithms that use one individual per circle.

It's certainly easier to write a fitness function that takes the entire solution as one individual, but you can do it the other way. If this is something you want to pursue, look at how XCS works and look into cooperative coevolutionary algorithms.

Improve this answer
$\endgroup$
2
  • $\begingroup$ What I did in terms of fitness was calculating the area that was overlapping and outside the box of each circle. But I get to the point where all have the same fitness and then child's are equal to parents $\endgroup$
    – scottbear
    Mar 26, 2018 at 18:19
  • $\begingroup$ If you're using the model where each individual represents all the circles, then that's fine. Note that Genetic Algorithms will generally converge to something. Once you've converged, you see the behavior you mention. You can do things to reduce selection pressure, increase mutation, etc. to try to slow that process down, but you generally will converge at some point. $\endgroup$
    – deong
    Mar 26, 2018 at 20:15

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.