前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >分布估计算法求解0-1背包问题一

分布估计算法求解0-1背包问题一

作者头像
mwangblog
发布2018-12-17 15:26:11
6490
发布2018-12-17 15:26:11
举报
文章被收录于专栏:mwangblog

0-1背包问题是:有一个固定容量的背包,和固定种类的物品,每种物品只有一件。每件物品有各自的价值和重量,求解哪些物品放入背包可以使价值总和最大,且不超过背包容量。

本例中用分布估计算法求解0-1背包问题结果如下:

可以看到,分布估计算法可能在很靠前的迭代中就能得到很好的解,但是由于该算法不会保留上一代最优解,因此该解很可能丢失。从平均收益图来看,种群的整体收益平均值还是增加的。

主程序

主程序主要有以下四步:

forgen = 1:maxgen

pop = makepop(popsize,stuffsize, p); % 制作种群

pop = capacitylimit(pop,capacity, weights, p); % 限制重量

spop = selection(pop, sn,profits); % 选择优势个体

p = makep(spop, p,alpha); % 更新概率向量

end

根据概率向量随机采样得到种群,并限制种群中个体的重量(不能超过背包容量),之后选择优势个体,并根据优势个体更新概率向量。进行下次迭代。

主程序如下:

functionmain()

capacity= load("bag\P08\p08_c.txt"); % 背包容量

bks= load("bag\P08\p08_s.txt"); % 最优解

bks = bks';

weights= load("bag\P08\p08_w.txt"); % 重量

weights =weights';

profits= load("bag\P08\p08_p.txt"); % 收益

profits =profits';

popsize= 100; % 群体规模

maxgen= 50; % 迭代次数

stuffsize= length(weights); % 物品数量

p= ones(1, stuffsize) .* 0.5; % 概率向量

alpha= 1; % 学习速率

sn= 0.7; % 优势个体数量

sn =ceil(popsize * sn);

bestselection= zeros(maxgen, stuffsize); % 记录每代最优选择

avgweights= zeros(1, maxgen); % 记录每代平均收益

for gen =1:maxgen

pop = makepop(popsize, stuffsize, p); % 制作种群

pop = capacitylimit(pop, capacity, weights,p); % 限制重量

wgtsum = weightsum(pop, weights);

[~, index] = max(wgtsum);

bestselection(gen, :) = pop(index, :);

avgweights(1, gen) = sum(wgtsum) / popsize;

spop = selection(pop, sn, profits); % 选择优势个体

p = makep(spop, p, alpha); % 更新概率向量

end

wgtsum =weightsum(bestselection, weights);

[~, index] =max(wgtsum);

figure(1);

plot(1:1:maxgen,wgtsum');

title("每代最优选择收益图");

figure(2);

plot(1:1:maxgen,avgweights);

title("每代平均收益图");

end

制作种群函数

制作种群函数根据概率向量p进行随机采样,直至达到种群规模。概率向量p中的一项代表在该位置上取1的概率:

function pop= makepop(popsize, stuffsize, p)

%初始化种群,但没有限制重量

%popsize input 种群规模

%stuffsize input 物品数目

%p input 概率向量

%pop output 构造的种群

pop =zeros(popsize, stuffsize);

for i=1:popsize

pop(i, :) = makepopv(stuffsize, p);

end

end

function pop= makepopv(stuffsize, p)

%初始化个体,没有限制重量

%stuffsize input 物品数目

%p input 概率向量

%pop output 构造的个体

tpop =rand(1, stuffsize);

pop =zeros(1, stuffsize);

for j =1:stuffsize

if tpop(1, j) <= p(1, j)

pop(1, j) = 1;

end

end

end

限制重量函数

如果种群中某一个个体重量超过背包容量,则重新生成该个体:

function npop= capacitylimit(pop, capacity, weights, p)

%限制重量

%pop input 种群

%capacity input 背包容量

%weights input 重量

%p input 概率向量

%npop output 新种群

npop = pop;

[popsize,stuffsize] = size(pop);

for i =1:popsize

wgtsum = weightsumv(npop(i, :), weights);

while wgtsum > capacity

npop(i, :) = makepopv(stuffsize, p);

wgtsum = weightsumv(npop(i, :),weights);

end

end

end

选择优势个体函数

从种群中选择指定数量的优势个体:

function spop= selection(pop, sn, profits)

%选择

%pop input 种群

%sn input 选择数量

%profits input 收益向量

%spop output 选择的种群

pftsum =profitssum(pop, profits);

pftsum =pftsum';

[~, index] =sort(pftsum, 'descend');

index =index(1: sn);

spop =pop(index, :);

end

更新概率向量函数

该函数更新概率向量:

function np =makep(pop, p, alpha)

%更新概率向量

%pop input 种群

%p input 概率向量

%alpha input 学习速率

%np output 更新后的概率向量

popsize =size(pop, 1);

np = (1 -alpha) .* p + alpha .* sum(pop) ./ popsize;

end

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2018-11-24,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 mwangblog 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 主程序
  • 制作种群函数
  • 限制重量函数
  • 选择优势个体函数
  • 更新概率向量函数
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档