?一、和聲搜索算法介紹

和聲搜索（Harmony Search, HS）算法是一種新穎的智能優(yōu)化算法。類似于遺傳算法對生物進(jìn)化的模仿、模擬退火算法對物理退火的模擬以及粒子群優(yōu)化算法對鳥群的模仿等，和聲算法模擬了音樂演奏的原理。

上圖是一個由7個人組成的樂隊，每個人演奏一種樂器，它們的演奏加起來對應(yīng)一組和聲X={x1, x2, x3, x4, x5, x6, x7}，他們會進(jìn)行不斷的進(jìn)行配合以及排練來得到最好的和聲效果，整個過程使用一個f(x)函數(shù)來衡量和聲的效果好壞，這個f(x)就相當(dāng)于總指揮，對他們演奏出的每一組和聲進(jìn)行權(quán)衡，如果達(dá)不到要求就繼續(xù)演奏，直到得到一組滿意的和聲為止，這就是和聲算法的最優(yōu)化過程。

上面就是和聲算法的基本思想，下面來具體看看算法的實現(xiàn)過程。

1.1、理解幾個變量

1、和聲庫大小（ Harmony memory Size，HMS）：因為每個樂器演奏的音樂具有一定的范圍，我們可以通過每個樂器的音樂演奏范圍來構(gòu)造一個解空間，然后通過這個解空間來隨機(jī)產(chǎn)生一個和聲記憶庫，所以我們需要先為這個和聲記憶庫指定一個大小。

2、記憶庫取值概率（Harmony memory considering rate, HMCR）：每次我們需要通過一定的概率來從這個和聲記憶庫中取一組和聲，并且對這組和聲進(jìn)行微調(diào)，得到一個組新的和聲，然后對這組新和聲進(jìn)行判別是否優(yōu)于和聲記憶庫中最差的和聲，這個判別使用的就是上面說的f(x)函數(shù)進(jìn)行比較，所以，我們需要隨機(jī)產(chǎn)生一個記憶庫取值概率。

3、微調(diào)概率(Pitch adjusting rate, PAR)：上面已經(jīng)說過，我們以一定的概率來在和聲記憶庫中選取一組和聲，進(jìn)行微調(diào)，這里指定的就是這個微調(diào)概率。

4、音調(diào)微調(diào)帶寬?bw：上面說了會把從記憶庫中取出的一組和聲以一定的概率進(jìn)行微調(diào)，這里指定就是這個調(diào)整幅度。

5、創(chuàng)作的次數(shù)?Tmax：這里指定的就是演奏家需要創(chuàng)作的次數(shù)，也就是上面整個調(diào)整過程需要重復(fù)多少次。

1.2、算法步驟

1、初始化上面的五個變量

2、確定解空間
上面有7個樂器，每個樂器的樂器演奏都在一定的范圍內(nèi)，通過確定每個樂器的音樂演奏范圍，確定一個解空間。

上面的N對應(yīng)的就是7，表示有7種樂器，U表示音樂的上限，L表示音樂的下限，這樣就為每個樂器的樂器確定了一個范圍，整個組合對應(yīng)的就是一個解空間。

3、初始化和聲記憶庫

我們首先會根據(jù)初始化的和聲庫大小HMCR和上面和聲的解空間來隨機(jī)的產(chǎn)生一個大小為HMCR的和聲記憶庫。

矩陣表示如下：

4、產(chǎn)生一個新和聲

（1）在[0，1]之間隨機(jī)的產(chǎn)生一個變量rand1，并且將rand1與上面初始化的HMCR進(jìn)行比較。

• 
  

• 如果rand1小于HMCR，那么在上面初始化的和聲記憶庫中隨機(jī)的得到一組和聲

• 
  

• 否則就在上面的解空間中隨機(jī)的得到一組和聲。

最終，就得到一組和聲，如果這組和聲是從和聲庫中得到的，就需要對這組和聲進(jìn)行微調(diào)，在[0，1]之間隨機(jī)的產(chǎn)生一個變量rand2

• 
  

• 如果rand2小于上面初始化的PAR，就需要以上面初始化的微調(diào)帶寬bw來對和聲進(jìn)行調(diào)整，得到一組新和聲

• 
  

• 否則，不做調(diào)整

可以看到上面進(jìn)行了兩次的變異過程，最終得到了一組和聲。

5、更新和聲庫

將得到的新和聲使用f(x)進(jìn)行進(jìn)行計算，如果這個新和聲比上面初始化的和聲庫HM中最差的的解具有更好的目標(biāo)函數(shù)解，那么將這新的和聲替換掉和聲庫中那個最差的和聲。

6、判斷是否終止

根據(jù)上面初始化的創(chuàng)作的次數(shù)來看當(dāng)前創(chuàng)作次數(shù)是否已經(jīng)達(dá)到這個最大次數(shù)，如果沒有，則重復(fù)4-5的過程，直到達(dá)到最大創(chuàng)作次數(shù)。

三、柵格地圖介紹

柵格地圖有兩種表示方法，直角坐標(biāo)系法和序號法，序號法比直角坐標(biāo)法節(jié)省內(nèi)存

室內(nèi)環(huán)境柵格法建模步驟

1.柵格粒大小的選取

柵格的大小是個關(guān)鍵因素，柵格選的小，環(huán)境分辨率較大，環(huán)境信息存儲量大，決策速度慢。

柵格選的大，環(huán)境分辨率較小，環(huán)境信息存儲量小，決策速度快，但在密集障礙物環(huán)境中發(fā)現(xiàn)路徑的能力較弱。

2.障礙物柵格確定

當(dāng)機(jī)器人新進(jìn)入一個環(huán)境時，它是不知道室內(nèi)障礙物信息的，這就需要機(jī)器人能夠遍歷整個環(huán)境，檢測障礙物的位置，并根據(jù)障礙物位置找到對應(yīng)柵格地圖中的序號值，并對相應(yīng)的柵格值進(jìn)行修改。自由柵格為不包含障礙物的柵格賦值為0，障礙物柵格為包含障礙物的柵格賦值為1.

3.未知環(huán)境的柵格地圖的建立

通常把終點設(shè)置為一個不能到達(dá)的點，比如（-1，-1），同時機(jī)器人在尋路過程中遵循“下右上左”的原則，即機(jī)器人先向下行走，當(dāng)機(jī)器人前方遇到障礙物時，機(jī)器人轉(zhuǎn)向右走，遵循這樣的規(guī)則，機(jī)器人最終可以搜索出所有的可行路徑，并且機(jī)器人最終將返回起始點。

備注：在柵格地圖上，有這么一條原則，障礙物的大小永遠(yuǎn)等于n個柵格的大小，不會出現(xiàn)半個柵格這樣的情況。

四、代碼

clc; close all clear load('data1.mat') S=(S_coo(2)-0.5)*num_shange+(S_coo(1)+0.5);%起點對應(yīng)的編號 E=(E_coo(2)-0.5)*num_shange+(E_coo(1)+0.5);%終點對應(yīng)的編號 PopSize=20;%種群大小 OldBestFitness=0;%舊的最優(yōu)適應(yīng)度值 gen=0;%迭代次數(shù) maxgen =100;%最大迭代次數(shù) %% 灰狼算法 c1=0.6;%頭狼保留概率 c2=0.3;%次狼保留概率 c3=0.1;%差狼保留概率 Alpha_score=inf; %change this to -inf for maximization problems Beta_score=inf; %change this to -inf for maximization problems Delta_score=inf; %change this to -inf for maximization problems %% 和聲算法 HMCR=0.95;%記憶庫取值概 PAR=0.4;%微調(diào)概率 bw=0.1;%帶寬 %% %% 初始化路徑 Group=ones(num_point,PopSize); ?%種群初始化 %最優(yōu)解 figure(3) hold on for i=1:num_shange ? ?for j=1:num_shange ? ? ? ?if sign(i,j)==1 ? ? ? ? ? ?y=[i-1,i-1,i,i]; ? ? ? ? ? ?x=[j-1,j,j,j-1]; ? ? ? ? ? ?h=fill(x,y,'k'); ? ? ? ? ? ?set(h,'facealpha',0.5) ? ? ? ?end ? ? ? ?s=(num2str((i-1)*num_shange+j)); ? ? ? ?text(j-0.95,i-0.5,s,'fontsize',6) ? ?end end axis([0 num_shange 0 num_shange])%限制圖的邊界 plot(S_coo(2),S_coo(1), 'p','markersize', 10,'markerfacecolor','b','MarkerEdgeColor', 'm')%畫起點 plot(E_coo(2),E_coo(1),'o','markersize', 10,'markerfacecolor','g','MarkerEdgeColor', 'c')%畫終點 set(gca,'YDir','reverse');%圖像翻轉(zhuǎn) for i=1:num_shange ? ?plot([0 num_shange],[i-1 i-1],'k-'); ? ?plot([i i],[0 num_shange],'k-');%畫網(wǎng)格線 end for i=2:index1 ? ?Q1=[mod(route_lin(i-1)-1,num_shange)+1-0.5,ceil(route_lin(i-1)/num_shange)-0.5]; ? ?Q2=[mod(route_lin(i)-1,num_shange)+1-0.5,ceil(route_lin(i)/num_shange)-0.5]; ? ?plot([Q1(1),Q2(1)],[Q1(2),Q2(2)],'r','LineWidth',3) end title('和聲算法改進(jìn)的灰狼算法-最優(yōu)路線'); %進(jìn)化曲線 figure(4); plot(BestFitness); xlabel('迭代次數(shù)') ylabel('適應(yīng)度值') grid on; title('進(jìn)化曲線'); disp('和聲算法改進(jìn)的灰狼算法-最優(yōu)路線方案：') disp(num2str(route_lin)) disp(['起點到終點的距離:',num2str(BestFitness(end))]);

?