1、模擬退火Simulated Annealing算法

        模擬冷卻算法是一種隨機搜索方法，它的主要特點是不用窮遍集合中每一種可能性就可以找到最優(yōu)或幾乎最優(yōu)的狀態(tài)。它是通過模擬一個分子系統的自然冷卻系統來做到這一點的。在每一種狀態(tài)，它隨機地選擇了一種相鄰的狀態(tài)，如這種相鄰的狀態(tài)有一個更低的成本，系統將會轉移到該狀態(tài)。如果這種相鄰的狀態(tài)有一個更高的成本，系統將可能會轉移到該狀態(tài)，也可能不會轉移到該狀態(tài)。轉移的概率依賴于現在的狀態(tài)的溫度參數（該值越高，轉移的概率越大）和兩個狀態(tài)之間的成本的差異（差異越大，轉移的概率越大）。溫度將會漸漸低下來，最終會達到均衡。模擬冷卻算法常常用來嘗試發(fā)現離散數學中一些問題的幾乎最優(yōu)的解。

        2、非連通的集合算法來結合覆蓋設計

        如果對某個v=v1+v2和所有的t1+t2=t,都有大小為N1的覆蓋設計（v1,k1,t1）和大小為N2的覆蓋設計(v2,k2,t2)存在，那么將有大小為N=N1*N2的覆蓋設計存在。然而，可以用這種方法產生的旋轉矩陣數量很少，而且構造的過程也很復雜。很少的旋轉矩陣是用這種方法產生的。

        3、貪婪算法

        這種算法產生了許多許多的旋轉矩陣。這種算法的核心思想是：每個區(qū)組都盡可能少重復前面區(qū)組的數字，一直重復下去，直到你得到一個覆蓋設計。你可以用順序、逆序或灰色、隨機的順序來重復這個過程?；蛘呖梢杂媚闼矚g的設計。事實上，筆者起初的時候正是用這個方法來產生一些比較簡單的矩陣，但是這種算法看起來容易，實際上卻十分繁瑣，如果不用計算機，即使是很簡單的矩陣，也要耗費無數的精力。而且，這種算法只能保證可以產生旋轉矩陣，卻無法保證產生的旋轉矩陣一定是最優(yōu)的。當參數很大時，用它產生的矩陣離最優(yōu)的矩陣還差的很遠。

        但是，可以用這種方法產生旋轉矩陣，然后利用其他的優(yōu)化算法對它再進一步優(yōu)化，這樣可以產生比較優(yōu)良的旋轉矩陣。

        4、誘致算法

        Greg Kuperberg是這種算法的主要創(chuàng)立者和提倡者。

        先利用一個巨大的參數為(V,K,t) 的旋轉矩陣 ，從V個點中按照某種順序或完全隨機的選出v個點，然后將他們用原來的長度為 K的區(qū)組隔斷，得到了每個區(qū)組個數不定的一個覆蓋。最后，將這個覆蓋進行如下的修補即可：對每一個長度為l的區(qū)組，將該區(qū)組替換成一個（l,k,t）的覆蓋設計。這是一種比較復雜的算法，然而，確是迄今最好的算法之一。

        運用他可以產生優(yōu)化程度比較高的矩陣。然而，運用這種算法的一個很大的限制是，必須要有一個參數很大的旋轉矩陣和許許多多的參數比它小的矩陣。

擴展閱讀

版權聲明：