1
$\begingroup$

For a random scattering of points, in a bounded area, the goal is to find the largest circle that can be drawn inside those same bounds that does not enclose any points. Solving this problem with a genetic algorithm requires deciding how to encode as a genome, information sufficient to represent any solution. In this case, the only information we need is the center point of the circle, so our genome of point $p_i$ will look like $(x_i, y_i)$, representing the Cartesian coordinates.

In this case, what does each of the genetic operators mean for this simplistic genome? Geometrically speaking, what would a 1-point crossover look like in this case? What about mutation?

This is my answer, but I am not sure.

Consider two individuals with 2 variables each (2 dimensions), $p_1=(x_1, y_1)$ and $p_2=(x_2, y_2)$. For each variable, the parent who contributes its variable to the offspring is chosen randomly with equal probability. Geometrically speaking, a 1-point crossover would represent a quadrilateral in the Cartesian space, where one of the diagonals is formed by the parents and the other one by the offsprings $c_1=(x_1, y_2)$ and $c_2=(x_2, y_1)$.

On the other hand, a mutation operator is an r-geometric mutation under the metric $d$ if all its offsprings are in the $d$-ball of radius $r$ centered in the parent.

The radius (fitness function) would be the distance between the center (genome) and the closest point (star) from the random points in the bounded area.

$\endgroup$
11
  • $\begingroup$ The problem is not fully clear to me. From what I understand, you have some bounded area, e.g. a rectangle, which contains some points. If you want to find a circle that can be drawn inside this rectangle, then you want to model circles, i.e. the individuals or genomes should model something about the circles (and not necessarily the points). So, it's not clear to me why a genome would be the x and y coordinates of a point. Maybe you understand why and you can clarify this. $\endgroup$
    – nbro
    Mar 26 at 13:19
  • $\begingroup$ The genome basically represents the center of the circle. $\endgroup$
    – Rim Sleimi
    Mar 26 at 14:14
  • $\begingroup$ Ha, right, for some reason, I missed that. But why isn't the radius also necessary in this case? The radius might also be necessary to determine the area that the circle covers. $\endgroup$
    – nbro
    Mar 26 at 15:07
  • $\begingroup$ The radius is actually the fitness function $\endgroup$
    – Rim Sleimi
    Mar 26 at 16:13
  • $\begingroup$ I don't think the radius is the fitness function. The fitness function must also take into account whether or not the circle encloses any point in this bounded area. So, the radius will definitely need to be included in the calculation of the fitness, but that's not just it. More specifically, the fitness function will be number of points enclosed in the circle (so you need some way to compute this; and the fewer the better: ideally, 0) + radius. Maybe I'm misunderstanding the problem again, but, from what I understand, there are other points in this bounded area that you want to "avoid". No? $\endgroup$
    – nbro
    Mar 26 at 16:14

Your Answer

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

Browse other questions tagged or ask your own question.