| 【遗传算法GA】具体实现（详细过程） | 您所在的位置：网站首页 › 遗传算法c实现 › 【遗传算法GA】具体实现（详细过程） |
【遗传算法GA】具体实现（详细过程）
|
1 遗传算法基本介绍：https://blog.csdn.net/See_Star/article/details/102589266 目录 一. 遗传编码二. 适应度函数三. 基本遗传操作1 选择操作2 交叉操作① 二进制交叉② 实值交叉 3 变异操作① 二进制变异② 实值变异 四 应用简例 一. 遗传编码常用的遗传编码算法有霍兰德二进制码、格雷码（Gray Code）、实数编码和字符编码等。 1 二进制编码（Binary encoding） 二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算精度有关。 例. 假设变量x的定义域为 [ 5 , 10 ] [5,10] [5,10]，要求的计算精度为 1 0 − 5 10^{-5} 10−5，则需要将 [ 5 , 10 ] [5,10] [5,10]至少分为 6 × 1 0 5 6×10^5 6×105个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于20。原因是： 524288 = 219 < 600000 < 220 = 1048576 524288=219fmax(x)−f(x)0当f(x) f m i n ( x ) 0 否 则 f_{nomal}(x)= \begin{cases} f(x)-f_{min}(x) &当f(x)>f_{min}(x)\\ 0 &否则 \end{cases} fnomal(x)={f(x)−fmin(x)0当f(x)>fmin(x)否则其中， f m i n ( x ) f_{min}(x) fmin(x)是原始适应函数 f ( x ) f(x) f(x)的一个下界。如果 f m i n ( x ) f_{min}(x) fmin(x)未知，则可用当前代或到目前为止各演化代中的 f ( x ) f(x) f(x)的最小值来代替。2 适应度函数的加速变换 在某些情况下，需要对适应度函数进行加速速度。适应度函数的加速变换有两种基本方法（暂时没搞懂）。 三. 基本遗传操作 1 选择操作选择（Selection）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。 比例选择方法（Proportional Model）的基本思想是：各个个体被选中的概率与其适应度大小成正比。常用的比例选择策略包括：轮盘赌选择、繁殖池选择。 其中最常用的为轮盘赌选择法，其又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：
P
(
x
i
)
=
f
(
x
i
)
∑
j
=
1
N
f
(
x
j
)
P(x_i)=\frac {f(x_i)} { \sum_{j=1}^N f(x_j)}
P(xi)=∑j=1Nf(xj)f(xi)其中，
P
(
x
i
)
P(x_i)
P(xi)是个体
x
i
x_i
xi的相对适应度，即个体
x
i
x_i
xi被选中的概率；
f
(
x
i
)
f(x_i)
f(xi)是个体xi的原始适应度。轮盘赌选择算法的基本思想是：根据每个个体的选择概率
P
(
x
i
)
P(x_i)
P(xi)将一个圆盘分成
N
N
N个扇区，其中第
i
i
i个扇区的中心角为：
2
π
f
(
x
i
)
∑
j
=
1
N
f
i
(
x
j
)
=
2
π
p
(
x
i
)
2\pi \frac {f(x_i)} { \sum_{j=1}^N f_i(x_j)}=2\pi p(x_i)
2π∑j=1Nfi(xj)f(xi)=2πp(xi)再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向第
i
i
i个扇区，则选择个体
i
i
i。其物理意义如图所示: 交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型。 ① 二进制交叉二进制交叉（Binary Valued Crossover）是指二进制编码情况下所采用的交叉操作，它主要包括单点交叉、两点交叉、多点交叉和均匀交叉等方法。 单点交叉 单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是： X = x 1 x 2 … x k x k + 1 … x n X=x_1 x_2 … x_k x_{k+1}… x_n X=x1x2…xkxk+1…xn Y = y 1 y 2 … y k y k + 1 … y n Y=y_1 y_2 … y_k y_{k+1}…y_n Y=y1y2…ykyk+1…yn 随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的xk+1到xn部分与Y中的yk+1到yn部分进行交叉，交叉后生成的两个新的个体是： X ’ = x 1 x 2 … x k y k + 1 … y n X’= x_1 x_2 … x_k y_{k+1} … y_n X’=x1x2…xkyk+1…yn Y ’ = y 1 y 2 … y k x k + 1 … x n Y’= y_1 y_2 … y_k x_{k+1} … x_n Y’=y1y2…ykxk+1…xn 其中， x k + 1 x_{k+1} xk+1与 y k + 1 y_{k+1} yk+1位置交叉。 例 设有两个父代的个体串A= 0 0 1 1 0 1 和B= 1 1 0 0 1 0 ，若随机交叉点为3和5，则交叉后的两个新的个体是： A’= 0 0 1 0 1 1 B’= 1 1 0 1 0 0 多点交叉 多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个新的个体。假设交叉点个数为m，则可将个体串划分为m+1个分段，其划分方法是： 当m为偶数时，对全部交叉点依次进行两两配对，构成m/2个交叉段。 当m为奇数时，对前(m-1)个交叉点依次进行两两配对，构成(m-1)/2个交叉段，而第m个交叉点则按单点交叉方法构成一个交叉段。 下面以m=3为例进行讨论。假设两个父代的个体串分别是 X = x 1 x 2 … x i … x j … x k … x n X=x_1 x_2 … x_i … x_j … x_k … x_n X=x1x2…xi…xj…xk…xn] Y = y 1 y 2 … y i … y j … y k … y n Y=y_1 y_2 … y_i … y_j … y_k … y_n Y=y1y2…yi…yj…yk…yn 随机设定第i、j、k位为三个交叉点（其中i |
从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。【本文地址】