2016, Vol. 33
多目标背包问题是一个易于描述却难以解决的NP-hard问题, 在现实世界中具有广泛的应用背景.投资组合、货物装载、工程设计等都可以建模为多目标背包问题.
随着背包内物品的数量增加, 考虑物品的性质增多, 多目标背包问题的求解空间和时间复杂度将呈指数级增加.大规模多目标背包问题的解空间很庞大, 传统的计算方法面临着计算时间长、计算成本高和搜索高质量解难等问题, 需要研究有效的搜索方法, 使得在求解时间和求解精度上取得平衡.粒子群算法[1-2]、遗传算法[3-4]和蝙蝠算法[5]等, 代表一类模拟自然进化的随机优化方法, 能在一次模拟运行中求出多个有效解[6], 所以特别适合研究多目标背包问题.
作为一种新型仿生群智能优化算法, 人工鱼群算法[7]具有鲁棒性强、全局收敛性好以及对初值要求低等优点.然而, 由于人工鱼个体的行为都是局部寻优行为, 所以难以避免个体趋同、早熟现象, 从而陷入局部极值[8].因此, 人工鱼群算法求解多目标背包问题存在收敛速度慢、求解精度不高、复杂度高等缺点.
针对上述缺点, 文献[9-11]把全局最优人工鱼信息加入人工鱼的位置更新公式中, 文献[12-15]根据鱼群整体状态的变化适时调整人工鱼的视野和步长对人工鱼群算法进行改进.
本文采用文献[12]中的自适应步长, 加入全局信息[10], 引入一个自适应因子, 自适应调整全局信息在算法中的作用, 以解决人工鱼群算法在求解多目标背包问题时收敛慢, 求解精度不高的问题.通过计算机仿真, 并与粒子群算法和遗传算法进行比较, 采用文献[3]中的评价方法评价算法的收敛性和求解精度, 证明本文改进的人工鱼群算法在多目标背包问题上的应用是有效的, 且搜索到的解质量比较高.
1 多目标背包问题及其数学模型假设存在m类物品, 每类物品中又包含n种具体物品, 现要求从这m种类别物品中分别选择一种物品放入背包中, 使得背包内物品的总价值最大, 总体积最小, 并且背包的总质量不超过c kg.背包问题的数学模型为
| $\begin{array}{*{20}{l}} {{\rm{max}}{\mathit{P}_\mathit{x}} = \sum\limits_{\mathit{i} = 1}^\mathit{n} {{\mathit{P}_\mathit{i}} \cdot {\mathit{X}^\mathit{\boldsymbol{'}}}_\mathit{i}} ,}\\ {{\rm{min}}{\mathit{R}_\mathit{x}} = \sum\limits_{\mathit{i} = 1}^\mathit{n} {{\mathit{R}_\mathit{i}} \cdot {\mathit{X}^\mathit{\boldsymbol{'}}}_\mathit{i},} }\\ {{\rm{s}}.{\rm{t}}.\sum\limits_{\mathit{i} = 1}^\mathit{n} {{\mathit{C}_\mathit{i}} \cdot {\mathit{X}^\mathit{\boldsymbol{'}}}_\mathit{i} \le \mathit{c}} .} \end{array}$ |
其中, Px表示背包内物品价值, Rx表示背包内物品体积, C表示物品质量, X为选择物品.P为每个物品的价值, R为每个物品的体积, X为一个0-1矩阵, 1表示该物品被选择, 0表示该物品不被选择.P, R, C的取值如下：
| $\begin{array}{l} P = \left[ {\begin{array}{*{20}{c}} {{p_{11}}}&{{p_{12}}}& \cdots &{{p_{1m}}}\\ {{p_{21}}}&{{p_{22}}}& \cdots &{{p_{2m}}}\\ \vdots & \vdots &{}& \vdots \\ {{p_{n1}}}&{{p_{n2}}}& \cdots &{{p_{nm}}} \end{array}} \right],\\ R = \left[ {\begin{array}{*{20}{c}} {{r_{11}}}&{{r_{12}}}& \cdots &{{r_{1m}}}\\ {{r_{21}}}&{{r_{22}}}& \cdots &{{r_{2m}}}\\ \vdots & \vdots &{}& \vdots \\ {{r_{n1}}}&{{r_{n2}}}& \cdots &{{r_{nm}}} \end{array}} \right],\\ C = \left[ {\begin{array}{*{20}{c}} {{c_{11}}}&{{c_{12}}}& \cdots &{{c_{1m}}}\\ {{c_{21}}}&{{c_{22}}}& \cdots &{{c_{2m}}}\\ \vdots & \vdots &{}& \vdots \\ {{c_{n1}}}&{{c_{n2}}}& \cdots &{{c_{nm}}} \end{array}} \right]. \end{array}$ |
在一片水域里, 鱼总是自行或尾随其他鱼朝该水域中营养物质最丰富的地方游动.人工鱼群算法就是根据鱼的这一自然特性, 模仿鱼群觅食等行为, 实现寻优.
假设在可行域内有N条人工鱼, Try_number为试探次数, δ为拥挤度因子, 视野范围为Visual, 移动步长为Step, Rand()为0到1的随机数；第i条人工鱼的当前位置为Xit, 视野范围内随机选择的一个状态Xj, 人工鱼个体间的距离为dij= Xit－Xj.若Xj所在位置的食物浓度高于当前位置, 则考虑向该位置方向移动一步到达位置Xit+1；否则继续巡视视野范围内其他位置, 位置更新表示如下:
| $\begin{array}{*{35}{l}} {{X}_{j}}=X_{i}^{t}+\rm{Visual}\cdot \rm{and()}, \\ X_{i}^{t+1}=X_{i}^{t}+\rm{ }\frac{{{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}}}{{{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}}}~\cdot \rm{Step}\cdot \rm{Rand()}. \\ \end{array}$ |
算法中Xj－Xit表示Xj和Xit之间的距离, 实际中使用的是欧氏距离.人工鱼从初始值移动到最优值的过程中, Xj和Xit之间的距离(欧氏距离、明氏距离、兰氏距离)等都是随机变化的, 并没规律可循.因此做如下变换：
| $X_{i}^{t+1}=X_{i}^{t}+({{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})~\cdot \rm{Step}\cdot \frac{\rm{Rand()}}{{{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}}}.$ |
其中, Xj是一个随机的数,
| $X_{i}^{t+1}=X_{i}^{t}+({{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})\cdot \rm{Step}\cdot \rm{Rand()}.$ |
在聚群行为和追尾行为中, 步长是一个固定的参数, 致使初期收敛速度较快, 后期不易集中, 最优解不精确.依据最优人工鱼与当前人工鱼的两种适应原则及食物浓度的比较, 确定移动步长, 表示如下：
| $\begin{array}{*{35}{l}} r\_\rm{Step}=\left| 1-\frac{{{\mathit{Y}}_{\mathit{j}}}}{{{\mathit{Y}}_{\mathit{i}}}} \right|\cdot \rm{Step}\left( 求极小值问题 \right), \\ r\_\rm{Step}=\left| 1-\frac{{{\mathit{Y}}_{\mathit{j}}}}{{{\mathit{Y}}_{\mathit{i}}}} \right|\cdot \rm{Step}\left( 求极大值问题 \right),~ \\ \end{array}$ |
即算法中移动步长大小取决于当前所在状态和视野范围中视点感知的状态[12].
2.4 全局人工鱼群算法基本人工鱼群算法中, 人工鱼的位置更新公式中只有局部信息没有全局信息.全局人工鱼群算法就是把人工鱼全局最优位置信息Xbest_af加入位置更新模式中, 实现人工鱼全局寻优[9].位置更新表示如下：
| $X_{i}^{t+1}=X_{i}^{t}+\left( \frac{({{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})+({{\mathit{X}}_{\rm{best}\_\rm{af}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})}{({{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})+({{\mathit{X}}_{\rm{best}\_\rm{af}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})} \right)\cdot \rm{Step}\cdot \rm{Rand()}.$ |
本文引入一个自适应因子w, 自适应调整全局信息在人工鱼寻找下一个位置时的判断和决策中的作用.其中,
| $w={{w}_{1}}\rm{- }\frac{{{\mathit{w}}_{2}}}{{{\mathit{T}}_{\max }}}~\cdot {{\mathit{T}}_{\rm{cur}}}.$ |
w1＞w2, Tmax为最大迭代次数, Tcur为当前迭代次数.
3.1 改进算法人工鱼的行为描述 3.1.1 觅食行为设人工鱼当前位置为Xit, 在其视野范围内随机选取位置Xj, 在求极大值问题中, 若Yi＜Yj(或求极小值为Yi＞Yj), 则朝Xj与全局最优位置Xbest_af的向量和方向移动一步；否则, 再次随机选取位置Xj, 判断是否符合移动条件, 若符合, 则向前移动一步
| $X_{i}^{t+1}=X_{i}^{t}+(({{\mathit{X}}_{\mathit{j}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})+({{\mathit{X}}_{\rm{best}\_\rm{af}}}-\mathit{X}_{\mathit{i}}^{\mathit{t}})\cdot \mathit{w})\cdot \rm{Step}\cdot \rm{Rand()}.$ |
若不符合则继续搜索, 反复尝试Try_number次后, 如果仍不符合前进条件, 则随机移动一步
| $X_{i}^{t+1}=X_{i}^{t}+\rm{Visual}\cdot \rm{Rand}().~$ |
设人工鱼当前位置为Xit, 搜索当前邻域内(即dij＜Visual)伙伴数目nf及其中心位置Xc.若
| $X_{i}^{t+1}=X_{i}^{t}+(({{X}_{c}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})+({{\mathit{X}}_{\rm{best}\_\rm{af}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})\cdot \mathit{w})\cdot \mathit{r}\_\rm{Step}\cdot \rm{Rand()},~$ |
否则执行随机行为.
3.1.3 追尾行为设人工鱼当前位置为Xit, 搜索当前邻域内(即dij＜Visual)nf个伙伴中Ym为最大的伙伴Xm.若
| $X_{i}^{t+1}=X_{i}^{t}+(({{X}_{m}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})+({{\mathit{X}}_{\rm{best}\_\rm{af}}}\rm{-}\mathit{X}_{\mathit{i}}^{\mathit{t}})\cdot \mathit{w})\cdot \mathit{r}\_\rm{Step}\cdot \rm{Rand()},~$ |
否则执行随机行为.
3.1.4 随机行为随机行为是在其视野范围内随机选取一个位置, 然后向该方向移动.其实, 它是觅食行为的一个缺省行为.
3.2 算法基本流程根据多目标搜索算法原理, 本文改进算法的基本流程如下.
Step1:初始化人工鱼初始位置以及人工鱼的相关参数, 计算每条人工鱼的适应度值, 初始筛选非劣解.
Step2:在非劣解集中随机选取人工鱼作为全局最优人工鱼, 并记录全局最优的人工鱼的状态, 计算w.
Step3:对每条人工鱼进行行为评价, 对其要执行的行为进行选择, 包括觅食、聚群、追尾和随机行为.
Step4:执行人工鱼选择的行为, 基于全局信息和局部信息更新人工鱼的位置信息.
Step5:更新全局最优人工鱼的状态.
Step6:如果达到最大迭代次数, 则更新人工鱼位置, 否则跳转到Step3.
Step7:根据新人工鱼和当前最优人工鱼的支配关系, 更新个体最优人工鱼位置, 即当两条人工鱼存在支配人工鱼时, 选择支配人工鱼, 否则从中随机选取一条人工鱼作为新的个体最优人工鱼.
Step8：非劣解筛选.
Step8.1:合并新非劣解集和旧非劣解集, 获取新的非劣解集；
Step8.2:根据非劣解集中的支配关系, 筛选出新的非劣解集.
Step9:如果达到最大迭代次数, 则输出最优解, 否则转到Step2.
4 数值实验 4.1 编码方式随机生成N条人工鱼的初始位置Xi=(xij)n×m, 其中xij(i=1, 2, …, n, j=1, 2, …, m)为1, n]的随机整数.例如存在5类物品, 每类物品中包含4种具体物品, 对每类物品中的具体物品进行编号为1, 2, 3, 4.(2, 3, 1, 4, 3) 表示：在第一类物品中取2号物品, 在第二类物品取3号物品, 在第三类物品中取1号物品, 第四类物品中取4号物品, 第五类物品中取3号物品.
4.2 数值算例算法用Matlab7.0编程, 在PC机上运行, 参数设定为Tmax=2000、N=50、Try_number=50、δ=25、Visual=10、Step=1.5、w1=10、w2=1.5.最大值与最小值问题可以互相转换, 为了能直观地评价解质量, 把求背包内物品的总体积最小问题转化为求总体积最大问题, 即总体积公式变为
| ${\rm{max}}{\mathit{R}_\mathit{x}}{\rm{ = }}\sum\limits_{\mathit{i}{\rm{ = 1}}}^\mathit{n} {\frac{{\rm{1}}}{{{\mathit{R}_\mathit{i}}}}} \cdot {\mathit{X}^\mathit{\boldsymbol{'}}}_\mathit{i}.$ |
算例1取10类物品, 每类物品包含5种物品, 分别在[1, 30], [0, 1]和[1, 30]中随机生成物品的价值、体积和质量, c取162.实验结果如图 1和图 2所示.
|
图 1 算例1各算法获得的非劣解分布情况 Figure 1 Non-dominated distribution of each algorithm of example 1 |
|
图 2 算例1各算法非劣解平均距离曲线 Figure 2 Average distance curve of the non-dominated solutions of each algorithm of example 1 |
算例2取20类物品, 每类物品包含5种物品, 分别在[1, 30], [0, 1]和[1, 30]中随机生成物品的价值、体积和质量, c取325.实验结果如图 3和图 4所示.
|
图 3 算例2各算法获得的非劣解分布情况 Figure 3 Non-dominated distribution of each algorithm of example 1 |
|
图 4 算例2各算法非劣解平均距离曲线 Figure 4 Average distance curve of the non-dominated solutions of each algorithm of example 2 |
对于本文中的多目标背包问题, 每个算法独立运行10次, 每次运行, 3个算法的初始种群都是相同的, 并迭代2 000次, 实验结果随机取其中一次.
由图 1, 图 3可以看出, 实验结果获得的Pareto最优前端在以目标空间坐标原点为球心的超球面上, 非劣解离原点越远, 解的精度越高.因而, 采用文献[3]中的评价方法, 根据某一次迭代后获得的所有非劣解到原点的距离算术平均值来评价该次迭代的求解精度, 再利用平均距离的变化趋势来评价算法的收敛性.
物品种类为10, 如图 1所示, 本文算法与遗传算法搜索到的解基本在一个球面上, 解离原点的距离比粒子群算法远, 且本文搜索到的解比遗传算法的多.如图 2所示, 本文算法的收敛速度比另外两个算法快, 解比较稳定.
当物品种类为20, 如图 3所示, 本文算法搜索到的解与原点距离远远大于另外两个算法, 且分布均匀.如图 4所示, 本文算法的收敛速度, 解的精度、稳定性和均匀的优势更加明显.
6 结语本文提出一种基于自适应移动策略, 加入位置全局最优信息的人工鱼群算法, 并用其求解多目标背包问题.仿真结果表明, 本文改进的人工鱼群算法在求解多目标背包问题上是有效的, 收敛速度和求解精度均优于遗传算法和粒子群算法.随着多目标背包问题中物品种类增加一倍, 本文算法的优势更加明显.
| [1] | 史峰, 王辉, 胡斐, 等. MATLAB智能算法30个案例分析[M]. 北京: 北京航空航天大学出版社, 2011. |
| [2] |
张雁, 肖伟. 基于禁忌粒子群求解多目标0-1背包问题研究与实现[J].
软件导刊, 2012, 11(3): 36-37.
ZHANG Y, XIAO W. The Research and implementation of multiple knapsack problem on Tabu PSO[J]. Software Guide, 2012, 11(3): 36-37. |
| [3] |
郭观七, 杨观赐, 黄韬, 等. 用遗传算法求解多目标0/1背包问题[J].
湖南理工学院学报, 2004, 17(4): 18-21.
GUO G Q, YANG G C, HUANG T, et al. Solving multi-objective 0/1 knapsack problems by genetic algorithms[J]. Journal of Hunan Institute of Science and Technology: Natural Sciences Edition, 2004, 17(4): 18-21. |
| [4] |
温金宝, 蔡延光. 基于自适应小生境遗传算法的物流配送路径优化研究[J].
广东工业大学学报, 2011, 28(1): 20-23.
WEN J B, CAI Y G. On the optimization of logistics distribution route based on self-adaption nice genetic algorithm[J]. Journal of Guangdong University of Technology, 2011, 28(1): 20-23. |
| [5] |
李枝勇, 马良, 张慧珍. 蝙蝠算法在多目标背包问题中的应用[J].
计算机仿真, 2013, 30(10): 350-353.
LI Z Y, MA L, ZHANG H Z. Application of bat algorithm in multi-objective and multi-choice knapsack problem[J]. Journal of Computer Simulation, 2013, 30(10): 350-353. DOI: 10.3969/j.issn.1006-9348.2013.10.080. |
| [6] |
刘海林, 刘永清. 多目标最优进化算法中适应性的选择[J].
广东工业大学学报, 2002, 19(1): 7-10.
LIU H L, LIU Y Q. The fitness selection about evolutionary algorithms for multi-objective optimization[J]. Journal of Guangdong University of Technology, 2002, 19(1): 7-10. |
| [7] |
李晓磊, 邵之江, 钱积新. 一种基于动物自治体的寻优模式:鱼群算法[J].
系统工程理论与实践, 2002, 22(11): 32-38.
LI X L, SHAO Z J, QIAN J X. An optimizing method based on autonomous animats: fish-swarm algorithm[J]. Systems Engineering-Theory & Practice, 2002, 22(11): 32-38. DOI: 10.3321/j.issn:1000-6788.2002.11.007. |
| [8] |
王翠茹, 周春雷, 马建伟. 一种改进的人工鱼群算法及其在软件可靠性优化中的应用[J].
计算机研究与发展, 2005, 4(S): 163-166.
WANG C R, ZHOU C L, MA J W. An Improved artificial fish-swarm algorithm and its application in software reliability optimization[J]. Journal of Computer Research and Development, 2005, 4(S): 163-166. |
| [9] | 程永明. 群智能优化算法及其在通信中的应用研究[D]. 济南: 山东大学信息科学与工程学院, 2010. |
| [10] | JIANG M Y, YUAN D F, CHENG Y M. Improved artificial fish swarm algorithm[C]//Proceedings of the 5th International Conference on Natural Computation. Tianjin: IEEE: 2009: 281-285. |
| [11] |
王联国, 洪毅, 施秋红. 全局版人工鱼群算法[J].
系统仿真学报, 2009, 21(23): 7483-7486.
WANG L G, HONG Y, SHI Q H. Global edition artificial fish swarm algorithm[J]. Journal of System Simulation, 2009, 21(23): 7483-7486. |
| [12] | 李晓磊. 一种新型的智能优化方法——人工鱼群算法[D]. 杭州: 浙江大学系统工程研究所, 2003. |
| [13] |
廖煜雷, 苏玉明, 张磊. 一种自适应人工鱼群算法及其在无人艇控制中的应用[J].
中南大学学报:自然科学版, 2013, 44(10): 4109-4116.
LIAO Y L, SU Y M, ZHANG L. Adaptive artificial fish swarm algorithm and application in control of unmanned surface vessel[J]. Journal of Central South University:Science and Technology, 2013, 44(10): 4109-4116. |
| [14] |
朱旭辉, 倪志伟, 程美英. 变步长自适应的改进人工鱼群算法[J].
计算机科学, 2015, 42(2): 210-216.
ZHU X H, NI Z W, CHENG M Y. Self-adaptive improved artificial fish swarm algorithm with changing step[J]. Computer Science, 2015, 42(2): 210-216. DOI: 10.11896/j.issn.1002-137X.2015.02.044. |
| [15] |
马宪民, 刘妮. 自适应视野的人工鱼群算法求解最短路径问题[J].
通信学报, 2014, 35(1): 1-6.
MA X M, LIU N. Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem[J]. Journal on Communications, 2014, 35(1): 1-6. |
| [16] | 江铭武, 袁东风. 人工鱼群算法及其应用[M]. 北京: 科学出版社, 2012. |