1

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.

Rim Sleimi
  • 215
  • 1
  • 6
  • 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. – nbro Mar 26 '21 at 13:19
  • The genome basically represents the center of the circle. – Rim Sleimi Mar 26 '21 at 14:14
  • 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. – nbro Mar 26 '21 at 15:07
  • The radius is actually the fitness function – Rim Sleimi Mar 26 '21 at 16:13
  • 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? – nbro Mar 26 '21 at 16:14
  • 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 – Rim Sleimi Mar 26 '21 at 16:30
  • In that case, yes, the radius is sufficient to determine the fitness, but you will need to compute the radius for every new individual. I would suggest that you include this info in your post, so that future readers of your post don't have to ask the same question that I asked to understand the problem. – nbro Mar 26 '21 at 16:33
  • Ok, there's one last thing that I don't understand in your post. What do you mean by "r-geometric mutation"? – nbro Mar 26 '21 at 16:38
  • Also, if you have noticed, I changed your title to ask for "How would these operators be **defined** for this problem?", but it seems, after having read your post again, that you're interested in describing how the subspace of possible crossovers and mutations **looks like** for a specific pair of individuals. So, my question is: Is your your question the one in the title or the second one (i.e. describing this subspace)? – nbro Mar 26 '21 at 16:41
  • Moreover, be careful about the definition of the fitness function in the extreme cases, e.g. when the circle's center is equal to some of these points that you don't want to enclose. In that case, you would have a circle of radius 0, but it would still enclose the point. So, you may need to avoid these circles altogether. – nbro Mar 26 '21 at 16:43
  • Yes I need to know how it looks like from a geometrical point of view. – Rim Sleimi Mar 26 '21 at 17:45

0 Answers0