2023年8月1日发(作者：)
【啃书】《智能优化算法及其MATLAB实例》例2.4遗传算法求解背包问题⽂章⽬录问题描述例2.4 0-1背包问题。有N件物品和⼀个容量为V背包。第件物品的体积是c（i），价值是w（i）。求解将哪些物品放⼊背包可使物品的体积总和不超过背包的容量，且价值总和最⼤。假设物品数量为10，背包的容量为300。每物积为[95，75，23，73，50，22，6，57，89，98]，价值为[89，59，19，43，100，72，44，16，7，64]。仿真过程解：仿真过程如下：（1）初始化种群数⽬为NP=50，染⾊体基因维数为L=10，最⼤进化代数为G=1002）产⽣⼆进制初始种群，其中1表⽰选择该物品，0表⽰不选择该物品。取适应度值为选择物品的价值总和，计算个体适应度值，当物品体积总和⼤于背包容量时，对适应度值进⾏惩罚计算。（3）对适应度进⾏归⼀化，采⽤基于轮盘赌的选择操作、基于概率的交叉和变异操作，产⽣新的种群，并把历代的最优个体保留在新种群中，进⾏下⼀步遗传操作。（4）判断是否满⾜终⽌条件：若满⾜，则结束搜索过程，输出优化值；若不满⾜，则继续进⾏迭代优化。优化结果为[1010111001]，1表⽰选择相应物品，0表⽰不选择相应物品，价值总和为388，其适应度进化曲线如所⽰。matlab代码%适应度函数命名为func4.m%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%function result = func4(f,C,W,V,afa)fit = sum(f.*W); % 20200928lu注：计算⽅案的物品的价值总和TotalSize = sum(f.*C); % 20200928lu注：计算⽅案的物品体积总和if TotalSize <= V % 20200928lu注：物品体积总和<背包容积 fit = fit;else fit = fit - afa * (TotalSize - V);% 20200928lu注：物品体积总和>背包容积,引⽤惩罚函数系数endresult = fit;%20200928lu注：该matlab代码成功在matlabR2019a运⾏%%%%%%%%%%%%%%%遗传算法解决0-1背包问题%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化参数%%%%%%%%%%%%%%%%%%%%%%clear all; %清变量close all; %清图clc; %清屏NP = 50; %种群规模L = 10; %物品件数Pc = 0.8; %交叉率Pm = 0.05; %变异率G = 100; %最⼤遗传代数V = 300; %背包容量C = [95,75,23,73,50,22,6,57,89,98]; %物品体积W = [89,59,19,43,100,72,44,16,7,64]; %物品价值afa = 2; %惩罚函数系数% f = randint(NP,L); %随机获得初始种群f = randi([0,1],NP,L);
%%%%%%%%%%%%%%%%%%%%%遗传算法循环%%%%%%%%%%%%%%%%%%%%%for k = 1:G %%%%%%%%%%%%%%%%%%适应度计算%%%%%%%%%%%%%%%%% for i = 1:NP Fit(i) = func4(f(i,:),C,W,V,afa);% 20200928lu注：调⽤func4适应度函数，计算适应度 end maxFit = max(Fit); %最⼤值 minFit = min(Fit); %最⼩值 rr = find(Fit==maxFit); rr = find(Fit==maxFit); fBest = f(rr(1,1),:); %历代最优个体 Fit = (Fit - minFit)/(maxFit - minFit); %归⼀化适应度值 %%%%%%%%%%%%%%基于轮盘赌的复制操作%%%%%%%%%%%%% sum_Fit = sum(Fit); fitvalue = Fit./sum_Fit; fitvalue = cumsum(fitvalue); ms = sort(rand(NP,1)); fiti = 1; newi = 1; while newi <= NP if (ms(newi)) < fitvalue(fiti) nf(newi,:) = f(fiti,:); newi = newi + 1; else fiti = fiti + 1; end end %%%%%%%%%%%%%%%基于概率的交叉操作%%%%%%%%%%%%% for i = 1:2:NP p = rand; if p < Pc% q = randint(1,L); q = randi([0,1],1,L); for j = 1:L if q(j)==1; temp = nf(i + 1,j); nf(i + 1,j) = nf(i,j); nf(i,j) = temp; end end end end %%%%%%%%%%%%%基于概率的变异操作%%%%%%%%%%%%%% for m = 1:NP for n = 1:L r = rand(1,1); if r < Pm nf(m,n) = ~nf(m,n); end end end f = nf; f(1,:) = fBest; %保留最优个体在新种群中 trace(k) = maxFit; %历代最优适应度endfBest; %最优个体figureplot(trace)xlabel('迭代次数')ylabel('⽬标函数值')string = {'适应度进化曲线';['最优价格总和=',num2str(sum(fBest.*W))]};title(string)中 智能优化算法及其MATLAB实例（第⼆版）[包⼦阳，余继周][电⼦⼯业出版社][2018年01⽉][9787121330308]
2023年8月1日发(作者：)
【啃书】《智能优化算法及其MATLAB实例》例2.4遗传算法求解背包问题⽂章⽬录问题描述例2.4 0-1背包问题。有N件物品和⼀个容量为V背包。第件物品的体积是c（i），价值是w（i）。求解将哪些物品放⼊背包可使物品的体积总和不超过背包的容量，且价值总和最⼤。假设物品数量为10，背包的容量为300。每物积为[95，75，23，73，50，22，6，57，89，98]，价值为[89，59，19，43，100，72，44，16，7，64]。仿真过程解：仿真过程如下：（1）初始化种群数⽬为NP=50，染⾊体基因维数为L=10，最⼤进化代数为G=1002）产⽣⼆进制初始种群，其中1表⽰选择该物品，0表⽰不选择该物品。取适应度值为选择物品的价值总和，计算个体适应度值，当物品体积总和⼤于背包容量时，对适应度值进⾏惩罚计算。（3）对适应度进⾏归⼀化，采⽤基于轮盘赌的选择操作、基于概率的交叉和变异操作，产⽣新的种群，并把历代的最优个体保留在新种群中，进⾏下⼀步遗传操作。（4）判断是否满⾜终⽌条件：若满⾜，则结束搜索过程，输出优化值；若不满⾜，则继续进⾏迭代优化。优化结果为[1010111001]，1表⽰选择相应物品，0表⽰不选择相应物品，价值总和为388，其适应度进化曲线如所⽰。matlab代码%适应度函数命名为func4.m%%%%%%%%%%%%%%%%%%适应度函数%%%%%%%%%%%%%%%%%function result = func4(f,C,W,V,afa)fit = sum(f.*W); % 20200928lu注：计算⽅案的物品的价值总和TotalSize = sum(f.*C); % 20200928lu注：计算⽅案的物品体积总和if TotalSize <= V % 20200928lu注：物品体积总和<背包容积 fit = fit;else fit = fit - afa * (TotalSize - V);% 20200928lu注：物品体积总和>背包容积,引⽤惩罚函数系数endresult = fit;%20200928lu注：该matlab代码成功在matlabR2019a运⾏%%%%%%%%%%%%%%%遗传算法解决0-1背包问题%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化参数%%%%%%%%%%%%%%%%%%%%%%clear all; %清变量close all; %清图clc; %清屏NP = 50; %种群规模L = 10; %物品件数Pc = 0.8; %交叉率Pm = 0.05; %变异率G = 100; %最⼤遗传代数V = 300; %背包容量C = [95,75,23,73,50,22,6,57,89,98]; %物品体积W = [89,59,19,43,100,72,44,16,7,64]; %物品价值afa = 2; %惩罚函数系数% f = randint(NP,L); %随机获得初始种群f = randi([0,1],NP,L);
%%%%%%%%%%%%%%%%%%%%%遗传算法循环%%%%%%%%%%%%%%%%%%%%%for k = 1:G %%%%%%%%%%%%%%%%%%适应度计算%%%%%%%%%%%%%%%%% for i = 1:NP Fit(i) = func4(f(i,:),C,W,V,afa);% 20200928lu注：调⽤func4适应度函数，计算适应度 end maxFit = max(Fit); %最⼤值 minFit = min(Fit); %最⼩值 rr = find(Fit==maxFit); rr = find(Fit==maxFit); fBest = f(rr(1,1),:); %历代最优个体 Fit = (Fit - minFit)/(maxFit - minFit); %归⼀化适应度值 %%%%%%%%%%%%%%基于轮盘赌的复制操作%%%%%%%%%%%%% sum_Fit = sum(Fit); fitvalue = Fit./sum_Fit; fitvalue = cumsum(fitvalue); ms = sort(rand(NP,1)); fiti = 1; newi = 1; while newi <= NP if (ms(newi)) < fitvalue(fiti) nf(newi,:) = f(fiti,:); newi = newi + 1; else fiti = fiti + 1; end end %%%%%%%%%%%%%%%基于概率的交叉操作%%%%%%%%%%%%% for i = 1:2:NP p = rand; if p < Pc% q = randint(1,L); q = randi([0,1],1,L); for j = 1:L if q(j)==1; temp = nf(i + 1,j); nf(i + 1,j) = nf(i,j); nf(i,j) = temp; end end end end %%%%%%%%%%%%%基于概率的变异操作%%%%%%%%%%%%%% for m = 1:NP for n = 1:L r = rand(1,1); if r < Pm nf(m,n) = ~nf(m,n); end end end f = nf; f(1,:) = fBest; %保留最优个体在新种群中 trace(k) = maxFit; %历代最优适应度endfBest; %最优个体figureplot(trace)xlabel('迭代次数')ylabel('⽬标函数值')string = {'适应度进化曲线';['最优价格总和=',num2str(sum(fBest.*W))]};title(string)中 智能优化算法及其MATLAB实例（第⼆版）[包⼦阳，余继周][电⼦⼯业出版社][2018年01⽉][9787121330308]
发布评论