Colabora
 

Algoritmos Genéticos

Aplicaciones paralelizadas

 

Fecha: 14/Feb/2007 (08-02-07)
Autor: Luis Alberto Cuenca Macas

 



INTRODUCCIÓN

El presente trabajo ha sido posible ser desarrollado gracias a la tecnología actual, como es de nuestro conocimiento la tecnología avanza cada día a pasos agigantados, y en lo que para nosotros nos es de mayor interés, como es los ordenadores, se ve como la tecnología en cuanto a procesadores avanza inexorablemente; hoy en día la capacidad de procesamiento de un ordenador es asombrosa, sin embargo las demandas de procesamiento son cada día mayores, es decir tenemos la necesidad de procesar enormes volúmenes de datos para obtener información.

La presente aplicación tiene como finalidad realizar un procesamiento en paralelo de un gran conjunto de datos, en este caso para nuestro trabajo se va ha realizar la comparación pixel a pixel de dos imágenes en blanco y negro; para lograr este objetivo se ha utilizado MPI (Message Passing Interface). MPI no es más que una “Interface de Paso de Mensajes”, en otras palabras, es una interface estandarizada para la realización de aplicaciones paralelas basadas en paso de mensajes.
Es importante mencionar que, la primera imagen será diseñada o armada en base a las distintas partes que hemos diseñado, para lo cual, se ha construido una interfaz de usuario en la que se puede escoger las distintas partes antes mencionadas; y la segunda imagen será generada mediante un algoritmo genético.

“En este mundo cambiante muy poco puede consolidarse como una verdad”



DESARROLLO


Herramientas de desarrollo

Una implementación del estándar MPI, en este caso hemos utilizado DeinoMPI (http://mpi.deino.net/) para implementar la aplicación paralelizada.
Microsoft Visual Studio, utilizando Visual C# para construir la interface de usuario, y Visual C++ en el cual esta desarrollado la aplicación que realiza las tareas de multiprocesamiento en el tratamiento de la imagen.

Tratamiento de las imágenes
El proceso de tratamiento de la imagen comienza cuando el usuario, diseña una imagen a partir de varias partes de un rostro humano definidas, estas partes pueden ser: cabello, ojos, nariz, forma del rostro, cejas, boca luego con un rostro definido, se representa cada característica en una cadena de bits, en total 17 bits. Una vez obtenida la imagen se procede a obtener todos los pixeles, los mismos que son transformados a una matriz de ceros y unos de acuerdo al color, un “1” para el color negro y un ”0” para el color blanco, ahora bien esta matriz es guardada en un archivo de texto plano, que será el archivo principal o archivo patrón que usaremos para compararlo a otras representaciones de rostros generadas mediante una implementación del algoritmo genético.

Sección de código donde se obtienen los pixeles y son pasados a una representación de una matriz de 0 y 1 que también son almacenados en un archivo.

Código


#region "Genera CodificaficacionRGB"
        public int[,] ObtenerPixeles(Bitmap img)
        {
            img1 = img; img2 = img; img3 = img; img4 = img;
            f = img.Width;
            c = img.Height;
            string s = null;
            Codif = "";
            MapaBit = new int[f, c];
            colores = new Color[f, c];
            for (int i = 0; i < f; i++)
            {
                for (int j = 0; j < c; j++)
                {
                    colores[i, j] = img.GetPixel(i, j);
                    if (colores[i, j].R.ToString() == "255" && 
                        colores[i, j].G.ToString() == "255" && colores[i, j].B.ToString() == "255")
                        MapaBit[i, j] = 0;
                    else
                        MapaBit[i, j] = 1;
                    s += MapaBit[i, j].ToString(); 
                    Codif += MapaBit[i, j].ToString();
                }
                s += Environment.NewLine;
            }
            GrabaArchivoCodificacion(s,"Entrada");
            return MapaBit;
        }
        private void GrabaArchivoCodificacion(string codif,string nomArch)
        {
            cont1++;
            DatosCodif= asciiEncoding.GetBytes(codif);
            PathArchivoC = string.Format("{0}{1}.txt",cont1.ToString(),nomArch);
            fs = new FileStream(PathArchivoC,FileMode.Create);
            fs.Write(DatosCodif, 0, DatosCodif.Length);
            fs.Close();
        }
    #endregion

El algoritmo genético, es un algoritmo genérico, que se puede utilizar en cualquier tipo de problema, utiliza básicamente el principio de evolución natural, el cual dice que en una generación de individuos, aquel con las mejores características o aquel que se adapte mejor a un escenario pasa a la siguiente generación, así el algoritmo genético utiliza tres métodos principales: selección, cruce y mutación.
El método de selección, permite seleccionar dos individuos que originan un nuevo individuo o hipótesis, en nuestra aplicación la selección se realiza al azar.

Código de aplicación del Algoritmo Genético para la generación de la población

public class Poblacion
{
        /// <summary>
        /// Cantidad de bits que representan una imagen de la poblacion
        /// </summary>
        /// 
        #region "Declaracion de Variables"
        public const int BITS = 17;
        public const int PUNTO1 = 9;
        public const int PUNTO2 = 8;
        static ManejadorGraficos objManejadorGraf;
        public static int estado;
        static List<string> lstCodif = new List<string>();
        #endregion

        #region "Propiedades"
        public int Cont
        {
            get { return estado; }
        }
        public List<string> ListaCodificacion
        {
            get { return lstCodif; }
        }
        #endregion

        #region "Declaracion de Constructores"
        public Poblacion()
        {
            estado = 0;
        }
        public Poblacion(ManejadorGraficos manejadorGraf)
        {
            objManejadorGraf = manejadorGraf;
            GenerarPoblacion(45);
        }
        public Poblacion(ManejadorGraficos manejadorGraf,int tamano)
        {
            objManejadorGraf = manejadorGraf;
            GenerarPoblacion(tamano);
        }
        #endregion

        #region "Implementacion de los Algoritmos Geneticos"
        public static List<string> GenerarPoblacion(int tamano)
        {
            if (tamano < 0)
                throw new ArgumentException("Tamano de la poblacion no puede ser negativo",
                    "tamano"
                    );

            List<string> retval = new List<string>(tamano);
            Random rnd = new Random();            
            

            for (int i = 0; i < tamano; i++)
            {
                string repImagen = string.Empty;

                for (int j = 0; j < Poblacion.BITS; j++)
                    if (rnd.Next(10) < 5)
                        repImagen += "1";
                    else         
                        repImagen += "0";

                if (retval.Count > 2)
                {
                    string primero = retval[rnd.Next(retval.Count)];
                    string segundo = retval[rnd.Next(retval.Count)];
                    repImagen = Poblacion.Cruce(primero, segundo);
                }

                if(rnd.NextDouble() > 0.5 && retval.Count > 0)                    
                    repImagen = Poblacion.Mutar(retval[rnd.Next(retval.Count)]);
                estado++;
                retval.Add(repImagen);
                objManejadorGraf.GeneraImagen(repImagen);
                lstCodif.Add(objManejadorGraf.Codificacion);
            }
            return retval;
        }

        private static string Mutar(string repImagen)
        {
            Random r = new Random();
            string retval = string.Empty;

            int indice = r.Next(Poblacion.BITS);

            for (int i = 0; i < repImagen.Length; i++)
                if (i == indice)
                    if (repImagen[i] == '1')
                        retval += "0";
                    else
                        retval += "1";
                else
                    retval += Convert.ToString(repImagen[i]);

            return retval;
        }

        /// <summary>
        /// Metodo de cruce con Punto Simple (SinglePoint)
        /// </summary>
        /// <param name=repImagen"></param>"
        /// <returns></returns>
        private static string Cruce(string primero, string segundo)
        {
            if ((Poblacion.PUNTO1 + PUNTO2) > Poblacion.BITS)
                throw new Exception("La mascara de cruce no esta definida con la 
                      representacion del individuo");
            
            string hijo = string.Empty;

            for (int p = 0; p < PUNTO1; p++)
                hijo += Convert.ToString(primero[p]);

            for (int s = PUNTO1; s < BITS; s++)
                hijo += Convert.ToString(segundo[s]);

            return hijo;
        }
        #endregion
}


Estrategia de Multiprocesamiento


Trabajando con MPI hemos encontrado varios contratiempos, debido a nuestra falta de experiencia trabajando en una programación multiprocesamiento, así también entender el modelo que el estándar MPI implanta, ya que MPI considera la migración de procesos, hemos escogido como solución, utilizar Servicios Web para la implementación del multiprocesamiento.
Un programa típico de MPI contiene la siguiente estructura:

#include <mpi.h>

int main(int argc,char* argv)
{
    MPI_Init(&argc,&argv);

    int numProcesos;
    int idProceso;

    MPI_Comm_rank(MPI_COMM_WORLD,&idProceso);
    MPI_Comm_size(MPI_COMM_WORLD,&numProcesos);

    if(idProceso == 0)
        //Enviar datos a los demas procesos
    else
        for(int i = 0; i < numProcesos; i++)
            //Recibir datos procesados

    MPI_Finalize();
}

Programa MPI

Como un programa de MPI se carga en un proceso y luego este es migrado hacia los demás equipos en el clúster, generalmente se utiliza estructuras de control condicionales (if – else) para controlar cual es el código que deberá ejecutar el proceso que estemos utilizando como director, generalmente el proceso 0, y cual es el código para los procesos que ejecutan las tareas paralelas, estas tareas paralelas usualmente significan que implementamos un método que contiene el mismo código para todas las tareas asignadas a los procesadores, pero con diferentes datos para cada uno de los procesos.
Tomando en cuenta ese escenario creemos que es factible aplicar esta misma estructura de un programa MPI, separándolo en Servicios Web, así cada nodo de nuestro clúster contendrá, un método publico, expuesto como Método Web que recibirá los datos correspondientes desde un programa cliente que actúa como director, e invocador de los Servicios Web.

 

nodo1.Service proxy1 = new hp.nodo1.Service();

nodo2.Service proxy2 = new hp.nodo2.Service();

nodo3.Service proxy3 = new hp.nodo3.Service();

string sp1 = proxy1.HpMethod(p1);

string sp2 = proxy2.HpMethod(p2);

string sp3 = proxy3.HpMethod(p3);

Invocación a Servicios Web

Entonces cada clúster contiene el mismo servicio web, el programa cliente o invocador es el encargado de determinar los parámetros para cada invocación a las diferentes instancias (proxies) de los servicios.

Ventajas 

  • No se necesita conocer en profundidad la forma de programación en red, tales como el uso de sockets, RMI (Remote Method Invocation), etc., ya que los Servicios Web abstraen toda esa funcionalidad.
  • Debido a que un Servicio Web se “ejecuta” sobre Internet, los equipos que conforman el clúster no necesariamente deberían estar en el mismo espacio geográfico que el director o los otros clúster de la topología.
  • Los Servicios Web utilizan protocolos estándar (HTTP, XML, SOAP) lo cual permite que estén implementados en cualquier tecnología, servicios Web en Java, .NET, etc. Logrando así poder tener una topología con ambientes de ejecución heterogéneos.

 

Desventajas

  • La topología del clúster es estática, ya que la invocación al servicio web de cada nodo debe ser establecida durante el desarrollo de la aplicación.
  • No se puede añadir nodos dinámicamente a la topología.
  • Se debe controlar en la aplicación el fallo de un nodo, si un nodo falla la aplicación debe reorganizar las invocaciones.

Topología

 

Bibliografia

 

Un método web es aquella funcionalidad de un Servicio Web que esta expuesto en Internet

SOAP, siglas de Simple Object Access Protocol

 

Aplicación funcionando

 

 


Código de ejemplo (ZIP):

 

Fichero con el código de ejemplo: lafbegMSI_AlgoritmoGenetico.zip - 463.69 KB

(MD5 checksum: 21FB2E48DCB3F56B55E0493FBD9C1A08)

 


ir al índice principal del Guille