1、“.....防止出现早熟现象。变异操作的实现相当简单，只需遍历各染色体 的各个单元，按变异概率将该单元变成个随机的合法值。 其执行过程是 对个体的每个基因组，依变异概率指定为变异点。 对每个指定的变异点，对其基因取非或者用其他等位基因值来代替，从 而产生个新的个体。实现代码如下 定义为随机变异概率 北京工业大学并行计算课程设计论文 串行遗传算法的主要流程如图所示。在每次进化过程中，总是找出种群 中的最优解与最差解，并将最优解保存，将本次最差解用上次保存的最优解替换， 这样保证了各次进化的最优解的适应度不会降低，从而增快收敛的速度。 按适应度随机 选择参与进化 的个体 杂交 变异 评估 选出最优个体和最差 个体,保存最优个体......”。

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

3、“.....这些算子作用于个体对应的染色体，产生新的染色体，从 而构成下代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或 者达到设定的进化代数。显然，这样的思想适合于现实世界中的大类问题，因 而具有广泛的应用价值。遗传算法的每次进化过程中的，各个体之间的操作大 多可以并列进行，因此，个非常自然的想法就是将遗传算法并行化，以提高计 算速度。本报告中试图得到个并行遗传算法的框架，并考察并行化之后的些 特性。为简单起见本来应该考虑更复杂的问题，如。因时间有些紧张，做 如等复杂问题怕时间不够，做不出来，请老师原谅，考虑的具有问题是 对给定的正整数元函数，以及定义域，求函数在内的最大值。 二串行遗传算法 染色体与适应度函数 对函数优化问题，个潜在的解就是定义域中的个点,，因 此......”。

4、“.....并交换，从而得到新的染色体。 具体算法见如下函数 产生随机交叉概率 如果随机交叉概率小于交叉概率，则进行交叉 。由于问题中 要求求函数的最大值，我们可以以个体所代表点,在函数下的值 来判断该个体的好坏。因此，我们直接用函数作为个体的适应度函数。 选择机制 选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若 选择过程中适应度好的个体生存的概率过大......”。

5、“.....从而收敛于局部最优解反之，若适应度对生存概率的影响过小，则会使 算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用 的选择机制。北京工业大学并行计算课程设计论文 我们定义为当前种群内所有个体的集合,,为中所有个体的 个固定排列。若为个体，表示该个体的适应度，则种群的 适应度定义为    对任意个体，的相对适应度定义为。相 对适应度反映了个体的适应度在整个适应度总和中所占的比例。个 体适应度越高，被选中的概率越高。累积适应度定义为 进行选择之前，先产生个到之间的随机实数，若满足 ，则第个个体被选中。循环以上过程，即得到生成下代 种群的母体......”。

6、“.....不 过从表可以看出，进程增加时，解得质量并没有任何降低。 北京工业大学并行计算课程设计论文 六源程序清单 定义控制台应用程序的入口点。 种群大小 染色体的长度 杂交概率 变异概率 记录染色体的基因 适应度 相对适应度 累积适应度 局部最优解 全局最优解 最小的适应度 表实验结果 结果分析 表中最为有趣的现象是，当进程数小于时，该算法的加速比似乎与进程 数存在个平方关系，也就是说，存在个超线性加速的关系。进程数大于等 于时......”。

7、“.....只是由于节点数的限制，被进程管理 的开销所限制。下面我们通过估计时间复杂性来分析造成这种超线性加速的原 因。 如果将对染色体中每变元上的个计算看作个基本计算，并设变元数为 ，总种群中个体数为，进程数则对每进程，分析容易得到函 数最坏情形的时间复杂性为，函数最坏情形的时间复杂性 为，函数最坏情形的时间复杂性为，评估函数最坏情形 的时间复杂性为，函数最坏情形的时间复杂性为。此 外，按照算法的设计，在选择过程中的通讯所耗费的时间为。综合可知， 次进化的时间复杂性为。因此，所有进程总的计算时间最坏情形的 渐近上界为。而串行遗传算法次进化的时间复杂性为，这 就解释了为什么小于的情形会具有超线性加速。当然，这并不能说明并行计 算真能产生超线性加速比，因为我们可以非常有效地用个进程来模拟个进程 的计算......”。

8、“.....真正值得研究的问题是 分析上述建立并行遗传算法收敛速度与串行遗传算法的收敛速度出最优解 是 开始 初始化 终止 图串行遗传算法基本流程 北京工业大学并行计算课程设计论文 三算法设计 分析图中的串行算法，容易看出，在选择函数中，计算相对适应度需要用 到全局种群的适应度之和，计算个体的累积适应度依赖于的累积适应度， 如果在并行算法中要原封不动地模拟串行算法的运算，这些数据依赖关系都将产 生通讯。更为不幸的是，选择后的个体需在各进程中作大量数据迁移。杂交算子 中，次杂交需要用到母体中的两个个体，若在这两个个体分配在不同进程，则 需要进行次通讯。此后的变异和评估都可以非常容易的实现并行，并且完全不 需要任何通讯。但最后步求最优个体和最差个体需要对各进程进行归约。由这 些分析可以看出，完全地模拟串行情形将使算法变得相当低效......”。

9、“.....遗传算法本身是个概率算法，我们完全可以对串行算法作些必 要的改变。如图所示，我们将整个种群分成个子种群，每子种群由个单 的进程负责。各进程独立地完成串行遗传算法的整个过程，唯不同的是选择 函数。各进程作选择操作时，首先计算各子种群内的局部累积适应度，然后根据 局部累积适应度选择若干本算法实现中使用的是常数，也可以设为子种群大 小的个函数个体按固定规则轮流发送到其他进程同时，按照该规则相应 地从其他进程获取若干用来进行交流的个体。获取到个体后，先将其暂存然后 按串行算法中的选择机制从原子种群中选择进行进化的母体最后再用之前暂存 的个体完成进程间的种群交流。对每个待交流的个体，具体策略如下 随机地从本地的待进化母体种群内抽取与之进行交流的母体 比较本地个体与传送过来的待交流个体，选取适应度高者作为最终母 体。 各进程在每次进化过程中......”。