¿Por qué las personas con baja condición física tienen la oportunidad de sobrevivir a la próxima generación?

24

Actualmente estoy leyendo y viendo algoritmos genéticos y me parece muy interesante (no he tenido la oportunidad de estudiarlo mientras estaba en la universidad).

Entiendo que las mutaciones se basan en la probabilidad (la aleatoriedad es la raíz de la evolución) pero no entiendo por qué es la supervivencia.

Por lo que entiendo, un individuo que $I$ una aptitud $F(i)$ como para otra persona $J$ tiene una aptitud $F(j)$ tenemos $F(i) > F(j)$ , entonces $I$ una mejor probabilidad que $J$ de sobrevivir a la próxima generación.

Probabilidad implica que $J$ puede sobrevivir y $I$ pueden no (con la "mala suerte"). No entiendo por qué esto es bueno en absoluto? Si $I$ gustaría siempre sobrevivir a la selección, lo que podría ir mal en el algoritmo? Supongo que el algoritmo sería similar a un algoritmo codicioso, pero no estoy seguro.

algorithms optimization genetic-algorithms Max
fuente

13

Quedarse atascado en un mínimo local.

Louis

Incluso en la vida real, las mutaciones beneficiosas no lo hacen / una mayor aptitud ambiental no garantiza la supervivencia de las personas con ellas, lo que en realidad permite que se exprese una mayor variedad de rasgos (y puede ser potencialmente beneficioso si el entorno cambia inesperadamente) aunque eso no es tan probable para un algoritmo de optimización). ... Y eso se afirma al final de la respuesta de Nick, así que lo que sea.

JAB

1

Si matas a los débiles todo el tiempo, ¿qué tienes sino un simple escalador?

Raphael

35

La idea principal es que al permitir que los individuos subóptimos sobrevivan, puede cambiar de un "pico" en el paisaje evolutivo a otro a través de una secuencia de pequeñas mutaciones incrementales. Por otro lado, si solo puedes subir cuesta arriba, se requiere una mutación gigantesca y enormemente improbable para cambiar los picos.

Aquí hay un diagrama que muestra la diferencia:

ingrese la descripción de la imagen aquí

Prácticamente, esta propiedad de globalización es el principal punto de venta de los algoritmos evolutivos: si solo desea encontrar un máximo local, existen técnicas especializadas más eficientes. (p. ej., L-BFGS con gradiente de diferencia finita y búsqueda de línea)

En el mundo real de la evolución biológica, permitir que los individuos subóptimos sobrevivan crea robustez cuando cambia el paisaje evolutivo. Si todos se concentran en un pico, entonces si ese pico se convierte en un valle, toda la población muere (por ejemplo, los dinosaurios fueron las especies más aptas hasta que hubo un ataque de asteroides y el paisaje evolutivo cambió). Por otro lado, si hay algo de diversidad en la población, cuando el paisaje cambie, algunos sobrevivirán.

Nick Alger
fuente

2

"En el mundo real de la evolución biológica, permitir que los individuos subóptimos sobrevivan crea robustez cuando cambia el paisaje evolutivo", como biólogo esto irrita. A los individuos con baja condición física no se les "permite" sobrevivir para maximizar la condición física que es solo la naturaleza de la realidad. Los organismos de baja aptitud están tratando de sobrevivir tanto como cualquier otra cosa.

Jack Aidley

Por supuesto que tienes razón, la naturaleza no decide permitir o rechazar nada, simplemente sucede. Por otro lado, hay muchos ejemplos en los que los humanos han criado selectivamente plantas y animales manteniendo solo lo "mejor", creando un monocultivo que no es robusto cuando aparece una nueva enfermedad o el entorno cambia.

Nick Alger

Existen otras técnicas para combatir este efecto, por ejemplo, dar pasos más grandes y volver a ejecutar con poblaciones iniciales aleatorias. Además, en presencia de recombinación cruzada, mantener un genotipo más débil puede ser útil si uno más fuerte muta y un cruce entre los dos resulta ser aún más fuerte.

Raphael

13

La respuesta de Nick Alger es muy buena, pero voy a hacerlo un poco más matemático con un método de ejemplo, el método Metropolis-Hastings.

$i$ $j$ $Q(i,j)$ $Q(i,j) = Q(j,i)$ $F(i)>0$ $i$

$i$ $j$

min (1, \frac{F (j)}{F (i)})

$\min\left(1, \frac{F(j)}{F(i)}\right)$

En otras palabras, si está más en forma, siempre lo tomamos, pero si está menos en forma, lo tomamos con probabilidad , de lo contrario lo intentamos nuevamente hasta que aceptemos un mutación. $j$ $j$ $\frac{F(j)}{F(i)}$

Ahora nos gustaría explorar , la probabilidad real de que hagamos la transición de a . $P(i,j)$ $i$ $j$

Claramente es:

P (i, j) = Q (i, j) min (1, \frac{F (j)}{F (i)})

$P(i,j) = Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$

Supongamos que . Entonces = 1, y así: $F(j) \ge F(i)$ $\min\left(1, \frac{F(j)}{F(i)}\right)$

F (i) P (i, j)

$F(i) P(i,j)$

= F (i) Q (i, j) min (1, \frac{F (j)}{F (i)})

$= F(i) Q(i,j) \min\left(1, \frac{F(j)}{F(i)}\right)$

= F (i) Q (i, j)

$= F(i) Q(i,j)$

= Q (j, i) m i n (1, \frac{F (i)}{F (j)}) F (j)

$= Q(j,i) min\left(1, \frac{F(i)}{F(j)}\right) F(j)$

= F (j) P (j, i)

$= F(j) P(j,i)$

Ejecutando el argumento al revés, y también examinando el caso trivial donde , puede ver eso para todos y : $i=j$ $i$ $j$

F (i) P (i, j) = F (j) P (j, i)

$F(i) P(i,j) = F(j) P(j,i)$

Esto es notable por algunas razones.

La probabilidad de transición es independiente de . Por supuesto, puede llevarnos un tiempo terminar en el atractor, y puede llevarnos un tiempo aceptar una mutación. Una vez que hagamos, la probabilidad de transición es totalmente dependiente de , y no en . $Q$ $F$ $Q$

Resumiendo todo lo que : $i$

\sum_{i} F (i) P (i, j) = \sum_{i} F (j) P (j, i)

$\sum_i F(i) P(i,j) = \sum_i F(j) P(j,i)$

Claramente, debe sumar si sumas todo (es decir, las probabilidades de transición de un estado deben sumar ), por lo que obtienes: $P(j,i)$ $1$ $i$ $1$

F (j) = \sum_{i} F (i) P (i, j)

$F(j) = \sum_i F(i) P(i,j)$

Es decir, es la función de densidad de probabilidad (no normalizada) para la cual el método elige. No solo tiene la garantía de explorar todo el paisaje, sino que lo hace en proporción a la "adecuación" de cada estado. $F$

Por supuesto, este es solo un ejemplo de muchos; Como señalé a continuación, es un método muy fácil de explicar. Por lo general, usa un GA no para explorar un pdf, sino para encontrar un extremo, y puede relajar algunas de las condiciones en ese caso y aún garantizar la convergencia eventual con alta probabilidad.

Seudónimo
fuente

Maravillosa respuesta! Desearía poder votarlo repetidamente. Una pregunta: ¿Puedes motivar por qué elegiríamos ? ¿Se elige eso porque entonces todo el resto de las matemáticas resulta en un resultado muy ingenioso? ¿O hay alguna razón externa por la que esa es una opción natural para ? (Hubiera esperado que un valor natural para fuera uno sobre el número de bordes externos del estado , en cuyo caso no tendríamos ya que en general el grado de salida de y puede diferir)

Q (i, j) = Q (j, i)

$Q(i,j)=Q(j,i)$

Q

$Q$

Q (i, j)

$Q(i,j)$

i

$i$

Q (i, j) = Q (j, i)

$Q(i,j)=Q(j,i)$

i

$i$

j

$j$

DW

La motivación en este caso es la condición de equilibrio detallada, , que es una condición suficiente (aunque no necesaria) para garantizar que es la estacionaria pdf. Si desea que su pdf sea estacionario, entonces ayuda que el proceso sea reversible en algún sentido. Además, si ayuda, el algoritmo MH fue diseñado para problemas continuos (transporte de neutrones) donde no hay un número discreto de bordes externos. Por supuesto, si está tratando de encontrar un máximo global, buscar en todo el pdf no siempre es lo que realmente quiere. Esto fue solo para fines ilustrativos.

F (i) P (i, j) = F (j) P (j, i)

$F(i) P(i,j) = F(j) P(j,i)$

F

$F$

Seudónimo

7

La ventaja de usar un GA es que puede explorar espacios de búsqueda más amplios siguiendo caminos que provienen de candidatos potencialmente peores. Debería haber peores candidatos para explorar estas diferentes áreas de la búsqueda, no muchas, pero definitivamente unas pocas. Si comienzas a tomar solo lo mejor cada vez que eliminas este aspecto de exploración del algoritmo y se convierte más en un escalador. Además, solo seleccionar lo mejor constantemente puede conducir a una convergencia prematura.

lPlanta
fuente

6

En realidad, los algoritmos de selección toman ambos enfoques. Una forma es lo que usted sugirió y la otra es que las personas con mayor condición física son seleccionadas y aquellas con niveles más bajos no.

El enfoque que elija para la selección también se adapta al problema que está tratando de modelar. En un experimento en la escuela, estábamos tratando de evolucionar a los jugadores de cartas haciéndolos jugar uno contra el otro (es decir , la selección de torneos ). En tal escenario, podríamos favorecer siempre a sobre (a partir de su ejemplo) porque el aspecto de 'suerte' ya está en el juego en sí. Incluso si para cualquiera de los dos y , en cualquier ronda, solo por la forma en que se repartieron las manos y cómo jugaron los demás, podría haber ganado la ronda y así podríamos terminar con $I$ $J$ $F(i) > F(j)$ $I$ $J$ $J$ $F(j) > F(i)$ . Tenga en cuenta que una población suele ser lo suficientemente grande como para permitirse el lujo de perder algunas personas buenas y, en general, no importará tanto.

Dado que las AG se modelan en torno a la evolución del mundo real, cuando se utilizan distribuciones probabilísticas, se modelan principalmente en torno a cómo evolucionan las comunidades reales en las que a veces las personas con una condición física más baja pueden sobrevivir, mientras que las personas con una condición física más alta no (una analogía cruda: accidentes automovilísticos, natural desastres, etc. :-)).

Omer Iqbal
fuente

0

es muy simple, desde un punto de vista: a veces, las soluciones de "niño" de mayor aptitud física pueden nacer de soluciones de "padre" de menor aptitud física a través de cruce o mutación (que en realidad es una gran parte de la teoría de los algoritmos genéticos). por lo tanto, en general, uno quiere buscar / llevar las soluciones de mayor aptitud física, pero demasiado énfasis en mantener / reproducir solo soluciones de alta aptitud física puede llevar a quedarse atascado en los mínimos locales y no buscar en el gran "paisaje evolutivo". en realidad, uno puede hacer que el "límite de aptitud física superior" para la supervivencia sea tan estricto o laxo como se desee y experimentar cómo afecta la calidad de la solución final. estrategias de corte demasiado estrictas o demasiado laxas conducirán a soluciones finales inferiores. Por supuesto, todo esto tiene alguna relación con la evolución biológica real. allí es más "

vzn
fuente

¿Por qué las personas con baja condición física tienen la oportunidad de sobrevivir a la próxima generación?

Respuestas: