# 遗传算法求最值问题
## 一、遗传算法
### 1.1 遗传算法简介
遗传算法是一种进化算法,基于自然选择和生物遗传等生物进化机制的一种搜索算法,其通过选择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的解,再从这组改进的解出发进一步改进。在搜索过程中,它利用结构和随机的信息,是满足目标的决策获得最大的生存可能,是一种概率型算法。
遗传算法主要借用生物中“适者生存”的原则,在遗传算法中,染色体对应的是数据或数组,通常由一维的串结构数据来表示。串上的各个位置对应一个基因座,而各个位置上所取的值对等位基因。遗传算法处理的是基因型个体,一定数量的个体组成了群体。群体的规模就是个体的数目。不同个体对环境的适应度不同,适应度打的个体被选择进行遗传操作产生新个体。每次选择两个染色体进行产生一组新染色体,染色体也可能发生变异,得到下一代群体。
### 1.2 遗传算法基本要素
1. **参数编码**:可以采用位串编码、实数编码、多参数级联编码等
2. **设定初始群体**:
1. 启发 / 非启发给定一组解作为初始群体
2. 确定初始群体的规模
3. **设定适应度函数**:将目标函数映射为适应度函数,可以进行尺度变换来保证非负、归一等特性
4. **设定遗传操作**:
1. 选择:从当前群体选出一系列优良个体,让他们产生后代个体,一般采用蒙特卡洛法,即按适应度占比分配概率
2. 交叉:两个个体的基因进行交叉重组来获得新个体
3. 变异:随机变动个体串基因座上的某些基因
5. **设定控制参数**:例如变异概率、交叉程度、迭代上限等
### 1.3 遗传算法一般步骤
![](https://www.writebug.com/myres/static/uploads/2022/9/9/ab7cad656c94a7019c8c0e8c777f100e.writebug)
## 二、程序说明
### 2.1 控制参数
以 ***ga_max.py*** 为例,默认参数如下:
| 变量 | 默认值 | 含义 |
| -------------- | ------ | -------- |
| **DNA_SIZE** | 24 | 编码长度 |
| **POP_SIZE** | 100 | 种群大小 |
| **CROSS_RATE** | 0.8 | 交叉率 |
| **MUTA_RATE** | 0.15 | 编译率 |
| **Iterations** | 1000 | 迭代次数 |
### 2.2 编码规则
***ga_max.py*** 和 ***ga_min.py*** 采用一样的编码规则,由于一个解是一个二元组 ***(x,y)*** ,编码采用多参数级联编码,编码步骤如下:
1. 设一个 DNA 是一个长度为 ***l*** 的二进制码串,因为解是二元组,一个染色体长为 ***2l***;
2. 使用奇偶级联的方式级联两条 DNA,即染色体二进制串的奇数位是 ***x*** 的 DNA,偶数位是 ***y*** 的 DNA;
3. 解码时需要将 ***x*** 和 ***y*** 分别从染色体中取出,然后映射到解空间,解空间是 [0,10] X [0,10],用 $2^l$ 均匀划分解空间来获得实际的 ***x*** 和 ***y***。
代码如下:
``` python
# 编码
# pop(二维矩阵) = 种群数 * (DNA长度 * 2) 个 0,1 随机数
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2))
# 解码
# 奇数列表示 X:取 pop 的奇数位
# 偶数列表示 Y:取 pop 的偶数位
x_pop = pop[:,1::2]
y_pop = pop[:,::2]
# 二进制转十进制,在归一化塞入区间[0,10]中
x = x_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(X_BOUND[1]-X_BOUND[0])+X_BOUND[0]
y = y_pop.dot(2**np.arange(DNA_SIZE)[::-1])/float(2**DNA_SIZE-1)*(Y_BOUND[1]-Y_BOUND[0])+Y_BOUND[0]
```
### 2.3 选择初始群体
对于一个函数求最大值/最小值问题,一般启发式信息比较少,故程序采用完全随机生成来产生初始群体。
``` python
# 产生初始群体 pop
# pop(二维矩阵) = 种群数 * (DNA长度 * 2) 个 0,1 随机数
pop = np.random.randint(2, size=(POP_SIZE, DNA_SIZE * 2))
```
### 2.4 适应度函数
适应度函数给予待求解的问题函数,为了方便后续的选择操作,一般保证适应度函数为正, ***ga_max.py*** 和 ***ga_min.py*** 的适应度函数分别如下。
虽然实验分别给出了最大值和最小值的算法,但实际上没什么必要,因为在求一个问题的最小值,只需将问题表达式乘以 -1,再用最大值算法求解即可。
```python
# 最大值问题的适应度函数
def getfitness(pop): # 计算适应度函数
x,y = decodeDNA(pop)
temp = F(x, y)
return (temp - np.min(temp)) + 0.0001 # 减去最小的适应度是为了防止适应度出现负数
```
```python
# 最小值问题的适应度函数
def getfitness(pop):
x,y = decodeDNA(pop)
temp = F(x, y)
return -(temp - np.max(temp)) + 0.0001 # 减去最大的适应度是为了防止适应度出现负数
```
### 2.5 遗传操作
* **选择**:使用蒙特卡洛法,即个体被选择的概率为其适应度占群体总适应度的比例`(fitness)/(fitness.sum())`
``` python
def select(pop, fitness): # 根据适应度选择
temp = np.random.choice(np.arange(POP_SIZE), size=POP_SIZE, replace=True,p=(fitness)/(fitness.sum()))
return pop[temp]
```
* **交换**:以概率 CROSS_RATE 进行两点交叉(交换两个染色体两点间的片段)
```python
temp = i # 子代先得到父亲的全部基因
if np.random.rand() < CROSS_RATE: # 以交叉概率发生交叉
j = pop[np.random.randint(POP_SIZE)] # 从种群中随机选择另一个个体,并将该个体作为母代
cpoints1 = np.random.randint(0, DNA_SIZE*2-1) # 随机产生交叉的点
cpoints2 = np.random.randint(cpoints1,DNA_SIZE*2)
temp[cpoints1:cpoints2] = j[cpoints1:cpoints2] # 子代得到位于交叉点后的母代的基因
```
* **变异**:以概率 MUTA_RATE 进行变异,变异行为具体为随机选取一个二进制位进行反转
```python
def mutation(temp, MUTA_RATE):
if np.random.rand() < MUTA_RATE: # 以MUTA_RATE的概率进行变异
mutate_point = np.random.randint(0, DNA_SIZE) # 随机产生一个实数,代表要变异基因的位置
temp[mutate_point] = temp[mutate_point]^1 # 将变异点的二进制为反转
```
### 2.6 迭代过程
```python
for _ in range(Iterations): # 迭代 Iterations 代
pop = np.array(crossmuta(pop, CROSS_RATE)) # 交换变异
fitness = getfitness(pop) # 计算适应度函数
pop = select(pop, fitness) # 选择生成新的种群
```
## 三、参数测试
下面以 ***ga_max.py*** 为例,通过调整参数,研究单一参数的变化对求解结果和求解耗时的影响,相关代码在附录 - 2,测试图表分别为修改不同参数下耗时、最优值、最右适应度的变化。
### 3.1 编码长度
* 编码长度测试范围:[6,30],每一个长度重复测试 10 次来减小随机误差。
* 测试显示随着编码长度的增加,算法耗时和适应度有降低趋势,最优值变化较小。
![](https://www.writebug.com/myres/static/uploads/2022/9/9/9c0191759684b86c12fda673be0e0a86.writebug)
### 3.2 种群大小
* 种群大小测试范围:[20,800],每一个长度重复测试 3 次来减小随机误差。
* 测试显示随着编码长度的增加,算法耗时呈线性增加,在种群数目大于100时最优值和最右适应度比较稳定。
![](https://www.writebug.com/myres/static/uploads/2022/9/9/0d62d790309d749cbcd10242b67dadb3.writebug)
### 3.3 交叉率
* 交叉率测试范围:[0,1],每一个长度重复测�
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
遗传算法是一种进化算法,基于自然选择和生物遗传等生物进化机制的一种搜索算法,其通过选择、重组和变异三种操作实现优化问题的求解。它的本质是从原问题的一组解出发改进到另一组较好的解,再从这组改进的解出发进一步改进。在搜索过程中,它利用结构和随机的信息,是满足目标的决策获得最大的生存可能,是一种概率型算法。
资源推荐
资源详情
资源评论
收起资源包目录
100011711-基于Python实现遗传算法求最值问题.zip (21个子文件)
ga_max
image
CROSS_RATE.png 52KB
POP_SIZE.png 51KB
OPT2.png 22KB
DNA_SIZE.png 46KB
ITERATION.png 55KB
OPT1.png 37KB
GA.png 9KB
MUTA_RATE.png 52KB
LICENSE 1KB
.idea
遗传算法求最值.iml 284B
vcs.xml 189B
misc.xml 185B
inspectionProfiles
profiles_settings.xml 174B
modules.xml 294B
ga_min.py 3KB
opt_2.py 8KB
ga_max.py 13KB
Report.pdf 605KB
__pycache__
ga_max.cpython-38.pyc 8KB
README.md 17KB
遗传算法求最值实验程序使用说明.docx 34KB
共 21 条
- 1
资源评论
神仙别闹
- 粉丝: 2679
- 资源: 7667
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功