-
Notifications
You must be signed in to change notification settings - Fork 0
/
prueba_genetico.js
156 lines (132 loc) · 4.71 KB
/
prueba_genetico.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
// Definimos la longitud de cada rollo
const rollLength = 100;
// Definimos los pedidos
const orders = [
{ length: 5, quantity: 20 },
{ length: 10, quantity: 10 },
{ length: 15, quantity: 15 },
];
// Ordenamos los pedidos de mayor a menor longitud
orders.sort((a, b) => b.length - a.length);
// Función para inicializar la población
function initializePopulation(orders, populationSize, rollLength) {
let population = [];
for (let i = 0; i < populationSize; i++) {
let individual = [];
orders.forEach(order => {
for (let j = 0; j < order.quantity; j++) {
individual.push(order.length);
}
});
shuffleArray(individual);
population.push(individual);
}
return population;
}
// Función para evolucionar la población
function evolvePopulation(population, orders, rollLength, mutationRate) {
let newPopulation = [];
for (let i = 0; i < population.length; i++) {
let parent1 = selectIndividual(population, rollLength);
let parent2 = selectIndividual(population, rollLength);
let offspring = crossover(parent1, parent2);
if (Math.random() < mutationRate) {
mutate(offspring);
}
newPopulation.push(offspring);
}
return newPopulation;
}
// Función para seleccionar un individuo
function selectIndividual(population, rollLength) {
const tournamentSize = 5;
let tournament = [];
for (let i = 0; i < tournamentSize; i++) {
let randomIndex = Math.floor(Math.random() * population.length);
tournament.push(population[randomIndex]);
}
return tournament.reduce((best, individual) => {
return (evaluateFitness(individual, rollLength) < evaluateFitness(best, rollLength)) ? individual : best;
});
}
// Función para realizar el cruce
function crossover(parent1, parent2) {
let crossoverPoint = Math.floor(Math.random() * parent1.length);
let offspring = parent1.slice(0, crossoverPoint).concat(parent2.slice(crossoverPoint));
return offspring;
}
// Función para mutar un individuo
function mutate(individual) {
let index1 = Math.floor(Math.random() * individual.length);
let index2 = Math.floor(Math.random() * individual.length);
[individual[index1], individual[index2]] = [individual[index2], individual[index1]];
}
// Función para evaluar la aptitud de un individuo
function evaluateFitness(individual, rollLength) {
let rolls = [];
let currentRoll = [];
let currentLength = 0;
individual.forEach(piece => {
if (currentLength + piece <= rollLength) {
currentRoll.push(piece);
currentLength += piece;
} else {
rolls.push(currentRoll);
currentRoll = [piece];
currentLength = piece;
}
});
if (currentRoll.length > 0) {
rolls.push(currentRoll);
}
let waste = rolls.reduce((total, roll) => {
let usedLength = roll.reduce((sum, piece) => sum + piece, 0);
return total + (rollLength - usedLength);
}, 0);
return waste;
}
// Función para mezclar un array
function shuffleArray(array) {
for (let i = array.length - 1; i > 0; i--) {
let j = Math.floor(Math.random() * (i + 1));
[array[i], array[j]] = [array[j], array[i]];
}
}
// Función principal para ejecutar el algoritmo genético
function executeGeneticAlgorithm(orders, rollLength) {
const populationSize = 50;
const generations = 100;
const mutationRate = 0.1;
let population = initializePopulation(orders, populationSize, rollLength);
for (let generation = 0; generation < generations; generation++) {
population = evolvePopulation(population, orders, rollLength, mutationRate);
}
const bestSolution = population.reduce((best, individual) => {
return (evaluateFitness(individual, rollLength) < evaluateFitness(best, rollLength)) ? individual : best;
});
return bestSolution;
}
// Ejecutamos la función y obtenemos los resultados
let bestSolution = executeGeneticAlgorithm(orders, rollLength);
// Mostramos los resultados
console.log('Resultado de la aplicación del Algoritmo Genético:');
let currentRoll = [];
let currentLength = 0;
let rolls = [];
bestSolution.forEach(piece => {
if (currentLength + piece <= rollLength) {
currentRoll.push(piece);
currentLength += piece;
} else {
rolls.push(currentRoll);
currentRoll = [piece];
currentLength = piece;
}
});
if (currentRoll.length > 0) {
rolls.push(currentRoll);
}
rolls.forEach((roll, index) => {
let usedLength = roll.reduce((sum, piece) => sum + piece, 0);
console.log(`Rollo ${index + 1}: ${roll.join(', ')} (Sobran ${rollLength - usedLength} metros)`);
});