Selección de rueda de la ruleta en algoritmo genético. La población necesita ser ordenada primero?

Question

En un algoritmo genético, al seleccionar miembros para el cruce utilizando el método de selección de rueda de ruleta, ¿la población primero debe ordenarse por rango de condición física?

Las posibilidades parecen ser:

1. población especie por primera vez por la aptitud ascendente población
2. ordenar por descender de fitness
3. no ordenar población & dejar caer la bola de la ruleta donde se puede ..

Estoy pensando que ordenar de cualquier manera puede no tener ningún efecto: un aterrizaje de guijarros al azar en una rueda que contiene rodajas de diferentes tamaños (por estado físico) tendrá exactamente la misma probabilidad de resultado si las rebanadas más grandes se agrupan juntas o no. Pero no estoy 100% convencido.

¿Qué opinas?

La necesidad de hacer una ordenación de cada generación afecta la velocidad del algoritmo también, así que preferiría no hacerlo (haría una especie si uso elitismo, pero no estoy en este caso). Gracias si lo conoce, ya que no puedo encontrar una respuesta definitiva a través de google, etc.

Answer 1

No, en realidad no necesita ordenarlos. Tiene razón en que no tendrá ningún efecto si los miembros de mayor rango se agrupan o no (al menos con un buen generador de números aleatorios :)).

Su intuición está muerta aquí - estadísticamente, no tendrá ningún efecto para ordenar, y como usted menciona, ¡no tiene que perder un montón de tiempo y esfuerzo clasificando cosas!

Answer 2

No necesita ordenar la población si utiliza dicha selección.

Y también tiene razón acerca de la complejidad, una especie es n * log (n), haciendo que el algoritmo genético sea significativamente más lento (pero aún así, la complejidad permanece polinomial, una característica crítica de los algoritmos genéticos).

Aquí es cómo lo haría (y obtener puntos extra en la escuela para esto):

1. poner en práctica una solución más genérica utilizando ganchos - antes de la mutación, después de la selección, etc, etc

2. mida el número de iteraciones y la velocidad del algoritmo/cada iteración

3. haga su clasificación en un gancho. medida. ahora deje que el gancho esté vacío y mida, y así sucesivamente.

Obtendrá algunos buenos datos y comprobará experimentalmente lo que le dice su intuición.

Answer 3

Incluso si aplica elitismo, no es necesario ordenar la población.

Encontrar las mejores N personas solo requiere una única iteración a través de la población.