群體演算法

1. 粒子群演算法（一）：粒子群演算法概述

  本系列文章主要針對粒子群演算法進行介紹和運用，並給出粒子群演算法的經典案例，從而進一步加深對粒子群演算法的了解與運用（預計在一周內完成本系列文章）。主要包括四個部分：

  粒子群演算法也稱粒子群優化演算法（Particle Swarm Optimization, PSO），屬於群體智能優化演算法，是近年來發展起來的一種新的進化演算法（Evolutionary Algorithm, EA）。 群體智能優化演算法主要模擬了昆蟲、獸群、鳥群和魚群的群集行為，這些群體按照一種合作的方式尋找食物，群體中的每個成員通過學習它自身的經驗和其他成員的經驗來不斷地改變搜索的方向。 群體智能優化演算法的突出特點就是利用了種群的群體智慧進行協同搜索，從而在解空間內找到最優解。
  PSO 演算法和模擬退火演算法相比，也是 從隨機解出發，通過迭代尋找最優解 。它是通過適應度來評價解的品質，但比遺傳演算法規則更為簡單，沒有遺傳演算法的「交叉」和「變異」，它通過追隨當前搜索到的最大適應度來尋找全局最優。這種演算法以其 容易實現、精度高、收斂快 等優點引起了學術界的重視，並在解決實際問題中展示了其優越性。

  在粒子群演算法中，每個優化問題的解被看作搜索空間的一隻鳥，即「粒子」。演算法開始時首先生成初始解，即在可行解空間中隨機初始化 粒子組成的種群 ，其中每個粒子所處的位置 ，都表示問題的一個解，並依據目標函數計算搜索新解。在每次迭代時，粒子將跟蹤兩個「極值」來更新自己， 一個是粒子本身搜索到的最好解 ，另一個是整個種群目前搜索到的最優解 。 此外每個粒子都有一個速度 ，當兩個最優解都找到後，每個粒子根據如下迭代式更新：

  其中參數 稱為是 PSO 的 慣性權重(inertia weight) ，它的取值介於[0,1]區間；參數 和 稱為是 學習因子(learn factor) ；而 和 為介於[0,1]之間的隨機概率值。
  實踐證明沒有絕對最優的參數，針對不同的問題選取合適的參數才能獲得更好的收斂速度和魯棒性，一般情況下 , 取 1.4961 ，而 採用 自適應的取值方法 ，即一開始令 ， 使得 PSO 全局優化能力較強 ；隨著迭代的深入，遞減至 ， 從而使得PSO具有較強的局部優化能力 。

  參數 之所以被稱之為慣性權重，是因為 實際 反映了粒子過去的運動狀態對當前行為的影響，就像是我們物理中提到的慣性。 如果 ，從前的運動狀態很少能影響當前的行為，粒子的速度會很快的改變；相反， 較大，雖然會有很大的搜索空間，但是粒子很難改變其運動方向，很難向較優位置收斂，由於演算法速度的因素，在實際運用中很少這樣設置。也就是說， 較高的 設置促進全局搜索，較低的 設置促進快速的局部搜索。

2. 群體智能演算法屬於新型計算模型嗎

群體智能演算法又稱為啟發式演算法，是現在廣泛應用於各個領域的先進演算法。
智能演算法是一種計算方法，計算模型是計算方法里可能用到的某種模型，不能說他們兩個誰是誰，但可以說某種群體智能演算法用到了某某計算模型

3. 常見的群體智能演算法不包括什麼演算法

遺傳演算法。
根據今日頭條查詢，遺傳演算法是進化演算法的一種，是不屬於群體智能演算法的。
遺傳演算法最早是由美國的Johnholland於20世紀70年代提出，該演算法是根據大自然中生物體進化規律而設計提出的。

4. 如何理解演算法多樣化和演算法優化之間的關系

1.演算法多樣化是「群體多樣化」
演算法多樣化不是要求每個學生都想出或都掌握兩種或多種演算法。「一個學生也許只想到了一種演算法，許多學生也許就有多種演算法，實施演算法多樣法時，教師不必將每一種演算法都挖掘出來，更不能憑教師自己的想像給學生列舉出千奇百怪、不合邏輯的演算法；教師不要生硬地套出學生的多種演算法；也不要求學生都要掌握多種演算法。」也就是說演算法多樣化是指「群體多樣化」，而不是「個體多樣化」。
2.演算法多樣化與演算法優化
有教師認為演算法優化就是跟著課本走，就是「演算法唯一化」。我們說的演算法優化有兩條標准，一是盡可能地選擇通法、通則，具有一般性，而不是適用於特殊數據的特殊演算法。二是盡可能選擇便於大多數同學接受、理解、掌握的演算法。第二條標准再具體些，又可細化為兩個方面：即算理上容易解釋，容易理解；演算法上簡捷，容易操作，容易掌握。有必要指出，這里的「優化」，不同於數學上的「最優化」，它是相對而言的，但又難以或者說不必精確刻畫的，其結果還常常不是唯一的。
演算法的優化可以是演算法多樣化的一個後繼步驟，演算法只有在優化後多樣化才有意義。新課標提倡演算法的多樣化，允許學生選擇自己喜愛的演算法，使得有些教師誤在課堂教學時，片面追求形式各異的演算法。雖說培養了學生的思維能力和創新精神，但明顯地思維難度太大，導致當堂課的教學內容不能完成。並且一些思維能力欠缺的學生腦筋轉不過來，直被說得雲里霧里，教學效果不夠理想。演算法的多樣化應是學生在探索演算法的過程中自然形成的，而不是生硬地套出多種演算法。在引導學生「群體演算法多樣化」後可以問一句：「你覺得哪種方法比較好？為什麼？」這樣，學生就在不知不覺中學會優化的方法了。

5. 群體數據的排序演算法有哪些

//群體數據的排序與查找

//1.直接插入排序的演算法實現：
void InsertSort(int arrForSort[],int nLength)
{
int i,j,temp;
for(i=1;i<nLength;i++) //遍歷整個序列
{
temp=arrForSort[i];
for(j=i;j>0&&temp<arrForSort[j-1];j--) //將第i個元素插入到合適的位置
arrForSort[j]=arrForSort[j-1];
arrForSort[j]=temp;
}
}

//2.直接選擇排序的演算法實現：
void SelectSort(int arrForSort[],int nLength)
{
int min,temp,
i,j;
for(i=0;i<nLength-1;i++)
{
min=i;
for(j=i+1;j<nLength;j++) //選出具有最小值的元素的下標標號
if(arrForSort[j]<arrForSort[min]) min=i;
temp=arrForSort[i]; //第i個元素與具有最小值的元素進行交換
arrForSort[i]=arrForSort[min];
arrForSort[min]=temp;
}
}

//3.起泡法排序的演算法實現：
void BubbleSort(int arrForSort[],int nLength)
{
int i,j,temp;
i=nLength-1;
while(i>0)
{
for(j=0;j<i;j++) //1次起泡的過程
{
if(arrForSort[j+1]<arrForSort[j]) //逆序交換
{temp=arrForSort[j+1];<br/> arrForSort[j+1]=arrForSort[j];<br/> arrForSort[j]=temp;}
}
i--; //准備下一次起泡序列的長度
}
}

//4.希爾排序的演算法實現：
void ShellSort(int arrForSort[],int nLength)
{
int k,j,i,temp;
k=nLength/2; //設置初始子序列的間隔
while(k>0)
{
for(j=k;j<nLength;j++) //子序列的插入排序
{
temp=arrForSort[j];i=j-k;
while((i>=0)&&(arrForSort[i]>temp))
{
arrForSort[i+k]=arrForSort[i];i=i-k;
}
arrForSort[i+k]=temp;
}
k=k/2; //重新設置子序列的間隔
}
return;
}

//5.順序查找的實現
int SequenceSearch(int arrForSearch[],int nLength,int nKey)
{
int i;
for(i=0;i<nLength;i++) //遍歷整個序列
if(arrForSearch[i]==nKey) return i;
return -1;
}

//6.折半查找的演算法實現
int MiddleSearch(int arrForSearch(int arrForSearch[],int nLength,int nKey)
{
int mid,top,bottom;
bottom=0; //設置首末元素下標
top=nLength-1;
while(bottom<=top)
{
mid=(bottom+top)/2; //取序列中間元素下標
if(arrForSearch[mid]==nKey) return mid; //如果找到該元素，返回其下標
else if(arrForSearch[mid]>nKey) top=mid-1; //在前半個序列中繼續查找
else bottom=mid+1;
}
return -1;
}

6. 優化演算法與群體智能之間有什麼關系

群體智能演算法與大多數基於梯度的優化演算法不同，群體智能演算法依靠的是概率搜索演算法。
與梯度演算法及傳統演化演算法相比優點：
沒有集中控制約束，不會因為個體的故障影響整個問題的求解。
以非直接信息交流的方式確保了系統的可擴展性。
並行分布式演算法模型，可充分利用多處理器。
對問題定義的連續性無特殊要求。演算法實現簡單。

7. 幾大群體智能演算法異同

1.都是一類不確定演算法。不確定性體現了自然界生物的生物機制,並且在求解某些特定問題方面優於確定性演算法。仿生優化演算法的不確定性是伴隨其隨機性而來的,其主要步驟含有隨機因素,從而在演算法的迭代過程中,事件發生與否有很大的不確定性。
2.都是一類概率型的全局優化演算法。非確定演算法的優點在於演算法能有更多機會求解全局最優解。
3.都不依賴於優化問題本身的嚴格數學性質。在優化過程中都不依賴於優化問題本身嚴格數學性質(如連續性,可導性)以及目標函數和約束條件精確的數學描述。
4.都是一種基於多個智能體的仿生優化演算法。仿生優化演算法中的各個智能體之間通過相互協作來更好的適應環境,表現出與環境交互的能力。

8. 群體智能演算法在什麼時候容易陷入局部最優

一般最優化演算法只能求局部最優值，很難求出全局最優值。
許多演算法當找到局部最優點後，就不能再繼續尋找了，這叫陷入局部極值。

9. 常見的群體智能演算法不包括什麼

遺傳演算法。
目前生物學里，群體智能演算法中最常見的是蟻群演算法、粒子群演算法、蜂群演算法，所以遺傳演算法不算常見的群體智能演算法。
群體智能演算法是通過模擬生物種群（或自然、人工群體）的行為，按照特定的相互作用機制來完成特定種群所給任務的優化演算法。

10. 常見的群體智能演算法不包括

有一些並不是廣泛應用的群體智能演算法，比如螢火蟲演算法、布穀鳥演算法、蝙蝠演算法以及磷蝦群演算法等等。

粒子群演算法（particle swarm optimization，PSO）是計算智能領域中的一種生物啟發式方法，屬於群體智能優化演算法的一種，常見的群體智能優化演算法主要有如下幾類：

設想這樣一個場景：一群鳥在隨機的搜索食物。在這個區域里只有一塊食物，所有的鳥都不知道食物在哪。但是它們知道自己當前的位置距離食物還有多遠。那麼找到食物的最優策略是什麼？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區域。

Step1:確定一個粒子的運動狀態是利用位置和速度兩個參數描述的，因此初始化的也是這兩個參數；

Step2:每次搜尋的結果（函數值）即為粒子適應度，然後記錄每個粒子的個體歷史最優位置和群體的歷史最優位置；

Step3:個體歷史最優位置和群體的歷史最優位置相當於產生了兩個力，結合粒子本身的慣性共同影響粒子的運動狀態，由此來更新粒子的位置和速度。

位置和速度的初始化即在位置和速度限制內隨機生成一個N x d 的矩陣，而對於速度則不用考慮約束，一般直接在0~1內隨機生成一個50x1的數據矩陣。

此處的位置約束也可以理解為位置限制，而速度限制是保證粒子步長不超限制的，一般設置速度限制為[-1,1]。

粒子群的另一個特點就是記錄每個個體的歷史最優和種群的歷史最優，因此而二者對應的最優位置和最優值也需要初始化。其中每個個體的歷史最優位置可以先初始化為當前位置,而種群的歷史最優位置則可初始化為原點。對於最優值，如果求最大值則初始化為負無窮，相反地初始化為正無窮。

每次搜尋都需要將當前的適應度和最優解同歷史的記錄值進行對比，如果超過歷史最優值，則更新個體和種群的歷史最優位置和最優解。

速度和位置更新是粒子群演算法的核心，其原理表達式和更新方式：

每次更新完速度和位置都需要考慮速度和位置的限制，需要將其限制在規定范圍內，此處僅舉出一個常規方法，即將超約束的數據約束到邊界（當位置或者速度超出初始化限制時，將其拉回靠近的邊界處）。當然，你不用擔心他會停住不動，因為每個粒子還有慣性和其他兩個參數的影響。

粒子群演算法求平方和函數最小值，由於沒有特意指定函數自變數量綱，不進行數據歸一化。