#include <iostream>

#include <cstdlib>

#include <ctime>

#define NUM 50

#define LENGTH 100

#define NCLASS 10

 

void calc_ninzu(int population[][LENGTH], int ninzu[][NCLASS]);

void calc_score(int ninzu_penalty1,int ninzu_panalty2, int population[][LENGTH], int ninzu[][NCLASS],int gno[],int kibo1[],int kibo2[],int kibo3[], int fitness[]);

void pairing(int population[][LENGTH], int pair[][LENGTH]);

void one_point_crossover(double crossover_rate, int population[][LENGTH],int pair[][LENGTH]);

void mutation(double mutation_rate,int population[][LENGTH]);

void population_disp2(int population[][LENGTH],int fitness[]);

void roulette_selection(int population[][LENGTH],int fitness[]);

void roulette_selection2(int population[][LENGTH],int fitness[]);

void ranking_selection(int population[][LENGTH],int fitness[]);

 

int main()

{

 

        int population[NUM][LENGTH], ninzu[NUM][NCLASS];

        int gno[LENGTH], kibo1[LENGTH], kibo2[LENGTH], kibo3[LENGTH];

        int i,j;

        int fitness[NUM];

        int pair[NUM][LENGTH];

        int juni[LENGTH];

        int juni_count[4], zemi_count[NCLASS];

        int sedai, best_id, best_value;

        double ave;

        FILE *fp, *fp2;

        char s[256];

        int algorithm;//アルゴリズムの選択に用いる

        int ninzu_penalty1=100;

        int ninzu_penalty2=5;

 

        if ((fp = fopen("kekka.csv", "w")) == NULL) {

                printf("File cannot be created.\n");

                return -1;

        }

        //ファイルseminar.csv読み込み

        if ((fp2 = fopen("seminar.csv", "r")) == NULL) {

                printf("File cannot be opened.\n");

                return -1;

        }

        fgets(s, 256, fp2);

        for (i=0; i<LENGTH; i++){

                fscanf(fp2,"%d,%d,%d,%d",&gno[i],&kibo1[i],&kibo2[i],&kibo3[i]);

                //printf("%d %d %d %d\n",gno[i],kibo1[i],kibo2[i],kibo3[i]);

        }

        fclose(fp2);

 

        double crossover_rate = 0.8;

        double mutation_rate = 0.01;

 

        std::cout << "ルーレット選択=>1, 改良ルーレット選択=>2,ランキング選択=>3のどれ?";

        std::cin >> algorithm;

 

        //乱数の初期化

        srand( (unsigned)time(NULL) );

 

        //初期個体の生成

        for(i=0;i<NUM;i++){

                for(j=0;j<LENGTH;j++){

                        population[i][j]=rand()%NCLASS;

                }

        }

        calc_ninzu(population,ninzu);

        calc_score(ninzu_penalty1,ninzu_penalty2,population,ninzu,gno,kibo1,kibo2,kibo3,fitness);

        //population_disp2(population, fitness);

 

        for (sedai=0; sedai<500; sedai++){

                std::cout << sedai << "\n";

                for (i=0;i<4;i++){

                        juni_count[i]=0;

                }

                for (i=0;i<NCLASS;i++){

                        zemi_count[i] = 0;

                }

                //ninzuをリセット

                for (i=0;i<NUM;i++){

                        for (j=0;j<NCLASS;j++){

                                ninzu[i][j] = 0;

                        }

                }

                //交叉

                pairing(population, pair);

                one_point_crossover(crossover_rate,population,pair);

                //突然変異

                mutation(mutation_rate,population);

                calc_ninzu(population,ninzu);

                calc_score(ninzu_penalty1,ninzu_penalty2,population,ninzu,gno,kibo1,kibo2,kibo3,fitness);

                //population_disp2(population,fitness);

 

                //選択

                if (algorithm==1){

                        roulette_selection(population,fitness);

                }

                else if (algorithm == 2) {

                        roulette_selection2(population,fitness);

                }

                else{

                        ranking_selection(population, fitness);

                }

                calc_ninzu(population,ninzu);

                calc_score(ninzu_penalty1,ninzu_penalty2,population,ninzu,gno,kibo1,kibo2,kibo3,fitness);

                //population_disp(population, weight, value, fitness);

                //最良個体検出

                best_id = 0;

                best_value  =fitness[best_id];

                ave = fitness[0];

                for (i = 1; i  <NUM; i++){

                        ave = ave + fitness[i];

                        if (fitness[i] > best_value){

                                best_id = i;

                                best_value = fitness[i];

                        }

                }

                fprintf(fp,"%d,%d,%d,",sedai,best_id,best_value);

                for (i=0; i<LENGTH;i++){

                        fprintf(fp,"%d",population[best_id][i]);

                }

                fprintf(fp,",%lf\n",ave/(double)NUM);

        }

 

 

 

 

        1215日課題の箇所はここ。ここだけをdai13kaime.txtにしてメール送付)

 

・値population[best_id][j] に対して、希望順位(13, それ以外)。

juni[j]=1,2,3,0となるようにする

・同じく個体best_idに対して、希望順位13が実現出来ている人数

juni_count[0], juni_count[1],…,juni_count[3]

・同じく個体best_idに対して、研究室ごとの人数

zemi_count[0]zemi_count[9]

 

 

 

 

fclose(fp);

return 0;

 

}

 

void calc_ninzu(int population[][LENGTH],int ninzu[][NCLASS]){

 

(ここは非公開。1215日は出さなくてよい)

 

 

}

 

void calc_score(int ninzu_panalty1,int ninzu_panalty2, int population[][LENGTH], int ninzu[][NCLASS],int gno[],int kibo1[],int kibo2[],int kibo3[],int fitness[]){

        int i, individual;

 

 

 

 

(ここは非公開。1215日は出さなくてよい)

 

 

 

 

 

 

}

void calc_fitness(int population[][LENGTH], int weight[], int value[], int fitness[], int a[], int b[], int capacity){

        int i,j;

 

        for (i=0; i<NUM; i++){ //個体毎

                weight[i] = 0;

                value[i] = 0;

                for(j=0; j<LENGTH; j++){ //品物毎

                        weight[i] += population[i][j] * b[j];

                        value[i] += population[i][j] * a[j];

                }

        }

        for (i=0; i<NUM; i++){

                if (weight[i] > capacity){

                        fitness[i] = value[i] - (weight[i] - capacity);

                }

                else{

                        fitness[i] = value[i];

                }

        }

}

void pairing(int population[][LENGTH], int pair[][LENGTH]){

        int shuffle[NUM];

        int r;

        int i,j;

        int temp;

 

        for(i=0; i<NUM; i++){

                shuffle[i]=i;

        }

 

        for(i=0;i<NUM; i++){

                r=rand() % NUM;

                temp = shuffle[r];

                shuffle[r] = shuffle[i];

                shuffle[i] = temp;

        }

 

        for(i=0; i<NUM; i++){

                for(j=0; j<LENGTH; j++){

                        pair[i][j] = population[shuffle[i]][j];

                }

        }

 

        /*

        std::cout << "[shuffle]\n";

        for (i=0; i<NUM; i++){

        for(j=0; j<LENGTH; j++){

        std::cout<< population[i][j];

        }

        std::cout << " => " << shuffle[i] << " ";

        for (j=0; j<LENGTH; j++){

        std::cout << pair[i][j];

        }

        std::cout <<"\n";

        }*/

}

void one_point_crossover(double crossover_rate,int population[][LENGTH],int pair[][LENGTH]){

        int i,j;

        int cross_point;

        //std::cout << "[交叉ポイント]\n";

        for(i=0;i<(NUM-1);i=i+2){

                if ((double)rand()/RAND_MAX<crossover_rate){

                        //交叉実行

                        cross_point=rand()%(LENGTH-1)+1;

                        //std::cout << i << "" << i+1 << "" << cross_point << std::endl;

                        for (j=0; j<cross_point;j++){

                                population[i][j]= pair[i+1][j];

                                population[i+1][j] = pair[i][j];

                        }

                        for (j=cross_point;j<LENGTH;j++){

                                population[i][j] = pair[i][j];

                                population[i+1][j] = pair[i+1][j];

                        }

                }

                else{

                        //交叉を行わず、そのままpairpopulationにコピー

                        for (j=0; j<LENGTH;j++){

                                population[i][j] = pair[i][j];

                                population[i+1][j] = pair[i+1][j];

                        }

                }

        }

        /*      std::cout << "[population]\n";

        for (i=0;i<NUM;i++){

        for (j=0; j<LENGTH;j++){

        std::cout << pair[i][j];

        }

        std::cout << ">>>";

        for (j=0; j<LENGTH;j++){

        std::cout << population[i][j];

        }

        std::cout << std::endl;

        }*/

}

void mutation(double mutation_rate,int population[][LENGTH]){

        int i,j;

        int pop_yes_no = 0;

        //std::cout << "突然変異確率 " << mutation_rate << std::endl;

        for (i=0;i<NUM;i++){

                for (j=0;j<LENGTH;j++){

                        if (mutation_rate > (double)rand() / RAND_MAX){

                                pop_yes_no++;

                                population[i][j] = rand()%NCLASS;

                                //std::cout << " " << i << "個体の第" << j << "遺伝子変化\n";

                        }

                }

        }

        /*      if (pop_yes_no==0){

        std::cout << "変化遺伝子なし\n";

        }*/

}

void population_disp2(int population[][LENGTH], int fitness[])

{

        int i, j;

        std::cout << "[適応度の表示]\n";

        for (i=0; i<NUM; i++){

                for (j=0; j<LENGTH; j++){

                        std::cout << population[i][j];

                }

 

                std::cout << " ";

                std::cout << " fitness = " << fitness[i] << "\n";

 

 

        }

}

void roulette_selection(int population[][LENGTH],int fitness[]){

        int i,j,k;

        int sum_fitness;                        //適応度の和が入る

        int new_population[NUM][LENGTH];                //選ばれた個体が入る

        double roulette[NUM];                   //選択される確率が入る

        double ac_roulette[NUM];                //ルーレットの累積値が入る

        double r;

 

        //std::cout << "ルーレット後\n";

        //適応度の和を求める

        sum_fitness = 0;

        for (i=0; i<NUM; i++){

                sum_fitness += fitness[i];

        }

 

        //ルーレットを作る

        roulette[0] = (double)fitness[0]/(double)sum_fitness;

        ac_roulette[0] = roulette[0];

        //printf("roulette[%d]=%lf ac_roulette[%d]=%lf\n",0,roulette[0],0,ac_roulette[0]);

        for (i=1; i<NUM; i++){

                roulette[i] = (double)fitness[i] / (double)sum_fitness;

                ac_roulette[i] = ac_roulette[i-1] + roulette[i];

                //printf("roulette[%d]=%lf ac_roulette[%d]=%lf\n",i,roulette[i],i,ac_roulette[i]);

        }

 

        //ルーレットを使って選択する

        for (i=0; i<NUM; i++){

                r=(double)rand() / (double)RAND_MAX;

                for (j=0; j<NUM; j++){

                        if (r<=ac_roulette[j]){

                                //printf("r=%lf, 選ばれた個体=%d, ac_roulette[%d]=%lf\n",r,j,j,ac_roulette[j]);

                                for (k=0; k<LENGTH;k++){

                                        new_population[i][k] = population[j][k];

                                }

                                break;

                        }

                }

        }

        //new populationpopulationにコピー

        for (i=0;i<NUM; i++){

                for (k=0; k<LENGTH; k++){

                        population[i][k] = new_population[i][k];

                }

        }

}

void roulette_selection2(int population[][LENGTH],int fitness[]){

        int i,j,k;

        int sum_fitness;                        //適応度の和が入る

        int new_population[NUM][LENGTH];                //選ばれた個体が入る

        double roulette[NUM];                   //選択される確率が入る

        double ac_roulette[NUM];                //ルーレットの累積値が入る

        double r;

        double fit_max, fit_min;

 

        //std::cout << "ルーレット後\n";

 

        //ここから

        //適応度の最大と最小を求める

        fit_max = fitness[0];

        fit_min = fitness[0];

        for (i=0; i<NUM; i++){

                if (fit_max < fitness[i]){

                        fit_max = fitness[i];

                }

                if (fit_min > fitness[i]){

                        fit_min = fitness[i];

                }

        }

        //適応度の再定義

        for (i=0; i<NUM; i++){

                if (fit_max != fit_min){

                        fitness[i] = (fitness[i] - fit_min) / (fit_max - fit_min)*100.0;

                }

        }

        //ここまで

 

        //適応度の和を求める

        sum_fitness = 0;

        for (i=0; i<NUM; i++){

                sum_fitness += fitness[i];

        }

 

        //ルーレットを作る

        roulette[0] = (double)fitness[0]/(double)sum_fitness;

        ac_roulette[0] = roulette[0];

        //printf("roulette[%d]=%lf ac_roulette[%d]=%lf\n",0,roulette[0],0,ac_roulette[0]);

        for (i=1; i<NUM; i++){

                roulette[i] = (double)fitness[i] / (double)sum_fitness;

                ac_roulette[i] = ac_roulette[i-1] + roulette[i];

                //printf("roulette[%d]=%lf ac_roulette[%d]=%lf\n",i,roulette[i],i,ac_roulette[i]);

        }

 

        //ルーレットを使って選択する

        for (i=0; i<NUM; i++){

                r=(double)rand() / (double)RAND_MAX;

                for (j=0; j<NUM; j++){

                        if (r<=ac_roulette[j]){

                                //printf("r=%lf, 選ばれた個体=%d, ac_roulette[%d]=%lf\n",r,j,j,ac_roulette[j]);

                                for (k=0; k<LENGTH;k++){

                                        new_population[i][k] = population[j][k];

                                }

                                break;

                        }

                }

        }

        //new populationpopulationにコピー

        for (i=0;i<NUM; i++){

                for (k=0; k<LENGTH; k++){

                        population[i][k] = new_population[i][k];

                }

        }

}

void ranking_selection(int population[][LENGTH],int fitness[]){

        int i,j,k;

        int sum_fitness;                        //適応度の和が入る

        int new_population[NUM][LENGTH];                //選ばれた個体が入る

        double roulette[NUM];                   //選択される確率が入る

        double ac_roulette[NUM];                //ルーレットの累積値が入る

        double r;

 

        int rank[NUM];

        int imax,idummy;

        double dummy,max;

 

        for (i=0; i<NUM; i++){

                rank[i] = i; //rank[i]i番目の個体の順位。初期値は,番号どおりの順位とする。

        }

 

        //選択ソート

        for (i=0; i<NUM-1; i++){

                imax=i;

                max = fitness[imax];

                for (j=i+1;j<NUM; j++){

                        if (fitness[j]>max){

                                imax = j;

                                max=fitness[imax];

                        }

                }

                idummy=rank[i];

                rank[i] = imax;

                rank[imax] = idummy;

                dummy=fitness[imax];

                fitness[imax] = fitness[i];

                fitness[i] = dummy;

        }

 

        for (i=0; i<NUM; i++){

                fitness[i] = NUM -i;

        }

 

 

        //適応度の和を求める

        sum_fitness = 0;

        for (i=0; i<NUM; i++){

                sum_fitness += fitness[i];

        }

 

        //ルーレットを作る

        roulette[0] = (double)fitness[0]/(double)sum_fitness;

        ac_roulette[0] = roulette[0];

        //printf("roulette[%d]=%lf ac_roulette[%d]=%lf\n",0,roulette[0],0,ac_roulette[0]);

        for (i=1; i<NUM; i++){

                roulette[i] = (double)fitness[i] / (double)sum_fitness;

                ac_roulette[i] = ac_roulette[i-1] + roulette[i];

                //printf("roulette[%d]=%lf ac_roulette[%d]=%lf\n",i,roulette[i],i,ac_roulette[i]);

        }

 

        //ルーレットを使って選択する

        for (i=0; i<NUM; i++){

                r=(double)rand() / (double)RAND_MAX;

                for (j=0; j<NUM; j++){

                        if (r<=ac_roulette[j]){

                                //printf("r=%lf, 選ばれた個体=%d, ac_roulette[%d]=%lf\n",r,j,j,ac_roulette[j]);

                                for (k=0; k<LENGTH;k++){

                                        new_population[i][k] = population[rank[j]][k];

                                }

                                break;

                        }

                }

        }

        //new populationpopulationにコピー

        for (i=0;i<NUM; i++){

                for (k=0; k<LENGTH; k++){

                        population[i][k] = new_population[i][k];

                }

        }

}