《基於神經網路的無約束0-1二次規劃全局最優算法研究》是依託上海大學，由顧申申擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於神經網路的無約束0-1二次規劃全局最優算法研究
- 項目類別：青年科學基金項目
- 項目負責人：顧申申
- 依託單位：上海大學
中文摘要,結題摘要,
中文摘要
神經網路最佳化算法在處理大規模最佳化問題方面具有明顯的優勢。無約束0-1二次規劃因其具有重要的理論意義和廣泛的套用價值，是近年來的研究熱點。但是由於該問題是NP難問題，僅僅套用神經網路無法得到該問題的全局最優確定算法，造成利用神經網路算法計算該問題的全局最優解仍屬於空白。對此，本項目將通過分析目標函式所蘊含的重要幾何性質並充分結合神經網路與分枝定界方法的優勢與特點，設計0-1二次規劃基於神經網路的算法。一方面探索目標函式與等值面幾何形態之間定性與定量關係，並在此理論基礎上研究利用神經網路方法來處理關鍵的最佳化和排序問題，從而提高求解常規問題算法的效率。另一方面從幾何特性出發研究0-1二次規劃的最優性條件，設計求解特殊問題的多項式時間算法及其神經網路實現。本項目旨在通過對問題深層次的認識，建立一種基於神經網路的全局最優算法，並通過數值實驗證明其高效性，為求解此類難題和拓展神經網路套用開闢新的途徑。
結題摘要
0-1二次規劃問題是一個經典的整數最佳化問題並且也是一個眾所周知的NP難問題。為了改進0-1二次規劃問題的全局最佳化算法的性能，本項目分別對0-1二次規劃的特殊問題和一般問題提出了一系列有效的算法。對於特殊問題，本項目在三對角無約束0-1二次規劃問題算法的基礎上，提出了五對角和七對角無約束0-1二次規劃問題的有效解法，並推導出針對多奇數對角0-1二次規劃問題的多項式時間算法。在此基礎上引入動態規劃的思想，提出了新的適用於多奇數對角帶約束0-1二次規劃問題的算法。通過算法實現與驗證，結果顯示相關算法能快速解決特殊的高維問題。對於一般問題，在本項目中我們提出了一種新型的確切解算法。通過研究原問題的幾何特性，我們提高了算法計算上界和下界的質量。然後對於推導出的上界和下界算法，我們提出並套用了相關的反饋神經網路模型以提高計算速度。進一步，我們通過FPGA硬體對相關的神經網路算法進行實現來充分利用神經網路的平行結構。數值結果顯示我們提出的基於神經網路的分支定界類型的算法具有非常好的效果與效率。
