Hola, les dejo código de ejemplo para operadores de recombinación de permutaciones, que pueden utilizar para resolver el problema del práctico. Obviamente, tendrán que adaptar el código a la representación que estén utilizando. El esquema algorítmico del operador lo pueden mantener.
Los códigos completos, incluyendo las representaciones a las que hacen referencia, los pueden ver en la web de Mallba: http://www.lsi.upc.edu/~mallba/. Les adjunto el newGA.req.cc correspondiente con todo el código y varios operadores (dos PMX, OX, CX y ER).
a) Para definir nuevos operadores deben crearlos en Intra_Operator, para despues poder usar el número correlativo correspondiente en el archivo de configuración para poder usar cada operador.
Por ejemplo:
Intra_Operator *Intra_Operator::create(const unsigned int _number_op) {
switch (_number_op) {
case 0: return new Crossover_PMX1();break;
case 1: return new Mutation();break;
case 2: return new Crossover_PMX2();break;
case 3: return new Crossover_OX();break;
case 4: return new Crossover_CX();break;
case 5: return new Crossover_ER();break;
}
}
b) Luego tienen que definir el operador, por ejemplo para un problema de ruteo de vehículos (VRP)
// Crossover_PMX1:Intra_operator -------------------------------------------------------------
Crossover_PMX1::Crossover_PMX1():Intra_Operator(0) {
probability = new float[1];
}
// PMX : Partially-Mapped Crossover
void Crossover_PMX1::cross(Solution& sol1,Solution& sol2) const {
int i,j;
// Copy old solutions
Rarray<int> aux1(sol1.dimension());
aux1=sol1.routes();
Rarray<int> aux2(sol2.dimension());
aux2=sol2.routes();
int limit2=rand_int(1,sol1.dimension()-1);
int limit1=rand_int(0,limit2-1);
for (i = limit1; i < limit2; i++) {
sol2.pos(i) = aux1[i];
sol1.pos(i) = aux2[i];
}
for (i = 0; i < limit1; i++) {
sol1.pos(i) = newValue(aux1[i],limit1,limit2,aux1,aux2);
sol2.pos(i) = newValue(aux2[i],limit1,limit2,aux2,aux1);
}
for (i = limit2; i < sol1.pbm().nCustomers(); i++) {
sol1.pos(i) = newValue(aux1[i],limit1,limit2,aux1,aux2);
sol2.pos(i) = newValue(aux2[i],limit1,limit2,aux2,aux1);
}
complete(sol1);
complete(sol2);
}
// Auxiliar function for PMX
int Crossover_PMX1::newValue(const int oldValue,const int l1,const int l2, Rarray<int> & s1, Rarray<int> & s2) const {
bool fin = false;
int nv = oldValue;
int n = s1.size();
bool *examinado = new bool[n];
for(int i = 0; i < n; i++) examinado[i] = false;
while (!fin) {
fin = true;
for(int i = l1; i < l2; i++)
if(nv == s2[i]) {
if(!examinado[i]) {
nv = s1[i];
examinado[i] = true;
fin = false;
}
else nv = -1;
break;
}
}
delete [] examinado;
return nv;
}
void Crossover_PMX1::complete(Solution& s) const {
int num = 0;
int n = s.dimension();
int j,k;
bool *escogido = new bool[n];
for(int i = 0; i < n; i++) escogido[i] = false;
for(int i = 0; i < n; i++) {
if(s.pos(i) != -1) escogido[s.pos(i)-1] = true;
else num++;
}
j = k = 0;
for(int i = 0; i < num; i++) {
while((j < n) && (s.pos(j) != -1)) j++;
while((k < n) && escogido[k]) k++;
s.pos(j) = k+1;
}
delete [] escogido;
}
void Crossover_PMX1::execute(Rarray<Solution*>& sols) const {
for (int i=0;i+1<sols.size();i=i+2)
if (rand01()<=probability[0]) cross(*sols[i],*sols[i+1]);
}