GPUを使って全部1の遺伝子を目指してみた。

all-one.cu

#include <stdio.h>


#define GENOM_SIZE 64
#define GENOM_NUM 10
#define MUTATION_RATE 5


__device__ unsigned int rand(unsigned int* seeds){
	seeds[threadIdx.x] = seeds[threadIdx.x] * 0x97531 + 0x13579;
	return (seeds[threadIdx.x] & 0x7fffffff) / 100;
}


__global__ void make(bool* dst, unsigned int* seeds){
	seeds[threadIdx.x] = threadIdx.x;
	for(int i=0; i<GENOM_SIZE; i++){
		dst[threadIdx.x*GENOM_SIZE + i] = rand(seeds)%2;
	}
}


__host__ __device__ void calc_fitness_single(bool* src, int pos, int* dst){
	*dst = 0;
	for(int i=0; i<GENOM_SIZE; i++){
		if(src[pos*GENOM_SIZE + i]){
			(*dst)++;
		}   
	}   
}   


__host__ int calc_fitness_single(bool* src, int pos){
	int result;
	calc_fitness_single(src, pos, &result);
	return result;
}   


__global__ void calc_fitness_parallel(bool* src, int* fitness){
	calc_fitness_single(src, threadIdx.x, &fitness[threadIdx.x]);
}


__device__ int select(int* fitness, unsigned int* seeds){
	int a = rand(seeds) % GENOM_NUM;
	int b = rand(seeds) % GENOM_NUM;
	return fitness[a] > fitness[b] ? a : b;
}


__global__ void step(bool* src, bool* dst, int* fitness, unsigned int* seeds){
	int a = select(fitness, seeds);
	int b = select(fitness, seeds);
	int pivot = 1 + rand(seeds) % (GENOM_SIZE - 1);

	for(int i=0; i<GENOM_SIZE; i++){
		dst[threadIdx.x*GENOM_SIZE + i] = src[(i<pivot ? a : b)*GENOM_SIZE + i];
	}
}


__global__ void mutation(bool* dst, unsigned int* seeds){
	if(rand(seeds)%MUTATION_RATE == 0){
		int pos = threadIdx.x*GENOM_SIZE + rand(seeds)%GENOM_SIZE;
		dst[pos] = !dst[pos];
	}
}


__host__ int find_best(bool* genoms){
	int best_fitness = 0;
	int best_position = 0;

	for(int i=0; i<GENOM_NUM; i++){
		int fitness = calc_fitness_single(genoms, i);
		if(fitness > best_fitness){
			best_fitness = fitness;
			best_position = i;
		}
	}

	return best_position;
}


__host__ int avg(int* fitness){
	int sum = fitness[0];
	for(int i=1; i<GENOM_NUM; i++){
		sum += fitness[i];
	}
	return sum / GENOM_NUM;
}


__host__ int max(int* fitness){
	int max = fitness[0];
	for(int i=1; i<GENOM_NUM; i++){
		max = max > fitness[i] ? max : fitness[i];
	}
	return max;
}


__host__ int min(int* fitness){
	int min = fitness[0];
	for(int i=1; i<GENOM_NUM; i++){
		min = min < fitness[i] ? min : fitness[i];
	}
	return min;
}


__host__ void show_genoms(bool* genoms, int* fitness){
	for(int i=0; i<GENOM_NUM; i++){
		if(fitness[i] != GENOM_SIZE){
			for(int j=0; j<GENOM_SIZE; j++){
				printf(genoms[i*GENOM_SIZE + j] ? "\e[32m1\e[0m " : "0 ");
			}
			printf(max(fitness) == fitness[i] ? "\e[31m(%d)\e[0m\n" : "(%d)\n", fitness[i]);
		}else{
			printf("\e[47m\e[30m");
			for(int j=0; j<GENOM_SIZE; j++){
				printf("1 ");
			}
			printf("(%d)\e[0m\n", fitness[i]);
		}
	}
	printf("max fitness: %d\n", max(fitness));
	printf("min fitness: %d\n", min(fitness));
	printf("average: %d\n", avg(fitness));
}


int main(){
	bool *genoms, *next, *swap;
	int *fitness;
	unsigned int *seeds;
	bool h_genoms[GENOM_SIZE * GENOM_NUM];
	int h_fitness[GENOM_SIZE * GENOM_NUM];

	cudaMalloc((void**)&genoms, GENOM_SIZE * GENOM_NUM);
	cudaMalloc((void**)&next, GENOM_SIZE * GENOM_NUM);
	cudaMalloc((void**)&fitness, sizeof(int) * GENOM_SIZE * GENOM_NUM);
	cudaMalloc((void**)&seeds, sizeof(unsigned int) * GENOM_SIZE * GENOM_NUM);

	make<<<1, GENOM_NUM>>>(genoms, seeds);
	calc_fitness_parallel<<<1, GENOM_NUM>>>(genoms, fitness);

	int generation=0;
	for(; calc_fitness_single(h_genoms, find_best(h_genoms)) < GENOM_SIZE; generation++){
		if(generation%5 == 0){
			cudaMemcpy(h_fitness, fitness, GENOM_SIZE * GENOM_NUM, cudaMemcpyDeviceToHost);

			printf("\n");
			show_genoms(h_genoms, h_fitness);
			printf("generation: %d\n", generation);
		}

		step<<<1, GENOM_NUM>>>(genoms, next, fitness, seeds);
		swap = genoms;
		genoms = next;
		next = swap;

		mutation<<<1, GENOM_NUM>>>(genoms, seeds);

		calc_fitness_parallel<<<1, GENOM_NUM>>>(genoms, fitness);
		cudaMemcpy(h_genoms, genoms, GENOM_SIZE * GENOM_NUM, cudaMemcpyDeviceToHost);
	}
	cudaMemcpy(h_genoms, genoms, GENOM_SIZE * GENOM_NUM, cudaMemcpyDeviceToHost);
	cudaMemcpy(h_fitness, fitness, GENOM_SIZE * GENOM_NUM, cudaMemcpyDeviceToHost);

	printf("\n");
	show_genoms(h_genoms, h_fitness);
	printf("generation: %d\n", generation);

	cudaFree(genoms);
	cudaFree(next);
	cudaFree(fitness);
	cudaFree(seeds);

	return 0;
}