背包问题的遗传算法

巴山学长

发布于 2019-07-15 15:18:21

1.6K0

发布于 2019-07-15 15:18:21

文章被收录于专栏：巴山学长

MATLAB爱爱爱好者

1 引言

往期二狗已经对遗传算法和背包问题的模拟退火算法进行了介绍，即使是初学者也能对GA，Knapsack,和SA有一些认识。今天我们将会带领大家进一步、更细节地实现遗传算法的背包问题求解，从另一个角度思考这个经典问题并比较两种启发式算法的不同。细心的你可能已经发现了，无论是GA还是SA都用到了轮盘赌这个“进化之神”，所以这两种算法的解并不是固定的。之前的读者留言也有提到这个问题。

背包问题是运筹学比较常见的部分，在很多规划问题中都会涉及。一般提法是：一位旅行者携带背包去登山，已知他所能承受的背包重量限度，n种物品的单件重量及其价值。旅行者应如何选择携带各种物品的件数，以使总价值最大？实际的问题中，如航空航天的装载，投资组合的购买，规划领域铁路渠送车调度等等都可以借鉴背包问题的解法。背包问题同样可以适用于那些能被有向赋权图描述的问题。

2 程序主逻辑

程序虽然略长，但总体逻辑十分简单。上图主体调用只有一个主函数：ga_main_fcn。学过C的狗子们应该并不陌生。再根据调用需要，逐个定义各个功能函数。虽然传参使人头秃了些。GA逻辑请参考历史推送。

3 部分变量及代码讲解

首先从文件中读取背包和物体的资料：第一列是物品重量，第二列是物品价值。数据被读取为两个50*1的矩阵。这样存储是为了后续和染色体相乘计算fitness值。

w=xlsread('D:\profit_and_weight.xlsx','sheet1','A1:A50');
p=xlsread('D:\profit_and_weight.xlsx','sheet1','B1:B50');

在读取之后，先写主函数的调用语句:（只有一句）

[fitbest, chrome_best]= ga_main_fcn(popu_size);

其他函数都被封装在主函数当中。值得一提的是，这里面种群被看成了分行叠加所得的矩阵，如下图：

如果一个糖葫芦串表示一个选择的二进制编码，则上图代表了整个程序运行中最重要的两个概念：种群和种群适应性值。这个概念图在matlab中的正式表现形式如下图：

最优决策在第100行是因为定义了排序函数。

二狗自己比较喜欢的部分是fitness_fcn，适应度计算函数。

function [fit,chrome]=fitness_fcn(chf,w,p)
contain=1000;
for i=1:80
    w_s=chf(i,:)*w;
   if w_s>contain;
       fit(i)=chf(i,:)*p-1000*(w_s-1000);
       if fit(i)<0
           fit(i)=0
       end
   else
       fit(i)=chf(i,:)*p;
   end
   chrome(i,:)=chf(i,:);
end

首先是对重量和价值的计算：用 chf(i,:)*w 来表示加总，利用了matlab在矩阵运算方面的优势，十分简洁。当然遍历也可以做到。其次是淘汰机制的建立，定义了一个罚函数：

此处将alpha设为一个大于1的正数，表示将超重的背包组合淘汰掉。篇幅所限，就不在这里给大家展示更多了。有兴趣的狗子们后台回复“背包GA”领取数据文件及完整代码。希望狗子们，尤其是初学者参与进来，动手改良这段代码并积极反馈给我们。在后续的遗传算法优化的介绍中二狗也会选择比较优美的优化方法分享。一花独放不是春，百花齐放春满园。Matlab爱好者，期待您的参与。