一、細菌覓食算法簡介
實際生活需求促進了最優化方法的發展。近半個多世紀以來,由于傳統優化方法的不足,一些具有全局優化性能且通用性強的進化算法,因其高效的優化性能、無需問題精确描述資訊等優點,受到各領域廣泛的關注和應用。其中産生最早也最具代表性的進化算法是20世紀70年代源于達爾文自然選擇學說和孟德爾遺傳變異理論的遺傳算法(Genetic Algorithm,GA)。而近年來,人們模拟自然界生物群體行為産生出一系列群體智能優化算法,如Dorigo等通過模拟螞蟻的尋徑行為于1991年提出了蟻群優化算法(Ant Colony Optimization,ACO);Eberhart和Kennedy通過模拟鳥群捕食行為于1995年提出了粒子群優化算法(Particle Swarm Optimization,PSO)。這些算法被廣泛應用于工程領域并取得了顯著的成果。随着群體智能優化算法的蓬勃發展,Passino于2002年提出了模拟人類大腸杆菌覓食行為的細菌覓食優化算法(Bacteria Foraging Optimization Algorithm,BFOA),為仿生進化算法家族增添了新成員。本章将着重向廣大程式設計愛好者介紹最基本的細菌覓食算法,各程式設計科研人員可以基于本章算法加以改進并應用到實際案例中。
1 标準細菌覓食優化算法
2 趨向性操作(Chemotaxis)
3 聚集性操作(Swarming)
4 複制性操作(Reproduction)
5 遷徙性操作(Elimination and Dispersal)
實際環境中的細菌所生活的局部區域可能會發生逐漸變化(如食物消耗殆盡)或者發生突如其來的變化(如溫度突然升高等)。這樣可能會導緻生活在這個局部區域的細菌種群被遷徙到新的區域中去或者集體被外力殺死。在BFO算法中模拟這種現象稱為遷徙性操作。
6 BFO算法流程
二、部分源代碼
%*********************Hybrid Bacterial Foraging with Parameter free PSO**********************
clear;
clc;
tic
a = 'lena.jpg';
x=imread(a);
a=rgb2gray(x);
count=imhist(a);
[m,n]=size(a);
N=m*n;
L=256;
count=count/N;
u0=0;
u=0;
for i=1:L
u0=u0+(i-1)*count(i);
w(i)=sum(count(1:i)); %w(i)是前i個像素的累加機率
u = u + (i-1)*count(i);
ua(i)= u;
end
%-----(1)初始化參數-----
p = 2; % 搜尋範圍的次元
BacterialNum = 20; % 細菌的個數
Nc = 30; %趨化的次數(Number of Chemotaxis steps)
Ns = 4; %趨化操作中單向運動的最大步數(Number of Swimming steps)
Nre = 4; %複制操作步驟數(Number of reproduction steps)
step=0.05; %翻轉標明方向後,單個細菌前進的步長
Sr = BacterialNum/2; %每代複制(分裂)數
range = 255;
for i = 1:BacterialNum % 産生初始細菌個體的位置
Bacterial(i).location = range * rand(1,p);
end
%------先計算各個細菌的适應度,并初始化Pbest----------------------
for i=1:BacterialNum
Bacterial(i).bestFitness = CalFitness1(Bacterial(i).location,w,ua,u0);
Bacterial(i).bestLocation = Bacterial(i).location;
end
%-----(2)複制操作開始-----
for k = 1:Nre
%-----(3)趨化操作(翻轉或遊動)開始-----
for j = 1:Nc
%-----對每一個細菌分别進行以下操作-----
for i = 1:BacterialNum
%-----(3a)計算适應度值
Bacterial(i).fitness = CalFitness1(Bacterial(i).location,w,ua,u0);
%-----儲存細菌目前的适應度值,直到找到更好的适應度值取代之-----
Bacterial_last = Bacterial(i);
%-----(3b)翻轉,産生一個随機向量,代表翻轉後細菌的方向-----
Delta = rands(1,p);
% PHI表示翻轉後選擇的一個随機方向上前進(機關向量)
PHI = Delta/sqrt(Delta*Delta');
%-----(3c)移動,向着翻轉後細菌的方向移動一個步長,并且改變細菌的位置-----
Bacterial(i).location = Bacterial(i).location + step*PHI;
%-----計算細菌目前位置的适應度值-----
Bacterial(i).fitness = CalFitness1(Bacterial(i).location,w,ua,u0);
%-----(3d)遊動-----
m = 0; % 給遊動長度計數器賦初始值
while(m < Ns) % 未達到遊動的最大長度,則循環
m = m + 1;
% 新位置的适應度值是否更好?如果更好,将新位置的适應度值存儲為細菌i目前最好的适應度值
if Bacterial(i).fitness < Bacterial_last.fitness
Bacterial_last = Bacterial(i); %儲存更好的适應度值
% 在該随機方向上繼續遊動步長機關,修改細菌位置
Bacterial(i).location = Bacterial(i).location + step*PHI;
% 重新計算新位置上的适應度值
Bacterial(i).fitness = CalFitness1(Bacterial(i).location,w,ua,u0);
else
% 否則,結束此次遊動
m = Ns;
Bacterial(i) = Bacterial_last; % 更新趨化操作後的适應度值
end
end
% pbest
if Bacterial(i).fitness < Bacterial(i).bestFitness
Bacterial(i).bestFitness = Bacterial(i).fitness;
Bacterial(i).bestLocation = Bacterial(i).location;
end
end % 如果i<BacterialNum,進入下一個細菌的趨化,i=i+1
%--------Mutation with pfPSO Opreator-------------
GlobalBest= Bacterial(1);
for i=2:BacterialNum
if Bacterial(i).fitness < GlobalBest.fitness;
GlobalBest = Bacterial(i);
end
end
for i=1:BacterialNum
r1=rand();
r2=rand();
Bacterial(i).location = ( 1 - GlobalBest.location / Bacterial(i).location ) * r1 * GlobalBest.location + (GlobalBest.location / Bacterial(i).location ) * r2 * Bacterial(i).bestLocation;
Bacterial(i).fitness = CalFitness1(Bacterial(i).location,w,ua,u0);
Bacterial(i).location = mod(Bacterial(i).location,255)+1;
end
end %-----(4)如果j<Nc,此時細菌還處于活躍狀态,進行下一次趨化,j=j+1-----
function fun = CalFitness1(x,w,ua,u0)
L=256;
x=int16(mod(x,255))+1;
w1=w(x(1));
u1=ua(x(1))/w1;
w2=w(x(2))-w(x(1));
u2=(ua(x(2))-ua(x(1)))/w2;
w3=w(L)-w(x(2));
u3=(ua(L)-ua(x(2)))/w3;