遗传算法介绍

㈠ 遗传算法具体应用

1、函数优化

函数优化是遗传算法的经典应用领域，也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。

2、组合优化

随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。

此外，GA也在生产调度问题、自动控制、机器人学、图象处理、人工生命、遗传编码和机器学习等方面获得了广泛的运用。

3、车间调度

车间调度问题是一个典型的NP-Hard问题，遗传算法作为一种经典的智能算法广泛用于车间调度中，很多学者都致力于用遗传算法解决车间调度问题，现今也取得了十分丰硕的成果。

从最初的传统车间调度（JSP）问题到柔性作业车间调度问题（FJSP），遗传算法都有优异的表现，在很多算例中都得到了最优或近优解。

(1)遗传算法介绍扩展阅读：

遗传算法的缺点

1、编码不规范及编码存在表示的不准确性。

2、单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。

3、遗传算法通常的效率比其他传统的优化方法低。

4、遗传算法容易过早收敛。

5、遗传算法对算法的精度、可行度、计算复杂性等方面，还没有有效的定量分析方法。

㈡ 十进制遗传算法简介

8.2.1 反演优化问题

用遗传算法反演水文地质参数^{［38，61］}，首先要构造优化问题。设区域有m个观测值，则构造误差函数为：

含水层参数识别方法

其中：为实测值，h_i （p₁，p₂，…，p_n）为计算值。和h_i 具有相同的时间和坐标点，p₁，p₂，…，p_n 为参数，为书写方便记 P=[p₁，p₂，…，p_n]。

模型选定之后，通过改变参数使误差函数达到最小值。那么本问题就转化为约束条件下的优化问题（8-2）。

含水层参数识别方法

8.2.2 遗传算法步骤

可用遗传算法求解优化问题（8-2），具体步骤如下。

1）解的表示结构。用十进制浮点向量，表示优化问题的解。每个染色体由一个浮点向量表示，其长度和解向量相同。这里用（p₁，p₂，…，p_n）表示最优化问题（8-2）的解。相应的染色体为V=（p₁，p₂，…，p_n）。

2）初始化过程。定义整数Pop-Size作为染色体的个数，并且随机产生Pop-Size个初始染色体。从优化问题的约束条件可以看出，（p₁，p₂，…，p_n）的可行域是一个长方形，我们用随机的方法可以得到Pop-Size个初始可行的染色体。

检验（p₁，p₂，…，p_n）是否为可行染色体，如果是，就保留。如果不是就再产生一组可行染色体。直到产生Pop-Size个初始可行的染色体V₁，V₂，…，V_Pop-Size。

3）评价函数。评价函数（用eval（V）表示）用来对种群中的每个染色体V设定一个概率，以使该染色体被选择的可能性与其种群中其他染色体的适应性成比例。通过轮盘赌，适应性强的染色体被选择产生后代的机会大。在实际应用中我们采取如下方法确定评价函数。

设目前该代中的染色体为V₁，V₂，…，V_Pop-Size，可以根据染色体的序进行再分配，无论采用何种数学规划均可以将染色体由好到坏进行重排，就是说，一个染色体越好，其序号越小。设参数α∈（0，1）给定，定义于序的评价函数为：

含水层参数识别方法

i=1意味着染色体是最好的，i=Pop-Size说明是最差的。

4）选择过程。选择过程是以旋转赌轮Pop-Size次为基础的。每次旋转都为新的种群选择一个染色体。赌轮是按每个染色体的适应度进行选择染色体的。其过程如下。

A.对每个染色体V_i，计算累积概率q_i

含水层参数识别方法

B.从区间（0，q_Pop-Size）中产生一个随机数r。

C.若q_i-1＜r≤q_i，则选择第i个染色体V_i（1≤i≤Pop-Size）。

D.重复步骤②和步骤③共Pop-Size次，这样可以得到Pop-Size个复制的染色体。上述过程并没有要求满足条件q_Pop-Size=1。实际上，可以用q_Pop-Size除以所有的q_i，使q_Pop-Size=1，新得到的概率同样与适应度成比例。

5）交叉操作。设P_c为交叉操作的概率，这个概率说明种群中有期望值为P_c·Pop

-Size个染色体进行交叉操作。为确定交叉操作的父代，从i=1到Pop-Size重复以下过程：从［0，1］中产生随机数r，如果r＜P_c，则选择V_i作为一个父代。

用V′₁，V′₂，V′₃，…表示上面选择的父代，并把他们随机分为交叉对。

（V′₁，V′₂），（V′₃，V′₄），（V′₅，V′₆），…

现仅以第一对为例说明交叉操作的过程，从（0，1）区间产生一个随机数c，然后按下式进行交叉操作，并产生两个后代X和Y

X=cV′₁+（1-c）V′₂，Y=（1-c）V′₁+cV′₂

检验新产生的后代是否为可行解，如果可行，用它们代替父代；否则，保留其中可行的。然后，产生新的随机数c，重新进行交叉操作，直到得到两个可行的后代为止。

6）变异操作。设参数P_m为遗传操作中的变异概率，为确定变异操作的父代，从i=1到Pop-Size重复以下过程：从［0，1］中产生随机数r，如果r＜P_m，则选择V_i作为一个变异父代。先选择一个变异方向D，M为一个随机数，则可以用下式：

X=V+M·D

为新后代，检验X是否为可行解。如不可行，改变随机数M或变异方向D直到X为可行解为止。

另一种产生变异的操作是在可行域中另外产生一个染色体，或染色体中的一个元素。

7）遗传算法的一般过程。遗传算法的一般过程可归纳如下：

输入参数Pop-Size，P_c，P_m；

通过初始化过程产生Pop-Size个染色体；

重复

根据某抽样机制选择染色体；

对染色体进行交叉和变异操作；

计算所有染色体的评价函数；

满足终止条件时终止，否则重复以上三个过程。

㈢ 基本的遗传算法

在许多实际应用领域，无论是工程技术科学还是社会经济科学中，都会遇到全局最优化问题^{[53，56～59，61]}，这一类问题大多数可以形式化为一个对（S，f）的寻优问题，其中 S⊂R ⁿ 是 R ⁿ 中的有界集，f∶S→R是 n 维实值函数。所要求解的问题就是要找到一点 x _best∈S，使得 f（x_best）是 S 上的全局最优解，可以是极大值或极小值。以极小值为例，即求一点 x _min∈S，满足

含水层参数识别方法

尽管人们对这类问题进行了大量的研究，但得到的成绩仍不能令人满意，目前只能解决一些简单的问题。对于更复杂的全局最优化问题，通常是利用数值解法，但许多数值解法都不能找到最优解，只是返回一个接近于全局最优的值。

全局最优化数值方法可以分为两大类：确定性算法和随机算法。在随机算法中，最优化步骤在一定程度上依赖于概率事件，它排除了确定性算法中的一个最大障碍——预先详细说明一个问题的全部特征并针对问题的特征决定算法应采用的对策。与常规的优化算法相比，遗传算法有可能在更大的范围内探寻问题潜在的解。确定性算法没有用到概率信息。只有当对S上进行穷举搜索及对f规定附加的假设条件下，算法才能找到全局最优解。实行穷举搜索在很多情况下（如实数解）是不可能的，因此多采用对f规定附加的假设条件，这必然影响到最终解的可靠性。在这些算法中，搜索速度越快的算法往往意味着需要对f做更多的假设，或者不能保证搜索成功。与此相对照，许多随机算法都可以证明在概率意义下渐近收敛到全局最优解，即这些算法保证以概率1渐近收敛，而且随机算法的计算结果一般要优于那些确定性算法的结果。遗传算法就是其中具有代表性的随机算法。

常用的遗传算法操作有选择（Selection）、交叉（Crossover）、变异（Mutation）。复制是直接将个体的代码进行拷贝形成新个体。下面就选择、交叉与变异操作做一介绍。

7.3.1 选择过程

选择过程是以旋转赌轮Pop-Size次（种群规模，即群体中个体的总个数）为基础，每次旋转都为新的种群选择一个染色体。首先计算出个体i被选择的概率P_i，优秀的染色体其选择概率大，然后根据选择概率的大小将一个圆盘分为Pop-Size个扇形，每个扇形的中心角的大小为2πP_i。

每次进行选择时，先选择赌轮边界旁一个不动的参考点，赌轮随机地转动，若不动点停留在扇形j内，则选择个体j。个体的适应值越大，被选择的概率越大，从而其染色体被遗传到下一代的概率越大。

赌轮式选择的特点是对于种群内的所有个体，无论其适应值大小，都有被选择的机会。适应值大的个体被选择的概率大，适应值小的个体被选择的概率小。经过选择后适应值大的个体在种群中的数目会增加。这正体现了适者生存的原则。

7.3.2 交叉操作

交叉操作是个有组织的、随机的字符串间的信息交换过程。假设群体G（t）是模式库。历史信息以每个模式实例数目的形式存储于G（t）中。交叉作用产生模式库中已有模式的新的实例，同时也产生新的模式。简单的交叉操作分为三步：

（1）从当前群体G（t）中选择两个个体结构：A=a₁a₂…a_n，B=b₁b₂…b_n；

（2）以交叉概率 P_c 随机选择一个整数 x∈{1，2，…，n}；

（3）交换A和B中位置x右边的元素，产生两个新的个体结构：a₁a₂…a_xb_x+1…b_n和b₁b₂…b_xa_x+1…a_n。

7.3.3 变异操作

对于群体G（t）中的每个个体A=a₁a₂…a_n，简单的变异操作过程如下：

1）每个位置的字符变量都有一个变异概率P_m，各位置互相独立，通过随机过程选择发生变异的位置x₁，x₂，…，x_n。

2）产生一个新个体结构 B=a₁ a₂……a_n ，其中是从对应位置x ₁ 的字符变量的值域中随机选择的一个取值。类似地，，…，可以同样得到。

如果每个位置的变异概率等于P_m，那么模式H（阶为o（H））发生一次或多次变异的概率是

含水层参数识别方法

遗传操作除了有选择、交叉、变异等算子外，还有染色体内部复制（Intrachromo-somal plication）、删除、易位（Translocation）、分异（Segregation）等。

㈣ 如何通俗易懂地解释遗传算法

遗传算法，核心是达尔文优胜劣汰适者生存的进化理论的思想。

我们都知道一个种群，通过长时间的繁衍，种群的基因会向着更适应环境的趋势进化，牛B个体的基因被保留，后代越来越多，适应能力低个体的基因被淘汰，后代越来越少。经过几代的繁衍进化，留下来的少数个体，就是相对能力最强的个体了。

那么在解决一些问题的时候，我们能不能学习这样的思想，比如先随机创造很多很多的解，然后找一个靠谱的评价体系，去筛选比较好的解，再用这些好的解像生小宝宝一样生一堆可能更好的解，然后再筛再生，反复弄个几代，得到的说不定就是近似最优解哟

说干就干，有一个经典组合问题叫“背包问题”，我们拿这种思路来试试

“背包问题（Knapsack Problem）是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。”

这个问题的衍生简化问题“0-1背包问题” 增加了限制条件：每件物品只有一件，可以选择放或者不放，更适合我们来举例

这样的问题如果数量少，当然最好选择穷举法

比如一共3件商品，用0表示不取，1表示取，那么就一共有

000 001 010

011 100 101

110 111

这样方案，然后让计算机去累加和，与重量上限比较，留下来的解里取最大即可。

㈤ 遗传算法及其应用的内容简介

本书系统全面地介绍了遗传算法的基本原理、设计方法及其并行实现，以及它在组合优化、机器学习、图像处理、过程控制、进化神经网络、模糊模式识别和人工生命等方面的应用。
本书可作为高等院校计算机、无线电电子学、自动控制、生物医学工程等有关专业高年级学生或研究生的教材和参考书，也可供从事人工智能、信息处理研究和应用的科技人员学习参考。

㈥ 遗传算法有哪些应用

遗传算法的搜索策略和优化搜索方法是不依附于梯度信息及其它的辅助知识，而只需要影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于许多科学。遗传算法的应用领域有很多，下面针对一些主要的应用领域做简单的介绍。

1．函数优化：该领域是遗传算法得以应用的经典领域，同时它也是遗传算法进行性能评价的常用算例，许多人构造出了各种各样复杂形式的测试函数：连续函数和离散函数、凸函数和凹函数、低维函数和高维函数、单峰函数和多峰函数等。对于函数优化问题，如一些非线性、多模型、多目标等函数问题用遗传算法很容易得到较好的结果，而用其他算法则较难。

2．组合优化：由于组合优化问题的搜索空间在不断地增大，有时用枚举法很难得到最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP问题非常有效。比如，在旅行商问题、装箱问题及图形划分等问题上，已经成功得以应用了遗传算法。

㈦ 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群自然进化一样的后生代种群比前代更加适应环境，末代种群中的最优个体经过编码（decoding），可以作为问题近似最优解。

5.4.1 非线性优化与模型编码

假定有一组未知参量

x_i（i=1，2，…，M）

构成模型向量m，它的非线性目标函数为Φ（m）。根据先验知识，对每个未知量都有上下界α_i及b_i，即α_i≤x≤b_i，同时可用间隔d_i把它离散化，使

d_i=（b_i-α_i）/N （5.4.1）

于是，所有允许的模型m将被限制在集

x_i=α_i+jd_i（j=0，1，…，N） （5.4.2）

之内。

通常目标泛函（如经济学中的成本函数）表示观测函数与某种期望模型的失拟，因此非线性优化问题即为在上述限制的模型中求使Φ（m）极小的模型。对少数要求拟合最佳的问题，求目标函数的极大与失拟函数求极小是一致的。对于地球物理问题，通常要进行杀重离散化。首先，地球模型一般用连续函数表示，反演时要离散化为参数集才能用于计算。有时，也将未知函数展开成已知基函数的集，用其系数作为离散化的参数集x_i，第二次离散化的需要是因为每一个未知参数在其变化范围内再次被离散化，以使离散模型空间最终包含着有限个非线性优化可选择的模型，其个数为

地球物理数据处理教程

其中M为未知参数x_i的个数。由此式可见，K决定于每个参数离散化的间隔d_i及其变化范围（α_i，b_i），在大多数情况下它们只能靠先验知识来选择。

一般而言，优化问题非线性化的程度越高，逐次线性化的方法越不稳定，而对蒙特卡洛法却没有影响，因为此法从有限模型空间中随机地挑选新模型并计算其目标函数 Φ（m）。遗传算法与此不同的是同时计算一组模型（开始时是随机地选择的），然后把它进行二进制编码，并通过繁殖、杂交和变异产生一组新模型进一步有限的模型空间搜索。编码的方法可有多种，下面举最简单的例说明之，对于有符号的地球物理参数反演时的编码方式一般要更复杂些。

假设地球为有三个水平层的层次模型，含层底界面深度h_j（j=1，2，3）及层速度v_j（j=1，2，3）这两组参数。如某个模型的参数值为（十进制）：

h₁=6，h₂=18，h₃=28，单位为10m

v₁=6，v₂=18，v₃=28，单位为 hm/s

按正常的二进制编码法它们可分别用以下字符串表示为：

地球物理数据处理教程

为了减少字节，这种编码方式改变了惯用的单位制，只是按精度要求（深度为10m，波速为hm/s）来规定参数的码值，同时也意味着模型空间离散化间距d_i都规格化为一个单位（即10m，或hm/s）。当然，在此编码的基础上，还可以写出多种新的编码字符串。例如，三参数值的对应字节顺序重排，就可组成以下新的二进制码串：

地球物理数据处理教程

模型参数的二进制编码是一种数学上的抽象，通过编码把具体的非线性问题和生物演化过程联系了起来，因为这时形成的编码字符串就相当于一组遗传基因的密码。不仅是二进制编码，十进制编码也可直接用于遗传算法。根据生物系统传代过程的规律，这些基因信息将在繁殖中传到下一带，而下一代将按照“适者生存”的原则决定种属的发展和消亡，而优化准则或目标函数就起到了决定“适者生存”的作用，即保留失拟较小的新模型，而放弃失拟大的模型。在传带过程中用编码表示的基因部分地交合和变异，即字符串中的一些子串被保留，有的改变，以使传代的过程向优化的目标演化。总的来说，遗传算法可分为三步：繁殖、杂交和变异。其具体实现过程见图5.8。

图5.8 遗传算法实现过程

5.4.2 遗传算法在地震反演中的应用

以地震走时反演为例，根据最小二乘准则使合成记录与实测数据的拟合差取极小，目标函数可取为

地球物理数据处理教程

式中：T_i，0为观测资料中提取出的地震走时；T_i，s为合成地震或射线追踪算出的地震走时；ΔT为所有合成地震走时的平均值；N_A为合成地震数据的个数，它可以少于实测T_i，0的个数，因为在射线追踪时有阴影区存在，不一定能算出合成数据T_j，0。利用射线追踪计算走时的方法很多，参见上一章。对于少数几个波速为常数的水平层，走时反演的参数编码方法可参照上一节介绍的分别对深度和速度编码方法，二进制码的字符串位数1不会太大。要注意的是由深度定出的字符串符合数值由浅到深增大的规律，这一约束条件不应在杂交和传代过程中破坏。这种不等式的约束（h₁＜h₂＜h₃…）在遗传算法中是容易实现的。

对于波场反演，较方便的做法是将地球介质作等间距的划分。例如，将水平层状介质细分为100个等厚度的水平层。在上地壳可假定波速小于6400 m/s（相当于解空间的硬约束），而波速空间距为100m/s，则可将波速用100m/s为单位，每层用6位二进制字符串表示波速，地层模型总共用600位二进制字符串表示（l=600）。初始模型可随机地选取24～192个，然后通过繁殖杂交与变异。杂交概率在0.5～1.0之间，变异概率小于0.01。目标函数（即失拟方程）在频率域可表示为

地球物理数据处理教程

式中：P₀（ω_k，v_j）为实测地震道的频谱；ω_k为角频率；v_j为第j层的波速；P_s（ω_k，v_j）为相应的合成地震道；A（ω_k）为地震仪及检波器的频率滤波器，例如，可取

A（ω）=sinC⁴（ω/ω_N） （5.4.6）

式中ω_N为Nyquist频率，即ω_N=π/Δt，Δt为时间采样率。参数C为振幅拟合因子，它起到合成与观测记录之间幅度上匹配的作用。C的计算常用地震道的包络函数的平均比值。例如，设E［］为波动信号的包络函数，可令

地球物理数据处理教程

式中：t_max为包络极大值的对应时间；J为总层数。包络函数可通过复数道的模拟取得。

用遗传算法作波速反演时失拟最小的模型将一直保存到迭代停止。什么时候停止传代还没有理论上可计算的好办法，一般要显示解空间的搜索范围及局部密度，以此来判断是否可以停止传代。值得指出的是，由（5.4.4）和（5.4.5）式给出的目标函数对于有误差的数据是有问题的，反演的目标不是追求对有误差数据的完美拟合，而是要求出准确而且分辨率最高的解估计。

遗传算法在执行中可能出现两类问题。其一称为“早熟”问题，即在传代之初就随机地选中了比较好的模型，它在传代中起主导作用，而使其后的计算因散不开而白白浪费。通常，增加Q值可以改善这种情况。另一类问题正相反，即传相当多代后仍然找不到一个特别好的解估计，即可能有几百个算出的目标函数值都大同小异。这时，最好修改目标函数的比例因子（即（5.4.5）式的分母），以使繁殖概率P_s的变化范围加大。

对于高维地震模型的反演，由于参数太多，相应的模型字符串太长，目前用遗传算法作反演的计算成本还嫌太高。实际上，为了加快计算，不仅要改进反演技巧和传代的控制技术，而且还要大幅度提高正演计算的速度，避免对遗传算法大量的计算花费在正演合成上。

㈧ 高分寻达人分别介绍下遗传算法和演化算法，以及之间的联系和区别

根据阅读的资料，大概有以下判断：
遗传算法是演化算法中的一种。

遗传算法（Genetic Algorithm）是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。它是由美国的J.Holland教授1975年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。

遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。它的思想源于生物遗传学和适者生存的自然规律，是具有“生存＋检测”的迭代过程的搜索算法。遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 作为一种新的全局优化搜索算法，遗传算法以其简单通用、鲁棒性强、适于并行处理以及高效、实用等显着特点，在各个领域得到了广泛应用，取得了良好效果，并逐渐成为重要的智能算法之一。

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法：
创建一个随机的初始状态

初始种群是从解中随机选择出来的，将这些解比喻为染色体或基因，该种群被称为第一代，这和符号人工智能系统的情况不一样，在那里问题的初始状态已经给定了。

评估适应度

对每一个解(染色体)指定一个适应度的值，根据问题求解的实际接近程度来指定(以便逼近求解问题的答案)。不要把这些“解”与问题的“答案”混为一谈，可以把它理解成为要得到答案，系统可能需要利用的那些特性。

繁殖(包括子代突变)

带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。

下一代

如果新的一代包含一个解，能产生一个充分接近或等于期望答案的输出，那么问题就已经解决了。如果情况并非如此，新的一代将重复他们父母所进行的繁衍过程，一代一代演化下去，直到达到期望的解为止。

并行计算

非常容易将遗传算法用到并行计算和群集环境中。一种方法是直接把每个节点当成一个并行的种群看待。然后有机体根据不同的繁殖方法从一个节点迁移到另一个节点。另一种方法是“农场主/劳工”体系结构，指定一个节点为“农场主”节点，负责选择有机体和分派适应度的值，另外的节点作为“劳工”节点，负责重新组合、变异和适应度函数的评估。
http://ke..com/view/45853.html

演化算法：
这部分的研究主要是提供具有演化特征的算法，已知的遗传算法是其中之一。许多新的算法正在研究中。由于遗传算法的整体搜索策略和优化计算时不依赖于梯度信息，所以它的应用非常广泛，尤其适合于处理传统搜索方法难以解决的高度复杂的非线性问题。人工生命研究的重要内容就是进化现象，遗传算法是研究进化现象的重要方法之一
我国学者接触这个领域较晚，目前尚未形成声势和有规模的研究队伍。1997年夏天，在中科院基础局、国家科委基础司及中国国际经济及技术交流中心的支持下，由中科院系统科学所和自动化研究所举办了第一次人工生命及进化机器人研讨会[20]。与会者约60人。除去邀请了五位国际知名学者的学术报告之外，国内也有数名学者介绍了相关的研究成果。主要在数字生命、复杂巨系统方面进行了一些研究。据目前了解到的情况，国内尚有一些人在研究演化算法，在人工智能的一本书上有一段介绍人工生命。但对人工社会、人工生态环境及进化机器人等尚无人问津。
http://blog.ustc.e.cn/chujx/archives/000925.html

㈨ 请问什么是遗传算法，并给两个例子

遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局优化算法，它借
用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性
的提高。这一点体现了自然界中"物竞天择、适者生存"进化过程。1962年Holland教授首次
提出了GA算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方
面，并奠定了坚实的理论基础。 用遗传算法解决问题时，首先要对待解决问题的模型结构
和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续
空间定义的GA(Genetic Algorithm in Continuous Space, GACS)，暂不讨论。

一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行：

(1) 对待解决问题进行编码；
(2) 随机初始化群体X(0):=(x1, x2, … xn)；
(3) 对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好
坏；
(4) 应用选择算子产生中间代Xr(t)；
(5) 对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有限
个体的覆盖面，体现全局搜索的思想；
(6) t:=t+1；如果不满足终止条件继续(3)。
GA中最常用的算子有如下几种：
(1) 选择算子(selection/reproction): 选择算子从群体中按某一概率成对选择个
体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulett
e wheel)模型。
(2) 交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率pc进行交叉
，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。
(3) 变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对
二值基因链(0,1编码)来说即是取反。
上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA的
某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度
及结果有很大的影响，应视具体问题选取不同的值。
GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的类的继
承为我们提供了这一可能。
定义两个基本结构：基因(ALLELE)和个体(INDIVIDUAL)，以个体的集合作为群体类TP
opulation的数据成员，而TSGA类则由群体派生出来，定义GA的基本操作。对任一个应用实
例，可以在TSGA类上派生，并定义新的操作。

TPopulation类包含两个重要过程：
FillFitness: 评价函数，对每个个体进行解码(decode)并计算出其适应度值，具体操
作在用户类中实现。
Statistic: 对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好
个体fmax、最坏个体fmin等。

TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个
重要的成员函数：
Select: 选择算子，基本的选择策略采用轮盘赌模型（如图2）。轮盘经任意旋转停止
后指针所指向区域被选中，所以fi值大的被选中的概率就大。
Crossover: 交叉算子，以概率Pc在两基因链上的随机位置交换子串。
Mutation: 变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。
Generate: 产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每运行一
次，产生新的一代。

SGA的结构及类定义如下(用C++编写)：
[code] typedef char ALLELE; // 基因类型
typedef struct{
ALLELE *chrom;
float fitness; // fitness of Chromosome
}INDIVIDUAL; // 个体定义

class TPopulation{ // 群体类定义
public:
int size; // Size of population: n
int lchrom; // Length of chromosome: l
float sumfitness, average;

INDIVIDUAL *fmin, *fmax;
INDIVIDUAL *pop;

TPopulation(int popsize, int strlength);
~TPopulation();
inline INDIVIDUAL &Indivial(int i){ return pop[i];};
void FillFitness(); // 评价函数
virtual void Statistics(); // 统计函数
};

class TSGA : public TPopulation{ // TSGA类派生于群体类
public:
float pcross; // Probability of Crossover
float pmutation; // Probability of Mutation
int gen; // Counter of generation

TSGA(int size, int strlength, float pm=0.03, float pc=0.6):
TPopulation(size, strlength)
{gen=0; pcross=pc; pmutation=pm; } ;
virtual INDIVIDUAL& Select();
virtual void Crossover(INDIVIDUAL &parent1, INDIVIDUAL &parent2,
INDIVIDUAL &child1, INDIVIDUAL &child2);
&child1, INDIVIDUAL &child2);
virtual ALLELE Mutation(ALLELE alleleval);
virtual void Generate(); // 产生新的一代
};
用户GA类定义如下：
class TSGAfit : public TSGA{
public:
TSGAfit(int size,float pm=0.0333,float pc=0.6)
:TSGA(size,24,pm,pc){};
void print();
}; [/code]

由于GA是一个概率过程，所以每次迭代的情况是不一样的；系统参数不同，迭代情况
也不同。在实验中参数一般选取如下：个体数n=50-200，变异概率Pm=0.03, 交叉概率Pc=
0.6。变异概率太大，会导致不稳定。

参考文献
● Goldberg D E. Genetic Algorithm in Search, Optimization, and machine

Learning. Addison-Wesley, Reading, MA, 1989
● 陈根社、陈新海，"遗传算法的研究与进展"，《信息与控制》，Vol.23,
NO.4, 1994, PP215-222
● Vittorio Maniezzo, "Genetic Evolution of the Topology and Weight Distri
bution of the Neural Networks", IEEE, Trans. on Neural Networks, Vol.5, NO
.1, 1994, PP39-53
● Xiaofeng Qi, Francesco Palmieri, "Theoretical Analysis of Evolutionary
Algorithms with an Infinite Population Size in Continuous Space. Part Ⅰ
l Networks, Vol.5, NO.1, 1994, PP102-119
● Xiaofeng Qi, Francesco Palmieri, "Theoretical Analysis of Evolutionary
Algorithms with an Infinite Population Size in Continuous Space. Part Ⅱ
al Networks, Vol.5, NO.1, 1994, PP102-119
● Gunter Rudolph, Convergence Analysis of Canonical Genetic Algorithms, I
EEE, Trans. on Neural Networks, Vol.5, NO.1, 1994, PP96-101
● A E Eiben, E H L Aarts, K M Van Hee. Gloable convergence of genetic alg
orithms: A Markov chain analysis. in Parallel Problem Solving from Nat
ure. H.-P.Schwefel, R.Manner, Eds. Berlin and Heidelberg: Springer, 1991
, PP4-12
● Wirt Atmar, "Notes on the Simulation of Evolution", IEEE, Trans. on Neu
ral Networks, Vol.5, NO.1, 1994, PP130-147
● Anthony V. Sebald, Jennifer Schlenzig, "Minimax Design of Neural Net Co
ntrollers for Highly Uncertain Plants", IEEE, Trans. on Neural Networks, V
ol.5, NO.1, 1994, PP73-81
● 方建安、邵世煌，"采用遗传算法自学习模型控制规则"，《自动化理论、技术与应
用》，中国自动化学会 第九届青年学术年会论文集，1993, PP233-238
● 方建安、邵世煌，"采用遗传算法学习的神经网络控制器"，《控制与决策》，199
3,8(3), PP208-212
● 苏素珍、土屋喜一，"使用遗传算法的迷宫学习"，《机器人》，Vol.16,NO.5,199
4, PP286-289
● M.Srinivas, L.M.Patnaik, "Adaptive Probabilities of Crossover and Mutat
ion", IEEE Trans. on S.M.C, Vol.24, NO.4, 1994 of Crossover and Mutation",
IEEE Trans. on S.M.C, Vol.24, NO.4, 1994
● Daihee Park, Abraham Kandel, Gideon Langholz, "Genetic-Based New Fuzzy
Reasoning Models with Application to Fuzzy Control", IEEE Trans. S. M. C,
Vol.24, NO.1, PP39-47, 1994
● Alen Varsek, Tanja Urbancic, Bodgan Filipic, "Genetic Algorithms in Con
troller Design and Tuning", IEEE Trans. S. M. C, Vol.23, NO.5, PP1330-13
39, 1993

㈩ 能通俗的介绍一下什么是遗传算法吗

遗传算法(Genetic Algorithms or GAs)是基于自然选择和自然遗传机制的搜索算法，它是一种有效的解决最优化问题的方法。遗传算法最早是由美国Michigan大学的John Holland和他的同事及学生提出的。类似于自然界演化的基本法则，“适者生存”是遗传算法的核心机制，同样，“复制（reproce）”、“杂交(crossover)”、“变异(mutation)”等自然界的生物演化规则在遗传算法中都得到类似的体现。

用遗传算法解最优化问题，首先应对可行域中的个体进行编码，然后在可行域中随机挑选指定群体大小的一些个体组成作为进化起点的第一代群体，并计算每个个体的目标函数值，即该个体的适应度。接着就像自然界中一样，利用选择机制从群体中随机挑选个体作为繁殖过程前的个体样本。选择机制保证适应度较高的个体能够保留较多的样本；而适应度较低的个体则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算法对挑选后的样本进行交换和基因突变。交叉算法交换随机挑选的两个个体的某些位，变异算子则直接对一个个体中的随机挑选的某一位进行突变。这样通过选择和繁殖就产生了下一代群体。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。

与其他算法相比，遗传算法主要有以下四个方面的不同： 遗传算法所面向的对象是参数集的编码,而不是参数集本身； 遗传算法的搜索是基于若干个点，而不是基于一个点； 遗传算法利用目标函数的信息，而不是导数或者其他辅助信息； 遗传算法的转化规则是概率性的，而不是确定性的。