misa.c

一个用人工免疫算法实现的TSP源程序 免疫算法实现的TSP源程免疫算法实现的TSP源程

#include "variable.h"
/*Change the objective functions and constraints in the next two functions (fenotipo and restricciones) respectively*/
/*compile with: gcc misa.c -o misa -lm  */
/*run with: ./misa  */
/*File input.txt must be updated with data from the problem */

/*Put here the objetive functions*/
void fenotipo (individuo *p)
{ int i;
 double sum1=0.0, sum2=0.0;
/*Put here the objetive functions*/
  /*function 1*/
  p->fx[0] = (-p->x[0]*p->x[0]+p->x[1]); //-x1*x1+x2
  /*function 2*/
  p->fx[1] = (p->x[0]/(double)2.0 + p->x[1] + 1);

 for (i=0; i<NumFun; i++) 
   if (MINMAX[i]==0)    //minimiza
     p->fx[i]=-1*p->fx[i];
 evaluaciones++;
}


/*Put here the contraints*/
void restricciones(individuo *p)
{
 p->factible=1; 
 //first constraint
 p->g[0] = p->x[0]/(double)6.0 + p->x[1] - 13.0/(double)2.0;
 if (p->g[0] > 0)
   p->factible = 0;
  //second constraint
 p->g[1] = p->x[0]/(double)2.0 + p->x[1] - 15.0/(double)2.0;
 if (p->g[1] > 0)
   p->factible=0;

//third constraint 
 p->g[2] = 5*p->x[0] + p->x[1] - 30;
 if (p->g[2] > 0)
   p->factible=0;
}


void pobInicial()
{int j,i;
 individuo *nuevo, *p;
 for(j=0; j<POB; j++){
	nuevo = (individuo *) malloc(sizeof(individuo));
	llenaDatos(nuevo);	//llenar alos individuos
	nuevo->next = NULL;
	if(j==0)
		inicio=nuevo;
	else
		p->next=nuevo;
	p=nuevo;
 }
}


void llenaDatos(individuo *p)
{ int i,j;
  for(i=0; i< longitud; i++){
	if(flip(0.5))
		p->cromo[i]=0;
	else
		p->cromo[i]=1;
  }
}


void afinidad(individuo *p)   //q es el inicio
{ int i;
	GrayBin(p->cromo, cromoBin); //Convierte Gray a Binar cromoBin tiene el binario
	//convierte las cadenas binarias a numeros reales
	for (i=0; i<NumVar;i++)
		p->x[i] = decode(tam[i], fin[i], LimInf[i]);
	//verifica que  valores de variables est閚 en rango
	for (i=0; i<NumVar; i++)
	   p->x[i] = Limite(p->x[i],tam[i],LimSup[i],LimInf[i]);
	fenotipo(p);
	restricciones(p);
}


void ordena()
{ individuo *p,*pfea,*pinfea, *ffea, *finfea, *q;
  int menor, mayor, igual;
  factibles=0;
  infactibles=0;
  p=inicio;
  while(p!=NULL){
  	p->dominado=0;
	p = p->next;
  }
  //primero separa factibles e infatibles en dos listas
  p=inicio;
  while(p!=NULL){
	if(p->factible == 1){
		if(factibles==0){
			pfea = p; ffea=p;
			p = p->next;
			ffea->next = NULL;
		}
		else{	ffea->next = p;
			ffea = p;
			p = p->next;
			ffea->next = NULL;
		}
		factibles++;
	}
	else{
		if(infactibles==0){
			pinfea = p; finfea=p;
			p = p->next;
			finfea->next = NULL;}
		else{	finfea->next = p;
			finfea = p;
			p = p->next;
			finfea->next = NULL;
		}
		infactibles++;
	}
   }  //del while
   //ahora ordenar de acuerdo a la dominancia
   //primero los factibles
  if(factibles != 0){
    p = domina(pfea);
    q = enorden(p,factibles);   //regresa el puntero al primer factible
    inicio = q;   //y lo guardo en inicio
  }
  //ahora los infactibles
  if(infactibles!=0){
    p = domina(pinfea);
    q = enorden(p,infactibles); //puntero al primer infactible
    if(factibles==0)
	inicio = q;
    else{
	p = inicio;
	while(p->next != NULL)
		p = p->next;   //se coloca al final de los factibles
	p->next = q;
	}
  }
}


void seleccionyclona()
{ individuo *p, *q;
  int i=0, cuantos;
  double temporal;
  Tclones=0;
  p=inicio;
  estimulados=0;
  p=inicio;
  if(factibles==0){  //cuenta los no dominados infactibles
	while(p!=NULL){
		if(p->dominado==0)
			estimulados++;
		p = p->next;
	}
  }
  else{   //cuenta factibles no dominados
	p=inicio;
	while(p != NULL){
		if((p->factible == 1) && (p->dominado == 0))
			estimulados++;
		p = p->next;
	}
  }
  if(estimulados < (0.05*POB))
  	estimulados = 0.3*POB;

  if(estimulados > (0.8*POB))
  	estimulados = 0.6*POB;

  p=inicio;i=1;  //localiza el final de los estimulados
  while(i<estimulados){
	p= p->next;
	i++;
  }
  intFranjas(p,(estimulados/4));
  temporal = (POB*0.8)/(double)estimulados;
  p = inicio;
  i=0;
  while((p!=NULL) && (i<estimulados)){
	if(contFranjas[p->franja] <4)
		cuantos = temporal * 2;
	else
		cuantos = temporal * 0.5;
	if(cuantos<3)
		cuantos=3;
	if(Tclones==0)
		copias(p,cuantos,0);
	else
		copias(p,cuantos,1);
	i++;
	p = p->next;
  }
}


void duplicar(individuo *nuevo, individuo *p)
{int i;
 nuevo->next = NULL;
 for(i=0; i< longitud; i++)
	nuevo->cromo[i] = p->cromo[i];
 for(i=0; i<NumVar; i++)
	nuevo->x[i] = p->x[i];
 for(i=0; i<Qg; i++)
	nuevo->g[i] = p->g[i];
 nuevo->factible = p->factible;
 for(i=0; i<NumFun; i++)
  	nuevo->fx[i] = p->fx[i];
 nuevo->violacion = p->violacion;
 nuevo->dominado = p->dominado;
}


void copias(individuo *p, int vcopias,int primi)
{ individuo *nuevo, *q,*r;
  int i, j;
  for(j=0; j<vcopias; j++){
	nuevo = (individuo *) malloc(sizeof(individuo));
	Tclones++;
	duplicar(nuevo,p);
	if(j==0){
	  q=nuevo;
	  if(primi==0)
	  	  ClonInicio = nuevo;
	  else{
	  	r=ClonInicio;
		while(r->next != NULL)
			r = r->next;
		r->next = nuevo;
	  }
	}
	else{
		q->next = nuevo;
		q = nuevo;
	}
  }
}


void mutacion()  //es decir hypermutation
{ individuo *p;
  int i=0,cont=0,cuantos,puntos,lugar;
  
  p = ClonInicio;
  while((p != NULL) && (cont < Tclones)){
	if((p->factible==1) && (p->dominado==0))  //factible no dominado
		puntos = NumVar;
	if((p->factible==1) && (p->dominado!=0))  //factible dominado
		puntos = NumVar + p->dominado;
	if((p->factible==0) && (p->dominado==0))//infactible no dominado
		puntos = NumVar+1;
	if((p->factible==0) && (p->dominado!=0))  //infactible dominado
		puntos = NumVar+p->dominado+1;
	for(i=0; i<puntos; i++){
	       lugar=rnd(0,longitud-1);
		if (p->cromo[lugar] == 1)
		  p->cromo[lugar] = 0;
       		else
		  p->cromo[lugar] = 1;
	}
	p = p->next;  //se mueve por los clones
	cont++;
  } //del while  de cont
 p = ClonInicio;
 while(p!=NULL){
	afinidad(p);
	p = p->next;
 }
}


void sigGen()   //elimina el exceso de celulas
{ individuo *p,*q, *r, *s;
  int i=0;
  //todos factibles o todos infactibles
  if((factibles==0) ||(infactibles==0)){
	p=inicio;i=1;
	while(i < POB){
		p = p->next;
		i++;
	}
	q = p->next;
	p->next = NULL;
	p = q;
	while(q != NULL){
		q = p->next;
		free(p);
		p = q;
	}
  }//OK
  else{    //mezcla
	while((i<factibles) && (i<POB-quedan)){
		if(i==0)
			p = inicio;
		else
			p = p->next;   //la p apunta al ultimo factible deseado o encontrado
		i++;
	}   //p apunta al ultimo factible
	if(i == (POB-quedan)){   //quiere decir que solo le quedan 'quedan' lugares
		if(infactibles >= quedan){
			r = p->next;//marcar lo que se va a borrar
			//buscar el primer infactible
			q=inicio;
			while(q->factible ==1)
				q=q->next;
			s=q;
			p->next = q;
			i=1;
			while(i<quedan){
				q = q->next;
				i++;
			}
			p=q->next;
			q->next = NULL;
			//borrar de r y p en adelante
			//if(s!=r){
			while((r!=NULL)&&(r!=s)){
				q=r->next;
				free(r);
				r=q;
			}
			while(p!=NULL){
				q=p->next;
				free(p);
				p=q;
			}
		}
		else{//printf("\nen el else linea 421\n");
			p=inicio;i=1;
			while(i < POB){
				p = p->next;
				i++;
			}
			q = p->next;
			p->next = NULL;
			p = q;
			while(q != NULL){
				q = p->next;
				free(p);
				p = q;
			}
		}
	}
	else{   //termino antes porque se acabaron los factibles, sigue hasta que se llene con POB y borra el resto
		while(i<POB){
			p = p->next;
			i++;
		}
		r = p->next;
		p->next = NULL;
		while(r != NULL){
			q = r->next;
			free(r);
			r = q;
		}
	}
  }
}


void reporte(FILE *archivo)
{individuo *p;int i;
   p = pmemoria;
   while(p!=NULL){
   	for(i=0;i<NumFun;i++)
	   if(MINMAX[i]==0)
	       fprintf(archivo,"%f ",-1*p->fx[i]);
	   else
	       fprintf(archivo,"%f ",p->fx[i]);
	fprintf(archivo,"\n");
	p = p->next;
 }
}


void liberaMemoria()
{individuo *q,*r;
  r = inicio;
  while(r != NULL){
	q = r->next;
	free(r);
	r = q;
  }
}


int main (int argc, char *argv[])
{int i,teval,gen=0,estimadas;
 double delta,incremento,valor;
 FILE *graf;
 individuo *p;
 graf = fopen("output","w");  //archivo de salida como par醡etro
 input1 = fopen ("input.txt","r");
 teval = 12000;
 lee(input1);
 aleatorio();
 llena();
 pm=0.3;
 estimadas = (teval - POB) /(POB*1.5);
 delta = (pm-(1/(float)longitud))/estimadas;
 pobInicial();
 pmemoria=NULL;
 p=inicio;
 while(p!=NULL){
	afinidad(p);
	p = p->next;
 }

 /********* Ciclo principal del programa  ***********/
 while(evaluaciones < teval){
   ordena();
   memoria();
   seleccionyclona();
   mutacion();   // los clones
   renovacion();
   ordena();
   sigGen();
   gen++;
   if(pm > 1/(float)longitud)
   pm = pm-delta;
 }
 /***** fin de ciclo principal del programa  *******/
 ordena();
 memoria();
 reporte(graf);
 printf("\nFuncion Kita. Evaluaciones:%d\n",evaluaciones);
 liberaMemoria();
 i=fcloseall();
 return(0);
}