资源描述：
《求解多维0_1背包问题的人工鱼群算法 (1)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第40卷第17期数学的实践与认识Vol.40,No.172010年9月MATHEMATICSINPRACTICEANDTHEORYSep.,2010求解多维0一1背包问题的人工鱼群算法李春梅,马良(上海理工大学管理学院,上海200093)摘要:对于多维住1背包问题,国内外学者提出了诸如模拟退火遗传算法蚁群算法以及其他启发式算法.给出一种新的智能寻优方法人工鱼群算法.算法通过各人工鱼的局部寻优,从而在群体中体现出全局最优.描述了人工鱼群算法的具体步骤并编程实现,通过多维背包算例进行了求解测试,获得了满意的效果.关键词:多维O一1背
2、包问题;人工鱼群算法;优化1引言多维0一1背包问题(Multi一Dimensionalo一1Knapsackproblem)是一个典型的组合优化问题,有着广泛的实际应用背景,如项目决策与规划材料切割资源分配货物装载等问题,并且还常常与其他相关间题结合加以研究.因此,寻找有效解决多维0一1背包问题的算法具有重要的理论价值和应用背景.背包间题的描述有多种形式,其中一般的多维整数背包间题可以在有界的前提下化成等价的多维0一1背包问题.迄今为止,对于一1背包间题的求解,人们已提出了许多有效地解决该问题的算法.一般的经典算法,如枚举法,分
3、支定界法,动态规划法等,仅适用于小规模的0一1背包间题,并且算法实现比较复杂,在实际应用中存在很大的局限性.因此,对于大规模的0一1背包间题,人们为了寻求在较短时间内得到较优解,提出了多种启发式算法,例如遗传算法禁忌搜索模拟退火神经网络蚁群算法等[l],这类算法特点是通过模拟自然生态系统机制以求解复杂优化问题的仿生优化算法,主要是面向具有大规模应用背景的问题.202年,李晓磊等人提出了一种新型的自适应寻优算法一人工鱼群算法lz](Art血ialFis卜swarmA坛orithm,AFsA),它是一种基于动物自治体的优化方法,能
4、够较好地解决非线性函数优化等问题.它具有对初值要求低参数选择不敏感鲁棒性强以及全局收敛性好等诸多优点.由于人工鱼群算法的上述特点,它可以被应用于各种不同领域的复杂间题[!一9!.因此,本文在此基础上,提出了一种用人工鱼群思想求解维一1背包问题的智能优化算法,为多维0一1背包间题的求解提供了一种新的解决手段.2多维0一1背包问题将一个维0一1背包问题可以描述为:收稿日期:201压冬10资助项目:国家自然科学基金(70871081);上海市重点学科建设资助项目(530504)1,6数学的实践与认识40卷已知n个价值为巧(j二1,2,∀
5、,川的物品,个容量大小为q#二1,2,∀,n)的容器,第J个物品所占第葱个容器的容积大小为w汀.应如何选择物品装入这二个容器,使得装入的总价值最大.问题的数学模型为:nmaxf(x1,x2,∀,珠)一艺二j=1几,了.艺∃勺∃葱=l,2,∀,ms.t.J=1x,%{o,1},j二1,2,&∀其中,f(二1,22,∀,纵):目标函数;二物品的编号;:容器的编号;马:第j个物品的价值;c∃:第∃个容器的容积;叭j:第j个物品所占第葱个容器的容积大小;xj:0一1决策变量,当物品j被选择装入时,xj二1,否则,肠二0.3人工鱼群算法3
6、.1算法思想在一片水域中,鱼往往能够自行或尾随其它鱼找到营养物质多的地方,因而鱼生存数目较多的地方一般就是本水域中富含营养物较多的地方.人工鱼群算法就是根据这一特点,通过构造人工鱼来模拟鱼群的觅食聚集以及追尾行为,从而实现全局寻优.鱼的3种生存行为:l)觅食行为:一般情况下在水里随机的自由游动,通过视觉或味觉感知水中食物量或浓度,一旦发现目标,就会向着目标方向快速游去.2)聚集行为:鱼在游动过程中自然地聚集成群进行集体觅食和躲避公害.3)追尾行为:当其中一条或几条鱼发现食物时,其临近的鱼会尾随其后快速的游去,进而导致更远处的鱼也尾随
7、游去.3.2算法描述每条人工鱼个体的状态X={zl,几,∀,几},即背包间题欲寻优的变量,它代表了一个候选方案,其中,夙二0表示该方案中未选择第乞种物品,及=l表示该方案中选择了第乞种物品;目标函数值y=f(X)表示人工鱼当前状态的食物浓度FC,即该方案的收益;人工鱼凡和人工鱼凡之间的距离为,一丫允全∀=1(二*一:)2Visual表示人工鱼的感知距离;SteP表示人工移动的步长;占表示拥挤度因子;肠yNumber表示人工鱼每次移动最大的试探次数.算法有3种行为描述和一个公告板,具体如下:l)觅食行为设人工鱼的当前状态为X∃,在其
8、感知范围内(即成,三v坛#成)随机的选择一个状态凡,若此时的食物浓度大于当前状态时,则向该方向前进一步,执行(l);反之,再重新随机选择状17期李春梅,等:求解多维0-1背包问题的人工鱼群算法197态凡,判断是否满足前进
