協同優化算法

協同優化算法的原理是將一複雜的目標函數分解成簡單的子目標函數，然後再將這些子目標函數進行協同優化。具體說來，協同優化是在優化每一子目標函數同時綜合考慮其它子目標函數的結果，使子目標函數之間的優化結果能夠一致。優化結果一致是指使每一變量的值在每一子目標函數的優化結果中能夠一致。一般來說，可以證明，如果變量的值一致則為最優解。協同優化算法沒有局部最優問題同時具有非常良好的收斂特性。 它很好地解決了許多實際中非線性優化及組合優化難題。

如果目標函數是一n個變量的函數$E(x_{1},x_{2},\ldots ,x_{n})$,簡寫成$E(x)$,協同優化算法先將它分解成n個簡單的子目標函數:

$E(x)=E_{1}(x)+E_{2}(x)+\ldots +E_{n}(x)$.

如果單獨優化每一子目標函數,則它們的結果很難達到一致。例如,變量$x_{i}$在包含它的子目標函數中的最優解值很難相同。對於$i=1,2,\ldots ,n$,如果我們取$E_{i}(x)$的最優解中$x_{i}$的值作為該變量的值，表示成${\tilde {x}}_{i}$,

${\tilde {x}}_{i}=\arg \min _{x_{i}}\min _{X_{i}\setminus x_{i}}E_{i}(x)$，這裏，$X_{i}$是$E_{i}(x)$的變量集，$X_{i}\setminus x_{i}$指變量集$X_{i}$除去元素$x_{i}$，

$({\tilde {x}}_{1},{\tilde {x}}_{2},\ldots ,{\tilde {x}}_{n})$則很難為原目標函數$E(x)$的最優解。

為了使子目標函數之間的優化結果能夠一致，協同優化算法在優化每一子目標函數$E_{i}(x)$同時考慮其它子目標函數的結果,

$\Psi _{j}(x_{j})=\min _{X_{j}\setminus x_{j}}E_{j}(x)$。

具體做法是利用其它子目標函數的優化結果通過數值加權修正每一個子目標函數如下,

$\left(1-\lambda \right)E_{i}(x)+\lambda _{k}\sum _{j}w_{ij}\Psi _{j}(x_{j})$，這裏，$\lambda _{k},w_{ij}$為加權係數，滿足$0\leq \lambda _{k},w_{ij}\leq 1$。

然後對修正後的子目標函數進行優化，優化結果再疊代放入修正的子目標函數中。協同優化算法的疊代方程如下,

$\Psi _{i}^{(k)}(x_{i})=\min _{X_{i}\setminus {x_{i}}}\left(\left(1-\lambda _{k}\right)E_{i}(x)+\lambda _{k}\sum _{j}w_{ij}\Psi _{j}^{(k-1)}(x_{j})\right),\quad for\;i=1,2,\ldots ,n.$

協同優化結果使每一變量的值在每一子目標函數的優化結果中達到一致。如果一致，則子目標函數的優化解既為最優解。

理論價值

現代優化理論中最重要的未解難題是發現通用的全局最優化條件。由於沒有全局最優化條件，我們不知道哪裏可以找到最優解，也不知道現有解是不是最優解. 因此,我們不知道如何更有效地組織優化過程及何時及時中斷搜索。任何全局最優化條件既有理論意義和實用價值。協同優化算法基於一種全新的優化原理解決了這一重要問題。

協同優化理論及量子力學的關係

從協同優化算法可以推導出薛定諤方程。

假設目標能量函數為

$E(x_{1},x_{2},\ldots ,x_{n})=\sum _{i=1}^{n}\left(e_{i}(x_{i})+\sum _{j:~j>i}^{n}e_{ij}(x_{i},x_{j})\right),\quad where\;e_{ij}(x_{i},x_{j})=e_{ji}(x_{j},x_{i}).$

協同優化算法在半環$(C,+,\times )$上的形式為

$\psi _{i}(x_{i},t+\Delta t)={\frac {1}{Z_{i}(t+\Delta t)}}\psi _{i}(x_{i},t)e^{-(\Delta t/\hbar )e_{i}(x_{i})}\prod _{j,j\not =i}\int dx_{j}\;e^{-(\Delta t/\hbar )e_{ij}(x_{i},x_{j})}\left|\psi _{j}(x_{j},t)\right|^{2},$

如果讓$\Delta t\rightarrow 0^{+}$及用高斯函數平滑$\psi _{i}\left(x_{i},t\right)$,則上式收斂後變成薛定諤方程如下:

$E_{i}\psi _{i}(x_{i},t)=\left(-{\frac {\hbar ^{2}}{2m_{i}}}\nabla _{i}^{2}+V_{i}(x_{i})\right)\psi _{i}(x_{i},t);$

這裏

$V_{i}(x_{i})=e_{i}+\sum _{j,j\not =i}\int dx_{j}~e_{ij}|\psi _{j}(x_{j},t)|^{2}.$

薛定諤方程是物理學中最基本的方程。因此，我們可以對自然界中一般分子及蛋白分子如何形成這一非線性優化問題從全局優化的角度有進一步更深的認識。

參考文獻

• X. Huang, 「Deriving the Normalized Min-Sum Algorithm from Cooperative Optimization」, accepted by IEEE Information Theory Workshop, Chengdu, China, 2006 (網上下載).

• X. Huang, ``The cooperative optimization metaheuristic: Inspiration from nature and applications, Computational Intelligence, ICIC 2005, Springer-Verlag, LNAI 4114, 2006, pp. 1246--1251.

• X. Huang, ``A general extension of constraint propagation for constraint optimization, Principles of Practice of Constraint Programming - CP 2004, Spinger-Verlag, LNCS 3258, 2004, pp. 737--741.

• X. Huang, ``Near perfect decoding of LDPC codes, Proceedings of IEEE International Symposium on Information Theory (ISIT), 2005, pp. 302--306 (網上下載).

• X. Huang, 「A New Kind of Hopfield Networks for Finding Global Optimum」, International Joint Conference on Neural Networks, Montreal, Canada, 2005, pp.764-769 (網上下載).

• X. Huang, ``Cooperative optimization for solving large scale combinatorial problems, Theory and Algorithms for Cooperative Systems, Series on Computers and Operations Research, World Scientific, 2004, pp. 117--156 (ISBN 981-256-020-3).

• X. Huang, ``Image segmentation by cooperative optimization, IEEE International Conference on Image Processing (ICIP), Singapore, 2004, pp. 945--948.

• X. Huang, ``Cooperative optimization for energy minimization in computer vision: A case study of stereo matching, Pattern Recognition, 26th DAGM Symposium, Springer-Verlag, LNCS 3175, 2004, pp. 302--309.

• X. Huang, ``A general framework for constructing cooperative global optimization algorithms, Frontiers in Global Optimization, Nonconvex Optimization and Its Applications, Kluwer Academic Publishers, 2004, pp. 179--221 (ISBN 1-4020-7699-1).

• X. Huang, 「A Polynomial Time Algorithm for Solving NP-hard Problems in Practice」, ACM SIGACT Volume 34, Issue 1, March 2003, pp. 101-108.

• X. Huang, 「A Cooperative Search Approach for Global Optimization」, Oral Presentation at the First International Conference on Optimization Methods and Software, Hangzhou, China, 2002.

• 黃曉非,丁溯泉,楊知行,吳佑壽,"GF(q)域上的低密度校驗(LDPC)碼的譯碼及其在深空通訊中的應用",飛行器測控學報",第25卷,第2期,2006年4月.