Estudio de las Técnicas de Inteligencia Artificial mediante el apoyo de un Software Educativo (página 3)

Por ejemplo, en una red que se va a aplicar al diagnóstico de imágenes médicas; durante la fase de entrenamiento el sistema recibe imágenes de tejidos que se sabe son cancerígenos y tejidos que se sabe son sanos, así como las respectivas clasificaciones de dichas imágenes. Si el entrenamiento es el adecuado, una vez concluido, el sistema podrá recibir imágenes de tejidos no clasificados y obtener su clasificación sano/no sano con un buen grado de seguridad. Las variables de entrada pueden ser desde los puntos individuales de cada imagen hasta un vector de características de las mismas que se puedan incorporar al sistema (por ejemplo, procedencia anatómica del tejido de la imagen o la edad del paciente al que se le extrajo la muestra).

3.2.2.1 Estructura RNA.

Están compuestas por unidades estructurales también conocidas como neuronas, conectadas entre sí. El modelo básico de una neurona es el siguiente:

Figura III.3 Estructura Red Neuronal Artificial

Típicamente las redes neuronales poseen una capa de entrada (input layer), una capa de salida (output layer), y una o varias capas ocultas intermedias (hidden layers) [Vega, 2000].

La mayoría de los científicos coinciden en que una RNA es muy diferente en términos de estructura de un cerebro animal. Al igual que el cerebro una RNA se compone de un conjunto masivamente paralelo de unidades de proceso muy simples y es en las conexiones entre estas unidades donde reside la inteligencia de la red. Sin embargo, en términos de escala, un cerebro es muchísimo mayor que cualquier RNA creada hasta la actualidad, y las neuronas artificiales también son más simples que su contrapartida animal.

Biológicamente, un cerebro aprende mediante la reorganización de las conexiones sinápticas entre las neuronas que lo componen. De la misma manera, las RNA tienen un gran número de procesadores virtuales interconectados que de forma simplificada simulan la funcionalidad de las neuronas biológicas. En esta simulación, la reorganización de las conexiones sinápticas biológicas se modela mediante un mecanismo de pesos, que son ajustados durante la fase de aprendizaje. En una RNA entrenada, el conjunto de los pesos determina el conocimiento de esa RNA y tiene la propiedad de resolver el problema para el que la RNA ha sido entrenada.

Por otra parte, en una RNA, además de los pesos y las conexiones, cada neurona tiene asociada una función matemática denominada función de transferencia. Dicha función genera la señal de salida de la neurona a partir de las señales de entrada. La entrada de la función es la suma de todas las señales de entrada por el peso asociado a la conexión de entrada de la señal. Algunos ejemplos de funciones de transferencia son la función escalón, la lineal o mixta, la sigmoidal y la función gaussiana.

La topología de una red neuronal estará determinada por el número de neuronas que esta tenga, por la forma en éstas estén ordenadas (en capas) y por la naturaleza de las conexiones presentes.

3.2.2.2 Características y Ventajas.

Las Redes de Neuronas Artificiales (RNA) tienen muchas ventajas debido a que están basadas en la estructura del sistema nervioso, principalmente el cerebro [Daza, 1997].

• Aprendizaje: Las RNA tienen la habilidad de aprender mediante una etapa que se llama etapa de aprendizaje. Esta consiste en proporcionar a la RNA datos como entrada a su vez que se le indica cuál es la salida (respuesta) esperada.

• Auto organización: Una RNA crea su propia representación de la información en su interior, descargando al usuario de esto.

• Tolerancia a fallos. Debido a que una RNA almacena la información de forma redundante, ésta puede seguir respondiendo aceptablemente aún si se daña parcialmente.

• Flexibilidad: Una RNA puede manejar cambios no importantes en la información de entrada, como señales con ruido u otros cambios en la entrada (ej. si la información de entrada es la imagen de un objeto, la respuesta correspondiente no sufre cambios si la imagen cambia un poco su brillo o el objeto cambia ligeramente).

• Tiempo real: La estructura de una RNA es paralela, por lo cual si esto es implementado con computadoras o en dispositivos electrónicos especiales, se pueden obtener respuestas en tiempo real.

• Capacidad de Asociación (Generalización).

• Seguridad ante caídas del sistema.

• Procesamiento masivamente paralelo.

• Representación y Procesamiento distribuido de la información.

3.2.2.3 Modelos.

Existe una serie de modelos que aparecen en la mayoría de estudios académicos y la bibliografía especializada.

Diferentes modelos de redes son utilizados para resolver diferentes tipos de problemas. En la siguiente tabla puede observarse algunos de los modelos más utilizados y su campo de aplicación.

Tabla III.1. Modelos y Campos de Aplicación RNA

3.2.2.4 Arquitectura de Redes Neuronales Artificiales.

Diferentes tipos de interconexión implican diferentes comportamientos de la red. El flujo de la información puede ser unidireccional desde la capa de entrada hacia la capa de salida (redes feedforward) o bidireccional con retroalimentación (redes recurrentes).

Por ejemplo, las redes que tienen flujo de datos unidireccional (feedforward) son estáticas, es decir, producen sólo un grupo de valores de salida en lugar de una secuencia de valores de salida para una entrada dada, además sus salidas no dependen de los valores anteriores de la red. Por otro lado las redes neuronales recurrentes o realimentadas son sistemas dinámicos. Según la arquitectura de la conexión las redes neuronales se pueden clasificar, entre otras, como: Red Neuronal Monocapa, Red Neuronal Multicapa y Red Neuronal Realimentada.

Red Neuronal Monocapa: Las redes monocapa están formadas sólo por una capa de neuronas, y suelen utilizarse frecuentemente en tareas relacionadas con la regeneración de información incompleta o distorsionada que se presenta a la red.

Figura III.4. Red Neuronal Monocapa

Red Neuronal Multicapa: Son las estructuras más comunes; además de la capas de entrada y salida, poseen un número de capas intermedias u ocultas que mejoran su desempeño.

Figura III.5. Red Neuronal Multicapa

Red Neuronal Recurrente: Se caracteriza porque sus salidas pueden ser utilizadas como entradas. La estabilidad de la red es un importante factor a considerar en este tipo de arquitectura [Fuente, 2000].

Figura III.6. Red Neuronal Realimentada

Aprendizaje: Una de las principales características de las redes neuronales es su capacidad de aprendizaje, esto se logra a través de la repetitiva presentación de ejemplos, lo cual permite adaptar los pesos sinápticos de las neuronas.

Otra clasificación que se suele hacer es en función del tipo de aprendizaje de que es capaz (si necesita o no un conjunto de entrenamiento supervisado). Para cada tipo de aprendizaje encontramos varios modelos propuestos por diferentes autores:

• Aprendizaje supervisado: necesitan un conjunto de datos de entrada previamente clasificado o cuya respuesta objetivo se conoce. Ejemplos de este tipo de redes son: el perceptrón simple, la red Adaline, el perceptrón multicapa y la memoria asociativa bidireccional.

• Aprendizaje no supervisado o auto organizado: no necesitan de tal conjunto previo. Ejemplos de este tipo de redes son: las memorias asociativas, las redes de Hopfield, la máquina de Bolzman y la máquina de Cauchy, las redes de aprendizaje competitivo, las redes de Kohonen o mapas auto organizados y las redes de resonancia adaptativa (ART) .

• Redes híbridas: son un enfoque mixto en el que se utiliza una función de mejora para facilitar la convergencia. Un ejemplo de este último tipo son las redes de base radial.

3.2.2.5 Aplicaciones.

Las características de las RNA las hacen bastante apropiadas para aplicaciones en las que no se dispone a priori de un modelo identificable que pueda ser programado, pero se dispone de un conjunto básico de ejemplos de entrada (previamente clasificados o no).

Esto incluye problemas de clasificación y reconocimiento de patrones de voz, imágenes, señales, etc. Asimismo se han utilizado para encontrar patrones de fraude, hacer predicciones en el mercado financiero, hacer predicciones de tiempo atmosférico, etc.

También se pueden utilizar cuando no existen modelos matemáticos precisos o algoritmos con complejidad razonable.

Otro tipo especial de redes neuronales artificiales se ha aplicado en conjunción con los algoritmos genéticos (AG) para crear controladores para robots. En este tipo de aplicación el genoma del AG lo constituyen los parámetros de la red (topología, algoritmo de aprendizaje, funciones de activación, etc.) y la adecuación de la red viene dada por la adecuación del comportamiento exhibido por el robot controlado (normalmente una simulación de dicho comportamiento).

En resumen las redes neuronales artificiales (RNA) son modelos computacionales que tratan de replicar, de manera simplificada, el complejo funcionamiento del cerebro humano utilizando métodos o modelos matemáticos muy sofisticados. Su capacidad de aprendizaje a través de ensayos repetidos, las ha hecho muy populares en una amplia variedad de aplicaciones en todas las ciencias. En este sentido las redes neuronales resultan una herramienta fundamental ya que proponen una estrategia de resolución de problemas basada en la adaptación al entorno de información.

3.2.3 Algoritmos Genéticos (AG).

Los Algoritmos Genéticos (AGs) son métodos adaptativos que pueden usarse para resolver problemas de búsqueda y optimización. Están basados en el proceso genético de los organismos vivos. A lo largo de las generaciones, las poblaciones evolucionan en la naturaleza de acorde con los principios de la selección natural y la supervivencia de los más fuertes, postulados por Darwin. Por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas.

También los algoritmos genéticos son métodos de optimización: dada una función objetivo, el AG lleva a cabo una búsqueda en el espacio de soluciones intentando encontrar la solución que minimiza dicha función objetivo. Por lo tanto, los AG están indicados para resolver todo tipo de problemas que puedan ser expresados como un problema de optimización.

Básicamente, los algoritmos genéticos (AG) funcionan como sigue: dada una población de soluciones, y en base al valor de la función objetivo para cada una de los individuos (soluciones) de esa población, se seleccionan los mejores individuos (los que minimizan la función objetivo) y se combinan para generar otros nuevos. Este proceso se repite cíclicamente [García, 2001].

Como se puede ver, el proceso es similar al que se da en la naturaleza: una serie de individuos compiten por su supervivencia; los mejor adaptados al medio (los que optimizan la función objetivo) sobreviven y tienen más posibilidades de aparearse, transmitiendo así parte de su material genético "mejor adaptado" a las generaciones siguientes. De esta manera, generación tras generación, la especie consigue una mayor y mejor adaptación al medio en el que vive.

Algo de Historia: Desde finales de los años 50 y principios de los 60 se desarrollaron trabajos por algunos biólogos para simular sistemas genéticos en una computadora. A pesar de estos trabajos, se reconoce al profesor John Holland de la Universidad de Michigan como el creador de los AG con su trabajo sobre teoría de los sistemas adaptativos, en el año 62. Es Holland el primero que adaptó la idea de la genética a sistemas artificiales. Su objetivo era lograr que las computadoras aprendieran por sí mismas. A la técnica que inventó Holland se le llamó originalmente "planes reproductivos", pero se hizo popular bajo el nombre "algoritmo genético" tras la publicación de su libro en 1975.

Terminología Usada: En el trabajo con AG se maneja una serie de términos "importados" de la genética natural. No siempre es adecuada la analogía, pero estos son comúnmente aceptados:

Tabla III.2 Términos de Algoritmos Genéticos

3.2.3.1 Componentes de un AG.

Los AG trabajan a partir de una población inicial de estructuras artificiales que van modificando repetidamente a través de la aplicación de los siguientes operadores genéticos:

• Operador de Selección o Darwiniano

• Operador de Cruzamiento o Mendeliano

• Operador de Mutación.

Para utilizar los AG es necesario encontrar una posible estructura para representar las soluciones. Pensando este asunto como el problema de buscar en un espacio de estados, una instancia de esta estructura representa un punto o un estado en el espacio de búsqueda de todas las posibles soluciones. Así, una estructura de datos en el AG consistirá en uno o más cromosomas (frecuentemente uno), el cual se representa comúnmente como una cadena de bits (existen otras representaciones) [Rodríguez, 2004].

Cada cromosoma (cadena) es una concatenación de un número de subcomponentes llamados genes. La posición de un gen en el cromosoma se conoce como locus y sus valores como alelos. En la representación como cadena de bits, un gen es un bit o una cadena de bits, un locus es su posición en la cadena y un alelo es su valor (0 ó 1 si es un bit).

Los AG realizan una maximización por defecto, para los problemas de minimización los valores de la función objetivo pueden ser negados y traslados con vistas a tomar valores positivos para producir así la adaptabilidad.

3.2.3.2 Funcionamiento de un AG.

El modo de trabajo de un AG puede resumirse en el siguiente esquema el funcionamiento de un AG simple. El mecanismo de un AG simple es:

• El AG simple genera aleatoriamente una población de n estructuras (cadenas, cromosomas o individuos).

• Sobre la población actúan los operadores transformando la población. Una vez completada la acción de los tres operadores se dice que ha transcurrido un ciclo generacional.

• Luego se repite el paso anterior mientras no se garantice el criterio de parada del AG.

Figura III.7. Diagrama funcional de un algoritmo genético.

• El operador de selección o Darwiniano realiza la selección de las cadenas de acuerdo a su adaptabilidad para el posterior apareamiento.

• El operador de cruzamiento o Mendeliano realiza la recombinación del material genético de dos cadenas padres.

• El operador de Mutación al estilo del operador natural realiza la mutación de un gen dentro de un cromosoma o cadena a sus diferentes formas alelomorfas.

• Para cada uno de estos operadores está asociado el uso de probabilidades y la generación de números aleatorios.

• El AG ejecuta para un número fijo de generaciones o hasta que se satisface algún criterio de parada.

Desde el punto de vista de la comparación de los AG con otros métodos de búsqueda se pueden enmarcar sus diferencias en cuatro aspectos:

1- Trabajan con una codificación de los parámetros y no con los parámetros mismos.

2- Buscan a partir de una población de puntos y no de un punto simple.

3- Usan directamente la función objetivo y no la derivada u otro conocimiento auxiliar.

• 4-   Usan reglas de transición probabilísticas y no determinísticas.

¿Por qué utilizar AG y no otros métodos conocidos?

Las razones que se pueden argumentar son varias. Los métodos conocidos son buenos mientras el problema no es muy complejo. Los AG permiten la solución eficiente de funciones extremadamente complejas.

Las potencialidades de los AG se pueden resumir por sus habilidades para resolver una variedad de problemas muy difíciles:

• ? Trabajar sin conocimiento previo de la función a optimizar.

• ? Optimizar funciones "ruidosas".

• ? Trabajar sin información secundaria como gradientes.

La mayoría de los especialistas en este tema coinciden en que los AG pueden resolver las dificultades representadas en los problemas de la vida real que a veces son insolubles por otros métodos.

Para [Rodríguez, 2004] el tema central de la investigación en AG consiste en la robustez: el balance entre la eficacia y la eficiencia necesaria para sobrevivir en muchos ambientes diferentes.

3.2.3.3 Aplicaciones tradicionales de AG.

Los algoritmos genéticos se utilizan en sistemas de búsqueda y optimización, este es el campo en que más aplicaciones se reportan, habiéndose realizado incluso trabajos con funciones muy complejas. También se ha trabajado en la obtención de soluciones a ecuaciones no lineales [Costa, 2002].

Desde aplicaciones evidentes, como la biología o la medicina, hasta otros campos como la industria (clasificación de piezas en cadenas de montaje). Los algoritmos genéticos poseen un importante papel en este ámbito.

3.3 Búsqueda en Inteligencia Artificial.

Los investigadores pioneros en Inteligencia Artificial tuvieron como su primer objetivo la solución de problemas que fueron difíciles de resolver mediante las técnicas computacionales existentes. Como se dijo antes, estos problemas generalmente no tienen solución algorítmica conocida o esta es tan compleja que no tiene una implementación práctica computacional.

La respuesta fue desarrollar nuevas técnicas de solución de problemas, similares a las humanas, una de las más importantes fue la búsqueda.

La búsqueda en la I.A. difiere de la búsqueda convencional sobre estructuras de datos esencialmente en que se busca en un espacio problema, no en una pieza de dato particular. Se busca un camino que conecte la descripción inicial del problema con una descripción del estado deseado para el problema, es decir, el problema resuelto. Este camino representa los pasos de solución del problema.

El proceso de buscar una solución a un problema produce un espacio solución, o sea, la parte del espacio problema que se examina realmente. A diferencia de las estructuras de datos que están predefinidas y ya existen cuando comienza la búsqueda, los espacios problema son generalmente definidos proceduralmente, es decir, el espacio problema es creado a medida que es explorado. Se usan procedimientos para definir los siguientes estados posibles en el espacio a través de los cuales la búsqueda puede continuar desde el estado actual. Solamente los caminos explorados tienen que estar definidos explícitamente.

Hay diferentes alternativas para realizar la búsqueda. Desde un punto de vista podemos apreciar tres alternativas: aleatoria, a ciegas y dirigida. Con el siguiente ejemplo se ilustran estos. Supóngase que está en París sin un mapa y no habla francés ¿Cómo llegar hasta la torre Eiffel?

Un método podía ser tomar aleatoriamente una calle esperando que más pronto que tarde se llegará a la torre. Esta búsqueda aleatoria puede llevar a encontrar la torre pero puede requerir una cantidad infinita de tiempo por la forma arbitraria en la cual seleccionamos un camino (el mismo puede tomarse múltiple veces).

Otra alternativa es seguir exhaustivamente cada calle de inicio a fin. Cuando se alcanza un final se busca una calle paralela y se sigue esta en dirección opuesta independientemente de si nos acercamos o alejamos del objetivo. Eventualmente esta variante consideraría todas las posiciones de nuestro espacio problema. Este tipo de búsqueda se llama a ciegas, ya que no usa conocimiento de cuan cerca estamos de la solución para tomar un determinado camino.

Alternativamente, podemos usar nuestro conocimiento sobre la torre para mejorar la eficiencia de la búsqueda. Suponiendo que el extremo superior de la torre puede ser visto desde cualquier lugar del espacio problema, podemos tomar la calle que nos parezca nos lleve en esa dirección. Esta es llamada búsqueda dirigida. La búsqueda dirigida es la base de la I.A.

En la siguiente figura se relacionan estas tres alternativas de búsqueda:

Figura III.8 Alternativas de Búsqueda.

Otro aspecto a considerar es la dirección de la búsqueda. Puede ser dirigida por dato (forward) o dirigida por objetivo (backward).

Una búsqueda dirigida por dato comienza a partir de la información (o hechos) y trata de extraer conclusiones. Una búsqueda dirigida por objetivo comienza a partir de expectativas de lo que es el objetivo o lo que sucederá, entonces busca las evidencias que soportan o contradicen esas expectativas (o hipótesis).

3.3.1 Definición formal de la solución de problemas en la I.A.

Para resolver un problema primero debemos identificar:

• Un punto de partida.

• Un objetivo a alcanzar.

• Acciones a disposición para resolver el problema.

• Restricciones sobre el objetivo (p.e. de costo).

• Elementos del dominio que son relevantes en el problema (p.e., conocimiento incompleto del punto de partida).

Estrategias de Búsqueda: La estrategia de búsqueda define el criterio para seleccionar el siguiente nodo a expandir. La estrategia se avalúa atendiendo a cuatro aspectos:

• Completitud: ¿Garantiza la estrategia encontrar una solución cuando esta exista?

• Complejidad del tiempo: ¿Cuánto tiempo requiere encontrar una solución?

• Complejidad del espacio: ¿Cuánta memoria se necesita para realizar la búsqueda?

• Optimalidad: ¿Encuentra la estrategia la solución de mayor calidad cuando haya varias soluciones diferentes?

En general y con mucha frecuencia las estrategias de búsqueda son:

• búsqueda exhaustiva.

• búsqueda a ciegas o no informada.

• búsqueda informada o heurística.

En la búsqueda exhaustiva la idea es examinar el espacio de estado completamente de una manera ordenada, usando todos los operadores y generando todos los sucesores posibles para encontrar la solución deseada. La búsqueda a ciegas es aquella donde no existe ninguna información para decidir que nodo expandir, no se conoce la cantidad de pasos o el costo del camino desde el estado actual hasta el objetivo. También se denomina búsqueda no informada. En el otro caso, cuando existe información para decidir, la búsqueda se denomina informada o heurística.

3.3.1.1 Búsqueda a ciega (blind search) o sin información.

La búsqueda a ciegas es una colección de procedimientos que investigan el espacio de estados de manera exhaustiva pero ciega. Estos procedimientos se consideran métodos débiles, pues imponen restricciones mínimas a la búsqueda, en general son técnicas de solución de problemas de propósito general y pueden describirse independientemente de cualquiera sea el dominio del problema. Estos métodos usan solamente la información estructural y no hacen ninguna distinción cualitativa entre los nodos, respecto a su posibilidad de encontrarse sobre el camino deseado. En consecuencia, para los problemas con un extenso espacio de estados, la cantidad de alternativas que deben explorarse es tan grande que hace que su uso sea computacionalmente imposible. El número de nodos a explorar crece, en general, exponencialmente con la longitud del camino que representa la solución del problema. Esto genera una explosión combinatoria que estos métodos son incapaces de superar. No obstante, continúan formando el núcleo de la mayoría de los sistemas de I.A. [Meseguer, 2006].

Características:

• El orden en que la búsqueda se realiza no depende de la naturaleza de la solución buscada.

• Exploración del árbol de búsqueda sistemáticamente pero sin información.

• La localización de la meta(s) no altera el orden de expansión de los nodos.

• No tienen en cuenta el coste de la solución en la búsqueda.

• Su funcionamiento es sistemático, siguen un orden de visitas y generación de nodo establecido por la estructura del espacio de búsqueda.

• Los dos métodos básicos de la búsqueda a ciegas son la búsqueda primero a lo ancho (breadth-first search) y la búsqueda primero en profundidad (depth-first search).

Estudiaremos algunas de las técnicas de búsqueda a ciegas más usadas

3.3.1.2 Búsqueda primero a lo ancho (breadth-First)

Una búsqueda primero a lo ancho (breadth-first) explora primero todos los sucesores del nodo raíz. Si no se encuentra la meta, pasa a los sucesores del segundo nivel y así sucesivamente por niveles. Suponiendo que el objetivo a alcanzar es el nodo 7, el recorrido primero a lo ancho del espacio de búsqueda que se muestra en la figura III.9, es 1-2-3-4-5-6-7. Este método simboliza a un explorador bastante conservador.

Figura. III.9. Un ejemplo de espacio de búsqueda.

Este método tiene como ventaja que siempre encuentra el camino más corto a la solución, si ésta existe, aún en el caso de que el espacio de búsqueda sea infinito. Es efectivo cuando el factor de ramificación, o sea, el número promedio de hijos de un nodo, es pequeño, pues entonces la cantidad de nodos por niveles será pequeña y es mejor explorar un nivel antes de pasar al siguiente. Sin embargo, tiene las siguientes desventajas:

• Necesita mucha memoria. Como cada nivel del árbol tiene que ser almacenado completamente para poder generar el próximo nivel y la cantidad de memoria es proporcional al número de nodos almacenados, su complejidad espacial también lo es.

• Requiere mucho trabajo, especialmente si el camino más corto a la solución es muy largo, puesto que el número de nodos que necesita examinar se incrementa exponencialmente con la longitud del camino.

• Los operadores irrelevantes o redundantes incrementarán grandemente el número de nodos que deben explorarse.

• Una búsqueda primero a lo ancho comienza por generar todos los sucesores de la raíz del nodo. Luego la búsqueda continúa expandiendo todos los nodos de cada nivel. La esencia del método es examinar todas las soluciones potenciales a un nivel antes de pasar al nivel inferior.

Fig. III.10.Búsqueda Primero a lo ancho.

3.3.1.3 Búsqueda primero en profundidad. (Depth-First).

Este método siempre expande uno de los nodos del nivel más profundo del árbol. Solamente cuando la búsqueda alcanza un nodo muerto (nodo no objetivo que no se puede expandir) la búsqueda va a atrás y expande nodos de niveles inferiores [Morales, 1999].

Esta búsqueda tiene requerimientos de memoria modestos. Solamente almacena un camino de la raíz a un nodo hoja junto con los hermanos de los nodos de este camino a cada nivel. La principal ventaja de este método es que sus requerimientos de memoria son linealmente proporcionales a la profundidad del árbol. La cantidad de tiempo que consume es la misma que en primero a lo ancho.

Su principal problema es que puede tomar un camino equivocado que si es muy largo, quizás infinito, no permite encontrar una solución nunca. Muchos problemas tienen árboles de búsquedas muy profundos o incluso infinitos, en cuyo caso este método nunca se podrá recuperar de una selección equivocada en uno de los nodos cercanos a la raíz del árbol.

Otra situación en la que puede caer el método es encontrar una solución con un camino más largo que la solución óptima, es decir, el método no es ni completo, ni óptimo. Este método debe evitarse para árboles de búsquedas muy profundos. Es un método apropiado cuando los estados objetivos se encuentran a la izquierda del árbol de búsqueda o cuando los caminos son cortos.

En depth-first cada nodo que es explorado genera todos sus sucesores antes de que otro nodo sea explorado. Después de cada expansión el nuevo hijo es de nuevo seleccionado para expansión. Para problemas con muchas soluciones depth-first puede ser más rápido que breadth-first porque existe una buena posibilidad de encontrar una solución después de explorar una pequeña parte del espacio de búsqueda.

La búsqueda primero en profundidad procede generando primeramente un sucesor del nodo raíz y luego un sucesor de este, y continúa extendiendo este camino solamente hasta que termina o se realiza un corte a alguna profundidad, si no se ha alcanzado el objetivo se realiza un retroceso al nivel anterior para generar otro camino.

Figura III.11 Búsqueda Primero en Profundidad

Ventajas de la búsqueda en amplitud:

• No se "pierde" explorando caminos infructuosos que consumen mucho tiempo sin llegar a una solución o de los que no se vuelve nunca (bucles en profundidad).

• Si hay una solución la encuentra. Es más, si hay varias encuentra la óptima.

Ventajas de la búsqueda en profundidad:

• Requiere mucha menos memoria (sólo hay que guardar el camino actual).

• Puede encontrar una solución sin examinar mucho el árbol, sobre todo si hay varios caminos a la solución.

3.3.1.4. Búsqueda heurística o con Información.

La palabra heurística viene del griego heuriskein que significa descubrir. Ella es también el origen de eureka, que se deriva de la famosa exclamación de Arquímides heurika ("lo encontré"), que lanzó al descubrir un método para determinar la pureza del oro. Feigenbaum y Feldman la definen así: "Una heurística (regla heurística o método heurístico) es una regla para engañar, simplificar o para cualquier otra clase de ardid, la cual limita drásticamente la búsqueda de soluciones en grandes espacios de solución" [Meseguer, 2006].

La posibilidad de efectuar la búsqueda de una forma más eficiente se basa en el uso de alguna información específica para el problema a solucionar. Esta información, aunque imprecisa e incompleta, permite distinguir cuáles de los nodos dirigen mejor el avance hacia la meta y permite realizar este avance siempre en la dirección que momentáneamente tiene la mejor perspectiva.

Se llama búsqueda heurística a los métodos de búsqueda que usan este tipo de información. Precisamente por esto a estos métodos, generalmente, se les llaman métodos fuertes. Las técnicas heurísticas son como las guías turísticas: son buenas cuando apuntan a direcciones interesantes y son malas cuando apuntan a callejones sin salida. Usando buenas técnicas heurísticas, podemos esperar lograr buenas soluciones a problemas difíciles, como el del vendedor ambulante, en un tiempo menor que el exponencial.

Existen 3 métodos muy conocidos:

• Generación y prueba.

• Ascenso de colina (-> profundidad primero).

• Primero el mejor.

3.3.1.5 Generación y Prueba. (GENERATE-AND-TEST)

• 1. Generar una posible solución. (Estado o camino).

• 2. Comprobar para ver si es una solución, mediante comparación con los elementos del conjunto de objetivos aceptables.

• 3. Si la solución ha sido encontrada salir, de otra manera, retornar al paso.

3.3.1.6 Hill Climbing o Escalador de colinas.

Existe un conjunto de problemas para los cuales el camino que conduce a la solución es irrelevante. Usualmente esto ocurre en aquellos problemas en los que la descripción del estado contiene toda la información necesaria para una solución. La idea general es comenzar con una configuración completa y hacer modificaciones para mejorar su calidad.

El método de búsqueda conocido por ascensión de colinas (hill-climbing) toma su nombre de la semejanza que tiene con un alpinista quien desea alcanzar rápidamente el pico de una montaña, este selecciona la dirección de ascenso mayor a partir de la posición actual.

Con este método la estrategia es repetidamente expandir un nodo, inspeccionar sus sucesores recién generados, y seleccionar y expandir el mejor entre los sucesores sin mantener referencias a los padres.

Este método es una variación de la búsqueda primero en profundidad en la cual se usa la función heurística para estimular la distancia entre el nodo actual y el nodo objetivo [Peraza, 1997].

Los algoritmos de ascenso a colina son típicamente locales, ya que deciden qué hacer, mirando únicamente a las consecuencias inmediatas de sus opciones. Puede que nunca lleguen a encontrar una solución, si son atrapados en estados que no son el objetivo, desde donde no se puede hallar mejores estados, por ejemplo:

• 1. Un máximo local, que es un estado mejor que sus vecinos pero no es mejor que otros que están algo más alejados.

• 2. Una meseta, es un espacio de búsqueda en el que todo un conjunto de estados vecinos tienen igual valor.

• 3. Un risco, que es un tipo especial de máximo local, imposible de atravesar con movimientos simples.

Hay algunas formas que pueden ayudar a solventar estos problemas, aunque no existe garantía:

• 1. Para evitar máximos locales, regresar a un estado anterior y explorar en una dirección diferente.

• 2. Para casos de mesetas, dar un salto grande en alguna dirección y tratar de encontrar una nueva sección del espacio de estado.

• 3. Para los riscos, aplicar dos o más reglas, antes de realizar una prueba del nuevo estado, esto equivale a moverse en varias direcciones a la vez.

Los algoritmos de ascenso a colina, a pesar de explorar sólo un paso adelante, al examinar el nuevo estado pueden incluir una cierta cantidad de información global codificada en la función objetivo o función heurística. [Costa, 2002]

3.3.1.7 Algoritmo Best-First (Primero el mejor)

La búsqueda por el mejor nodo es una forma de combinar las ventajas de las búsquedas en profundidad y a lo ancho en un único método. En cada paso del proceso de búsqueda se selecciona el más prometedor de aquellos nodos que se han generado hasta el momento. Entonces este se expande usando los operadores para generar sus sucesores. Si uno de ellos es una solución se termina. Si no, todos esos nuevos nodos se añaden al conjunto de nodos generados hasta ese momento.

Se selecciona de nuevo el nodo más prometedor y el proceso continúa. La selección del nodo a expandir es independiente de la posición en que nos encontramos en el árbol de búsqueda y de la posición del nodo más prometedor. Lo que sucede usualmente es que se realiza un poco de búsqueda a profundidad mientras se explora una rama prometedora. En un momento dado esa rama comienza a ser menos prometedora que otras de más alto nivel que se han ignorado hasta ese momento.

El nombre de búsqueda primero el mejor (Best-First Search) es impreciso. Si realmente pudiéramos expandir el mejor nodo primero no sería una búsqueda sino un procedimiento directo al estado objetivo.

Ascenso de colina inspecciona la que parece la mejor trayectoria hasta el final; la búsqueda primero el mejor analiza varias trayectorias a la vez, siempre siguiendo la mejor trayectoria parcial conocida al momento.

Generalmente la búsqueda primero el mejor encuentra trayectorias más cortas a los estados meta.

3.3.1.8 Búsqueda con Sistemas Evolutivos.

Los Algoritmos Genéticos son métodos de búsqueda que recorren el espacio de posibilidades en forma paralela y aleatoria, obedecen a una analogía con la evolución de las especies Darwiniana. En cada etapa, se tiene una población de soluciones posibles para el problema a partir de ésta se genera una nueva población de soluciones mediante operadores que emulan la selección entre las especies del cruzamiento y la mutación. El método trabaja, generación tras generación, mejorando la calidad de la mejor solución de cada población hasta que algún criterio de detección se cumpla, por ejemplo que el esfuerzo computacional que se ha invertido en la solución del problema ha superado el límite predefinido [Tolmos, 2004].

Cuál es el mejor método:

• Primero en profundidad es bueno cuando se sabe con seguridad que el árbol no es muy profundo.

• Primero en anchura, cuando el factor de ramificación no es muy grande.

• Los métodos heurísticos son adecuados cuando existe una medida natural de la distancia entre cada estado y el estado meta.

3.4 Resumen Comparativo de las Técnicas I.A.

Algunos sistemas basados en el conocimiento, como los sistemas Fuzzy encuentran aplicación en automatizar características de percepción, conocimiento y toma de decisiones propias de los operarios humanos. Las redes neuronales artificiales (RNA) emulan ligeramente a las redes neuronales naturales (RNN). Se les ha utilizado, por ejemplo, para aprender la forma de controlar un sistema "observando" las acciones que efectúa un operario. Los algoritmos genéticos (AG) se utilizan en el diseño asistido por computadora para "evolucionar" controladores, bajo el principio de supervivencia para los que mejor se ajusten al objetivo determinado.

Conclusiones.

• En este Capítulo, aprendimos el funcionamiento de las Técnicas de Inteligencia Artificial como son: la lógica difusa la cual es ideal para resolver problemas de la vida real con alto nivel de incertidumbre, debido a sus características de ambigüedad.

• Estudiamos las principales características de las redes neuronales y algoritmos genéticos que son utilizados principalmente para el reconocimiento de voz, imágenes y son métodos de optimización de problemas basados en los mecanismos de la reproducción natural.

• También estudiamos las características básicas de los tipos de búsquedas para resolver problemas de Inteligencia Artificial como: primero el mejor, heurística, primero en amplitud, primero en profundidad.

CAPITULO 4. Implementación del Software.

4.1. Introducción.

El Capítulo muestra la Implementación del software para el Tutorial de Inteligencia Artificial, donde se plantean los requerimientos funcionales que debe asegurar el sistema para satisfacer al cliente y usuarios finales.

Se aborda lo referido al diseño de la Interfaz de Usuario, la Base de Datos, Actores, Casos de Uso, diagramas de Casos de Uso, describiendo cada Caso de Uso textualmente sobre la base de su prototipo de Interfaz-Usuario, realizado con el uso de artefactos del Lenguaje Unificado de Modelado (UML).Se refiere además a la gestión de usuarios del Sistema, definiendo los tipos de Usuario Estudiante y Profesor con sus respectivos permisos de acceder al Sistema y el diagrama de Navegación.

También para la implementación de la Base de Datos conoceremos las características de MySQL, para el diseño de la Interfaz de Usuario se aprenderá las ventajas del entorno de programación PHP, Dreamweaver como editor de páginas Web y como servidor Web el Apache.

4.2 Funcionamiento del Sistema

Este Tutorial brinda Información sobre temas de Inteligencia Artificial, un servicio de Ejercicios Evaluativos, en donde los estudiantes pueden acceder a la información y evaluarse mientras los profesores pueden consultar y eliminar evaluaciones realizadas por sus estudiantes, también se visualiza el contenido de cada Tema de Inteligencia Artificial. Todas las funcionalidades que tiene la aplicación se basa en información que no debe ser alterada y a la cual no debe tener acceso cualquier tipo de usuario para garantizar que el proceso de gestión sea confiable, por esa razón se decide asegurar la integridad de los datos en la Base de Datos iadatabase, donde se definen tipos y cuentas de usuarios con los cuales se controla el acceso tanto al diseño como modificación de los datos.

4.3 Diseño de la Interfaz-Usuario.

El diseño de la Interfaz de Usuario debe estar en correspondencia con los requerimientos funcionales que debe cumplir el sistema y satisfacer a los usuarios finales. La opción de elegir las herramientas para la implementación de un sistema es una tarea a veces compleja.

Este Sistema, es una aplicación Web, cuyo objetivo está centrado en lograr una interfaz amigable y legible para el usuario, que sea capaz de cumplir con los requerimientos y dar respuesta en el menor tiempo posible.

Los requerimientos planteados en el Sistema son:

• R1: Consultar Información sobre Inteligencia artificial

• R2: Gestionar Ejercicios Evaluativos.

• R3: Gestionar Cuenta de Usuarios.

• R4: Autentificar al usuario del Sistema.

• R5: Gestionar Documentos Adicionales.

• R6: Evaluar Estudiante.

Ver Anexo IV.1 Interfaz Usuario.

Para construir este Tutorial elegimos PHP (Personal Home Page por sus siglas en inglés) el cual, es uno de los lenguajes más populares utilizados en la creación de sitios Web dinámicos en Internet además de ser Open Source e interpretado en el lado del servidor el cual se muestra como código embebido dentro de una página HTML [García,2004].

Se realizó una caracterización más amplia y profunda de PHP por ser este el lenguaje escogido para la implantación del Tutorial de Inteligencia Artificial, resultando que:

• Es un lenguaje específicamente diseñado para realizar aplicaciones Web, mientras que otros lenguajes son adaptaciones de lenguajes preexistentes, no pensados para la Web.

• Mantiene un bajo consumo de recursos de máquina.

• Gran seguridad, muy poca probabilidad de corromper los datos.

• Soporte para una gran cantidad de bases de datos: MySQL, PostgreSQL, Oracle, MS SQL Server, Informix, entre otras.

• Rico en funciones predefinidas.

• Fácil aprendizaje.

• Es un lenguaje libre.

• Dispone de muchísimos más recursos que ASP.

• Trabaja en combinación con otras tecnologías: perl, javascript, phyton y dhmtl puedes hacerlo todo, por ejemplo: Creación de gráficos interactivos por el usuario, al estilo photoshop.

• Combina excelentemente con otras inmejorables herramientas, como son el servidor apache y la base de datos mysql (o msql, o postgres), todas ellas gratuitas.

• Buena documentación.

• PHP corre en casi cualquier plataforma utilizando el mismo código fuente, como es Unix, Windows (95,98, NT, ME, 2000, XP) y Macs. Como en todos los sistemas se utiliza el mismo código base, los scripts pueden ser ejecutados de manera independiente al SO.

• PHP actualmente se puede ejecutar bajo Apache, IIS, AOLServer, Roxen y THTTPD.

• Rapidez.PHP generalmente es usado como modulo de Apache, que lo hace extremadamente veloz. Esta completamente escrito en C.

• Miles de ejemplos y código fuente disponible.

Este Sistema Tutorial de Inteligencia Artificial se publicará en el servidor Web Apache por ser un servidor por excelencia. Apache ha sido uno de los mayores éxitos del software libre. Su continuo desarrollo y portabilidad le han llevado a múltiples plataformas como Windows y casi todos los sistemas Unix.

Principales características de Apache [Pérez, 2004]:

• Es un servidor Web flexible, rápido y eficiente, continuamente actualizado y adaptado a los nuevos protocolos HTTP.

• Implementa los últimos protocolos aunque se base en HTTP.

• Puede ser adaptado a diferentes entornos y necesidades, con los diferentes módulos de apoyo y con la API de programación de módulos.

• Incentiva la realimentación de los usuarios, obteniendo nuevas ideas, informes de fallos y parches de solución a los mismos.

Dentro de las herramientas para la implementación de la interfaz de usuario del Tutorial de Inteligencia Artificial se encuentra Dreamweaver 8.0, el cual es el más avanzado para el desarrollo de aplicaciones y sitios Web, utiliza un editor de diseño y código de primera calidad en la misma herramienta. A través de sus características y funcionalidades nos permite crear documentos Web que se adapten a nuestras necesidades. En dicho software aunque el usuario que lo maneje sea un experto programador de HTML, siempre encontrarán razones para utilizarlo.

Dreamweaver incluye soporte para la creación de páginas dinámicas de servidor en ASP, PHP, HTML con acceso a bases de datos y una mayor integración con otras herramientas de Macromedia como Fireworks. Este permite editar las páginas Web de forma visual sin tener que teclear el código HTML, además de brindar la opción de trabajar con el código, y por último la posibilidad de ver ambas ventanas de desarrollo a la vez. También posibilita crear botones flash y formularios. Además incluye nuevas herramientas de zoom y guía para revisar los diseños, y una barra de código para acceder funciones frecuentes. Destaca también que las funciones para cargar y descargar archivos ahora funcionan en el background sin interrumpir la productividad en el programa.

4.4 Lenguaje de Modelado Unificado.

Para el diseño del Sistema se emplearon algunos de los artefactos del Lenguaje de Modelado Unificado (UML) el cual según la literatura referenciada se ha convertido en el estándar internacional para definir, organizar y visualizar los elementos que configuran la arquitectura de una aplicación. Su utilización es independiente del lenguaje de programación y de las características del proyecto, pues UML ha sido diseñado para modelar cualquier tipo de proyectos, tanto informáticos o de cualquier otra rama. UML se caracteriza por [Booch, 2000]:

• Ser un lenguaje gráfico con una semántica bien definida que estandariza la modelación durante el proceso de desarrollo del software para que sea legible por todo el equipo de proyecto y usuario.

• Construye modelos precisos, no ambiguos y completos.

• No es un lenguaje de programación, pero sus modelos pueden transformarse en código fuente, tablas o almacenamiento de objetos (Generación directa del código).

• Permite describir requerimientos, la arquitectura y modelar las pruebas a través de artefactos que permiten documentar el proceso.

Es importante recalcar que sólo se trata de una notación, es decir, de una serie de reglas y recomendaciones para representar modelos. UML no es un proceso de desarrollo, no describe los pasos sistemáticos a seguir para desarrollar el software. UML sólo permite documentar y especificar los elementos creados mediante un lenguaje común describiendo modelos.

Por las ventajas antes referidas para el diseño de la Interfaz de Usuario del Tutorial de Inteligencia Artificial se emplearon algunos de los artefactos del Lenguaje de Modelado Unificado (UML),

4.5. Casos de Uso.

En el diseño del tutorial se utilizaron específicamente vistas lógicas para representar las funcionalidades a realizar por el Sistema, empleándose los conceptos de:

• Actores: elementos que interactúan con la aplicación ya sea un humano, un software o hardware.

• Casos de usos: agrupación de fragmentos de funcionalidad que el sistema ofrece para aportar un resultado de valor para los actores.

• Diagrama de Caso de Uso: modela la funcionalidad del sistema agrupándola en descripciones de acciones ejecutadas por un sistema para obtener un resultado. Se representa la relación entre los casos de uso y los actores relacionados con estos.

En el Tutorial de Inteligencia Artificial se definieron los tipos de usuario siguientes:

• ADMINISTRADOR/PROFESOR tiene el derecho de controlar toda la información brindada por el sistema incluyendo la del registro de usuarios, puede controlar la Información Adicional sobre Inteligencia Artificial y los Ejercicios Evaluativos.

• ESTUDIANTE solo tiene el derecho de poder leer la información de la aplicación y realizar los ejercicios evaluativos propuestos.

• USUARIO puede consultar información como es: Información sobre Inteligencia Artificial y todo su contenido.

Tabla IV.1. Actores del Tutorial de Inteligencia Artificial.

Los Casos de Uso definidos para el sistema se encuentran relacionados dentro del Diagrama de Caso de Uso con el objetivo de lograr una mayor y mejor comprensión del Modelo y modularización de la funcionalidad que brinda el sistema estos se muestran en la figura IV.1, cada uno de los casos de uso están relacionados entre sí representando el flujo de información o comunicación que existe entre ellos.

Figura IV.1- Diagrama de Casos de Uso del Sistema.

Se han definido siete Casos de Uso que garantizan un análisis modular del sistema. Los Casos de Uso son: Iniciar Tutorial, Gestionar Cuenta de Usuario, Consultar Información sobre Inteligencia Artificial, Gestionar Ejercicios Evaluativos, Autentificarse, Gestionar Información Adicional y Evaluarse. Tabla IV.2.

Tabla IV.2 Casos de Uso del Sistema

A continuación se describe textualmente cada uno de los Casos de Uso del Diagrama empleado su prototipo de su Interfaz-Usuario.

Tabla IV.3.Caso de Uso Iniciar Tutorial.

Figura IV.2 Figura de Iniciar Tutorial (IP).

Tabla IV.4. Caso de Uso Autentificarse

Figura IV. 3- Figura Interfaz Autentificarse.

Tabla IV.5. Caso de Uso Consultar Información sobre I.A.

Figura IV.4 – Interfaz Consultar Información sobre I.A. (CIIA).

Figura IV.5- Caso de Uso Consultar Información sobre I.A.

Tabla IV.6. Caso de Uso Gestionar Información Adicional.

Figura IV. 6. Gestión de Documentos Adicionales

La descripción del Caso de Uso Gestionar Ejercicios Evaluativos, se resume en la descripción de los casos de uso: Realizar Evaluación, Consultar Resultados de Evaluaciones, Mostrar Registro de Evaluaciones, Seleccionar Estudiante, Eliminar Evaluación, Administrar ejercicios evaluativos y Autentificarse. En la figura IV.7 se muestra el Caso Uso Gestionar Ejercicios Evaluativos.

Figura IV.7 – Caso Uso Gestionar Ejercicios Evaluativos.

Tabla IV.7. Caso de Uso Realizar Evaluación.

Figura IV.8- Interfaz Realizar Evaluación (RE)

Tabla IV.8. Caso de Uso Registro Evaluaciones Realizadas.

Figura IV.9- Interfaz Mostrar Registro de Evaluaciones Realizadas (MRER)

Tabla IV.9. Caso de Uso Administrar Ejercicios

Evaluativos.

Figura IV. 10- Interfaz Administrar Pregunta (AP).

Figura IV. 11- Interfaz Administrar Respuesta (AR).

Descripción del caso de uso Gestionar Cuenta de Usuario.