1、“.....保存最优个体,并 将最差个体用上代 最优个体替代 已完成规定进 化代数 否 输出最优解 是 开始 初始化种群 终止 初始化种群 按适应度随机 选择参与进化 的个体 杂交 变异 评估 选出最优个体和最差 个体,保存最优个体,并 将最差个体用上代 最优个体替代 已完成规定进 化代数 否 是 归约 另外，全局最优解的归约由如下代码实现 , ,从本地的待进化母体种群内抽取与之进行交流的母体 比较本地个体与传送过来的待交流个体，选取适应度高者作为最终母 体。 各进程在每次进化过程中，均分别保留各自的局部最优解，用来在下次 交流的个体。获取到个体后......”。

2、“.....对每个待交流的个体，具体策略如下 随机地累积适应度，然后根据 局部累积适应度选择若干本算法实现中使用的是常数，也可以设为子种群大 小的个函数个体按固定规则轮流发送到其他进程同时，按照该规则相应 地从其他进程获取若干用来进行 要的改变。如图所示，我们将整个种群分成个子种群，每子种群由个单 的进程负责。各进程地完成串行遗传算法的整个过程，唯不同的是选择 函数。各进程作选择操作时，首先计算各子种群内的局部要任何通讯。但最后步求最优个体和最差个体需要对各进程进行归约。由这 些分析可以看出，完全地模拟串行情形将使算法变得相当低效。 幸运地是，遗传算法本身是个概率算法，我们完全可以对串行算法作些必 择后的个体需在各进程中作大量数据迁移。杂交算子 中，次杂交需要用到母体中的两个个体，若在这两个个体分配在不同进程，则 需要进行次通讯......”。

3、“.....并且完全不 需算相对适应度需要用 到全局种群的适应度之和，计算个体的累积适应度依赖于的累积适应度， 如果在并行算法中要原封不动地模拟串行算法的运算，这些数据依赖关系都将产 生通讯。更为不幸的是，选 输出最优解 是 开始 初始化 终止 图串行遗传算法基本流程 北京工业大学并行计算课程设计论文 三算法设计 分析图中的串行算法，容易看出，在选择函数中，计增快收敛的速度。 按适应度随机 选择参与进化 的个体 杂交 变异 评估 选出最优个体和最差 个体,保存最优个体,并 将最差个体用上代 最优个体替代 已完成规定进 化代数 否 串行遗传算法的主要流程如图所示。在每次进化过程中，总是找出种群 中的最优解与最差解，并将最优解保存，将本次最差解用上次保存的最优解替换， 这样保证了各次进化的最优解的适应度不会降低......”。

4、“.....对其基因取非或者用其他等位基因值来代替，从 而产生个新的个体。实现代码如下 ,出现早熟现象。变异操作的实现相当简单，只需遍历各染色体 的各个单元，按变异概率将该单元变成个随机的合法值。 其执行过程是 对个体的每个基因组，依变异概率指定为变异点。 变异算子 在遗传算法中使用变异算子有两个目的改善遗传算法的局部搜索能力。维持群 体的多样性，防止 交叉运算，两个个体的交叉点前的基因进行交换 ,随机交叉概率小于交叉概率，则进行交叉 得到个交叉点 随机交叉概率小于交叉概率，则进行交叉 得到个交叉点 交叉运算，两个个体的交叉点前的基因进行交换 ......”。

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

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

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

8、“.....各进程均完成所预定的进化迭代后，最后对各进程 的局部最优解进行归约，从而得到整个算法的全局最优解。算法的主要流程详见 图。北京工业大学并行计算课程设计论文 按适应度随机 选择参与进化 的个体 选出最优个体和最差 个体,保存最优个体,并 将最差个体用上代 最优个体替代 已完成规定进 化代数 否 输出最优解 是 开始 初始化种群 终止 初始化种群 按适应度随机 选择参与进化 的个体 杂交 变异 评估 选出最优个体和最差 个体,保存最优个体,并 将最差个体用上代 最优个体替代 已完成规定进 化代数 否 是 归约 另外，全局最优解的归约由如下代码实现 , 其中，具体的归约操作由如下函数实现 ......”。

9、“.....用来计算最大值的函数为 ,   其定义域如文件中所示，总种群大小为，最大进化次数为。 进程个数 运算时间 加速比 运 行 结 果 进程个数北京工业大学并行计算课程设计论文 运算时间 加速比 运 行 结 果 表实验结果 结果分析 表中最为有趣的现象是，当进程数小于时，该算法的加速比似乎与进程 数存在个平方关系，也就是说，存在个超线性加速的关系。进程数大于等 于时，这种超线性加速实际也应该存在，只是由于节点数的限制，被进程管理 的开销所限制。下面我们通过估计时间复杂性来分析造成这种超线性加速的原 因。 如果将对染色体中每变元上的个计算看作个基本计算，并设变元数为 ，总种群中个体数为......”。