Evidencia 5

1455668

1491641

1607064

1456371

Instancia 1

Objeto	o1	o2	o3	o4	o5
Ganancia	15	15	30	30	10
Peso	8	7	15	10	5

Capacidad de la mochila: 35

Generación de la población inicial:

public static void Cruza(){

             int x1=rnd.nextInt(100)+1; //Tomamos cuatro cromosomas de la ruleta

             int x2=rnd.nextInt(100)+1;

             int x3=rnd.nextInt(100)+1;

             int x4=rnd.nextInt(100)+1;

      

Evaluación:

public static void Evaluar(){

             int fact1,fact3,fact2,fact4;

              apt1=(matriz[x1][0]*ganancia[0])+(matriz[x1][1]*ganancia[1])+(matriz[x1][2]*ganancia[2])+(matriz[x1][3]*ganancia[3])+(matriz[x1][4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

             aptacum=aptacum+apt1;

              apt2=(matriz[x2][0]*ganancia[0])+(matriz[x2][1]*ganancia[1])+(matriz[x2][2]*ganancia[2])+(matriz[x2][3]*ganancia[3])+(matriz[x2][4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

             aptacum=aptacum+apt2;

              apt3=(matriz[x3][0]*ganancia[0])+(matriz[x3][1]*ganancia[1])+(matriz[x3][2]*ganancia[2])+(matriz[x3][3]*ganancia[3])+(matriz[x3][4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

             aptacum=aptacum+apt3;

              apt4=(matriz[x4][0]*ganancia[0])+(matriz[x4][1]*ganancia[1])+(matriz[x4][2]*ganancia[2])+(matriz[x4][3]*ganancia[3])+(matriz[x4][4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

             aptacum=aptacum+apt4;

      

Selección de pareja:

public static void Cruza(){

             int x1=rnd.nextInt(100)+1; //Tomamos cuatro cromosomas de la ruleta

             int x2=rnd.nextInt(100)+1;

             int x3=rnd.nextInt(100)+1;

             int x4=rnd.nextInt(100)+1;

             System.out.println("Cromosomas tomados de la ruleta: "+x1+" "+x2+" "+x3+" "+x4);

              System.out.println("Cromosoma 1: "+ruleta[x1][0]+ruleta[x1][1]+ruleta[x1][2]+ruleta[x1][3]+ruleta[x1][4]);

              System.out.println("Cromosoma 2: "+ruleta[x2][0]+ruleta[x2][1]+ruleta[x2][2]+ruleta[x2][3]+ruleta[x2][4]);

            System.out.println("Cromosoma 3: "+ruleta[x3][0]+ruleta[x3][1]+ruleta[x3][2]+ruleta[x3][3]+ruleta[x3][4]);

              System.out.println("Cromosoma 4: "+ruleta[x4][0]+ruleta[x4][1]+ruleta[x4][2]+ruleta[x4][3]+ruleta[x4][4]);

              

      

Cruza:

for(int i=0;i<5;i++){//Cruzamos

                     int apt1,apt2,apt3,apt4;

                     cromosoma1[3]=cromosoma2[3];//----->Dejamos la cabeza del cromosoma 1 y la cola del 2

                     cromosoma1[4]=cromosoma2[4];

                     cromosoma2[3]=cromo1clon[3];//----->Dejamos la cabeza del cromosoma 2 y la cola del 1

                     cromosoma2[4]=cromo1clon[4];

                     cromosoma3[3]=cromosoma4[3];//----->Dejamos la cabeza del cromosoma 3 y la cola del 4

                     cromosoma3[4]=cromosoma4[4];

                     cromosoma4[3]=cromo3clon[3];//----->Dejamos la cabeza del cromosoma 4 y la cola del 3

                     cromosoma4[4]=cromo3clon[4];

                     System.out.println("Cromosoma 1 despues de cruza: "+i+":"+cromosoma1[0]+cromosoma1[1]+cromosoma1[2]+cromosoma1[3]+cromosoma1[4]);

                     System.out.println("Cromosoma 2 despues de cruza: "+i+":"+cromosoma2[0]+cromosoma2[1]+cromosoma2[2]+cromosoma2[3]+cromosoma2[4]);

                     System.out.println("Cromosoma 3 despues de cruza: "+i+":"+cromosoma3[0]+cromosoma3[1]+cromosoma3[2]+cromosoma3[3]+cromosoma3[4]);

                     System.out.println("Cromosoma 4 despues de cruza: "+i+":"+cromosoma4[0]+cromosoma4[1]+cromosoma4[2]+cromosoma4[3]+cromosoma4[4]);

                     

                     apt1=(cromosoma1[0]*ganancia[0])+(cromosoma1[1]*ganancia[1])+(cromosoma1[2]*ganancia[2])+(cromosoma1[3]*ganancia[3])+(cromosoma1[4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

                     apt2=(cromosoma2[0]*ganancia[0])+(cromosoma2[1]*ganancia[1])+(cromosoma2[2]*ganancia[2])+(cromosoma2[3]*ganancia[3])+(cromosoma2[4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

                     apt3=(cromosoma3[0]*ganancia[0])+(cromosoma3[1]*ganancia[1])+(cromosoma3[2]*ganancia[2])+(cromosoma3[3]*ganancia[3])+(cromosoma3[4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

                     apt4=(cromosoma4[0]*ganancia[0])+(cromosoma4[1]*ganancia[1])+(cromosoma4[2]*ganancia[2])+(cromosoma4[3]*ganancia[3])+(cromosoma4[4]*ganancia[4]);//mutiplicamos los arreglos para evaluar.

                      System.out.println("\nGanancia del cromosoma 1 = "+apt1);

                      System.out.println("Ganancia del cromosoma 2 = "+apt2);  

                      System.out.println("Ganancia del cromosoma 3 = "+apt3);  

                      System.out.println("Ganancia del cromosoma 4 = "+apt4);  

Parámetro	Valor
Tamaño de las generaciones (poblaciones)	4
Método para generar la población inicial	Random
Probabilidad de cruza	45%
Probabilidad de mutación	70%
Método de cruza	Método de la ruleta
Criterio de terminación	Mayor ganancia menor peso

Instancia 2

Objeto	o1	o2	o3	o4	o5	o6	o7	o8	o9	o10
Ganancia	67	15	33	75	81	44	17	72	91	16
Peso	47	43	44	35	33	36	24	49	41	29

Capacidad de la mochila: 150

Generación de la población inicial:

System.out.println("Cromosomas a tomar: "+x1+" "+x2+" "+x3+" "+x4);//generamso los numeros de los cromosomas que tomaremos.

              System.out.println("Cromosoma 1: "+matriz[x1][0]+matriz[x1][1]+matriz[x1][2]+matriz[x1][3]+matriz[x1][4]+matriz[x1][5] +matriz[x1][6] +matriz[x1][7] +matriz[x1][8] +matriz[x1][9]);//Tomamos los cromosomas

              System.out.println("Cromosoma 2: "+matriz[x2][0]+matriz[x2][1]+matriz[x2][2]+matriz[x2][3]+matriz[x2][4]+matriz[x2][5] +matriz[x2][6] +matriz[x2][7] +matriz[x2][8] +matriz[x2][9]);

            System.out.println("Cromosoma 3: "+matriz[x3][0]+matriz[x3][1]+matriz[x3][2]+matriz[x3][3]+matriz[x3][4]+matriz[x3][5] +matriz[x3][6] +matriz[x3][7] +matriz[x3][8] +matriz[x3][9]);

              System.out.println("Cromosoma 4: "+matriz[x4][0]+matriz[x4][1]+matriz[x4][2]+matriz[x4][3]+matriz[x4][4]+matriz[x4][5] +matriz[x4][6] +matriz[x4][7] +matriz[x4][8] +matriz[x4][9]);

      

Evaluación:

if(fact1>35){//Se valida que los cromosomas sean factbibles sino se toma otro.

                          x1=rnd.nextInt(1023)+1;

                          System.out.println("modx1");     

                           }

                          if(fact2>150){

                                 x2=rnd.nextInt(1023)+1;

                                 System.out.println("modx2");

                          }

                                 if(fact3>150){

                                        x3=rnd.nextInt(1023)+1;

                                        System.out.println("modx3");

                                 }

                                        if(fact4>150){

                                               x4=rnd.nextInt(1023)+1;

                                               System.out.println("modx4");

                                        }

Selección de pareja:

public static void Cruza(){

             int x1=rnd.nextInt(100)+1; //Tomamos cuatro cromosomas de la ruleta

             int x2=rnd.nextInt(100)+1;

             int x3=rnd.nextInt(100)+1;

             int x4=rnd.nextInt(100)+1;

             System.out.println("Cromosomas tomados de la ruleta: "+x1+" "+x2+" "+x3+" "+x4);

              System.out.println("Cromosoma 1: "+ruleta[x1][0]+ruleta[x1][1]+ruleta[x1][2]+ruleta[x1][3]+ruleta[x1][4]+ruleta[x1][5]+ruleta[x1][6]+ruleta[x1][7]+ruleta[x1][8]+ruleta[x1][9]);

              System.out.println("Cromosoma 2: "+ruleta[x2][0]+ruleta[x2][1]+ruleta[x2][2]+ruleta[x2][3]+ruleta[x2][4]+ruleta[x2][5]+ruleta[x2][6]+ruleta[x2][7]+ruleta[x2][8]+ruleta[x2][9]);

            System.out.println("Cromosoma 3: "+ruleta[x3][0]+ruleta[x3][1]+ruleta[x3][2]+ruleta[x3][3]+ruleta[x3][4]+ruleta[x3][5]+ruleta[x3][6]+ruleta[x3][7]+ruleta[x3][8]+ruleta[x3][9]);

              System.out.println("Cromosoma 4: "+ruleta[x4][0]+ruleta[x4][1]+ruleta[x4][2]+ruleta[x4][3]+ruleta[x4][4]+ruleta[x4][5]+ruleta[x4][6]+ruleta[x4][7]+ruleta[x4][8]+ruleta[x4][9]);

            

Cruza:

for(int i=0;i<10;i++){//Cruzamos

                     int apt1,apt2,apt3,apt4;

                     cromosoma1[3]=cromosoma2[3];//----->Dejamos la cabeza del cromosoma 1 y la cola del 2

                     cromosoma1[4]=cromosoma2[4];

                     cromosoma2[3]=cromo1clon[3];//----->Dejamos la cabeza del cromosoma 2 y la cola del 1

                     cromosoma2[4]=cromo1clon[4];

                     cromosoma3[3]=cromosoma4[3];//----->Dejamos la cabeza del cromosoma 3 y la cola del 4

                     cromosoma3[4]=cromosoma4[4];

                     cromosoma4[3]=cromo3clon[3];//----->Dejamos la cabeza del cromosoma 4 y la cola del 3

                     cromosoma4[4]=cromo3clon[4];

            

Parámetro	Valor
Tamaño de las generaciones (poblaciones)	4
Método para generar la población inicial	Random
Probabilidad de cruza	54%
Probabilidad de mutación	78%
Método de cruza	Método de la ruleta
Criterio de terminación	Mayor ganancia menor peso

Reporte de conclusiones:

• ¿Qué tan lejos quedó tu AG del óptimo?

Instancia 1: 75

Instancia 2:134

• ¿Qué valores funcionaron mejor para la instancia?

Valores más pequeños.

• ¿Qué diferencia notaste entre resolver las instancias por fuerza bruta y resolverlas mediante un AG?

Con AG es un código más corto, mayor eficiente y rápido.

• ¿Qué tan fácil crees que sea resolver por fuerza bruta una instancia de 11 objetos? ¿De 20? ¿De 30?

Difícil, ya que sería un código aún más largo. 

• ¿Para qué sirve un AG?

Para la solución de problemas de optimización.

• Qué ventajas tiene un AG?

Estos operan de forma simultánea con varias soluciones, en vez de la manera secuencial. Para los problemas de optimización son menos afectados por los máximos locales. La habilidad de manipular muchos parámetros simultáneamente.

• ¿Qué desventajas tiene un AG?

Definir una representación del problema, pueden tardar en converger dependiendo del tamaño de los parámetros, pueden converger prematuramente debido a una serie de problemas.

Instancia 1

Instancia 2