发布时间 : 星期六 文章遗传算法基础知识更新完毕开始阅读548e4f6027d3240c8547ef04
遗传算法（GENETIC ALGORITHM，GA）
一、遗传算法的特点：
1、 遗传算法的操作对象是一组可行解，而非单个可行解；搜索轨道有多条，而非单条，因而具有良好的并行性。
2、 遗传算法只需要利用目标的取值信息，而无需梯度等高价值信息，因而适用于任何大规模、高度非线性的不连续多峰函数的优化以及无解析表达式的目标函数的优化，具有很强的通用性。
3、 遗传算法择优机制是一种软选择，加上其良好的并行性，使它具有良好的全局优化和稳健性。
4、 遗传算法操作的可行解是经过编码化的（通常采用二进制编码），目标函数解释为编码化个体（可行解）的适应值，因而具有良好的可操作性和简单性。 二、遗传算法的发展与现状
遗传算法的产生归功于美国的Michigan大学的Holland在20世纪60年代末、70年代初的开创性，其本意是在人工适应系统中设计的一种基于自然演化原理搜索机制。大约在同一时代，Foegl和Rechenberg及Schwefel,引入了另两种基于自然演化原理的算法，演化程序（evolutionary programming）和演化策略(evolution strategies).这三种算法构成了目前演化计算(evolutionary computation)领域的三大分支，它们从不同层次、不同角度模拟自然演化原理，以达到求解问题的目的。Holland不仅设计了遗传算法的模拟与操作原理，更重要的是他运用统计策略理论对遗传算法的搜索机理进行了理论分析，
1
建立了著名的Schema定理和隐含并行（implicit parallelism）原理，为遗传算法奠定了基础。遗传算法应用于函数优化始于De Jone的在线（one-line）和离线（off-line）指标仍是目前衡量遗传算法性能的主要手段。
1、 遗传算法在神经网络、模糊系统和机器学习中的应用
神经网络的学习包含两个优化过程，分别是网络连接权重的优化和网络拓扑结构的优化。优化连接权重最著名的方法是Rumelhart提出的基于梯度下降法的反向传播法（backpropagation,BP）。BP算法的最大弱点是局部极小问题和无法学习网络拓扑结构。作为一种通用性和全局性良好的优化技术，遗传算法用于神经网络的训练就是很自然的事情。遗传算法用于神经网络的学习可分为三个不同的层次：连接权重的学习规则的学习。目前遗传算法已经广泛用于前向网络（feedward networks）、径向基网络（radial basis function networks）、Kohonen特征映射及Recurrent网络等各种人工神经网络的训练与设计中。演化神经网络（evolutionary artificial neural networks）作为一种一般的自适应学习模型加以研究。
被Zedeh 称作软计算（soft computing）的两大组成部分——遗传算法与模糊系统的相互融合也是近年人们关注的话题。模糊系统是对人类处理模糊性概念极其推理机制的模拟。最初，在模糊系统设计中，推理方法的选取、隶属函数形状及参数的选取、相关权重的确定以及规则的确定，均是由专家根据实际经验经验指定的。模糊神经网络（fuzzy neural networks）.遗传算法已成功应用于隶属函数形状与参
2
数优化，系统相关权重的优化以及推理规则的选取。此外，模糊集技术也被用于遗传算法的某些GA的新型遗传算法，以达到改进经典遗传算法的目的。
大多数机器学习系统都有一个共同的特征，即具备对自身结构进行调整的能力，从而达到改进性能的、发现并利用有意义的概念，或改进其内部知识结构的一致性和通用性。分类系统（classifer system）是遗传算法与机器学习经典的生产系统（production system）相结合的产物。遗传算法也用于导师概念学习（supervised concept learing）、特征选取与重构及强迫学习(reinforcement learing)等机器学习领域。 2、 遗传算法设计与执行策略
遗传算法操作的是一群编码化的可行解，称作种群。它通过种群的更新与迭代来搜索全局最优解。种群的迭代是通过选择、杂交和变异等具有生物意义的遗传算子来实现的。在Holland的最初模型中采用的是二进制定长编码和固定种群，遗传算法的主要形式为比例选择、单点杂交和位变异。近年的发展： （1） 编码方法
灰色编码可用于克服二进制编码映射的不连续问题（即欧氏空间中邻近点的二进制编码在Hamming距离下并不邻近）。动态参数编码（dynamic parameter encoding）提出是为了克服搜索效率与表示时间精度间的矛盾，同时对克服过早收敛现象。此外，多值编码、实值编码、区间编码、Delta编码等多种编码方法也各有优缺点。 （2） 选择机制
3
选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。选择压(selective pressure)描述了选择机制挑选种群中不同个体做母体的概率大小的差异。选择压过大，会造成几个较好可行解（不一定是近似全局最优解）迅速抢占了整个种群；选择压过小，则会使算法呈现出纯粹的随机徘徊行为。秩选择、适应值函数的尺度变换均是为了克服经典的比例选择所造成的选择压过大或过小而设计的。杰出者选择(elitist selection)则通过无条件地保留每代种群中最优者而克服选择下遗传算法不能依靠概率收敛到全局最优解的问题。杂交和变异是遗传算法最具争议的两种机制。争论的焦点是：单点杂交、多点杂交的优劣；杂交机制与变异机制的优劣。经典的观点强调杂交的作用，而认为变异只是一个背景机制，并认为在杂交机制中强度最弱的单点杂交是最好的。强调杂交作用的观点是基于遗传算法中著名的建筑块假设(building block hypothesis),而这一假设并末得到证明。 （3） 杂交与变异机制
除了关于世代GA（generation GA）和稳定状态GA(steady state GA)的比较仍在研究。 （4） 执行策略的改进
1、 遗传算法与模拟退火算法的结合
模拟退火(simulated annealing)是一种基于热力学理论的优化方法，并有着完善的全局收敛理论。在遗传算法中已各种形式融入模拟退火思想，从而使得遗传算法在理论上具有全局收敛次性。 2、 遗传算法与局部优化方法的结合
4