¿Definir el punto de detención de un algoritmo genético anula el propósito del algoritmo?

Wikipedia define el punto de terminación de un GA para esto:

Comúnmente, el algoritmo termina cuando se ha producido un número máximo de generaciones o se ha alcanzado un nivel de aptitud física satisfactorio para la población. Si el algoritmo ha finalizado debido a un número máximo de generaciones, puede o no haberse alcanzado una solución satisfactoria.

Ahora, si termina cuando se ha alcanzado un nivel de condición física satisfactorio, y usted es quien define ese nivel de condición física, ¿por qué no sería capaz de crear el genoma "perfecto" desde el principio, ya que ya conoce las características? de este genoma perfecto?

Supongo que estoy un poco confundido aquí. Pensé que el propósito de un GA era evolucionar constantemente y mostrarnos posiblemente una solución aún mejor de lo que pensábamos, y nuestra función de condición física era solo algo que nos ayudó en el camino, no algo que pusimos en el pedestal como la terminación ". perfecto "estado. ¿Eso no destruye el punto?

La función de aptitud evalúa la salida de su algoritmo. Es muy posible reconocer una salida ideal cuando la ve, pero no conoce los pasos para producir esa salida a partir de una entrada dada. Ahí es donde los algoritmos genéticos son más útiles.

Por ejemplo, una aplicación divertida común de GA es producir una animación que pueda mover una criatura virtual de manera eficiente. Es fácil saber si la criatura se mueve a cierta velocidad en una línea relativamente recta. Esa es tu función física. Es mucho más difícil determinar la secuencia exacta de los movimientos "musculares" para lograrlo.

A menudo, puede determinar la idoneidad de una solución, pero no puede determinar directamente la solución en sí. Digamos que está tratando de evolucionar conejos rápidos, y hay un puñado de genes que afectan la velocidad del conejo. Puede probar la velocidad del conejo, pero enumerar todas las combinaciones de genes relacionados con la velocidad no sería práctico. En tal caso, es posible que tenga un GA que compite con conejos y críe los más rápidos. Podrías hacerlo para siempre, pero probablemente prefieras detenerte cuando:

• has encontrado un conejo que es más rápido que X, o
• la mejora incremental durante n generaciones ha caído por debajo de algún umbral
• has criado conejos a través de m generaciones

El objetivo de GA es darle la solución al problema que tiene ese nivel de condición física. Esta solución sería muy difícil de encontrar utilizando otros algoritmos de búsqueda más convencionales, que generalmente es la razón por la que está utilizando un GA en primer lugar.

O, en lugar de un límite de valor de condición física, puede decidir cuántas generaciones desea correr (cuantas más generaciones corra, mayor será la probabilidad de encontrar valores de condición física cada vez mayores). Por ejemplo, en el problema del vendedor ambulante, obtener un camino que tenga el costo más bajo entre las ciudades que necesita recorrer.

Su problema generalmente determina si su condición de detención es un cierto nivel de condición física que es aceptable o una cierta restricción de tiempo (ejecutar el GA durante un período de tiempo máximo o un número limitado de generaciones para aplicaciones críticas como la búsqueda de rutas o aplicaciones de IA) dominio.

Intuitivamente, el propósito de un algoritmo genético es formular una solución algorítmica a un problema que no se presta a un análisis lógico directo. Una vez que se logra ese objetivo, la AG no necesita seguir adelante.

Por supuesto, si se desea una mejor "aptitud", el algoritmo genético puede dejarse en funcionamiento para ver si puede encontrar una solución más optimizada, o el algoritmo genético puede ajustarse para ver si convergerá en una solución mejor.

Un algoritmo genético requiere alguna forma de recompensar genes buenos con una mayor propagación. Si no tuviera forma de distinguir los genes buenos de los genes malos, no podría utilizar un algoritmo genético en absoluto.

Para que funcione un algoritmo genético, debe permitir que las soluciones más adecuadas se reproduzcan con preferencia a las soluciones menos adecuadas. De lo contrario, solo intentarías soluciones aleatorias.

Aquí hay un ejemplo típico de mi propia experiencia: al desarrollar uno de los primeros sistemas de marcación por voz, tuvimos dificultades para encontrar un algoritmo que hiciera coincidir un nombre hablado con una copia almacenada de ese mismo nombre. Nos dijeron que el 95% de precisión eligiendo un nombre de 25 era suficiente. Teníamos un corpus almacenado de personas que decían 25 nombres 10 veces cada uno.

Primero, desarrollamos un sistema de entrada que midió la longitud de la palabra hablada y la energía de frecuencia en varios fragmentos normalizados. Luego desarrollamos un algoritmo que asignaba pesos a las coincidencias en esos parámetros y comparaba dos conjuntos de parámetros a través de esos pesos.

Ahora, tuvimos un último paso: ¿cuál debería ser el valor de esos pesos?

Creamos 1,000 conjuntos de pesos al azar y los probamos contra el corpus. Descartamos los 500 que tuvieron el peor desempeño. Para los 500 restantes, duplicamos cada uno y en uno de ellos, subimos o bajamos al azar uno de los pesos.

Repetimos este proceso en una computadora durante aproximadamente dos semanas hasta que finalmente tuvo un conjunto de pesas que cumplieron con el criterio de precisión del 95%. Luego lo probamos en datos que no están en el corpus. Era aproximadamente un 92% de precisión. Así que trabajamos más tiempo para obtener una precisión del 98% en el corpus y ese conjunto de pesas produjo una precisión del 95% en los datos que no están en el corpus.

Entonces, el punto es que debe tener una función de aptitud física para ejecutar un algoritmo genético. Si no tiene forma de distinguir los genes buenos de los genes malos, ¿cómo puede asegurarse de que los genes buenos se reproducen y los genes malos no?

Iterar hasta que una solución no difiera mucho de la iteración anterior. Por mucho, por favor entienda una tolerancia fija.

Solution in iteration n-6: 600
Solution in iteration n-5: 800
Solution in iteration n-4: 768
Solution in iteration n-3: 780 
Solution in iteration n-2: 778
Solution in iteration n-1: 778.23
Solution in iteration n: 780.18
Solution in iteration n+1: 780.1815

En este ejemplo, si su tolerancia fija era 0.01, entonces (n + 1) le dice que pare porque abs (solución (n + 1) -solución (n)) <0.01.

Resumiendo, ahí es cuando su algoritmo puede decir: ¡esto no mejorará!

Para una respuesta rápida a su pregunta principal: Hay una gran diferencia entre saber lo que quiere lograr y saber cómo llegar allí.

Más detalladamente, por ejemplo, con uno de los problemas más populares resueltos mediante el uso de algoritmos genéticos / evolutivos, generalmente un estudio de caso en clase, para encontrar la ruta óptima en un gráfico. Esto se usa a menudo en redes para encontrar la ruta más barata de un extremo a otro. Al definir los costos (número de saltos, costo de cada salto, etc.) también define su costo objetivo (nivel de condición física) con el que está satisfecho con el resultado. Es posible que su algoritmo no encuentre el mejor, pero encontrará un óptimo algorítmicamente aceptable. Con esto quiero decir que la relación costo / beneficio de encontrar una mejor respuesta es prohibitiva.

Con GA / EA, encontrará que es un comportamiento normal encontrar rápidamente una respuesta óptima del 95% +, pero reducir ese último 5% es exponencialmente más costoso. Entonces, la teoría es que usted define un óptimo aceptable para lograr el mejor resultado en la menor cantidad de tiempo. Dado que el costo de encontrar, digamos el 1% superior, podría superar sus beneficios sobre el 5% superior, usted define su óptimo aceptable.

En resumen, ahora no es la respuesta a ningún problema en particular, simplemente define, por problema, su óptimo aceptable, el punto en el que encontrar una mejor respuesta no es práctico.

Se está investigando la solución de errores en C con algoritmos genéticos al proporcionar casos de prueba negativos y positivos como funciones de aptitud, junto con un código roto como entrada. Este es un ejemplo de un problema que podría ser resuelto por un humano, pero que es más fácil de hacer para un algoritmo genético. Es importante tener en cuenta:

Aunque los métodos descritos en este documento no desarrollan nuevos programas desde cero, sí muestran cómo evolucionar el software heredado para reparar fallas existentes.

Sin embargo, los nuevos programas se han desarrollado desde cero, solo que no en C. Los pocos programas no triviales escritos en el lenguaje de programación esotérico de Malbolge se han desarrollado todos (según mi conocimiento), no escritos. El lenguaje es demasiado complejo para que lo use un programador, y demasiado complicado para deducir eficientemente los programas solo de la lógica, por lo que la mayoría de los programas escritos en él han sido producidos por algoritmos genéticos. La función de aptitud es generalmente la distancia de edición a la salida esperada.

Esto es muy circular, en cierto sentido. Al observar que el código genético complejo está escrito por procesos evolutivos, podemos simular procesos evolutivos para producir código en un lenguaje complejo diferente, ¡sin siquiera saber cómo funciona el código!