基因算法

A. 基因遗传演算法是个啥求详解

基因遗传算法主要理论就是优胜劣汰的进化论。
它的主要精神是透过每次迭代都能比上次更进步，逐步演化，表现出针对一个目标函数寻求最佳解的过程。但是因为是随机搜索，所以虽然基因算法设置如交配、突变等来避免，却仍可能会陷入区域最佳解；也有可能最后得到的不是最佳解，只是在结束条件之前找到的最好的解。

基本的基因算法流程：
1.初始化族群：假定这个族群中有4条染色体，每条染色体有5个基因。

基因 -从目标函数的角度来看，就是自变数。
例如：用基因算法解目标函数 f(X,Y,Z)=2X+3Y-Z，
限制式为“X,Y,Z＝{1,0}”※，
求目标函数的最大值。
此题目对应到染色体的概念，就有3个基因，
三个基因分别代表X、Y、Z三个自变数的值。
染色体 -单一组解
例如：有很多符合目标函数限制式的（X,Y,Z），
其中一组是（x1,y1,z1）=（1,0,0），
函数值 f(x1,y1,z1)为2*1+3*0-0=2。
此例中，这组解当然不是最佳解，但它是这个题目的一个可行解。
*想象我们用直觉解题，拿张计算纸，把所有可行解都列出来，
然后比较所有我们想得到的可行解，最后可以得
到最佳的一组(X,Y,Z)，因为它的f(X,Y,Z)为最大值。
族群 -多组解的集合
例如：族群中有四条染色体，这四条染色体就是四组可行解。

2.设定交配率和突变率：假定交配率a为0.6，突变率b为0.1。

交配率 -每个世代中，族群内有多少比率的染色体会互相交配。
突变率 -每个世代中，族群内的染色体有多少机率会突变。

3.迭代世代。
For iter=10 -假定做十次优胜劣汰。
3.1. 天择：在这个世代中，根据每条染色体的权重，随机选择母代来产生后代，
用以做下一个运算。
通常使用轮盘法来作天择，也就是说，
如果染色体甲的解是这个族群中最好的，
那么甲的权重就是最高的。反之则是最低的。
*轮盘法：假定这次族群为“[1,1,1],[0,1,1],[1,0,1],[1,0,0]”，
四条染色体的适应值分别是“4，2，1，2”，
适应值总和为4+2+1+2=9，
则四条染色体被选到的机会为“4/9，2/9，1/9，2/9”
＝“0.4，0.2，0.1，0.2”。这个机会就是权重。
为了不让每次选择都选到同一条染色体，所以只是
“有比较高的机会”选择到“有更好适应值的染色体”，
而不是一定会选择这个好适应值的染色体。

3.2. 交配：母代产生后，依照交配率a，随机选择染色体来作交配。
比较交配前的子代1和交配后的子代2，在8条染色体中，
选择适应值最好的4条染色体留下来。
最简单的交配方式就是交换两条染色体的某个基因。
*例如，染色体S=[0,1,0]，染色体Q=[1,1,1]，交配位于首位的基因，
则可以得到新的两条染色体S'=[1,1,0]、Q'=[0,1,1]。

3.3. 突变：交配完后，依照突变率b，决定这一个世代要不要突变。
假设要突变，则若突变后子代3的适应值比突变前子代2好，就用子代3取代子代2。
最简单的突变方式就是随机选择某条染色体的某个基因，改变它。
*例如，随机选中染色体M=[1,0,1]，随机突变中间的基因，
得到新染色体M'=[1,1,1] 。

3.4. 更新：最后得到的族群中，所有染色体的适应值。
END For

4. 比较所有染色体的适应值，列出最好的那一个染色体为算法最后的解。

※一般使用二元染色体，限制染色体的基因只会等于零或壹。
在此处只是方便解说，所以直接把限制式设成零和壹。
假设我们用二元染色体来解目标函数f(x)=x^2的最大值，限制式为0<=x<=7，x为整数。
用基因算法求解，则需要产生log_2(8)=3个基因，
简单说来，就是用二进位表示一个有限整数值。
（也可以把基因想成电脑的位元数，我们用三个位元来表示一个有限的整数值。）
这样做的话，突变的方法就是直接把某个基因转成零或壹，
不用设定要更改多少值（例如加3、加100或减0.8）（基因算法应该一般不会这样做）；
计算适应值时，互相转换二进位与十进位。

基因三个，则可以表达：
111=2^2+2^1+2^0=4+2+1=7
110=2^2+2^1=4+2=6
101=2^2+2^0=4+1=5
100=4
001=1
000=0
011=3
010=2

B. 基因的基因计算

DNA分子类似“计算机磁盘”，拥有信息的保存、复制、改写等功能。将人体细胞核中的23对染色体中的DNA分子连接起来拉直，其长度大约为0.7米，但若把它折叠起来，又可以缩小为直径只有几微米的小球。因此，DNA分子被视为超高密度、大容量的分子存储器。
基因芯片经过改进，利用不同生物状态表达不同的数字后还可用于制造生物计算机。基于基因芯片和基因算法，未来的生物信息学领域，将有望出现能与当今的计算机业硬件巨头――英特尔公司、软件巨头――微软公司相匹敌的生物信息企业。

C. 谁能解释基因算法

基因算法 1975年 John Holland 学者所提出
成为非常着名的算法
Genetic Algorithm (GA)
基因算法 又称: 遗传算法
基因算法的概念
将问题编码成 染色体的型式
基因: 0 or 1
染色体: x = 0 1 0 0 1 1 0
设计 适应函数 (fitness function)
f(x) :适应函数，给一 x 可得一 适应值 f(x)
适应值愈高, 表愈适应环境
基因算法三个基本动作
选择(Selection)与复制 (Reproction)：
X = 0 1 0 0 1 1 0
选择 适应值高 之染色体
复制成多个染色体
基因算法三个基本动作
交换 (crossover)：
父：0 1 0 0 1 1 0 0 1 1 1 0 1 0
母：1 0 1 1 0 0 1 1 0 0 0 1 0 1
交换 基因算法三个基本动作
突变 (mutation)：
0 1 0 0 1 1 0
1 选择 产生初始族群
计算适应値 复制 交换
突变 产生下一子代
是否满足 停止条件
产生最适个体
否是 基因算法 基本架构图
取材自:辅仁大学资管系林文修老师
选择与 基因操作阶段
评估阶段 初始阶段 生成下一世代
问题否是 生成母体
评估适应函数
符合停止条件？
选择 复制 交换 突变
开始 结束 编码 适应函数
领域知识 表现型 基因型
解码 基因算法 之流程图
取材自:辅仁大学资管系林文修老师
算法步骤 Step1：随机产生N个染色体
Step2：利用适应函数算出每个染色体的适应值
Step3 : 选择与复制: 选择 适应值高 之染色体 复制成多个染色体
Step4：利用交换及突变的动作产生新的染色体
Step5：测试新染色体的适应值是否达到门槛值
是：则 停止
否：则 Go to Step3
范例1 假设 x 在 (0,31) 之间，y = x ，求 x = ，y 可得最大值
将问题编码成 基因的型式
x : 0 0 0 0 0～1 1 1 1 1
设计 适应函数 (fitness function)
f (x) = y = x
范例1 <Step 1, 2, 3>
取4组染色体 x f (x) f (x) /m 复制个数
0 1 1 1 0 (14) 196 0.71 1
1 1 0 0 0 (24) 576 2.07 2
1 0 0 0 1 (17) 289 1.04 1
0 0 1 1 1 ( 7) 49 0.18 0
m = = 278
196+576+289+49
4 范例1 <Step 4.1> 交换
x f (x)
0 1 1 1 0 0 1 0 0 0 (8) 8 = 64
1 1 0 0 0 1 1 1 1 0 (30) 30 = 900
1 1 0 0 0 1 1 0 0 1 (25) 25 = 625
1 0 0 0 1 1 0 0 0 0 (16) 16 = 256
交换 交换 范例1 <Step 4.1> 交换
交换点 下一子代 x f (x)
0 1 1 1 0 2 0 1 0 0 0 8 64
1 1 0 0 0 2 1 1 1 1 0 30 900
1 1 0 0 0 4 1 1 0 0 1 25 625
1 0 0 0 1 4 1 0 0 0 0 16 256
范例1 <Step4.2>突变 (机率0.1)
4个染色体× 5个基因 = 20个基因
20 × 0.1 = 2 有2个基因要突变
1 st：0 1 0 0 0 0 1 1 0 0 (12)
第一个染色体之第3基因突变
3 rd：1 1 0 0 1 1 0 0 0 1 (17)
第三个染色体之第2基因突变
范例1 <Step5>
停止条件有三种可能方法：
设定繁衍代数 (ex：1000代)
收敛 (ex：最佳适应值已50代未改进)
适应值达到门槛
否则，Go to Step3
编码（coding）-1
运用基因演化算法的目的是求问题的解，在初始阶段的编码步骤是把与问题相关变数的值（或称为问题解）以特定编码的方式将其组合成一条染色体 （chromosome，或称为字串string），每一条染色体即代表一可能的问题解答，
最简单而且被广泛使用的是标准二进位编码法（Standard binary encoding）。这种编码法是将染色体内的每个基因用二进位码{0，1}来表示，而编码后的染色体即是一串由01组合字串（string）。

D. 遗传算法

遗传算法是从代表问题可能潜在解集的一个种群开始的，而一个种群则由经过基因编码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因的组合，它决定了个体形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代（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的变化范围加大。

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

E. 遗传算法的基本原理

自然界是一个自适应的大系统^{［53，56～60］}，自然系统中的大多数生物体通过自然选择和有性生殖这两种基本过程进行自身的演化，使自己逐步达到完美来适应大自然。遗传算法受生物进化与遗传的启发，形成一种独特的优化方式，遗传算法的运算原理常常与生物进化及遗传学说相吻合，而且其术语也常仿照生物学的术语。遗传算法的运算基础是字符串，先将搜索对象编码为字符串形式；字符串就相当于生物学中的染色体，由一系列字符组成；每个字符都有特定的含义，反映所解决问题的某个特征，这就相当于基因，亦即染色体DNA的片段。每个字符串结构被称为个体，每个个体都可以通过问题本身所具有的适应值度量来计算反映其适应性好坏的适应值，然后对一组字符串结构（被称为一个群体）进行循环操作。每次循环操作被称作一代，其中的操作包括：保存字符串组中适应性较好的那些字符串到下一代（对应于遗传学中的复制），使上一代中的优良个体得以生存下去，这类似于生物进化论中的自然选择。通过有组织的然而是随机的字符串间的信息交换来重新结合那些适应性好的字符串（对应于遗传学中的交叉），在每一代中利用上一代字符串结构中适应性好的位和段来生成一个新的字符串的群体；作为额外增添，偶尔也要在字符串结构中尝试用新的位和段来替代原来的部分（对应于遗传学中的变异），等等。遗传算法中这些操作只涉及字符串的某些片段，这就类似于遗传过程只涉及某些基因而不是整个染色体。遗传算法是一类随机算法，但它不是简单的随机走动，它可以有效地利用已有的信息来搜寻那些有希望改善解质量的字符串。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。

F. 什么是遗传算法

是电路里的吗？

G. 基因遗传算法主流

基因遗传算法是一种灵感源于达尔文自然进化理论的启发式搜索算法 该算法反映了自然选择的过程 即最适者被选定繁殖 并产生下一代
自然选择的过程从选择群体中最适应环境的个体开始 后代继承了父母的特性 并且这些特性将添加到下一代中 如果父母具有更好的适应性 那么它们的后代将更易于存活 迭代地进行该自然选择的过程 最终 我们将得到由最适应环境的个体组成的一代
这一概念可以被应用于搜索问题中 我们考滤一个问题的诸多解决方案 并从中搜寻出最佳方案
遗传算法含以下五步
1.初始化
2.个体评价（计算适应度函数）
3.选择运算
4.交叉运算
5.变异运算
初始化
该过程从种群的一组个体开始 且每一个体都是待解决问题的一个候选解
个体以一组参数（变量）为特征 这些特征被称为基因 串联这些基因就可以组成染色体（问题的解）
在遗传算法中 单个个体的基因组以字符串的方式呈现 通常我们可以使用二进制（1和0的字符串）编码 即一个二进制串代表一条染色体串 因此可以说我们将基因串或候选解的特征编码在染色体中
个体评价利用适应度函数评估了该个体对环境的适应度（与其它个体径争的能力）每一个体都有适应评分 个体被选中进行繁殖的可能性取决于其适应度评分 适应度函数是遗传算法进化的驱动力 也是进行自然选择的唯一标准 它的设计应结合求解问题本身的要求而定
选择运算的目的是选出适应性最好的个体 并使它们将基因传到下一代中 基于其适应度评分 我们选择多对较优个体（父母）适应度高的个体更易被选中繁殖 即将较优父母的基因传递到下一代
交叉运算是遗传算法中最重要的阶段 对每一对配对的父母 基因都存在随机选中的交叉点
变异运算
在某些形成的新后代中 它们的某些基因可能受到低概率变异因子的作用 这意味着二进制位串中的某些位可能会翻转
变异运算前后
变异运算可用于保持群内的多样性 并防止过早收敛
终止
在群体收敛的情况下（群体内不产生与前一代差异较大的后代）该算法终止 也就是说遗传算法提供了一组问题的解

H. 遗传算法的一般算法

遗传算法是基于生物学的，理解或编程都不太难。下面是遗传算法的一般算法： 繁殖(包括子代突变)
带有较高适应度值的那些染色体更可能产生后代(后代产生后也将发生突变)。后代是父母的产物，他们由来自父母的基因结合而成，这个过程被称为“杂交”。 各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫适应度函数。 这个函数是计算个体在群体中被使用的概率。

I. 网上经常所说的遗传算法与基因算法是一回事吗有什么不同各自的用途用在什么地方

遗传算法
GA是一种基于自然群体遗传演化机制的高效探索算法，它是美国学者Holland于1975年首先提出来的。

它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。

Holland创建的遗传算法是一种概率搜索算法，它是利用某种编码技术作用于称为染色体的数串，其基本思想是模拟由这些组成的进化过程。跗算法通过有组织地然而是随机地信息交换重新组合那些适应性好的串，在每一代中，利用上一代串结构中适应好的位和段来生成一个新的串的群体；作为额外增添，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。

遗传算法是一类随机化算法，但是它不是简单的随机走动，它可以有效地利用已经有的信息处理来搜索那些有希望改善解质量的串，类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。与自然界相似，遗传算法对待求解问题本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应度值来造反染色体，使适用性好的染色体比适应性差的染色体有更多的繁殖机会。

基因：组成染色体的单元，可以表示为一个二进制位，一个整数或一个字符等。

染色体或个体：表示待求解问题的一个可能解，由若干基因组成，是GA操作的基本对象。

群体：一定数量的个体组成了群体，表示GA的遗传搜索空间。

适应度或适度：代表一个个体所对应解的优劣，通常由某一适应度函数表示。

选择：GA的基本操作之一，即根据个体的适应度，在群体中按照一定的概论选择可以作为父本的个体，选择依据是适应度大的个体被选中的概率高。选择操作体现了适者生存，优胜劣汰的进化规则。

交叉：GA的基本操作之一，即将父本个体按照一定的概率随机地交换基因形成新的个体。

变异：GA的基本操作之一，即即按一定概率随机改变某个体的基因值。

基因算法是一种生物进化的算法,实际上是一种多目标的探索法.能够用于计划与排程.它是非常新的技术,目前,还没有在商业中实际运用.
采用生物基因技术高级算法,处理日益复杂的现实世界,也是人工智能上,高级约束算法上的挑战. 基因算法是一种搜索技术，它的目标是寻找最好的解决方案。这种搜索技术是一种优化组合，它以模仿生物进化过程为基础。基因算法的基本思想是，进化就是选择了最优种类。基因算法将应用APS上，以获得“最优”的解决方案。