謝安世

?

基于對標學(xué)習(xí)的智能優(yōu)化算法

謝安世

（浙江工業(yè)大學(xué)，浙江 杭州 310014）

科研、工程和管理中的很多問題都可以轉(zhuǎn)化為優(yōu)化問題。應(yīng)用于這些優(yōu)化問題的各種方法本身就是各種模型，設(shè)計不同的方法即設(shè)計不同的模型。將標桿管理理念建模成為一種用于單目標優(yōu)化問題的元啟發(fā)式搜索方法。基于奧卡姆剃刀原則，摒棄了復(fù)雜的操作算子的概率調(diào)優(yōu)規(guī)則，用一個簡單的框架來組織核心算子，從而達到許多組合算法的搜索效果。

智能優(yōu)化算法；探索性與開發(fā)性；全局搜索與局部優(yōu)化；標桿管理

1 引言

元啟發(fā)式優(yōu)化/搜索算法的研究，從橫向看，可以分為算法自身設(shè)計研究（即設(shè)計不同的優(yōu)化搜索算法）、算法自身的理論研究（包括復(fù)雜度、收斂性等）和算法在各學(xué)科領(lǐng)域的具體應(yīng)用研究共3個方面。單從算法自身的設(shè)計看，大體可以分為兩個層次：一是對已有的算法進行改進，主要體現(xiàn)在改良現(xiàn)有的（或設(shè)計出新的）操作算子及其概率規(guī)則；二是提出全新的算法。

目前很多新提出的算法，基本上都由幾個廣泛使用的核心算子組成，它們的“新”，只是用一種別的“新”物種來命名常見的元啟發(fā)式搜索[1]。事實上有很多高被引算法都是一些經(jīng)典算法的翻版，只是名稱不同[2]。因為自然界現(xiàn)象的多樣性，最近十幾年來有越來越多各種各樣的所謂新算法不斷地被提出，都喜歡使用各種隱喻，看起來好像挺熱鬧，但如果就科學(xué)的求真求實來講，真的有必要嗎[3]？同時由于各類隱喻的特殊性，在用于算法設(shè)計時，只有某種特定的編碼方案才能很好地實現(xiàn)這種隱喻。換一種編碼方案，就不容易實現(xiàn)這種隱喻了，即算法的“智能性”也就大打折扣了。比如粒子群算法，由于其特定的候選解更新方案，用浮點數(shù)編碼，效果很好，用二進制編碼、字符串編碼或者布爾型編碼，效果就不好。因此，這類算法的搜索效果很大程度上依賴于其核心操作算子的概率規(guī)則，在運行過程中需要參數(shù)調(diào)優(yōu)才能平衡其搜索過程的探索性（exploration）與開發(fā)性（exploitation），并借此保持搜索過程中的種群多樣性。

本文也使用了隱喻手法，借用企業(yè)管理領(lǐng)域中的標桿管理理念，將“見賢思齊”這一思想建模為一種通用的優(yōu)化/搜索框架。不限于某種特定的編碼方案，并且不需要特定的概率規(guī)則，只需將核心操作算子按本文給出的組織策略進行組織安排，算法就可以平衡其搜索過程的探索性與開發(fā)性，并保持搜索過程中的種群多樣性。因此說本文提出的算法的“智能性”，沒有體現(xiàn)在操作算子的概率規(guī)則上，而是體現(xiàn)在操作算子的組織策略上。

2 對標學(xué)習(xí)算法的基本框架

對標管理，顧名思義，就是以知己知彼的方式，檢驗自己并了解對手，從而知道自己與競爭對手的差距，以便學(xué)習(xí)和改進?；趯斯芾硭枷氲膬?yōu)化算法，其總體思路如下。

在整個生態(tài)系統(tǒng)（即解空間）內(nèi)，通過某種規(guī)則產(chǎn)生若干小生境種群（即初始解集），相當于全球市場上各類企業(yè)主體，種群內(nèi)的個體相當于企業(yè)部門或員工。首先根據(jù)優(yōu)化目的，以評價函數(shù)為衡量標準，進行立標管理，分別確定各小生境種群內(nèi)的最佳個體（即局部最佳個體、局部最優(yōu)解）和整個生態(tài)系統(tǒng)內(nèi)的最佳個體（即全局最佳個體、全局最優(yōu)解），相當于樹立企業(yè)內(nèi)部標桿和企業(yè)外部標桿，并記錄在案。種群內(nèi)的個體，按照對標學(xué)習(xí)的指導(dǎo)原則進行對標學(xué)習(xí)。這一輪立標管理與對標學(xué)習(xí)完成之后，再次進行評估，重新樹立標桿，并更新記錄。然后開始新一輪的對標學(xué)習(xí)，如此往復(fù)，直至滿足迭代停止條件。此時的全局最佳個體，解碼之后便是全局最優(yōu)解，各局部最佳個體，解碼之后便是局部最優(yōu)解。由此可知，這是一種同時包含學(xué)習(xí)性競爭與競爭性學(xué)習(xí)的尋優(yōu)思想。

2.1 對標學(xué)習(xí)算法的簡單版本

簡單對標學(xué)習(xí)算法，主要是指全局標桿由全程最優(yōu)個體擔任；局部標桿由當代最優(yōu)個體擔任；試探性學(xué)習(xí)策略分別嵌套在全局對標學(xué)習(xí)和局部對標學(xué)習(xí)兩個操作算子之內(nèi)；全局對標學(xué)習(xí)、局部對標學(xué)習(xí)和自我學(xué)習(xí)3個基本操作算子的概率都取隨機數(shù)。基本步驟如下。

步驟1 初始化種群和個體的數(shù)目，迭代停止條件等。

步驟2 根據(jù)對標管理的指導(dǎo)原則，評估所有個體的適應(yīng)度值，記錄并更新標桿。

步驟3 根據(jù)對標學(xué)習(xí)的具體方法，個體有選擇地執(zhí)行對標學(xué)習(xí)。

步驟4 若迭代停止條件不滿足，轉(zhuǎn)向步驟2，否則輸出標桿并解碼。

2.2 對標學(xué)習(xí)的指導(dǎo)原則

基于對標管理思想的優(yōu)化理論，其總體思想是對標學(xué)習(xí)，但其核心思想與根本精髓，則是對標學(xué)習(xí)的指導(dǎo)規(guī)則和對標學(xué)習(xí)的具體方法。對標管理的規(guī)則是中觀的，是針對具體問題設(shè)計具體算法，其內(nèi)容如下。

（1）立標記錄實時更新。在算法運行過程中，每一輪產(chǎn)生的標桿，包括局部標桿與全局標桿，均記錄在案，并不斷更新。

（2）對標學(xué)習(xí)按需選擇。個體在進行對標學(xué)習(xí)時，3個操作算法無需按順序執(zhí)行。某個體如果執(zhí)行全局對標學(xué)習(xí)之后沒有獲得改善，則繼續(xù)進行局部對標學(xué)習(xí)，否則直接退出本輪對標學(xué)習(xí)。

（3）學(xué)習(xí)對象靈活切換。隨著算法運行，理論上每次迭代之后的局部（和全局）標桿將不斷變化。但為了避免極端狀況，可以設(shè)定規(guī)則強制要求各個小生境種群相互交換局部標桿，從而保證生態(tài)系統(tǒng)內(nèi)的全局極值點能被搜索到。

（4）高效利用馬太效應(yīng)。個體在執(zhí)行對標學(xué)習(xí)時的欲望和強度，也即操作算子的概率，可以根據(jù)個體自身與標桿對象的差異度和相似度來決定?；跇藯U管理的優(yōu)化思想規(guī)定，這個差異度越小，或相似度越大，則其學(xué)習(xí)欲望就越大，隨之其學(xué)習(xí)強度也越大，這是個體層面的馬太效應(yīng)。

（5）合理利用集群效應(yīng)。在對標學(xué)習(xí)過程中，如果某個種群發(fā)現(xiàn)了更好的全局解，則其他種群將指派部分個體進入該種群，以協(xié)助進行密集搜索。但如果某種群在對標學(xué)習(xí)過程中一直都沒有發(fā)現(xiàn)更好的全局解，則種群內(nèi)所有個體將逐漸被調(diào)配往其他種群，這是種群層面的集群效應(yīng)。

2.3 對標學(xué)習(xí)的具體方法

對標學(xué)習(xí)的總體原則就是見賢思齊。具體來講，就是個體減少其自身與標桿對象之間的差異度，并（或）增加其自身與標桿對象之間的相似度。具體怎樣實現(xiàn)這種對標式學(xué)習(xí)，取決于算法本身采用的編碼方案。下面給出幾種常見的編碼方案及其相應(yīng)的對標學(xué)習(xí)方法。

2.3.1 0/1編碼方案下的對標學(xué)習(xí)方法

常見的0/1編碼方案，有二進制碼（binary）、格雷碼（Gray-code）以及獨熱碼（one-hot）。這3種編碼方案，針對不同的問題，各有優(yōu)勢，也各有缺點。對于這三者的聯(lián)系和區(qū)別，這里無需詳述，只是對于智能優(yōu)化算法來說，采用二進制碼時，個體（即候選解）的編碼與解碼過程，相對比較簡單，消耗的計算時間較少，但對于個體之間的轉(zhuǎn)碼操作，即對于候選解的搜索操作，相對復(fù)雜，消耗的存儲空間較多。采用格雷碼或獨熱碼時，編碼與解碼操作相對復(fù)雜，消耗的計算時間較多，但是轉(zhuǎn)碼操作相對簡單，消耗的存儲空間較少。此種情形，與數(shù)字控制系統(tǒng)中的情形，剛好不同，二進制編碼與格雷碼編碼，使用觸發(fā)器較少，對組合邏輯消耗較多，而獨熱碼編碼則相反。

當算法采用0/1編碼方案時，使用海明距離度量個體之間的差異度。個體對標學(xué)習(xí)的具體方法，就是減少自身與標桿對象之間的海明距離。搜索方向和搜索步長的調(diào)整，主要體現(xiàn)在對自身坐標基因的調(diào)整上。個體對標學(xué)習(xí)欲望的強弱，主要體現(xiàn)在學(xué)習(xí)率的大小上。個體對標學(xué)習(xí)行為的強度，主要體現(xiàn)在編碼基因位調(diào)整的個數(shù)上。

2.3.2 浮點數(shù)編碼方案下的對標學(xué)習(xí)方法

當采用浮點數(shù)編碼方案時，一般可以使用距離概念來表征個體之間的差異度，用相關(guān)系數(shù)來表征個體之間的相似度。對于表征差異度的距離概念，可以采用閔可夫斯基距離（Minkowski distance），根據(jù)問題特征和數(shù)據(jù)結(jié)構(gòu)，選取合適的參數(shù)值，容易簡化成曼哈頓距離（Manhattan distance）、歐幾里得距離（Euclidean distance）、切比雪夫距離（Chebyshev distance）等。對于表征相似度的相關(guān)系數(shù)，也可以根據(jù)問題需要和數(shù)據(jù)特征，選取合適的計算方法，如皮爾遜相關(guān)系數(shù)（Pearson correlation coefficient）、夾角余弦相似度（cosine similarity）、Tonimoto系數(shù)、Spearman相關(guān)系數(shù)、Kendall相關(guān)系數(shù)等。

當算法采用浮點數(shù)編碼方案時，個體對標學(xué)習(xí)的具體方法，就是減少自身與標桿對象之間的閔可夫斯基距離，并（或）增大自身與標桿對象之間的相關(guān)系數(shù)。

另外，針對浮點數(shù)編碼，必須特別注意以下兩個問題。一是關(guān)于合理選用度量差異度與相似度的方法問題。個體之間的差異度與相似度，從字面意義來看，只是兩個相對應(yīng)的概念，似乎從算術(shù)上可以相互轉(zhuǎn)換。但是站在計算機科學(xué)與數(shù)據(jù)科學(xué)的角度來看，這是兩個完全不同的概念，有著不同的確切定義，其內(nèi)涵和外延是完全不同的，不能相互轉(zhuǎn)換。這里用距離概念衡量的差異度，與用相關(guān)系數(shù)衡量的相似度，在不同的分析模型與數(shù)據(jù)結(jié)構(gòu)之下，兩者的差別非常大。差異度，更多的是體現(xiàn)編碼數(shù)值上的大小差別，而相似度，更多的是體現(xiàn)編碼方向上的區(qū)別。在計算和搜索過程中，可能會出現(xiàn)這樣一種現(xiàn)象，即個體之間的差異度發(fā)生改變了，而相似度卻沒有變化，或者相反，個體之間的相似度發(fā)生改變了，而差異度卻沒有變化。因此，在針對具體的優(yōu)化問題設(shè)計具體的優(yōu)化算法時，需要根據(jù)其分析模型與數(shù)據(jù)結(jié)構(gòu)，選用合適的度量方法。二是算法設(shè)計與測試中浮點數(shù)的轉(zhuǎn)碼、計算與精度問題。符合IEEE754標準，支持SSE2指令集的絕大多數(shù)CPU/GPU，是當前進行算法設(shè)計與測試的硬件基礎(chǔ)。但是按照IEEE754標準規(guī)定的浮點存儲格式，有一些帶小數(shù)位的十進制數(shù)據(jù)，無法使用當前計算機所使用的0/1二進制代碼準確表示出來。因此在轉(zhuǎn)碼與計算時，如果沒有合理的處理方法，會出現(xiàn)精度失準的問題。浮點數(shù)及其轉(zhuǎn)碼與計算的精度，很大程度上取決于指數(shù)范圍的大小。以現(xiàn)行的32位單精度浮點數(shù)為例，最低不能低過2-7-1，最高不能高過28-1（其中剔除了指數(shù)部分全0和全1的特殊情況）。如果超出表達范圍，那就得舍棄末尾的小數(shù)，造成向上或向下溢出，甚至有時候舍棄都無法表示。這樣在需要表達一個極小的數(shù)值時，如果不用規(guī)格化數(shù)值表示，CPU就只能把它當0來處理。如果多次做低精度浮點數(shù)舍棄，則必然精度失準嚴重，甚至?xí)霈F(xiàn)除數(shù)為0的情形，從而導(dǎo)致計算異常。如果做非規(guī)格化浮點處理，雖然可以補救精度失準的問題，但對于CPU硬件或編譯器要求甚高，轉(zhuǎn)碼和計算的效率將呈指數(shù)下降。因此智能優(yōu)化算法在設(shè)計和測試時，不僅要考慮問題域特征，還要考慮計算過程中的硬件CPU/GPU、軟件編譯器問題。最后返回計算結(jié)果時，還有算法自身的解碼環(huán)節(jié)，即二進制機器碼與浮點數(shù)之間的轉(zhuǎn)碼，這涉及算法代碼優(yōu)化問題，不再贅述。

2.3.3 字符（串）編碼或布爾值編碼下的對標學(xué)習(xí)方法

現(xiàn)代管理工作中，尤其數(shù)據(jù)管理工作中的許多問題，比如電子商務(wù)領(lǐng)域常見的商品評價與推薦問題，涉及人機交互，許多模型必須使用符號函數(shù)，往往需要字符或字符串編碼，或者布爾值編碼。

當采用字符（串）編碼或布爾值編碼方案時，一般可以使用Levenshtein distance（編輯距離）、Jaro-Winkler distance（哈羅-溫克勒距離）、Jaccard coefficient（杰卡德系數(shù)）等概念來表征個體之間的差異度或相似度。個體對標學(xué)習(xí)的具體方法，就是通過基因編輯，減少自身與標桿對象之間的距離，并（或）增大自身與標桿對象之間的相似度。

3 對標學(xué)習(xí)算法的若干技術(shù)

3.1 智能性

基于概率搜索的智能優(yōu)化算法，其智能性主要體現(xiàn)在概率規(guī)則的制定上。這個概率規(guī)則，主要是指算法在運行過程中，其設(shè)計的操作算子被執(zhí)行時的概率規(guī)則。因此，幾乎所有的智能優(yōu)化算法，除了需要為操作算子的概率設(shè)置初始值之外，還需要為其設(shè)計一套相應(yīng)的變化規(guī)則。比如遺傳算法及其各種改進版本，需要為選擇、交叉和變異這3個操作算子的概率設(shè)置相應(yīng)的初始值和變化規(guī)則；粒子群算法及其各種改進版本，需要為其慣性權(quán)重和加速系數(shù)設(shè)置合適的初始值和變化規(guī)則；蟻群算法及其各種改進版本，需要為其信息素和啟發(fā)式因子設(shè)置合適的初始值和變化規(guī)則。這些概率的初始值及其變化規(guī)則，設(shè)置恰當與否，決定了算法能否搜索到問題的最優(yōu)解，甚至直接決定了算法能否正常發(fā)揮其應(yīng)有的搜索性能。但是，概率參數(shù)如何配置，才能使得算法的優(yōu)化性能達到最優(yōu)，這本身就是一個組合優(yōu)化問題。目前該問題在理論上尚沒有得到很好的解決，因此，幾乎所有智能優(yōu)化算法，在概率參數(shù)的配置上，主要依靠統(tǒng)計經(jīng)驗。這也是目前所有智能優(yōu)化算法存在著的一個軟肋。

本文提出的對標學(xué)習(xí)算法，完全不存在這個問題。由前文內(nèi)容可知，對標學(xué)習(xí)算法，完全不需要為其操作算子的概率設(shè)置初始值和變化規(guī)則。無論全局學(xué)習(xí)率、局部學(xué)習(xí)率，還是自我學(xué)習(xí)率，在對標學(xué)習(xí)算法的簡單版本中，都是完全隨機的。在設(shè)計其他版本時，可以為每個操作算子的概率設(shè)置相應(yīng)的初始值及變化規(guī)則。但這樣一來，不僅增加了算法的復(fù)雜性，而且實驗表明，這種做法并沒有讓算法性能有質(zhì)的提升。實際上，標桿學(xué)習(xí)算法的搜索性能，不依賴于操作算子的概率規(guī)則，而是依賴于對標管理思想，依賴于對標學(xué)習(xí)的指導(dǎo)原則和具體方法。算法中的基本操作算子，只是對標學(xué)習(xí)思想及其指導(dǎo)原則在特定的編碼方案和特定的數(shù)據(jù)結(jié)構(gòu)之下的一種具體實現(xiàn)而已。事實上，只要遵循對標管理的若干思想和若干原則，設(shè)計出特定的編碼方案及相應(yīng)的數(shù)據(jù)結(jié)構(gòu)之下的學(xué)習(xí)方法，自然就會獲得優(yōu)良的搜索和優(yōu)化性能。這種無需概率規(guī)則的制度設(shè)計，完全避免了概率規(guī)則對于算法性能的影響。對標學(xué)習(xí)算法的“智能性”，完全沒有體現(xiàn)在操作算子的概率規(guī)則上，而體現(xiàn)在了操作算子的組織策略上。

3.2 探索性與開發(fā)性的自動平衡

探索性體現(xiàn)了算法進行全局搜索，開拓新空間的能力，而開發(fā)性體現(xiàn)了算法進行局部優(yōu)化，小幅改善求精的能力。一般來說，一個算法的探索性越強，則其開發(fā)性就越弱，反之亦然。因此傳統(tǒng)上，算法的探索性與開發(fā)性是一對矛盾體，相互沖突和對立，無法相容。如果探索性太強而開發(fā)性太弱，則搜索結(jié)果容易發(fā)散，容易錯過全局最優(yōu)解，最終不利于對全局極值的搜索；如果探索性太弱而開發(fā)性太強，則搜索結(jié)果容易集聚，容易陷入局部最優(yōu)解，最終也不利于對全局極值的搜索。判斷一個智能優(yōu)化算法的性能如何，其中最為重要的一點，就是看其采用什么策略來平衡其全局搜索與局部優(yōu)化。算法的探索性與開發(fā)性權(quán)衡的策略，在很大程度上決定了一個算法的優(yōu)劣。為了平衡算法的探索性與開發(fā)性，目前現(xiàn)存的智能優(yōu)化算法采用的策略，幾乎都是給不同的操作算子附加相應(yīng)的概率參數(shù)。在這個概率參數(shù)的取值上，具體做法大體有兩種，一是根據(jù)統(tǒng)計經(jīng)驗提前設(shè)定某個（些）固定值，二是根據(jù)某些原則在搜索過程中自適應(yīng)地動態(tài)調(diào)整。比如遺傳算法及其各類改良版本，往往都是通過選擇率、交叉率和變異率3個參數(shù)來平衡其探索性與開發(fā)性；粒子群優(yōu)化算法及其各類改良版本，往往都是通過一個慣性權(quán)重和兩個加速系數(shù)來平衡其探索性與開發(fā)性；蟻群優(yōu)化算法及其各類改良版本，往往都是通過信息素濃度這個參數(shù)來平衡其探索性與開發(fā)性。在這個概率參數(shù)的取值上，每個算法雖然各有自己的技巧，但都不盡如人意。因為這個概率參數(shù)，作為控制變量，其取值問題本身也是一個待解的優(yōu)化問題，尚未得到圓滿解決。事實上，無論使用什么技巧來設(shè)定這個概率參數(shù)，其取值及相應(yīng)的平衡效果可能都不是最優(yōu)的。因此，總體而言，現(xiàn)存的智能優(yōu)化算法，對于全局搜索與局部優(yōu)化，即探索性與開發(fā)性，如何平衡的難題，沒有得到很好的解決。

人們認為算法的探索性與開發(fā)性，其本身是相互對立和無法相容的，但是在算法的設(shè)計中，是可以實現(xiàn)協(xié)同并存和自動均衡的。因此在算法的設(shè)計與開發(fā)過程中，探索性與開發(fā)性相互對立、無法相容的“潛規(guī)則”是完全可以避免的。本文提出的算法框架，拋棄了傳統(tǒng)的利用概率參數(shù)來平衡算法探索性與開發(fā)性的策略。事實上，只要是根據(jù)對標學(xué)習(xí)的指導(dǎo)原則，即不依賴控制參數(shù)，而是依靠科學(xué)合理的制度，設(shè)計出來的優(yōu)化算法，其全局搜索與局部優(yōu)化，即算法的探索性與開發(fā)性將會協(xié)同并存，并且會自動平衡。在本文提出的通用框架之內(nèi)，個體進行全局對標學(xué)習(xí)，就相當于對未知極值點的概率分布進行探索，這樣進行全局搜索，就起到了開拓新空間的作用，體現(xiàn)了算法的探索性。個體進行局部對標學(xué)習(xí)，就相當于根據(jù)當前的觀測值，利用已知的動作獲取更多回饋以使下一次“收益最大化”，這樣進行局部優(yōu)化，就起到了小幅改善求精的作用，體現(xiàn)了算法的開發(fā)性。對標學(xué)習(xí)的指導(dǎo)原則中第二條，即學(xué)習(xí)行為按需選擇的設(shè)計原則，使全局對標學(xué)習(xí)行為與局部對標學(xué)習(xí)行為，在同一輪的迭代搜索中，都得到執(zhí)行。這樣同輪異步的制度設(shè)計，巧妙地解決了全局搜索與局部優(yōu)化無法并行共存的難題，從根本上保證了算法探索性與開發(fā)性的自動平衡。這個特點，在后面的仿真實驗中也得到了證實。

3.3 對于探索性與開發(fā)性自動平衡的實驗證明

現(xiàn)以MATLAB內(nèi)置的Peaks函數(shù)為例，測試本文提出的對標學(xué)習(xí)算法如何實現(xiàn)探索性與開發(fā)性的自動平衡。本次測試使用對標學(xué)習(xí)算法簡單版本，初始階段生態(tài)系統(tǒng)內(nèi)共有5個小生境種群，每個種群包含3個個體，即總共包含15個個體。算法采用二進制編碼方案，個體的編碼長度為30，算法的最大迭代次數(shù)設(shè)定為100。

這里分兩種情形，一是初始種群在搜索空間內(nèi)隨機分布時；二是初始種群被置于搜索空間內(nèi)同一點（3，3）時。下面分別列出以上兩種情況下，生態(tài)系統(tǒng)內(nèi)每一個個體的搜索過程。因為同時在動畫中展示15個個體的搜索過程會顯得非?；靵y，因此每一個個體的搜索過程均使用一張動態(tài)圖片單獨展示，這樣就有30張動態(tài)圖片，顯示了個體是如何在探索性與開發(fā)性之間實現(xiàn)動態(tài)平衡的。從15個個體分別在兩種初始分布條件下的搜索過程的動態(tài)展示中，可以看到如下3個明顯的現(xiàn)象。

一是個體進行了多次“爬山”過程。在搜索過程中，可以很明顯地看到，當它居于半山腰時，受到局部標桿的吸引，它產(chǎn)生了多次“爬山”過程，并最終爬到了山頂，實現(xiàn)了對全局最大值的搜索。這個“爬山”過程，相當于根據(jù)當前的觀測值，利用已知的動作獲取更多回饋，以使下一次“收益最大化”，起到了小幅改善求精的作用，體現(xiàn)了對標學(xué)習(xí)算法的開發(fā)性。

二是個體的搜索軌跡幾乎遍及整個解空間。算法的最大迭代次數(shù)設(shè)定為100，即個體只演化搜索100個世代，可以看到，在這100次迭代過程中，個體的搜索路徑幾乎覆蓋了整個解空間。理論上，只要迭代次數(shù)足夠多，個體可以遍歷整個搜索空間。這種大范圍的遍歷性全局搜索能力，體現(xiàn)了個體開拓新空間的能力，體現(xiàn)了對標學(xué)習(xí)算法的探索性。

三是所有個體均多次搜索到了全局極大值。比如第一號個體在100次迭代過程中，在初始種群隨機分布和同一分布兩種條件下，分別有15次和17次搜索到了Peaks函數(shù)的全局最大值。這是由對標學(xué)習(xí)算法的搜索策略決定的，對標學(xué)習(xí)式的搜索策略使得算法具有很高的搜索效率。

需要說明的是，本次實驗所使用的數(shù)據(jù)，是由算法隨便運行一次產(chǎn)生的，并無特意挑揀。

4 對標學(xué)習(xí)算法對于動態(tài)優(yōu)化問題的應(yīng)用

4.1 動態(tài)函數(shù)優(yōu)化問題設(shè)計原因

為什么要設(shè)計動態(tài)函數(shù)優(yōu)化問題？有3個原因，第一是現(xiàn)實世界中的科學(xué)、工程和管理問題，大多都可以轉(zhuǎn)化為最優(yōu)化問題。第二是這些最優(yōu)化問題大多都可以轉(zhuǎn)化為對相關(guān)數(shù)學(xué)模型的求解問題。比如，現(xiàn)代信息生物學(xué)中預(yù)測蛋白質(zhì)穩(wěn)定結(jié)構(gòu)的問題，可以轉(zhuǎn)化為求解蛋白質(zhì)結(jié)構(gòu)的最低勢能值問題，而后者，又可以轉(zhuǎn)化為對HP格點模型、AB非格點模型等蛋白質(zhì)結(jié)構(gòu)簡化模型的求解問題；現(xiàn)代分子生物學(xué)中腫瘤微陣列基因表達數(shù)據(jù)的分類問題，可以轉(zhuǎn)化為求解最優(yōu)的腫瘤特征基因提取和分類模型的問題，而后者，可以轉(zhuǎn)化為對表征樣本間距離和相似性的目標函數(shù)的求解問題；當代大數(shù)據(jù)科學(xué)中復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)測定問題，可以轉(zhuǎn)化為求解最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)的問題，而后者，又可以轉(zhuǎn)化為對網(wǎng)絡(luò)平衡結(jié)構(gòu)模型的求解問題；現(xiàn)代智能工業(yè)移動機器人的實時調(diào)度問題，可以轉(zhuǎn)化為機器人的移動路徑最優(yōu)化問題，而后者又可以轉(zhuǎn)化為對移動機器人運動學(xué)模型的求解問題。第三是這些靜態(tài)數(shù)學(xué)模型是其現(xiàn)實世界當中動態(tài)模型的特例，是其真實模型的理想狀態(tài)。如果一個算法能夠很好地求解某個問題的動態(tài)模型，則對其理想狀態(tài)下的靜態(tài)模型的求解，自然不成問題。

關(guān)于動態(tài)函數(shù)的構(gòu)造，已經(jīng)有學(xué)者提出了許多種方法。本文使用兩種簡單的通過靜態(tài)函數(shù)優(yōu)化問題構(gòu)造動態(tài)函數(shù)優(yōu)化問題的方法。一是改變函數(shù)的約束條件，使得搜索空間發(fā)生變形，比如靜態(tài)函數(shù)中變量的個數(shù)及其取值范圍，根據(jù)特定的規(guī)則發(fā)生變化，從而構(gòu)造動態(tài)函數(shù)優(yōu)化問題；二是改變個體基因的編碼序列，使得個體基因發(fā)生變形。比如當采用0/1編碼方案時，所有個體的基因表達式，周期性地與某個特定的模板進行異或運算，從而構(gòu)造動態(tài)函數(shù)優(yōu)化問題。

動態(tài)問題與靜態(tài)問題最大的不同，在于其因環(huán)境變量不斷變化，其最優(yōu)解不再固定不變，而是隨著環(huán)境的變化而動態(tài)變化。因此對動態(tài)問題進行求解，不僅是要求出問題的最優(yōu)解，更重要的是要跟蹤問題最優(yōu)解的運動軌跡。動態(tài)函數(shù)優(yōu)化問題主要用來測試算法對所求解問題的全局極值的動態(tài)跟蹤能力。

4.2 基于空間變形的動態(tài)函數(shù)優(yōu)化

基于空間變形的動態(tài)函數(shù)優(yōu)化問題，是這樣定義的：Schwefel函數(shù)的定義域在±500之間變化時有3個變量；在±1 000之間變化時有2個變量，這樣其全局最小值會隨之發(fā)生漂移。動態(tài)函數(shù)如下：

定義域變化大小程度表征環(huán)境震蕩強度，可以用來測試算法對于函數(shù)在不同解空間內(nèi)全局最小值的動態(tài)追蹤能力。在本次測試實驗中，使用IEEE CEC2017實參數(shù)單目標優(yōu)化競賽中排名前四的4個算法，分別是jSO[4]、LSHADE-cnEpSin[5]、LSHADE-SPACMA[6]、DES[7]，與本文提出的對簡單標學(xué)習(xí)算法（SBA）進行對比。為保證公平公正，在實驗中，用以測試的5個算法的最大迭代次數(shù)統(tǒng)一都設(shè)為1 000，每隔100代函數(shù)的定義域發(fā)生一次震蕩，即環(huán)境總共經(jīng)歷10個周期，也即10次震蕩。5個算法都包括100個個體（或粒子），初始化時所有個體都被安置在同一點（3，3）。5個算法都采用浮點數(shù)編碼方案，且都運行100次，取平均值。計算結(jié)果如圖1所示。

從實驗結(jié)果可以觀察到幾個明顯的現(xiàn)象：一是對標學(xué)習(xí)算法的動態(tài)追蹤能力遠強于其他4個算法，且其頑健性超強?？梢钥吹剑瑹o論函數(shù)定義域如何變化，對標學(xué)習(xí)算法都能進行有效追蹤，并且都能搜索到新空間內(nèi)的全局最優(yōu)解。二是對標學(xué)習(xí)算法的快速收斂能力很強。面對新環(huán)境，對標學(xué)習(xí)算法總是能很快收斂到全局最優(yōu)解上。這是學(xué)習(xí)性競爭與競爭性學(xué)習(xí)思想有機融合的魅力。另外，這也與初始化時設(shè)置的種群及個體數(shù)量有關(guān)，數(shù)量越大，則全局收斂速度越快。三是在環(huán)境發(fā)生不同強度的震蕩時，其他4個算法的搜索性能也同步發(fā)生了不同程度的震蕩。這4個算法的動態(tài)優(yōu)化性能，看似總體差別不大，但實際上彼此之間差異很大。從圖1中可以看到，每個算法搜索到的最優(yōu)解的路徑與軌跡整體上比較平滑，那是因為它們是每個算法運行100次結(jié)果的平均值?？梢杂^察到，其他4個算法的搜索性能是極不穩(wěn)定的。

4.3 基于基因變形的動態(tài)函數(shù)優(yōu)化

圖1 基于空間變形的動態(tài)函數(shù)優(yōu)化運行100次的平均值

在本次測試實驗中，5個算法的參數(shù)設(shè)置與第4.2節(jié)實驗完全相同。為保證公平公正，在本次實驗中，用以測試的5個算法的最大迭代次數(shù)統(tǒng)一都設(shè)為1 000，每隔100代函數(shù)的定義域發(fā)生一次震蕩，即環(huán)境總共經(jīng)歷10個周期，也即10次震蕩。5個算法都包括100個個體（或粒子），初始化時所有個體都被安置在同一點(3,3)。5個算法都采用二進制編碼方案，且都運行100次，取平均值。當環(huán)境變化強度（CR）分別為0.1、0.5、0.9時，5個算法對全局最小值的動態(tài)追蹤軌跡如圖2所示。

可以看出：一是對標學(xué)習(xí)算法的快速收斂能力較強，且其頑健性很強，遠遠優(yōu)于其他4個算法。二是環(huán)境變化對算法具有顯著的影響?？梢钥吹江h(huán)境震蕩強度，從0.1增大到0.5時，5個算法的搜索結(jié)果都出現(xiàn)了強烈的震蕩，從0.5增大到0.9時，其他4個算法的搜索結(jié)果的震蕩程度都增大了，但對標學(xué)習(xí)算法反而減小了，這和它具有較強的保持種群多樣性的能力有關(guān)。因為對標學(xué)習(xí)算法在運行過程能一直保持較好的種群多樣性，在環(huán)境發(fā)生變化前夕，即所有個體基因在與模板做異或運算之前，有的個體本來離全局最優(yōu)解的距離較遠，同時因為環(huán)境震蕩強度為0.9，即模板上有90%的基因值為1，于是那些本來較差的個體在與模板做異或運算時，其基因反而得到了改善。于是圖2（c）中所示的算法在每一代的全局最優(yōu)解，在搜索空間發(fā)生變形時，震蕩反而不及0.5時劇烈。三是與基于空間變形的動態(tài)函數(shù)優(yōu)化時類似，在環(huán)境發(fā)生不同強度的震蕩時，其他4個算法的搜索性能也同步發(fā)生了不同程度的震蕩，時好時差。

5 結(jié)束語

本文的核心貢獻在于算法的“智能性”是體現(xiàn)在操作算子的組織策略而非概率規(guī)則上，這樣就打破了需要依靠概率規(guī)則來平衡探索性與開發(fā)性的“潛規(guī)則”。從本質(zhì)上講，本框架不只是一個具體的算法，更是一種普適性方法論，它介于工程技術(shù)與認知哲學(xué)之間。因此它可以應(yīng)用于科學(xué)、工程和管理中許多具體問題當中。

一般來說，元啟發(fā)式搜索的設(shè)計是一類實驗性科學(xué)，其大部分工作是基于模擬實驗和實際應(yīng)用的。這類算法的復(fù)雜隨機性使得嚴謹?shù)睦碚撗芯浚绕涫怯嬎銖?fù)雜性研究難以實現(xiàn)。盡管已經(jīng)提出了許多理論和方法來研究這類算法的計算復(fù)雜性和收斂性，但在理論界存在一些爭議[8,9]。根據(jù)奧卡姆剃刀原則，本文拋棄了復(fù)雜的操作算子的概率調(diào)優(yōu)規(guī)則，用一個簡單的框架來組織核心算子，達到了許多組合算法的搜索效果。本文的目的是將企業(yè)管理中的標桿管理思想建模為單目標實參數(shù)優(yōu)化問題的搜索方法。

[1] S?RENSEN K. Metaheuristic-the metaphor exposed[J]. International Transactions in Operational Research, 2015, 22(1): 3-18.

[2] PIOTROWSKI A P, NAPIORKOWSKIJ J, ROWINSKIP M. How novel is the “novel” black hole optimization approach?[J]. Information Sciences, 2014(267): 191-200.

[3] FONG S, WANG X, XU Q, et al. Recent advances in metaheuristic algorithms: does the Makara dragon exist?[J]. The Journal of Supercomputing, 2016, 72(10): 3764-3786.

[4] BREST J, MAU?EC M S, BO?KOVI? B. Single objective real-parameter optimization: algorithm jSO[C]//2017 IEEE Congress onEvolutionary Computation (CEC), June 5-8, 2017, San Sebastian, Spain. Piscataway: IEEE Press, 2017: 1311-1318.

[5] AWAD N H , ALI M Z, SUGANTHAN P N. Ensemble sinusoidal differential covariance matrix adaptation with Euclidean neighborhood for solving CEC2017 benchmark problems[C]//2017 IEEE Congress on Evolutionary Computation (CEC), June 5-8, 2017, San Sebastian, Spain. Piscataway: IEEE Press, 2017: 372-379.

[6] MOHAMED A W, HADI A A, FATTOUH A M, et al. LSHADE with semi-parameter adaptation hybrid with CMA-ES for solving CEC 2017 benchmark problems[C]//2017 IEEE Congress on Evolutionary Computation (CEC), June 5-8, 2017, San Sebastian, Spain. Piscataway: IEEE Press, 2017:145-152.

[7] JAGODZI?SKI D, ARABAS J. A differential evolution strategy[C]//2017 IEEE Congress on Evolutionary Computation (CEC), June 5-8, 2017, San Sebastian, Spain. Piscataway: IEEE Press, 2017: 1872-1876.

[8] MICHALEWICZ Z. Quo vadis, evolutionary computation? On a growing gap between theory andpractice[J]. Lecture Notes in Computer Science, 2012: 98-121.

[9] MICHALEWICZ Z. The emperor is naked: evolutionary algorithms for real-world applications[J]. Association for Computing Machinery Inc, 2012(3): 1-13.

Intelligent optimization algorithm based on benchmarking

XIE Anshi

Zhejiang University of Technology, Hangzhou 310014, China

Many of the issues in scientific research, engineeringand management can be transformed into optimization problems. The various methods applied to these problems were a variety of models. Designing different methods was designing different models. The theme was to model the benchmarking philosophy in business management as a meta-heuristic search method for single objective bound-constrained real-parameter optimization problems. According to the principle of Occam’s Razor, many complicated operators and their probability tuning rules were abandoned and a simple framework was used to organize the core operators to achieve the effect of many composition algorithms.

intelligent optimization algorithm, exploration and exploitation, global search and local optimization, benchmarking management

N940，TP202

A

10.11959/j.issn.1000?0801.2018144

2017?08?01；

2018?04?05

浙江省哲學(xué)社會科學(xué)重點研究基地技術(shù)創(chuàng)新與企業(yè)國際化研究中心項目；浙江工業(yè)大學(xué)中小微企業(yè)轉(zhuǎn)型升級協(xié)同創(chuàng)新中心項目；教育部人文社會科學(xué)基金資助項目（No.17YJC630011）

Research Fund from “Zhejiang Provincial Key Research Base of Philosophy and Social Sciences-Research Centre for Technology Innovation and Enterprise Internationalization”, Research Fund from “Collaborative Innovation Center for Transformation and Upgrading of Micro, Small and Medium Enterprises, Zhejiang University of Technology”, The Ministry of Education of Humanities and Social Science Project (No.17YJC630011)

謝安世（1983–），男，博士，浙江工業(yè)大學(xué)助理研究員，主要研究方向為管理與決策的認識論與方法論。