cultural.c

经典的文化算法的程序,希望会对需要这方面程序的朋友有所帮助!

/* Cultural algorithm for constrained optimization */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <values.h>
#include <time.h>
#include <sys/timeb.h>
#include "randfunc.h"
/* Give the file name with the problem */
#include "probl01.h"

#define TRUSSPROBL 1

/* Give the following 2 parameters. Do not modify anything else in this file */
/* Population size */
#define TAMPOBL 20
/* How many individuals will take the acceptance function at each generation */
#define TOP 2

/* Clases de celdas de creencias */
#define SEMIFACTIBLE 1
#define FACTIBLE 2
#define DESCONOCIDA 3
#define NO_FACTIBLE 4

void violacionInic(float *);
void violacion(struct individuo *, float *);
void creenciasInic(struct creencias *);
void poblacionInic(struct individuo *, struct creencias *);
void actualizaCreencias(struct individuo *, struct creencias *, int);
void expande(struct celda *, struct individuo *, struct creencias *);
void aceptar(struct individuo *);
int compAptitud(const void *, const void *);
void generarHijos(struct individuo *, struct creencias *);
void mueve(int, int, float, struct individuo *, struct creencias *);
struct celda *cercana(int, struct celda *);
struct celda *busca(int, struct celda *);
void selecciona(struct individuo *);
int compVictorias(const void *, const void *);
void nuevoInd(struct individuo *);
void extremos(int *, int *, struct individuo *);

float media;
/* pacific standard & daylight savings */
char *tzstr = "TZ=PST8PDT";
struct timeb tiempo1, tiempo2;
int diferencia;

main(int argc, char **argv) {
	int i, j, indmin, indmax, Gmax;
	float semilla;
	float gmax[NUMCONSTR];
	char cadena[25];
	long evs = 0;
	FILE *a;
	struct creencias espcreencias;
	struct individuo pobl[2*TAMPOBL + 3];

	if (argc == 4) {
		Gmax = atoi(argv[1]);
		semilla = atof(argv[2]);
		strcpy(cadena, argv[3]);
	}
	else {
		printf("Teclee el n鷐ero m醲imo de generaciones: ");
		scanf("%d", &Gmax);
		printf("Teclee la semilla de aleatorios (0..1): ");
		scanf("%f", &semilla);
		printf("Teclee el nombre del archivo de salida: ");
		scanf("%s", cadena);
	}


	if ( (a = fopen(cadena, "w")) == NULL ) {
		printf("Error al abrir el archivo de salida.\n");
		return (1);
	}
	fprintf(a, "N鷐ero m醲imo de generaciones: %d\n", Gmax);
	fprintf(a, "Semilla de aleatorios %f\n\n", semilla);

	putenv(tzstr);
	tzset();
	diferencia = 0;

	/* Inicializa aleatorios */
	randomizef(semilla);
	initrandomnormaldeviate();

	/* Inicia los valores gmax */
	violacionInic(gmax);

	/* Inicia el espacio de creencias */
	creenciasInic(&espcreencias);

	/* Crea una poblaci髇 inicial aleatoria */
	poblacionInic(pobl, &espcreencias);

	/* Se eval鷄 la aptitud de cada individuo */
	for (i = 0; i < TAMPOBL; i++) {
		evalua(&(pobl[i]), 0, 0, 0);
		violacion(&(pobl[i]), gmax);
		evs++;
	}

	/* El ciclo principal, se ejecuta Gmax generaciones */
	for (j = 0; j < Gmax; j++) {

		/* Actualiza el espacio de creencias,
		   tanto normativas como de restricciones */
		actualizaCreencias(pobl, &espcreencias, j);

		/* Se generan los hijos mediante mutaci髇 influenciada
		   por el espacio de creencias */
		generarHijos(pobl, &espcreencias);
		/* Se eval鷄 la aptitud de cada hijo */
		for (i = TAMPOBL; i < 2*TAMPOBL; i++) {
			evalua(&(pobl[i]), 0, 0, 0);
			violacion(&(pobl[i]), gmax);
			evs++;
		}

		/* Se hace el torneo entre padres e hijos */
		selecciona(pobl);
		
		/* Impresi髇 de los datos de la generaci髇 */
		if (j >= Gmax - 11 || (j+1)%(Gmax/100) == 0) {
		extremos(&indmin, &indmax, pobl);
		fprintf(a, "Generaci髇 %d\n", j+1);
		fprintf(a, "Aptitud media: %0.7f, aptitud m醲ima: %0.7f, aptitud m韓ima: %0.7f\n", media, pobl[indmax].aptitud, pobl[indmin].aptitud);
		fprintf(a, "Mejor individuo:");
		for (i = 0; i < VARIABLES; i++) {
			fprintf(a, " %0.7f,", pobl[indmin].variable[i]);
		}
		for (i = 0; i < NUMCONSTR; i++) {
			fprintf(a, "\ng%d = %0.7f", i+1, pobl[indmin].g[i]);
		}
fprintf(a, "\nviol = %0.7f", pobl[indmin].viol);
		fprintf(a, "\nEl mejor individuo es ");
		if (!pobl[indmin].factible) {
			fprintf(a, "no ");
		}
		fprintf(a, "factible.\nEvluaciones: %ld\n\n", evs);
		}
	}
	fclose(a);
//	printf("Thousandths of a second: %d\n", diferencia);
	printf("%0.7f", pobl[indmin].aptitud);
	if (!pobl[indmin].factible) {
		printf(" i");
	}
	printf("\n");
	return (0);
}

/* Inicia el espacio de creencias, con los intervalos para cada variable. */
void creenciasInic(struct creencias *esp) {
	int i;
	float l[VARIABLES], u[VARIABLES];

	limites(l, u);
	for (i = 0; i < VARIABLES; i++) {
		esp->L[i] = esp->U[i] = MAXFLOAT;
		esp->l[i] = esp->lp[i] = l[i];
		esp->u[i] = esp->up[i] = u[i];
	}
	esp->raiz = (struct celda *) malloc(sizeof(struct celda));
	esp->raiz->padre = NULL;
	esp->raiz->hijo = NULL;
	esp->raiz->profundidad = PROFUNDIDAD_MAX;
}

void poblacionInic(struct individuo *pobl, struct creencias *esp) {
	int i, j;
	for (i = 0; i < TAMPOBL; i++) {
		/* Para cada variable se elige un n鷐ero real,
		   en el rango especificado */
		for (j = 0; j < VARIABLES; j++) {
			pobl[i].variable[j] = rndreal(esp->lp[j], esp->up[j]);
		}
	}
}

void violacionInic(float gmax[]) {
	int i;

	for (i = 0; i < NUMCONSTR; i++) {
		gmax[i] = 0;
	}
}

void violacion(struct individuo *ind, float gmax[]) {
	int i;
	float v;

	if (TRUSSPROBL) {
		return;
	}

	ind->viol = 0;

	for (i = 0; i < NUMCONSTR; i++) {
		/* Inequiality constraints */
		if (i < NUMCONSTR - NUMEQCONSTR) {
			v = (ind->g[i] > 0)? ind->g[i]: 0;
		}
		/* Equality constraints */
		else {
			v = fabs(ind->g[i]);
		}

		if (v > gmax[i]) {
			gmax[i] = v;
		}
		ind->viol += v/gmax[i];
	}
}

/* Actualiza el espacio de creencias.
   La parte normativa se actualiza cada k generaciones */
void actualizaCreencias(struct individuo *pobl, struct creencias *esp, int t) {
	int aceptados[TOP + 3];
	int i, j, iinf, isup, dim, numHijo, sumando, celda, k = 20;
	float sup, inf;
	struct celda *nodoAct;

	/* Decide si realiza la actualizaci髇 de la parte normativa */
	if (t%k == 0) {
		/* Elige a los aceptados para afectar a la parte normativa
		   del espacio de creencias */
		aceptar(pobl);
		for (i = 0; i < VARIABLES; i++) {
			iinf = 0;
			inf = pobl[0].variable[i];
			isup = 0;
			sup = pobl[0].variable[i];
			/* Ciclo para buscar los valores m醩 altos y bajos
			   de cada una de las variables */
			for (j = 1; j < TOP; j++) {
				if (pobl[j].variable[i] < inf) {
					iinf = j;
					inf = pobl[j].variable[i];
				}
				if (pobl[j].variable[i] > sup) {
					isup = j;
					sup = pobl[j].variable[i];
				}
			}

			/* Aplicaci髇 de las reglas de actualizaci髇
			   de la parte normativa */
/*			if ( (inf < esp->l[i]) || (pobl[iinf].aptitud < esp->L[i] && pobl[iinf].factible) ) {
				if ( (sup > esp->u[i]) || (pobl[isup].aptitud < esp->U[i] && pobl[isup].factible) ) {
					if (inf < sup || inf < esp->l[i]) {
						esp->l[i] = inf;
						esp->L[i] = pobl[iinf].aptitud;
					}
					if (sup > inf || sup > esp->u[i]) {
						esp->u[i] = sup;
						esp->U[i] = pobl[isup].aptitud;
					}
				}
				else {
					if (inf < esp->u[i]) {
						esp->l[i] = inf;
						esp->L[i] = pobl[iinf].aptitud;
					}
				}
			}
			else if ( (sup > esp->u[i]) || (pobl[isup].aptitud < esp->U[i] && pobl[isup].factible) ) {
				if (sup > esp->l[i]) {
					esp->u[i] = sup;
					esp->U[i] = pobl[isup].aptitud;
				}
			}*/

			if ( (inf < esp->l[i]) || (pobl[iinf].aptitud < esp->L[i] && pobl[iinf].factible) ) {
				if (inf < esp->u[i]) {
					esp->l[i] = inf;
					esp->L[i] = pobl[iinf].aptitud;
				}
			}
			if ( (sup > esp->u[i]) || (pobl[isup].aptitud < esp->U[i] && pobl[isup].factible) ) {
				if (sup > esp->l[i]) {
					esp->u[i] = sup;
					esp->U[i] = pobl[isup].aptitud;
				}
			}
//printf("Dimensi髇 %2d: %0.10f - %0.10f\n", i, esp->l[i], esp->u[i]);
		}
		/* Crea un nuevo 醨bol para los nuevos intervalos */
ftime(&tiempo1);
		expande(esp->raiz, pobl, esp);
ftime(&tiempo2);
diferencia += 1000*(tiempo2.time - tiempo1.time) + tiempo2.millitm - tiempo1.millitm;
	}

	/* Actualiza la parte de restricciones */

	/* Asocia a cada individuo con el nodo que lo contiene */
	ftime(&tiempo1);
	for (i = 0; i < TAMPOBL; i++) {
		numHijo = 0;
		/* Ciclo para verificar que el individuo se encuentre
		   dentro de los intervalos de la parte normativa */
		for (j = 0; j < VARIABLES; j++) {
			if (pobl[i].variable[j] < esp->l[j] ||
			    pobl[i].variable[j] > esp->u[j]) {
				numHijo = -1;
				break;
			}
		}
		if (numHijo == -1) {
			pobl[i].celda = NULL;
			continue;
		}

		for (nodoAct = esp->raiz; nodoAct->d[0] != -1; nodoAct = &(nodoAct->hijo[numHijo])) {
			numHijo = 0;
			sumando = 1;
			for (j = 0; j < TREEDIMS; j++) {
				dim = nodoAct->d[j];
				if (pobl[i].variable[dim] > (nodoAct->lnodo[dim] + nodoAct->unodo[dim])/2) {
					numHijo += sumando;
				}
				sumando += sumando;
			}
		}
		pobl[i].celda =  nodoAct;

		if (pobl[i].factible) {
			pobl[i].celda->factibles++;
			if (pobl[i].celda->factibles == 1) {
				if (pobl[i].celda->noFactibles == 0) {
					pobl[i].celda->clase = FACTIBLE;
				}
				else {
					pobl[i].celda->clase = SEMIFACTIBLE;
					if (pobl[i].celda->profundidad > 1) {
						expande(pobl[i].celda, pobl, esp);
						i = -1;
						continue;
					}
				}
			}
		}
		else {
			pobl[i].celda->noFactibles++;
			if (pobl[i].celda->noFactibles == 1) {
				if (pobl[i].celda->factibles == 0) {
					pobl[i].celda->clase = NO_FACTIBLE;
				}
				else {
					pobl[i].celda->clase = SEMIFACTIBLE;
					if (pobl[i].celda->profundidad > 1) {
						expande(pobl[i].celda, pobl, esp);
						i = -1;
						continue;
					}
				}
			}
		}
	}
	ftime(&tiempo2);
	diferencia += 1000*(tiempo2.time - tiempo1.time) + tiempo2.millitm - tiempo1.millitm;
}

void expande(struct celda *nodoAct, struct individuo *pobl, struct creencias *esp) {
	int i, j, numArbol, numHijo, sumando, dim, min;
	int sumMin[PRUEBAS_ARBOL][TREEDIMS + 1];
	float tmp;

	/* Crea y habilita a los hijos para formar el 醨bol */
	if (nodoAct->hijo == NULL) {
		nodoAct->hijo = (struct celda *) malloc(TREENODES*sizeof(struct celda));
		for (i = 0; i < TREENODES; i++) {
			nodoAct->hijo[i].padre = nodoAct;
			nodoAct->hijo[i].hijo = NULL;
			nodoAct->hijo[i].profundidad = nodoAct->profundidad - 1;
		}
	}
	for (i = 0; i < TREENODES; i++) {
		nodoAct->hijo[i].d[0] = -1;
	}

	/* Si es la ra韟, sus intervalos son los de la parte normativa */
	if (nodoAct->padre == NULL) {
		for (i = 0; i < VARIABLES; i++) {
			nodoAct->lnodo[i] = esp->l[i];
			nodoAct->unodo[i] = esp->u[i];
		}
	}

	if (VARIABLES > TREEDIMS) {
		for (numArbol = 0; numArbol < PRUEBAS_ARBOL; numArbol++) {
			/* Reiniciaci髇 de los contadores de individuos factibles
			   de los hijos */
			for (i = 0; i < TREENODES; i++) {
				nodoAct->hijo[i].factibles = 0;
				nodoAct->hijo[i].noFactibles = 0;
			}

			/* Elecci髇 de las dimensiones por particionar al azar */
			sumMin[numArbol][1] = rnd(0, VARIABLES-1);
			sumMin[numArbol][2] = rnd(0, VARIABLES-2);
			sumMin[numArbol][3] = rnd(0, VARIABLES-3);
			if (sumMin[numArbol][2] >= sumMin[numArbol][1]) {
				sumMin[numArbol][2]++;