Algoritmos genéticos: cálculo de trayectorias

Introducción

En un post anterior (Complejidad Algorítmica) he hablado sobre la problemática a la hora de ofrecer una solución computacional para determinados problemas, al necesitar un tiempo de procesamiento muy elevado debido al espacio de estados que se necesitan explorar para buscar la solución. Pues bien, una técnica muy utilizada para problemas de búsqueda de soluciones en este tipo de problemas, son los algoritmos evolutivos [1] que se apoyan en la teoría de la evolución humana, para que partiendo de un conjunto de soluciones aleatorias (primera generación) irlas mejorando generación tras generación hasta alcanzar una solución aceptable en un espacio de tiempo válido.

En este post, mostraré aplicación de los algoritmos genéticos para el cálculo de trayectorias en un plano bidimensional. La idea es que dado un escenario con diferentes obstáculos queremos calcular una trayectoria lo más optimizada posible para desplazarnos de un punto origen a un destino.

Para comenzar debemos saber que para abordar cualquier problema con algoritmos genéticos, necesitaremos tener en cuenta los siguientes puntos:

1. Representación: como codificar una posible solución (o individuo) del problema, de manera que resulta sencillo y eficiente aplicar las operaciones de evaluación, selección, cruce y mutación.
2. evaluación: valoración de la calidad de cada solución o individuo.
3. Selección: una vez generada una población y evaluado cada individuo de la misma, deberemos seleccionar aquellos que nos interesen para generar la siguiente generación.
4. Cruce: mezclar los genes de dos progenitores para generar un descendiente que pasará a formar parte de la siguiente generación.
5. Mutación: al igual que en la naturaleza, podemos implementar el concepto de mutación, que significa hacer algún cambio aleatorio en los genes de algún individuo.

Teniendo esto en cuenta, el procedimiento genérico de un algoritmo genético sería el siguiente:

1. Generar primera generación aleatoria
2. Evaluar la calidad de cada individuo de la generación
3. Seleccionar aquellos individuos que utilizaremos para generar la siguiente generación
4. Aplicar el operador de cruce para generar la siguiente generación a partir de los individuos obtenidos en el paso 3.
5. Aplicar el operador de mutación en algún individuo al azar. (Este paso tan solo se ejecutará con un porcentaje de probabilidad pequeño, no en todas las generaciones).
6. Volver al paso 2

A continuación comentaremos la implementación de los diferentes pasos del algoritmo genético para el problema propuesto.

Representación

El primer paso que tenemos que abordar a la hora de aplicar los algoritmos genéticos a cualquier problema, se trata de la codificación de una posible solución al problema en un cromosoma o individuo. En este caso, una posible solución al problema planteado, es cualquier ruta (válida o no) entre la posición origen y el destino.

	1	2	3	4	5	6	7	8	9
1	*	*	*
2			*	*
3				*	*
4					*
5					*
6					*	*	*	*
7

Tabla 1: posible solución para ir desde una posición origen (casilla verde) a otra destino (casilla roja)

En la tabla 1, se muestra gráficamente una posible trayectoria, así pues, el objetivo es codificar en un cromosoma la misma trayectoria de manera que nos facilite las operaciones, de cruce, evaluación y mutación. Una características a tener en cuenta, es el tipo de movimientos permitidos, ya que en este caso para facilitar el problema, tan solo están permitidos movimientos en ángulos rectos, es decir, que podemos movernos hacía arriba, abajo, izquierda y derecha, pero nunca en diagonal.

Según, esto, una posible codificación podría ser un vector con las coordenadas de las casillas por las que pasa dicha trayectoria, de manera que la solución de la figura 1, quedaría de la siguiente manera:

[(1,1), (1,2), (1,3)(2,3), (2,4),(3,4),(3,5),(4,5),(5,5),(6,5),(5,5),(6,7),(6,8)]

Esta podría ser una codificación válida, pero debido a que la optimización en la codificación del cromosoma es un factor crítico vamos a intentar optimizarlo un poco más. Hay que tener en cuenta que el escenario real sobre el que se aplique el algoritmo puede ser mucho más grande que el de la figura 1. Una posible optimización puede ser, codificar tan solo el número de columna para cada fila entre la posición origen y destino.

[1,3,4,5,5,5]

Como se puede ver, el tamaño del cromosoma se reduce notablemente, pero además, otro factor importante es que con esta codificación, el cromosoma tendrá una longitud fija que será igual al número de filas existentes entre la posición origen y destino, característica que nos puede simplificar las operaciones de cruce, evaluación y mutación.

También vamos añadir un dato más al cromosoma, que representará la dirección utilizada para avanzar hacía la siguiente posición (vertical u horizontal). El valor horizontal, significa que se avanzará horizontalmente hasta situarse justo encima de la columna en la que deberemos estar en la siguiente fila, y vertical lo contrario, avanzamos verticalmente hasta la siguiente fila y a continuación horizontalmente hasta situarnos en la columna indicada.

[1,H,3,H,4,H,5,H,8]

Evaluación

Para la evaluación de cada cromosoma, hemos utilizado una función de fitness que tiene en cuenta tanto el número total de movimientos necesarios para ejecutar la trayectoria, como las colisiones que dicha trayectoria puede provocar contra los obstáculos existentes en el escenario.

F = a movimientos + ß colisiones

De esta manera dispondremos de dos factores (a y ß) que podremos ajustar para establecer al peso tanto del tamaño de la trayectoria o de las colisiones en el valor del fitness. Por supuesto, lo que queremos es que una simple colisión afecte muy negativamente al valor de fitness, mucho más que una ruta más larga, ya que una ruta larga sin colisiones seguirá siendo una ruta correcta, mientras que una simple colisión no será una ruta correcta, y lo que queremos es que ese individuo tenga pocas probabilidades de reproducirse para una siguiente población.

Selección

Para este problema, hemos probado dos métodos de selección, el de la ruleta y el de selección por torneo [1] [2], obteniendo mejores resultados con el segundo.

Selección de la ruleta

La selección de la ruleta, consiste en un tipo de selección probabilístico, que a la hora de seleccionar los individuos de la población que se utilizarán para generar la siguiente generación, da mayores probabilidades de ser seleccionados a aquellos cromosomas que han tenido un mejor valor de fitness. El problema de este tipo de selección, es que como hemos dicho, asigna mayores probabilidades de selección a los mejores individuos, pero nada impide que se puedan seleccionar los peores, incluso varias veces.

Básicamente, el funcionamiento de este método, consiste en dividir un determinado intervalo (por ejemplo [0, 1]), en tantas partes como el número de individuos que tiene la población, asociando cada una de estas partes a un individuo, y estableciendo el tamaño de la parte asignada a un individuo proporcional a su valor de fitness. A continuación se comienzan a obtener números aleatorios (se gira la ruleta), y se selecciona aquel individuo perteneciente al intervalo donde ha caído el valor obtenido. Por supuesto aquellos individuos con un fitness mejor, como se le ha asignado un intervalo mayor, tienen más posibilidades de ser seleccionados.

Los pasos de implementación para dicho método serían los siguientes:

1. Normalizar el fitness de cada individuo, sumando el valor de fitness de todos los individuos y diviendo el valor del individuo actual por el sumatorio recién calculado.
2. Calcular para cada individuo el valor de fitness acumulativo, que consiste en la suma de todos los fitness de individuos situados en posiciones anteriores.
3. Seleccionar los individuos que servirán para generar la siguiente población, generando números aleatores, y seleccionando el individuo cuyo valor de fitness acumulativo sea el que más se aproxime al valor aleatorio sin sobrepasarlo.

Para entenderlo un poco mejor, en las siguientes dos tablas se muestra un ejemplo con datos reales. En la primera tabla se lista el valor de fitness para 10 individuos junto con sus valores de fitness normalizados y acumulativos, y en la segunda tabla, una serie de posibles valores obtenidos aleatoriamente, y el individuo que se seleccionaría de la tabla anterior.

Individuo	Fitness	Fitness Normalizado	Fitness Acumulativo	Tamaño intervalo
1	165.5	0.07306843267108168	0.07306843267108168	0.070
2	226.0	0.09977924944812362	0.17284768211920531	0.099
3	174.0	0.07682119205298013	0.24966887417218545	0.077
4	297.0	0.13112582781456952	0.38079470198675497	0.131
5	289.5	0.12781456953642384	0.5086092715231788	0.128
6	250.5	0.11059602649006622	0.619205298013245	0.111
7	186.5	0.08233995584988962	0.7015452538631346	0.082
8	168.0	0.07417218543046358	0.7757174392935982	0.074
9	317.0	0.13995584988962473	0.9156732891832229	0.140
10	191.0	0.08432671081677705	0.9999999999999999	0.084

Tabla 2: valores de fitness para cada individuo

Valor aleatorio	Individuo seleccionado
0.41598817048488446	4
0.5833559626242413	5
0.7970389715363804	8
0.20626833490455576	2
0.9738636658234414	9
0.809138404321271	8

Tabla 3: resultado del algoritmo de la ruleta

A continuación, se muestra una implementación de este algoritmo en java.

1. private int [] rouletteSelection(){
2. double sumFitness = 0;
3. double partialSum = 0;
4. double[] normFitness;
5. double[] cumulativeFitness;
6. int[] selectedIndividuals;
7. Random random;
8. double rValue;
9. //calculate sumFitness
10. for(int i=this.fitnessValues.length;–i>=0;){
11. sumFitness += this.fitnessValues[i];
12. }
13. //normalize all fitness
14. normFitness = new double[this.fitnessValues.length];
15. for(int i=this.fitnessValues.length;–i>=0;){
16. normFitness[i] = fitnessValues[i] / sumFitness;
17. }
18. //cumulative fitness
19. cumulativeFitness = new double[fitnessValues.length];
20. for(int i=-1;++i<normFitness.length;){
21. partialSum += normFitness[i];
22. cumulativeFitness[i]= partialSum;
23. }
24. //select individuals
25. random = new Random();
26. selectedIndividuals = new int[this.population.size()-1];
27. for(int i=this.population.size()-1;–i>=0;){
28. rValue = random.nextDouble();
29. for(int j=-1;++j<cumulativeFitness.length;){
30. if(cumulativeFitness[j] >= rValue){
31. selectedIndividuals[i] = j;
32. }
33. break;
34. }
35. }
36. }
37. return selectedIndividuals;
38. }

Selección por torneo

Otra alternativa al método de la ruleta, es la selección por torneo, obteniendo resultados mucho mejores.

Este mecanismo de selección comienza seleccionando de manera aleatorio un grupo de individuos de un tamaño determinado (tamaño de rango), que normalmente suele ser igual a 2, y seleccionar para reproducirse al mejor individuo de dicho rango. Por supuesto como se puede apreciar el coste computacional de esta técnica es muchísimo menor que el de la ruleta.

Una posible implementación sería la mostrada a continuación, donde vamos seleccionando dos individuos aleatoriamente y añadiendo al mejor de estos dos al conjunto de individuos que servirán para formar la siguiente generación.

1. private int[] tournamentSelection(){
2. int[] selectedIndividuals = new int[this.population.size()-1];
3. Random random;
4. int rValue1,rValue2;
5. //select individuals
6. random = new Random();
7. for(int i=this.population.size()-1;–i>=0;){
8. rValue1 = random.nextInt(this.population.size());
9. rValue2 = random.nextInt(this.population.size());
10. selectedIndividuals[i] =
11. (fitnessValues[rValue1] <= fitnessValues[rValue2])
12. ? rValue1:rValue2;
13. }
14. return selectedIndividuals;
15. }

Cruce

Una vez seleccionados los individuos padres para la siguiente generación, lo único que nos queda es aplicar algún operador de cruce que nos permita crear uno o dos hijos a partir de dos padres (dos individuos de la lista que hemos seleccionado en el apartado anterior). El operador de cruce más común es el que realiza una simple mezcla de los genes de ambos padres partiendo de uno o varios puntos de cruce. En la figura siguiente se muestra un ejemplo gráfico.

Progenitor 1

1

0

3

1

4

1

5

1

6

1

7

1

7

1

7

1

8

0

9

1

11

Progenitor 2

1

0

5

1

8

0

2

0

8

0

3

1

9

1

2

1

9

1

6

0

8

Descendiente 1

1

0

3

1

4

1

5

1

6

0

3

1

9

1

2

1

9

1

6

0

8

Descendiente 2

1

0

5

1

8

0

2

0

8

3

1

9

1

2

1

9

1

6

0

8

3

Mutación

Como operador de mutación podemos utilizar la mutación por desplazamiento que consiste simplemente en seleccionar dos genes al azar e intercambiarlos. Para este problema, debemos seleccionar dos pares de posiciones al azar, el primer par correspondientes a posiciones pares y el segundo correspondientes posiciones impares, ya que como hemos dicho cuando hablamos de cómo representar los individuos, en las posiciones impares del cromosoma representamos la información del número de columna y en las posiciones pares la dirección del movimiento, de manera que no podemos mezclar los contenidos de posiciones pares e impares.

Individuo original

1

0

3

1

4

1

5

1

6

1

7

1

7

1

7

1

8

0

9

1

11

Individuo mutado

1

0

7

1

4

1

5

1

6

0

3

1

7

1

7

1

8

1

9

1

11

Resultados

Aquí muestro un par de resultados, de trayectorias calculadas desde la posición superiorior a un destino determinado.

Matlab: ejemplo backpropagation

Como veo que algunos en los comentarios piden un ejemplo completo de creación, entrenamiento y simulación de una red neuronal en matlab, en este post voy a mostrar un ejemplo simple sobre la aplicación de una red neuronal backpropagation, para el típico problema de reconocimiento de dígitos manuscritos del cero al nueve. Además, este ejemplo también servirá para ver un poco como funciona el toolbox de redes neuronales en la versión 2008 de matlab, puesto que en esta versión han modificado algo el interfaz del mismo.

A la hora de aplicar redes neuronales, y en general para cualquier problema de reconocimiento de patrones, hay una seríe de pasos que serán comunes a la mayoría de los problemas.

1. Representación original de los datos
2. Preprocesamiento de los datos originales para codificarlos en un formato apropiado para la red neuronal.
3. Procesamiento de la información. (aplicación de la red neuronal)
4. Interpretación de los resultados.

1. Representación de la información original.

Lo primero que deberemos tener en cuenta, será la representación original de los datos que deberemos procesar, en este caso, el de reconocimiento de dígitos manuscritos, vamos a partir de una imagen, o conjunto de píxles en blanco y negro que contendrán el dígito a reconocer.

2. Preprocesamiento de los datos originales para codificarlos en un formato apropiado para la red neuronal.

Para aplicar la información con el dígito manuscrito a la red neuronal, deberemos realizar algún tipo de procesamiento para obtener la información apropiada que le pasaremos como entrada a dicha red.

En este caso, lo que haremos será generar un array de valores enteros 0 o 1, de manera que un 1 significa que hay algo pintado y 0 no, de manera que este array de valores discretos será la información que pasaremos a la entrada de la red neuronal.

Algo a tener en cuenta es el tamaño del vector generado a partir de la imagen, por ejemplo si la imagen original tiene un tamaño de 200×200 pixels, y creamos un array con un valor para cada píxel de dicha imagen obtendríamos un array de 40.000 elementos siendo necesario una red neuronal con el mismo número de entradas. Para optimizar mejor esto, vamos a procesar tan solo aquella zona de la imagen donde esté el dígito manuscrito y además, vamos a dividir esta zona en una cuadrícula de por ejemplo 3×5, de manera que generaremos un vector de 15 elementos, correspondiendose cada elemento con una de esas zonas en las que hemos dividido el dígito manuscrito y en caso de que algún píxel de dicha zona esté pintado pondremos un uno y en caso contrario un cero.

3. Procesamiento de la información. Creación de la Red neuronal en matlab

Una vez tenemos creado el vector representando el digito manuscrito, queremos ser capaces de procesarlo para detectar el dígito real que el usuario a escrito. En este caso sencillo, nos centraremos en predecir los dígito enteros del 0 al 9, para lo cual vamos a utilizar una red neuronal de tipo backpropagation, y como implemetnación el toolbox de redes neuronales de matlab.

Como hemos dicho, la entrada de la red neuronal, será un array de 15 elementos conteniendo la información de los píxeles pintados en la imagen, así que necesitaremos una red neuronales de 15 entradas, de manera que en cada entrada se le aplicará un uno o un cero indicando la existencia de un trazo en dicha zona de la imagen.

Como el objetivo es reconocer 10 valores numéricos (del cero al 9), o mejor dicho, el objetivo es que la red neuronales aprenda a clasificar los patrones den entrada en 10 clases diferentes, la red neuronal dispondrá de 10 salidas, una para cada dígito, de manera que tan solo se activará la salida correspondiente al dígito reconocido.

3.1  Creación de la red neuronal

Para la creación y simulación de la red neuronal, hemos generado primero una serie de patrones de muestra para cada uno de los dígitos que queremos reconocer.


1;1;1;1;0;1;1;0;1;1;0;1;1;1;1
1;1;1;1;0;1;1;0;1;1;0;1;1;1;1
1;1;1;1;0;1;1;0;1;1;0;1;1;1;1
1;1;1;1;0;1;1;0;1;1;0;1;1;1;1
…


En segundo lugar, también tenemos la información de la salida que la red neuronal deberá generar para cada uno de estos patrones.


1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0
1;0;0;0;0;0;0;0;0;0
…


Así, pues primero cargaremos dicha información en matlab.


load matlab_pattern.txt
load matlab_targets.txt


A continuación creamos la red neuronal con la función newff indicándole que queremos 20 neuronas para la capa oculta.


net = newff(matlab_pattern, matlab_targets,T,20);


Listo, ya tenemos la red neuronal creada con los parámetros por defecto. La interfaz de estas funciones del toolbox de redes neuronales, han cambiado en la versión 2008 de matlab, que es la que aquí estamos viendo, y en esta versión, además de que le estamos indicando en la propia creación un ejemplo de patrones y tarjets, matlab los utilizará para crear la red neuronal con una configuración adecuada, número de capas, tamaño de la capa de entrada, tamaño de la capa de salida, randos de entrada de la red neuronal, etc. Podemos navegar un poco por la estructura del objeto “net” para asegurarnos de que todo está correcto.


net.inputs{1}
net.numlayers
net.outputs{1}
…


3.2  Entrenamiento de la red neuronal

Una vez creada la red neuronal, y como ya tenemos los patrones de entrenamiento con sus respectivos targets cargados en matlab, tan solo nos queda invocar a la función train.


net = train(net,P,T);


Con esto matlab comenzará a entrenar la red neuronal hasta alcanzar el performance deseado, abriéndosenos una ventana con la información de dicho proceso.

3.3  Simulación de la red neuronal

Pues nada, una vez entrenada la red neuronal, ya podemos aplicar un patrón real a la entrada y ver en la salida la clase (o dígito) en la que se ha clasificado.


[Y, Pf, Af, E, perf] = sim(net, [1;1;1;0;0;1;0;1;1;1;1;0;1;1;1]);
YY =0.0000
0.0008
1.0013
0.0005
0.0003
0.0012
-0.0004
0.0004
-0.0006
0.0011

En este caso, de las diez salidas todas tienen un valor muy cercano a cero, excepto la salida correspondiente al dígito dos, que tiene un valor muy cercano a uno, siendo este el dígito reconocido.

4. Interpretación de los resultados

En este caso, los resultados son fáciles de interpretar como hemos visto en el apartado anterior, la salida de la red neuronal que tenga valor 1 (o que más se parezca al valor 1) será la que tomaremos como salida activa indicando el dígito reconocido.

Para terminar, simplemente mostraros una captura de pantalla de un pequeño prototipo que permite a un usuario dibujar caracteres a mano con el ratón y le muestra el dígito reconocido, realizado con la información aquí comentada y las interfaces externas que hemos visto en el post “Matlab: interfaz com”.

Matlab: interfaz COM

En un post anterior he hablado sobre el toolbox de redes neuronales que matlab nos ofrece como implementación alternativa de todos los algoritmos y estructuras necesarias para trabajar con este tipo de herramienta. Pues bien, puede ser muy interesante poder interactuar entre un lenguaje convencional (java, c++, c#, etc) y matlab, de manera que podamos embeber dentro de una aplicación de usuario final las funcionalidades que matlab nos puede ofrecer.

Para facilitar esto, matlab ofrece un interfaz externo que nos permite bien directamente con C++ o mediante componentes COM (también podemos hacerlo indirectamente con java, puesto que en el terminal de matlab tenemos acceso directo para ejecutar clases java, pero esto está más pensado para invocar código java desde matlab que a la inversa ) ejecutar comandos en el terminal, intercambiar datos, manipular diferentes propiedades de la sesión etc.

Como lo que yo he utilizado han sido los componentes COM, será lo que pasaré a comentar, si bien las funciones son las mismas, y por supuesto utilizando C++ será mucho más eficiente que utilizando COM.

Haciendo una simple búsqueda en la ayuda de matlab por “automation server”, nos encontramos con la documentación que matlab nos ofrece [1] sobre cómo utilizar su interfaz externa con ejemplos en Visual Basic, aquí comentaré los métodos que podemos ejecutar y mostrando ejemplos en C#.

El primer paso que debemos dar en conseguir conectar al “automation server” que nos ofrece matlab, utilizando las facilidades que nos ofrezca el lenguaje de programación seleccionado. En este caso utilizaremos las facilidades que nos ofrece el API de reflesión de .NET, que gracias a las clases Type y Activator podremos enlazar dinámicamente con el componente COM de matlab.

//Obtained COM type from a ProdId. In this

//case matlab’s prodId is matlab.application

Type matlabServerType =

Type.GetTypeFromProgID(“matlab.application”);

//Create a Object with Type information

Object matlabServerObj = Activator.CreateInstance(

matlabServerType);

La clase Type nos ofrece el método GetTypeFromProgID que a partir de un identificador de programa nos devuelve una referencia a la clase Type para después pasárselo al método CreateInstance de la clase Activator para recuperar una referencia de tipo Object que después utilizaremos para invocar todos los métodos disponibles en el componente invocando al método InvokeMember.

Podemos ver la cadena “matlab.application” que se pasa el método GetTypeFromProdID. Esta cadena es el progID (identificador de programa) que todo componente COM registrado en nuestro sistema deberá tener y deberemos conocer para poder utilizarlo con esta técnica. En el caso del servidor COM de matlab el identificador es el que acabamos de utilizar.

Bueno, pues ya está, ahora si ejecutamos el código anterior, crearemos una sesión nueva en matlab, apareciéndosenos una ventana de terminal matlab como la mostrada a continuación.

A partir de este momento podremos comenzar a interactuar con la sesión recién creada, creando matrices, invocando comandos y funciones matlab, cerrar sesión, etc, las cuales repasaremos a continuación.

Cerrar Sessión: Quit

La función “Quit” nos permite cerrar la sesión que acabamos de crear. Para invocarla no necesitamos ningún parámetro y el código C# para utilizarla sería el siguiente:

object result = matlabServerType.InvokeMember(

“Quit”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

new
Object[]{});

La variable matlabServerType y matlabServerObj corresponden a los dos objetos de tipo Type y Object que hemos creado en el código del apartado anterior cuando hemos iniciado la sesión. Como no necesitamos pasar ningún argumento a la función Quit, como cuarto parámetro al método InvokeMember, le pasamos un array vacio “new Object[]{}”.

Ejecución de comandos: Execute

Para poder ejecutar cualquier comando de matlab, disponemos de la función Execute, que recibe como parámetro la cadena que representa el comando a ejecutar.

object[] arrayInput = new
object[] {aStringCommand};

Object result

= matlabServerType.InvokeMember(

“Execute”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

arrayInput);

En este caso no le pasamos un array vacio de parámetros, puesto que el array contiene un elemento con la cadena que representa el comando a ejecutar. En este caso como resultado en la variable result, obtenemos la salida el comando, que sería lo mismo que matlab nos visualiza cuando ejecutamos el comando sin terminar con el carácter ‘;‘.

Cadenas: PutCharArray & GetCharArray

Con estas dos funciones podemos crear y recuperar variables de tipo cadena.

object[] arrayInput

= new
object[] {“aVarName”,“global”,“aString”};

Object result =

matlabServerType.InvokeMember(

“PutCharArray”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

arrayInput);

En el vector arrayInput alojamos los parámetros de la función PutCharArray: el nombre de la variable que utilizaremos para almacenar el valor de la variable, el workspace que en este caso será “global” (también pudiera ser “base“), y por último, el valor de la variable creada. Así, en este caso crearemos la variable aVarName con el valor aString.

Para realizar el caso contrario y recuperar el valor de una variable de tipo cadena.

object[] arrayInput

= new
object[] {“aVarName”,“global”};

Object result =

matlabServerType.InvokeMember(

“GetCharArray”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

arrayInput);

Para recuperar el valor de la variable, tan solo le tenemos que pasar como parámetros, el nombre de la variable y el workspace, obteniendo en la variable result el valor de la variable indicada.

Matrices: PutFullMatrix & GetFullMatrix

Nos permiten almacenar una matriz o recuperarla respectivamente en el workspace indicado.

Array aRealArray     = new
Double[3]     {2, 3, 5};

Array aImgArray     = new
Double[3]     {0, 0, 0};

object[] arrayInput = new
object[] {

“aVarName”,

“base”,

aRealArray,

aImgArray

};

object result = matlabServerType.InvokeMember(

“PutFullMatrix”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

arrayInput);

En matlab todos los arrays tiene una parte real y otra imaginaria, por este motivo, a parte del nombre de la variable y el workspace, le debemos pasar a la función PutFullMatrix dos arrays, uno con los valores para la parte real y otra para la parte imaginaria.

Para hacer la función inversa y recuperar el valor de una matriz haremos lo siguiente.

Array realArray = new
double[n];

Array imgArray = new
double[n];

object[] arrayInput = new
object[] {

“aVarName”,

“base”,

realArray,

imgArray

};

ParameterModifier p = new
ParameterModifier(4);

p[0] = false; p[1] = false;

p[2] = true; p[3] = true;

ParameterModifier[] mods = {p};

Object result = this.matlabServerType.InvokeMember(

“GetFullMatrix”,

BindingFlags.InvokeMethod,

null,

this.matlabServerObj,

arrayInput,

mods,

null, null);

Para este caso, tendremos que utilizar una forma diferente de la función InvokeMember, que recibe tres parámetros más adicionales, de los cuales los dos últimos dejaremos a null, pero el siguiente se trata de un objeto de tipo ParameterModifier, que se trata de un array de booleanos que nos sirve para indicar cuales de los parámetros que indicamos en el array arrayInput son de salida, de manera que pondremos las posiciones 2 y 3 a true para indicar que los parámetros realArray e imgArray son de salida.

Manipulación de la ventana: MaximizeCommandWindow & MinimizeCommandWindow

Como utilidades, se nos ofrecen dos funciones que nos permiten maximizar y minimizar la ventana de terminal asociada a la sesión de Matlab que hemos creado al principio.

object result = matlabServerType.InvokeMember(

“MaximizeCommandWindow”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

new
Object[]{});

object result = matlabServerType.InvokeMember(

“MinimizeCommandWindow”,

BindingFlags.InvokeMethod,

null,

matlabServerObj,

new
Object[]{});

Esto es todo, si a alguien le interesa este tema y tiene alguna duda, podéis compartirla en este blog y si coincide que le puedo ayudar lo haré. Como ejemplo de cosillas que se pueden hacer, aquí va una captura de pantalla de una aplicación que en su día hice (utilizando este api y el toolbox de redes neuronales de matlab) para manipular redes neuronales, de manera que los equipos de investigación que se dedicaran a trabajar con redes neuronales pudieran crear sus propios prototipos de redes y probar los resultados.

Referencias

[1] Página oficial de Matlab, donde podemos encontrar toda la documentación necesaria.

http://www.mathworks.com/

[2] Ayuda Msdn sobre el api de reflexión.

http://msdn.microsoft.com/en-us/library/ms173183(VS.80).aspx

[3] Ejemplo de reflexión e invocación dinámica

http://my.execpc.com/~gopalan/dotnet/reflection.html

Complejidad Algorítmica

La teoría de la complejidad algorítmica tiene como objetivo clasificar cualquier problema que se pueda computar atendiendo al esfuerzo computacional requerido para su resolución. Para medir dicha complejidad, no se tienen en cuenta destalles de bajo nivel acerca de las características hardware de la máquina, y nos centramos en los detalles del algoritmo en sí, de manera que nos fijaremos en la frecuencia de ejecución de las instrucciones del algoritmo.

(1)    a = 1;

(2)    desde i=1 hasta n hacer

a = a+i;

(3)    desde j=1 hasta n hacer

desde k=1 hasta n hacer

a = a+j+k

En este caso la complejidad para cada segmente de código es O(1) para el segmente (1), O(n) para el segmente (2) y O(n²) para el segmente (3). Así denotamos la complejidad de un algoritmo con la expresión O(g(n)).

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O (n³) < O(2ⁿ)

En estos momentos disponemos de una medida estándar que nos permitirá expresar la eficiencia computacional de un algoritmo, y comparar diferentes soluciones a un mismo problema. Por ejemplo el algoritmo de ordenación QuickSort, tiene una complejidad del orden de O(n log n) [1] siendo n el tamaño del vector a ordenar, y el algoritmo de la burbuja del orden de O(n²) [2], de manera que podemos decir que en circunstancias normales, el algoritmo quicksort es más eficiente.

Una vez disponemos de una manera de expresar la complejidad algorítmica, podemos comenzar a analizar cualquier problema computacional que se nos ocurra y obtener de la misma manera la complejidad algorítmica, pero desgraciadamente, el mundo no es perfecto, y en algún momento se nos ocurrirá algún problema para el que no exista ningún algoritmo que se pueda resolver en un tiempo polinomial expresado con la notación anterior. Aquellos problemas para los que exista un algoritmo que lo soluciones en un tiempo polinomial se dice que pertenecen a la clase P mientras que aquellos problemas para los que no se puede diseñar un algoritmo que se resuelva en un tiempo polinomial se les conoce como problemas de clase NP
[3](nodeterministic polinomial problems). Si un problema de tipo NP se pude reformular en tiempo polinomial en otro problema NP, se dice que dicho problema pertenece a la clase NP-completo [4], de manera que si en algún momento se descubre un algoritmo que solucione en un tiempo polinomial dicho problema, automáticamente se habrán resuelto todos los demás problemas NP de dicha clase, puesto que se pueden convergen hacía este.

Aquellos problemas que pertenecen a la clase NP, son problemas que aunque teóricamente se conoce el algoritmo que lo resolvería, este necesitará muchísimo tiempo (por lo menos en el peor de los casos) encontrar la solución, haciendo que no sean viables. Como ejemplo de dichos problemas:

• Problema del viajante (o entrutado) [5]: este problema consiste en que partiendo de un conjunto de ciudades C = {C₁, C₂, … C_n} deberemos encontrar una combinación que nos permita recorrerlas todas una y solo una vez minimizando la distancia totas recorrida. Como he dicho antes, el algoritmo que soluciones este problema, a priori es sencillo, simplemente deberemos comparar todas las posibles combinación de ciudades posibles y obtener aquella que minimiza la distancia. El problema radica en que a medida que aumenta el número n de ciudades la cantidad de combinaciones posibles de ciudades aumenta exponencialmente (n-1)!/2.

Para n = 10, unas 181.000 combinaciones.

Para n = 20, unas 10.000.000.000.000.000 soluciones posibles.

Para n = 50, … habrá que calcularlo, pero son muchísimas combinaciones posibles.

• Problema de la asignación [6]
• Problema de la mochila [7]
• …

Queda claro, que para abarcar la solución de este tipo de problemas, se hace necesario cambiar de táctica, al no poder utilizar las soluciones tradicionales recorriendo todo el espacio de soluciones y devolviendo la mejor de todas. Como técnicas posibles para este tipo de problemas podemos citar:

• Técnicas heurísticas: utilizan “meta-información” que ofrezca “conocimiento” al algoritmo hacer de lo buena que es una solución y así poder guiar la búsqueda en el espacio de soluciones, de manera que podamos obtener en un tiempo razonable una solución que aun no siendo la mejor, represente una solución buena.
• Algoritmos genéticos: se inspiran en los mecanismos que la propia naturaleza utiliza para hacer evolucionar las especies haciendo que generación tras generación se mejoren los resultados.
• Redes neuronales: podéis ver mi post sobre introducción a las redes neuronales.
• Búsqueda tabú [8].
• Optimización basada en colonias de hormigas [9].
• …

Referencias

[1]    http://es.wikipedia.org/wiki/Quicksort

[2]    http://es.wikipedia.org/wiki/Bubblesort

[3]    http://es.wikipedia.org/wiki/Clases_de_complejidad_P_y_NP

[4]    http://es.wikipedia.org/wiki/NP-completo

[5]    http://es.wikipedia.org/wiki/Problema_del_viajante

[6]    http://en.wikipedia.org/wiki/Assignment_problem

[7]    http://es.wikipedia.org/wiki/Problema_de_la_mochila

[8]    http://en.wikipedia.org/wiki/Tabu_search

[9]    http://en.wikipedia.org/wiki/Ant_colony_optimization

Matlab: toolbox de redes neuronales

Para trabajar con redes neuronales, seguramente podremos encontrar con una simple búsqueda en Internet un gran número de API’s y frameworks que implementen por nosotros la estructura de la mayor parte de los tipos de redes y la funciones necesarias para trabajar con ellas. Uno de estos frameworks es el Toolbox que matlab posee, que nos ofrece una implementación genérica de redes neuronales, así como implementaciones de redes neuronales concretas como las perceptrón, backpropagation, Som, etc.

Estructura

Matlab utiliza una estructura única que nos dará acceso a todas las propiedades de la red neuronal, independientemente del tipo que esta sea, de manera que utilizando esta propiedad podremos modificar las entradas, capas, conexiones, pesos, etc. De esta manera una vez configurada la red neuronal según nuestras necesidades invocaremos las funciones de manipulación de redes neuronales disponibles en matlab, (simulación, entrenamiento, inicialización, etc.), pasándole como parámetro la estructura de la red neuronal.

net = network;

Si ejecutamos el comando anterior y visualizamos el contenido de la variable myNetwork se nos vializará la estructura mencionada, la cual se puede dividir en cinco secciones:

1. Arquitectura:

   Define las características básicas de la red neuronal, número de entradas, capas, conexiones de bias, etc.

2. Subobjetos:

   Contiene referencias a las subestructuras de la red neuronal, que nos permitirán configurar las propiedades de los distintos componentes que forman la red (capas, entradas, salidas, etc.).

3. Funciones:

   Funciones principales de la red neuronal, utilizadas para ejecutar las operaciones de inicialización, entrenamiento o simulación.

4. Parámetros:

   Configuración de los parámetros asociados a las funciones seleccionadas en el bloque de funciones.

5. Valores:

   Aquí se definen las matrices con los valores de los pesos de entrada, conexiones entre capas y bías.

Funciones

Una vez creada la red neuronal, para trabajar con la misma, podremos utilizar las siguientes funciones para realizar las operaciones típicas:

1. Inicialización (net = init(net)):

   Mediante la función de inicialización, obtenemos una red neuronal con los valores de los pesos y bias actualizados según las funciones de inicialización que le hayamos asociado a la red, mediante su propiedad net.initFcn, o bien net.layers{i}.initFcn y net.biases{i}.initFcn.

2. Entrenamiento ([net, tr, Y, E, Pf, Af] = train(net, P, T, Pi, Ai, VV, TV);):

   Realiza el entrenamiento de la red neuronal, modificando los pesos asociados a las conexiones entre las diferentes capas y neuronas de la misma. Para esto, debemos indicar unos patrones de entrada a la red (P, matriz de dimenesiones MxN siendo M la suma de los tamaños de las capas de entrada de la red neuronal, y N el número de patrones que deseamos aplicar en el entrenamiento). En caso de ser un entrenamiento supervisado también indicaremos los targets (T, matriz de MxN), con estos datos la matriz de patrones se aplica a la red neuronal, y el toolbox utilizando las funciones de entrenamiento que le hemos indicado en las propiedades “trainFcn” se encargará de actualizar los pesos asociados a las conexiones de la red. Los resultados del entrenamiento los obtendremos en la variable de retorno Y y los errores para cada patrón de entrada respecto a la salida esperada en la variable de retorno E.

3. Simulación ([Y, Pf, Af, E, perf] = sim(net, P, Pi, Ai, T)):

   Función parecida a la anterior pero que no actualizará los pesos de la red neuronal. Una vez que tengamos entrenada la red neuronal y  esta ofrezca unos resultado válidos, utilizaremos esta función para analizar nuevos patrones de entrada.

Redes neuronales conocidas

Normalmente a la hora de trabajar con redes neuronales, querremos trabajar con un tipo de red neuronal concreto, el cual se ajuste mejor a nuestras necesidades. En este caso en vez de utilizar la función “network” para la creación de la estructura base, podemos utilizar funciones específicas para cada tipo de red neuronal, de manera que la estructura base que matlab nos devuelva tenga una configuración de capas de entrada, ocultas, conexiones etc apropiada para el tipo de red neuronal deseado.

1. Perceptron: newp(P,S)
2. Backpropagation: newff(P, [S1,…., Sn])
3. Radiales: newgrnm(P,T)
4. Mapas Autoorganizados: newsom(P,S)

Bibliografía

1. http://www.mathworks.com/ : página oficial de matlab.
2. http://www.mathworks.com/products/neuralnet/ : documentación oficial del toolbox de redes neuronales.

Introducción a las redes neuronales

1. Estructura

La estructura de una red neuronal se compone de neuronas agrupadas en capas, distinguiendo entre capas de entrada, capas ocultas y capas de salida. La capa de entrada es la que recibe los datos que la red deberá procesar del exterior, transmitiendo dichos datos a una o más capas ocultas de la red neuronal. Una vez que la información ha llegado a las capas ocultas de la red, esta información será procesada por cada una de las neuronas de la capa, transmitiendo la salida generada a las capas siguientes de la red neuronal. De esta manera la información se irá propagando por las capas ocultas de la red hasta llegar a la capa de salida Esta última capa tiene una función similar a la capa de entrada salvo que en vez de coger los datos del exterior y transmitirlos al interior de la red, realizará la operación contraria, recibiendo los datos de la red neuronal y transmitiéndolos al exterior, generando de esta manera los resultados de la red neuronal.

2. Neurona

La neurona, como se ha comentado en el apartado 2.1, es el elemento básico de procesamiento de la red neuronal, cuyo objetivo es procesar los datos que recibe en sus entradas y generar una salida determinada.

 Como se aprecia en la figura anterior,  la neurona dispone de una serie de valores de entrada, los cuales provienen de las neuronas de las capas anterior, además como se puede apreciar a cada una de las conexiones de entrada, se le aplica un determinado peso (W).  De esta manera la entrada de una neurona vendría determinado por dos vectores. El vector X que representa los valores de propagación de las capas anteriores y el vector W que representa los pesos asociados a cada una de las entradas.

A este conjunto de entrada (WX),  se le aplica una determinada función denominada función de red, la cual servirá para calcular el valor de entrada de la neurona, normalmente esta función es una un simple sumatorio del vector resultante de multiplicar los elementos de entrada (X) por sus correspondientes pesos (W). Una vez aplicada la función de red para obtener el valor de entrada de la neurona, es necesario calcular el valor de salida de la neurona, (función de activación), denominada así debido a la propiedad de dicha función de inhibir o desinhibir la salida de la neurona, es decir, el valor de salida de la neurona puede ser nulo en caso de que el valor de entrada no cumpla la condición de la fórmula de activación, o ser un valor dentro de un rango determinado dependiendo del tipo de función de que se trate.Pues bien, una vez calculado el resultado de la función de activación, este valor será el que se propague a las neuronas de las capas hacia las que se conecte la neurona actual.

3. Capas

Como se ha comentado anteriormente, las neuronas de la red se agrupan en capas, y dichas capas se conectan entre sí. En la figura 2, se muestra la estructura más habitual de una red neuronal.

Como se puede apreciar en la figura anterior, la red neuronal consta de una capa de entrada, una o más capas ocultas y una capa de salida. Además cada capa se conecta con su capa siguiente, situación más habitual con la que nos podemos encontrar, sin embargo esto no se tiene porque cumplir, pudiendo estar conectadas una capa hacía más capas que su siguiente o no estar conectado a la siguiente y sí hacia otras, o incluso tener conexiones hacía capas anteriores.

Como se puede imaginar el lector, los valores de entrada de la red, se aplican como entradas de las neuronas de la capa de entrada e inmediatamente se propagan a la primera capa de la red (o hacia las capas conectadas con dicha capa de entrada), una vez echo esto, las neuronas de las capas que acaban de recibir los valores de la capa de entrada, calcularán su correspondiente valor de entrada, teniendo en cuenta los valores que acaban de recibir y los pesos asociados a cada una de las conexiones, para posteriormente aplicarle a dicho valor la función de activación y calcular el valor de salida de cada neurona, valor que será a su vez enviado hacia las neuronas de las capas hacia las que se conecta la capa a la que pertenece cada neurona.

Siguiendo este proceso los valores de salida de cada neurona se van propagando por las capas de la red, hasta llegar a la capa de salida de la red. Por supuesto como se ha comentado en la sección 2.1.1 algunas neuronas pueden desinhibir el valor de entrada, no generando salida alguna.

4. Funcionamiento

En las redes neuronales, se pueden distinguir dos fases principales, la fase de aprendizaje y la fase de aplicación (opcionalmente se puede añadir una fase de Tes. entre una y otra).

La fase de aprendizaje consiste en intentar optimizar las salidas de la red neuronal para que se ajusten a las salidas esperadas dentro del ámbito de aplicación de la red neuronal. Para realizar esto la forma de operar consiste en modificar los pesos asociados a las conexiones entre las neuronas en base a la presentación de una serie de patrones de entrada.

En base a la manera en que la red detecta los errores en las salidas generadas, se distingue entre aprendizaje supervisado, no supervisado.

Entrenamiento Supervisado

En el aprendizaje supervisado se le indican a la red neuronal junto a los patrones de entrada la salida esperada que se debe generar (targets), de esta manera la red ajusta los pesos de las conexiones en base a una función de minimización del error producido. Según esto dado un patrón de entrada n, la fórmula utilizada para ajustar el peso sería de la siguiente manera:

Wij(n+1) = W(n) + Awij(n)Siendo A el valor de incremento que se asignará al nuevo peso en base al error cometido

Como se puede apreciar el Nuevo peso se calcularía en base al peso anterior incrementándole el error obtenido resultado de comparar la salida real generada por la red para el patrón y la salida deseada indicada en el target asociado a dicho patrón.

En la siguiente figura se puede apreciar una representación de este tipo de entrenamiento.

Entrenamiento No Supervisado

En el aprendizaje no supervisado a la red tan solo se le indican los patrones de entrada, dejando a la red neuronal que decida si la salida generada es correcta y como debe ajustar los pesos de las conexiones en base a la experiencia recogida de los patrones de entrenamiento que ha procesado anteriormente.Este tipo de redes se basan en el principio de reducción del rango de los vectores de entrada, de forma relativamente parecida a como actual los algoritmos numéricos usados en estadística. Como el Principal Component Analisis, K-means o multidimensional Scaling.

Presentación

Hola a todos,

Como primer post para este blog, quiero hacer una pequeña presentación de mi persona y de la temática que pretendo abordar en los sucesivos post que intentaré ir publicando.

Soy un joven licenciado en informática ejerciendo mi labor profesional en diversos campos de las tecnologías de la información y telecomunicaciones (gestión, automatización, redes móviles, etc). Como principal plataforma de desarrollo siempre me he movido en el mundo java tanto en el mundo web J2EE como en entornos cliente servidor tradicionales sobre aplicaciones de escritorio, aunque siempre he estado en contacto con otras plataformas como .NET, C++, php, etc.

Independientemente de mi trabajo, me encuentro realizando el curso de doctorado en el campo del diseño y desarrollo de software inteligente, concretamente centrándome en la línea de investigación “visión artificial”, y como es de suponer, en este campo estoy mucho más en contacto con el lenguaje C++ y tecnologías relacionadas que con el mundo Java.

Teniendo en cuenta todo esto, mi intención con este blog es centrarme principalmente en el mundo de la inteligencía artificial y procesamiento de imágenes, aunque tampoco descarto añadir algún que otro post relacionados con mi pérfil profesional.

Un saludo a todos y hasta pronto.

“Todo lo que podía ser inventado ya ha sido inventado”,  Charles Duell 1899