當前位置:首頁 » 操作系統 » 蜂群演算法matlab

蜂群演算法matlab

發布時間: 2024-06-16 19:34:58

A. 有沒有人有多目標人工蜂群演算法的MATLAB代碼。發我一份 不勝感激!!

http://emuch.net/bbs/attachment.php?tid=3808850&aid=11221&pay=yes
裡面有多個文件
其中之一
%/* ABC algorithm coded using MATLAB language */

%/* Artificial Bee Colony (ABC) is one of the most recently defined algorithms by Dervis Karaboga in 2005, motivated by the intelligent behavior of honey bees. */

%/* Referance Papers*/

%/*D. Karaboga, AN IDEA BASED ON HONEY BEE SWARM FOR NUMERICAL OPTIMIZATION,TECHNICAL REPORT-TR06, Erciyes University, Engineering Faculty, Computer Engineering Department 2005.*/

%/*D. Karaboga, B. Basturk, A powerful and Efficient Algorithm for Numerical Function Optimization: Artificial Bee Colony (ABC) Algorithm, Journal of Global Optimization, Volume:39, Issue:3,pp:459-171, November 2007,ISSN:0925-5001 , doi: 10.1007/s10898-007-9149-x */

%/*D. Karaboga, B. Basturk, On The Performance Of Artificial Bee Colony (ABC) Algorithm, Applied Soft Computing,Volume 8, Issue 1, January 2008, Pages 687-697. */

%/*D. Karaboga, B. Akay, A Comparative Study of Artificial Bee Colony Algorithm, Applied Mathematics and Computation, 214, 108-132, 2009. */

%/*Copyright ?2009 Erciyes University, Intelligent Systems Research Group, The Dept. of Computer Engineering*/

%/*Contact:
%Dervis Karaboga ([email protected] )
%Bahriye Basturk Akay ([email protected])
%*/

clear all
close all
clc

%/* Control Parameters of ABC algorithm*/
NP=20; %/* The number of colony size (employed bees+onlooker bees)*/
FoodNumber=NP/2; %/*The number of food sources equals the half of the colony size*/
limit=100; %/*A food source which could not be improved through "limit" trials is abandoned by its employed bee*/
maxCycle=2500; %/*The number of cycles for foraging {a stopping criteria}*/

%/* Problem specific variables*/
objfun='Sphere'; %cost function to be optimized
D=100; %/*The number of parameters of the problem to be optimized*/
ub=ones(1,D)*100; %/*lower bounds of the parameters. */
lb=ones(1,D)*(-100);%/*upper bound of the parameters.*/

runtime=1;%/*Algorithm can be run many times in order to see its robustness*/

%Foods [FoodNumber][D]; /*Foods is the population of food sources. Each row of Foods matrix is a vector holding D parameters to be optimized. The number of rows of Foods matrix equals to the FoodNumber*/
%ObjVal[FoodNumber]; /*f is a vector holding objective function values associated with food sources */
%Fitness[FoodNumber]; /*fitness is a vector holding fitness (quality) values associated with food sources*/
%trial[FoodNumber]; /*trial is a vector holding trial numbers through which solutions can not be improved*/
%prob[FoodNumber]; /*prob is a vector holding probabilities of food sources (solutions) to be chosen*/
%solution [D]; /*New solution (neighbour) proced by v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij}) j is a randomly chosen parameter and k is a randomlu chosen solution different from i*/
%ObjValSol; /*Objective function value of new solution*/
%FitnessSol; /*Fitness value of new solution*/
%neighbour, param2change; /*param2change corrresponds to j, neighbour corresponds to k in equation v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij})*/
%GlobalMin; /*Optimum solution obtained by ABC algorithm*/
%GlobalParams[D]; /*Parameters of the optimum solution*/
%GlobalMins[runtime]; /*GlobalMins holds the GlobalMin of each run in multiple runs*/

GlobalMins=zeros(1,runtime);

for r=1:runtime

% /*All food sources are initialized */
%/*Variables are initialized in the range [lb,ub]. If each parameter has different range, use arrays lb[j], ub[j] instead of lb and ub */

Range = repmat((ub-lb),[FoodNumber 1]);
Lower = repmat(lb, [FoodNumber 1]);
Foods = rand(FoodNumber,D) .* Range + Lower;

ObjVal=feval(objfun,Foods);
Fitness=calculateFitness(ObjVal);

%reset trial counters
trial=zeros(1,FoodNumber);

%/*The best food source is memorized*/
BestInd=find(ObjVal==min(ObjVal));
BestInd=BestInd(end);
GlobalMin=ObjVal(BestInd);
GlobalParams=Foods(BestInd,:);

iter=1;
while ((iter <= maxCycle)),

%%%%%%%%% EMPLOYED BEE PHASE %%%%%%%%%%%%%%%%%%%%%%%%
for i=1:(FoodNumber)

%/*The parameter to be changed is determined randomly*/
Param2Change=fix(rand*D)+1;

%/*A randomly chosen solution is used in procing a mutant solution of the solution i*/
neighbour=fix(rand*(FoodNumber))+1;

%/*Randomly selected solution must be different from the solution i*/
while(neighbour==i)
neighbour=fix(rand*(FoodNumber))+1;
end;

sol=Foods(i,:);
% /*v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij}) */
sol(Param2Change)=Foods(i,Param2Change)+(Foods(i,Param2Change)-Foods(neighbour,Param2Change))*(rand-0.5)*2;

% /*if generated parameter value is out of boundaries, it is shifted onto the boundaries*/
ind=find(sol<lb);
sol(ind)=lb(ind);
ind=find(sol>ub);
sol(ind)=ub(ind);

%evaluate new solution
ObjValSol=feval(objfun,sol);
FitnessSol=calculateFitness(ObjValSol);

% /*a greedy selection is applied between the current solution i and its mutant*/
if (FitnessSol>Fitness(i)) %/*If the mutant solution is better than the current solution i, replace the solution with the mutant and reset the trial counter of solution i*/
Foods(i,:)=sol;
Fitness(i)=FitnessSol;
ObjVal(i)=ObjValSol;
trial(i)=0;
else
trial(i)=trial(i)+1; %/*if the solution i can not be improved, increase its trial counter*/
end;

end;

%%%%%%%%%%%%%%%%%%%%%%%% CalculateProbabilities %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%/* A food source is chosen with the probability which is proportioal to its quality*/
%/*Different schemes can be used to calculate the probability values*/
%/*For example prob(i)=fitness(i)/sum(fitness)*/
%/*or in a way used in the metot below prob(i)=a*fitness(i)/max(fitness)+b*/
%/*probability values are calculated by using fitness values and normalized by dividing maximum fitness value*/

prob=(0.9.*Fitness./max(Fitness))+0.1;

%%%%%%%%%%%%%%%%%%%%%%%% ONLOOKER BEE PHASE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

i=1;
t=0;
while(t<FoodNumber)
if(rand<prob(i))
t=t+1;
%/*The parameter to be changed is determined randomly*/
Param2Change=fix(rand*D)+1;

%/*A randomly chosen solution is used in procing a mutant solution of the solution i*/
neighbour=fix(rand*(FoodNumber))+1;

%/*Randomly selected solution must be different from the solution i*/
while(neighbour==i)
neighbour=fix(rand*(FoodNumber))+1;
end;

sol=Foods(i,:);
% /*v_{ij}=x_{ij}+\phi_{ij}*(x_{kj}-x_{ij}) */
sol(Param2Change)=Foods(i,Param2Change)+(Foods(i,Param2Change)-Foods(neighbour,Param2Change))*(rand-0.5)*2;

% /*if generated parameter value is out of boundaries, it is shifted onto the boundaries*/
ind=find(sol<lb);
sol(ind)=lb(ind);
ind=find(sol>ub);
sol(ind)=ub(ind);

%evaluate new solution
ObjValSol=feval(objfun,sol);
FitnessSol=calculateFitness(ObjValSol);

% /*a greedy selection is applied between the current solution i and its mutant*/
if (FitnessSol>Fitness(i)) %/*If the mutant solution is better than the current solution i, replace the solution with the mutant and reset the trial counter of solution i*/
Foods(i,:)=sol;
Fitness(i)=FitnessSol;
ObjVal(i)=ObjValSol;
trial(i)=0;
else
trial(i)=trial(i)+1; %/*if the solution i can not be improved, increase its trial counter*/
end;
end;

i=i+1;
if (i==(FoodNumber)+1)
i=1;
end;
end;

%/*The best food source is memorized*/
ind=find(ObjVal==min(ObjVal));
ind=ind(end);
if (ObjVal(ind)<GlobalMin)
GlobalMin=ObjVal(ind);
GlobalParams=Foods(ind,:);
end;

%%%%%%%%%%%% SCOUT BEE PHASE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%/*determine the food sources whose trial counter exceeds the "limit" value.
%In Basic ABC, only one scout is allowed to occur in each cycle*/

ind=find(trial==max(trial));
ind=ind(end);
if (trial(ind)>limit)
Bas(ind)=0;
sol=(ub-lb).*rand(1,D)+lb;
ObjValSol=feval(objfun,sol);
FitnessSol=calculateFitness(ObjValSol);
Foods(ind,:)=sol;
Fitness(ind)=FitnessSol;
ObjVal(ind)=ObjValSol;
end;

fprintf('Ýter=%d ObjVal=%g\n',iter,GlobalMin);
iter=iter+1;

end % End of ABC

GlobalMins(r)=GlobalMin;
end; %end of runs

save all

B. 優化演算法筆記(八)人工蜂群演算法

(以下描述,均不是學術用語,僅供大家快樂的閱讀)
工蜂群演算法(Artificial Bee Colony Algorithm,ABC)是一種模仿蜜蜂采蜜機理而產生的群智能優化演算法。其原理相對復雜,但實現較為簡單,在許多領域中都有研究和應用。
人工蜂群演算法中,每一個蜜源的位置代表了待求問題的一個可行解。蜂群分為采蜜蜂、觀察蜂和偵查蜂。采蜜蜂與蜜源對應,一個采蜜蜂對應一個蜜源。觀察蜂則會根據采蜜蜂分享的蜜源相關信息選擇跟隨哪個采蜜蜂去相應的蜜源,同時該觀察蜂將轉變為偵查蜂。偵查蜂則自由的搜索新的蜜源。每一個蜜源都有開採的限制次數,當一個蜜源被采蜜多次而達到開采限制次數時,在寬檔該蜜源采蜜的采蜜蜂將轉變為偵查蜂。每個偵查蜂將隨機尋找一個新蜜源進行開采,並轉變成為采蜜蜂。

下面是我的實現方式(我的答案):
1. 三種蜜蜂之間可以相互轉化。
采蜜蜂->觀察蜂:有觀察蜂在采蜜過程中發現了比當前采蜜蜂更好的蜜源,則采蜜蜂放棄當前蜜源轉而變成觀察蜂跟隨優質蜜源,同時該觀察蜂轉變為采蜜蜂。
采蜜蜂->觀察蜂:當該采蜜蜂所發現的蜜源被開采完後,它會轉變為觀察蜂去跟隨其他采蜜蜂。
采蜜蜂->偵查蜂:當所有的采蜜蜂發現的蜜源都被開采完後,采蜜蜂將會變為偵查蜂,觀察蜂也會變成偵查蜂,因為大家都無蜜可采。
偵查蜂->采蜜蜂、觀察蜂:偵查蜂隨機搜索蜜源,選擇較好的數個蜜源位置的蜜蜂為采蜜蜂,其他蜜蜂為觀察蜂。

2.蜜源的數量上限
蜜源的數量上限等於采蜜蜂的數量上限。初始化時所有蜜蜂都是偵查蜂,在這些偵查蜂所搜索到的蜜源中選出數個較優的蜜源,發現這些蜜源的偵查蜂變為采蜜蜂,其他蜜蜂變為觀察蜂。直到所有的蜜源都被開采完之前,蜜源的數量不會增加,因為這個過程中沒有產生偵查蜂緩配。所有的蜜源都被開采完後,所有的蜜蜂再次全部轉化為偵查蜂,新的一輪蜜源搜索開始。也可以在一個蜜源開采完時馬上產生一個新的蜜源補充,保證在整個開采過程中蜜源數量恆定不變。

蜜源的開采實際上就是觀察蜂跟隨采蜜蜂飛向蜜源的過程。得到的下一代的位置公式如下:

表示第i只觀察蜂在第t代時隨機選擇第r只採蜜蜂飛行一段距離,其中R為(-1,1)的隨機數。

一隻觀察蜂在一次迭代過程中只能選擇一隻采蜜蜂跟隨,它需要從眾多的采蜜蜂中選擇一隻來進行跟隨。觀察蜂選擇的策略很簡單,隨機跟隨一隻采蜜蜂,該采蜜蜂發現的蜜源越優,則選擇它的概率越大。
是不是很像輪盤賭,對,這就是輪盤賭,同時我們也可以稍作修改,比如將勤勞的小蜜蜂改為懶惰的小蜜蜂,小蜜蜂會根據蜜源的優劣和距離以及開采程度等因素綜合來選擇跟隨哪只採蜜蜂(雖然影響不大,但聊勝於無)。
忘記了輪盤賭的小夥伴可以看一下 優化演算法筆記(六)遺傳演算法 。
下面是我的人工蜂群演算法流程圖

又到了實驗環節,參數實驗較多,慎哪亂全部給出將會佔用太多篇幅,僅將結果進行匯總展示。

實驗1:參數如下

上圖分別為采蜜蜂上限為10%總數和50%總數的情況,可以看出當采蜜蜂上限為10%總群數時,種群收斂的速度較快,但是到最後有一個點死活不動,這是因為該點作為一個蜜源,但由於適應度值太差,使用輪盤賭被選擇到的概率太小從而沒有得到更佳的蜜源位置,而因未開采完,采蜜蜂又不能放棄該蜜源。
看了看采蜜蜂上限為50%總群數時的圖,發現也有幾個點不動的狀態,可以看出,這時不動的點的數量明顯多於上限為10%總數的圖,原因很簡單,采蜜蜂太多,「先富」的人太多,而「後富」的人較少,沒有帶動「後富者」的「先富者」也得不到發展。
看看結果

嗯,感覺結果並沒有什麼差別,可能由於問題較簡單,迭代次數較少,無法體現出采蜜蜂數對於結果的影響,也可能由於蜜源的搜索次數為60較大,總群一共只能對最多20*50/60=16個蜜源進行搜索。我們將最大迭代次數調大至200代再看看結果

當最大迭代次數為200時,人工蜂群演算法的結果如上圖,我們可以明顯的看出,隨著采蜜蜂上限的上升,演算法結果的精度在不斷的下降,這也印證了之前的結果,由於蜜源搜索次數較大(即搜索深度較深)采蜜蜂數量越多(搜索廣度越多),結果的精度越低。不過影響也不算太大,下面我們再來看看蜜源最大開采次數對結果的影響。
實驗2:參數如下

上圖分別是蜜源開采限度為1,20和4000的實驗。
當蜜源開采上限為1時,即一個蜜源只能被開采一次,即此時的人工蜂群演算法只有偵查蜂隨機搜索的過程,沒有觀察蜂跟隨采蜜蜂的過程,可以看出圖中的蜜蜂一直在不斷的隨機出現在新位置不會向某個點收斂。
當蜜源開采上限為20時,我們可以看到此時種群中的蜜蜂都會向一個點飛行。在一段時間內,有數個點一動不動,這些點可能就是采蜜蜂發現的位置不怎麼好的蜜源,但是在幾次迭代之後,它們仍會被觀察蜂開采,從而更新位置,蜜源開采上限越高,它們停頓的代數也會越長。在所有蜜蜂都收斂於一個點之後,我們可以看到仍會不斷的出現其他的隨機點,這些點是偵查蜂進行隨機搜索產生的新的蜜源位置,這些是人工蜂群演算法跳出局部最優能力的體現。
當蜜源開采上限為4000時,即不會出現偵查蜂的搜索過程,觀察蜂只會開采初始化時出現的蜜源而不會采蜜蜂不會有新的蜜源產生,可以看出在蜂群收斂後沒有出現新的蜜源位置。

看看最終結果,我們發現,當蜜源開采上線大於1時的結果提升,但是好像開采上限為5時結果明顯好於開采次數上限為其他的結果,而且隨著開采次數不斷上升,結果在不斷的變差。為什麼會出現這樣的結果呢?原因可能還是因為問題較為簡單,在5次開採的限度內,觀察蜂已經能找到更好的蜜源進行開采,當問題較為復雜時,我們無法知曉開采發現新蜜源的難度,蜜源開采上限應該取一個相對較大的值。當蜜源開采限度為4000時,即一個蜜源不可能被開采完(開采次數為20(種群數)*200(迭代次數)),搜索的深度有了但是其結果反而不如開采限度為幾次幾十次來的好,而且這樣不會有偵查蜂隨機搜索的過程,失去了跳出局部最優的能力。
我們應該如何選擇蜜源的最大開采次數限制呢?其實,沒有最佳的開采次數限制,當適應度函數較為簡單時,開采次數較小時能得到比較好的結果,但是適應度函數較復雜時,經過試驗,得出的結果遠差於開采次數較大時。當然,前面就說過,適應度函數是一個黑盒模型,我們無法判斷問題的難易。那麼我們應該選擇一個適中的值,個人的選擇是種群數的0.5倍到總群數的2倍作為蜜源的最大開采次數,這樣可以保證極端情況下,1-2個迭代周期內小蜜蜂們能將一個蜜源開采完。

人工蜂群演算法算是一個困擾我比較長時間的演算法,幾年時間里,我根據文獻實現的人工蜂群演算法都有數十種,只能說人工蜂群演算法的描述太過模糊,或者說太過抽象,研究者怎麼實現都說的通。但是通過實現多次之後發現雖然實現細節大不相同,但效果相差不多,所以我們可以認為人工蜂群演算法的穩定性比較強,只要實現其主要思想即可,細節對於結果的影響不太大。
對於人工蜂群演算法影響最大的因素還是蜜源的開采次數限制,開采次數限制越大,對同一蜜源的開發力度越大,但是分配給其他蜜源的搜索力度會相對減少,也會降低蜂群演算法的跳出局部最優能力。可以動態修改蜜源的開采次數限制來實現對演算法的改進,不過效果不顯著。
其次對於人工蜂群演算法影響是三類蜜蜂的搜索行為,我們可以重新設計蜂群的搜索方式來對演算法進行改進,比如采蜜蜂在開采蜜源時是隨機飛向其他蜜源,而觀察蜂向所選的蜜源靠近。這樣改進有一定效果但是在高維問題上效果仍不明顯。
以下指標純屬個人yy,僅供參考

目錄
上一篇 優化演算法筆記(七)差分進化演算法
下一篇 優化演算法筆記(九)杜鵑搜索演算法

優化演算法matlab實現(八)人工蜂群演算法matlab實現

C. 優化演算法筆記(二)優化演算法的分類

(以下描述,均不是學術用語,僅供大家快樂的閱讀)

在分類之前,我們先列舉一下常見的優化演算法(不然我們拿什麼分類呢?)。
1遺傳演算法Genetic algorithm
2粒子群優化演算法Particle Swarm Optimization
3差分進化演算法Differential Evolution
4人工蜂群演算法Artificial Bee Colony
5蟻群演算法Ant Colony Optimization
6人工魚群演算法Artificial Fish Swarm Algorithm
7杜鵑搜索演算法Cuckoo Search
8螢火蟲演算法Firefly Algorithm
9灰狼演算法Grey Wolf Optimizer
10鯨魚演算法Whale Optimization Algorithm
11群搜索演算法Group search optimizer
12混合蛙跳演算法Shuffled Frog Leaping Algorithm
13煙花演算法fireworks algorithm
14菌群優化演算法Bacterial Foraging Optimization
以上優化演算法是我所接觸過的演算法,沒接觸過的演算法不能隨便下結論,知之為知之,不知為不知。其實到目前為止優化演算法可能已經有幾百種了,我們不可能也不需要全面的了解所有的演算法,而且優化演算法之間也有較大的共性,深入研究幾個之後再看其他優化演算法上手速度會灰常的快。
優化演算法從提出到現在不過50-60年(遺傳演算法1975年提出),雖種類繁多但大多較為相似,不過這也很正常,比較香蕉和人的基因相似度也有50%-60%。當然演算法之間的相似度要比香蕉和人的相似度更大,畢竟人家都是優化演算法,有著相同的目標,只是實現方式不同。就像條條大路通羅馬,我們可以走去,可以坐汽車去,可以坐火車去,也可以坐飛機去,不管使用何種方式,我們都在去往羅馬的路上,也不會說坐飛機去要比走去更好,交通工具只是一個工具,最終的方案還是要看我們的選擇。

上面列舉了一些常見的演算法,即使你一個都沒見過也沒關系,後面會對它們進行詳細的介紹,但是對後面的分類可能會有些許影響,不過問題不大,就先當總結看了。
再對優化演算法分類之前,先介紹一下演算法的模型,在筆記(一)中繪制了優化演算法的流程,不過那是個較為簡單的模型,此處的模型會更加復雜。上面說了優化演算法有較大的相似性,這些相似性主要體現在演算法的運行流程中。
優化演算法的求解過程可以看做是一個群體的生存過程。

有一群原始人,他們要在野外中尋找食物,一個原始人是這個群體中的最小單元,他們的最終目標是尋找這個環境中最容易獲取食物的位置,即最易存活下來的位置。每個原始人都去獨自尋找食物,他們每個人每天獲取食物的策略只有採集果實、製作陷阱或者守株待兔,即在一天之中他們不會改變他們的位置。在下一天他們會根據自己的策略變更自己的位置。到了某一天他們又聚在了一起,選擇了他們到過的最容易獲取食物的位置定居。
一群原始人=優化演算法中的種群、群體;
一個原始人=優化演算法中的個體;
一個原始人的位置=優化演算法中個體的位置、基因等屬性;
原始人變更位置=優化演算法中總群的更新操作;
該位置獲取食物的難易程度=優化演算法中的適應度函數;
一天=優化演算法中的一個迭代;
這群原始人最終的定居位置=優化演算法所得的解。
優化演算法的流程圖如下:

對優化演算法分類得有個標准,按照不同的標准分類也會得到不一樣的結果。首先說一下我所使用的分類標准(動態更新,有了新的感悟再加):

按由來分類比較好理解,就是該演算法受何種現象啟發而發明,本質是對現象分類。

可以看出演算法根據由來可以大致分為有人類的理論創造而來,向生物學習而來,受物理現象啟發。其中向生物學習而來的演算法最多,其他類別由於舉例有偏差,不是很准確,而且物理現象也經過人類總結,有些與人類現象相交叉,但仍將其獨立出來。
類別分好了,那麼為什麼要這么分類呢?

當然是因為要湊字數啦,啊呸,當然是為了更好的理解學習這些演算法的原理及特點。
向動物生存學習而來的演算法一定是一種行之有效的方法,能夠保證演算法的效率和准確性,因為,如果使用該策略的動物無法存活到我們可以對其進行研究,我們也無法得知其生存策略。(而這也是一種倖存者偏差,我們只能看到行之有效的策略,但並不是我們沒看到的策略都是垃圾,畢竟也發生過小行星撞地球這種小概率毀滅性事件。講個冷笑話開cou心一shu下:一隻小恐龍對他的小夥伴說,好開心,我最喜歡的那顆星星越來越亮了(完)。)但是由於生物的局限性,人們所創造出的演算法也會有局限性:我們所熟知的生物都生存在三維空間,在這些環境中,影響生物生存的條件比較有限,反應到演算法中就是這些演算法在解決較低維度的問題時效果很好,當遇到超高維(維度>500)問題時,結果可能不容樂觀,沒做過實驗,我也不敢亂說。

按更新過程分類相對復雜一點,主要是根據優化演算法流程中更新位置操作的方式來進行分類。更新位置的操作按我的理解可大致分為兩類:1.跟隨最優解;2.不跟隨最優解。
還是上面原始人的例子,每天他有一次去往其他位置狩獵的機會,他們採用何種方式來決定今天自己應該去哪裡呢?
如果他們的策略是「跟隨最優解」,那麼他們選取位置的方式就是按一定的策略向群體已知的最佳狩獵位置(歷史最佳)或者是當前群體中的最佳狩獵位置(今天最佳)靠近,至於是直線跑過去還是蛇皮走位繞過去,這個要看他們群體的策略。當然,他們的目的不是在最佳狩獵位置集合,他們的目的是在過去的途中看是否能發現更加好的狩獵位置,去往已經到過的狩獵地點再次狩獵是沒有意義的,因為每個位置獲取食物的難易程度是固定的。有了目標,大家都會朝著目標前進,總有一日,大家會在謀個位置附近相聚,相聚雖好但不利於後續的覓食容易陷入局部最優。
什麼是局部最優呢?假設在當前環境中有一「桃花源」,擁有上帝視角的我們知道這個地方就是最適合原始人們生存的,但是此地入口隱蔽「山有小口,彷彿若有光」、「初極狹,才通人。」,是一個難以發現的地方。如果沒有任何一個原始人到達了這里,大家向著已知的最優位置靠近時,也難以發現這個「桃源之地」,而當大家越聚越攏之後,「桃源」被發現的可能性越來越低。雖然原始人們得到了他們的解,但這並不是我們所求的「桃源」,他們聚集之後失去了尋求「桃源」的可能,這群原始人便陷入了局部最優。

如果他們的策略是「不跟隨最優解」,那麼他們的策略是什麼呢?我也不知道,這個應該他們自己決定。畢竟「是什麼」比「不是什麼」的范圍要小的多。總之不跟隨最優解時,演算法會有自己特定的步驟來更新個體的位置,有可能是隨機在自己附近找,也有可能是隨機向別人學習。不跟隨最優解時,原始人們應該不會快速聚集到某一處,這樣一來他們的選擇更具多樣性。
按照更新過程對上面的演算法分類結果如下

可以看出上面不跟隨最優解的演算法只有遺傳演算法和差分進化演算法,他們的更新策略是與進化和基因的重組有關。因此這些不跟隨最優解的演算法,他們大多依據進化理論更新位置(基因)我把他們叫做進化演算法,而那些跟隨群體最優解的演算法,他們則大多依賴群體的配合協作,我把這些演算法叫做群智能演算法。

目前我只總結了這兩種,分類方法,如果你有更加優秀的分類方法,我們可以交流一下:

目錄
上一篇 優化演算法筆記(一)優化演算法的介紹
下一篇 優化演算法筆記(三)粒子群演算法(1)

D. 人工蜂群演算法的蜜蜂采蜜機理

蜜蜂是一種群居昆蟲,雖然單個昆蟲的行為極其簡單,但是由單個簡單的個體所組成的群體卻表現出極其復雜的行為。真實的蜜蜂種群能夠在任何環境下,以極高的效率從食物源(花朵)中採集花蜜;同時,它們能適應環境的改變。
蜂群產生群體智慧的最小搜索模型包含基本的三個組成要素:食物源、被僱傭的蜜蜂(employed foragers)和未被僱傭的蜜蜂(unemployed foragers);兩種最為基本的行為模型:為食物源招募(recruit)蜜蜂和放棄(abandon)某個食物源。
(1)食物源:食物源的價值由多方面的因素決定,如:它離蜂巢的遠近,包含花蜜的豐富程度和獲得花蜜的難易程度。使用單一的參數,食物源的「收益率」(profitability),來代表以上各個因素。
(2)被僱用的蜜蜂:也稱引領蜂(Leader),其與所採集的食物源一一對應。引領蜂儲存有某一個食物源的相關信息(相對於蜂巢的距離、方向、食物源的豐富程度等)並且將這些信息以一定的概率與其他蜜蜂分享。
(3)未被僱用的蜜蜂:其主要任務是尋找和開採食物源。有兩種未被僱用的蜜蜂:偵查蜂(Scouter)和跟隨蜂(Follower)。偵察蜂搜索蜂巢附近的新食物源;跟隨蜂等在蜂巢裡面並通過與引領蜂分享相關信息找到食物源。一般情況下,偵察蜂的平均數目是蜂群的5%-20%。
在群體智慧的形成過程中,蜜蜂間交換信息是最為重要的一環。舞蹈區是蜂巢中最為重要的信息交換地。蜜蜂的舞蹈叫做搖擺舞。食物源的信息在舞蹈區通過搖擺舞的形式與其他蜜蜂共享,引領蜂通過搖擺舞的持續時間等來表現食物源的收益率,故跟隨蜂可以觀察到大量的舞蹈並依據收益率來選擇到哪個食物源采蜜。收益率與食物源被選擇的可能性成正比。因而,蜜蜂被招募到某一個食物源的概率與食物源的收益率成正比。
初始時刻,蜜蜂以偵察蜂的身份搜索。其搜索可以由系統提供的先驗知識決定,也可以完全隨機。經過一輪偵查後,若蜜蜂找到食物源,蜜蜂利用它本身的存儲能力記錄位置信息並開始采蜜。此時,蜜蜂將成為「被僱用者」。蜜蜂在食物源采蜜後回到蜂巢卸下蜂蜜然後將有如下選擇:
(1)放棄食物源而成為非僱傭蜂。
(2)跳搖擺舞為所對應的食物源招募更多的蜜蜂,然後回到食物源采蜜。
(3)繼續在同一個食物源采蜜而不進行招募。
對於非僱傭蜂有如下選擇:
(1)轉變成為偵察蜂並搜索蜂巢附近的食物源。其搜索可以由先驗知識決定,也可以完全隨機。
(2)在觀察完搖擺舞後被僱用成為跟隨蜂,開始搜索對應食物源鄰域並采蜜。

E. java人工蜂群演算法求解TSP問題

一、人工蜂群演算法的介紹

人工蜂群演算法(Artificial Bee Colony, ABC)是由Karaboga於2005年提出的一種新穎的基於群智能的全局優化演算法,其直觀背景來源於蜂群的采蜜行為,蜜蜂根據各自的分工進行不同的活動,並實現蜂群信息的共享和交流,從而找到問題的最優解。人工蜂群演算法屬於群智能演算法的一種。

二、人工蜂群演算法的原理

1、原理

標準的ABC演算法通過模擬實際蜜蜂的采蜜機制將人工蜂群分為3類: 采蜜蜂、觀察蜂和偵察蜂。整個蜂群的目標是尋找花蜜量最大的蜜源。在標準的ABC演算法中,采蜜蜂利用先前的蜜源信息尋找新的蜜源並與觀察蜂分享蜜源信息;觀察蜂在蜂房中等待並依據采蜜蜂分享的信息尋找新的蜜源;偵查蜂的任務是尋找一個新的有價值的蜜源,它們在蜂房附近隨機地尋找蜜源。

假設問題的解空間是

代碼:

[cpp]view plain

  • #include<iostream>

  • #include<time.h>

  • #include<stdlib.h>

  • #include<cmath>

  • #include<fstream>

  • #include<iomanip>

  • usingnamespacestd;

  • constintNP=40;//種群的規模,采蜜蜂+觀察蜂

  • constintFoodNumber=NP/2;//食物的數量,為采蜜蜂的數量

  • constintlimit=20;//限度,超過這個限度沒有更新采蜜蜂變成偵查蜂

  • constintmaxCycle=10000;//停止條件

  • /*****函數的特定參數*****/

  • constintD=2;//函數的參數個數

  • constdoublelb=-100;//函數的下界

  • constdoubleub=100;//函數的上界

  • doubleresult[maxCycle]={0};

  • /*****種群的定義****/

  • structBeeGroup

  • {

  • doublecode[D];//函數的維數

  • doubletrueFit;//記錄真實的最小值

  • doublefitness;

  • doublerfitness;//相對適應值比例

  • inttrail;//表示實驗的次數,用於與limit作比較

  • }Bee[FoodNumber];

  • BeeGroupNectarSource[FoodNumber];//蜜源,注意:一切的修改都是針對蜜源而言的

  • BeeGroupEmployedBee[FoodNumber];//采蜜蜂

  • BeeGroupOnLooker[FoodNumber];//觀察蜂

  • BeeGroupBestSource;//記錄最好蜜源

  • /*****函數的聲明*****/

  • doublerandom(double,double);//產生區間上的隨機數

  • voidinitilize();//初始化參數

  • doublecalculationTruefit(BeeGroup);//計算真實的函數值

  • doublecalculationFitness(double);//計算適應值

  • voidCalculateProbabilities();//計算輪盤賭的概率

  • voidevalueSource();//評價蜜源

  • voidsendEmployedBees();

  • voidsendOnlookerBees();

  • voidsendScoutBees();

  • voidMemorizeBestSource();

  • /*******主函數*******/

  • intmain()

  • {

  • ofstreamoutput;

  • output.open("dataABC.txt");

  • srand((unsigned)time(NULL));

  • initilize();//初始化

  • MemorizeBestSource();//保存最好的蜜源

  • //主要的循環

  • intgen=0;

  • while(gen<maxCycle)

  • {

  • sendEmployedBees();

  • CalculateProbabilities();

  • sendOnlookerBees();

  • MemorizeBestSource();

  • sendScoutBees();

  • MemorizeBestSource();

  • output<<setprecision(30)<<BestSource.trueFit<<endl;

  • gen++;

  • }

  • output.close();

  • cout<<"運行結束!!"<<endl;

  • return0;

  • }

  • /*****函數的實現****/

  • doublerandom(doublestart,doubleend)//隨機產生區間內的隨機數

  • {

  • returnstart+(end-start)*rand()/(RAND_MAX+1.0);

  • }

  • voidinitilize()//初始化參數

  • {

  • inti,j;

  • for(i=0;i<FoodNumber;i++)

  • {

  • for(j=0;j<D;j++)

  • {

  • NectarSource[i].code[j]=random(lb,ub);

  • EmployedBee[i].code[j]=NectarSource[i].code[j];

  • OnLooker[i].code[j]=NectarSource[i].code[j];

  • BestSource.code[j]=NectarSource[0].code[j];

  • }

  • /****蜜源的初始化*****/

  • NectarSource[i].trueFit=calculationTruefit(NectarSource[i]);

  • NectarSource[i].fitness=calculationFitness(NectarSource[i].trueFit);

  • NectarSource[i].rfitness=0;

  • NectarSource[i].trail=0;

  • /****采蜜蜂的初始化*****/

  • EmployedBee[i].trueFit=NectarSource[i].trueFit;

  • EmployedBee[i].fitness=NectarSource[i].fitness;

  • EmployedBee[i].rfitness=NectarSource[i].rfitness;

  • EmployedBee[i].trail=NectarSource[i].trail;

  • /****觀察蜂的初始化****/

  • OnLooker[i].trueFit=NectarSource[i].trueFit;

  • OnLooker[i].fitness=NectarSource[i].fitness;

  • OnLooker[i].rfitness=NectarSource[i].rfitness;

  • OnLooker[i].trail=NectarSource[i].trail;

  • }

  • /*****最優蜜源的初始化*****/

  • BestSource.trueFit=NectarSource[0].trueFit;

  • BestSource.fitness=NectarSource[0].fitness;

  • BestSource.rfitness=NectarSource[0].rfitness;

  • BestSource.trail=NectarSource[0].trail;

  • }

  • doublecalculationTruefit(BeeGroupbee)//計算真實的函數值

  • {

  • doubletruefit=0;

  • /******測試函數1******/

  • truefit=0.5+(sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*sin(sqrt(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))-0.5)

  • /((1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1]))*(1+0.001*(bee.code[0]*bee.code[0]+bee.code[1]*bee.code[1])));

  • returntruefit;

  • }

  • doublecalculationFitness(doubletruefit)//計算適應值

  • {

  • doublefitnessResult=0;

  • if(truefit>=0)

  • {

  • fitnessResult=1/(truefit+1);

  • }else

  • {

  • fitnessResult=1+abs(truefit);

  • }

  • returnfitnessResult;

  • }

  • voidsendEmployedBees()//修改采蜜蜂的函數

  • {

  • inti,j,k;

  • intparam2change;//需要改變的維數

  • doubleRij;//[-1,1]之間的隨機數

  • for(i=0;i<FoodNumber;i++)

  • {

  • param2change=(int)random(0,D);//隨機選取需要改變的維數

  • /******選取不等於i的k********/

  • while(1)

  • {

  • k=(int)random(0,FoodNumber);

  • if(k!=i)

  • {

  • break;

  • }

  • }

  • for(j=0;j<D;j++)

  • {

  • EmployedBee[i].code[j]=NectarSource[i].code[j];

  • }

  • /*******采蜜蜂去更新信息*******/

  • Rij=random(-1,1);

  • EmployedBee[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]);

  • /*******判斷是否越界********/

  • if(EmployedBee[i].code[param2change]>ub)

  • {

  • EmployedBee[i].code[param2change]=ub;

  • }

  • if(EmployedBee[i].code[param2change]<lb)

  • {

  • EmployedBee[i].code[param2change]=lb;

  • }

  • EmployedBee[i].trueFit=calculationTruefit(EmployedBee[i]);

  • EmployedBee[i].fitness=calculationFitness(EmployedBee[i].trueFit);

  • /******貪婪選擇策略*******/

  • if(EmployedBee[i].trueFit<NectarSource[i].trueFit)

  • {

  • for(j=0;j<D;j++)

  • {

  • NectarSource[i].code[j]=EmployedBee[i].code[j];

  • }

  • NectarSource[i].trail=0;

  • NectarSource[i].trueFit=EmployedBee[i].trueFit;

  • NectarSource[i].fitness=EmployedBee[i].fitness;

  • }else

  • {

  • NectarSource[i].trail++;

  • }

  • }

  • }

  • voidCalculateProbabilities()//計算輪盤賭的選擇概率

  • {

  • inti;

  • doublemaxfit;

  • maxfit=NectarSource[0].fitness;

  • for(i=1;i<FoodNumber;i++)

  • {

  • if(NectarSource[i].fitness>maxfit)

  • maxfit=NectarSource[i].fitness;

  • }

  • for(i=0;i<FoodNumber;i++)

  • {

  • NectarSource[i].rfitness=(0.9*(NectarSource[i].fitness/maxfit))+0.1;

  • }

  • }

  • voidsendOnlookerBees()//采蜜蜂與觀察蜂交流信息,觀察蜂更改信息

  • {

  • inti,j,t,k;

  • doubleR_choosed;//被選中的概率

  • intparam2change;//需要被改變的維數

  • doubleRij;//[-1,1]之間的隨機數

  • i=0;

  • t=0;

  • while(t<FoodNumber)

  • {

  • R_choosed=random(0,1);

  • if(R_choosed<NectarSource[i].rfitness)//根據被選擇的概率選擇

  • {

  • t++;

  • param2change=(int)random(0,D);

  • /******選取不等於i的k********/

  • while(1)

  • {

  • k=(int)random(0,FoodNumber);

  • if(k!=i)

  • {

  • break;

  • }

  • }

  • for(j=0;j<D;j++)

  • {

  • OnLooker[i].code[j]=NectarSource[i].code[j];

  • }

  • /****更新******/

  • Rij=random(-1,1);

  • OnLooker[i].code[param2change]=NectarSource[i].code[param2change]+Rij*(NectarSource[i].code[param2change]-NectarSource[k].code[param2change]);

  • /*******判斷是否越界*******/

  • if(OnLooker[i].code[param2change]<lb)

  • {

  • OnLooker[i].code[param2change]=lb;

  • }

  • if(OnLooker[i].code[param2change]>ub)

  • {

  • OnLooker[i].code[param2change]=ub;

  • }

  • OnLooker[i].trueFit=calculationTruefit(OnLooker[i]);

  • OnLooker[i].fitness=calculationFitness(OnLooker[i].trueFit);

  • /****貪婪選擇策略******/

  • if(OnLooker[i].trueFit<NectarSource[i].trueFit)

  • {

  • for(j=0;j<D;j++)

  • {

  • NectarSource[i].code[j]=OnLooker[i].code[j];

  • }

  • NectarSource[i].trail=0;

  • NectarSource[i].trueFit=OnLooker[i].trueFit;

  • NectarSource[i].fitness=OnLooker[i].fitness;

  • }else

  • {

  • NectarSource[i].trail++;

  • }

  • }

  • i++;

  • if(i==FoodNumber)

  • {

  • i=0;

  • }

  • }

  • }

  • 熱點內容
    免費的文件夾加密大師 發布:2024-07-23 03:44:44 瀏覽:451
    3位密碼鎖密碼是多少 發布:2024-07-23 03:17:55 瀏覽:209
    linuxandroid內核版本 發布:2024-07-23 02:37:24 瀏覽:73
    緩存模型導出max 發布:2024-07-23 02:20:53 瀏覽:98
    android進程回收 發布:2024-07-23 02:20:52 瀏覽:660
    數組打亂php 發布:2024-07-23 02:20:52 瀏覽:66
    西安php 發布:2024-07-23 02:16:05 瀏覽:213
    無冬腳本 發布:2024-07-23 02:16:04 瀏覽:996
    方舟伺服器推薦什麼模式 發布:2024-07-23 02:07:17 瀏覽:390
    淘寶支付密碼怎麼改 發布:2024-07-23 02:01:37 瀏覽:927