蚁群算法解决01背包问题

用matlab编写的运用蚁群算法解决01背包问题，经测试，可用

function [R_bestL_bestL_aveShortest_RouteShortest_Length]=ACATSP（CNC_maxmAlphaBetaRhoQv）
%%=========================================================================
%% ACATSP.m
%% Ant Colony Algorithm for Traveling Salesman Problem
%% ChengAihuaPLA Information Engineering UniversityZhengZhouChina
%% Email:aihuacheng@gmail.com
%% All rights reserved
%%-------------------------------------------------------------------------
%% 主要符号说明
%% C n个物体的价值和重量，n×2的矩阵
%% NC_max 最大迭代次数
%% m 蚂蚁个数
%% Alpha 表征信息素重要程度的参数
%% Beta 表征启发式因子重要程度的参数
%% Rho 信息素蒸发系数
%% Q 信息素增加强度系数
%% R_best 各代最佳装载方案
%% L_best 各代最大价值
%%=========================================================================

%%第一步：变量初始化
n = size（C1）;%n表示问题的规模（物体个数）

Eta = zeros（n1）;%Eta为启发因子
Eta = C（:1）./C（:2）;

Tau = ones（n1）;%Tau为信息素矩阵
Tabu = zeros（mn）;%存储蚂蚁遍历过的物体
flag = zeros（mn）;%存储装载的物体
count = zeros（m1）;%蚂蚁装载的物体个数
NC=1;%迭代计数器
R_best=zeros（NC_maxn）;%各代最佳方案
L_best=inf.*ones（NC_max1）;%各代最大价值
Wsum = zeros（m1）;%存储已装载的重量

while NC <= NC_max%停止条件之一：达到最大迭代次数
    
    %%第二步：将m只蚂蚁随机放到n个物体上
    Randpos=[];
    for i = 1:（ceil（m/n））
        Randpos = [Randposrandperm（n）];
    end
    Tabu（:1） = （Randpos（11:m））‘;
    count = count+1;
    flag（:1） = Tabu（:1）;
    
    Wsum = Wsum + C（flag（:1）2）;    
    
    %%第三步：m只蚂蚁按概率函数选择下一座物体，完成各自的周游
    for j=2:n
        for i=1:m
            visited = Tabu（i1:（j-1））;%已访问的物体
            J = zeros（1（n-j+1））;%待访问的物体
            P = J;%待访问物体的选择概率分布
            Jc = 1;
            for k = 1:n
                if length（find（visited==k））==0 
                    J（Jc） = k;
                    Jc = Jc+1;
                end
            end
            %下面计算待选物体的概率分布
            for k = 1:length（J）
                P（k） = （Tau（J（k））^Alpha）*（Eta（J（k））^Beta）;
            end
            P = P/（sum（P））;
            %按概率原则选取下一个物体
            Pcum = cumsum（P）;
            Select = find（Pcum>=rand）;
            to_visit = J（Select（1））;
            Tabu（ij） = to_visit;
            
            %判断此物体能否放入包中
            Wsum（i） = Wsum（i） + C（to_visit2）;
            if Wsum（i） <= v
                count（i） = count（i） + 1;
                flag（icount（i）） = Tabu（ij）;
            else
                Wsum（i） = Wsum（i） - C（to_visit2）;
            end     
        end
    end

    %%第四步：记录本次迭代最佳方案
    L = zeros（m1）;
    for i = 1:m
        R = flag（i:）;
        for j = 1:count（i）            
            L（i） = L（i） + C（R（j）1）;
        end
    end
    L_best（NC） = max（L）;
    
    maxValue = max（L）
    
    pos = find（L==L_best（NC））;
    R_best（NC:） = flag（pos（1）:）;
    NC=NC+1    
    
    %%第五步：更新信息素
    Delta_Tau = zeros（n1）;
    for i = 1:m
        for j = 1:count（i）
            Delta_Tau（flag（ij）） = Delta_Tau（flag（ij）） + C（flag（ij）1）*Q/L（i）;
        end
    end
    Tau = （1-Rho）.*Tau + Delta_Tau;
    
    %%第六步：禁忌表清零
    Tabu=zeros（mn）;

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件       3609  2011-08-03 11:31  蚁群算法解决01背包问题\ACATSP.m

     文件        215  2011-08-02 18:55  蚁群算法解决01背包问题\test01_10.m

     文件        904  2011-08-03 11:15  蚁群算法解决01背包问题\test01_100.m

     文件        328  2011-08-02 18:53  蚁群算法解决01背包问题\test01_20.m

     文件       1697  2011-08-03 11:25  蚁群算法解决01背包问题\test01_200.m

     文件       2482  2011-08-03 11:33  蚁群算法解决01背包问题\test01_300.m

     目录          0  2011-08-19 18:42  蚁群算法解决01背包问题

     文件        154  2011-08-19 18:44  蚁群算法解决01背包问题\readme.txt

----------- ---------  ---------- -----  ----

                 9389                    8