神经网络与智能信息处理

四．遗传算法

遗传算法（Genetic Algorithm ：GA）是模拟生物的进化现象（自然、淘汰、交叉、突然变异）的一种概率搜索和最优化方法。是模拟自然淘汰和遗传现象的工程模型。

GA的历史可追溯到1960年，明确提出遗传算法的是1975年美国Michigan大学的Holland博士，他根据生物进化过程的适应现象，提出如下的GA模型方案：

1．将多个生物的染色体（Chromosmoe）组成的符号集合，按文字进行编码，称为个体。

2．定义评价函数，表示个体对外部环境的适应性。其数值大的个体表示对外部环境的适应性高，它的生存（子孙的延续）的概率也高。

3．每个个体由多个“部分”组合而成，每个部分随机进行交叉及突然变异等变化，并由此产生子孙（遗传现象）。

4．个体的集合通过遗传，由选择淘汰产生下一代。

遗传算法提出之后，很快得到人工智能、计算机、生物学等领域科学家的高度重视，并在各方面广泛应用。1989年美国Goldberg博士发表一本专著：“Genetic Algorithms in Search，Optimization and Machine Learning”。出版后产生较大影响，该书对GA的数学基础理论，GA的基本定理、数理分析以及在搜索法、最优化、机器学习等GA应用方面进行了深入浅出的介绍，并附有Pascal模拟程序。

1985年7月在美国召开第一届“遗传算法国际会议”（ICGA）。以后每隔两年召开一次。近年来，遗传算法发展很快，并广泛应用于信息技术的各个领域，例如：

智能控制：机器人控制。机器人路径规划。

工程设计：微电子芯片的布局、布线；通信网络设计、滤波器设计、喷气发动机设计。

图象处理：图象恢复、图象识别、特征抽取。

调度规划：生产规划、调度问题、并行机任务分配。

优化理论：TSP问题、背包问题、图划分问题。

人工生命：生命的遗传进化以及自增殖、自适应；免疫系统、生态系统等方面的研究。

神经网络、模糊集理论和以遗传算法为代表的进化算法都是仿效生物信息处理模式以获得智能信息处理功能的理论。三者目标相近而方法各异；将它们相互结合，必能达到取长补短、各显优势的效果。例如，遗传算法与神经网络和模糊计算相结合方面就有：

☆神经网络连续权的进化。

传统神经网络如BP网络是通过学习，并按一定规则来改变数值分布。这种方法有训练时间过长和容易陷入局部优化的问题。采用遗传算法优化神经网络可以克服这个缺点。

☆神经网络结构的进化。

目前神经网络结构的设计全靠设计者的经验，由人事先确定，还没有一种系统的方法来确定网络结构，采用遗传算法可用来优化神经网络结构。

☆神经网络学习规则的进化。

采用遗传算法可使神经网络的学习过程能够适应不同问题和环境的要求。

☆基于遗传算法的模糊推理规则的优化，以及隶属度函数的自适应调整也都取得很好效果。

上述神经网络、模糊计算、遗传算法和混沌理论等都是智能信息处理的基本理论和方法。近年来学术界将它们统称为“计算智能”。有关这方面更详细的内容，可参阅我们编著的下列著作：

“神经网络与神经计算机”（1992年科学出版社出版）

“遗传算法及其应用” （1996年邮电出版社出版）

“混沌、分形及其应用” （科大出版社出版）