|
#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 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_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);
}
| 
本类阅读TOP10