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

1、最優(yōu)化理論和方法的出現(xiàn)可以追溯到十分古老的極值問題，然而，它成為一門獨立的學科還是在本世紀40年代末，是在1947年Dantzing提出求解一般線性規(guī)劃問題的單純形算法之后。隨著工業(yè)革命、信息革命的不斷深化，和計算機技術的巨大發(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)點和缺點，為我們進一步的推廣和構