社會認知優化

社會認知優化（Social Cognitive Optimization, SCO），又稱社會認識優化算法、社會認知算法。它是一種基於社會認知理論的群體智能優化算法。

SCO算法已經被應用於非線性規劃問題，布爾可滿足性問題，軟件可靠性分配問題，自動機制設計等。

算法

SCO算法可用於求解全局最小化問題$f(x)$,其中$x$為屬於問題空間S的一個問題狀態（State），或稱為知識點，而$f$為質量衡量函數。

在SCO中，由$N_{c}$個主體（Agent）同時進行求解，而它們通過環境中的社會共享庫（Library）的進行交互。其中每個主體$i$ $(i=1,\ldots ,N_{c})$擁有一個私有知識點$x_{i}$，而社會共享庫中擁有一個知識集$X=\{x_{j}|j=1,\ldots ,N_{L}\}$ (即一組知識點，其數量為$N_{pop}$)。，SCO以馬爾科夫過程方式（即當前周期的運行只依賴於上一周期的狀態）重複運行$T$個周期。其算法流程如下：

• [1.初始化]：在問題空間S中（隨機）初始化每個主體i的私有知識點$x_{i}$和社會共享庫中的知識集$X$中的每個知識點。
• [2.運行周期]：在每個周期$t$ $(t=1,\ldots ,T)$中：
  • [2.1.主體認知]對每個主體$i$ $(i=1,\ldots ,N_{c})$：
    • [2.1.1.榜樣選擇]：在$X(t)$中選擇一個較高質量的知識點$x_{M}$。通常通過錦標選擇來實現，即隨機選擇$TAU_{B}$個知識點，並返回其中質量最高（即$f$值最小）的知識點作為$x_{M}$。
    • [2.1.2.質量衡量]：比較$x_{i}(t)$和$x_{M}$，將其中質量高的一個返回為基本知識點$x_{Base}$，而質量低的一個返回為參考知識點$x_{Ref}$。
    • [2.1.3.社會學習]：以$x_{Base}$和 $x_{Ref}$為輸入產生新知識點$x_{i}(t+1)$。通常$x_{i}(t+1)$應在以$x_{Base}$的周圍，而且離$x_{Base}$的距離和與$x_{Ref}$離$x_{Base}$的距離相關，且應嵌入邊界處理方式使得$x_{i}(t+1)$屬於S。
    • [2.1.4.知識反饋]：將部分已有知識反饋給社會共享庫。通常將$x_{i}(t+1)$直接提交。
    • [2.1.5.知識更新]：更新主體$i$本身的私有知識點。通常將 $x_{i}(t+1)$直接替換 $x_{i}(t)$，當然也可通過其它方式更新，比如蒙特卡洛方式。
  • [2.2.社會共享庫維護]：社會共享庫利用所有主體提交的知識點更新已有的知識集，即將$X(t)$更新為$X(t+1)$。一種簡單的方式是一對一錦標選擇方式，即對每一個主體提交的知識點，替換$X(t)$中隨機選擇$TAU_{W}$個知識點後質量最差（即$f$值最大）的一個。
• [3.結束]：返回歷史上得到的質量最高的知識點作為準優解。

【注】在以上這些步驟中，只有2.1.3步尤其和問題空間S的形式相關。例如S為$D$維連續空間時（每維值有給定的上下界），新知識點$x_{i}(t+1)$可以以如下方式產生。首先得到$x_{Ref}$以$x_{Base}$為中心的對稱點$x_{Image}$，然後得到以$x_{Image}$和 $x_{Ref}$為頂點的超矩形體$S_{V}$（而$x_{Base}$可視為在該超矩形體的中心），接着得到S和$S_{V}$的交集空間（邊界處理方式），並在該交集空間中返回一個純隨機知識點作為$x_{i}(t+1)$。如S為離散和組合空間（如對旅行商問題），則該步需要進行相應的設計。

SCO算法共有三個主要參數，即主體數目$N_{c}$，知識集大小$N_{pop}$，以及執行周期數$T$。通常$N_{pop}$為$N_{c}$的3～5倍。加上初始化過程，總知識點評估次數為$N_{pop}+N_{c}*(T+1)$，因此總知識點評估次數在T較大時基本與$N_{pop}$無關。SCO算法還有兩個次要參數，通常固定為默認值，即$TAU_{B}=2$與$TAU_{W}=4$。

最優化問題可以視為一個類似於Newell和Simon所定義的（可以度量的）問題空間，而問題求解則可看做在問題空間中進行搜索高質量的問題狀態或知識點。對每個主體而言，其私有知識點可以看做一種私有記憶，而該知識點隨執行周期的變化軌跡則可以視為是對認知過程的一種模擬，即由低質量知識點得到高質量知識點的過程。在每個周期中，每個主體使用他的私有記憶以及參考社會共享庫中的部分信息或線索，通過搜索得到的新知識將會被主體用來更新它的私有記憶，並提交（部分）已有知識給環境用來最後更新社會共享庫。因此SCO模擬一種簡單的社會認知過程：每個主體的認知過程利用了社會共享庫，而高質量的社會共享庫的積累過程則來源於個體認知過程的貢獻。主體間的交互和合作搜索實際上是隱式的通過對社會共享庫的使用和影響其更新而實現。如果將在問題空間中迅速得到准優解的過程視為一種創造性思維過程，SCO也可以視為對腦力激盪優化法的一種簡單模擬，這也意味着SCO有在研究群體創造性方面的擴展的可能性。

比較

以下比較一下SCO和幾種主要的基於群體的優化算法的異同點。這些算法包括遺傳算法（Genetic Algorithm, GA)，蟻群算法（Ant Colony Optimization, ACO），粒子群優化（Particle Swarm Optimization，PSO）。

和GA所不同的是，每個主體長期存在於所有周期中，而不會被新個體替換。也就是，SCO模擬多個個體的學習和認知周期，而GA模擬群體的演化周期。

和ACO所不同的是，每個主體擁有私有記憶，這個記憶長期存在於所有周期中。在這點上，SCO和PSO類似。主體的私有記憶保證了個體學習能力，有助於群體中湧現新知識並維護群體知識的差異性。

和PSO所不同的是，社會共享庫中的知識和主體中的知識相互獨立。首先，拿走某個主體，不會影響社會共享庫。在這點上，SCO和ACO類似。減少個體數目不會嚴重影響算法性能，SCO甚至能在只有一個個體時得到比較穩定的搜索結果，儘管使用多個個體會使得搜索過程更魯棒。其次，改變庫裡面的部分信息，不會直接影響到主體本身，因此也可以通過調整社會共享庫來調節算法性能。

外部連結

• NLPSolver中的社會認知優化算法 （頁面存檔備份，存於網際網路檔案館）
• SCO源代碼鏈接 （頁面存檔備份，存於網際網路檔案館）