Algoritmos Genéticos

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

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
}

#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();
}

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 

Desventajas

Topología

Bibliografia

• http://www.w3.org/XML
  http://msdn.microsoft.com/xml
• http://msdn.microsoft.com/xml/general/wsdl.asp
• http://www.w3.org/TR/SOAP
  http://msdn.microsoft.com/soap
• http://msdn.microsoft.com/xml/general/disco.asp
• http://www.uddi.org
• http://www.microsoft.com/PressPass/features/2000/sept00/09-06uddi.asp)

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