《MATLAB智能优化算法》学习笔记一
一、0-1背包问题概述
有$n$件物品和一个载重量为$C$的背包。第$i$件物品的质量是$w_i$,其价值是$v_i$。求解在不超过背包载重量的情况下,将哪些物品装入背包可使价值总和最大。
因此,0-1背包问题的数学模型如下:
式中,$x_i$为0-1决策变量,表示物品$i$是否被装包,如果是,则$x_i=1$,否则,$x_i=0$。
接下来以一个实例讲解上述0-1背包问题。假设现有1个背包和5个物品,背包的最大载重量为$6kg$,这5个物品的质量和价值如表所示:
枚举所有可行的装包方案:
从上表可以看出方案8的装包物品总价值是最大的。
二、算法设计
这是$n$为5的情况下,可以把所有情况列举出来,但是当$n$稍微大一点时,装包的方案就很多,一一列举出来很费力。此时枚举法已经不适合用来解决此问题了,因此我将会使用智能优化算法中的遗传算法(GA)来求解该问题。首先要给位明确的一点是,使用GA求解0-1背包问题并不能保证找到最有的装包方案。
(1)编码
编码采用01编码的形式。如选择装入物品2、3、5对应的编码就是“01101”,这个染色体(个体)就为 [0 1 1 0 1]。
(2)解码
与编码恰好相反。染色体(个体)[1 0 1 0 0] 对应的是装入背包的物品是1号和3号。
(3)约束处理
约束处理的步骤如下:
(1)将已经装进包中的物品按照性价比(性价比=价值/质量)由低到高进行排序。
(2)按照第(1)步排序结果,取走排在第1位的物品后,检验此时是否满足背包的载重量约束。如果满足约束,则将染色体中基因位上的数字1改为数字0.此时染色体初步修复完毕;如果可以不满足约束,则先将染色体中基因位上的数字1改为数字0.然后继续取走排在第2位的物品,并再次检验此时的染色体是否满足背句的载重量约束。循环往复,一直到满足背包的载重量约束为止.染色体初步修复完毕。
(3)在第(2)步已经得到满足背包载重量约束的染色体,但此时背包可能还有剩余空间。因此,将此时未装包的物品按照性价比从高到低排序,然后按照该顺序依次将物品装进包中。在装包过程中,将不满足约束的物品不装包,将满足约束的物品装包,并将染色体中基因位上的数字0改为数字1。一直遍历到最后一个未装包的物品为止,染色体最终修复完毕。
(4)适应度函数
只有对一条染色体进行合适的评价,才能保证GA在搜索过程中方向不”跑偏”。
适应度函数为物品价值之和,即
适应度值越大的染色体越优,反之越劣质。
(5)种群初始化
假设种群的数目为$NIND$,那么需要初始化$NIND$个个体(染色体)。因此只需要理解如何初始化一个个体就可以以此类推了。
假设有$n$个物品,那么一个染色体的长度为$n$,即这个染色体有$n$个数字组成(每个数字或是1或是0)。
初始化一个个体步骤如下:
①随机生成$n$个数字(每个数字或是1或是0),将此时的个体命名为Individual。
②检验Individual是否满足背包的载重约束,如果满足约束,个体Individual初始化为完毕;如果不满足约束,则对个体Individual进行约束处理,约束处理结束后,个体Individual初始化完毕。
按照一个个体初始化的方法,对$NIND$个个体全部进行初始化,初始化结束后,即完成对父代种群Chrom的初始化。
(6)选择操作
初始化种群后,种群中每个个体的适应度值都会存在差异。按道理我们应该选择适应度值大的个体来进行后续操作,但其实这样做很可能会导致种群在后续的进化中停滞不前,陷入局部最优。
所以我们不仅要多选择适应度值大的个体,还要兼顾适应度值小的个体,防止陷入局部最优。
在这里我们采用轮盘赌策略。
由于在自然界中动物也不是百分百孕育出后代,所以我们在选择个体时也不必要选择$NIND$个,可能选择出$Nsel=n\times GGAP$个($GGAP$称为代沟,是一个大于0小于等于1的随机数)。因此,我们只要转动$Nsel$次转盘就能选出子代种群SelCh。
在轮盘赌转盘上,每个个体对应一个被选中的概率。假设第$i$个个体的适应度值为$Fitness_i$,那么其被选中的概率为:
假如有4个个体,每个个体被选中的概率分别为:25%,40%,21%,14%。轮盘赌转盘如图所示:
(7)交叉操作
选择出子代种群后,我们要种群向着适应度值增大的方向进化,所以需要改变个体上的基因,因此我们的第一个操作就是交叉操作。我们看下面这个例子:
个体1 : 1 0 0 1 1 0 1 1
个体2 : 0 1 0 0 0 1 0 1
随机选择两个交叉位置,$a_1=3,a_2=5$,那么两个位置中间那段染色体就会进行交换。
交换后:
个体1 : 1 0 0 0 0 0 1 1
个体2 : 0 1 0 1 1 1 0 1
由于自然界中交叉是概率性事件且交叉概率较大,所以我们在编写代码时也要给交叉操作一个概率并且取值较大。
当种群中所有个体都需要交叉操作时,我们就会将种群中$Nsel$个个体分成$Nsel/2$组(如果$Nsel$为奇数,则在分组时不考虑最后一个个体)
(8)变异操作
这就是模拟自然界中的基因变异,我们看下面这个例子:
变异前个体 : 1 0 1 0 1 0 1 1
随机产生两个变异位置a和b,如a=2,b=5,则变异操作就是将两位置中间的基因进行逆序排列。
变异后个体 : 1 1 0 1 0 0 1 1
由于自然界中变异是概率性事件且变异概率较小,所以我们在编写代码时也要给变异操作一个概率并且取值较小。
(9)重组操作
经过上述选择操作、交叉操作和变异操作得到$Nsel$个个体,由于父代种群数目为$NIND$,所以还需要$NIND-Nsel$个个体才可以对父代种群Chrom进行更新。这$NIND-Nsel$个个体就从父代种群Chrom中找出适应度值排在前$NIND-Nsel$位的$NIND-Nsel$个个体,然后添加到子代种群SelCh中。至此新的父代种群Chrom更新完毕,作为下一次选择操作的种群。
三、求解流程
四、MATLAB程序实现
(1)判断函数:
1 | %% 判断一个个体是否满足背包的载重量约束,1表示满足,0表示不满足 |
(2)约束处理函数:
1 | %% 对违反约束的个体进行修复 |
(3)编码函数:
1 | %% 编码,生成满足约束的个体 |
(4)种群初始化函数:
1 | %% 初始化种群 |
(5)目标函数:
1 | %% 计算单个染色体的装包物品总价值和总重量 |
1 | %% 计算种群中每个染色体的物品总价值 |
(6)轮盘赌选择操作函数:
1 | %% 选择操作 |
(7)交叉操作函数:
1 | %% 交叉操作 |
(8)变异操作函数:
1 | %% 变异操作 |
(9)重组操作函数:
1 | %% 重插入子代的新种群 |
(10)主函数:
1 | tic |
五、实验结果展示
1. 《MATLAB智能优化算法》(曹旺著) ↩