求解多维0_1背包问题的蚁群算法研究

《求解多维0_1背包问题的蚁群算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第7卷%第12期软件导刊Vol.7No.122008年12月SoftwareGuideDec.2008求解多维0-1背包问题的蚁群算法研究张芹，宫洪芸（中国地质大学计算机学院，湖北武汉430074）摘要：系统地阐述了蚁群算法,并对它进行改进、优化。将蚁群算法应用于求解多维0-1背包问题,提出一种新的求解多维0-1背包问题的算法———基于交换策略的蚁群算法。关键词：多维0-1背包问题；蚁群算法；交换策略；优化中图分类号：TP312文献标识码：A文章编号：1672-7800（2008）12-0049-03n

2、1maxf（x1，x2，x3，…，xn）=Σvj*xj多维0-1背包问题j=1ns.t．Σbij*xj≤ci（i=1，2，…，m）（1）1.1问题描述j=1多维0-1背包问题就是给出一套实体及它们的价值和尺xi∈{0，1}，（i=1，2，…，n）寸，选择一个或多个互不相干的子集，使每个子集的尺寸不超其中f（x1，x2，x3，…，xn）为目标函数；xj为0-1变量，当物品j过给定边界，而被选择的价值总和最大。具体地，已知n个价值被选入时xj=1，否则xj=0。为vj（j=1，2，…，n）的物品，m个容积为

3、Ci（i=1，2，…，m）的容１.2多维0-1背包问题的图形表示器，第j个物品占用第i个容器的容积大小为bij。现在的问题是多维0-1背包问题的构造图如图1所示。该图由n+1个节点按照先后顺序排列而成，从节点i（i=1，2，…n）出发共有n条有向选择哪些物品装入这m个容器，即求一个二进制的向量X=（线段a［i，j］（j=1，2，…n）连接到节点i+1，在a［i，j］（i，j=1，2，…n）x1，x2，…，xn），使得装入的总价值最大。这是一个整数规划问题。上有vj（第j个物品的价值）和占用每个容器大小b

4、ij（i，j=1，2，…其严格的数学描述如下：n）与其相关联。３结束语参考文献:［1］王丽娜，郭迟，李鹏.信息隐藏技术实验教程［M］.武汉：武汉大学本文提出了一种基于离散小波变换（DWT）的彩色图像水出版社，2004.印算法，与二值图像和灰度图像不同，彩色图像作为水印图像［2］王丽娜，张焕国.信息隐藏技术与应用［M］.武汉：武汉大学出版嵌入与提取的难度较大，因其具有R，G，B不同的层面，在嵌入社，2003.与提取时都要充分考虑水印图像嵌入到原始图像的各层的比［3］SwansonMD，KobayashiM

5、，TewfikAH.Multimediadata例系数，从嵌入水印后图像中提取时也要考虑比例系数（本文embeddingandwatermarkingtechnologies［J］.ProceedingsoftheR，G，B各层的嵌入与提取的比例系数均取0.1），实验结果表IEEE，1986（6）.明：隐藏了水印的图像与原始图像在视觉上几乎分辨不出，较［4］龚劬，苗婷.基于图像特征的小波域自适应水印算法［J］.计算机好地达到了隐藏水印的目的，实验结果：输入图像均方差工程与应用，2007（25）.（MSE

6、）检测数据的MSE为:127.6094，待测图像的信躁比为:［5］孔祥维，刘华健，刘雨.数字图像的光电处理对数字水印的影响0.034245dB，提取的水印具有很高的峰值信噪比（PSNR=［J］.光电子·激光，2001（6）.［6］刘挺，尤韦彦.一种基于离散小波变换和HVS的彩色图像数字水51.154dB）且与原始水印具有很好的相似性（NC=0.94974），从印技术［J］.计算机工程，2003（４）.而验证了该算法的可行性。但该算法提取水印时需要原始图像（责任编辑：卓光）的参与，不能实现盲水印提取。作者

7、简介：张芹（1983~），女，湖北武汉人，中国地质大学（武汉）硕士研究生，研究方向为计算机网络；宫洪芸（1985~），女，湖北武汉人，中国地质大学（武汉）硕士研究生，研究方向为网络工程与应用。·50·软件导刊2008年步骤2：生成M只蚂蚁，并将其置于节点1。步骤3：for每只蚂蚁do{按照式（1）计算并选择下一条有向线段；如果没有有向线段满足背包问题的约束条件，则该蚂蚁就死掉；图1背包问题的图形表示如果蚂蚁没有死亡，则将选择有向线段的序号加入蚂蚁的禁忌表中；2蚁群算法}2.1算法基本思想步骤4：计算本次

8、迭代的最好解，如果其优于当前的最好蚁群算法是一种源于大自然的新型仿生类进化算法，源解，则用其替代当前的最好解。于对蚂蚁觅食模型的研究。它成功地应用于求解TSP、二次分步骤5：按照式（2）更新路径的信息素。配、图着色、车辆调度、集成电路设计以及通信网络负载等问步骤6：if（未达到NCmax）&&（没有进入停滞状态）then题。蚁群算法的基本思想是：模仿蚂蚁依赖信息素进行通信而{显示出的社会性行为，在智能体定义的基础上，由一个贪心法（1）清空所