Primero, cuente los nodos . Veo 26 .
Luego, cuente cada color: 6 negros y 20 blancos .
Deberíamos hacer un par de supuestos simplificadores, como:
- Cómo implementar un código C para la eliminación de un nodo de una lista vinculada considerando todos los casos de prueba
- ¿En qué lenguaje de programación están escritos los algoritmos de aprendizaje automático de Google: C ++ o Java? ¿Por qué?
- ¿Es posible que el modelo de espacio vectorial que utilizamos para entrenar algoritmos de aprendizaje automático sea inadecuado para la representación del aprendizaje humano?
- ¿Cuál es tu problema de programación dinámica favorito?
- ¿Por qué se ejecuta un análisis de tiempo de un algoritmo llamado asintótico?
- Solo hay dos variaciones de un rasgo heredable, llámelo W (mayúscula) para blanco yw (minúscula) para negro.
- Tenga en cuenta que dado que hay muy pocos nodos negros o aproximadamente 1/4 , sigue la típica genética mendeliana de dos variaciones de un solo gen que sugiere una situación dominante o recesiva de un solo gen . En esta situación, parece que W es dominante, de modo que WW , Ww y wW (3/4) producen el fenotipo blanco, pero ww produce el fenotipo negro.
- Dado que solo tenemos una forma de crear el fenotipo negro, asigne a todos esos nodos el genotipo fijo ww . Para todos los nodos blancos, pueden estar en uno de los tres genotipos posibles: WW , Ww o wW . Como no nos importa el orden del par, podemos decir que cada nodo blanco es WW o Ww ignorando el orden. Otra forma de formular esta pregunta es que sabemos que cada nodo blanco tiene al menos una W, pero la pregunta es cuáles tienen una w recesiva.
En esta etapa, tiene sentido señalar que, en general, no podemos saber con certeza cuáles son los genotipos reales para cada nodo dados estos supuestos. Pero podemos hablar sobre las asignaciones de genotipo más probables para todos los nodos desconocidos. Supongamos que nuestro objetivo es encontrar las asignaciones más probables de genotipos para cada uno de los nodos desconocidos.
Ahora pasemos al programa para resolver el problema. Para mayor claridad , comencemos con una variación más simple que un Algoritmo genético llamado Búsqueda exhaustiva . Usemos la notación 2 ^ 7 para significar ” dos a la séptima potencia “.
Configuración de la búsqueda exhaustiva:
- Para cada nodo blanco, sea 0 significa que no hay recesivo w y 1 significa que lleva un solo recesivo w . Imagine que etiquetamos todos los nodos blancos 1-20. El espacio de estado completo corresponde a asignaciones (ordenadas) para cada uno de los veinte nodos blancos. Podemos representar todo el espacio de estado de los genotipos desconocidos en el grupo con un número binario de 20 bits , o un poco más de un millón de posibilidades . Este número de combinaciones es fácil de generar rápidamente, por ejemplo, utilizando un número entero en el lenguaje de programación C o Java . Escriba un ciclo que pueda iterar sobre todas estas posibilidades y calcule una función especial llamada probabilidad para cada número de 0 a (2 ^ 20) -1 , o aproximadamente un millón de valores diferentes.
- La probabilidad de un sistema particular es el producto de todas las probabilidades en cada relación padre-hijo. Por ejemplo, la probabilidad de que una pareja de apareamiento contenga un solo padre WW con un hijo fenotipo negro es 0 . La posibilidad de que un par de apareamiento que contenga un padre ww y un padre Ww produzca cualquier fenotipo es 1/2 . La posibilidad de que un Ww y un Ww produzcan un fenotipo blanco es 3/4 y un fenotipo negro es 1/4 . Puede calcular estas probabilidades siguiendo el enlace:
Reglas de probabilidad para la herencia mendeliana – Libro de texto abierto ilimitado
Iteración repetida de búsqueda exhaustiva:
- Comience con una variable llamada maxProbability y otra llamada bestCombination . A medida que calcula la probabilidad de cada uno de los posibles números binarios de 20 bits , realice un seguimiento de la probabilidad máxima hasta ahora vista en la variable llamada maxProbability y realice un seguimiento de la asignación genética correspondiente a maxProbability en (el entero ) bestCombination . Un detalle técnico menor es decidir si maxProbability se mantendrá en probabilidad de registro o probabilidad simple . Consulte la Suma de probabilidades en el espacio log-prob para obtener más información sobre este tema.
Tenga en cuenta que el algoritmo anterior es bastante manejable en las computadoras modernas en un corto período de tiempo y puede resolverse exactamente dado el enunciado del problema. Todavía no describe un algoritmo genético porque utiliza un algoritmo exacto y seguro llamado Exhaustive Search en su lugar. Por lo general, los algoritmos exactos se consideran mejores en la mayoría de las situaciones cuando no requieren demasiado tiempo o potencia de la CPU . Si la velocidad de ejecución es un problema o si desea abordar problemas más grandes y difíciles que son similares a este, podría tener sentido aplicar una optimización de rendimiento a costa de no tener la certeza total de obtener la respuesta correcta más probable. Una buena opción para una optimización del rendimiento es el algoritmo genético .
Dado el algoritmo de búsqueda exhaustiva anterior, la mayoría de las piezas ya están en su lugar para un algoritmo genético . La principal diferencia entre un algoritmo genético y una búsqueda exhaustiva es que un algoritmo genético utiliza suposiciones de aleatoriedad y convexidad para ahorrar tiempo . En lugar de pasar por un poco más de un millón de combinaciones posibles, puede comenzar con una población inicial de quizás cien números diferentes que representan asignaciones genéticas totales. Estos pueden ser elegidos al azar . Imagine que esos números son individuos en su acervo genético artificial . Luego, asigne un estado físico a cada uno utilizando la estimación de probabilidad descrita anteriormente. Finalmente, clasifique a estos individuos por condición física y descarte los 30 menos aptos . Luego, haga treinta nuevos individuos seleccionando un par aleatorio de los 70 individuos restantes y utilizando su propia función cruzada . Deje que los dos miembros del par elegido al azar se llamen A y B. Esto significa que para cada par lanzará una moneda para elegir aleatoriamente el bit de A o B para formar el bit ( 0 o 1 ) para C en cada posición de bit . De esta manera, puede crear una cadena de bits que sea similar a A y B pero potencialmente diferente de cualquiera de ellas. Treinta de estos nacimientos virtuales harán que el recuento de la población vuelva a 100. Repita este proceso durante aproximadamente 20 generaciones y puede esperar que el miembro de mayor probabilidad de la población evolucionada contenga la respuesta más probable . No está garantizado, pero es muy probable, incluso exponencialmente dado suposiciones razonables. El número de evaluaciones de aptitud física es de 100 para la primera ronda, pero si guarda las probabilidades con cada individuo, entonces solo necesita calcular 30 nuevas probabilidades para los nuevos nacimientos en cada generación. Entonces, el número total de evaluaciones de probabilidad utilizando este conjunto particular de parámetros sería sobre:
100 + 20 * 30 = 700 . Eso es aproximadamente 1000 veces más rápido que la búsqueda exhaustiva descrita anteriormente. También puede funcionar aún mejor a medida que aumenta el tamaño del problema. Para este tipo de problema debido a que el espacio del problema es convexo , es muy probable que un algoritmo genético pueda lograr resultados muy rápidos y precisos para problemas muy grandes.
