遗传算法的并行实现

《遗传算法的并行实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、遗传算法（基于遗传算法求函数最大值）指导老师：刘建丽学号：S201007156姓名：杨平班级：研10级1班遗传算法一、遗传算法的基本描述遗传算法（GeneticAlgorithm，GA）是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要

2、存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如TSP。因时间有些紧张，做如TSP等复杂问题怕时间不够，做不出来，请老师

3、原谅），考虑的具有问题是：对给定的正整数n、n元函数f，以及定义域D，求函数f在D内的最大值。二、串行遗传算法1．染色体与适应度函数对函数优化问题，一个潜在的解就是定义域D中的一个点，因此，我们只需用一个长度为n的实数数组来表示一个个体的染色体。由于问题中要求求函数f的最大值，我们可以以个体所代表点在f函数下的值来判断该个体的好坏。因此，我们直接用函数f作为个体的适应度函数。2．选择机制选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；

4、反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。我们定义为当前种群内所有个体的集合，为中所有个体的一个固定排列。若为某一个体，表示该个体的适应度，则种群的适应度定义为：对任意个体，的相对适应度定义为。相对适应度反映了个体的适应度在整个适应度总和中所占的比例。个体适应度越高，被选中的概率越高。累积适应度定义为:进行选择之前，先产生一个0到1之间的随机实数，若满足，则第k+1个个体被选中。循环以上过程，即得到生成下一代种群的母体。具体实现见如下函数：voidpop_select

5、(void){intmem,i,j,k;doublesum=0;doublep;/*计算种群适应度之和*/for(mem=0;mem=population[j].cfitness&&p

6、].cfitness)newpopulation[i]=population[j+1];}}/*计算种群的总适应度*/for(i=0;i

7、on[0].cfitness=population[0].rfitness;/*计算累积适应度*/for(mem=1;mem

8、,k,m,point;intfirst=0;doublex;for(k=0;k