探讨遗传算法论文：遗传算法的精髓究竟何在？

遗传算法的精髓在于遗传操作的交配算子。

在自然界生物进化历程中，生物遗传基因的重组（包括变异）扮演着核心角色。同样，在遗传算法中，起核心作用的是遗传操作的交配算子。所谓交配，是指将两个父代个体的部分结构进行替换重组，从而生成新个体的操作。通过交配，遗传算法的搜索能力得以显著提升。

交配算子根据交配率，将种群中的两个个体随机地交换某些基因，从而产生新的基因组合，旨在将有益基因组合在一起。

扩展资料

评估编码策略通常遵循以下3个准则：

a) 完整性(completeness): 问题空间中的所有点（候选解）都能作为GA空间中的点（染色体）呈现。

b) 合理性(soundness): GA空间中的染色体能对应所有问题空间中的候选解。

c) 非重复性(nonredundancy): 染色体和候选解一一对应。

目前常用的编码技术包括二进制编码、浮点数编码、字符编码、变长编码等。

而二进制编码是遗传算法中最常用的编码方法。即是由二进制字符集{0,1}产生的通常的0,1字符串来表示问题空间的候选解。

参考资料来源：百度百科-遗传算法

参考资料来源：百度百科-SGA

请问什么是遗传算法，并给出两个实例

分类:教育/科学>>科学技术

问题描述:

最好再介绍一下免疫算法

解析:

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

一个串行运算的遗传算法（Sequential Genetic Algorithm，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/reproduction）：选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最常用的实现方法是轮盘赌模型。

(2) 交配算子（Crossover）：交配算子将被选中的两个个体的基因链按概率pc进行交配，生成两个新的个体，交配位置是随机的。其中Pc是一个系统参数。

(3) 变异算子（Mutation）：变异算子将新个体的基因链的各位按概率pm进行变异，对二值基因链（0,1编码）来说即是取反。

上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA的某些性能。系统参数（个体数n、基因链长度l、交配概率Pc、变异概率Pm等）对算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。

GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的类的继承为我们提供了这一可能。

定义两个基本结构：基因（ALLELE）和个体（INDIVIDUAL），以个体的属性作为群体类TPopulation的数据成员，而TSGA类则由群体派生出来，定义GA的基本操作。对任一个应用实例，可以在TSGA类上派生，并定义新的操作。

TPopulation类包含两个重要过程：

FillFitness: 评价函数，对每个个体进行解码（decode）并计算出其适应度值，具体操作在用户类中实现。

Statistic: 统计函数，对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好个体fmax、最坏个体fmin等。

TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个重要的成员函数：

Select: 选择算子，基本的选择策略采用轮盘赌模型。轮盘经任意旋转停止后指针所指向区域被选中，所以fi值大的被选中的概率就大。

Crossover: 交配算子，以概率Pc在两基因链上的随机位置交换子串。

Mutation: 变异算子，以概率Pm对基因链上每一个基因进行随机干扰（取反）。

Generate: 产生下代，包括了评价、统计、选择、交配、变异等全部过程，每运行一次，产生新的一代。

SGA的结构及类定义如下（用C++编写）：

typedef char ALLELE;

基因类型

typedef struct

{...

ALLELEchrom;

INDIVIDUALfmin,fmax;

INDIVIDUALpop;

TPopulation(int popsize, int strlength);

~TPopulation();

inline INDIVIDUAL&Individual(int i)

{...

return pop [i ];

}

;

void FillFitness();

评价函数

virtual void Statistics();

统计函数

};

class TSGA: public TPopulation

{...

TSGA类派生于群体类

public: float pcross;

public: float crossover_rate;

交叉概率

float mutation_rate;

变异概率

int generation;

代数计数器

TSGA(int size, int str_length, float mutation_rate=0.03, float crossover_rate=0.6): TPopulation(size, str_length)

{...

generation=0;

crossover_rate=crossover_rate;

mutation_rate=mutation_rate;

};

virtual INDIVIDUAL& Choose();

virtual void Cross(INDIVIDUAL& parent1, INDIVIDUAL& parent2, INDIVIDUAL& child1, INDIVIDUAL& child2);

virtual ALLELE Mutate(ALLELE allele_val);

virtual void Generate();

生成新一代

};

用户GA类定义如下： class TSGAfit: public TSGA

{...

public: TSGAfit(int size,float mutation_rate=0.0333,float crossover_rate=0.6):TSGA(size,24,mutation_rate,crossover_rate)

{...

}

;

void Display();

};

由于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 Distribution 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Ⅰ", Neural 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Ⅱ", Neural Networks, Vol.5, NO.1, 1994, PP102-119

● Gunter Rudolph, Convergence Analysis of Canonical Genetic Algorithms, IEEE, Trans. on Neural Networks, Vol.5, NO.1, 1994, PP96-101

● A E Eiben, E H L Aarts, K M Van Hee. Global convergence of genetic algorithms: A Markov chain analysis. in Parallel Problem Solving from Nature. H.-P.Schwefel, R.Manner, Eds. Berlin and Heidelberg: Springer, 1991, PP4-12

● Wirt Atmar,"Notes on the Simulation of Evolution", IEEE, Trans. on Neural Networks, Vol.5, NO.1, 1994, PP130-147

● Anthony V. Sebald, Jennifer Schlenzig,"Minimax Design of Neural Net Controllers for Highly Uncertain Plants", IEEE, Trans. on Neural Networks, Vol.5, NO.1, 1994, PP73-81

●方建安、邵世煌，"采用遗传算法自学习模型控制规则"，《自动化理论、技术与应用》，中国自动化学会第九届青年学术年会论文集，1993, PP233-238

●方建安、邵世煌，"采用遗传算法学习的神经网络控制器"，《控制与决策》，1993,8(3), PP208-212

●苏素珍、土屋喜一，"使用遗传算法的迷宫学习"，《机器人》，Vol.16,NO.5,1994, PP286-289

● M.Srinivas, L.M.Patnaik,"Adaptive Probabilities 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 Controller Design and Tuning", IEEE Trans. S. M. C, Vol.23, NO.5, PP1330-13

39, 1993