并行遗传算法在智能优化算法中的应用

GA的内在并行性在Holland提出GA时就得到了认识，因此，在并行计算机上实现GA是提高算法性能和效率的有效途径。Grefenstette（1981）对GA并行化实现的结构问题进行了全面研究，并给出了多种结构形式，在此仅对其中最基本的三种并行方案进行简单阐述。

1.同步主仆式

遗传算法的同步主仆式并行执行方案，如图2.3所示。

图2.3　同步主仆式并行遗传算法框图

在这种并行方式中，一个主过程协调若干个仆过程。其中，主过程控制选择、交叉和变异的执行，仆过程仅执行适配值的计算。这种并行化方式很直观，且易于实现，但是也存在两个主要的缺点：若各仆过程计算适配值的时间存在明显差异时，将会造成整个系统长时间的等待；整个系统可靠性较差，对主过程状况的依赖性较大。

2.异步并发式

遗传算法的异步并发式并行执行方案，如图2.4所示。

(www.xing528.com)

图2.4　异步并发式并行遗传算法框图

在这种并行方式中，通过存取一个共享存储器，若干个同样的处理机彼此无关地执行各个遗传算子和适配值的计算。只要存在一个并行进程，同时共享存储器可继续运行，则整个系统就可以进行有效的处理。显然，这种方式不易实现，但可以大大提高系统的可靠性。

3.网络式

遗传算法的网络式并行执行方案，如图2.5所示。

图2.5　网络式并行遗传算法

在这种并行方式中，若干个无关的遗传算法分别在独立的存储器上进行独立的遗传；操作和适配值计算，同时各个子群体在每一代中发现的最佳个体通过相应的通信网络传送给其他子群体。与前两种方式相比较，由于存在通信时的间断，该方式的连接带宽缩小了。但是，由于各独立过程的自治性，系统的可靠性提高了。