組合優化演算法

1. 組合優化問題的一般求解方法有哪些

組合（最）優化問題是最優化問題的一類。最優化問題似乎自然地分成兩類：一類是連續變數的問題，另一類是離散變數的問題。具有離散變數的問題，我們稱它為組合的。在連續變數的問題里，一般地是求一組實數，或者一個函數；在組合問題里，是從一個無限集或者可數無限集里尋找一個對象——典型地是一個整數，一個集合，一個排列，或者一個圖。一般地，這兩類問題有相當不同的特色，並且求解它們的方法也是很不同的。

2. 優化演算法是什麼呢

優化演算法是指對演算法的有關性能進行優化，如時間復雜度、空間復雜度、正確性、健壯性。

大數據時代到來，演算法要處理數據的數量級也越來越大以及處理問題的場景千變萬化。為了增強演算法的處理問題的能力，對演算法進行優化是必不可少的。演算法優化一般是對演算法結構和收斂性進行優化。

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

遺傳演算法

遺傳演算法也是受自然科學的啟發。這類演算法的運行過程是先隨機生成一組解，稱之為種群。在優化過程中的每一步，演算法會計算整個種群的成本函數，從而得到一個有關題解的排序，在對題解排序之後，一個新的種群----稱之為下一代就被創建出來了。首先，我們將當前種群中位於最頂端的題解加入其所在的新種群中，稱之為精英選拔法。新種群中的餘下部分是由修改最優解後形成的全新解組成。

常用的有兩種修改題解的方法。其中一種稱為變異，其做法是對一個既有解進行微小的、簡單的、隨機的改變；修改題解的另一種方法稱為交叉或配對，這種方法是選取最優解種的兩個解，然後將它們按某種方式進行組合。爾後，這一過程會一直重復進行，直到達到指定的迭代次數，或者連續經過數代後題解都沒有改善時停止。

3. 請問組合優化和非線性整數規劃的區別是什麼

先問一下提問者，在什麼情形下想要了解這方面的內容？提出這樣的問題，可以看出你對這方面的了解幾乎是零……
組合優化和非線性整數規劃根本不是能在一個范疇上比較的東西啊。組合優化是運籌學的後繼課程，同時也是運籌學的一個重要獨立分支，是一類重要的優化問題，它又稱離散優化，是通過數學方法去尋找離散事件的最優編排、分組、次序或篩選等。而非線性整數規劃則是將事件抽象成數學表達式後的一類問題，可以看作組合優化問題的一類分支，或更准確的說，解決組合優化問題的演算法的一個分支。
另外，組合優化是各種離散問題的總和，它包含了各式各樣的問題，最常見的有裝箱問題、平行機問題、背包問題、圖論問題（最短路徑、一筆畫問題、最小生成樹問題、著色問題等）、旅行商問題、在線問題等等很多，每種問題都有自己的精確解和近似解的各種演算法，其中任意一個問題的研究都可以寫成一本書了，而所謂的組合優化的比較新的解決方法……這個東西是不存在的……非線性整數規劃也是的，其實一些比較傳統的演算法不見得不好，建議你去找一本講數學規劃和組合優化的書去系統了解一下。
至於國內外研究現狀，也不是一兩句話能說的清的，還是一句話，去搜近時間的論文吧。

4. 什麼叫組合優化

組合優化（Combinatorial Optimization）問題的目標是從組合問題的可行解集中求出最優解，通常可描述為：令Ω＝{s1，s2，…，sn}為所有狀態構成的解空間，C(si)為狀態si對應的目標函數值，要求尋找最優解s*，使得對於所有的si∈Ω，有C(s*)＝minC(si)。組合優化往往涉及排序、分類、篩選等問題，它是的一個重要分支。
典型的組合優化問題有旅行商問題（Traveling Salesman Problem－TSP）、加工調度問題（Scheling Problem，如Flow-Shop，Job-Shop）、0-1背包問題（Knapsack Problem）、裝箱問題（Bin Packing Problem）、圖著色問題（Graph Coloring Problem）、聚類問題（Clustering Problem）等。這些問題描述非常簡單，並且有很強的工程代表性，但最優化求解很困難，其主要原因是求解這些問題的演算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現有計算機上實現，即所謂的「組合爆炸」。正是這些問題的代表性和復雜性激起了人們對組合優化理論與演算法的研究興趣。

5. 組合優化的問題分類

典型的組合優化問題有：
旅行商問題（Traveling Salesman Problem－TSP）；
加工調度問題（Scheling Problem，如Flow-Shop，Job-Shop）；
0-1背包問題（Knapsack Problem）；
裝箱問題（Bin Packing Problem）；
圖著色問題（Graph Coloring Problem）；
聚類問題（Clustering Problem）等。
這些問題描述非常簡單，並且有很強的工程代表性，但最優化求解很困難，其主要原因是求解這些問題的演算法需要極長的運行時間與極大的存儲空間，以致根本不可能在現有計算機上實現，即所謂的「組合爆炸」。正是這些問題的代表性和復雜性激起了人們對組合優化理論與演算法的研究興趣。

6. 組合優化問題是不是只能用智能優化演算法來解決有沒有其它演算法來解決這個問題

最優化演算法，例如分枝定界、分枝定價、列生成、動態規劃等演算法也可以求解組合優化問題。

7. 連續優化問題和組合優化問題在演算法設計方面的差異

這個問題本身不完整埃 組合數量最少這個優化目標有問題。按照題目理解，直接找出最少公共特性的最大集合就可以了。 聚類分析、神經網路等演算法都可以做這種分類問題。

8. 使用matlab遺傳演算法工具箱能不能解決組合優化問題還有使用工具箱方便還是自己編程方便呢

1、要看你組合優化是屬於哪種問題，一般的組合優化都是混合整數線性或非線性的，那麼就不行了，因此要對遺傳演算法改進才能計算。
2、如果有現成的工具箱求解你的組合優化問題肯定要方便些，但碰到具體問題，可能要對參數進行一些設置更改，所以最好能有編程基礎，那樣就可以自己修改工具箱裡面的參數或策略了

對你的補充問題，組合優化問題一般都是用matlab 和 lingo實現吧。建議買一本數學建模的書看一看，都涉及到組合優化問題，也可以下載論文看看。lingo對編程要簡單些，主要是求混合規劃，缺點是似乎還不能用上多目標問題，一般的組合優化都屬於多目標問題。但是matlab功能強大的多。

9. 經典組合優化問題的一般求解方法有哪些

組合最優化方法(combinatorial optimizationmethod )求解組合最優化問題的方法一般地，對於不同類的組合最優化問題，對應著不同的求解方法.判定一個組合最優化方法好壞的主要標準是運算次數.用n表示某一組合最優化問題的規模p(n)表示在對方法影響最壞的情況下所需的運算次數.若p(n)是n的多項式函數，則稱該方法是多項式演算法.凡能用多項式演算法求解的問題都稱為P問題.有一類問題稱為NP完全問題，若這類組合最優化問題具有如下特點:
1.它們都未找到多項式演算法.
2.如果對其中某一問題存在多項式演算法，那麼此類中的所有問題也都有多項式演算法.
已發現有成千的組合最優化問題屬於NP完成問題.為求解該類中的問題，人們往往採用「啟發式」方法.這些方法一般地，不能保證求得問題的最優解，但常能得到較好的近似解