guess.cpp

遗传算法,实现的是一个猜答案的过程

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define M 100	//演化池大小

struct answer {
	char ch[101];
	int score;
}pool[M];

float crossPro = 0.7;
long generation = 500;

int getScore(int k);

void initPool();
void GA();
void outResult();
void crossOver(int k1, int k2, int p1, int p2);
void mutationFirst(int k, int p);
void mutationLast(int k, int p);
void order();

void main(){

	srand((unsigned)time(NULL));
	initPool();
	GA();
	//outResult();
	getchar();
}


void initPool(){
	for(int i = 0; i < M/2; i ++) {
		for(int j = 0; j < 100; j ++) {
			pool[i].ch[j] = 'A' + (rand()%4);
		}
		pool[i].score = getScore(i);
	}
}

void GA(){
	for(int i = 0; i < generation; i ++){
		if(pool[0].score >= 100)
			break;
		int newSon = 0;
		int p = newSon + 50;
		if(i >= 40)
			crossPro = 0.1;
		
		while(newSon < 50){
			int x = rand()%10;
			if(x < crossPro*10){
				crossOver(rand()%(M/4), rand()%(M/2), p, p+1);	//杂交
				newSon += 2;
			}else{
				if(i<50)
					mutationFirst(rand()%(M/2), p);				//变异
				else
					mutationLast(rand()%(M/2), p);
				newSon ++;
			}
			p = newSon + 50;
		}
		//valuate and order
		for(int m = 0; m < M; m ++){
			pool[m].score = getScore(m);
		}
		order();
		printf("第%d代最优解：",i);
		outResult();
		//printf("\n");
	}
}

void outResult(){
//	for(int k = 0; k < 50; k ++){
	for(int i = 0; i < 100; i ++){
		printf("%c",pool[0].ch[i]); 		
		if((i+1)%10 == 0)
			printf(" ");			
	}
	printf("%d\n",pool[0].score);
	//printf("%d ", pool[0].score);
//	}
}

void crossOver(int k1, int k2, int p1, int p2){
	int x = rand()%98 + 1;
	for(int i = 0; i < x; i ++){
		pool[p1].ch[i] = pool[k1].ch[i];
		pool[p2].ch[i] = pool[k2].ch[i];
	}
	for(int j = x; j < 100; j ++){
		pool[p1].ch[j] = pool[k2].ch[j];
		pool[p2].ch[j] = pool[k1].ch[j];
	}
}

void mutationFirst(int k, int p){
/*	int x = rand()%98 + 1;
	for(int i = 0; i < x; i ++){
		pool[p].ch[i] = pool[k].ch[100 - i];
	}
	for(int j = x; j < 100; j ++){
		pool[p].ch[j] = pool[k].ch[100 - j];
	}*/
	int x;
	strcpy(pool[p].ch, pool[k].ch);
	for(int i = 0; i < 5; i ++){
		x = rand()%99;
		//pool[p].ch[x] = (pool[p].ch[x] + (rand()%3 + 1))%('A') + 'A';
		pool[p].ch[x] = 'A' + rand()%4;
	}
}

void mutationLast(int k, int p){
	int x;
	strcpy(pool[p].ch, pool[k].ch);
	for(int i = 0; i < 1; i ++){
		x = rand()%99;
		//pool[p].ch[x] = (pool[p].ch[x] + (rand()%3 + 1))%('A') + 'A';
		pool[p].ch[x] = 'A' + rand()%4;
	}
}

int getScore(int k){
	char answers[] = {"ABCDDCBADDBBADDADDDCCABCDAAABBDDACCBCDDACCBBCCADCBBCDCDADACDACBACCABADDCCBBBDAAAABCDDDDDCCABBBBAAACD"};
	int score = 0;
	for(int i = 0; i < 100; i ++){
		if(pool[k].ch[i] == answers[i])
			score ++;
	}
	return score;
}

void order(){
	struct answer temp;
	for(int i = 0; i <= M/2-10; i ++){
		for(int j = M-1; j > i; j--){
			if(pool[j].score > pool[j-1].score){
				temp = pool[j];
				pool[j] = pool[j-1];
				pool[j-1] = temp;
			}
		}
	}
}