Matlab 遗传算法——背包问题
例题描述
有16件物品，各有不同的体积、重量和价值，具体下图所示。要求选择其中若干件放入一个背包，使放入的物品总价值尽量高。该背包容量不超过93（体积单位），可承受重量不超过88（重量单位）。
变量及名词解释
需要的变量（部分）
| 变量名 | 含义 |
|---|---|
volumes | 数组中每个元素表示相应下标物体的体积 |
weight | 数组中每个元素表示相应下标物体的重量 |
values | 数组中每个元素表示相应下标物体的价值 |
volumeCapacity | 背包最大容量 |
weightCapacity | 背包最大承重能力 |
populationSize | 种群数量 |
maxIteration | 最大迭代次数 |
population | 用0/1表示的种群 |
bestFitness | 最佳适应度（最大价值） |
bestSolution | 最优解 |
correspondingVolume | 最优解相应体积 |
correspondingWeight | 最优解相应重量 |
surviveProbability | 生存概率 |
cumulativeProbability | 处理后的生存概率，便于用“轮盘赌法” |
crossoverProbability | 发生交叉互换概率 |
mutationProbability | 变异概率 |
种群
种群内是否含有个体用0/1表示，0代表不含有，1代表含有
例如在0101000101101000中，代表物品2、4、8、10、11、13装入背包中
适应度
由约束条件：
\[\sum_{i}^{16} m_{i} \le 88\]当含有0/1的字符串对应的物体质量超过88，则该个体被淘汰
例如1111011111011101对应质量为
该个体被淘汰
选择
采用似赌轮的方式进行选择，使用rand()函数生成要筛选出的个体
使用rand()生成一个0～1的数字，例如生成0.735，则生存概率小于0.735的个体死亡
配对交叉
随机选取个体，两两一组，随机进行某一位点的交叉互换
例如对于个体1001101000000100和0101000101101000
假若选到2～5位点互换：
变异
此算法仅考虑单点变异，即寻找到某个位点将数字取反
代码及逻辑示例
初始化变量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
volumeCapacity = 93; %背包容量
weightCapacity = 88; %背包承重大小
volumes = [7, 4, 8, 11, 19, 5, 3, 9, 16, 7, 8, 5, 4, 4, 3, 12]; %物品体积
weights = [12, 7, 9, 6, 7, 8, 5, 6, 18, 2, 3, 6, 2, 9, 5, 4]; %物品重量
values = [9, 8, 7, 8, 18, 7, 3, 10, 18, 4, 4, 12, 3, 5, 4, 6]; %物品价值
populationSize = 500; %种群数量
maxIteration = 200; %迭代次数
%初始化种群
population = randi([0, 1], populationSize, length(volumes));
bestFitness = 0; %最佳适应度（价值）
bestSolution = []; %最优解
correspondingWeight = 0; %最优解对应重量
correspondingVolume = 0; %最优解对应体积
总体框架
1
2
3
4
5
6
7
8
9
10
%迭代
for generation = 1:maxIteration
%计算适应度
%选择
%交叉
%变异
%更新种群
end
%寻找最优解
计算适应度
1
2
3
4
5
6
7
8
9
10
11
fitness = zeros(populationSize, 1);
for i = 1:populationSize
%计算每个个体的体积、重量、价值
totalVolume = volumes * population(i, :)';
totalWeight = weights * population(i, :)';
totalValue = values * population(i, :)';
%进行判断，当体积超出额定容量或重量超出背包最大承重能力时，使用默认适应度0，即将要淘汰
if totalVolume <= volumeCapacity && totalWeight < weightCapacity
fitness(i) = totalValue;
end
end
选择
1
2
3
4
5
6
7
8
9
surviveProbability = fitness / sum(fitness);
%将生存概率转化为累加概率，从而实现“赌轮”
cumulativeProbability = cumsum(surviveProbability);
newPopulation = zeros(populationSize, length(volumes));
for i = 1:populationSize
r = rand();
selectedIndividual = find(cumulativeProbability >= r, 1);
newPopulation(i, :) = population(selectedIndividual, :);
end
交叉
1
2
3
4
5
6
7
8
9
10
crossoverProbability = 0.8;
for i = 1:2:populationSize
if rand() < crossoverProbability
%随机选择一段发生交叉互换
crossoverPoint = randi([2 length(volumes)-1]);
tmp = newPopulation(i, crossoverPoint+1:end);
newPopulation(i, crossoverPoint+1:end) = newPopulation(i+1, crossoverPoint+1:end);
newPopulation(i+1, crossoverPoint+1:end) = tmp;
end
end
变异
1
2
3
4
5
6
7
8
mutationProbability = 0.01;
for i = 1:populationSize
for j = 1:length(volumes)
if rand() < mutationProbability
newPopulation(i, j) = ~newPopulation(i, j);
end
end
end
变异概率过小会导致缺乏多样性或收敛速度慢，过大会导致失去收敛性或过早收敛
更新种群
1
population = newPopulation;
寻找最优解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
for i = 1:populationSize
totalVolume = volumes * population(i, :)';
totalWeight = weights * population(i, :)';
totalValue = values * population(i, :)';
if totalValue > bestFitness && totalWeight <= weightCapacity && totalVolume <= volumeCapacity
bestSolution = population(i, :);
bestFitness = totalValue;
correspondingWeight = totalWeight;
correspondingVolume = totalVolume;
end
end
disp('放入物品的序号');
fprintf(' ');
for i=1:length(bestSolution)
if bestSolution(i) == 1
fprintf('%d ', i);
end
end
fprintf('\n\n');
disp('最优解对应的总价值：');
disp(bestFitness);
disp('对应重量：');
disp(correspondingWeight);
disp('对应体积：');
disp(correspondingVolume);
笔者发现，种群数量和迭代次数共同影响着求解结果。当种群数量很大时，很少的迭代次数反而比较多迭代次数多次运行后的结果更稳定；当迭代次数较多时，需要给予合适的初始种群数量才能使结果较为稳定
This post is licensed under CC BY 4.0 by the author.