【背包问题】基于禁忌搜索算法求解背包问题附Matlab代码

1 内容介绍

设计了一种基于禁忌搜索的遗传算法,利用遗传算法提供的并行搜索主框架,结合禁忌算法的个体串行搜索方式,能扩大搜索空间,快速实现全局优化。把基于禁忌搜索的遗传算法与启发式方法相结合用来求解背包问题,经过计算机仿真,其优化性能指标及搜索效率均有大幅度的提高。

2 仿真代码

function [x,p1,p2]=near(x1,list)

a=[4,43,83,84,68,92,82,6,44,32,18, 56,83,25,96,70,48,14,58,92];

c=[46,90,72,91,40,75,35,8,54,78,40,77,15,61,17,75,29,75,63,44];

b=878;

temp=0;xtemp=0;

for j=1:60

    k=1;%选择初始可行解

    xt=x1;    

         while(k)        

             px=ceil(rand*19)+1;  %在[2,20]范围内随机产生一个变异位

             py=ceil(rand*19)+1;

             xt(px)=abs(xt(px)-1);             

            xt(py)=abs(xt(py)-1);

            w=a*xt;

            if w<=b

                k=0;

            end            

         end

         if (list(px)>0)&(list(py)>0)

             continue;

         else

             if (c*xt)>temp

                temp=c*xt;

                xtemp=xt;

                p1=px;p2=py;

             end

        end  

end

x=xtemp;p1=px’;

p2=py’;

3 运行结果

4 参考文献

[1]张晓琴, 黄玉清. 基于禁忌搜索的启发式求解背包问题算法[J]. 电子科技大学学报, 2005, 34(3):4.

博主简介：擅长智能优化算法、神经网络预测、信号处理、元胞自动机、图像处理、路径规划、无人机等多种领域的Matlab仿真，相关matlab代码问题可私信交流。

部分理论引用网络文献，若有侵权联系博主删除。