variable.h

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

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <malloc.h>
#include "aleatori.c"

#define tam_memoria 100
#define cadena 820
#define objetivos 5
#define POB 60
#define num_var 32
#define nsf 100

typedef struct individuo individuo;
	struct individuo {
		unsigned int cromo[cadena];
		int dominado;
		double x[num_var];
		double g[num_var];
		int factible;
		double fx[objetivos];
		double fxR[objetivos];
		double violacion;
		int franja;
		individuo *next;
	};
individuo *inicio, *primero, *ClonInicio,*pmemoria;
int Ceros, MINMAX[objetivos],longitud,factibles,infactibles,totalClones, totalMemoria=0,NumVar,NumFun,Qg;
int tam[num_var], fin[num_var],estimulados,evaluaciones=0, Tclones=0;
double LimInf[num_var], LimSup[num_var];
float pm;
FILE *input1;
unsigned int cromoBin[cadena];
int contFranjas[nsf+2];
int quedan=2, ns=50;

//funciones
individuo * buscaND(individuo *,int);
void llenaDatos(individuo *);
double Limite(double, int, double, double);
void copias(individuo *, int ,int);
void duplicar(individuo *, individuo *);
void afinidad(individuo *);
int domUno(individuo *,individuo *);
int franjas(individuo *);
//void intFranjas(void);
void intFranjas(individuo * , int);

//inician las funciones
void lee (FILE *Darchivo)
{ char c; int i;
 char optimiza[20];
 
 c=fgetc(Darchivo);
 while (c !=':') 
   c=fgetc(Darchivo);
 fscanf (Darchivo, "%d", &Ceros);
//printf("\nPrecision=%d",Ceros);
 
 c=fgetc(Darchivo);
 while (c !=':') 
   c=fgetc(Darchivo);
 fscanf (Darchivo, "%d", &NumVar);
 //printf("\nNumber of Variables=%d",NumVar);

 c=fgetc(Darchivo);
 while (c !=':') 
   c=fgetc(Darchivo);
 fscanf (Darchivo, "%d", &NumFun);
//printf("\nNumber of objective functions=%d",NumFun);
 
 c=fgetc(Darchivo);
 while (c !=':') 
   c=fgetc(Darchivo);
 fscanf (Darchivo, "%d", &Qg);
//printf("\nNumber of constraints=%d",Qg);

 for (i=0; i<NumVar; i++){
    c=fgetc(Darchivo);
    while (c !=':') 
   	 c=fgetc(Darchivo);
    fscanf (Darchivo, "%lf", &LimInf[i]); //limite inferior
  //  printf(" var=%d,LI=%.2f ",i+1,LimInf[i]);
    c=fgetc(Darchivo);
    while (c !=':') 
   	 c=fgetc(Darchivo);
    fscanf (Darchivo,"%lf", &LimSup[i]);//limite superior
  //  printf("LS=%.2f\n",LimSup[i]);
    }

  for (i=0; i<NumFun; i++){
    c=fgetc(Darchivo);
    while (c !=':') 
   	 c=fgetc(Darchivo);
    fscanf (Darchivo, "%d", &MINMAX[i]);
  /*  if(MINMAX[i]==0)
	printf(" Minimize\n");
    else 
	printf(" Maximize\n");*/
 }
 fclose(Darchivo);
}


void llena ()
{ int auxi, i;
 long precision;
 double Sup, Inf, aux;
 precision = pow(10,Ceros);
 longitud = 0;
 for (i=0; i<NumVar; i++) {
   Sup = LimSup[i] * precision;
   Inf = LimInf[i] * precision;
   aux = log(Sup - Inf) / log(2);
   auxi = ceil(aux);
   aux = auxi;
   tam[i]= aux;
   longitud = longitud + auxi;
   fin[i] = longitud;
   // printf("%d ",fin[i]);
 }
// printf ("\nLongitud de la cadena : %d\n", longitud);
}


//Transforma un binario a real
double decode (int tamano,int finx,double Inferior)
{ double xx=0.0;
  int i;
  for (i=0; i<tamano; i++)
    if (cromoBin[finx-i-1] == 1)
      xx = xx + pow ( 2,  i );
  return (xx);
}

unsigned Not(unsigned x)
{ int y;
  if(x) y = 0; else y = 1;
  return y;
}

/* Convierte una cadena de codigo de Gray a binario*/
/* regresa el resultado en el arreglo B*/
void GrayBin(unsigned int G[],unsigned int B[])
{ int k; unsigned int val, aux, aux2,i;
  aux=0;
  for(i = 0; i < NumVar; i++){
    aux2 = fin[i];
    val = G[aux];
    B[aux] = val;
    for(k = aux+1; k < aux2; k++){
      if (G[k] == 1) val = Not(val);
      B[k] = val;
    }
    aux=aux2;
  }
}


double Limite(double X, int Lon, double LimSup, double LimInf)
{
// X= (X/(double)precision)+LimInf;  //con esta OK!
 X = LimInf + ((X * (LimSup-LimInf)) /(double)(pow(2.0,Lon)-1));
  return (X);
}


//regresa el puntero al inicio de la lista donde checo dominancia
individuo * domina(individuo *punto)
{individuo *p,*q;
  int j, menor, mayor, igual;
  p=punto;
  while(p!=NULL){
	q = punto;
  	while(q!=NULL){
	       if(p!=q){
		  menor=0;mayor=0;igual=0;
		  for (j=0; j<NumFun; j++) {   //Recorre los objetivos
       			if (p->fx[j] > q->fx[j])  //soy mayor
			 mayor++;
	       		if (p->fx[j] == q->fx[j])  //soy igual
			 igual++;
			if (p->fx[j] < q->fx[j])  //soy menor
			 menor++;
		   }  //DEL FOR
		   if (((menor+igual) == NumFun) && (igual!=NumFun))//menor pero diferente, medomina
		      p->dominado++;
		}  //del if
            q = q->next;
        }  //del while de q
    p = p->next;
  }
  p=punto;
  return(p);
}


individuo * agrega(individuo *a, individuo *i,int c)
{ individuo *r,*q;
  int mover=0;
  q=i;
  if(q == a){
	q = q->next;
	mover=1;}
  else{
  	while(q->next != a)
  		q = q->next;
	q->next = a->next;
  }
  a->next = NULL;
  if (c==0) primero=a;
  else{  //agregar al final
  	r = primero;
  	while(r->next != NULL)
		r = r->next;
	r->next = a;
  }
  if(mover==1)
	i = q;
  return(i);
}

individuo * enorden(individuo *p,int total)//el nodo inicial
{ int cf=0, contador=0;
  individuo *q;
  q = p;
  while(cf < total){
	q=buscaND(p,contador);
	if(q!=NULL){
		cf++;
		p=agrega(q,p,contador);
		contador=1;
	}
  }
return(primero);
}


individuo * buscaND(individuo *pi,int contador)
{ individuo *p, *q;
  int mejor;
  q=NULL;
  for(p=pi; p!=NULL; p=p->next){
	if(q==NULL){   //es el primero que se encuentra
		 mejor = p->dominado;    //lo guarda
		 q = p;           // y lo senala
	}
	else{
		 if(p->dominado < mejor){
		 	mejor = p->dominado;
			q=p;
		}
	}
  }
 return(q);
}

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

void renovacion()  //de los anticuerpos padres
{individuo *p;
 int i;
 p = inicio;
 while(p!=NULL){
	for(i=0; i<longitud; i++){
		if(flip(pm)){
			if(p->cromo[i]==0)
			   p->cromo[i]=1;
			else
			   p->cromo[i]=0;
		}
	}
	afinidad(p);
	p = p->next;
 }
  p=inicio;     //pegar al final a los clones
  while(p->next != NULL)
  	p = p->next;    //en el ultimo de la lista
  p->next = ClonInicio;
}


int domUno(individuo *q,individuo *p)  //lista y un punto
{int j, menor, mayor, igual,regresa = 0;
  if(p!=NULL)
  	p->dominado = 0;
  while(q!=NULL){
	menor=0;mayor=0;igual=0;
	for (j=0; j<NumFun; j++) {   //Recorre los objetivos
       		if (p->fx[j] > q->fx[j])  //soy mayor
		 mayor++;
       		if (p->fx[j] == q->fx[j])  //soy igual
		 igual++;
		if (p->fx[j] < q->fx[j])  //soy menor
		 menor++;
	   }  //DEL FOR
	if(((menor+igual)==NumFun) && (igual!=NumFun)){//menor medomina
	   p->dominado++;
	   q = NULL;
	   regresa=2;
	}
	if(((mayor+igual)==NumFun) && (igual!=NumFun)){//lo domino
	    q->dominado++;
	    regresa=1;
	}
	if(igual==NumFun){//repetido
	   q = NULL;
	   regresa=2;
	}
	if(q!=NULL)
		q = q->next;
  }  //del while de q
  return(regresa);
}


void elimina()
{individuo *p, *q, *r;
 p = pmemoria;
 q = p;
 while((q!=NULL)||(p!=NULL)){
  if(q==NULL) q=p;
  r = q->next;
  if(q->dominado!=0){
	if(q==pmemoria){
		pmemoria=r;
		free(q);
		p=pmemoria;
		q=pmemoria;
	}
	else{
		p->next=r;
		free(q);
		q = r;
		if(p->next==NULL)
			p=NULL;
	}
	totalMemoria--;
  }
  else{
	if(p==q){
		q=q->next;
		if(q==NULL)
		p=NULL;
	}
	else{
	  q=q->next;
	  p=p->next;
	}
  }
 }
 if(totalMemoria<0)
	  printf("---ERROR --- en elimina!!! \n\n");
}

void ingresa(individuo *p)
{individuo *nuevo, *r;
 int sat, i;
  if(totalMemoria  < tam_memoria){   //hay espacio
 	nuevo = (individuo *) malloc(sizeof(individuo));
	duplicar(nuevo,p);
 	if(totalMemoria==0)
		pmemoria = nuevo;
 	else{
		r = pmemoria;
		while(r->next != NULL)
		  r = r->next;
		r ->next = nuevo;
	}
	totalMemoria++;
  }
  else{  //la memoria ya se saturo'
	p->franja=franjas(p);
	sat = 1;
	for(i=1; i<ns+1; i++) //calcula rejilla mas saturada
		if(contFranjas[i] > contFranjas[sat])
			sat=i;
	if(contFranjas[p->franja]<(tam_memoria/ns)){//si entra
		r = pmemoria;//busca al que va a reemplazar
		while(r->franja != sat)
		  r = r->next;  //r es un individuo de mas satu
		for(i=0; i< longitud; i++)
			r->cromo[i] = p->cromo[i];
		for(i=0; i<NumVar; i++)
			r->x[i] = p->x[i];
		for(i=0; i<Qg; i++)
			r->g[i] = p->g[i];
		r->factible = p->factible;
		for(i=0; i<NumFun; i++)
		 	r->fx[i] = p->fx[i];
		r->violacion = p->violacion;
		r->dominado = p->dominado;
		contFranjas[sat]--;
		contFranjas[p->franja]++;
	}
  }  //del else
}


int franjas(individuo *q)
{ int i,stripe;
  individuo *p,*min0,*min1;
  double h, hx,theta,m,norm[2];
  p = pmemoria;
  for(i=0; i<ns+1; i++)
	contFranjas[i]=0;
  min0 = p;   //busca el minimo de f0
  while(p!=NULL){
	if(p->fx[0] < min0->fx[0])
		min0 = p;
	p = p->next;
  }
  p = pmemoria;
  min1 = p;   //busca el minimo de f1
  while(p!=NULL){
	if(p->fx[1] < min1->fx[1])
		min1 = p;
	p = p->next;
  }
  m = (min0->fx[1] - min1->fx[1])/(min0->fx[0] - min1->fx[0]);
  theta = -atan(m);
  norm[0]=cos(theta);
  norm[1]=sin(theta);
  p = pmemoria;   //ahora calcula las rotadas
  while(p != NULL){
  	p->fxR[0] = (norm[0]*p->fx[0]) - (norm[1]*p->fx[1]);
  	p->fxR[1] = (norm[1]*p->fx[0]) + (norm[0]*p->fx[1]);
  	p = p->next;
  }
  h = fabs(min1->fxR[0] - min0->fxR[0])/(ns-1);
  p = pmemoria;
  while(p != NULL){
  	hx= (p->fxR[0]-min0->fxR[0])/h;
  	if(hx < 0.5)
		stripe = 1;
	if((hx >= 0.5) && (hx<(ns-0.5)))  //0.5
		stripe = floor(hx+1.5);
	if(hx >= ns-1.5)
		stripe = ns;
  	p->franja = stripe;
	contFranjas[stripe]++;
	p = p->next;
  }
  //calcula la franja de un unico candidato q
  q->fxR[0] = (norm[0]*q->fx[0]) - (norm[1]*q->fx[1]);
  q->fxR[1] = (norm[1]*q->fx[0]) + (norm[0]*q->fx[1]);
  hx= (q->fxR[0] - min0->fxR[0])/h;
  if(hx < 0.5)
	stripe = 1;
  if((hx >= 0.5) && (hx<(ns-0.5)))  //0.5
	stripe = floor(hx+1.5);
  if(hx >= ns-1.5)
	stripe = ns;
  q->franja = stripe;
  return(stripe);
}


void memoria()
{individuo *p;
 int x,i=0;
 p=inicio;
 while((p!=NULL) && (i<estimulados)){
	x=domUno(pmemoria,p); //checar dominancia de p con la memoria
	//0no domina ni es dominado.1domina a otros.2dominadoOrepetido
	if((x==0) || (x==1)){  //ingresa
		if(x==1)
		   elimina();
		ingresa(p);
	}
   i++;
   p = p->next;
 }  //del while
}


void intFranjas(individuo *r, int nsInt)
{ int i,stripe;
  individuo *p,*min0,*min1;
  double h, hx,theta,m,norm[2];
  r = r->next;
  for(i=0; i<nsInt+1; i++)
	contFranjas[i]=0;
	
  p = inicio;
  min0 = p;   //busca el minimo de f0
  while(p!=r){
	if(p->fx[0] < min0->fx[0])
		min0 = p;
	p = p->next;
  }
  
  p = inicio;
  min1 = p;   //busca el minimo de f1
  while(p!=r){
	if(p->fx[1] < min1->fx[1])
		min1 = p;
	p = p->next;
  }
  
  m = (min0->fx[1] - min1->fx[1])/(min0->fx[0] - min1->fx[0]);
  theta = -atan(m);
  norm[0]=cos(theta);
  norm[1]=sin(theta);
  p = inicio;   //ahora calcula las rotadas
  while(p != r){
  	p->fxR[0] = (norm[0]*p->fx[0]) - (norm[1]*p->fx[1]);
  	p->fxR[1] = (norm[1]*p->fx[0]) + (norm[0]*p->fx[1]);
  	p = p->next;
  }
  h = fabs(min1->fxR[0] - min0->fxR[0])/(nsInt-1);
  p = inicio;
  while(p != r){
  	hx = (p->fxR[0]-min0->fxR[0])/h;
  	if(hx < 0.5)
		stripe = 1;
	if((hx >= 0.5) && (hx<(nsInt-0.5)))  //0.5
		stripe = floor(hx+1.5);
	if(hx >= nsInt-1.5)
		stripe = nsInt;
  	p->franja = stripe;
	contFranjas[stripe]++;
	p = p->next;
  }
}


int franjasSG(individuo *r,int nsInt)
{ int i,stripe, saturada=0;
  individuo *p,*min0,*min1;
  double h, hx,theta,m,norm[2];
  r = r->next;
  for(i=0; i<nsInt+1; i++)
	contFranjas[i]=0;
	
  p = inicio;
  min0 = p;   //busca el minimo de f0
  while(p!=r){
	if(p->fx[0] < min0->fx[0])
		min0 = p;
	p = p->next;
  }
  
  p = inicio;
  min1 = p;   //busca el minimo de f1
  while(p!=r){
	if(p->fx[1] < min1->fx[1])
		min1 = p;
	p = p->next;
  }
  
  m = (min0->fx[1] - min1->fx[1])/(min0->fx[0] - min1->fx[0]);
  theta = -atan(m);
  norm[0]=cos(theta);
  norm[1]=sin(theta);
  p = inicio;   //ahora calcula las rotadas
  while(p != r){
  	p->fxR[0] = (norm[0]*p->fx[0]) - (norm[1]*p->fx[1]);
  	p->fxR[1] = (norm[1]*p->fx[0]) + (norm[0]*p->fx[1]);
  	p = p->next;
  }
  h = fabs(min1->fxR[0] - min0->fxR[0])/(nsInt-1);
  p = inicio;
  while(p != r){
  	hx = (p->fxR[0]-min0->fxR[0])/h;
  	if(hx < 0.5)
		stripe = 1;
	if((hx >= 0.5) && (hx<(nsInt-0.5)))  //0.5
		stripe = floor(hx+1.5);
	if(hx >= nsInt-1.5)
		stripe = nsInt;
  	p->franja = stripe;
	contFranjas[stripe]++;
	p = p->next;
  }
  for(i=0; i<nsInt+1; i++)
	if(contFranjas[i]>contFranjas[saturada])
	  saturada=i;
  return(saturada);
}

void desconecta(individuo *marca)
{individuo *q, *r, *p;
 p = inicio;
 q = p;
 while((q!=NULL)||(p!=NULL)){
  if(q==NULL) q=p;
  r = q->next;
  if(q!=marca){
	if(q==pmemoria){
		inicio=r;
		free(q);
		p=inicio;
		q=inicio;
	}
	else{
		p->next=r;
		free(q);
		q = r;
		if(p->next==NULL)
			p=NULL;
	}
  }
  else{
	if(p==q){
		q=q->next;
		if(q==NULL)
		p=NULL;
	}
	else{
	  q=q->next;
	  p=p->next;
	}
  }
 }
}