數學建模演算法（一）——優化問題
數學建模演算法（一）——優化問題
9 人贊了文章
主要來自司守奎先生的《數學建模》、感謝知乎網友Loez的《數學建模演算法總結》
一、優化問題
【一般表達形式】
都可以用蒙特卡洛方法解決
1、 線性規劃
賽題中常出現轉換為「分段線性函數」的情況。
2、 整數規劃
求解方法：
1- 分支定界法
【主要思路】：分支定界法的主要思想是對規劃問題的解空間進行遍歷從而得出最優解，利用剪枝的思想在遍歷的過程中由已得出的可行解確定上下界，在後續遍歷是進行「剪枝」，縮小遍歷範圍。
【求解步驟】：
1、 不考慮整數限制，得出相應線性規劃的最優解，確定目標函數的上/下界；
2、 確定可行解，進行分枝
3、 比較分枝的最優目標函數與上下界的關係，判斷是否剪枝
2- 割平面法
3- 隱枚舉法（0-1整數規劃）【過濾隱枚舉法】【分支隱枚舉法】
過濾隱枚舉法：
1、 求出一個可行解，確定過濾條件
2、 依次計算其他可行解，不滿足過濾條件的結果刪除
3、 每得出一個更優解，改進過濾條件
4- 匈牙利法（特殊0-1整數規劃）
5- 蒙特卡洛法
【主要思想】：當變數取值範圍極大時，在一定範圍內進行遍歷，得到最優解。
3、 非線性規劃
【無約束條件】
主要思路是搜索，根據如何搜索，怎樣確定搜索方向，如何加速搜索，可大致分為以下幾種方法：
常用求解方法：
1、0.618法（試探法）
【主要思想】：以0.618的縮短率，逐漸縮小搜索範圍尋找一定精度內的最優解。是一種等速對稱進行試探的方法，每次試探點都取在區間長度的0.618和0.382倍處。
2、 二次插值法 （插值法）
【主要思想】：在搜索區間中，不斷用低次多項式（不超過3）來近似目標函數，逐步用插值多項式的極小點來逼近最優解。
3、 二分法
4、 梯度法（最速下降法）
【主要思想】：每次迭代都從函數的負梯度方向（下降最快的方向）出發，進行搜索。
【求解步驟】：
1、 選取初始點和允許誤差
2、 計算梯度向量，若梯度向量小於給允許誤差，則停止
3、 構造負梯度方向
4、 在負梯度方向上進行一維搜索，求出該方向上的極值；轉到2
5、 Newton法
【主要思想】：和最速下降法思路類似，只是每次選取Newton方向
出發
收斂速度快於方法4，當變數維數高時計算量大，不適用。
6、 變尺度法（DFP法）
【主要思想】：每一步都以現有信息來確定尺度矩陣，從而決定下一個搜索方向，每次一迭代，目標函數值均有所下降
收斂速度快，計算量小，對高維問題具有顯著優越性。
【求解步驟】：（書p51）
7、直接法
【有約束條件】：
主要思路是將約束問題轉化為無約束問題。
1、 二次規劃
2、 罰函數法SUMT（p54）
【主要思想】：利用約束條件作出罰函數，從而構造出帶參數的增廣目標函數，將問題化為無約束非線性規劃問題。
3、 梯度法（p57）
4、 動態規劃問題
5、 對策論（p162）：參與者的利益相互衝突
典型問題：【零和對策】：只有兩名局中人
【現代優化演算法】：禁忌搜索、模擬退火、遺傳演算法、人工神經網路
1、 禁忌搜索：
局部搜索演算法的拓展，利用禁止重複前面工作的思想，用一個禁忌表記錄已經到達過的局部最優點，從而避免出現在後序（禁忌長度以內）的搜索範圍中。
【關鍵概念】：候選集合、禁忌對象、禁忌長度、評價函數、特赦規則、記憶頻率
2、 模擬退火：
在找尋最優解的過程中，每次以一種方法變換新解，再利用退火過程的思想，當溫度下降時會以較大概率接受一個新的解，重複該過程直至達到熱平衡狀態（符合接受準則）。
【關鍵概念】：狀態空間（初始解空間應盡量靠近最優解，這樣演算法執行速度快，可考慮蒙特卡洛方法）、降溫速度（降溫係數）、新解變換方法（2、3變換法、代價函數法）、接受準則、終止溫度
3、 遺傳演算法：
通過羣體搜索技術，根據適者生存的原則（演算法停止時，最優目標值的解被留住的概率大）逐代進化，最終得到準最優解。
【關鍵概念】：解的編碼、適應度函數、變異概率（編碼中的某一分量發生改變）、交叉概率（產生一組新解）
【改進的遺傳演算法】1、交叉操作以「門當戶對」為原則，目標函數小與小的配對，大的與大的配對。 2、變異操作以混沌序列對染色體中多個基因進行變異，以免演算法早熟，從而跳出局部最優解，尋找全局最優解。
4、 蟻羣演算法（TSP問題）
推薦閱讀：
