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
