黄美华， 温洁嫦， 何　勇

(广东工业大学 应用数学学院, 广东 广州 510520)



求解多目标背包问题的改进人工鱼群算法

黄美华， 温洁嫦， 何勇

(广东工业大学 应用数学学院, 广东 广州 510520)

作为一种新的群智能算法,在求解多目标背包问题时,人工鱼群算法存在盲目搜索、收敛速度慢和求解精度低等问题.针对这些问题,本文结合人工鱼位置全局最优信息,对人工鱼的移动策略进行自适应改进,提出一种改进的人工鱼群算法.对多目标背包优化问题实验仿真表明,本文改进的人工鱼群算法收敛速度和搜索到的非劣解的精度均优于粒子群算法和遗传算法.

多目标优化； 背包问题； 人工鱼群算法； 自适应

多目标背包问题是一个易于描述却难以解决的NP-hard问题,在现实世界中具有广泛的应用背景.投资组合、货物装载、工程设计等都可以建模为多目标背包问题.

随着背包内物品的数量增加,考虑物品的性质增多,多目标背包问题的求解空间和时间复杂度将呈指数级增加.大规模多目标背包问题的解空间很庞大,传统的计算方法面临着计算时间长、计算成本高和搜索高质量解难等问题,需要研究有效的搜索方法,使得在求解时间和求解精度上取得平衡.粒子群算法[1-2]、遗传算法[3- 4]和蝙蝠算法[5]等,代表一类模拟自然进化的随机优化方法，能在一次模拟运行中求出多个有效解[6],所以特别适合研究多目标背包问题.

作为一种新型仿生群智能优化算法……