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

using namespace std;

#define GeneNumber        4                 // 基因長度
#define PopulationSize    10                // 母群數量
#define MaxGeneration     100               // 迭代次數
#define CrossoverRate     0.7               // 交配率
#define MutationRate      0.1               // 突變率

class parent{
public: 
	int genes[GeneNumber];
	double fitness;
	double dec_value;
};

// PositionRand(): 隨機取得(交配點/突變位置)
#define PositionRand()           (rand()%GeneNumber)
// BinaryRand():  隨機產生0~1整數(無小數)for(產生基因)
#define BinaryRand()            (rand()%2)
// PointRand():   隨機產生0~1 的亂數(有小數)for(交配/突變率)
#define PointRand()             ((double)rand()/(double)RAND_MAX)

// =====================================================

// 進行初始化
void initialize();           
// 輪盤式選擇(隨機式)
void CrossoverPool();   
// 交配, 交配池中的個體進行交配(兩點交配)
void crossover();           
// 突變, 逐一bit 慢慢確認突變
void mutation();
// 計算基因所對應之適應值
void cal_fitness(parent *x);     
// 計算基因對應之進制值
void cal_Decimal(parent *x);     
// 讓交配點的第二點永遠比第一點大
void swap(int *x,int *b);


// =====================================================

parent population[PopulationSize];      // 母體數量
parent pool[PopulationSize];            // 交配池
parent *best_gene;                       // 從以前到現在最好的基因


// binary 2 dec，將染色體中的二進位(genes) ，轉為十進位(dec_value)
void cal_Decimal(parent *x)
{
	int i,j = 0;
	double dec = 0;
	for(i=GeneNumber-1; i >= 0; i--){
		dec += x->genes[i]*pow((double)2,j);
		j++;
	}
	x->dec_value = dec;
}

//計算適應值 適應函數為31i-i*i
void cal_fitness(parent *x)
{    
     double i = x->dec_value;
     x->fitness = 31*i - i*i;
}

//將a,b兩數互換，讓起始數永遠比終點數小
void swap(int *a,int *b)
{
	int x;
	x = *a;
	*a = *b;
	*b = x;
}

//初始化
void initialize()
{
     int i, j,x,y;
	 for(i=0; i<PopulationSize; i++){
		 for(j=0; j<GeneNumber; j++){
			 // 每個母體的基因都是隨機給/1
			 population[i].genes[j] = BinaryRand();
		 }
	 }

	 // 計算母體基因之進制值
	 for(x = 0; x < PopulationSize; x++){
		 cout <<x <<" : bin = ";
		 for(y = 0; y < GeneNumber; y++){
			 cout << population[x].genes[y];
		 }

		 cout << '\n';
		 //計算十進位之值並輸出
		 cal_Decimal(&population[x]);
		 cout << "Dec = " << population[x].dec_value << '\n';
		 //計算適應並變輸出
		 cal_fitness(&population[x]);
		 cout << "Fitness = "<< population[x].fitness << '\n';
		 //更新最佳基因
		 if(x==0)
			 	 best_gene = &population[0];
		 else if(population[x].fitness > best_gene->fitness)
			 best_gene = &population[x];
		 cout << "best_gene = "<< best_gene->fitness << '\n';
		 cout << "======================================="<< '\n';

	 }
}
//輪盤式選擇
void CrossoverPool()
{
	int i,j;
	double FitnessSum = 0;//適應值總和
	double Fitness_percent[PopulationSize];//每個基因的適應值所占整體的比例
	double Fitness_percent_total=0;
	int pickup;//抽取個體 
	//計算適應值總和並輸出
	for(i=0; i < PopulationSize; i++){
		FitnessSum += population[i].fitness;
	}
	cout << "FitnessSum = "<< FitnessSum <<'\n';
	//計算每個基因的適應值佔總合多少比例並輸出
	for(i=0; i < PopulationSize; i++){
		Fitness_percent[i] = population[i].fitness / FitnessSum;
		cout << "Fitness_percent = " << Fitness_percent[i]<< '\n';
		Fitness_percent_total+=Fitness_percent[i];
	}	 
	cout << "Fitness_percent_total = " << Fitness_percent_total << '\n';
	//選擇基因丟入交配池
	for(i=0; i < PopulationSize; i++){
		pickup = rand()%PopulationSize;
		cout << i << " : Pool = ";
		for(j=0; j < GeneNumber; j++){
			pool[i].genes[j] = population[pickup].genes[j];
			cout << pool[i].genes[j];
		}
		cout << '\n';
	}  
}
//兩點交配
void crossover()
{
	int i,j;
	int PartOfComplete=0;//完成數目
	int p1,p2;//交配池中的隨機兩組基因
	int pos1=0,pos2=0;//交換點由pos1~pos2
	double CrossoverProbability;//交配機率



	//重複執行直到交配完10組個體
	while(PartOfComplete < PopulationSize){
		//隨機選擇兩個個體
		p1 = rand() % PopulationSize;
		do{ p2 = rand() % PopulationSize;}while(p2 == p1);
		CrossoverProbability=PointRand();	
		cout << "CrossoverProbability = " << CrossoverProbability << '\n';
		
		//交配
		if(CrossoverProbability < CrossoverRate){
			pos1=PositionRand();		
			do{
				pos2=PositionRand();
			}while(pos2 == pos1 || ((pos1 == 0 || pos1 == GeneNumber-1) && (pos1+pos2 == GeneNumber-1)));
			//↑↑↑↑↑判斷機制pos1:pos1與pos2不可為同值且pos1與pos2不可同時為第一點與最後一點↑↑↑↑↑
			cout << "pos1 = "<< pos1 <<" pos2 = "<< pos2 << '\n';			
			//強制由左往右做區域的選取
			if(pos1>pos2)
				swap(&pos1,&pos2);
			cout << "pos1 = " << pos1 <<" pos2 = " << pos2 << '\n';
			cout << "p1 = " << p1 <<" p2 = " << p2 << '\n';

			//第一階段交配
			for(i=0; i<pos1; i++){
				population[PartOfComplete].genes[i]=pool[p1].genes[i];
				population[PartOfComplete+1].genes[i]=pool[p2].genes[i];
			}
			//第二階段交配
			for(i=pos1; i<=pos2; i++){
				population[PartOfComplete+1].genes[i]=pool[p1].genes[i];
				population[PartOfComplete].genes[i]=pool[p2].genes[i];
			}
			//第三階段交配
			for(i=pos2+1; i<GeneNumber; i++){
				population[PartOfComplete].genes[i]=pool[p1].genes[i];
				population[PartOfComplete+1].genes[i]=pool[p2].genes[i];
			}
			//輸出交配後的二進制之值
			for(i = 0; i < PopulationSize; i++){
				cout <<i <<" : bin = ";
				for(j = 0; j < GeneNumber; j++){
					cout << population[i].genes[j];
				}
				cout << '\n';
			}
			//進行下面兩個個體的交配
			PartOfComplete+=2;
		}
	}
}
//突變
void mutation()
{
	int i,j;
	int pos;//突變點
	double MutationProbability;//突變機率
	for(i = 0; i < PopulationSize; i++){
		MutationProbability = PointRand();
		cout << "MutationProbability = "<< MutationProbability <<'\n';
		//是否發生突變
		if(MutationProbability < MutationRate){
			//突變點
			pos = PositionRand();
			//做突變點的突變處理
			population[i].genes[pos] = !population[i].genes[pos];
			cout<<"pos = "<< pos <<'\n';
		}
		cout << i <<" : bin = ";
		for(j = 0; j < GeneNumber; j++){
			cout << population[i].genes[j];
		}
		cout << '\n';
		//計算十進制之值並輸出
		cal_Decimal(&population[i]);
		cout << "Dec = " << population[i].dec_value << '\n';
		//計算適應值並輸出
		cal_fitness(&population[i]);
		cout << "Fitness = "<< population[i].fitness << '\n';
		//更新最佳基因
		if(population[i].fitness > best_gene->fitness)
			best_gene = &population[i];
		cout << "best_gene = "<< best_gene->fitness << '\n';
		cout << "======================================="<< '\n';
	}	
}


int main()
{
	srand((unsigned)time(NULL));
	initialize();            // 初始化
		cout<<'\n';
	CrossoverPool();		//分配式選擇
		cout<<'\n'; 
	crossover();			//兩點交配
		cout<<'\n';
	mutation();				//突變
		cout<<'\n';
				cout << "best_gene = "<< best_gene->fitness << '\n';

	system("pause");
}