ENSAYO: INTELIGENCIA ARTIFICIAL

...

- Explique que es un algoritmo genético, mediante un ejemplo explique su proceso de construcción.

Algoritmo Genético

Son métodos adaptativos que se pueden usar para resolver problemas de búsqueda y optimización, están basados en el proceso genético de los organismos vivos y el proceso de evolución natural donde el más fuerte sobrevive, pueden crear soluciones a problemas del mundo real.

Más específicamente son funciones matemáticas o rutinas de software que toman ciertas ejemplares de entrada y retornan como salida cuales de estos son los que deben generar descendencia para la nueva generación, así a lo largo de las generaciones las características buenas se propagan a través de la población, con individuos mejor adaptados, con un algoritmo bien diseñado la población convergerá a una solución óptima del problema.

Proceso de construcción de un algoritmo genético.

Estos son los pasos que se deben seguir

Codificación del dominio: lo primero que se requiere es determinar en qué espacio se encuentran las posibles soluciones al problema que se pretende resolver, para obtener estructuras manejables que puedan ser manipuladas por el algoritmos genético, es frecuente que el código de los elementos del dominio del problema utilice un alfabeto binario (0’s y 1’s).

Así se conoce la forma de pasar de un elemento a su código y viceversa, Los algoritmos genéticos manipulan conjuntos de códigos en generaciones sucesivas, a los elementos de la población serán llamados individuos y a los códigos se les denominará indistintamente cromosomas, genotipo, genoma o código genético.

Evaluación de la población: Cada individuo de cada generación de un algoritmo genético recibe una calificación o una medida de su grado de adaptación, a cada individuo de la población se le asigna una y sólo una calificación.

Selección: el algoritmo debe seleccionar a los individuos más calificados para que tengan mayor oportunidad de reproducción e incrementar la probabilidad de tener mejores individuos en el futuro y elevando así el nivel de adaptación de toda la población.

Cruzamiento: El cruce de individuos exitosos favorece la aparición de nuevos individuos que heredan de sus ancestros características deseables, es decir generar descendientes que posean un código híbrido mejor adaptado que el de sus padres.

Mutación: Generar nuevos individuos que exploren regiones del dominio del problema que probablemente no se han visitado aún, esta es una de las características que hacen aplicables los algoritmos genéticos a gran variedad de problemas.

- Desarrollo de los ejercicios de la hoja de Ruta que se encuentra en el entorno de aprendizaje práctico.

Responda y justifique cada uno de los siguientes ejercicios:

- Dentro de las búsquedas sin contar con la información también conocidas como búsquedas a ciegas se encuentran seis estrategias, según la gráfica indique a qué estrategia corresponde y justifique su respuesta.

[pic 1][pic 2]

[pic 3][pic 4][pic 5]

[pic 6][pic 7][pic 8][pic 9][pic 10][pic 11]

[pic 12][pic 13]

[pic 14][pic 15][pic 16][pic 17]

ITERACIONES DE BÚSQUEDA

Nodo

Actual

Sucesores

1

A

B,C,D

2

B

C,D,E,F

R= La estrategia utilizada en este ejercicio es la búsqueda preferente por amplitud, ya que primero se expandes los nodos que están en profundidad 1 (B, C, D) del árbol de búsqueda antes que los demás nodos que estén en las siguientes profundidades (E, F).

b. Teniendo en cuenta la siguiente gráfica, en el tipo de búsqueda preferente por profundidad ¿cuál es el recorrido? Justifique su respuesta. Si se utiliza la búsqueda A* ¿cuál sería el recorrido?

R=

[pic 18]

[pic 19][pic 20][pic 21][pic 22][pic 23]

[pic 24][pic 25][pic 26][pic 27][pic 28]

[pic 29][pic 30][pic 31][pic 32][pic 33]

[pic 34][pic 35][pic 36][pic 37][pic 38][pic 39][pic 40][pic 41]

[pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54]

[pic 55][pic 56][pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67][pic 68][pic 69][pic 70][pic 71][pic 72][pic 73][pic 74][pic 75][pic 76][pic 77][pic 78][pic 79][pic 80][pic 81][pic 82][pic 83][pic 84][pic 85][pic 86][pic 87][pic 88]

[pic 89][pic 90][pic 91][pic 92][pic 93][pic 94]

Recorrido Búsqueda preferente por profundidad

A, B, C, D, E, I, J, F, K, L, C, G, M, N, H, O, P, D

Se inicia en el nodo A, se escoge la ruta más profunda, el nodo B.

Se escoge la ruta más profunda, el nodo E.

Se escoge la ruta más profunda, el nodo I, no tiene nodos más profundos.

Se revierte la búsqueda en los nodos menos profundos, se devuelve a E.

Como E tiene otro nodo profundo, se escoge J. no tiene nodos más profundos.

Se revierte la búsqueda en los nodos menos profundos, se devuelve a E.

Se revierte la búsqueda en los nodos menos profundos, se devuelve a B.

B tiene otro nodo profundo, se escoge F.

Se escoge la ruta más profunda, el nodo K, no tiene nodos más profundos.

Se revierte