國賽需了解的模型和演算法

12 人贊了文章

1.按模型的數學方法分：

幾何模型、圖論模型、微分方程模型、概率模型、最優控制模型、規劃論模型、馬氏鏈模型等。

2.按模型的特徵分：

靜態模型和動態模型，確定性模型和隨機模型，離散模型和連續性模型，線性模型和非線性模型等。

3.按模型的應用領域分：

人口模型、交通模型、經濟模型、生態模型、資源模型、環境模型等。

4.按建模的目的分：

預測模型、優化模型、決策模型、控制模型等。

一般研究數學建模論文的時候，是按照建模的目的去分類的，並且是演算法往往也和建模的目的對應

5.按對模型結構的了解程度分：

有白箱模型、灰箱模型、黑箱模型等。

比賽盡量避免使用，黑箱模型、灰箱模型，以及一些主觀性模型。

6.按比賽命題方向分：

國賽一般是離散模型和連續模型各一個

數學建模十大演算法

1、蒙特卡羅演算法

該演算法又稱隨機性模擬演算法，是通過計算機模擬來解決問題的演算法，同時可以通過模擬可以來檢驗自己模型的正確性，比較好用的演算法

2、數據擬合、參數估計、插值等數據處理演算法

比賽中通常會遇到大量的數據需要處理，而處理數據的關鍵就在於這些演算法，通常使用Matlab作為工具

3、線性規劃、整數規劃、多元規劃、二次規劃等規劃類問題

建模競賽大多數問題屬於最優化問題，很多時候這些問題可以用數學規劃演算法來描述，通常使用Lindo、Lingo軟體實現

4、圖論演算法

這類演算法可以分為很多種，包括最短路、網路流、二分圖等演算法，涉及到圖論的問題可以用這些方法解決，需要認真準備

5、動態規劃、回溯搜索、分治演算法、分支定界等計算機演算法

這些演算法是演算法設計中比較常用的方法，很多場合可以用到競賽中

6、最優化理論的三大非經典演算法：模擬退火法、神經網路、遺傳演算法

這些問題是用來解決一些較困難的最優化問題的演算法，對於有些問題非常有幫助，但是演算法的實現比較困難，需慎重使用

7、網格演算法和窮舉法

當重點討論模型本身而輕視演算法的時候，可以使用這種暴力方案，最好使用一些高級語言作為編程工具

8、一些連續離散化方法

很多問題都是從實際來的，數據可以是連續的，而計算機只認的是離散的數據，因此將其離散化後進行差分代替微分、求和代替積分等思想是非常重要的

9、數值分析演算法

如果在比賽中採用高級語言進行編程的話，那一些數值分析中常用的演算法比如方程組求解、矩陣運算、函數積分等演算法就需要額外編寫庫函數進行調用

10、圖象處理演算法

賽題中有一類問題與圖形有關，即使與圖形無關，論文中也應該要不乏圖片的這些圖形如何展示，以及如何處理就是需要解決的問題，通常使用Matlab進行處理

其他演算法簡介

1、灰色預測模型（一般）

解決預測類型題目。由於屬於灰箱模型，一般比賽期間不優先使用。滿足兩個條件可用：

①數據樣本點個數6個以上

②數據呈現指數或曲線的形式，數據波動不大

2、微分方程模型（一般）

微分方程模型是方程類模型中最常見的一種演算法。近幾年比賽都有體現，但其中的要求，不言而喻，學習過程中無法直接找到原始數據之間的關係，但可以找到原始數據變化速度之間的關係，通過公式推導轉化為原始數據的關係。

3、回歸分析預測（一般）

求一個因變數與若干自變數之間的關係，若自變數變化後，求因變數如何變化；樣本點的個數有要求：

①自變數之間協方差比較小，最好趨近於0，自變數間的相關性小；

②樣本點的個數n＞3k+1，k為預測個數；

4、馬爾科夫預測（較好）

一個序列之間沒有信息的傳遞，前後沒聯繫，數據與數據之間隨機性強，相互不影響；今天的溫度與昨天、後天沒有直接聯繫，預測後天溫度高、中、低的概率，只能得到概率，其演算法本身也主要針對的是概率預測。

5、時間序列預測

預測的是數據總體的變化趨勢，有一、二、三次指數平滑法（簡單），ARMA（較好）。

6、小波分析預測（高大上）

數據無規律，海量數據，將波進行分離，分離出周期數據、規律性數據；其預測主要依靠小波基函數，不同的數據需要不同的小波基函數。網上有個通用的預測波動數據的函數。

7、神經網路（較好）

大量的數據，不需要模型，只需要輸入和輸出，黑箱處理，建議作為檢驗的辦法，不過可以和其他方法進行組合或改進，可以拿來做評價和分類。

8、混沌序列預測（高大上）

適用於大數據預測，其難點在於時延和維數的計算。

9、插值與擬合（一般）

擬合以及插值還有逼近是數值分析的三大基礎工具，通俗意義上它們的區別在於：擬合是已知點列，從整體上靠近它們；插值是已知點列並且完全經過點列；逼近是已知曲線，或者點列，通過逼近使得構造的函數無限靠近它們。

10、模糊綜合評判（簡單）不建議單獨使用

評價一個對象優、良、中、差等層次評價，評價一個學校等，不能排序

11、層次分析法（AHP）（簡單）不建議單獨使用

作決策，去哪旅遊，通過指標，綜合考慮作決策

12、數據包絡（DEA）分析法（較好）

優化問題，對各省發展狀況進行評判

13、秩和比綜合評價法和熵權法（較好）

秩和比綜合評價法是評價各個對象並排序，但要求指標間關聯性不強；熵權法是根據各指標數據變化的相互影響，來進行賦權。兩者在對指標處理的方法類似。

14、優劣解距離法(TOPSIS法)（備用）

其基本原理，是通過檢測評價對象與最優解、最劣解的距離來進行排序，若評價對象最靠近最優解同時又最遠離最劣解，則為最好；否則為最差。其中最優解的各指標值都達到各評價指標的最優值。最劣解的各指標值都達到各評價指標的最差值。

15、投影尋蹤綜合評價法（較好）

可揉和多種演算法，比如遺傳演算法、模擬退火等，將各指標數據的特徵提取出來，用一個特徵值來反映總體情況；相當於高維投影之低維，與支持向量機相反。該方法做評價比一般的方法好。

16、方差分析、協方差分析等（必要）

方差分析：看幾類數據之間有無差異，差異性影響，例如：元素對麥子的產量有無影響，差異量的多少

協方差分析：有幾個因素，我們只考慮一個因素對問題的影響，忽略其他因素，但注意初始數據的量綱及初始情況。

此外還有靈敏度分析，穩定性分析

17、線性規劃、整數規劃、0-1規劃（一般）

模型建立比較簡單，可以用lingo解決，但也可以套用智能優化演算法來尋最優解。

18、非線性規劃與智能優化演算法（智能演算法至少掌握1-2個，其他的了解即可）

非線性規劃包括：無約束問題、約束極值問題

智能優化演算法包括：模擬退火演算法、遺傳演算法、改進的遺傳演算法、禁忌搜索演算法、神經網路、粒子群等

其他規劃如：多目標規劃和目標規劃及動態規劃等

19、複雜網路優化（較好）

離散數學中經典的知識點——圖論。主要是編程。

20、排隊論與計算機模擬（高大上）

排隊論研究的內容有3個方面：統計推斷，根據資料建立模型；系統的性態，即和排隊有關的數量指標的概率規律性；系統的優化問題。其目的是正確設計和有效運行各個服務系統，使之發揮最佳效益。

計算機模擬可通過元胞自動機實現，但元胞自動機對編程能來要求較高，一般需要證明其機理符合實際情況，不能作為單獨使用。

21、圖像處理（較好）

MATLAB圖像處理，針對特定類型的題目，一般和數值分析的演算法有聯繫。例如2013年國賽B題，2014網路賽B題。

22、支持向量機（高大上）

支持向量機實現是通過某種事先選擇的非線性映射（核函數）將輸入向量映射到一個高維特徵空間，在這個空間中構造最優分類超平面。主要用於分類。

23、多元分析

1、聚類分析、

2、因子分析

3、主成分分析：主成分分析是因子分析處理過程的一部分，可以通過分析各指標數據的變化情況，然後將數據變化相似的指標用一種具有代表性的來代替，從而達到降維的目的。

4、判別分析

5、典型相關分析

6、對應分析

7、多維標度法（一般）

8、偏最小二乘回歸分析（較好）

24、分類與判別

主要包括以下幾種方法，

1、距離聚類（系統聚類）（一般）

2、關聯性聚類

3、層次聚類

4、密度聚類

5、其他聚類

6、貝葉斯判別（較好）

7、費舍爾判別（較好）

8、模糊識別

25、關聯與因果

1、灰色關聯分析方法

2、Sperman或kendall等級相關分析

3、Person相關（樣本點的個數比較多）

4、Copula相關（比較難，金融數學，概率密度）

5、典型相關分析

（例：因變數組Y1234，自變數組X1234，各自變數組相關性比較強，問哪一個因變數與哪一個自變數關係比較緊密？）

6、標準化回歸分析

若干自變數，一個因變數，問哪一個自變數與因變數關係比較緊密

7、生存分析（事件史分析）（較好）

數據裡面有缺失的數據，哪些因素對因變數有影響

8、格蘭傑因果檢驗

計量經濟學，去年的X對今年的Y有沒影響

9、優勢分析

26、量子優化演算法（高大上）

量子優化可與很多優化演算法相結合，從而使尋優能力大大提高，並且計算速率提升了很多。其主要通過編程實現，要求編程能力較好。