Practica 2 Algoritmo Genético Cobertura de Vertices Java

Introducción.

*En esta practica realizamos dos codificaciones en diferentes lenguajes, para comprender mejor y también para abarcar el lenguaje Python al igual que Java. Ambas codificaciones contienen sus respectivos puntos a tratar, introducción, código, vídeo etc.

El problema a analizar será vertex cover (cobertura de vértices) que es un problema NP-completo.

Este problema es muy utilizado en teoría de complejidad computacional para probar la pertenencia a la clase NP-Hard de otros problemas computacionales difíciles.

Por ejemplo:

• Clique
• Set covering
• Circuitos Hamiltonianos

El problema de la cobertura de vértices consiste en determinar una cobertura con el mínimo número de vértices.

El problema de poner guardias en los extremos (vértices) de los pasillos (lados) para cubrirlos todos por ejemplo es un problema de cubierta de vértices; el problema abastecer una colonia con el menor número de luminarias también lo es.

Cada vértice cubre su arco incidente y se trata de buscar el conjunto de vértices que cubra todos los arcos. La idea es encontrar la cobertura de vértices de tamaño mínimo.

En el siguiente grafo, {1,3,5,6} es una cobertura de vértices de tamaño 4. Sin embargo, esta no es la cobertura mínima, porque existen las coberturas de vértices {245} {124} y,ambas de tamaño 3 que satisfacen la cobertura.

 Objetivo.-  Minimizar la cantidad de nodos necesarios para la cubierta de un grafo dado, mediante un algoritmo genético.


 Justificación.- Por que es un problema de la vida cotidiana que no se puede esperar a tener una respuesta exacta del  problema supongamos que tienen que poner luminarias ahorrando la cantidad de estas en una colonia donde las calles son irregulares y el suministro de luz de las luminarias tiene que llegar a cada calle(aristas) y estas luminarias se tienen que poner en intersecciones con diferentes calles (nodos) así se tiene un ejemplo de como utilizar el algoritmo.

 Desarrollo.- Se necesitaran los siguientes datos recibidos como parametros para poder correr el programa: numero de nodos/vértices  y densidad del grafo (cantidad de enlaces entre nodos) y poblacion probabilidad de cruzamiento/mutación

ejemplo : karenalduncin@lilalduncin:~/Dropbox/LAB Adaptativos$ java Arista.java 12 .5 10 .4

Código.- Aqui se muestran las partes mas importantes del código:

/**Metaheurísticade genetica Basica 
       Incluye metodos 
       -poblacion
       -cromosoma
       -cubierta
       -mutacion 
       -nacimiento 
       -ruleta para la seleccion aleatoria :| <- :P
     */
    //genetica <3

    /**
       Metodo Poblacion
       recibe el grafo y el tamaño de la pobacion
       genera una poblacion a partir de soluciones iniciales 
     */
    // genera una poblacion inicial
    public static ArrayList<ArrayList<Integer>> poblacion(ArrayList <Arista> grafo,int tam)//verif
    {
 ArrayList<ArrayList<Integer>> lista= new ArrayList<ArrayList<Integer>>();//lista de listas de enteros
 while(lista.size()<=tam)//mientras que la lista aun sea menor al tamaño
     {
  lista.add(Arista.inicial(grafo));//agrega una solucion inicial a la lista de poblacion
     }
 System.out.println("Poblacion @_@");//flag
 Arista.imprime(lista);//imprime dicha lista //flag
 return lista;//regresa la lista para utilizarla 
    }
    //cromosoma
    /**
       metodo cromosoma transforma la solucion inicial en binario 
       recibe una solucion inicial (conjunto de vertices que forman la cubierta)
       y la cantidad total de vertices 
       
     */
    public static ArrayList<String> cromosoma(ArrayList<Integer> seleccion, int cantidad) //cantidad total de vertices 
    {
 ArrayList<String> ref = new ArrayList<String>();//cadena de caracteres 0 y 1 para representarlo
 for(int i=0;i<cantidad;i++)//recorre el arreglo
     {
  if(seleccion.contains(i))//si contiene el numero referenciado al indice
     {
         ref.add("1");//agrega un uno
     }
     else
         ref.add("0");//si no ... un cero 
     }
 //Arista.imprime(ref);
        return ref;//regresa el patron de referencia en binario
    }

    /**metodo cubierta 
       recibe la referencia en binario de la solucion (conjunto de vertices que forman la cubierta)
       
     */
    public static ArrayList<Integer> cubierta (ArrayList<String> cromosoma)
    {
 ArrayList<Integer> selection= new ArrayList<Integer>(); 
 int pos =0;
  for (int i=0;i<cromosoma.size();i++)
     {
  if((cromosoma.get(i)).equals("1"))//si es igual a 1 
      selection.add(pos);//agrega la "iteracion" actual a el conjunto cubierta
  pos+=1;
     }
 //System.out.println("cubierta");//flag
 //Arista.imprime(selection);//flag
 return selection;//regresa el conjunto 
    }
 /**
       metodo mutacion
       recibe una poblacion de soluciones iniciales 
       el total de vertices y el grafo 
       elije un individuo a cambiar atravez del metodo ruleta que selecciona
    */
public static void mutacion(ArrayList<ArrayList<Integer>>poblacion,int verticestotales,ArrayList<Arista> g)
    {
 int individuo = ruleta(poblacion);
 ArrayList<Integer> id = poblacion.get(individuo);//selecciono el individuo que voy a mutar  
 ArrayList<String> cr =cromosoma(id,verticestotales);
 int ubic= Arista.r.nextInt(verticestotales);
 if (cr.get(ubic)== "0")//si el individuo seleccionado es igual a 0
     {
  cr.set(ubic,"1"); 
     }
 else
     {
  cr.set(ubic,"0");
     }
 ArrayList <Integer> mutante = Arista.cubierta(cr);
 //int objetivo = Arista.objetivo(mutante);
 boolean fact = Arista.factible(mutante,g);
 if(fact==true )
     poblacion.add(mutante);
 return;
    }
/**
       metodo generacion manda llamar a todos los metodos del algoritmo heuristico de genetica basica recibe la lista de aristas de coneccion (grafo)y el tamaño de la poblacion de las generaciones
     */
public static void generacion(ArrayList<Arista> grafo,int tam,double cruz,double mut)
    {
 ArrayList<ArrayList<Integer>> pob = poblacion(grafo,tam);
 int n=pob.size();
 for(int i=0;i<(int)Math.floor(tam * cruz);i++)
     {
  Arista.nacimiento(pob,n,grafo);
  for (int m=0;m<(int)Math.floor(tam * mut);m++)
      {
   Arista.mutacion(pob,n,grafo);
      }
     }
 Arista.matanza(pob);
 System.out.println("Despues de la  Matanza:");//futura mejora por que se repiten :/
 Arista.imprime(pob);
 return;
    }

Resultados.-

 Video en youtube.-


 Conclusiones.- Esta entrada es complemento de la entrada anterior donde se muestra también un algoritmo genético programado en python con gráficas y su explicación, también es una recopilación del trabajo anterior en la clase de Temas Selectos de Optimización donde se muestran mas algoritmos de programación heúristica de este problema y donde se muestra en el siguiente enlace la primera versión del AG de VC el cual se modifico para poder tener los resultados esperados.
Link de Referencia:  http://ts-optimizacion.blogspot.mx
Autor: Karen Alduncin et Al.
y añadimos un video para que se pueda entender mejor el problema de la cobertura de vértices.