cultural.c

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

				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]);

			for (i = 0; i < TAMPOBL; i++) {
				numHijo = 0;
				for (j = 0; j < VARIABLES; j++) {
					if (pobl[i].variable[j] < nodoAct->lnodo[j] ||
					    pobl[i].variable[j] > nodoAct->unodo[j]) {
						numHijo = -1;
						break;
					}
				}
				if (numHijo == -1) {
					continue;
				}
				sumando = 1;
				for (j = 0; j < TREEDIMS; j++) {
					dim = sumMin[numArbol][j + 1];
					if (pobl[i].variable[dim] > (nodoAct->lnodo[dim] + nodoAct->unodo[dim])/2) {
						numHijo += sumando;
					}
					sumando += sumando;
				}
				if (pobl[i].factible) {
					nodoAct->hijo[numHijo].factibles++;
				}
				else {
					nodoAct->hijo[numHijo].noFactibles++;
				}
			}

			sumMin[numArbol][0] = 0;
			for (i = 0; i < TREENODES; i++) {
				sumMin[numArbol][0] += (nodoAct->hijo[i].factibles < nodoAct->hijo[i].noFactibles)? nodoAct->hijo[i].factibles: nodoAct->hijo[i].noFactibles;
			}
		}
		min = sumMin[0][0];
		numArbol = 0;
		for (i = 1; i < PRUEBAS_ARBOL; i++) {
			if (sumMin[i][0] < min) {
				min = sumMin[i][0];
				numArbol = i;
			}
		}
		
		for (i = 0; i < TREEDIMS; i++) {
			nodoAct->d[i] = sumMin[numArbol][i + 1];
		}
	}

	else {
		for (i = 0; i < VARIABLES; i++) {
			nodoAct->d[i] = i;
		}
	}

	for (i = 0; i < TAMPOBL; i++) {
		numHijo = 0;
		for (j = 0; j < VARIABLES; j++) {
			if (pobl[i].variable[j] < nodoAct->lnodo[j] ||
			    pobl[i].variable[j] > nodoAct->unodo[j]) {
				numHijo = -1;
				break;
			}
		}
		if (numHijo == -1) {
			continue;
		}
		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;
		}
		if (pobl[i].factible) {
			nodoAct->hijo[numHijo].factibles++;
		}
		else {
			nodoAct->hijo[numHijo].noFactibles++;
		}
	}

	/* Asignaci髇 del los intervalos a cada celda */
	for (i = 0; i < TREENODES; i++) {
		for (j = 0; j < VARIABLES; j++) {
			nodoAct->hijo[i].lnodo[j] = nodoAct->lnodo[j];
			nodoAct->hijo[i].unodo[j] = nodoAct->unodo[j];
		}
		numHijo = i;
		sumando = 1;
		for (j = 0; j < TREEDIMS; j++) {
			tmp = (nodoAct->lnodo[nodoAct->d[j]] + nodoAct->unodo[nodoAct->d[j]]) / 2;
			if (numHijo % (2*sumando)) {
				nodoAct->hijo[i].lnodo[nodoAct->d[j]] = tmp;
				numHijo -= sumando;
			}
			else {
				nodoAct->hijo[i].unodo[nodoAct->d[j]] = tmp;
			}
			sumando += sumando;
		}
	}

	/* Asignaci髇 de la clase a la celda */
	for (i = 0; i < TREENODES; i++) {
		if (nodoAct->hijo[i].factibles > 0) {
			if (nodoAct->hijo[i].noFactibles > 0) {
				nodoAct->hijo[i].clase = SEMIFACTIBLE;
			}
			else {
				nodoAct->hijo[i].clase = FACTIBLE;
			}
		}
		else {
			if (nodoAct->hijo[i].noFactibles > 0) {
				nodoAct->hijo[i].clase = NO_FACTIBLE;
			}
			else {
				nodoAct->hijo[i].clase = DESCONOCIDA;
			}
		}
	}

	/* Llamada recursiva a expande */
	if (nodoAct->profundidad > 1) {
		for (i = 0; i < TREENODES; i++) {
			if (nodoAct->hijo[i].clase == SEMIFACTIBLE) {
				expande(&(nodoAct->hijo[i]), pobl, esp);
			}
		}
	}
}

void aceptar(struct individuo *pobl) {
	/* Ordenar descendentemente por aptitud, pero dejando factibles primero */
	qsort(pobl, TAMPOBL, sizeof(struct individuo), &compVictorias);
}

int compAptitud(const void *ind1, const void *ind2) {
	int dif;

	if ( ((struct individuo *)ind2)->factible && ((struct individuo *)ind1)->factible ) {
		if (((struct individuo *)ind2)->aptitud > ((struct individuo *)ind1)->aptitud) {
			return -1;
		}
		if (((struct individuo *)ind2)->aptitud < ((struct individuo *)ind1)->aptitud) {
			return 1;
		}
		return 0;
	}
		
	if ( ((struct individuo *)ind1)->factible ) {
		return -1;
	}
	if ( ((struct individuo *)ind2)->factible ) {
		return 1;
	}

	if (((struct individuo *)ind2)->viol > ((struct individuo *)ind1)->viol) {
		return -1;
	}
	if (((struct individuo *)ind2)->viol < ((struct individuo *)ind1)->viol) {
		return 1;
	}

	return 0;
}

void generarHijos(struct individuo *pobl, struct creencias *esp) {
	int i, j;
	float x;

	for (i = 0; i < TAMPOBL; i++) {
		for (j = 0; j < VARIABLES; j++) {
			pobl[i+TAMPOBL].variable[j] = pobl[i].variable[j];
			x = randomnormaldeviate();
			if (pobl[i].variable[j] < esp->l[j]) {
				pobl[i+TAMPOBL].variable[j] += fabs(x*(esp->u[j] - esp->l[j]));
			}
			else if (pobl[i].variable[j] > esp->u[j]) {
				pobl[i+TAMPOBL].variable[j] -= fabs(x*(esp->u[j] - esp->l[j]));
			}
			else if (pobl[i].celda == NULL) {
				pobl[i+TAMPOBL].variable[j] += x*(esp->u[j]-esp->l[j]);
			}
			else if (pobl[i].celda->clase == NO_FACTIBLE) {
				mueve(i, j, x, pobl, esp);
			}
			else {
				pobl[i+TAMPOBL].variable[j] += x*(pobl[i].celda->unodo[j] - pobl[i].celda->lnodo[j]);
			}
			if (pobl[i+TAMPOBL].variable[j] > esp->up[j]) {
				pobl[i+TAMPOBL].variable[j] = esp->up[j];
			}
			else if (pobl[i+TAMPOBL].variable[j] < esp->lp[j]) {
				pobl[i+TAMPOBL].variable[j] = esp->lp[j];
			}
		}
	}
}

void mueve(int indiv, int dim, float x, struct individuo *pobl, struct creencias *esp) {
	struct celda *celdaNueva;

	celdaNueva = cercana(SEMIFACTIBLE, pobl[indiv].celda);
	if (celdaNueva == NULL) {
		celdaNueva = cercana(DESCONOCIDA, pobl[indiv].celda);
	}

	if (celdaNueva == NULL) {
//		pobl[indiv+TAMPOBL].variable[dim] += x*(pobl[indiv].celda->unodo[dim] - pobl[indiv].celda->lnodo[dim]);
		pobl[indiv+TAMPOBL].variable[dim] += x*(esp->u[dim] - esp->l[dim]);
	}
	else {
/*		if (pobl[indiv+TAMPOBL].variable[dim] < celdaNueva->lnodo[dim]) {
			pobl[indiv+TAMPOBL].variable[dim] += fabs(x*(celdaNueva->lnodo[dim] - pobl[indiv+TAMPOBL].variable[dim]));
		}
		else if (pobl[indiv+TAMPOBL].variable[dim] > celdaNueva->unodo[dim]) {
			pobl[indiv+TAMPOBL].variable[dim] -= fabs(x*(pobl[indiv+TAMPOBL].variable[dim] - celdaNueva->unodo[dim]));
		}
		else {
			pobl[indiv+TAMPOBL].variable[dim] += x*(celdaNueva->unodo[dim] - celdaNueva->lnodo[dim]);
		}*/
		pobl[indiv+TAMPOBL].variable[dim] = x*(celdaNueva->unodo[dim] - celdaNueva->lnodo[dim]) + (celdaNueva->unodo[dim] + celdaNueva->lnodo[dim])/2;
	}
}

struct celda *cercana(int prioridad, struct celda *nodo) {
	int i;
	struct celda *res;

	for (; nodo->padre != NULL; nodo = nodo->padre) {
		for (i = 0; i < TREENODES; i++) {
			if (&(nodo->padre->hijo[i]) == nodo) {
				continue;
			}
			res = busca(prioridad, &(nodo->padre->hijo[i]));
			if (res != NULL) {
				return res;
			}
		}
	}
	return NULL;
}

struct celda *busca(int prioridad, struct celda *nodo) {
	int i;
	struct celda *res;

	if (nodo->d[0] == -1) {
		if (nodo->clase <= prioridad) {
			return nodo;
		}
		else {
			return NULL;
		}
	}

	for (i = 0; i < TREENODES; i++) {
		res = busca(prioridad, &(nodo->hijo[i]));
		if (res != NULL) {
			return res;
		}
	}
	return NULL;
}

/* Realiza el torneo de la poblacion de tama駉 2*TAMPOBL.
   El n鷐ero de enfrentamientos por individuo es c */
void selecciona(struct individuo *pobl) {
	int c = TAMPOBL/2;
	int i, j, contr, indmin;
	float min;
	char hayFactibles;

	/* Prueba para saber si hay factibles */
	for (i = 0; (!pobl[i].factible) || (i < 2*TAMPOBL); i++);
	hayFactibles = (i < 2*TAMPOBL)? 1: 0;

	/* Ciclo para realizar los torneos */
	for (i = 0; i < 2*TAMPOBL; i++) {
		pobl[i].victorias = 0;
		for (j = 0; j < c; j++) {
			contr = rnd(0, 2*TAMPOBL-2);
			contr = (contr>=i)? contr+1: contr;
			if ((pobl[i].factible && pobl[contr].factible)) {
				if (pobl[i].aptitud < pobl[contr].aptitud) {
					pobl[i].victorias++;
				}
			}
			else {
				if (!pobl[contr].factible) {
					if (pobl[i].factible) {
						pobl[i].victorias++;
					}
					else if (pobl[i].viol < pobl[contr].viol) {
						pobl[i].victorias++;
					}
				}
			}
/*			if (pobl[i].factible == pobl[contr].factible) {
				if (pobl[i].aptitud < pobl[contr].aptitud) {
					pobl[i].victorias++;
				}
			}
			else {
				if (pobl[i].factible) {
					pobl[i].victorias++;
				}
			}*/
		}
	}

	/* Lleva a cabo el elitismo, asignando m醩 vicorias al mejor individuo */
	for (i = 0; !pobl[i].factible && i < 2*TAMPOBL; i++);
	if (i < 2*TAMPOBL) {
		min = pobl[i].aptitud;
		indmin = i;
		for (; i < 2*TAMPOBL; i++) {
			if (pobl[i].factible && pobl[i].aptitud < min) {
				indmin = i;
				min = pobl[i].aptitud;
			}
		}
		pobl[indmin].victorias = c + 1;
	}

	/* Ordenar descendentemente por n鷐ero de victorias */
	qsort(pobl, 2*TAMPOBL, sizeof(struct individuo), &compVictorias);
//	nuevoInd(&(pobl[TAMPOBL - 1]));
}

int compVictorias(const void *ind1, const void *ind2) {
	int dif;
	dif = ((struct individuo *)ind2)->victorias - ((struct individuo *)ind1)->victorias;
	return dif;
}

void nuevoInd(struct individuo *ind) {
	int j;
	float l[VARIABLES], u[VARIABLES];

	limites(l, u);
	for (j = 0; j < VARIABLES; j++) {
		ind->variable[j] = rndreal(l[j], u[j]);
	}
}

/* Funci髇 para encontrar las aptitudes m韓ima y m醲ima de pobl */
void extremos(int *indmin, int *indmax, struct individuo *pobl) {
	int i, sumados = 0;
	float min, max, med = 0.0;

	/* Se prefieren soluciones factibles */
	for (i = 0; !pobl[i].factible && i < TAMPOBL; i++);
	if (i < TAMPOBL) {
		max = min = pobl[i].aptitud;
		*indmin = *indmax = i;
		for (; i < TAMPOBL; i++) {
			if (pobl[i].factible) {
				if (pobl[i].aptitud < min) {
					*indmin = i;
					min = pobl[i].aptitud;
				}
				if (pobl[i].aptitud > max) {
					*indmax = i;
					max = pobl[i].aptitud;
				}
				med += pobl[i].aptitud;
				sumados++;
			}
		}
	}
	else {
		max = min = pobl[0].viol;
		*indmin = *indmax = 0;
		for (i = 0; i < TAMPOBL; i++) {
			if (pobl[i].viol < min) {
				*indmin = i;
				min = pobl[i].viol;
			}
			if (pobl[i].viol > max) {
				*indmax = i;
				max = pobl[i].viol;
			}
			med += pobl[i].aptitud;
			sumados++;
		}
	}
	media = med/sumados;
}