test_gentic.cpp

用c编写的一个基于遗传算法的工程调度的实例。

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

void exchange_gene(int *chromosome_first, int *chromosome_second, int num_of_job);
void reverse_gene(int *chromosome, int num_of_job);
void gene_variation(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 data's 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_variation = 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_variation,
			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_variation(int *chromosome, int num_of_job)
{
	int variation_pos;                 // 变异点
	int variation_value;               // 变异后基因值
	int ex_pos;                            // 与变异点的交换点
	int i;

	variation_pos = rand() % num_of_job;
	variation_value = rand() % num_of_job + 1;

	for (i=0; i<num_of_job; ++i)
	{
		if (chromosome[i] == variation_value)
		{
			ex_pos = i;
			break;
		}
	}

	i = chromosome[ex_pos];
	chromosome[ex_pos] = chromosome[variation_pos];
	chromosome[variation_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_variation(colony[i], num_of_job);
			gene_variation(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);
}