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.