求全局最優(yōu)化的幾種確定性算法.pdf

1、最優(yōu)化理論和方法的出現(xiàn)可以追溯到十分古老的極值問題，然而，它成為一門獨立的學科還是在本世紀40年代末，是在1947年Dantzing提出求解一般線性規(guī)劃問題的單純形算法之后。隨著工業(yè)革命、信息革命的不斷深化，和計算機技術的巨大發(fā)展，至今短短的幾十年，它得到了迅猛的發(fā)展?，F(xiàn)在，解線性規(guī)劃、非線性規(guī)劃以及隨機規(guī)劃、非光滑規(guī)劃、多目標規(guī)劃、幾何規(guī)劃、整數規(guī)劃等各種最優(yōu)化問題的理論研究發(fā)展迅速，新方法不斷涌現(xiàn)，在經濟、軍事、科學等方面得到了廣泛

2、的應用，成為一門十分活躍的學科。 全局最優(yōu)化是最優(yōu)化一個重要分支。相對于線性規(guī)劃等分支，它在理論和算法上遠沒有那么成熟、完善，大多數的全局最優(yōu)化算法缺少終止準則。但是現(xiàn)實社會對它有更多更迫切的要求，使得全局最優(yōu)化工作者利用不同的數學理論和工具，提出了各式各樣的算法，從理論到算法，都具有強大的生命力，而且需要進一步完善、深化。例如，在函數變換的基礎上，提出了填充函數法；在非線性方程理論的基礎上，提出了打洞函數法；在微分方程動力系統(tǒng)

3、的基礎上，提出了動力打洞算法；在積分原理的基礎上，提出了積分水平集算法；在組合理論的基礎上提出了分支定界算法，在隨機和啟發(fā)式基礎上提出了模擬退火法、遺傳算法等等。 全局最優(yōu)化算法，從算法的構造上大體可以分為確定型算法和隨機型算法，例如，填充函數法、打洞函數法屬于確定型算法；模擬退火法、遺傳算法屬于隨機型算法。我們在這篇文章中僅僅考慮非線性規(guī)劃的全局最優(yōu)化確定型算法、非線性整數規(guī)劃的全局最優(yōu)化確定型算法和非線性混合整數規(guī)劃的全局最

4、優(yōu)化確定型算法。這篇文章的主要目的就是，在研究已有確定型算法的基礎上，嘗試提出一些改進和創(chuàng)新。力圖在算法效果方面有所提高，在理論方面有所深化。其內容詳細情況如下： 在第一章中，我們介紹了幾種常見的全局最優(yōu)化算法，以及他們的特點。這包括：填充函數法、打洞函數法、分支定界算法和積分水平集算法。每一個算法都有各自的優(yōu)缺點。首先，我們從算法思想到相關理論都給出一些深入淺出的說明，在此基礎上，分析了各自的優(yōu)點和缺點，為我們進一步的推廣和構

5、造新的算法，提供一些指導思想和思路。 在第二章中，我們給出三個求解無約束全局最優(yōu)化問題的算法，在第二節(jié)中，對于一般無約束全局最優(yōu)化問題，我們給出一個填充函數的新的定義，它不同于傳統(tǒng)的填充函數定義。在此基礎上，提出了一種新的填充函數和相應的算法，該算法降低了對參數的依賴，具有較好的可操作性。數值試驗顯示，該算法是有效和可靠的。 在研究填充函數和打洞函數的基礎上，為克服打洞函數算法的一些缺點，在本章的第三節(jié)中，提出了修正打洞

6、函數算法。 我們在本章的第三節(jié)中，提出了一種求無約束全局最優(yōu)化的新的算法即積分函數算法，并分析了他們的的收斂性。 在第三章中，我們考慮了非線性整數規(guī)劃中的全局最優(yōu)問題，在它的第二節(jié)中，我們將填充函數推廣到整數規(guī)劃中，并給出了相應的填充函數算法。在第三節(jié)中，修正打洞函數算法被推廣到整數規(guī)劃中。在第四節(jié)中，我們提出了逐次下降算法，也取得了較好的計算效果。 在第四章中，我們嘗試著用已有的算法求解混合整數規(guī)劃的全局最優(yōu)問