人工智能作业-遗传算法解决背包问题

遗传算法解决背包问题

问题实例求解：已知背包的装载量为C=10, 现有n=5个物品，它们的重量和价值分别是(2,3,5,1,4)和(2,5,8,3,6)。试用遗传算法求解背包问题

这里初始的条件设置如下：

# 如果'random_problem' 不为空，则使用随机生成的问题，注意修改'max_weight'
random_problem = 0
items = [[2, 2], [3, 5], [5, 8], [1, 3], [4, 6]]
max_weight = 10
population_size = 12
mutation_rate = 0.1
generations = 100

该问题的全局最优解为 $\left(\begin{array}{ccccc}0& 0& 1& 1& 1\end{array}\right)$ with fitness: 17

为了提高迭代效率，设定当连续50次迭代中没有出现更优值则退出迭代并输出结果。

不同变异率对结果求解的影响

其他初始条件不变，对 mutation_rate 选取0.1:1,0.1的间距，分析该条件下运行100次出现全局最优解的次数。 | mutation_rate | 0.1 | 0.2 | 0.3 | 0.4 | 0.5 | 0.6 | 0.7 | 0.8 | 0.9 | 1 | |:----------------------------:|: ---- :|: ---- :|: ---- :|: ---- :|: ---- :|: ---- :|: ---- :|: ---- :|: ---- :|: ---- :| | 出现全局最优解次数 | 48 | 56 | 60 | 69 | 71 | 76 | 70 | 79 | 80 | 100 | | 平均第一次出现最优解的迭代数 | 6.44 | 6.11 | 6.25 | 5.91 | 6.78 | 9.13 | 7.56 | 7.16 | 9.56 | 8.58 | | 总耗时/ms | 518 | 564 | 570 | 481 | 464 | 522 | 463 | 577 | 462 | 545 |

type: line
labels: [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1]
series:
  - title: 最优解次数
    data: [48,56,60,69,71,76,70,79,80,100]
tension: 0.82
width: 100%
labelColors: true
fill: false
beginAtZero: false

type: line
labels: [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1]
series:
  - title: 平均第一次出现最优解的迭代数
    data: [6.44,6.11,6.25,5.91,6.78,9.13,7.56,7.16,9.56,8.58]
tension: 0.82
width: 100%
labelColors: true
fill: false
beginAtZero: false

type: line
labels: [0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1]
series:
  - title: 总耗时/ms
    data: [518,564,570,481,464,522,463,577,462,545]
tension: 0.82
width: 100%
labelColors: true
fill: false
beginAtZero: false

从数据上可以看出，随着变异率的增大，出现全局最优解的次数近似线性，而其他数据则没有明显规律，而能出现最优解的平均迭代次数都在10次以内。

不同的其他数据对结果的影响

这里可以仿造上例对其他因素进行探究，如 population_size, generations 等。但是在该问题中，全局搜索空间为32, 对上述因素进行增大会增大单次迭代中的局部搜索空间，必然会得到全局最优解，所以没有进行探究。

此外，代码中还附有随机生成的背包问题，可以继续探究遗传算法的优势。