遗传算法是解决搜索问题的一种通用算法。

模拟自然界优胜劣汰的进化现象，把搜索问题转化为遗传问题，把可能的解转为成一个向量——染色体，向量的每个元素称为基因。通过不断计算各染色体的适应值，选择最好的染色体，获得最优解。

基本概念 （以下均以二进制串 a=<1000101110110101000111> 为例）

1. 遗传：子代和父代具有相同或相似的性状，保证物种的稳定性；

2. 变异：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；

3. 生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。

自然选择过程是长期的、缓慢的、连续的过程。

4. 个体与种群

● 个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。

● 种群就是模拟生物种群而由若干个体组成的群体, 它一般是整个搜索空间的一个很小的子集。

5. 适应度与适应度函数

● 适应度就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。

● 适应度函数就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个实值函数。该函数就是遗传算法中指导搜索的评价函数，数值越接近目标值则说明适应度越高。

6. 染色体与基因

● 染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因。

7. 遗传操作

　　亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作:

● 选择 (selection)

● 交叉(crossover，亦称交换、交配或杂交)

● 变异(mutation，亦称突变)

---

现在写个简单的例子：设 f(x) = -x2 + 2x + 0.5，求 max f(x), x在[-1, 2]之间。

对于二进制串 a=<1000101110110101000111> ；

1.先将其转为十进制数：ve=2288967

2.将其转化为[-1，2]内的实数为：

X=-1+ve*(2-(-1))/((2^22)-1)=0.631797

3.随机的产生一个初始群体（这里假设初始群体的个体数为 4）

pop1={

<1101011101001100011110>， % a1

<1000011001010001000010>， % a2

<0001100111010110000000>， % a3

<0110101001101110010101>} % a4

4.转化成 [-1, 2] 之间的十进制数即为

pop1={ 1.523032,0.574022,-0.697235,0.247238}

5.定义适应函数和求适应值

由于目标函数 f(x) 在 [-1, 2] 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。

最后假设得到适应值：

g(pop1)={2.226437,2.318543, 0,1.933350}

6.算出入选下一代的概率：

p(pop1)=g(pop1)/sum(g(pop1))

={0.343675, 0.357892, 0, 0.298433}

7.产生种群

newpop1={

<110101110 1001100011110>， % a1

<100001100 1010001000010>， % a2

<10000110010100 01000010>， % a2

<01101010011011 10010101>} % a4

8.交叉：

将第七步的加粗部分交换，（a1与a2,a3与a4）得到如下结果：

<1101011101010001000010>， % a1

<1000011001001100011110>， % a2

<10000110 0 1010010010101>， % a2

<0110101001101101000010>} % a4

9.变异：将a3中加粗基因变异：

<1101011101010001000010>， % a1

<1000011001001100011110>， % a2

<10000110 1 1010010010101>， % a2

<0110101001101101000010>} % a4

10.终止：我们可以采用遗传指定代数的方法进行停止程序的运行，但是精确度较低，亦可以根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制

---

来一个实际的例子加代码（本人也正在学习java，如有不足之处欢迎指出）

用遗传算法（ GA ）求如下问题的最优解， x1, x2精确到小数点后2位。 （采用二进制编码方法）

max f (x1, x2) = 2x1·sin(8p x2) +x2·cos(13p x1)

x1:[-3,7]

x2:[-4,10]

代码如下：

class chromasome{
    //染色体    public static final int DNAsize1=10;    public static final int DNAsize2=11;    int []DNA1=new int[DNAsize1];    int []DNA2=new int[DNAsize2];    chromasome(){        int a,b;        for(int i=0;i
     
      =0&&select_rate[j]
     

结果：