cultural.cpp

此代码是文化算法的一个例子

/* Cultural algorithm for constrained optimization */

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.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
#define MAXFLOAT ((float)3.40282346638528860e+38)
/* 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("Max generations: ");
		scanf("%d", &Gmax);
		printf("(Key in)the seed of random(0..1): ");
		scanf("%f", &semilla);
		printf("(Key in)the name of the exit file: ");
		scanf("%s", cadena);
	}
	
	
	if ( (a = fopen(cadena, "w")) == NULL ) {
		printf("Error when opening the exit file.\n");
		return (1);
	}
	fprintf(a, "Max generations: %d\n", Gmax);
	fprintf(a, "Seed of random %f\n\n", semilla);
	
	putenv(tzstr);
	tzset();
	diferencia = 0;
	
	randomizef(semilla);
	initrandomnormaldeviate();
	

	violacionInic(gmax);
	
	creenciasInic(&espcreencias);
	
	poblacionInic(pobl, &espcreencias);
	
	for (i = 0; i < TAMPOBL; i++) {
		evalua(&(pobl[i]), 0, 0, 0);
		violacion(&(pobl[i]), gmax);
		evs++;
	}
	

	for (j = 0; j < Gmax; j++) {
		
		actualizaCreencias(pobl, &espcreencias, j);
		
		generarHijos(pobl, &espcreencias);
		for (i = TAMPOBL; i < 2*TAMPOBL; i++) {
			evalua(&(pobl[i]), 0, 0, 0);
			violacion(&(pobl[i]), gmax);
			evs++;
		}
		
		selecciona(pobl);
		
		if (j >= Gmax - 11 || (j+1)%(Gmax/100) == 0) {
			extremos(&indmin, &indmax, pobl);
			fprintf(a, "Generation %d\n", j+1);
			fprintf(a, "Average fitness: %0.7f, max fitness: %0.7f, min fitness: %0.7f\n", media, pobl[indmax].aptitud, pobl[indmin].aptitud);
			fprintf(a, "Better individual:");
			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, "\nThe best individual is ");
			if (!pobl[indmin].factible) {
				fprintf(a, "no ");
			}
			fprintf(a, "feasible.\nEvluaciones: %ld\n\n", evs);
		}
	}
	fclose(a);
	printf("%0.7f", pobl[indmin].aptitud);
	if (!pobl[indmin].factible) {
		printf(" i");
	}
	printf("\n");
	return (0);
}

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++) {
		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];
	}
}


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;

	if (t%k == 0) {

		aceptar(pobl);
		for (i = 0; i < VARIABLES; i++) {
			iinf = 0;
			inf = pobl[0].variable[i];
			isup = 0;
			sup = pobl[0].variable[i];
		
			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;
				}
			}
			
		}
	}	
	for (i = 0; i < TAMPOBL; i++) {
		numHijo = 0;
		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;
					}
				}
			}
		}
	}
}

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;
	

	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;
	}
	

	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++) {
	
			for (i = 0; i < TREENODES; i++) {
				nodoAct->hijo[i].factibles = 0;
				nodoAct->hijo[i].noFactibles = 0;
			}
			
		
			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]++;
				if (sumMin[numArbol][3] >= sumMin[numArbol][1]) {
					sumMin[numArbol][3]++;
				}
				if (sumMin[numArbol][3] >= sumMin[numArbol][2]) {
					sumMin[numArbol][3]++;
				}
			}
			else {
				if (sumMin[numArbol][3] >= sumMin[numArbol][2]) {
					sumMin[numArbol][3]++;
				}
				if (sumMin[numArbol][3] >= sumMin[numArbol][1]) {
					sumMin[numArbol][3]++;
				}
			}
			//printf("%d %d %d\n",sumMin[numArbol][1],sumMin[numArbol][2],sumMin[numArbol][3]);