下载文档原格式
第四章遗传算法在经济活动中，很多实际优化问题涉及到大量参数的优化，或者寻找问题的全局最优解。
这些问题不仅仅涉及大量计算，而且往往难以给出精确的数学模型，或者有了数学模型，也难以求出解析解来。
有的搜索问题还面临着组合爆炸，常规算法无法应付。
这些困难使得一些学者们寻求一种适于大规模并行且具有某些智能特征如自组织、自适应、自学习等的算法。
遗传算法（Genetic Algorithm, GA）就是一种伴随解决此类复杂的、非线性问题而发展起来的广为应用的、高效的随机全局搜索与优化的自适应智能算法。
第一节引言一、遗传算法的生物学意义遗传算法的生物学基础是达尔文进化论和孟德尔遗传变异理论。
根据达尔文进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。
生物种群从低级、简单的类型逐渐发展成为高级、复杂的类型。
各种生物要生存下去就必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。
具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少，直至消亡。
达尔文把这一过程和现象叫做“自然选择、适者生存”。
按照孟德尔遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。
不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。
经过优胜劣汰的自然选择，适应值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基本规律。
现代遗传学则对基因的本质、功能、结构、突变和调控进行了深入探讨，开辟了遗传工程研究的新领域。
在一定的环境影响下，生物物种通过自然选择、基因交换和变异等过程进行繁殖生长，构成了生物的整个进化过程。
生物进化过程的发生需要四个基本条件：(1)存在由多个生物个体组成的种群；(2)生物个体之间存在着差异，或群体具有多样性；(3)生物能够自我繁殖；(4)不同个体具有不同的环境生存能力，具有优良基因结构的个体繁殖能力强，反之则弱。
2.遗传算法随着优化理论的发展，一些新的智能算法得到了迅速发展和广泛应用，成为解决传统系统辨识问题的新方法，如遗传算法、蚁群算法、粒子群算法、差分进化算法等。
这些算法丰富了系统辨识技术，这些优化算法都是通过模拟揭示自然现象和过程来实现的，其优点和机制的独特，为具有非线性系统的辨识问题提供了切实可行的解决方案。
本章介绍遗传算法解决参数辨识问题。
2.1 遗传算法的基本原理遗传算法简称GA（Genetic Algorithms），是1962年由美国密歇根大学Holland 教授提出的模拟自然界遗传机制和生物进化论而成的一种并行随机搜索最优化方法。
遗传算法是以达尔文的自然选择学说为基础发展起来的。
自然学说包括以下3个方面。
（1）遗传这是生物的普遍特征，亲代把生物信息交给子代，子代按照所得信息而发育、分化，因而下代总是和亲代具有相同或相似的性状。
生物有了这个特征，物种才能稳定存在。
（2）变异亲代和子代之间及子代的不同个体之间总有些差异，这种现象成为变异。
变异是随机发生的，变异的选择和积累是生命多样性的根源。
（3）生存斗争和适者生存自然选择来自繁殖过剩和生存斗争。
由于弱肉强食的生存斗争不断的进行，其结果是适者生存，既具有适用性变异的个体被保存下来，不具有适应性变异的个体被淘汰，通过一代代的生存环境的选择作用，性状逐渐与祖先有所不同，演变为新的物种。
这种自然选择是一个长期的、缓慢的、连续的过程。
遗传算法将“优胜劣汰，适者生存”的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适配值函数并通过遗传中复制、交叉以及变异对个体进行筛选，使适配值高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。
这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。
遗传算法的算法简单，可并行处理，并能得到全局最优解。
遗传算法的基本操作分为如下三种：（1）复制（Reproduction Operator）复制是从一个旧种群中选择生命力强的个体位串产生新种群的过程。
遗传粒子群优化算法混合遗传算法（Genetic Algorithm，GA）和粒子群优化算法（Particle Swarm Optimization，PSO）是两种常见的进化优化算法，它们各自有着优点和不足。
为了充分发挥它们的优势并弥补其不足之处，研究者们对这两种算法进行了混合。
本文将详细介绍遗传粒子群优化算法混合的相关内容。
首先，我们来了解一下遗传算法和粒子群优化算法的原理和特点。
遗传算法是一种模拟生物进化过程的优化算法，其基本思想是通过生物进化中的遗传、变异和选择等算子来最优解。
遗传算法通常由编码、适应度评价、选择、交叉和变异等步骤组成。
编码将待优化问题的解表示为染色体，适应度评价函数用于度量染色体的优劣，选择算子根据适应度选择个体进行繁殖，交叉算子和变异算子模拟生物的遗传和变异操作。
粒子群优化算法是一种模拟鸟群觅食行为的优化算法，其基本思想是通过多个粒子在解空间中的和迭代来找到最优解。
每个粒子都有自己的位置和速度，通过更新速度和位置来不断调整方向和距离。
粒子群优化算法主要包括初始化粒子群、更新速度和位置、更新最优个体和全局最优个体等步骤。
遗传粒子群优化算法混合的基本思想是将粒子群优化算法的能力和遗传算法的全局优化能力结合起来，形成一种新的混合优化算法。
具体来说，在遗传算法的基础上引入粒子群优化算法的思想和操作，使得算法能够更好地在空间中寻找到全局最优解。
将遗传算法和粒子群优化算法进行混合有以下几种常见的方式：1.遗传算法与粒子群优化算法交替使用：先使用遗传算法进行初始化种群和进行交叉变异操作，然后再使用粒子群优化算法进行和更新操作。
通过交替使用这两种算法，可以综合利用它们的优点，提高算法的效率和精度。
2.遗传算子和粒子群优化算法算子的融合：将遗传算法和粒子群优化算法的算子进行融合，形成一种新的算子。
例如，可以将遗传算法的交叉操作与粒子群优化算法的速度更新操作相结合，形成一种新的交叉操作方式；或者将遗传算法的变异操作与粒子群优化算法的位置更新操作相结合，形成一种新的变异操作方式。
组合优化问题的遗传算法求解一、简介组合优化问题指的是在有限个元素中选取某些元素，以达到最优化的目标。
组合优化问题的求解在实际中应用广泛，如旅行商模型、调度问题、网络优化等领域。
但是这类问题求解面临着复杂度高、难以精确求解等困难。
在这种情况下，遗传算法是一种有效的求解方法。
遗传算法是一种基于达尔文进化论的计算方法，通过模拟生物进化的方式求解组合优化问题。
本文将介绍遗传算法在组合优化问题求解中的应用，着重介绍遗传算法基本框架、编码方法、适应度函数的构建以及遗传算法的优化策略等。
二、遗传算法基本框架遗传算法的求解过程主要包括初始种群生成、适应度评价、选择操作、交叉操作和变异操作等基本步骤。
（1）初始种群生成遗传算法首先需要生成一定数量的初始种群，初始种群可以通过随机生成或其他启发式算法生成。
例如，在旅行商问题中，初始种群可以随机生成多条路径。
（2）适应度评价适应度函数是遗传算法的核心，适应度函数的构建直接关系到遗传算法的性能。
适应度函数是对每个染色体的优劣进行量化评价，用以指导后续优化操作。
适应度函数构建需要根据问题特点进行设计。
（3）选择操作选择操作是指将上一代种群中的某些个体复制到下一代种群中，个体复制的概率与其适应度大小有关。
适应度越高的个体被选择的概率越大，从而使适应度高的个体更有机会进化到下一代。
选择操作可以通过轮盘赌选择、锦标赛选择等方式实现。
（4）交叉操作交叉操作是指对选择后的个体进行杂交，交叉操作是遗传算法的核心，它通过随机杂交个体的染色体，产生新的杂交染色体，从而增加搜索空间。
交叉操作可分为单点交叉、多点交叉、均匀交叉等。
（5）变异操作变异操作是指在交叉操作之后对个体发生变异，从而产生新的个体。
变异操作是通过随机改变染色体中的基因，从而增加多样性。
变异操作可以是简单变异、非一致变异、高斯变异等。
以上是遗传算法的基本框架，遗传算法的性能因素有适应度函数的设计、进化代数、群体大小、交叉概率、变异概率等。
混合遗传算法混合遗传算法是一种非常有效的优化算法，它利用遗传算法（GA）和其他有效的优化技术来搜索高质量的最优解。
因此，混合遗传算法可用于优化复杂的实际问题，特别是那些无法直接使用标准遗传算法进行优化的问题。
近些年来，混合遗传算法在优化理论方面受到了越来越多的关注。
混合遗传算法是一种混合优化算法，它将两个不同的优化算法结合在一起，因此它可以从一种优化算法中获得灵活性，从另一种优化算法中获得强大的搜索性能。
两个典型的混合遗传算法分别是遗传算法和模拟退火算法之间的混合算法，以及遗传算法和粒子群算法之间的混合算法。
虽然遗传算法具有良好的搜索性能，但是它也有一些缺点，如低收敛速度，结果容易陷入局部最优解，它过于依赖随机性，因此收敛性较差。
但模拟退火算法具有良好的收敛性能，但它也有它自己的缺点，如极限搜索性能较差，容易陷入停滞状态，尤其是在遇到非凸优化问题时，它在解决问题中有一定的局限性。
因此，为了克服这些缺点，混合遗传算法的出现是一个很好的选择。
一般来说，混合遗传算法的工作流程如下：首先，利用遗传算法从原初解空间中生成一组初始解；其次，从这组初始解中，按照给定的进化策略，交叉和变异形成新一代解；最后，用另一种优化算法对最后一代解进行精调，最终得到一个非常有效的最优解。
混合遗传算法在优化理论方面有着巨大的应用前景。
它可以解决复杂的实际问题，如模式识别、工程设计、系统优化、机器学习等。
典型的应用包括仿真优化、工程设计优化以及航空机应力及耐久性优化等。
混合遗传算法还可以解决多种非线性优化问题，例如模糊系统优化、非凸优化等。
由于混合遗传算法具有灵活性和强大的搜索性能，它可以有效地解决多种类型的复杂问题，这使得混合遗传算法在实际应用中特别有用。
然而，混合遗传算法也有自己的局限性。
首先，由于混合遗传算法需要使用两种不同的优化算法，因此它所需的计算能力较大，需要解决的算法问题也会变得更加复杂。
其次，混合遗传算法的参数参数化也很复杂，需要有一定的经验来针对特定的优化问题才能调整正确的参数。
求解不可微函数优化的一种混合遗传算法
摘要在浮点编码遗传算法中加入Powell方法，构成适于不可微函数全局优化的混合遗传算法。
混合算法改善了遗传算法的局部搜索能力，显著提高了遗传算法求得全局解的概率。
由于只利用函数值信息，混合算法是一种求解可微和不可微函数全局优化问题的通用方法。
关键词全局最优；混合算法；遗传算法；Powell方法
1 引言
不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内最大应力最小而归结为极大极小优化（minmax）问题、数据鲁棒性拟合中采取最小绝对值准则建立失拟函数等。
其求解方法的研究越来越受到人们的重视，常用的算法有模式搜索法、单纯形法、Powell方法等，但是这些方法都是局部优化方法，优化结果与初值有关。
近年来，由Holland研究自然现象与人工系统的自适应行为时，借鉴“优胜劣汰”的生物进化与遗传思想而首先提出的遗传算法，是一种较为有效的求不可微非线性函数全局最优解的方法。
以遗传算法为代表的进化算法发展很快，在各种问题的求解与应用中展现了其特点和魅力，但是其理论基础还不完善，在理论和应用上暴露出诸多不足和缺陷，如存在收敛速度慢且存在早熟收敛问题[1,2]。
为克服这一问题，早在1989年Goldberg就提出混合方法的框架[2]，把GA与传统的、基于知识的启发式搜索技术相结合，来改善基本遗传算法的局部搜索能力，使遗传算法离开早熟收敛状态而继续接近全局最优解。
近来，文献[3]和[4]在总结分析已有发展成果的基础上，均指出充分利用遗传算法的大范围搜索性能，与快速收敛的局部优化方法结合构成新的全局优化方法，是目前有待集中研究的问题之一，这种混合策略可以从根本上提高遗传算法计算性能。
文献[5]采用牛顿－莱佛森法和遗传算法进行杂交求解旅行商问题，文献[6]把最速下降法与遗传算法相结合来求解连续可微函数优化问题，均取得良好的计算效果，但是不适于不可微函数优化问题。
本文提出把Powell方法融入浮点编码遗传算法，把Powell方法作为与选择、交叉、变异平行的一个算子，构成适于求解不可微函数优化问题的混合遗
传算法，该方法可以较好解决遗传算法的早熟收敛问题。
数值算例对混合方法的有效性进行了验证。
2 混合遗传算法
编码是遗传算法应用中的首要问题，与二进制编码比较，由于浮点编码遗传算法有精度高，便于大空间搜索的优点，浮点编码越来越受到重视[7]。
考虑
非线性不可微函数优化问题(1)，式中
min
step1 给遗传算法参数赋值。
这些参数包括种群规模m，变量个数n，交叉概率p c、变异概率p m，进行Powell搜索的概率p Powell和遗传计算所允许的最大
代数T。
Step2 随机产生初始群体，并计算其适应值。
首先第i个个体适应值取为f i’=f max - f i，f i是第i个个体对应的目标函数值，f max为当前种群成员的最大目标函数值，i=1,2,…,m。
然后按Goldberg线性比例变换模型[2]式(2)进行拉伸。
f i ’= a⋅f
i
’+b（f
i
≥ 0 ） (2)
step3 执行比例选择算子进行选择操作。
step4 按概率
step5 按照概率
step6 对每个个体按照概率p Powell进行Powell搜索。
若个体
step7 计算个体适应值，并执行最优个体保存策略。
step8 判断是否终止计算条件，不满足则转向step3，满足则输出计算结果。
作为求解无约束最优化问题的一种直接方法，Powell法的整个计算过程由若干轮迭代组成，在每一轮迭代中，先依次沿着已知的n个方向搜索，得一个最好点，然后沿本轮迭代的初始点与该最好点连线方向进行搜索，求得这一阶段的最好点。
再用最后的搜索方向取代前n个方向之一，开始下一阶段的迭代。
为了保持算法中n个搜索方向是线性无关的，保证算法的收敛性，对替换方向的规则进行改进，在混合法的计算步骤step6中采用文[9]中的改进Powell方法，其求解过程如下：
(1) 变量赋初值
(2) 令
(3) 求
(4) 若
函数f(x)有相当多的极小点,全局极小点是
采用改进的Powell方法计算100次，初值在区间[-500,500]内随机产生，只有6次（即以概率0.06）搜索到全局最优，计算成功的概率极低。
Holland建立的标准（或简单）遗传算法，其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。
取种群规模
m=30，交叉概率p
=0.95、变异概率p m=0.05，最大进化代数T=1000，每个变量
c
用串长为L=16的二进制子串表示。
二进制编码比浮点编码遗传算法计算精度低，对于标准遗传算法以目标函数小于-800为搜索成功，标准遗传算法运行100次。
当取最大进化代数为T=200时，40次（以概率0.40）搜索到全局最优，平均计算时间为0.51秒；当取T=500时，51次（以概率0.51）搜索到全局最优，平均计算时间为1.13秒。
采用本文混合法计算，取m=30，p c=0.85、p m=0.2，T=100，进行Powell搜索的概率p Powell取不同值，混合法运行100次，计算结果见如表1。
对于这个具有多极值的算例，多次计算表明p Powell=0.3时，混合法能以完全概率搜索到全局最优的准确值，但是此时混合法计算时间约为标准遗传算法取T=500时计算时间的4/5。
对应的浮点编码遗传算法，取m=30，p c=0.85、p m=0.2，T=100，运行100次，82次（以概率0.82）搜索到全局最优（如表1中P Powell=0所示），计算时间约为标准遗传算法取T=500时计算时间的1/8，但是搜索到全局最优的概率却远远高于标准遗传算法。
表1 p Powell取不同值时混合法的计算结果
P Powell
0.0
0.02
0.05
0.1
0.2
0.3
求得最优解的次数
82
85
89
94
98
100
求得最优解的概率
0.82
0.85
0.89
0.94
0.98
1.00
平均计算时间/秒
0.14
0.20
0.31
0.47
0.68
0.87
4 结束语
针对不可微函数的全局优化问题，本文提出一种把Powell方法与浮点编码遗传算法相结合的混合遗传算法，该算法兼顾了遗传算法全局优化方面的优势和Powell方法局部搜索能力较强的特点，提高求得全局解的概率。
计算结果表明混合法优于遗传算法和Powell法，可以可靠地搜索到具有多个局部极值的函数优化问题的全局解。
由于计算中只用到函数值信息，本文混合法不仅适用于不可微函数优化问题，也适合可微函数全局优化问题。
参考文献
[1]周明，孙树林．遗传算法原理及应用[M]．北京：国防工业出版社，1999．
[2]Goldberg D E. Genetic algorithms in search, optimization and machine learning[M].
Reading, Ma: Addison Wesley,1989．
[3]孟庆春，贾培发．关于Genetic算法的研究及应用现状[J]．清华大学出版社，1995，35(5)：44。
