简述遗传算法

用户7506105

发布于 2021-08-09 14:57:33

1.4K0

发布于 2021-08-09 14:57:33

文章被收录于专栏：碎片学习录碎片学习录

思想

达尔文自然选择学说和孟德尔遗传机理的生物进化过程的计算模型，个体经过每一代的迭代不断产生更优良的基因序列(可行解)，淘汰掉适应度值低的个体，从而不断接近最优的适应度(目标函数)，一般来说遗传算法是启发性算法，得到的目标函数值可能不尽相同

步骤

遗传算法由编解码，个体适应度评估和遗传运算三大模块组成

可行解的编码

(取决于决策变量的定义域区间)

一般采用二进制编码，设某一个参数x的取值范围为(L,U),假设用长度为k的二进制编码表示该参数，则一共有2^k种不同的编码，参数变化的步长为

\delta

,则

\delta = \frac{U-L}{2^k-1}

因为x的变化情况是

L, L+\delta,L+2\delta,...,2^k-1

编码解码成可行解

目的是为了把不直观的二进制串还原成十进制，设某一个个体的二进制串为

b_k b_{k-1} b_{k-2}...b_3 b_2 b_1

,则解码公式为

x = L+(\sum_{i=1}^kb_i 2^{i-1})\delta

=L + (\sum_{i=1}^kb_i 2^{i-1})\frac{U-L}{2^k-1}

确定k的大小，一般需要根据所求的x精度来确定，若x精度要求保留m位小数，则可行解的空间大小为(U-L)*10^m，所以此时的k应该满足

2^{k-1} <(U-L)*10^m<=2^k-1

如果有多个自变量

x_i

,则需要对每个

x_i

进行各自的可行解范围的编码计算，然后计算出每个

k_i

后，将这些

k_i

拼串到一起组成一个大的二进制串

适应度函数的确定

适应度函数即为待求解的目标函数，因为轮盘选择一般是选择最好的适应度，所以一般来求解最大值问题，所以如果是最小值问题，需要取负数求最大

种群中初始个体的确定

初始个体即为寻找最优解的初始可行解，此时算出的适应度函数值不一定是最优的，初始种群大小为超参数，根据问题的规模来确定，且种群大小不随着迭代次数增加而变化，遗传算法本质上是不断把优质基因加入到后代当中去，不存在淘汰最差个体的情况

生存代数的确定

生存代数即为迭代次数，一般是等着适应度函数的变化收敛程度满足设定的阈值参数后就可以终止迭代，即此时的最优解就是此时最大适应度函数对应的个体

基因的遗传(复制)

计算适应度值每个个体的基因编码解码成实际的xk(k最大为个体总数)后，将每个x(列向量)代入适应度函数中

eval(f_k) = f(x_k) = f(x_{k1},x_{k2},...,x_{ki})

i 为自变量个数

计算适应度值的总和

F = \sum_{k=1}^N eval(f_k)

每个个体被复制的概率

P_k = \frac{eval(f_k)}{F}

计算每个染色体被复制的累积概率

Q_k = \sum_{j=1}^kP_k

计算累积概率的目的是任何一个被复制的概率都会等于区间

[Q_{k-1}, Q_k]

的区间长度,方便后续做轮盘选择，即随机数落在这个区间的会因为区间长度的越大而越多

复制操作生成(0,1)的维度为种群个体数N的随机序列，针对序列中的每个随机数与累积概率Q值进行判断，若随机数大于

Q_{k-1}

小于

Q_{k+1}

则说明第k个个体是被选中的，这样就会得到一些含有重复个体的新种群，但种群大小还是为N

基因点位的自由组合，交配

自由组合一般有单点自由或多点进行交叉的情况，考虑单点组合，设置一个交配概率，则参与交配的染色体数量为染色体总量乘以交配概率并向下取整，此时采取的方法是生成总数为N的(0,1)随机序列，低于选定的交配概率的值的个体作为交配的对象，如果只有一个个体则不进行交配，如果有多个个体则随机两两配对，然后分别在每对中生成以基因串长为范围的整数随机数即交配点位，然后进行基因片段的互换，一般交配是在复制之后进行操作