云計算環(huán)境下可驗證的粒子群優(yōu)化外包研究.pdf

1、目前，云計算的發(fā)展十分快速，對于計算資源有限的用戶來說，無法對結(jié)構(gòu)龐大的項目進行計算，尋求云計算的協(xié)助成為優(yōu)先的選擇。實際生活中，很多問題能夠歸結(jié)為非線性規(guī)劃（NLP）問題，NLP問題一般沒有確定的通用解法，對于很多復(fù)雜問題常使用啟發(fā)式算法求解。粒子群優(yōu)化算法（PSO）作為一種進化計算技術(shù)，在求解NLP問題上有著不錯的效果。比如，當一個計算能力有限的用戶有一個復(fù)雜且龐大的優(yōu)化問題需要使用PSO算法來求解，他可以將問題的求解工作委托給云，

2、運用云強大的計算能力快速求解。盡管云計算有很多好處，但是對用戶來說，云執(zhí)行計算的過程并不透明，因此帶來用戶如何驗證云如實地運行了算法進行求解的問題。
　　本文首先介紹了NLP和PSO算法的相關(guān)概念。KKT條件可以用來檢驗解的最優(yōu)性，但是傳統(tǒng)KKT條件在檢驗進化算法結(jié)果上有比較大的局限性。進化算法求得的解可能并不是最優(yōu)的，近似KKT條件的提出就提供了一種衡量KKT點鄰域內(nèi)的點最優(yōu)性的思路。然后概要介紹了可驗證計算的研究進展?？沈炞C計

3、算領(lǐng)域希望能設(shè)計一個通用的方案來驗證計算的結(jié)果，但是即便是對十分簡單的問題也需要極其龐大的存儲和計算資源來構(gòu)造執(zhí)行程序，很難應(yīng)用到實際的場景中。
　　其次，本文針對PSO算法外包問題提出可驗證的PSO算法以及對應(yīng)的驗證方案?？沈炞C的PSO算法保留了傳統(tǒng)粒子群優(yōu)化算法計算高效的優(yōu)點，還能對傳遞的算法參數(shù)進行驗證。用戶對需要發(fā)送的參數(shù)簽名，可驗證的PSO算法驗證簽名的有效性，驗證失敗則終止算法進程。云端返回結(jié)果后，由驗證算法驗證結(jié)果的

4、有效性，根據(jù)驗證結(jié)果可以判斷云是不是如實進行了運算。
　　最后，本文將外包問題限制為NLP問題，用戶需要確認云按要求執(zhí)行了PSO算法來求解并返回合適的結(jié)果。用戶需要對NLP問題進行預(yù)處理，使用罰函數(shù)法將問題轉(zhuǎn)化為可以被PSO算法解決的適應(yīng)度函數(shù)的形式后，由云服務(wù)器執(zhí)行計算。該方案移除了可驗證PSO算法中的簽名部分，并采用了近似KKT條件作為工具，通過驗證解是否是一個ε-KKT點，來檢驗PSO算法返回解的最優(yōu)性。
　　本文還通