Body: <blockquote>
  <p>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 <span class="math-container">$p_i$</span> will look like <span class="math-container">$(x_i, y_i)$</span>, representing the Cartesian coordinates.</p>
  </blockquote>
  <p>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?</p>
  <p>This is my answer, but I am not sure.</p>
  <p>Consider two individuals with 2 variables each (2 dimensions), <span class="math-container">$p_1=(x_1, y_1)$</span> and <span class="math-container">$p_2=(x_2, y_2)$</span>. 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 <span class="math-container">$c_1=(x_1, y_2)$</span> and <span class="math-container">$c_2=(x_2, y_1)$</span>.</p>
  <p>On the other hand, a mutation operator is an r-geometric mutation under the metric <span class="math-container">$d$</span> if all its offsprings are in the <span class="math-container">$d$</span>-ball of radius <span class="math-container">$r$</span> centered in the parent.</p>
  <p>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.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T13:19:16.430Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T14:14:31.193Z
Comments.Text: The genome basically represents the center of the circle.
Comments.UserDisplayName: Rim Sleimi
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T15:07:13.410Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:13:06.693Z
Comments.Text: The radius is actually the fitness function
Comments.UserDisplayName: Rim Sleimi
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:14:29.087Z
Comments.Text: 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?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:30:12.197Z
Comments.Text: 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
Comments.UserDisplayName: Rim Sleimi
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:33:54.457Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:38:10.153Z
Comments.Text: Ok, there's one last thing that I don't understand in your post. What do you mean by "r-geometric mutation"?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:41:01.620Z
Comments.Text: 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)?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T16:43:18.073Z
Comments.Text: 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.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-26T17:45:08.923Z
Comments.Text: Yes I need to know how it looks like from a geometrical point of view.
Comments.UserDisplayName: Rim Sleimi
Tags: <genetic-algorithms><crossover-operators><homework><mutation-operators><chromosomes>
Title: How should the 1-point crossover and mutation be defined for the problem of finding the largest circle that does not enclose any point?
UserDisplayName: Rim Sleimi
ThreadText: # How should the 1-point crossover and mutation be defined for the problem of finding the largest circle that does not enclose any point?
  
  (Asked by: username_0 on 2021-03-24)
  
  > 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.
  
  **Tags:** genetic-algorithms, crossover-operators, homework, mutation-operators, chromosomes
  > **Comments:**
  > **username_1**: 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.  
  > **username_0**: The genome basically represents the center of the circle.  
  > **username_1**: 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.  
  > **username_0**: The radius is actually the fitness function  
  > **username_1**: 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?  
  > **username_0**: 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  
  > **username_1**: 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.  
  > **username_1**: Ok, there's one last thing that I don't understand in your post. What do you mean by "r-geometric mutation"?  
  > **username_1**: 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)?  
  > **username_1**: 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.  
  > **username_0**: Yes I need to know how it looks like from a geometrical point of view.  
  
  ---
  
  ## 0 answers
  
  