INTELIGENCIA ARTIFICIAL MOMENTO 2

POR

WILDER MANUEL BRAVOMARTA ISABEL CUESTA PAREDES

OLIVER MARTINEZ CAMPOLUIS CARLOS MENDOZA

RAFAEL SEBASTIAN TAPIA

PRESENTADO AANGELA MARIA GONZALEZ

TUTORA

UNIVERSIDAD NACIONAL ABIERTA Y A DISTANCIAESCUELA DE CIENCIAS BASICAS TECNOLOGIA E INGENIERIA

ABRIL 2015.

INTRODUCCIN

Cuando nos referimos a Inteligencia Artificial, decimos que es la rama de las

ciencias de la informtica, que se basa en el comportamiento inteligente de los

sistemas informticos, a travs de mquinas construidas por el hombre.

En el presente trabajo colaborativo, esta asignatura, tiene como finalidad trabajar

sobre los mtodos de bsqueda (Heurstico Ciego) de un agente, son una serie de

esquemas de representacin del conocimiento; lo ms importante es afianzar los

conocimientos por medio de los problemas asignados por el tutor adquiriendo

habilidades dignas de ingenieros de sistemas unadistas.

OBJETIVOS

GENERALTener presente los mtodos de bsqueda (heurstico ciego), para ser utilizados en laprogramacin y solucionar, los problemas que se presentan en la Inteligencia Artificial.

ESPECIFICOS Identificar la importancia de los mtodos de bsqueda en la Inteligencia Artificial Diferenciar los tipos de bsqueda e implementarlos Solucionar problemas utilizando los mtodos representativos de bsqueda, de

manera adecuada, para encontrar la meta Identificar y representar un algoritmo gentico a base del problema

DESARROLLO TRABAJO COLABORATIVO

El equipo de trabajo colaborativo debe enviar a travs del foro una presentacinnica que represente el trabajo de todos los integrantes que contenga la solucina los siguientes planteamientos:

a. explicar que es, las caractersticas, las estrategias de bsquedas y por mediode ejemplos identificar qu papel tiene la bsqueda en la inteligencia artificial.

b. Teniendo en cuenta el trabajo individual, elabore un cuadro comparativoentre la bsqueda heurstica y la bsqueda ciega

c. Explique que es un algoritmo gentico, mediante un ejemplo explique suproceso de construccin.

d. Desarrollo de los ejercicios de la hoja de Ruta que se encuentra en el entornode aprendizaje prctico.

A. Explicar que es, las caractersticas, las estrategias de bsquedas y por medio deejemplos identificar qu papel tiene la bsqueda en la inteligencia artificial.

Debido a la complejidad, se generan ciertas dudas sistemticas que deben serrespondidas para emplear el programa, este realiza la funcin, siendo dirigido por ungrafo en el que cada nodo segn las caractersticas que requiere tendr caractersticasespecificas que ayudan al funcionamiento del programa y completa el sistema.

Podemos definir la bsqueda de resolucin de problemas como el proceso quepartiendo de unos datos iniciales y utilizando un conjunto de procedimientos escogidosa priori, es capaz de determinar el conjunto de pasos o elementos que nos llevan a loque denominaremos una solucin. Esta solucin puede ser, por ejemplo, el conjunto deacciones que nos llevan a cumplir cierta propiedad o como deben combinarse loselementos que forman los datos iniciales para cumplir ciertas restricciones.Las caractersticas que describen la bsqueda de la solucin a un problema laspodemos identificar los siguientes elementos:

Un punto de partida, los elementos que definen las caractersticas del problema.

Un objetivo a alcanzar, qu queremos obtener con su resolucin.

Acciones a nuestra disposicin para resolver el problema, de qu herramientasdisponemos para manipular los elementos que describen el problema.

Restricciones sobre el objetivo, qu caractersticas debe tener la solucin

Elementos definidos por el dominio concreto que son relevantes en el problema,qu conocimiento tenemos en el dominio que nos puede ayudar a resolver elproblema de una manera eficiente.

Atendiendo a estos criterios podemos clasificar los algoritmos principales de bsquedaen:

Algoritmos de bsqueda no informada: Estos algoritmos no tienen en cuenta el costede la solucin durante la bsqueda. Su funcionamiento es sistemtico, siguen un ordende visitas de nodos fijo, establecido por la estructura del espacio de bsqueda. Losprincipales ejemplos de estos algoritmos son el de anchura prioritaria, el de profundidadprioritaria y el de profundidad iterativa.

Algoritmos de bsqueda heurstica y bsqueda local: Estos algoritmos utilizan unaestimacin del coste o de la calidad de la solucin para guiar la bsqueda, de maneraque se basan en algn criterio heurstico dependiente del problema. Estos algoritmosno son sistemticos, de manera que el orden de exploracin no lo determina laestructura del espacio de bsqueda sino el criterio heurstico. Algunos de ellos tampocoson exhaustivos y basan su menor complejidad computacional en ignorar parte delespacio de bsqueda.Existen bastantes algoritmos de este tipo con funcionamientos muy diferentes, nosiempre garantizan el encontrar la solucin ptima, ni tan siquiera el hallar una solucin.Los principales ejemplos de estos algoritmos son A*, IDA*, Branch & Bound y Hill-climbing

B. Teniendo en cuenta el trabajo individual, elabore un cuadro comparativo entre labsqueda heurstica y la bsqueda ciega

CONCEPTO DEFINICIN CARACTERSTICAS TIPOS

Bs

qued

a C

iega

Es lainformacinsobre unnodo delproblema,para sersolucionadode manerafragmentada.

Utilizan lasestrategiasnecesarias que seconsideran en larelacin, pasando lainformacin de unnodo a otro. Nosiendo consideradoel anterior.Creciendo el rbol deforma sistemtica yno se realizananlisis entre losestados.

a) Por profundidad:La bsqueda seempieza por unarama del rbol, hastaque se encuentra lasolucin. Si a la final,no hay evento,retrocedemos abuscar en otra ramau hoja.

b) Por amplitud:Utilizando el Sistemade Produccin. Sialguno de los nodosdel primer nivelcorresponde alestado objetivodonde acaba; en elcaso contrario generelos nodos sucesoresno redundante delprimer nivel, esto eslos nodos delsegundo nivel,utilizando el Sistemade Proteccin. Elproceso se repitehasta encontrar elestado meta ocuando no seaposible generarnuevos sucesores.-

Bs

qued

a H

eurs

tica

Es lainformacinsobre elproblemaque permitereducir larapidez de labsqueda.

Para hallar lasolucin con mayoreficacia, utilizan elconocimiento deldominio y se adaptael solucionador. Asse avanzaencontrando lasolucin ms rpido.El crecimiento delrbol es inyectadopor el nodo anterior.

a) Templado: Es untipo de sistema debsqueda meta-heurstica, parasolucionar y optimizara nivel global,encontrandoaproximaciones alvalor optimo de unafuncin.

b) Tab: Dirige y orientala bsqueda de otroprocedimiento mslocal, de bsqueda.

:

C. Explique que es un algoritmo gentico, mediante un ejemplo explique su proceso deconstruccin.

Algoritmo Gentico:

Cuando nos referimos a Algoritmo, nos referimos a los pasos que se describen enun proceso, para llegar a la solucin. En 1970, por Henry Hollland se origino una delas lneas ms importantes de la Inteligencia Artificial, la de los algoritmos genticos,presentando distintas variaciones, dependiendo de los lineamientos, mutacin ocruzamientos en la seleccin, as mismo se toma la decisin en los reemplazos yobtener nuevos individuos en la poblacin.

Un algoritmo gentico es un mtodo de bsqueda que imita la teora de la evolucinbiolgica de Darwin para la resolucin de problemas. Para ello, se parte de unapoblacin inicial de la cual se seleccionan los individuos ms capacitados para luegoreproducirlos y mutarlos para finalmente obtener la siguiente generacin deindividuos que estarn ms adaptados que la anterior generacin.

Un algoritmo gentico consiste en una funcin matemtica o una rutina desoftware que toma como entradas a los ejemplares y retorna como salidas cules deellos deben generar descendencia para la nueva generacin.

Versiones ms complejas de algoritmos genticos generan un ciclo iterativo quedirectamente toma a la especie (el total de los ejemplares) y crea una nuevageneracin que reemplaza a la antigua una cantidad de veces determinada por supropio diseo. Una de sus caractersticas principales es la de ir perfeccionando supropia heurstica en el proceso de ejecucin, por lo que no requiere largos perodosde entrenamiento especializado por parte del ser humano, principal defecto de otrosmtodos para solucionar problemas, como los Sistemas Expertos.

Ejemplo Marea: Ejemplo de un Algoritmo Gentico sencillo con un vector devalores binarios

El problema a resolver

El comienzo siempre es igual: Tenemos un problema, adems ese problema loqueremos resolver usando algoritmos evolutivos. Supongamos que tenemos lafuncin marea cuya expresin matemtica es la siguiente:

y cuya grfica se muestra en la Figura 1. El problema al que nos enfrentamos esencontrar las coordenadas (x,y), que maximicen la funcin f(x,y).

Figura 1:Grfica de la funcin "marea".

Si observamos la grfica de la funcin (ver Figura 1) la forma de la funcin vahaciendo ondulaciones conforme se acerca a la coordenado (0,0), alcanzando elmximo en dicha coordenada, de forma que f(x,y)=1 para x=y=0.

Eleccin del tipo de individuo

Una vez conocido el problema a resolver, deberemos decidir es los tipos de datosque usaremos para codificar la solucin, en este ejemplo usaremos un vector de 128bits, donde los primeros 64bits, sern el valor binario de la x y los restantes 64bits,sern la codificacin en binario del valor y. Por tanto, de entre los tipos de individuosde OPEAL escogemos VectorIndi que sirve pare representar un vector de valoresbinarios.

Creacin de la funcin de adecuamiento o fitness

Ya sabemos el tipo de individuo a usar y el problema a resolver, por lo que ahoradebemos construir nuestra funcin de fitness (funcin de adecuamiento) que mide lobuena que es el individuo, en nuestro ejemplo calcular f(x,y) a partir del individuode 64bits, cuyos primeros 32bits son para la x y los restantes 32bits para la y.Vamos a construir nuestra funcin de fitness en Perl, para nuestro problema ynuestra representacin:

my $rr = sub {#Cogemos el individuo a evaluarmy $chrom = shift;

#Pasamos el individuo a una cadenamy $str = $chrom->Chrom();

#El fitness (adecuamiento), inicialmente, es uno (caso de divisin por cero)my $fitness = 1;

#extraemos los dos nmeros binariosmy $l2=length($str)/2;my $x=eval("0b".substr ($str, 0, $l2));my $y=eval("0b".substr ($str, $l2));

#Los normalizamos y los pasamos al rango [0,1]my $max=(2 ** ($l2) )-1;$x=$x/$max;$y=$y/$max;

#Calculamos la funcin mareamy $sqrt=sqrt( ($x*$x) + ($y*$y) );$fitness= sin( $sqrt ) / $sqrt if ($sqrt !=0 );

#Y devolvemos el fitness calculadoreturn $fitness;

};

Si nos fijamos un poco las dos primeras instrucciones que hemos ejecutado ennuestra funcin de fitness se utilizarn en todas las funciones de fitness queprogramemos. Con la primera cogemos el individuo a evaluar y con la segundacogemos el cromosoma del individuo.

Creacin de la poblacin inicial

Una vez elegidos el tipo de individuo y construida la funcin de adecuamiento(fitness). Vamos a construir la poblacin inicial de individuos que evolucionarn:#Definimos la poblacin inicial$numBits=64; #Nmero de bits a usar 32bits->x 32bits->y$popSize=100; #Tamao de la poblacin que ser evolucionado, usaremos 100individuosmy @pop; #Poblacin de individuos

#Creamos $popSize individuosfor ( 0..$popSize ) {

my $indi = new BinaryIndi $numBits ; #Creamos individuos aleatoriospush( @pop, $indi ); #Los aadimos a la poblacin

}

Eleccin del algoritmo evolutivo y operadores genticos

Ahora tenemos que decidir el algoritmo evolutivo de OPEAL a usar, escogeremosEZFullAlgo, que es un algoritmo evolutivo simple. Para usar dicho algoritmotendremos que definir como se realiza una sla generacin de dicho algoritmo, estolo haremos con EasyAlgorithm.Para describir una generacin del algoritmo, nos hace falta la funcin deadecuamiento (que ya la tenemos hecha) y especificarle los operadores a usar.Como operadores usaremos la mutacin de un slo bit (MutationOne) y el cruceclsico de dos puntos (Crossover). Entonces quedara:

#Definimos los operadores de variacinmy $m = new MutationOne; #Cambia a un slo bitmy $c = new Crossover; #Cruce en 2 puntos clsico

#Usamos estos operadores para definir una generacin del algoritmo. Lo cual# no es realmente necesario ya que este algoritmo define ambos operadores por# defecto. Los parmetros son la funcin de fitness, la tasa de seleccin y los# operadores de variacin.my $generation = new EasyAlgorithm( $rr, 0.2, [$m, $c] );

Ahora tenemos que especificar el terminador del algoritmo evolutivo, es decir, elobjeto que se encarga de decidir cundo termina el algoritmo evolutivo. En nuestroejemplo vamos a parar cuando lleguemos a 200 generaciones.

my $term; #Terminadormy $numGens=200; #Nmero de generaciones

$term = new GenerationalTerm $numGens ; #Utilizamos un terminadorgeneracional.

Despus de definir el terminador y una vez que tenemos definida una slageneracin, creamos el algoritmo evolutivo (habamos escogido EZFullAlgo) y loejecutamos sobre la poblacin inicial que habamos construido:

#Definimos el algoritmomy $fullAlgo = new EZFullAlgo $generation, $term, 1 ;

#Ejecutamos el algoritmo$fullAlgo->apply( \@pop );

Terminando

Y finalmente, en nuestro script, mostramos los resultados:#Mostramos los resultadosprint "La mejor solucin encontrada es ", $pop[0]->asString(), "\n";

Adems necesitamos incluir, al principio, los mdulos a usar:#Incluimos las libreras de OPEAL que nso van a hacer faltause EasyAlgorithm;use EZFullAlgo;use BinaryIndi;use GenerationalTerm;

Finalmente hemos obtenido el fichero marea-tutorial.pl (en este fichero se haaadido un terminador delta, se permite que ciertos valores se pasen comoparmetros y se ha mejorado la presentacin de resultados).

D. Desarrollo de los ejercicios de la hoja de Ruta que se encuentra en el entorno deaprendizaje prctico

Responda y justifique la respuesta de cada uno de los siguientes ejercicios:

a. Dentro de las bsquedas sin contar con informacin tambin conocidas comobsquedas ciegas se encuentran seis estrategias, segn la grfica indique a questrategia corresponde y justifique su respuesta:

Para buscar la solucin a este problema, se debe utilizar la estrategia de bsquedaprimero en anchura. Vemos que al expandir el nodo 2 (B) los que siguen en cola deexploracin son los vecinos del mismo nivel (C, D) para luego bajar al siguiente nivel(E, F)

b. Teniendo en cuenta la siguiente grfica, en el tipo de bsqueda preferente porprofundidad Cul es el recorrido? Justifique su respuesta. Si se utiliza la bsquedaA* cual sera el resultado?

En este caso utilizando el mtodo en profundidad el recorrido seria el siguiente:

Estado inicial en A: Estado inicial en B:

La bsqueda heurstica A* se utiliza para hallar una solucin ms corta y de menorcosto y se necesita informacin del problema a resolver por lo que en este caso noaplica esa forma de solucin.

CONCLUSIN

Al terminar el presente trabajo podemos concluir que los mtodos de bsqueda a laresolucin de problemas hace parte vital del desarrollo de la inteligencia artificial, yaque cada vez que se vea un problema ms complejo se busca que la solucin seasemejante a la forma de resolver los conflictos en la vida humana, utilizando tcnicasms recursivas para simplificar computacionalmente las dificultades que se puedanpresentar en los sistemas de inteligencia artificial.

1. REFERENCIAS

Pginas web:

http://elvex.ugr.es/decsai/iaio/slides/A3%20Search.pdf

http://expo.itch.edu.mx/view.php?f=ai_30#page5

https://docs.google.com/presentation/d/1t8sQObYfa0FINy3yvQnB5w2GN_0xHyBx4PzQVQxg8v4/edit?pli=1#slide=id.p16

http://www.nebrija.es/~cmalagon/ia/apuntes/algoritmosgeneticos.pdfhttp://es.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico#/media/File:Evolutionary_algorithm.svg

http://www.bubok.es/libros/2050/Inteligencia-Artificial-Resolucion-de-problemas-Algoritmos-de-busquedahttps://www.youtube.com/watch?v=g6l685-LMbUhttps://www.youtube.com/watch?v=Y4tndzfQkoEhttps://www.youtube.com/watch?v=3VA5brfM68Yhttps://www.youtube.com/watch?v=OieuTB8qKys

REFERENCIAS BIBLIOGRAFICAS

STUART Russel, NORVIG Peter. Inteligencia artificial Un Enfoque Moderno. SegundaEdicin. Ed. Pearson. Madrid, 2004. Tomado el 5 de Abril de 2015. Paginas 67-90.

Goldberg, D. (1989) Genetics Algorithms in Search, Optimization and Machine Learning.Addison Wesley. Extraido de intertet el 06/04/2015. disponible en:http://www.gbv.de/dms/ilmenau/toc/01600020X.PDF.

Tolmos, R ( ) Introduccin a los algoritmos genticos y sus aplicaciones. Extraido deinternet el 06/04/2015. disponible en: http://www.uv.es/asepuma/X/J24C.pdf

CAC Coello ( ) algoritmo genetico y sus aplicaciones . Extraido de internet el06/04/2015 disponible en: http://delta.cs.cinvestav.mx/~ccoello/revistas/genetico.pdf.gz

Arranz de la Pea, Jorge. Parra Truyol, Antonio. Algoritmos genticos. Recuperado el 8de abril del 2015 de: http://www.it.uc3m.es/~jvillena/irc/practicas/06-07/05.pdf

J.J. Merelo. J.G. Castellano. (2001). Opeal. Tomado el 8 de abril del 2015 de:http://opeal.sourceforge.net/texample1.htm