【人工智能】遗传算法
@[TOC](人工智能算法---遗传算法（基础篇）)
# 知识导图：感觉写的好的话，求收藏，没动力了快，一篇写下来累死累活的。
<center>
<img src="https://img-blog.csdnimg.cn/80d86381f3284fc4b9dd845bec31baee.png" ></img>
# 全文围绕其简单题目：
<center>
<img src="https://img-blog.csdnimg.cn/aac45e3a8f5e4830996f7c0dc36b66d9.png" ></img>
## 遗传算法（概念）
可以把遗传算法类比成一个游戏，我们需要通过这个游戏来找到最佳的解决方案。
- 首先，我们需要创建一些角色（也就是种群），每个角色有自己的装备和技能（染色体），但是我们并不知道哪个角色更加强大。
- 然后，我们让这些角色相互竞争，通过升级、打怪等方式来获得经验值（适应度值）。经验值越高的角色，就拥有了更多胜利的可能性。
- 接着，我们会将经验值高的角色进行复制，将装备/技能进行升级，继承属性（对应其交叉操作），而一些随机变异的角色也会加入其中。这些新的角色代表了我们在寻找答案的过程中的探索。如果它们的表现好于之前的角色，那么我们就可以用它们来代替原来的角色。
- 最后，通过这样的迭代过程，我们会逐渐找到最强大的角色，也就是最优解。
总之，遗传算法通过不断地试错，从而找到最优解决方案，就像在玩游戏一样。
具体来说，遗传算法的流程包括以下几个步骤：
- 初始化种群：通过随机方式生成一组初始解，称为种群。
- 适应度函数：根据问题要求，设计一个适应度函数，用于评价每个个体的好坏程度。
- 选择操作：按照适应度函数的评价结果，从当前种群中选择一些优秀的个体作为父代，并使用复制、交叉等方法产生下一代种群。
- 变异操作：在新产生的个体中进行随机变异的操作，增加搜索的多样性。
- 终止条件：根据预设的停止条件（如迭代次数、达到最优解等）决定算法何时结束。
<font size=4 color=red>遗传算法通过不断地试错，在种群中选择、交叉和变异来生成新的个体，并计算它们的适应度值。然后，根据设定的适应度函数来选择出适应度值高的个体作为下一代的父母，再进行交叉和变异操作，生成新的个体。通过这样的迭代过程，逐渐找到最优解决方案</font>
## 步骤：
### 1.初始化种群
 初始化种群是指在遗传算法中，初始阶段按照其规定的<font size=3 color=red>编码方式</font><font size=3 color=blue>随机生成一组个体</font>，并将其作为遗传算法的起点。
> 这些个体构成了一个种群，每个个体都代表了问题的一个可能解。通过对这些个体进行交叉、变异等操作，不断迭代，从而逐步逼近问题的最优解。因此，初始化种群的质量和数量对于遗传算法的性能有很大影响。
基础篇，理解并学会使用以下三种编码方式方法：
- <font size=3 color=red>二进制</font>
- ~~整数（没学，有机会的话，放到进阶篇写）~~
- ~~浮点数（没学，有机会的话，放到进阶篇写）~~
#### 1.1二进制编码与解码
顾名思义，就是将10进制数编码成二进制数
<font size=4 color=blue>以下是我总结的常用方式和其代码：</font>
 假设需要解决一个最小化函数$f(x)$（适应函数$f$），其中变量x是取值范围出现以下情况：
<font size=3 color=black> 1. 当x是取值范围为$[a,b]$之间的实数。</font>
$$x=a+\frac{c_{⑩}}{2^n-1}*(b-a)$$
: $c_{⑩}$是随机生成的一个二进制串的10进制值
> 例如：10101的$c_{⑩}$为21,
:n就是我们选取的二进制位数
:n的取值和你所需要的精度p有关，计算公式是$2^{n-1}<(b-a)*10^p<2^{n}$
> 例如：例子[来源](https://blog.csdn.net/x1020915098/article/details/77855219?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522168233525416800227498973%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=168233525416800227498973&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~baidu_landing_v2~default-1-77855219-null-null.142%5Ev86%5Einsert_down1,239%5Ev2%5Einsert_chatgpt&utm_term=%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3%95%E4%B8%AD%E7%9A%84%E4%BA%8C%E8%BF%9B%E5%88%B6&spm=1018.2226.3001.4187)<center>
> <img src="https://img-blog.csdnimg.cn/1e89a78d36f54b7d84447aeb61a3c1dc.png" ></img>
> 例如：假设需要解决一个最小化函数f(x)，其中变量x是取值范围为[0,10]之间的实数。可以将c表示为一个长度为n的二进制串。例如，当$n=5$时，可将二进制串c:$10101$带入公式<font size=3 color=red>$x=(\frac{21}{31})*10=6.77$</font>
<font size=4 color=blue>下面是最初题目的一些示例代码（主要工作就是初始化种群*100 二进制串----> $c_{⑩}$）</font>
代码：
```python
import math
import random
# 求n（已知精度p,x的取值范围[a,b]）
def calculate_n(p, a, b):
power = math.log2((b - a) * 10 ** p)
n = math.ceil(power)
return n
# 随机生成n位二进制数
def generate_binary_number(n):
binary = ""
for i in range(n):
bit = random.randint(0, 1)
binary += str(bit)
return binary
# 初始化种群（二进制版）
def initialize_population(population_size, n):
population = []
for i in range(population_size):
individual = generate_binary_number(n)
population.append(list(map(int,individual)))
return population
# 二进制编码 n位二进制的选择
n = calculate_n(1, -5, 5)
print("n:", n)
# 初始化种群
population_2 = initialize_population(100, n)
print("初始化种群", population_2)
```
输出：
<center>
<img src="https://img-blog.csdnimg.cn/8493d94ef5904b1697fbfcdfe2f28309.png" ></img>
---
>一般遗传题目中的变量是多维的（或者说多个变量），那么我们采用的一般都是将其转化为1维的二进制串，当然，这不属于我的基础篇内容，可以了解下以下内容：
> <center>
> <img src="https://img-blog.csdnimg.cn/ff9717516a6a43168386b402bae2fc13.png" ></img>
### 2.选择操作
 根据第一步初始化的种群，对其每个个体进行评价，<font size=5 color=red>选出</font>适应度最高的个体作为下一代的父代。
 所谓个体评价可以被视为对该个体在特定问题上表现优劣的度量。<font size=3 color=red>将个体带入适应度函数得到的适应度值作为判别依据</font>。适应度函数是用来衡量每个个体相对于解决问题的能力或者质量的函数。评价指标通常越高，表示个体在当前环境下的适应度越好。通过比较不同个体的适应度，可以选出<font size=3 color=red>适应度最高</font>的个体作为下一代的父代。
<font size=4 color=blue>选择操作是一种基于适应度的算法，通过使用<font size=5 color=red>某些技术</font>从当前群体中选出适应性较高的个体作为下一代的父代。这种方法可以反复迭代，以提高整个群体的适应度水平。</font>
---
#### 2.1 拿到个体适应度
那么，我们就用步骤1.1中的公式$x=a+\frac{c_{⑩}}{2^n-1}*(b-a)$，将得到的10进制，转化为相应x值，方便我们去带入适应度函数$f(x)$。
函数代码：
```python
# 得到相应区间的x值
def binary_to_x(binary_list, a, b, n):
x_list = []
range_value = b - a
for binary in binary_list:
decimal = int("".join(map(str, binary)), 2)
ratio = decimal / (2 ** n - 1)
x = ratio * range_value + a
x_list.append(x)
return x_list
# 求x
x = binary_to_x(population_2, -5, 5, n)
x = [round(num, 1) for num in x]
print("x", x)
```
输出：
带入适应度函数（按照原题目中，适应度函数为$f(x) = x^2-3x+4$）
```python
def fitness(x):
return round(x ** 2 - 3 * x + 4, 1)
# 求适应度
fitness_values = [fitness(x) for x in x]
print("适应度", fitness_values)
```
输出： 
#### 2.2 轮盘赌选择
<center>
<img src="https://img-blog.csdnimg.cn/3fb381a2934c48e2957a5da17df20597.png" ></img>
轮盘赌选择是一种常用的遗传算法选择方法，也被称为比例选择。
轮盘赌选择法（roulette wheel selection）是最简单也是最常用的选择方法，在该方法中，各个个体的选择概率和其适应度值成比例，适应度越大，选中概率也越大。
但实际在进行轮盘赌选择时个体的选择往往不是依据个体的选择概率，而是根据<font size=4 color=blue>“累积概率”</font>来进行选择。
解析：知乎[轮盘赌选择](https://zhuanlan.zhihu.com/p/140418005)
设某一部分$x_i$的适应度值表示为$f(x_i)$，该部分被选中的概率为$p(x_i)$，累积概率为$q(x_i)$，对应的计算公式如下：
$$p(x_i) = \frac{f(x_i)}{\sum^{N}_{j=1}f_i}$$
$$q(x_i)=\sum^i_{j=1}p(x_j)$$
上式中的累积概率表示每个个体之前所有个体的选择概率之和，它相当于在转盘上的“跨度”，“跨度”越大越容易选到，就相当于概率论中的概率分布函数F(x)。轮盘赌选择法的过程如下：
（1）计算每个个体的被选中概率p(xi)
（2）计算每个部分的累积概率q(xi)
（3）随机生成一个数组m，数组中的元素取值范围在0和1之间，并将其按从小到大的方式进行排序。若累积概率q(xi)大于数组中的元素m[i]，则个体x(i)被选中，若小于m[i]，则比较下一个个体x(i+1)直至选出一个个体为止。
（4）若需要转中N个个体，则将步骤（3）重复N次即可.
<font size=4 color=blue>问题：</font>上述操作似乎很正确，但是你想没想过，$\sum^{N}_{j=1}f_i$中的$f_i$<font size=3 color=red>有正有负</font>会出现什么情况吗？
<font size=4 color=blue>答：</font>我们上述思想步骤完全不成立。概率$p(x_i)$和累计概率$q(x_i)$的失去其原本意义
<font size=4 color=blue>解决方法：</font><font size=4 color=red>归一化</font>
##### 2.2.1归一化
使用种群中最小适应度值的个体作为归一化的最小值。这被称为“最小-最大规范化”（Min-Max Normalization）或“线性比例缩放”（Linear Proportional Scaling）。具体地，对于一个种群，可以通过以下步骤进行归一化：
1. 计算种群中所有个体的适应度值$f(x)$。
2. 找到所有适应度值中的最小值$f_{min}$和最大值$f_{max}$。
3. 对于每个个体，计算其归一化适应度值$f'(x)$，公式如下：
4. $f'(x) = \frac{f(x) - f_{min}} { f_{max} - f_{min}}$
：其中$f(x)$是个体的原始适应度值。
：这样得到的归一化适应度值f'(x)会被限制在[0, 1]之间，并且种群中适应度值最小的个体的归一化适应度值将为0
<font size=4 color=blue>问题：</font>在使用最小-最大规范化对适应度进行归一化时，如果存在某个个体的适应度值为0，则它的归一化适应度值也将为0。这可能会导致一些问题，因为在选择过程中，只有归一化适应度值比较大的个体才会被选中，而归一化<font size=4 color=red>适应度值为0</font>的个体则<font size=4 color=red>无法被选中</font>。
<font size=4 color=blue>解决方法：</font>有一种解决方案是添加一个非零的偏移量例如，在计算f'(x)时，我们可以使用以下公式：
$$f'(x) = (f(x) - f_{min} + epsilon) / (f_{max} - f_{min} + epsilon)$$
其中epsilon是一个足够小的正数，用来避免出现分母为0的情况。通过添加epsilon，所有的适应度值都可以被成功归一化，而且可以继续使用遗传算法等选择方法。
需要注意的是，选择过程不仅依赖于适应度值的大小，还涉及到其他因素，如选择操作的参数、选择算子的类型等。因此，在使用归一化适应度值进行选择时，需要谨慎地选择合适的方法，并进行实验测试和验证。
---
代码：
```python
上面代码略
上面的代码在文章上面
def roulette_wheel_selection(population, fitness_values):
# 计算总适应度
total_fitness = sum(fitness_values)
# 计算适应度最大值的偏移量
offset = abs(min(fitness_values))
# 计算相对适应度
relative_fitness = [(f + offset) / total_fitness for f in fitness_values]
# 计算累积概率
probabilities = [sum(relative_fitness[:i + 1]) for i in range(len(relative_fitness))]
# 选择个体
selected = []
for i in range(len(population)):
r = random.random()
for j, p in enumerate(probabilities):
if r <= p:
selected.append(population[j])
break
return selected
def normalize_fitness(fitness_list, population):
# Calculate the minimum and maximum fitness values
min_f = min(fitness_list)
max_f = max(fitness_list)
# Add a small constant to avoid division by zero
epsilon = 1e-8
# Normalize the fitness values for each individual in the population
normalized_fitness = []
for i in range(len(population)):
fitness = fitness_list[i]
norm_fitness = (fitness - min_f + epsilon) / (max_f - min_f + epsilon)
normalized_fitness.append(norm_fitness)
return normalized_fitness
# 归一化适应度
fitness_values_nor = normalize_fitness(fitness_values,population_2)
print("归一化的适应度值",fitness_values_nor)
# 轮盘赌选择父代
select = roulette_wheel_selection(population_2, fitness_values_nor)
print(select)
```
输出：
<font size=4 color=red>重要知识点：</font>在轮盘赌选择算法中，每个个体在被选中的概率与其适应度成正比。因此，如果得到的个体重复出现，那么它们必须被视为不同的个体，并分别参与下一代的繁殖。
一般来讲，我们选择种群的个数和初始种群个数<font size=3 color=blue>保持一致</font>。
### 3.交叉操作
交叉操作是遗传算法中的一种重要操作，用于产生新的个体。其原理是通过对<font size=3 color=red>两个或多个</font>个体的<font size=3 color=red>某些基因位点</font>进行交换，从而产生具有<font size=3 color=red>不同基因组合</font>的新个体。
#### 3.1单点交叉
<center>
<img src=" https://img-blog.csdnimg.cn/20191202151959116.gif#pic_center" >图片来自：<a herf="https://blog.csdn.net/u010743448/article/details/108445588">博客:遗传算法中的一些交叉算子</a></img>
单点交叉是其中一种常见的交叉方式，它是指在随机选择的一个交叉点处将两个个体的染色体分为两段，然后将这两段互换，产生两个新个体。
由上面选择操作，选择到了种群一些优秀个体作为父代基因，将这些优秀个体<font size=4 color=red>随机</font>两两交叉。
> 这样做的好处是：
>
> 在使用已经选择出来的父代个体进行交叉操作时，通常是随机选取两个不同的父代进行交叉操作。这样可以增加交叉的随机性，从而更好地避免陷入局部最优解。
>
> 如果您采用逐一对每一对父代进行交叉操作，则可能会导致某些父代个体之间没有交叉，或者某些个体交叉的次数过多，从而影响算法效果。因此，随机选择两个不同的父代进行交叉是比较合适的做法。
代码：
```python
# 单点交叉
def single_point_crossover(parents):
# 随机选择两个不同的父代基因进行交叉，并产生相应数量的子代基因
children = []
for i in range(int(len(parents) / 2)):
parent1, parent2 = random.sample(parents, 2)
crossover_point = random.randint(1, len(parent1) - 1)
parent1_left, parent1_right = parent1[:crossover_point], parent1[crossover_point:]
parent2_left, parent2_right = parent2[:crossover_point], parent2[crossover_point:]
child1 = parent1_left + parent2_right
child2 = parent2_left + parent1_right
children.append(child1)
children.append(child2)
# 返回交叉后的子代基因
return children
# 轮盘赌选择父代
children = single_point_crossover(select)
print(children)
```
输出：
#### 3.2 多点交叉
看图就能理解吧，就不解读了=========
<center>
<img src="https://img-blog.csdnimg.cn/20191202152133536.gif#pic_center" ></img>
<center>
<img src="https://img-blog.csdnimg.cn/20191202152908184.gif#pic_center" ></img>
#### 3.3部分交叉
看这篇博客吧：[遗传算法一些交叉算子](https://blog.csdn.net/u010743448/article/details/108445588)
### 4.变异操作
变异操作是遗传算法中的一种重要操作，它可以引入新的基因组合，帮助种群避免局部最优解并提高全局搜索能力。在遗传算法中，变异操作通常通过以下三个步骤来实现：
1. 随机选择一个个体：从当前种群中随机选择一个个体作为变异对象。
2. 选择一个基因位点：从该个体的染色体序列中随机选择一个基因位点（即染色体上的一个基因）。
3. 改变基因值：根据预定义的概率将该基因值进行改变。这个概率通常很小，通常设置为0.1或更小，以确保变异不会太频繁影响种群稳定性。
变异操作的实现方式有很多种，具体取决于问题的特性和目标函数的形式。例如，在二进制编码的问题中，变异操作可以通过随机翻转某些基因位来实现；在实数编码的问题中，变异操作可以通过对染色体上的某些基因进行随机加减来实现。
需要注意的是，变异操作应该谨慎使用，以防止过度变异导致种群的多样性降低。同时，由于变异操作通常会增加种群的多样性，因此应该控制变异概率，以确保种群能够平衡地进行探索和利用。
```python
# 变异操作
def mutation(population, mutation_rate):
mutated_population = []
for individual in population:
if random.random() < mutation_rate:
mutated_individual = list(individual)
gene_index = random.randint(0, len(mutated_individual) - 1)
mutated_individual[gene_index] ^= 1
mutated_population.append(mutated_individual)
else:
mutated_population.append(individual)
return mutated_population
mutated_children = mutation(children,0.01)
print("变异后的子代种群", mutated_children)
```
输出：
### 5.评估操作
这一步很简单，就是将子代的适应度求一下。
看到这了，其实你已经掌握了90%的遗传算法了，
我们将上面的操作进行一下可视化，看一下我们第一次迭代得到的效果：
> 这里，我把之前的代码中的种群个数修改为20个，提高可视化的可读性
```python
# Generate data for the fitness function curve
x_fit = np.linspace(-5, 5, 100)
y_fit = [fitness(x) for x in x_fit]
# Plot the fitness function curve
plt.plot(x_fit, y_fit, label='Fitness Function')
# Plot the population and offspring
for i, population in enumerate([population_2, mutated_children]):
x = binary_to_x(population, -5, 5, n)
x = [round(num, 1) for num in x]
fitness_values = [fitness(x) for x in x]
if i == 0:
label = 'Population'
color = 'blue'
else:
label = 'Offspring'
color = 'red'
plt.scatter(x, fitness_values, c=color, label=label)
plt.legend()
plt.xlabel('x')
plt.ylabel('Fitness')
plt.show()
```
输出：
<center>
<img src="https://img-blog.csdnimg.cn/79ade81febc04011afc3a921c691cfbc.png" ></img>
看到了把，子代函数值要大于父代，接近成功了，接下来，我们仅仅需要将上述操作迭代下去，就能逼近那个函数的最大值。
### 6.终止操作
进行完上述步骤之后，需要检查是否满足终止条件，如达到最大迭代次数或目标函数值足够小等。如果不满足，则继续执行上述步骤，直到满足终止条件为止。
根据终止条件的不同，大致可以分为以下几种终止条件设置方法：
- 迭代次数：可以设置算法运行的最大迭代次数，超过迭代次数则停止运行。
- 精度要求：可以设置算法达到一定的精度要求后，停止运行。例如，对于优化问题，当目标函数值变化很小或者收敛到一个特定值时，算法就可以停止。
- 计算时间：可以设置算法运行的最大时间，当超过这个时间限制时，算法就停止。
- ~~变异率：可以根据变异率来判断算法何时停止。如果变异率已经非常小，那么算法就可以停止。~~
- ~~种群适应性：可以设置种群适应性的阈值，当种群适应性达到一定水平时，算法就停止。~~
需要注意的是，终止条件的设置应该合理，否则可能会导致算法早停或持续运行而无法得到最优解。因此，在实际应用中，需要根据具体情况进行细致的分析和设置。
> 删除线：基础篇就不写了，有时间的话，放到进阶篇讲
#### 6.1 设置迭代次数
很好理解，就是设置迭代次数，次数到了，自然就结束了。
代码：
```python
# 二进制编码 n位二进制的选择
n = calculate_n(1, -5, 5)
print("n:", n)
# 初始化种群
population_2 = initialize_population(20, n)
print("初始化种群", population_2)
# 方便操作
population = population_2
def xunhuan(population_2, mutation_rate, a, b, n):
x = binary_to_x(population_2, a, b, n)
x = [round(num, 1) for num in x]
fitness_values = [fitness(x) for x in x]
fitness_values_nor = normalize_fitness(fitness_values, population_2)
select = roulette_wheel_selection(population_2, fitness_values_nor)
children = single_point_crossover(select)
mutated_children = mutation(children, 0.01)
return mutated_children
stop_flag = False
max_iterations = 1000
iteration_count = 0
while not stop_flag:
population = xunhuan(population, 0.01, -5, 5, n)
iteration_count += 1
if iteration_count >= max_iterations:
stop_flag = True
mutated_children = population
# Generate data for the fitness function curve
x_fit = np.linspace(-5, 5, 100)
y_fit = [fitness(x) for x in x_fit]
# Plot the fitness function curve
plt.plot(x_fit, y_fit, label='Fitness Function')
# Plot the population and offspring
for i, population in enumerate([population_2, mutated_children]):
x = binary_to_x(population, -5, 5, n)
x = [round(num, 1) for num in x]
fitness_values = [fitness(x) for x in x]
if i == 0:
label = 'Population'
color = 'blue'
else:
label = 'Offspring'
color = 'red'
plt.scatter(x, fitness_values, c=color, label=label)
plt.legend()
plt.xlabel('x')
plt.ylabel('Fitness')
plt.show()
```
输出：
<center>
<img src="https://img-blog.csdnimg.cn/7f4c660cbe024d7bb1e20a080cb14c99.png" ></img>
最后看到子代的基因几乎都为一种，恒定。这个就是我们找到的最大解。
#### 剩余两种，可以网上查阅，这里我就不介绍了，不然文章过长，又又没人看了，能看到这里的人应该也会了这个算法。
- 点赞
- 收藏
- 关注作者
评论（0）