遗传算法的并行实现
遗传算法的并行实现
章衡 2007310437
一、 问题描述
遗传算法是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。
遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如TSP 。因时间有些紧张，请老师原谅），考虑的具有问题是：对给定的正整数n 、n 元函数f ，以及定义域D ，求函数f 在D 内的最大值。 二、 串行遗传算法 1． 染色体与适应度函数
对函数优化问题，一个潜在的解就是定义域D 中的一个点011(,,...,)n x x x -，因此，我
们只需用一个长度为n 的实数数组来表示一个个体的染色体。由于问题中要求求函数f 的最大值，我们可以以个体所代表点011(,,...,)n x x x -在f 函数下的值来判断该个体的好坏。因此，我们直接用函数f 作为个体的适应度函数。 2． 选择机制
选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中
适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。
我们定义P 为当前种群内所有个体的集合，(0)(1)(1),,...,n x x x -为P 中所有个体的一个固定排列。若x P ∈为某一个体，()f x 表示该个体的适应度，则种群P 的适应度定义为：
1
()
0()()n i i s P f x
-==
∑
对任意个体x P ∈，x 的相对适应度定义为()()/()r x f x s P =。累积适应度定义为
()
()
()()k
k i i c x r x
==
∑
进行选择之前，先产生一个0到1之间的随机实数t ，若满足1()()k k r x t r x +≤<，则
第k+1个个体被选中。循环以上过程，即得到生成下一代种群的母体。
具体实现见如下函数：
void pop_select(void ) { int mem, i, j, k; double sum = 0; double p; /* 计算种群适应度之和 */ for (mem = 0; mem < POPSIZE; mem++) { sum += (population[mem].fitness - lower_fitness); } /* 计算相应适应度 */ for (mem = 0; mem < POPSIZE; mem++) { population[mem].rfitness = (population[mem].fitness - lower_fitness)/sum; } population[0].cfitness = population[0].rfitness; /* 计算累积适应度 */ for (mem = 1; mem < POPSIZE; mem++) { population[mem].cfitness = population[mem-1].cfitness + population[mem].rfitness; } /* 按照累积适应度概率选取母体种群 */ for (i = 0; i < POPSIZE; i++) { p = rand()%1000/1000.0; if (p < population[0].cfitness) newpopulation[i] = population[0]; else { for (j = 0; j < POPSIZE;j++) if (p >= population[j].cfitness && p < population[j+1].cfitness) newpopulation[i] = population[j+1]; } } for (i = 0; i < POPSIZE; i++) population[i] = newpopulation[i]; }
3． 杂交算子
杂交算子的流程一般如下：
（1） 按杂交概率选择一对参与进化的个体；
（2）随机确定一个截断点；
（3）将两个个体的染色体从截断点处截断，并交换，从而得到新的染色体。
具体算法见如下函数：
void crossover(void)
{
int i, j, k, m, point;
int first = 0;
double x;
for (k = 0; k < POPSIZE; k++) {
x = rand()%1000/1000.0;
if (x < PXOVER)
{
first++;
if (first % 2 == 0) {
if (NVARS == 2) point = 1;
else point = (rand() % (NVARS - 1)) + 1;
for (j = 0; j < point; j++)
swap(&population[m].gene[j], &population[k].gene[j]);
}
else m = k;
}
}
}
4．变异
变异操作的实现相当简单，只需遍历各染色体的各个单元，按某一变异概率将该单元变成一个随机的合法值。具体操作如下函数所示：
void mutate(void)
{
int i, j;
double lbound, hbound;
double x;
for (i = 0; i < POPSIZE; i++)
for (j = 0; j < NVARS; j++) {
x = rand()%1000/1000.0;
if (x < PMUTATION) {
population[i].gene[j] = randval(lower[j], upper[j]);
}
}
}
串行遗传算法的主要流程如图1所示。在每一次进化过程中，总是找出种群中的最优解与最差解，并将最优解保存，将本次最差解用上次保存的最优解替换，这样保证了各次进化的最优解的适应度不会降低，从而增快收敛的速度。
图1 串行遗传算法基本流程
三、算法设计
分析图1中的串行算法，容易看出，在选择函数中，计算相对适应度需要用到全局种群的适应度之和，计算个体x k+1的累积适应度依赖于x k的累积适应度，如果在并行算法中要原封不动地模拟串行算法的运算，这些数据依赖关系都将产生通讯。更为不幸的是，选择后的个体需在各进程中作大量数据迁移。杂交算子中，一次杂交需要用到母体中的两个个体，若在这两个个体分配在不同进程，则需要进行一次通讯。此后的变异和评估都可以非常容易的实现并行，并且完全不需要任何通讯。但最后一步求最优个体和最差个体需要对各进程进行归约。由这些分析可以看出，完全地模拟串行情形将使算法变得相当低效。
幸运地是，遗传算法本身是一个概率算法，我们完全可以对串行算法作些必要的改变。如图2所示，我们将整个种群分成p个子种群，每一子种群由一个单一的进程负责。各进程独立地完成串行遗传算法的整个过程，唯一不同的是选择函数。各进程作选择操作时，首先计算各子种群内的局部累积适应度，然后根据局部累积适应度选择若干（本算法实现中使用的时常数3，也可以设为子种群大小的一个函数）个体按一固定规则轮流发送到其他进程；同时，按照该规则相应地从其他进程获取若干用来进行交流的个体。获取到个体后，先将其
暂存；然后按串行算法中的选择机制从原子种群中选择进行进化的母体；最后再用之前暂存的个体完成进程间的种群交流。对每一个待交流的个体，具体策略如下：
（1）随机地从本地的待进化母体种群内抽取与之进行交流的母体；
（2）比较本地个体与传送过来的待交流个体，选取适应度高者作为最终母体。
各进程在每一次进化过程中，均分别保留各自的局部最优解，用来在下一次进化中替换局部最差的个体。各进程均完成所预定的进化迭代后，最后对各进程的局部最优解进行归约，从而得到整个算法的全局最优解。算法的主要流程详见图2。
图2 并行遗传算法基本流程
四、算法实现
该算法实现的最关键部分为选择中的种群交流，该功能有如下函数实现
void pop_select(void)
{
MPI_Status status;
MPI_Request handle;
int mem, i, j, k;
double sum = 0;
double p;
static struct genotype ex_member[EX_NUM];
/* 计算子种群的总适应度 */
for (mem = 0; mem < TASK_NUM(pid); mem++) {
sum += (population[mem].fitness - lower_fitness);
}
/* 计算各个体相应适应度 */
for (mem = 0; mem < TASK_NUM(pid); mem++) {
population[mem].rfitness = (population[mem].fitness - lower_fitness)/sum;
}
population[0].cfitness = population[0].rfitness;
/* 计算各个体累积适应度 */
for (mem = 1; mem < TASK_NUM(pid); mem++) {
population[mem].cfitness = population[mem-1].cfitness + population[mem].rfitness;
}
/* 按照累积适应度概率选取种群交流个体，并发送和接收 */
for (i = 1; i <= EX_NUM; i++) {
p = rand()%1000/1000.0;
if (p < population[0].cfitness) {
MPI_Isend(&population[0], sizeof(struct genotype)/sizeof(char),
MPI_CHAR, (pid+i*generation)%pnum, 0, MPI_COMM_WORLD, &handle);
}
else {
for (j = 0; j < TASK_NUM(pid);j++)
if (p >= population[j].cfitness && p < population[j+1].cfitness) {
MPI_Isend(&population[j+1], sizeof(struct genotype)/sizeof(char),
MPI_CHAR, (pid+i*generation)%pnum, 0, MPI_COMM_WORLD, &handle);
break;
}
}
MPI_Recv (&ex_member[i-1], sizeof(struct genotype)/sizeof(char), MPI_CHAR,
(pid+(pnum-i)*generation)%pnum, 0, MPI_COMM_WORLD, &status);
}
/* 按照累积适应度概率选取母体种群 */
for (i = 0; i < TASK_NUM(pid); i++)
{
p = rand()%1000/1000.0;
if (p < population[0].cfitness)
newpopulation[i] = population[0];
else {
for (j = 0; j < TASK_NUM(pid); j++)
if (p >= population[j].cfitness &&
p < population[j+1].cfitness)
newpopulation[i] = population[j+1];
}
}
for (i = 0; i < TASK_NUM(pid); i++)
population[i] = newpopulation[i];
/* 按优胜劣汰的原则完成种群交流 */
for (i = 0; i < EX_NUM; i++) {
j = rand()%TASK_NUM(pid);
if (population[j].fitness < ex_member[i].fitness) {
for (k = 0; k < NVARS; k++) {
population[j].gene[k] = ex_member[i].gene[k];
}
population[j].rfitness = 0;
population[j].cfitness = 0;
population[j].fitness = ex_member[i].fitness;
}
}
}
另外，全局最优解的归约由如下代码实现：
MPI_Op_create((MPI_User_function *)gene_max, 1, &my_op);
MPI_Reduce( local_best_individual, best_individual, NVARS+1,
MPI_DOUBLE, my_op, pnum-1, MPI_COMM_WORLD );
其中，具体的归约操作由如下函数实现：
void gene_max(double *in, double *inout, int *len, MPI_Datatype *dptr) { int i; if (inout[0] < in[0]) { /* 比较适应度 */ for (i=0; i < *len; ++i) { inout[i] = in[i]; /* 复制适应度较高的个体 */ } } }
五、 算法分析与实验结果
下面的实验结果是在166.111.143.24上利用结点cn115和cn116获得的。用来计算最大值的函数为
625123456112346356
2
22223
2456135
23561245
(,,,,,)f x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x =-+--++
其定义域如文件ga_data.txt 中所示，总种群大小为500，最大进化次数为2000。
表1 实验结果
表1中最为有趣的现象是，当进程数小于5时，该算法的加速比似乎与进程数p存在一个平方关系，也就是说，存在一个超线性加速的关系。进程数大于等于5时，这种超线性加速实际也应该存在，只是由于节点数的限制，被进程管理的开销所限制。下面我们通过估计时间复杂性来分析造成这种超线性加速的原因。
如果将对染色体中每一变元上的一个计算看作一个基本计算，并设变元数为k，总种群中个体数为n，进程数则对每一进程，分析容易得到：pop_select函数最坏情形的时间复杂性为O((kn/p)2)，crossover函数最坏情形的时间复杂性为O(kn/p)，mutate函数最坏情形的时间复杂性为O(kn/p)，评估函数最坏情形的时间复杂性为O(kn/p)，elitist函数最坏情形的时间复杂性为O(n/p+k)。此外，按照算法的设计，在选择过程中的通讯所耗费的时间为O(kn/p)。综合可知，一次进化的时间复杂性为O((kn/p)2)。因此，所有进程总的计算时间醉最坏情形的渐近上界为O((kn)2/p)。而串行遗传算法一次进化的时间复杂性为O((kn)2)，这就解释了为什么p小于5的情形会具有超线性加速。当然，这并不能说明并行计算真能产生超线性加速比，因为我们可以非常有效地用一个进程来模拟p个进程的计算，也就是说在串行的情形下也能达到这样的加速。真正值得研究的问题是分析上述建立并行遗传算法的收敛速度与串行遗传算法的收敛速度之间的关系。不过从表1可以看出，进程增加时，解得质量并没有任何降低。因为时间的限制，不能在这里进行进一步的理论分析，请老师谅解。
六、源程序清单
#include"mpi.h"
#include
#include
#include
#define POPSIZE 500
#define NVARS 6
#define MAXGENS 2000
#define PXOVER 0.8 /* 杂交概率*/
#define PMUTATION 0.15 /* 变异概率*/
#define TASK_NUM(i) ((POPSIZE+pnum-1)/pnum)
#define EX_NUM 3
struct genotype
{
double gene[NVARS];
double fitness; /* 适应度*/
double rfitness; /* 相对适应度*/
double cfitness; /* 累积适应度*/
} *population, *newpopulation;
double upperbound[NVARS];
double local_best_individual[NVARS+1]; /* 局部最优解*/
double best_individual[NVARS+1]; /* 全局最优解*/
int generation;
double lower_fitness;
FILE *galog;
int pid, pnum;
double randval(double low, double high)
{
double val;
val = ((double)(rand()%1000)/1000.0)*(high - low) + low;
return val;
}
void initialize(void)
{
FILE *infile;
int i, j, r;
double lbound, ubound;
MPI_Status status;
population = malloc(sizeof(struct genotype)*(TASK_NUM(pid)+1));
newpopulation = malloc(sizeof(struct genotype)*(TASK_NUM(pid)+1));
if (pid == pnum - 1) {
if ((infile = fopen("ga_data.txt","r"))==NULL)
{
fprintf(galog,"\nCannot open input file!\n");
exit(1);
}
srand(time(0));
for (i=0; i r = rand(); MPI_Send(&r, 1, MPI_INT, i, 1, MPI_COMM_WORLD); } for (i = 0; i < NVARS; i++) { fscanf(infile, "%lf",&lowerbound[i]); fscanf(infile, "%lf",&upperbound[i]); } } else { MPI_Recv(&r, 1, MPI_INT, pnum-1, 1, MPI_COMM_WORLD, &status); srand(r); } MPI_Bcast(lowerbound, NVARS, MPI_DOUBLE, pnum-1, MPI_COMM_WORLD); MPI_Bcast(upperbound, NVARS, MPI_DOUBLE, pnum-1, MPI_COMM_WORLD); for (j = 0; j < TASK_NUM(pid); j++) { population[j].fitness = 0; population[j].rfitness = 0; population[j].cfitness = 0; //printf("\nGene of member %d in %d is:\n", j, pid); for (i = 0; i < NVARS; i++) { population[j].gene[i] = randval(lowerbound[i], upperbound[i]); //printf(" %lf ", population[j].gene[i]); } } if (pid == pnum - 1) fclose(infile); } void evaluate(void) { int mem; int i; double x[NVARS+1]; lower_fitness = 0.0; for (mem = 0; mem < TASK_NUM(pid); mem++) { for (i = 0; i < NVARS; i++) x[i+1] = population[mem].gene[i]; population[mem].fitness = (x[1]*x[1]*x[1]*x[1]*x[1]*x[1]) - (x[1]*x[2]*x[3]*x[4]*x[4]*x[6]) + (x[3]*x[3]*x[3]*x[3]*x[3]*x[5]*x[6]) - (x[2]*x[4]*x[5]*x[5]*x[6]) - (x[1]*x[1]*x[3]*x[3]*x[5]*x[5]) + (x[2]*x[2]*x[3]*x[5]*x[6]) + (x[1]*x[2]*x[4]*x[4]*x[4]*x[5]); if(population[mem].fitness < lower_fitness) lower_fitness = population[mem].fitness; } } void keep_the_best() { int mem, i, cur_best = 0; for (mem = 0; mem < TASK_NUM(pid); mem++) { if (population[mem].fitness > population[TASK_NUM(pid)].fitness) { cur_best = mem; population[TASK_NUM(pid)].fitness = population[mem].fitness; } } for (i = 0; i < NVARS; i++) { population[TASK_NUM(pid)].gene[i] = population[cur_best].gene[i]; local_best_individual[i+1] = population[cur_best].gene[i]; } local_best_individual[0] = population[cur_best].fitness; } void pop_select(void) { MPI_Status status; MPI_Request handle; int mem, i, j, k; double sum = 0; double p; static struct genotype ex_member[EX_NUM]; for (mem = 0; mem < TASK_NUM(pid); mem++) { sum += (population[mem].fitness - lower_fitness); } for (mem = 0; mem < TASK_NUM(pid); mem++) { population[mem].rfitness = (population[mem].fitness - lower_fitness)/sum; } population[0].cfitness = population[0].rfitness; for (mem = 1; mem < TASK_NUM(pid); mem++) { population[mem].cfitness = population[mem-1].cfitness + population[mem].rfitness; } for (i = 1; i <= EX_NUM; i++) { p = rand()%1000/1000.0; if (p < population[0].cfitness) { MPI_Isend(&population[0], sizeof(struct genotype)/sizeof(char), MPI_CHAR, (pid+i*generation)%pnum, 0, MPI_COMM_WORLD, &handle); } else { for (j = 0; j < TASK_NUM(pid);j++) if (p >= population[j].cfitness && p < population[j+1].cfitness) { MPI_Isend(&population[j+1], sizeof(struct genotype)/sizeof(char), MPI_CHAR, (pid+i*generation)%pnum, 0, MPI_COMM_WORLD, &handle); break; } } MPI_Recv (&ex_member[i-1], sizeof(struct genotype)/sizeof(char), MPI_CHAR, (pid+(pnum-i)*generation)%pnum, 0, MPI_COMM_WORLD, &status); } for (i = 0; i < TASK_NUM(pid); i++) { p = rand()%1000/1000.0; if (p < population[0].cfitness) newpopulation[i] = population[0]; else { for (j = 0; j < TASK_NUM(pid); j++) if (p >= population[j].cfitness && p < population[j+1].cfitness) newpopulation[i] = population[j+1]; } } for (i = 0; i < TASK_NUM(pid); i++) population[i] = newpopulation[i]; for (i = 0; i < EX_NUM; i++) { j = rand()%TASK_NUM(pid); if (population[j].fitness < ex_member[i].fitness) { for (k = 0; k < NVARS; k++) { population[j].gene[k] = ex_member[i].gene[k]; } population[j].rfitness = 0; population[j].cfitness = 0; population[j].fitness = ex_member[i].fitness; } } } void swap(double *x, double *y) { double temp; temp = *x; *x = *y; *y = temp; } void Xover(int one, int two) { int i; int point; if(NVARS > 1) { if(NVARS == 2) point = 1; else point = (rand() % (NVARS - 1)) + 1; for (i = 0; i < point; i++) swap(&population[one].gene[i], &population[two].gene[i]); } } void crossover(void) { int i, mem, one; int first = 0; double x; for (mem = 0; mem < TASK_NUM(pid); mem++) { x = rand()%1000/1000.0; if (x < PXOVER) { first++; if (first % 2 == 0) Xover(one, mem); else one = mem; } } } void mutate(void) { int i, j; for (i = 0; i < TASK_NUM(pid); i++) for (j = 0; j < NVARS; j++) { if (rand()%1000/1000.0 < PMUTATION) { population[i].gene[j] = randval(lowerbound[j], upperbound[j]); } } } void elitist(void) { int i; double best, worst; int best_mem, worst_mem; best = population[0].fitness; worst = population[0].fitness; for (i = 0; i < TASK_NUM(pid) - 1; ++i) { if(population[i].fitness > population[i+1].fitness) { if (population[i].fitness >= best) { best = population[i].fitness; best_mem = i; } if (population[i+1].fitness <= worst) { worst = population[i+1].fitness; worst_mem = i + 1; } } else { if (population[i].fitness <= worst) { worst = population[i].fitness; worst_mem = i; } if (population[i+1].fitness >= best) { best = population[i+1].fitness; best_mem = i + 1; } } } if (best >= population[TASK_NUM(pid)].fitness) { for (i = 0; i < NVARS; i++) { population[TASK_NUM(pid)].gene[i] = population[best_mem].gene[i]; local_best_individual[i+1] = population[best_mem].gene[i]; } population[TASK_NUM(pid)].fitness = population[best_mem].fitness; local_best_individual[0] = population[best_mem].fitness; } else { for (i = 0; i < NVARS; i++) population[worst_mem].gene[i] = population[TASK_NUM(pid)].gene[i]; population[worst_mem].fitness = population[TASK_NUM(pid)].fitness; } } void report(void) { int i, j; fprintf(galog, "\nGene data in %d for generation %d is:\n", pid, generation); for (j = 0; j < TASK_NUM(pid); j++) { fprintf(galog, "%4d :", j); for (i = 0; i < NVARS; i++) { fprintf(galog, "\t%10.6lf ", population[j].gene[i]); } fprintf(galog, ": %20.6lf\n", population[j].fitness); } } void gene_max(double *in, double *inout, int *len, MPI_Datatype *dptr) { int i; if (inout[0] < in[0]) { for (i=0; i < *len; ++i) { inout[i] = in[i]; } } } int main(int argc, char **argv) { double startwtime = 0.0, endwtime; int i, j, flag; int n = 0; MPI_Op my_op; MPI_Init(&argc, &argv); MPI_Comm_size(MPI_COMM_WORLD, &pnum); MPI_Comm_rank(MPI_COMM_WORLD, &pid); fprintf(stdout, "Process %d of %d start ....\n",pid, pnum); //if ((galog = fopen("ga_log.txt","w"))==NULL) //{ // exit(1); //} galog = stdout; generation = 0; if (pid == pnum - 1) { srand(time(0)); startwtime = MPI_Wtime(); } initialize(); evaluate(); keep_the_best(); while(generation { generation++; pop_select(); crossover(); mutate(); evaluate(); elitist(); } MPI_Op_create((MPI_User_function *)gene_max, 1, &my_op); MPI_Reduce( local_best_individual, best_individual, NVARS+1, MPI_DOUBLE, my_op, pnum-1, MPI_COMM_WORLD ); /* for (i = 0; i < NVARS; i++) { fprintf (galog,"\n var(%d) = %3.3f",i,population[POPSIZE].gene[i]); } fprintf(galog,"\n\n Best fitness = %3.3f",population[POPSIZE].fitness); */ if (pid == pnum - 1) { fprintf(galog, "\n The solution is (population size = %d, # of generations = %d):\n", TASK_NUM(0)*pnum, generation); for (i=0; i fprintf(galog, " fitness \n"); for (i=0; i fprintf(galog, "%20.6lf\n", best_individual[0]); endwtime = MPI_Wtime(); fprintf(galog, "\n Wall clock time = %lf\n ", endwtime-startwtime); //fclose(galog); } //printf("\nProcess %d of %d Done ....\n", pid, pnum); fflush(stdout); MPI_Finalize(); return 0; } 一需求分析 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．测试数据 输入初始变量后用y=100*(x1*x1-x2)*(x1*x2-x2)+(1-x1)*(1-x1)其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 二概要设计 1．程序流程图 2．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 4．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个体就被选出，即适应度为fi的个体以fi/∑fk的概率继续存在； 显然，个体适应度愈高，被选中的概率愈大。但是，适应度小的个体也有可能被选中，以便增加下一代群体的多样性。 （4）染色体交叉函数crossoveroperator() 这是遗传算法中的最重要的函数之一，它是对个体两个变量所合成的染色体进行交叉，而不是变量染色体的交叉，这要搞清楚。首先用rand ()函数产生随机概率，若小于交叉概率，则进行染色体交叉，同时交叉次数加1。这时又要用rand()函数随机产生一位交叉位，把染色 遗传算法并行化的研究 学号：SC02011036 姓名：黄鑫 摘要 本文是针对遗传算法并行化进行了研究，首先简要给出了基本遗传算法的形式化描述，然后做了并行性的分析，详细介绍了遗传算法的结构化并行模型：步进模型，岛屿模型，邻接模型，最后指出了进一步要研究的课题。 关键词：遗传算法，并行计算，结构化GA 1引言 遗传算法（GA）是根据达尔文进化论“优胜劣汰，适者生存”的一种启发式搜索算法。采用选择，交叉，变异等基本变化算子在解空间同时进行多点搜索，本身固有并行性。随着大规模并行机的迅速发展，将并行机的高速性与遗传算法并行性结合起来，从而促进遗传算法的发展。然而，仅仅将基本遗传算法硬件并行化伴随着大量通讯开销等问题，从而必须对标准GA的进行改进，使得并行遗传算法不单单是遗传算法硬件并行实现，更重要的是结构化的遗传算法。本文首先给出了GA形式化描述，对基本GA的可并行性做出分析，然后给出了并行GA的模型，最后指出了并行遗传算法还需要解决的问题。 2 基本遗传算法 在这里我们不对遗传算法做过多的介绍，只是给出基本遗传算法的形式化描述：begin (1)initialization (1.1)产生一个初始群体 (1.2)评估第一代整个群体的适应度值 （2）while running do (2.1)选择父代 (2.2)交叉操作 (2.3)子代变异 (2.4)评估子代的适应度 (2.5)子代取代父代，形成新的一带个体 endwhile end 3 遗传算法的并行性分析 从第一节对遗传算法的描述，我们可以看出基本遗传算法模型是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体(候选解)，这个迭代过程直到满足某种结束条件为止。对应于基本遗传算法的运行过程，为实现其并行化要求，可以从下面四种并行性方面着手对其进行改进和发展。 并行性Ⅰ：个体适应度评价的并行性。 个体适应度的评价在遗传算法中占用的运行时间比较大。通过对适应度并行计算方法的研究，可提高个体适应度评价的计算效率。 并行性Ⅱ：整个群体各个个体适应度评价的并行性。 硕士生考查课程考试试卷 考试科目： 考生姓名：考生学号： 学院：专业： 考生成绩： 任课老师(签名) 考试日期：年月日午时至时 《MATLAB 教程》试题： A 、利用MATLA B 设计遗传算法程序，寻找下图11个端点最短路径，其中没有连接端点表示没有路径。要求设计遗传算法对该问题求解。 a e h k B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 C 、利用MATLAB 编程实现：三名商人各带一个随从乘船渡河，一只小船只能容纳二人，由他们自己划行，随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货，但是如何乘船渡河的大权掌握在商人手中，商人们怎样才能安全渡河？ D 、结合自己的研究方向选择合适的问题，利用MATLAB 进行实验。 以上四题任选一题进行实验，并写出实验报告。 选择题目： B 、设计遗传算法求解f (x)极小值，具体表达式如下： 321231(,,)5.12 5.12,1,2,3i i i f x x x x x i =?=???-≤≤=? ∑ 要求必须使用m 函数方式设计程序。 一、问题分析（10分） 这是一个简单的三元函数求最小值的函数优化问题，可以利用遗传算法来指导性搜索最小值。实验要求必须以matlab 为工具，利用遗传算法对问题进行求解。 在本实验中，要求我们用M 函数自行设计遗传算法，通过遗传算法基本原理，选择、交叉、变异等操作进行指导性邻域搜索，得到最优解。 二、实验原理与数学模型（20分） （1）试验原理： 用遗传算法求解函数优化问题，遗传算法是模拟生物在自然环境下的遗传和进化过程而形成的一种自适应全局优化概率搜索方法。其采纳了自然进化模型，从代表问题可能潜在解集的一个种群开始，种群由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体；初始种群产生后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的解：在每一代，概据问题域中个体的适应度大小挑选个体；并借助遗传算子进行组合交叉和主客观变异，产生出代表新的解集的种群。这一过程循环执行，直到满足优化准则为止。最后，末代个体经解码，生成近似最优解。基于种群进化机制的遗传算法如同自然界进化一样，后生代种群比前生代更加适应于环境，通过逐代进化，逼近最优解。 遗传算法是一种现代智能算法，实际上它的功能十分强大，能够用于求解一些难以用常规数学手段进行求解的问题，尤其适用于求解多目标、多约束，且目标函数形式非常复杂的优化问题。但是遗传算法也有一些缺点，最为关键的一点，即没有任何理论能够证明遗传算法一定能够找到最优解，算法主要是根据概率论的思想来寻找最优解。因此，遗传算法所得到的解只是一个近似解，而不一定是最优解。 （2）数学模型 对于求解该问题遗传算法的构造过程： （1）确定决策变量和约束条件； Windows下MATLAB分布式并行计算服务器配置和使用方 法 1MATLAB分布式并行计算服务器介绍 MATLAB Distributed Computing Server可以使并行计算工具箱应用程序得到扩展，从而可以使用运行在任意数量计算机上的任意数量的worker。MATLAB Distributed Computing Server还支持交互式和批处理工作流。此外，使用Parallel Computing Toolbox 函数的MATLAB 应用程序还可利用MATLAB Compiler （MATLAB 编译器）编入独立的可执行程序和共享软件组件，以进行免费特许分发。这些可执行应用程序和共享库可以连接至MATLAB Distributed Computing Server的worker，并在计算机集群上执行MATLAB同时计算，加快大型作业执行速度，节省运行时间。 MATLAB Distributed Computing Server 支持多个调度程序：MathWorks 作业管理器（随产品提供）或任何其他第三方调度程序，例如Platform LSF、Microsoft Windows Compute Cluster Server（CCS）、Altair PBS Pro，以及TORQUE。 使用工具箱中的Configurations Manager（配置管理器），可以维护指定的设置，例如调度程序类型、路径设置，以及集群使用政策。通常，仅需更改配置名称即可在集群间或调度程序间切换。 MATLAB Distributed Computing Server 会在应用程序运行时在基于用户配置文件的集群上动态启用所需的许可证。这样，管理员便只需在集群上管理一个服务器许可证，而无需针对每位集群用户在集群上管理单独的工具箱和模块集许可证。 作业（Job）是在MATLAB中大量的操作运算。一个作业可以分解不同的部分称为任务（Task），客户可以决定如何更好的划分任务，各任务可以相同也可以不同。MALAB中定义并建立作业及其任务的会话（Session）被称为客户端会话，通常这是在你用来编写程序那台机器上进行的。客户端用并行计算工具箱来定义和建立作业及其任务，MDCE通过计算各个任务来执行作业并负责把结果返 实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法(Genetic Algorithm —GA),就是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型，它就是由美国Michigan大学的J、Holla nd教授于1975 年首先提出的?遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位. 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算? 1. 遗传算法的基本原理 遗传算法的基本思想正就是基于模仿生物界遗传学的遗传过程?它把问题的参数用基因代表，把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体?这个群体在问题特定的环境里生存 竞争,适者有最好的机会生存与产生后代?后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境，不断进化,最后收敛到一族最适应环境的类似个体，即得到问题最优的解?值得注意的一点就是，现在的遗传算法就是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身就是否完全正确并不重要(目前生物界对此学说尚有争议). (1)遗传算法中的生物遗传学概念 由于遗传算法就是由进化论与遗传学机理而产生的直接搜索优化方法；故而 在这个算法中要用到各种进化与遗传学的概念? 首先给出遗传学概念、遗传算法概念与相应的数学概念三者之间的对应关系这些概念 （2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）:选择（Selection）、交叉（Crossover）、变异（Mutation）. 遗传算法基本步骤主要就是：先把问题的解表示成“染色体”，在算法中也就就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就就是假设的可行解.然后，把这些假设的可行解置于问题的“环境”中,并按适者生存的原则从中选 择出较适应环境的“染色体”进行复制 ，再通过交叉、变异过程产生更适 应环境的新一代“染色体”群.经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就就是问题的最优解. 下面给出遗传算法的具体步骤，流程图参见图1: 第一步:选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步:定义适应函数，便于计算适应值； 第三步:确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 第四步:随机产生初始化群体； 第五步:计算群体中的个体或染色体解码后的适应值； 第六步:按照遗传策略，运用选择、交叉与变异算子作用于群体，形成下一代群体； 第七步:判断群体性能就是否满足某一指标、或者就是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步. 图1 一个遗传算法的具体步骤 function youhuafun D=code; N=50;%Tunable maxgen=50;%Tunable crossrate=0.5;%Tunable muterate=0.08;%Tunable generation=1; num=length(D); fatherrand=randint(num,N,3); score=zeros(maxgen,N); while generation<=maxgen ind=randperm(N-2)+2;%随机配对交叉 A=fatherrand(:,ind(1:(N-2)/2)); B=fatherrand(:,ind((N-2)/2+1:end)); %多点交叉 rnd=rand(num,(N-2)/2); ind=rnd tmp=A(ind); A(ind)=B(ind); B(ind)=tmp; %%两点交叉 %for kk=1:(N-2)/2 %rndtmp=randint(1,1,num)+1; %tmp=A(1:rndtmp,kk); %A(1:rndtmp,kk)=B(1:rndtmp,kk); %B(1:rndtmp,kk)=tmp; %end fatherrand=[fatherrand(:,1:2),A,B]; %变异 rnd=rand(num,N); ind=rnd[m,n]=size(ind); tmp=randint(m,n,2)+1; tmp(:,1:2)=0; fatherrand=tmp+fatherrand; fatherrand=mod(fatherrand,3); %fatherrand(ind)=tmp; %评价、选择 scoreN=scorefun(fatherrand,D);%求得N个个体的评价函数 score(generation,:)=scoreN; [scoreSort,scoreind]=sort(scoreN); sumscore=cumsum(scoreSort); sumscore=sumscore./sumscore(end); childind(1:2)=scoreind(end-1:end); for k=3:N tmprnd=rand; tmpind=tmprnd difind=[0,diff(t mpind)]; if~any(difind) difind(1)=1; end childind(k)=scoreind(logical(difind)); end fatherrand=fatherrand(:,childind); generation=generation+1; end %score maxV=max(score,[],2); minV=11*300-maxV; plot(minV,'*');title('各代的目标函数值'); F4=D(:,4); FF4=F4-fatherrand(:,1); FF4=max(FF4,1); D(:,5)=FF4; save DData D function D=code load youhua.mat %properties F2and F3 F1=A(:,1); F2=A(:,2); F3=A(:,3); if(max(F2)>1450)||(min(F2)<=900) error('DATA property F2exceed it''s range (900,1450]') end %get group property F1of data,according to F2value F4=zeros(size(F1)); for ite=11:-1:1 index=find(F2<=900+ite*50); F4(index)=ite; end D=[F1,F2,F3,F4]; function ScoreN=scorefun(fatherrand,D) F3=D(:,3); F4=D(:,4); N=size(fatherrand,2); FF4=F4*ones(1,N); FF4rnd=FF4-fatherrand; FF4rnd=max(FF4rnd,1); ScoreN=ones(1,N)*300*11; %这里有待优化 1在并行机系统中，主流操作系统有UNIX/Linux，AIX(IBM)，HPUX(HP)，Solaris(SUN)，IRIX(SGI)等。 2 常用的并行算法设计的基本技术有划分，分治，倍增，流水域，破对称，平衡 树等设计技术。 3 Matlab并行程序编写过程分为创建对象，创建工作，指定工作任务，提交工作，等待和返回计算任务结果六步。 1. 云计算是对（ D ）技术的发展与运用 A. 并行计算 B网格计算 C分布式计算 D三个选项都是 2. IBM在2007年11月退出了“改进游戏规则”的（ A ）计算平台，为客户带来即买即用的云计算平台。 A. 蓝云 B. 蓝天 C. ARUZE D. EC2 3. 微软于2008年10月推出云计算操作系统是（ C ） A. Google App Engine B. 蓝云 C. Azure D. EC2 4. 2008年，（ A ）先后在无锡和北京建立了两个云计算中心 A. IBM B. Google C. Amazon D. 微软 5. 将平台作为服务的云计算服务类型是（ B ） A. IaaS B.PaaS C.SaaS D.三个选项都不是 6. 将基础设施作为服务的云计算服务类型是（ A ） A. IaaS B.PaaS C.SaaS D.三个选项都不是 7. IaaS计算实现机制中，系统管理模块的核心功能是（ A ） A. 负载均衡 B 监视节点的运行状态 C应用API D. 节点环境配置 8. 云计算体系结构的（ C ）负责资源管理、任务管理用户管理和安全管理等工作 A.物理资源层 B. 资源池层 C. 管理中间件层 D. SOA构建层 9. 下列不属于Google云计算平台技术架构的是（ D ） A. 并行数据处理MapReduce B.分布式锁Chubby C. 结构化数据表BigTable D.弹性云计算EC2 10. 在目前GFS集群中，每个集群包含（ B ）个存储节点 A.几百个 B. 几千个 C.几十个 D.几十万个 11. 下列选项中，哪条不是GFS选择在用户态下实现的原因（ D ） A.调试简单 B.不影响数据块服务器的稳定性 C. 降低实现难度，提高通用性 D. 容易扩展 12. GFS中主服务器节点存储的元数据包含这些信息（ BCD ） A.文件副本的位置信息 B.命名空间 C. Chunk与文件名的映射 D. Chunk副本的位置信息 13. 单一主服务器（Master）解决性能瓶颈的方法是（ ABCD ） A.减少其在数据存储中的参与程度 B. 不适用Master读取数据 C.客户端缓存元数据 D. 采用大尺寸的数据块 14. （ B ）是Google提出的用于处理海量数据的并行编程模式和大规模数据集的并行运算的软件 架构。 A. GFS B.MapReduce C.Chubby D.BitTable 15. Mapreduce适用于（ D ） A. 任意应用程序 B. 任意可在windows servet2008上运行的程序 C.可以串行处理的应用程序 D. 可以并行处理的应用程序 一个简单实用的遗传算 法c程序 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 一个简单实用的遗传算法c程序（转载） 2009-07-28 23:09:03 阅读418 评论0 字号：大中小 这是一个非常简单的遗传算法源代码，是由Denis Cormier (North Carolina State University)开发的，Sita (University of North Carolina at Charlotte)修正。代码保证尽可能少，实际上也不必查错。对一特定的应用修正此代码，用户只需改变常数的定义并且定义“评价函数”即可。注意代码的设计是求最大值，其中的目标函数只能取正值；且函数值和个体的适应值之间没有区别。该系统使用比率选择、精华模型、单点杂交和均匀变异。如果用Gaussian变异替换均匀变异，可能得到更好的效果。代码没有任何图形，甚至也没有屏幕输出，主要是保证在平台之间的高可移植性。读者可以从,目录 coe/evol中的文件中获得。要求输入的文件应该命名为‘’；系统产生的输出文件为‘’。输入的文件由几行组成：数目对应于变量数。且每一行提供次序——对应于变量的上下界。如第一行为第一个变量提供上下界，第二行为第二个变量提供上下界，等等。 /**************************************************************************/ /* This is a simple genetic algorithm implementation where the */ /* evaluation function takes positive values only and the */ /* fitness of an individual is the same as the value of the */ /* objective function */ /**************************************************************************/ #include <> #include <> #include <> /* Change any of these parameters to match your needs */ #define POPSIZE 50 /* population size */ 第1期作者简介：李红梅（1978-），女，湖南湘潭人，硕士，广东白云学院讲师，研究方向为演化计算。 1遗传算法的发展史 遗传算法（Genetic Algorithms ）研究的历史比较短，20世纪 60年代末期到70年代初期，主要由美国家Michigan 大学的John Holland 与其同事、学生们研究形成了一个较完整的理论 和方法，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。我国对于GA 的研究起步较晚，不过从20世纪90年代以来一直处于不断上升中。 2遗传算法的基本思想 遗传算法是从代表问题可能潜在解集的一个种群（popu- lation ）开始的，而一个种群则由经过基因（gene ）编码（coding ） 的一定数目的个体（individual ）组成。每个个体实际上是染色体（chromosome ）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation ）演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度（fitness ）、大小挑选（selection ）个体，借助于自然遗传学的遗传算子（genetic operators ）进行组合交叉（crossover ）和变异（mutation ），产生出代 表新的解集的种群。这个过程将导致后生代种群比前代更加适应环境，末代种群中的最优个体经过解码（decoding ），可以作为问题近似最优解。 3遗传算法的一般流程 （1）随机产生一定数目的初始种群，每个个体表示为染色 体的基因编码； （2）计算每个个体的适应度，并判断是否符合优化准则。若符合，输出最佳个体及其代表的最优解并结束计算，否则转向第3步； （3）依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰； （4）执行交叉和变异操作，生成新的个体；（5）得到新一代的种群，返回到第2步。 4遗传算法的特点 传统的优化方法主要有三种：枚举法、启发式算法和搜索 算法： （1）枚举法 可行解集合内的所有可行解，以求出精确最 优解。对于连续函数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达不到最优解。此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前先进计算机工具上无法求解。 （2）启发式算法 寻求一种能产生可行解的启发式规则， 以找到一个最优解或近似最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找出其特有的启发式规则。这个启发式规则一般无通用性，不适合于其它问题。 （3）搜索算法 寻求一种搜索算法，该算法在可行解集合 的一个子集内进行搜索操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和效率上达到一种较好的平衡。 遗传算法不同于传统的搜索和优化方法。主要区别在于： ①遗传算法直接处理问题参数的适当编码而不是处理参数集 本身。②遗传算法按并行方式搜索一个种群数目的点，而不是 遗传算法概述 李红梅 （广东白云学院计算机系，广东广州510450） 摘要：遗传算法是一种全局优化的随机搜索算法。它是解决复杂优化问题的有力工具。在工程设计、演化硬件电路 设计以及人工智能等方面应用前景广阔。系统地介绍了遗传算法的发展史、基本思想、特点、主要应用领域等相关方 面。 关键词：遗传算法；搜索；进化；最优解；种群中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2009）01-0067-02 第8卷第1期2009年1月 Vol.8No.1Jan.2009 软件导刊 Software Guide 并行计算技术及其应用简介 XX （XXX，XX，XXX） 摘要：并行计算是实现高性能计算的主要技术手段。在本文中从并行计算的发展历程开始介绍，总结了并行计算在发展过程中所面临的问题以及其发展历程中出现的重要技术。通过分析在当前比较常用的实现并行计算的框架和技术，来对并行计算的现状进行阐述。常用的并行架构分为SMP（多处理系统）、NUMA （非统一内存存储）、MPP（巨型并行处理）以及集群。涉及并行计算的编程模型有MPI、PVM、OpenMP、TBB及Cilk++等。并结合当前研究比较多的云计算和大数据来探讨并行计算的应用。最后通过MPI编程模型，进行了并行编程的简单实验。 关键词：并行计算；框架；编写模型；应用；实验 A Succinct Survey about Parallel Computing Technology and It’s Application Abstract:Parallel computing is the main technology to implement high performance computing. This paper starts from the history of the development of Parallel Computing. It summarizes the problems faced in the development of parallel computing and the important technologies in the course of its development. Through the analysis of framework and technology commonly used in parallel computing currently,to explain the current situation of parallel computing.Framework commonly used in parallel are SMP(multi processing system),NUMA(non uniform memory storage),MPP(massively parallel processing) and cluster.The programming models of parallel computing are MPI, PVM, OpenMP, TBB and Cilk++, etc.Explored the application of parallel computing combined with cloud computing and big data which are very popular in current research.Finally ,through the MPI programming model,a simple experiment of parallel programming is carried out. Key words:parallel computing; framework; programming model; application; experiment 1引言 近年来多核处理器的快速发展，使得当前软件技术面临巨大的挑战。单纯的提高单机性能，已经不能满足软件发展的需求，特别是在处理一些大的计算问题上，单机性能越发显得不足。在最近AlphaGo与李世石的围棋大战中，AlphaGo就使用了分布式并行计算技术，才能获得强大的搜索计算能力。并行计算正是在这种背景下，应运而生。并行计算或称平行计算时相对于串行计算来说的。它是一种一次可执行多个指令的算法，目的是提高计算速度，及通过扩大问题求解规模，解决大型而复杂的计算问题。可分为时间上的并行和空间上的并行。时间上的并行就是指流水线技术，而空间上的并行则是指用多个处理器并发的执行计算。其中空间上的并行，也是本文主要的关注点。 并行计算（Parallel Computing）是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算。并行计算系统既可以是专门设计的，含有多个处理器的超级计算机，也可以是以某种方式互联的若干台的独立计算机构成的集群。通过并行计算集群完成数据的处理，再将处理的结果返回给用户。 目前常用的并行计算技术中，有调用系统函数启动多线程以及利用多种并行编程语言开发并行程序，常用的并行模型有MPI、PVM、OpenMP、TBB、Cilk++等。利用这些并行技术可以充分利用多核资源适应目前快速发展的社会需求。并行技术不仅要提高并行效率，也要在一定程度上减轻软件开发人员负担，如近年来的TBB、Cilk++并行模型就在一定程度上减少了开发难度，提高了开发效率，使得并行软件开发人员把更多精力专注于如何提高算法本身效率，而非把时间和精力放在如何去并行一个算法。 华南理工大学分布式计算期末考试卷题整 理 第一章：分布式 1）并行计算与分布式计算区别？ （1）所谓分布式计算是一门计算机科学，它研究如何把一个需要非常巨大的计算能力才能 解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些 计算结果综合起来得到最终的结果。 与并行计算不同的是，并行计算是使用多个处理器并行执行单个计算。 2）分布式计算的核心技术是？ 进程间通信IPC！！！ 3）解决进程间通信死锁的两种方法？ 超时和多线程 4）分布式系统的CAP理论是什么？ 一致性，可用性，分区容忍性 第二章：范型 1)网络应用中使用的最多的分布式计算范型是？ 客户-服务器范型（简称CS范型） 2)消息传递范型与消息中间件范型异同？ 消息传递：一个进程发送代表请求的消息，该消息被传送到接受者；接受者处理该请求，并发送一条应答消息。随后，该应答可能触发下一个请求，并导致下一个应答消息。如 此不断反复传递消息，实现两个进程间的数据交换. 基于该范型的开发工具有Socket应用程序接口（Socket API）和信息传递接口（Message Passing Interface，MPI）等 消息系统模型可以进一步划分为两种子类型：点对点消息模型（Point- to-point message model）和发布订阅消息模型（Public/Subscribe message model）。 在这种模型中，消息系统将来自发送者的一条消息转发到接收者的消息 队列中。与基本的消息传递模型不同的是，这种中间件模型提供了消息 暂存的功能，从而可以将消息的发送和接受分离。与基本的消息传递模 型相比，点对点消息模型为实现异步消息操作提供了额外的一层抽象。 如果要在基本的消息传递模型中达到同样的结果，就必须借助于线程或 者子进程技术。 3)一个分布式应用能否使用多个分布式计算范型？ 可以，部分。 并行遗传算法及其应用 1、遗传算法（GA）概述 GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。生物遗传物质的主要载体是染色体，在GA中同样将问题的求解表示成“染色体Chromosome”，通常是二进制字符串表示，其本身不一定是解。首先，随机产生一定数据的初始染色体，这些随机产生的染色体组成一个种群（Population），种群中染色体的数目称为种群的大小或者种群规模。第二：用适值度函数来评价每一个染色体的优劣，即染色体对环境的适应程度，用来作为以后遗传操作的依据。第三：进行选择（Selection），选择过程的目的是为了从当前种群中选出优良的染色体，通过选择过程，产生一个新的种群。第四：对这个新的种群进行交叉操作，变异操作。交叉、变异操作的目的是挖掘种群中个体的多样性，避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。 GA通常包含5个基本要素：1、参数编码：GA是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常选择二进制编码。2、初始种群设定：GA随机产生一个由N个染色体组成的初始种群（Population），也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3、适值度函数的设定：适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4、遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5、控制参数设定：在GA的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率，进化代数等。 GA的优点是擅长全局搜索，一般来说，对于中小规模的应用问题，能够在许可的范围内获得满意解，对于大规模或超大规模的多变量求解任务则性能较差。另外，GA本身不要求对优化问题的性质做一些深入的数学分析，从而对那些不 C语言遗传算法代码 以下为遗传算法的源代码，计算一元代函数的代码和二元函数的代码以+++++++++++++++++++++++++++++++++++++为分割线分割开来，请自行选择适合的代码，使用时请略看完代码的注释，在需要更改的地方更改为自己需要的代码。 +++++++++++++++++++++++++++++++一元函数代码++++++++++++++++++++++++++++ #include 遗 传 算 法 （基于遗传算法求函数最大值） 指导老师：刘建丽 学号：S201007156 姓名：杨平 班级：研10级1班 遗传算法 一、 遗传算法的基本描述 遗传算法（Genetic Algorithm ，GA ）是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如TSP 。因时间有些紧张，做如TSP 等复杂问题怕时间不够，做不出来，请老师原谅），考虑的具有问题是：对给定的正整数n 、n 元函数f ，以及定义域D ，求函数f 在D 内的最大值。 二、 串行遗传算法 1． 染色体与适应度函数 对函数优化问题，一个潜在的解就是定义域D 中的一个点011(,,...,)n x x x -，因此，我们只需用一个长度为n 的实数数组来表示一个个体的染色体。由于问题中要求求函数f 的最大值，我们可以以个体所代表点011(,,...,)n x x x -在f 函数下的值来判断该个体的好坏。因此，我们直接用函数f 作为个体的适应度函数。 2． 选择机制 选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。 遗传算法的C语言程序案例 一、说明 1．本程序演示的是用简单遗传算法随机一个种群，然后根据所给的交叉率，变异率，世代数计算最大适应度所在的代数 2．演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的命令；相应的输入数据和运算结果显示在其后。3．举个例子，输入初始变量后，用y= (x1*x1)+(x2*x2)，其中-2.048<=x1,x2<=2.048作适应度函数求最大适应度即为函数的最大值 4．程序流程图 5．类型定义 int popsize; //种群大小 int maxgeneration; //最大世代数 double pc; //交叉率 double pm; //变异率 struct individual { char chrom[chromlength+1]; double value; double fitness; //适应度 }; int generation; //世代数 int best_index; int worst_index; struct individual bestindividual; //最佳个体 struct individual worstindividual; //最差个体 struct individual currentbest; struct individual population[POPSIZE]; 3．函数声明 void generateinitialpopulation(); void generatenextpopulation(); void evaluatepopulation(); long decodechromosome(char *,int,int); void calculateobjectvalue(); void calculatefitnessvalue(); void findbestandworstindividual(); void performevolution(); void selectoperator(); void crossoveroperator(); void mutationoperator(); void input(); void outputtextreport(); 6．程序的各函数的简单算法说明如下： （1）．void generateinitialpopulation ()和void input ()初始化种群和遗传算法参数。 input() 函数输入种群大小，染色体长度，最大世代数，交叉率，变异率等参数。 （2）void calculateobjectvalue();计算适应度函数值。 根据给定的变量用适应度函数计算然后返回适度值。 （3）选择函数selectoperator() 在函数selectoperator()中首先用rand ()函数产生0～1间的选择算子，当适度累计值不为零时，比较各个体所占总的适应度百分比的累计和与选择算子，直到达到选择算子的值那个个遗传算法的c语言程序
遗传算法并行化的研究.doc
MATLAB课程遗传算法实验报告及源代码
MATLAB分布式并行计算服务器配置和使用方法Word版
遗传算法与优化问题
基于遗传算法的matlab源代码
并行计算考试复习
一个简单实用的遗传算法c程序完整版
遗传算法概述
分布式与并行计算报告
华南理工大学分布式计算期末考试卷题整理
并行遗传算法
遗传算法C语言源代码(一元函数和二元函数)
遗传算法的并行实现
遗传算法的C语言程序案例