ga.txt

遗传算法的一个实例。m个工件分配给m架机床的效益最优化问题

#include <iostream>

#include <fstream>

#include <algorithm>

#include <numeric>

#include <stdlib.h>

#include <time.h>

#include <math.h>

using namespace std;

 

void generate_colony(int **colony, int num_of_chromosomes, int num_of_job); //初始群体产生 

int compute_benefit(int **benefit_matrix, int *chromosome, int num_of_machine); // 对单个染色体的效益评估 

void copy_chromosomes(int **colony, int num_of_chromosomes, int num_of_job, int *benefit_array);//复制

int execute_probably(float probability); //按一定概率返回1或0

//上面的函数实现中使用rand产生随机数，这是不严格的，应该采用一个均匀(Uniform)分布的随机数生成器

 

void exchange_gene(int *chromosome_first, int *chromosome_second, int num_of_job); //对两个染色体实行交换

void reverse_gene(int *chromosome, int num_of_job); //对单个染色体实行到位

void gene_mutate(int *chromosome, int num_of_job); //对单个染色体实行变异

 

void ERV_colony(int **colony, float pe, float pr, float pv, int num_of_job, int num_of_chromosomes);

//对群体按概率实行交换，到位和变异 

 

int main()

{

    int **benefit_matrix = NULL;        // 效益矩阵

    int num_of_job;             // 工件数

    int num_of_machine;       // 机床数

 

    ifstream inputTM("numoftm.txt");

    inputTM >> num_of_job >> num_of_machine;

    inputTM.close();

 

    benefit_matrix = (int**)malloc(sizeof(int*)*num_of_job);

    for (int i=0; i<num_of_job; ++i)

    {

        benefit_matrix[i] = (int*)malloc(sizeof(int)*num_of_machine);

    }

 

    ifstream inputBenefit("benefit.txt");

    for (int i=0; i<num_of_job; ++i)

    {

        for (int j=0; j<num_of_machine; ++j)

        {

            inputBenefit >> benefit_matrix[i][j];

        }

    }

    inputBenefit.close();

 

    /*********************************************

    // Test for inital datas input

    cout <<num_of_job << \t << num_of_machine << endl;

    for (int i=0; i<num_of_job; ++i)

    {

        for (int j=0; j<num_of_machine; ++j)

        {

            cout <<  benefit_matrix[i][j] << \t;

        }

        cout << \n;

    }

    **********************************************/

 

    int num_of_chromosomes;   //群体数

    ifstream inputCln("numofcolony.txt");

    inputCln >> num_of_chromosomes;

    inputCln.close();

 

    int **colony = NULL;   //群体    

    colony = (int**)malloc(sizeof(int*)*num_of_chromosomes);

    for (int i=0; i<num_of_chromosomes; ++i)

    {

        colony[i] =(int*)malloc(sizeof(int)*num_of_job);

    }

 

    srand(time(0));

    generate_colony(colony, num_of_chromosomes, num_of_job);

 

    cout << "Origin Colonies" << \n;

    /***********************************/

    // Test for genetare_colony

    for (int i=0; i<num_of_chromosomes; ++i)

    {

        for (int j=0; j<num_of_job; ++j)

        {

            cout << colony[i][j] << \t;

        }

 

        cout << \n;

    }

    /************************************/

 

    int *benefit_array = NULL;   // 群体中每个个体的效益组成的数组

    benefit_array = (int*)malloc(sizeof(int)*num_of_chromosomes);

    for (int i=0; i<num_of_chromosomes; ++i)

    {

        benefit_array[i] = compute_benefit(benefit_matrix, colony[i], num_of_machine);

    }

    

    cout << "Current benefit" << \n

        << "mean:" << (float)accumulate(benefit_array, benefit_array+num_of_chromosomes, 0) / num_of_chromosomes << \t

        << "max:" << *max_element(benefit_array, benefit_array+num_of_chromosomes) << \t

        << "min:" << *min_element(benefit_array, benefit_array+num_of_chromosomes) << \n;

   

    int num_of_gen;  // 产生的代数，也就是最后产生的那个代的序数 

         ifstream inputNG("num_of_gen.txt");

         inputNG >> num_of_gen;

         inputNG.close();

 

    float probability_of_exchange = 0.7f;

    float probability_of_reverse = 0.2f;

    float probability_of_mutate = 0.01f;

 

    for (int i=0; i<num_of_gen; ++i)

    {

        //调用复制子程序

        copy_chromosomes(colony, num_of_chromosomes, num_of_job, benefit_array);

 

                   ERV_colony(colony, probability_of_exchange, probability_of_reverse, probability_of_mutate,

                            num_of_job, num_of_chromosomes);

 

        //重新计算各个个体的效益

        for (int j=0; j<num_of_chromosomes; ++j)

        {

            benefit_array[j] = compute_benefit(benefit_matrix, colony[j], num_of_machine);

        }

 

        //本代评估效益

        cout << "current gen : " << i+1 << \n

            << "mean: " << (float)accumulate(benefit_array, benefit_array+num_of_chromosomes, 0) / num_of_chromosomes << \t

                            << "max:" << *max_element(benefit_array, benefit_array+num_of_chromosomes) << \t

            << "min:" << *min_element(benefit_array, benefit_array+num_of_chromosomes) << \n;

    }

 

         cout << "Laster Colony" << \n;

         for (int i=0; i<num_of_chromosomes; ++i)

         {

                   for (int j=0; j<num_of_job; ++j)

                   {

                            cout << colony[i][j] << \t;

                   }

 

                   cout << \n;

         }

                   

    // free all resource

    for (int i=0; i<num_of_job; ++i)

    {

        free(benefit_matrix[i]);

    }

    free(benefit_matrix);

    

    for (int i=0; i<num_of_chromosomes; ++i)

    {

        free(colony[i]);

    }

    free(colony);

 

    free(benefit_array);

 

         system("pause");

}

 

void generate_colony(int **colony, int num_of_chromosomes, int num_of_job)

{

    int *initial_array = (int*)malloc(sizeof(int)*num_of_job);

    for (int i=0; i<num_of_job; ++i)

    {

        initial_array[i] = i + 1;

    }

 

    for (int i=0; i<num_of_chromosomes; ++i)

    {

        random_shuffle(initial_array, initial_array+num_of_job);

        copy(initial_array, initial_array+num_of_job, colony[i]);

    }

 

    free(initial_array);

}

 

int compute_benefit(int **benefit_matrix, int *chromosome, int num_of_machine)

{

    int benefit = 0;

    for (int i=0; i<num_of_machine; ++i)

    {

        benefit += benefit_matrix[chromosome[i]-1][i];

    }

 

    return benefit;

}

 

void copy_chromosomes(int **colony, int num_of_chromosomes, int num_of_job, int *benefit_array)

{

    int i, j;

    int *next_gen_reserve;   //各个个体在后代中的复制量

    int hasCopyed = 0;  // 防止复制数超过群体总数??

    int **temp_colony;   //暂存群体

         float mean, max_benefit, min_benefit;

         float big_separator, small_separator;

 

         mean = (float)accumulate(benefit_array, benefit_array+num_of_chromosomes, 0) / (float)num_of_chromosomes;

         max_benefit = *max_element(benefit_array, benefit_array+num_of_chromosomes);

         min_benefit = *min_element(benefit_array, benefit_array+num_of_chromosomes);

         big_separator = max_benefit - (max_benefit-mean) / 2;

         small_separator = min_benefit + (mean-min_benefit) / 2;

 

    temp_colony = (int**)malloc(sizeof(int*)*num_of_chromosomes);

    for (i=0; i<num_of_chromosomes; ++i)

    {

        temp_colony[i] =(int*)malloc(sizeof(int)*num_of_job);

    }

 

    // 复制暂存群体

    for (i=0; i<num_of_chromosomes; ++i)

    {

        for (j=0; j<num_of_job; ++j)

        {

            temp_colony[i][j] = colony[i][j];

        }

    }

 

    next_gen_reserve = (int*)malloc(sizeof(int)*num_of_chromosomes);

 

    // 计算个体贡献并进行参数圆整

    for (i=0; i<num_of_chromosomes; ++i)

    { 

                   if (benefit_array[i] >= big_separator)

            next_gen_reserve[i] = 0;

                   else if (benefit_array[i] <= small_separator)

                            next_gen_reserve[i] = 2;

                   else

                            next_gen_reserve[i] = 1;

    }

 

    for (i=0; i<num_of_chromosomes; ++i)

    {

        for (j=0; j<next_gen_reserve[i]; ++j)

        {

            if (hasCopyed >= num_of_chromosomes)

            {

                i = num_of_chromosomes;

                break;

            }

            memcpy(colony[hasCopyed], temp_colony[i], sizeof(colony[0][0])*num_of_job);

            ++hasCopyed;

        }

    }

 

    for (i=0; i<num_of_chromosomes; ++i)

    {

        free(temp_colony[i]);

    }

    free(temp_colony);

    free(next_gen_reserve);

}

 

int execute_probably(float probability)

{

    if (probability > 1.0)

        return 1;

    else if (probability <= 0.0)

        return 0;

    else

    {

        int rndNum = rand() % 1000;

 

        if (rndNum < (int)(probability * 1000.0))

            return 1;

        else

            return 0;

    }

}

 

void exchange_gene(int *chromosome_first, int *chromosome_second, int num_of_job)

{

         int exchange_pos;     //交换随机点

    int *derived_first, *derived_second;  //交换后的两个新子代的临时存放

         int i, j, k;

         int is_equal;

 

         exchange_pos = rand() % num_of_job;

 

         derived_first = (int*)malloc(sizeof(int)*num_of_job);

         derived_second = (int*)malloc(sizeof(int)*num_of_job);

 

         // 复制交换点前的基因

         memcpy(derived_first, chromosome_first, sizeof(int)*(1+exchange_pos));

         memcpy(derived_second, chromosome_second, sizeof(int)*(1+exchange_pos));

 

         // 由两个亲本产生第一个子代

         k = exchange_pos + 1;

         for (i=0; i<num_of_job; ++i)

         {

             is_equal = 0;

                   

                   for (j=0; j<=exchange_pos; ++j)

                   {

                            if (chromosome_second[i]==chromosome_first[j])

                            {

                                     is_equal = 1;

                                     break;

                            }

                   }

                   

                   if (is_equal == 0)

        {

            derived_first[k] = chromosome_second[i];

                       ++k;

                   }

         }

         

 

         // 由两个亲本产生第二个子代

         k = exchange_pos + 1;

         for (i=0; i<num_of_job; ++i)

         {

             is_equal = 0;

                   

                   for (j=0; j<=exchange_pos; ++j)

                   {

                            if (chromosome_first[i]==chromosome_second[j])

                            {

                                     is_equal = 1;

                                     break;

                            }

                   }

                   

                   if (is_equal == 0)

                   {

                       derived_second[k] = chromosome_first[i];

                       ++k;

        }

         }

 

         // 覆盖原始亲本

         memcpy(chromosome_first, derived_first, sizeof(int)*num_of_job);

         memcpy(chromosome_second, derived_second, sizeof(int)*num_of_job);

 

         free(derived_first);

         free(derived_second);

}

 

void reverse_gene(int *chromosome, int num_of_job)

{

         int first_rev_pos;                      //第一倒位点

         int second_rev_pos;                  //第二倒位点

         int i, distance;

         int temp;

 

         first_rev_pos = rand() % num_of_job;

         second_rev_pos = rand() % (num_of_job-first_rev_pos)+first_rev_pos;

 

         distance = (second_rev_pos - first_rev_pos) / 2;

         for (i=0; i<=distance; ++i)

         {

                   temp = chromosome[first_rev_pos+i];

                   chromosome[first_rev_pos+i] = chromosome[second_rev_pos-i];

                   chromosome[second_rev_pos-i] = temp;

         }

}

 

void gene_mutate(int *chromosome, int num_of_job)

{

         int mutate_pos;                 // 变异点

         int mutate_value;               // 变异后基因值

         int ex_pos;                            //与变异点的交换点

         int i;

 

         mutate_pos = rand() % num_of_job;

         mutate_value = rand() % num_of_job + 1;

 

         for (i=0; i<num_of_job; ++i)

         {

                   if (chromosome[i] == mutate_value)

                   {

                            ex_pos = i;

                            break;

                   }

         }

 

         i = chromosome[ex_pos];

         chromosome[ex_pos] = chromosome[mutate_pos];

         chromosome[mutate_pos] = i;

}

 

void ERV_colony(int **colony, float pe, float pr, float pv, int num_of_job, int num_of_chromosomes)

{

         int **tmp_colony;

         int i;

         int first, second;

 

         tmp_colony = (int**)malloc(sizeof(int*)*num_of_chromosomes);

    for (i=0; i<num_of_chromosomes; ++i)

    {

        tmp_colony[i] =(int*)malloc(sizeof(int)*num_of_job);

    }

 

         // copy

         for (i=0; i<num_of_chromosomes; ++i)

         {

                   memcpy(tmp_colony[i], colony[i], sizeof(int)*num_of_job);

         }

 

         for (i=0; i<num_of_chromosomes; i+=2)

         {

        first = rand() % num_of_chromosomes;

             while (1)

             {

                       second = rand() % num_of_chromosomes;

                       if (first != second)

                                break;

             }

 

                   memcpy(colony[i], tmp_colony[first], sizeof(int)*num_of_job);

                   memcpy(colony[i+1], tmp_colony[second], sizeof(int)*num_of_job);

 

                   if (execute_probably(pe))

                            exchange_gene(colony[i],colony[i+1],num_of_job);

 

                   if (execute_probably(pr))

                   {

                            reverse_gene(colony[i], num_of_job);

                            reverse_gene(colony[i+1], num_of_job);

                   }

 

                   if (execute_probably(pv))

                   {

                            gene_mutate(colony[i], num_of_job);

                            gene_mutate(colony[i+1], num_of_job);

                   }

         }

 

         // free all resource

         for (int i=0; i<num_of_chromosomes; ++i)

    {

        free(tmp_colony[i]);

    }

    free(tmp_colony);

}