#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");
}