%蟻群算法求解背包問題（相當于50只螞蟻每只背了一個背包）
clear?all;%清除所有變量
close?all;%清圖
clc;%清屏
m=50;%螞蟻個數
Alpha=1;%信息素重要程度參數
Beta=5;%啟發式因子重要程度參數
Rho=0.1;%信息素蒸發系數
G=200;%最大迭代次數
Q=1;%信息素增加強度系數（螞蟻循環一周或一個過程在經過的路徑上所釋放的信息量總量）
c=[98?92?95?70?72?70?83?80?65?25?50?55?40?48?50?32?22?60?30?32?40?38?35?32?25?28?30?22?50?30?45?30?60?50?20?65?20?25?30?10?56?50?30?20?15?10?8?5?3?1?];%初始化物品質量
value=[300?318?298?192?180?180?265?242?160?138?155?130?125?122?120?118?115?110?105?101?100?100?98?96?95?90?88?82?80?77?75?73?72?70?69?66?65?63?60?58?20?25?15?10?20?10?7?5?2?2];%初始化物品價值
m1=1000;%總重量約束值
C=[value;c]‘;%50x2
%第一步：變量初始化
n=size（C1）;%物品數量50
Eta=C（:1）./C（:2）;%Eta為啟發因子，價值密度50x1
Tau=ones（n1）;%Tau為信息素矩陣初始時刻各物品上的信息量相等即為const50x1
Tabu=zeros（mn）;%存儲螞蟻遍歷過的物品50x50
flag=zeros（mn）;%標識表存儲裝載的物品50x50
count=zeros（m1）;%螞蟻裝載的物品個數50x1
NC=1;%迭代計數器
R_best=zeros（Gn）;%各代最佳裝載方案200x50
L_best=inf.*ones（G1）;%各代最大價值200x1
Wsum=zeros（m1）;%存儲已裝載的重量50x1
while?NC<=G
????%第二步：將m只螞蟻放到n個物品上
????Randpos=[];
????for?i=1:（ceil（m/n））
????????Randpos=[Randposrandperm（n）];
????end
????Tabu（:1）=（Randpos（11:m））‘;%第一列為50螞蟻初始物品
????count=count+1;%背包物品數+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）<=m1
????????????????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%計算50只螞蟻中每只螞蟻所背物品最大價值
????????R=flag（i:）;
????????for?j=1:count（i）????????????
????????????L（i）=L（i）+C（R（j）1）;
????????end
????end
????L_best（NC）=max（L）;%找出50只螞蟻所背物品最大價值
????maxValue=max（L）;
????pos=find（L==L_best（NC））;%找出50只螞蟻所背物品最大價值方案
????R_best（NC:）=flag（pos（1）:）;
????NC=NC+1;
????%第五步：更新信息素
????Delta_Tau=zeros（n1）;%初始時刻信息素增量為0
????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）;
????flag=zeros（mn）;
????count=zeros（m1）;
????Wsum=zeros（m1）;??
end
%第七步：輸出結果
Pos=find（L_best==max（L_best））;
Shortest_Route=R_best（Pos（1）:）;
Best_Rout

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????3676??2017-06-26?17:09??ac.m