1. 设种群规模为4,采用二进制编码,适应度函数$f(x) = x^2$,初始种群如表1所示 \begin{center} 表1 初始种群 \\…
- User
- 设种群规模为4,采用二进制编码,适应度函数,初始种群如表1所示
\begin{center} 表1 初始种群 \ \begin{tabular}{|c|c|c|c|c|c|c|} \hline 编号 & 基因型 & 表现型 & 适应度 & 选择 & 累计选择 & 选中 \ & & & 函数值 & 概率 & 概率 & 次数 \ \hline S1 & 1010 & 10 & & & & \ S2 & 0100 & 4 & & & & \ S3 & 1100 & 12 & & & & \ S4 & 0111 & 7 & & & & \ \hline \end{tabular} \end{center}
\begin{center} 表2 新一代种群 \ \begin{tabular}{|c|c|c|} \hline 编号 & 基因型 & 表现型 \ & (二进制) & (十进制) \ \hline S1' & & \ S2' & & \ S3' & & \ S4' & & \ \hline \end{tabular} \end{center}
如果遗传操作规定如下: \begin{enumerate} \item 选择概率Pr=1,选择操作用轮盘赌算法,且依次生成的4个随机数分别为0.42,0.16,0.89和0.71; \item 交叉概率Pc=1,交叉算法为单点交叉,交叉点为3,交叉顺序按个体在群体中的顺序; \item 变异概率Pm=0.1 \end{enumerate}
请完成初始种群的选择、交叉和变异操作,并给出所得到的新一代种群。请给出计算过程。
- Assistant
解答:
第一步:计算适应度函数值和选择概率
-
计算适应度函数值
[ \begin{align*} f(S1) &= f(10) = 10^2 = 100 \ f(S2) &= f(4) = 4^2 = 16 \ f(S3) &= f(12) = 12^2 = 144 \ f(S4) &= f(7) = 7^2 = 49 \ \end{align*} ]
-
计算总适应度
[ F_{\text{total}} = f(S1) + f(S2) + f(S3) + f(S4) = 100 + 16 + 144 + 49 = 309 ]
-
计算选择概率
[ \begin{align*} p_1 &= \frac{100}{309} \approx 0.3236 \ p_2 &= \frac{16}{309} \approx 0.0518 \ p_3 &= \frac{144}{309} \approx 0.4650 \ p_4 &= \frac{49}{309} \approx 0.1586 \ \end{align*} ]
-
计算累积选择概率
[ \begin{align*} q_1 &= p_1 = 0.3236 \ q_2 &= q_1 + p_2 = 0.3236 + 0.0518 = 0.3754 \ q_3 &= q_2 + p_3 = 0.3754 + 0.4650 = 0.8404 \ q_4 &= q_3 + p_4 = 0.8404 + 0.1586 = 0.9990 \ \end{align*} ]
-
填写初始种群表
\begin{center} 表1 初始种群 \begin{tabular}{|c|c|c|c|c|c|c|} \hline 编号 & 基因型 & 表现型 & 适应度 & 选择概率 & 累计选择概率 & 选中次数 \ & & & 函数值 & & & \ \hline S1 & 1010 & 10 & 100 & 0.3236 & 0.3236 & 1 \ S2 & 0100 & 4 & 16 & 0.0518 & 0.3754 & 0 \ S3 & 1100 & 12 & 144 & 0.4650 & 0.8404 & 2 \ S4 & 0111 & 7 & 49 & 0.1586 & 0.9990 & 1 \ \hline \end{tabular} \end{center}
第二步:选择操作(轮盘赌算法)
使用给定的随机数 [0.42, 0.16, 0.89, 0.71],依次选择个体:
-
随机数 0.42
0.3754 < 0.42 ≤ 0.8404,对应 ,选中 S3。
-
随机数 0.16
0 ≤ 0.16 ≤ 0.3236,对应 ,选中 S1。
-
随机数 0.89
0.8404 < 0.89 ≤ 0.9990,对应 ,选中 S4。
-
随机数 0.71
0.3754 < 0.71 ≤ 0.8404,对应 ,选中 S3。
选择结果:
- 选中个体顺序:S3,S1,S4,S3
第三步:交叉操作(单点交叉,交叉点为3)
交叉概率 ,因此对所有相邻个体进行交叉。
交叉配对:
- 第一对:S3(1100) 和 S1(1010)
- 第二对:S4(0111) 和 S3(1100)
交叉操作:
-
第一对交叉:
- 父本1:1 1 0 | 0
- 父本2:1 0 1 | 0
交叉点在第3位之后,交换后:
- 子代1:1 1 0 0(从父本1前3位+父本2第4位)
- 子代2:1 0 1 0(从父本2前3位+父本1第4位)
-
第二对交叉:
- 父本1:0 1 1 | 1
- 父本2:1 1 0 | 0
交叉点在第3位之后,交换后:
- 子代3:0 1 1 0(从父本1前3位+父本2第4位)
- 子代4:1 1 0 1(从父本2前3位+父本1第4位)
交叉结果的基因型:
- 子代1:1100
- 子代2:1010
- 子代3:0110
- 子代4:1101
第四步:变异操作(变异概率 )
对每一位基因进行变异判断,共有16个位,需要生成16个随机数。变异规则是当随机数小于0.1时,该位发生变异。
生成随机数并确定变异位(假设随机数如下):
- 子代1(1100):
- 第1位:随机数0.35(不变异)
- 第2位:随机数0.09(变异)
- 第3位:随机数0.55(不变异)
- 第4位:随机数0.78(不变异)
- 子代2(1010):
- 第1位:随机数0.12(不变异)
- 第2位:随机数0.95(不变异)
- 第3位:随机数0.06(变异)
- 第4位:随机数0.88(不变异)
- 子代3(0110):
- 第1位:随机数0.47(不变异)
- 第2位:随机数0.23(不变异)
- 第3位:随机数0.68(不变异)
- 第4位:随机数0.02(变异)
- 子代4(1101):
- 第1位:随机数0.99(不变异)
- 第2位:随机数0.11(不变异)
- 第3位:随机数0.31(不变异)
- 第4位:随机数0.07(变异)
变异结果:
- 子代1(1100)第2位变异,结果为1000
- 子代2(1010)第3位变异,结果为1000
- 子代3(0110)第4位变异,结果为0111
- 子代4(1101)第4位变异,结果为1100
第五步:得到新一代种群
新一代种群的基因型和表现型:
-
S1':
- 基因型:1000
- 表现型:8
-
S2':
- 基因型:1000
- 表现型:8
-
S3':
- 基因型:0111
- 表现型:7
-
S4':
- 基因型:1100
- 表现型:12
填写新一代种群表
\begin{center} 表2 新一代种群 \ \begin{tabular}{|c|c|c|} \hline 编号 & 基因型 (二进制) & 表现型 (十进制) \ \hline S1' & 1000 & 8 \ S2' & 1000 & 8 \ S3' & 0111 & 7 \ S4' & 1100 & 12 \ \hline \end{tabular} \end{center}
总结:
通过选择、交叉和变异操作,我们得到了新一代种群,其基因型和表现型如上表所示。
-