算法骨架

算法骨架，英文全称是：algorthmic skeleton，是一种并行 编程环境。并行 编程环境为构建并行程序提供了基本工具、语言功能和应用编程接口（API）。Murray.Cole最早引入了skeleton（algorithmic skeleton）的概念，其中skeleton是算法的抽象，是对重复出现的算法和通信模式的精确、严格的定义，它对一系列的应用而言是公共的，并且可以并行地实现。

通过提供算法骨架，使得用户只需考虑问题的类型，适合哪种算法骨架，而不必显式地去处理如并行单元间通讯、同步等低层的并行特性，同时算法骨架还是与具体问题中无关的，从具体的问题和具体的并行环境都相解脱出来。所以算法骨架的作用可以总结为：

（1）通过提高并行开发的抽象层次，简化了 并行程序设计。

（2）通过skeleton的实现细节对用户透明，提高skeleton的可重用性和可移植性。

（3）在特定的体系结构上，skeleton的实现能够充分利用优化技术，从而有效提高并行程序的性能。

skeleton的上述思想与软件工程中许多成功的思想是相同的，如结构化的 程序设计、面向对象编程和设计模式等。值得一提的是，设计模式的思想已被扩充到并行领域。由于skeleton与设计模式概念的相关性，基于skeleton的 并行程序设计领域将基于skeleton与基于模式的并行研究工作很好地融合在一起，以提供一种通用的、更高层次的并行程序设计方法。

在特定的体系结构上，算法骨架能够充分利用优化技术，从而有效提高并行程序的性能，而这并不是所有从事并行编程的程序员所具备的，或者说让每一个并行程序员都编出很优秀的并行是很难的；这里的算法骨架独立于各种 并行计算环境，与各种并行计算环境无关的，并针对不同的计算环境做出相应的调整。

国内外关于算法骨架的研究也很多。

不同的组织都有各自的算法骨架，如Cole的eskel，Darlington、Rabhi、P3L等知名的骨架；

并行已经成为程序设计中的一个趋势，越来越高要求的计算，越来越多的 多核处理器，都预示着未来计算机世界的并行趋势已成必然。

并行遗传算法骨架(PGA_Skeleton)是为了简化遗传算法应用问题的求解过程，并可并行实现的这一类问题求解和算法设计方法的一种抽象结构。

并行遗传算法作为应用求解大型问题的方法，应用范围很广，包括函数优化、组合优化、生产调度等一系列问题，我们将其中的大部分雷同的部分形成抽象的算法骨架，这就是并行遗传算法骨架，它可以简化这类问题的求解过程，以及降低用户求解难度。

PGA_Skeleton 的描述

在PGA_Skeleton中，完成了包括初始化种群、选择、交叉、突变等几乎所有遗传算法应用中的计算操作以及遗传进化过程的控制行为，只为用户留下个体适应度评价函数作为与具体问题的交互接口。PGA_Skeleton 通过调用结构骨架来实现操作的并行，由于现存结构骨架形式多样，并行执行流程也就不尽相同，所以需要根据问题的不同特点选择合适的结构骨架，比如当个体适应度评价函数 (evaluate) 的复杂度较高时，使用 FARM 结构骨架并行效果就十分明显。PGA_Skeleton 由种群初始模块和遗传进化模块，流程图如图 2 所示。

种群初始模块(PGACreate)负责建立初始种群，需要接收来自用户的参数，包括染色体的编码方式，染色体上字符串的长度和初始种群的规模。遗传进化模块(PGARun)包括结构骨架选择(PGAChoose)、结构骨架调用和进化终止检查(PGACheck)3 部分组成。结构骨架选择部分根据问题规模和适应度函数复杂度，按照选择策略确定一个结构骨架；结构骨架调用部分将选择、交叉、变异和个体适应度评价函数传递给选中的结构骨架并行执行；进化过程控制部分主要对进化循环控制和个体迁移实现。应用并行抽象编程语言 APLA+描述 PGA_Skeleton 接口，如图 3 所示

PGA_Skeleton的内部流程

PGA_Skeleton由种群初始模块(PGACreate)和遗传进化模块(PGARun)组成。

(1)初始化模块

种群初始模块(PGACreate)负责建立初始种群。种群初始化包括随机产生和确定给出两种方式，大多数情况下都采用随机产生，这样可以免去输入工作的麻烦，它适合与对问题的解无任何先验知识的情况；在具备某些先验知识的情况下，可以根据要求产生一组个体，这样可以使遗传进化更快一些收敛到最优解。初始化工作需要接收来自用户的参数，包括染色体的编码方式，染色体上字符串的长度和初始种群的规模，这些参数共同确定初始种群的表现。

(2)进化模块

遗传进化模块(PGARun)包括结构骨架选择(PGAChoose)、结构骨架调用和进化终止检查(PGACheck)三部分组成。首先PGAChoose根据问题规模和适应度函数复杂度，按照选择策略确定一个结构骨架；然后结构骨架调用部分将选择、杂交、变异和个体适应度评价函数等任务传递给选中的结构骨架并行执行；最后进化终止检查部分检查进化代数和收敛程度决定是否终止进化。

PGA_Skeleton的接口描述

按照并行抽象编程语言Apla+中定义的规定的关键字skeleton和语法描述PGA_Skeleton接口。其中CODETYPEFLAG是关于编码方式的枚举类型，包括一维二进制编码、一维整数编码、一维实数编码、二维二进制编码、二维整数编码、二维实数编码等常见的六种染色体编码方式；PGACreate函数根据给定参数创建大小为nPopSize，编码方式为codeTypeFlag，上下界分别为upper和lower，码长为nChromSize的初始种群；函数PGARun完成遗传进化模块的功能；函数GetChorm用于获得第i个个体的染色体上的字符串值；函数SetFitness将适应度值写回染色体中；函数Evaluate是用户自己编写的个体的适应度评价方法；函数GetBest获取最优个体。

透明机制

透明的机制是对用户而言的，指的是并行程序员在编写程序时，不必关心任务时如何并行执行的。用户在调用PGA_Skeleton寻找最优解时，只知道问题的解是如何编解码的，而不去涉及遗传进化的整个进程。用户只知道自己用的是一个并行遗传算法骨架，而不去涉及这个算法骨架是调用哪个结构骨架实现并行的。用户只需要熟悉PGA_Skeleton的接口，知道如何获取最优解就足够了。

编码方式

对于编码方式，首先必须是正确的，即保证杂交、变异之后的子代有意义，可以解码得到实际问题的解。适应度评价过程包括解码和评价两个部分，先将染色体上的字符串进行解码，得到有实际意义的解后对解的适应度评价，所以编码方式的选择一定程度上决定了适应度评价函数的程序编写方法。

编码方式的选择在一定程度决定了杂交和变异操作，所以为了算法骨架的自动化编程，必须将编码方式做一定程度的固定。常见的编码方式按照表达形式可以分成二进制、整数、实数；按照维数可以分成一维、二维。让用户在现有的进制和维数上进行选择，而不是任意的编码方式，我们也可以把我们选择使用的编码方式称为固定码。

遗传算子

PGA_Skeleton内部包括选择、杂交、变异算子。其中既可以采用一些传统的方法，如轮盘选择、锦标赛选择、单点两点杂交、换位变异等，也可以采用一些现代方法，如非均匀变异和蠕变等，这些都与实际应用问题无关。

开放原则

各遗传算子的修改不会影响骨架的整体结构，所以在需要对并行遗传算法调整时，可以按照需求更换遗传算子，PGA_Skeleton的升级是很方便的。这些都说明并行算法骨架是开放的。

并行遗传算法骨架是解决遗传算法并行的一种行之有效的手段。PGA_Skeleton 是开放的，其中的遗传算子还可以引入一些现代化的方法，如均匀交叉，蠕变等，用以达到提高更好的进化效果。由于该算法骨架的并行实现依赖于结构骨架的实现，但是目前结构骨架库中目前仅提供了FARM和Data Parallel两种合适的结构骨架可供选择，所以进一步的工作将放在组合骨架设计的研究上，以便提供组合骨架的支持，从而实现混合并行遗传算法模型。