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

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

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

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

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

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

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