遗传算法的一个例子(C/C++)

遗传算法的一个例子(C/C++)

作者:newsuppy

摘要: m个工件分配给m架机床的效益最优化问题，使用一种遗传算法解决。

一，已知效益矩阵E

eij

M1

M2

M3

M4

M5

J1

5

6

4

8

3

J2

6

4

9

8

5

J3

4

3

2

5

4

J4

7

2

4

5

3

J5

3

6

4

5

5

Jn为工件，Mn为机床，矩阵对应的一格即为，某工件分配给某机床的效益。效益指花费的时间，金钱等，数值越大越差。产生一个分配序列C=(5,2,3,4,1)指将5号工件分配给1号机床，2号工件分配给2号机床，以此类推求得当前分配对应的效益为3+4+2+5+3=17。最佳化问题就是要求该效益值最小时对应的分配序列。下面采用一种遗传算法，具体算法这里不再复述，可以参考[1]或其他相关书籍。要注意由于工件与机床是一一对应的，算法与一些常见的遗传算法在某些细节上有所不同，如染色体编码，到位，变异。

下面是算法实现，由于某些原因，不得不采用C/C++混合编码，C++代码主要在文件输入输出部分。另外要让程序正常运行需要包括几个支持文件(与程序在同一路径):

benefit.txt输入效益矩阵

num_of_gen.txt最后产生的代序

numofcolony.txt为群体中个体总数

numoftm.txt为工件数与机床数

内容可以如下:

benefit.txt

5 6 4 8 3

6 4 9 8 5

4 3 2 5 4

7 2 4 5 3

3 6 4 5 5

num_of_gen.txt

50

numofcolony.txt

10

numoftm.txt

5

5

注意:由于程序写得比较仓促，未考虑错误处理，请保证相关文件的正确性。

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

}

下面是程序编译运行后的一种结果（已经在VC7.1,Dev-C++4.9.8.0上编译测试过）。输出为初始群体，0至第50代的平均效益(mean)

最差效益(max),最佳效益(min)。最后是最后一代群体的分配情况。

由于初始序列随机产生，且一般遗传算法往往存在难于收敛到最佳解的情况，本程序有时候也会无法收敛到最佳解。但是只要多运行几次，就可以获得最佳解序列。

最佳分配序列:5 2 3 4 1， 此时效益为17

Origin Colonies

5 3 2 4 1

5 2 1 4 3

2 5 4 1 3

2 3 5 4 1

1 2 4 5 3

1 3 2 4 5

5 4 3 2 1

3 1 4 2 5

5 3 4 1 2

5 1 3 4 2

Current benefit

mean:23 max:28 min:18

current gen : 1

mean: 21.8 max:29 min:18

current gen : 2

mean: 19.7 max:23 min:18

current gen : 3

mean: 19.8 max:24 min:17

current gen : 4

mean: 18.4 max:21 min:17

current gen : 5

mean: 18.2 max:21 min:17

current gen : 6

mean: 17.4 max:18 min:17

current gen : 7

mean: 17.8 max:22 min:17

current gen : 8

mean: 17.2 max:18 min:17

current gen : 9

mean: 17 max:17 min:17

current gen : 10

mean: 17.3 max:20 min:17

current gen : 11

mean: 17 max:17 min:17

current gen : 12

mean: 17.3 max:20 min:17

current gen : 13

mean: 18.8 max:27 min:17

current gen : 14

mean: 17.6 max:23 min:17

current gen : 15

mean: 17.5 max:20 min:17

current gen : 16

mean: 18.2 max:23 min:17

current gen : 17

mean: 17.5 max:22 min:17

current gen : 18

mean: 17 max:17 min:17

current gen : 19

mean: 17 max:17 min:17

current gen : 20

mean: 17.5 max:22 min:17

current gen : 21

mean: 17.6 max:20 min:17

current gen : 22

mean: 17 max:17 min:17

current gen : 23

mean: 17.8 max:22 min:17

current gen : 24

mean: 17.6 max:23 min:17

current gen : 25

mean: 17.5 max:22 min:17

current gen : 26

mean: 17 max:17 min:17

current gen : 27

mean: 17 max:17 min:17

current gen : 28

mean: 17 max:17 min:17

current gen : 29

mean: 17 max:17 min:17

current gen : 30

mean: 18.1 max:22 min:17

current gen : 31

mean: 17.8 max:20 min:17

current gen : 32

mean: 17 max:17 min:17

current gen : 33

mean: 17.6 max:23 min:17

current gen : 34

mean: 17.3 max:20 min:17

current gen : 35

mean: 17 max:17 min:17

current gen : 36

mean: 17 max:17 min:17

current gen : 37

mean: 17 max:17 min:17

current gen : 38

mean: 17 max:17 min:17

current gen : 39

mean: 18.1 max:23 min:17

current gen : 40

mean: 17.3 max:20 min:17

current gen : 41

mean: 17 max:17 min:17

current gen : 42

mean: 17 max:17 min:17

current gen : 43

mean: 17 max:17 min:17

current gen : 44

mean: 17.5 max:22 min:17

current gen : 45

mean: 17 max:17 min:17

current gen : 46

mean: 18.3 max:27 min:17

current gen : 47

mean: 17.9 max:20 min:17

current gen : 48

mean: 17 max:17 min:17

current gen : 49

mean: 17 max:17 min:17

current gen : 50

mean: 17 max:17 min:17

Laster Colony

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

5 2 3 4 1

参考文献:

[1] 计算机集成制造系统 主编 严新民 西北工业大学出版社 p110-p114

• ·学习笔记《.NET框架程序设计（修订版）》－－
• ·Volume Rendering
• ·得到windows系统图标的解决方案
• ·HOWTO: CVS with VS.NET
• ·upload file into databa
• ·深入 CSocket 编程之阻塞和非阻塞模式
• ·无刷新显示即时更新数据两例
• ·T-SQL: 15 个与日期时间相关的自定义函
• ·Protected-Mode Memory M
• ·Linux 核心（The Linux Kern