BÚSQUEDA HEURÍSTICA A*

BÚSQUEDA HEURÍSTICA A*

Prueba de escritorio

   Algoritmo:

      1. Lista abierta <-Nodo_raiz

      2. Si open vacío, fallo, Stop.

      Si no n<- extraer-mínimo-lista abierta

      3.Si n es objetivo, éxito, stop

         Si no añadir n a lista cerrada y generar sucesores de n (expansión de n)

     4.Para cada sucesor de n hacer

           4.1. Si n esta en lista cerrada, ignorar n.

           4.2. Si n esta en lista abierta, re etiquetar con el camino mas corto.

           4.3. Si n no está en lista abierta ni en lista cerrada, añadir n a lista abierta.

           4.4. Continuar en punto 2.

  Problema:

  Ir del punto inicial (OR) al punto final(DE).

                                                         0          1          2        3        4                                                         

		OR		-----
	-----
-----	-----		-----
		-----
-----	DE			-----

                                                      

                                               

OR = punto inicial

DE= punto final

----- = obstáculo

Calculo de g(n) h(n) y f(n).

G(n)=costo de un nodo a otro es de 1.

H(n)=raíz cuadrada de (X1-X2)^2+( Y1-Y2)^2

F(n)=G(n)+F(n).

Árbol Generado 

En el siguiente cuadro se muestra el paso a paso de la prueba de escritorio del algoritmo A*; la columna Open, va hacer referencia a los nodos que se encuentran en esta lista en cada iteración, Closed se encuentran los nodos añadidos a esta lista tras cada iteración, N será el nodo seleccionado en cada iteración y S son los nodos generados a partir de N.

Cada nodo esta representado por sus coordenadas.

Los nodos marcados en rojo, son los q fueron eliminados o descartados.

Open	Closed	N	S
(0,2)	(0,2)	(0,2)	(0,1), (0,3),(1,2)
(0,1),(0,3),(1,2)	(1,2)	(1,2)	(0,2),(2,2),(1,3)
(2,2),(1,3)	(2,2)	(2,2)	(1,2)
(0,0)	(0,1)	(0,1)	(0,0)
(1,4), (1,0)	(0,3)	(0,3)	(0,2), (1,3)
(2,4)	(1,3)	(1,3)	(1,4), (1,2),(0,3)
(3,4)	(0,0)	(0,0)	(1,0),(0,1)
(3,3)	(1,0)	(1,0)	(0,0)
(4,3)	(1,4)	(1,4)	(2,4), (1.3)
(4,2)	(3,4)	(2,4)	(3,4),(1,4)
(4,1)	(4,3)	(3,4)	(3,3),(3,4)
	(4,2)	(4,3)	(4,3),(3,4)
		(4,2)	(4,2),(3,3)
		(4,1)	(4,1),(4,3)

ALGORITMOS GENETICOS

ANÁLISIS ARTÍCULO DE ALGORITMOS GENETICOS

El articulo habla acerca de la posibilidad de realizar problemas genéticos y su aplicabilidad en la resolución de problemas. Para garantizar una diversidad  de soluciones la población debe ser grande y generada de forma aleatoria.

También es muy preciso al indicar los pasos para generar la diversidad de soluciones y los pasos básicos de un algoritmo genético, entre los pasos más destacables se encuentra:

-Evaluar la puntación de cada uno de los cromosomas

-Con cierta probabilidad de mutación, mutar un gen del nuevo individuo generado.

-Organizar la nueva población.

Los pasos anteriores se repetirán hasta que se dé una condición de terminación.

Parámetros Genéticos de los algoritmos  

Dentro de los parámetros genéticos de los algoritmos se encuentran:

El tamaño de la población, el cual indica el número de cromosomas para una generación determinada. No obstante si la medida es insuficiente se tendrá como resultado una búsqueda de soluciones escasa. Aunque por otro lado si la población es excesiva el resultado será contraproducente, pues dicho algoritmo será lento.

Probabilidad de Cruce, este indica la frecuencia con la que se producen cruces entre los cromosomas padre.

Probabilidad de Mutación.  Como su nombre lo indica, esta probabilidad va a dar cuenta de la frecuencia con la que los genes de un cromosoma son mutados.

Por otro lado es importante destacar que el algoritmo genético está implícito en el método para resolver el problema.

Hay que tener en cuenta que un algoritmo genético es independiente del problema, lo cual lo hace un algoritmo robusto, al resultar útil en cualquier ámbito de acción, pero a la vez débil, pues no está especializado en ninguno. 

Codificación de las Variables

Esta parte trata más sobre la forma en que se representa la información acerca de la solución que representa en los cromosomas, para ello se cuenta con varios métodos que se adaptan dependiendo el problema que se está tratando de solucionar, alguno de esos métodos son:

Codificación Binaria:

Es la codificación más  antigua y extensa que existe, dado que en los primeros algoritmos genéticos este método fue el usado. Este método realiza la representación de cada cromosoma en una cadena de bits de 0 o 1.

Codificación Numérica

En este tipo de codificación, en la representación se utiliza cadenas de números, que representan un número dentro de una secuencia.

Codificación por Valor Directo

Esta codificación es la usada en la resolución de problemas en los que se requiera el uso de valores cifrados complicado como lo podría ser en el uso de números reales.

SELECCIÓN

Esta parte del proceso se trata de escoger los individuos más capacitados para que sean los que lleven acabo la reproducción con mayores probabilidades, esto está fundamentado a partir de la teoría de Darwin. Para este fin se puede usar diferentes formas de selección, entre ellas encontramos.

Selección por Rueda de Ruleta

Para este tipo de selección se crea una ruleta, donde estarán representados cada uno de los cromosomas, en donde su probabilidad de selección será determinada por un porcentaje determinado según sus capacidades, entre mayor sea su capacidad mayor será su porcentaje y probabilidad de ser seleccionado.

Selección Elitista

En este tipo de selección, se copia el mejor cromosoma se una generación anterior en la nueva generación, evitando que estos cromosomas con mayores capacidades sean ignorados.

Reproducción o Crossover

Después de la selección se procede a realizar la reproducción entre los cromosomas seleccionados, realizando un intercambio de material genético entre ellos, con ello se busca que los descendientes mejoren las aptitudes de sus padres.

Mutación

Tras el cruce, se procede a determinar que individuos serán mutados, esto con el fin de diversificar genéticamente a la población, para evitar que la solución se vea limitada por un óptimo local.

Fuentes: 

Articulo, ALGORITMOS GENÉTICOS, Arranz de la Peña, Jorge, Parra Truyol, Antonio