最優(yōu)化（Optimization）就是在復(fù)雜環(huán)境中遇到的許多可能的決策中，挑選“最好”的決策的科學(xué)。
17世紀(jì)，英國(guó)科學(xué)家艾薩克·牛頓（Isaac Newton）創(chuàng)立微積分的時(shí)代，就已提出極值問題，1847年，法國(guó)數(shù)學(xué)家奧古斯丁-路易·柯西（Cauchy）研究了函數(shù)值沿什么方向下降最快的問題，提出了最速下降法。20世紀(jì)40年代后，隨著生產(chǎn)和科學(xué)研究突飛猛進(jìn)地發(fā)展，最優(yōu)化理論和算法得以迅速發(fā)展，并不斷完善，逐步成為一門系統(tǒng)的學(xué)科。20世紀(jì)50年代以后，人們從一些自然現(xiàn)象和規(guī)律中受到啟發(fā)，提出了許多求解復(fù)雜優(yōu)化問題的新方法，例如模擬退火算法、遺傳算法及蟻群系統(tǒng)啟發(fā)式算法等。近半個(gè)世紀(jì)以來，最優(yōu)化得到了充分研究，在理論上取得了非常重要的研究成果，在實(shí)際應(yīng)用中正在發(fā)揮越來越大的作用，如計(jì)算機(jī)科學(xué)、工程學(xué)、運(yùn)籌學(xué)、經(jīng)濟(jì)學(xué)等，并且最優(yōu)化已經(jīng)成為發(fā)展迅速、內(nèi)容豐富、應(yīng)用廣泛的活躍學(xué)科。
最優(yōu)化常用算法有優(yōu)化算法、迭代法、啟發(fā)式算法，主要子領(lǐng)域包括多目標(biāo)規(guī)劃及整數(shù)規(guī)劃等。其中常見優(yōu)化問題有連續(xù)和離散優(yōu)化問題、無約束和約束優(yōu)化問題等。
定義
最優(yōu)化就是在復(fù)雜環(huán)境中遇到的許多可能的決策中，挑選“最好”的決策的科學(xué)。
最優(yōu)化問題的一般形式為：。
其中是中的集合，是上的實(shí)值函數(shù)。是英文（極小化）的縮寫。稱為目標(biāo)函數(shù)，稱為可行域，可行域中的點(diǎn)稱為可行點(diǎn)。
最優(yōu)化在不同的意義下，有不同的標(biāo)準(zhǔn)，它的范圍廣泛，無法在短時(shí)間內(nèi)系統(tǒng)又全面地介紹，這里來介紹最優(yōu)化的一個(gè)重要分支—數(shù)學(xué)規(guī)劃。數(shù)學(xué)規(guī)劃指的是對(duì)個(gè)變量對(duì)單目標(biāo)（或多目標(biāo)）函數(shù)求極小（或極大）。
其數(shù)學(xué)表達(dá)式為：
，
，
，
這里表示求極小，意思是受限制于···，是維向量，其分量為。在問題中稱為目標(biāo)函數(shù)，稱為約束條件。若求極大，可以將目標(biāo)函數(shù)寫成，若不等式約束可以寫成。
在問題中，若均是線性函數(shù)，則得到的規(guī)劃稱為線性規(guī)劃，其一般表達(dá)式為：
，
。
在問題中，中之一是非線性函數(shù)，則稱為非線性規(guī)劃，若去掉問題的約束條件，則得到：
，
稱為無約束最優(yōu)化問題，因此也稱問題為約束最優(yōu)化問題。
簡(jiǎn)史
17世紀(jì)，英國(guó)科學(xué)家艾薩克·牛頓（Isaac Newton）創(chuàng)立微積分的時(shí)代，就已提出極值問題，后來約瑟夫·拉格朗日（Lagrange）研究一個(gè)函數(shù)在一組等式約束條件下的極值問題時(shí)提出了乘數(shù)法。1847年，法國(guó)數(shù)學(xué)家奧古斯丁-路易·柯西（Cauchy）研究了函數(shù)值沿什么方向下降最快的問題，提出了最速下降法，這也是最優(yōu)化研究歷史上的第一種數(shù)值方法。1939年，蘇聯(lián)數(shù)學(xué)家康托洛維奇（Л.В.Канторович）提出了解決下料問題和運(yùn)輸問題這兩種線性規(guī)劃的求解方法。
人們關(guān)于最優(yōu)化問題的研究工作，隨著歷史的發(fā)展不斷深入。20世紀(jì)40年代以來，生產(chǎn)和科學(xué)研究突飛猛進(jìn)地發(fā)展，特別是電子計(jì)算機(jī)日益廣泛應(yīng)用，使最優(yōu)化問題的研究不僅成為一種迫切需要，而且有了求解的有力工具，最優(yōu)化理論和算法才得以迅速發(fā)展，并不斷完善，逐步成為一門系統(tǒng)的學(xué)科。 1947年，美國(guó)科學(xué)家丹齊克（Dantzig）提出了求解線性規(guī)劃問題的單純形法，為線性規(guī)劃的理論和算法奠定了基礎(chǔ)。 1951年，由托馬斯·庫(kù)恩（Kuhn）和塔克（Tucker）完成了非線性規(guī)劃的理論基礎(chǔ)性工作。20世紀(jì)50年代以后，人們從一些自然現(xiàn)象和規(guī)律中受到啟發(fā)，提出了許多求解復(fù)雜優(yōu)化問題的新方法，例如模擬退火算法，遺傳算法及蟻群系統(tǒng)啟發(fā)式算法等。近半個(gè)世紀(jì)以來，最優(yōu)化得到了充分研究，在理論上取得了非常重要的研究成果，在實(shí)際應(yīng)用中正在發(fā)揮越來越大的作用，已經(jīng)成為發(fā)展迅速、內(nèi)容豐富、應(yīng)用廣泛的活躍的學(xué)科。
相關(guān)概念
最優(yōu)解
局部最優(yōu)解
設(shè)問題的可行域?yàn)椋瑢?duì)于，如果存在的鄰域。
（1）使得，有，則稱是上述問題的局部最優(yōu)解。
（2）使得，，有，則稱是上述問題的嚴(yán)格局部最優(yōu)解。
全局最優(yōu)解
設(shè)問題的可行域?yàn)椋瑢?duì)于。
（1）如果，有，則稱是上述問題的全局最優(yōu)解。
（2）如果，，有，則稱是上述問題的嚴(yán)格全局最優(yōu)解。
凸集
對(duì)于中的兩個(gè)點(diǎn)，形如的點(diǎn)形成了過點(diǎn)和的直線。當(dāng)時(shí)，這樣的點(diǎn)形成了連接點(diǎn)與的線段。如果過集合中任意兩點(diǎn)的直線都在內(nèi)，則稱為仿射集，即；如果連接集合中任意兩點(diǎn)的線段都在內(nèi)，則稱為凸集，即
。
從仿射集的定義容易看出仿射集都是凸集。
凸函數(shù)
設(shè)函數(shù)為適當(dāng)函數(shù)，
如果是凸集，且對(duì)所有都成立，則稱是凸函數(shù)。
若存在常數(shù)，使得為凸函數(shù)，則稱為強(qiáng)凸函數(shù)，其中為強(qiáng)凸參數(shù)。
共軛函數(shù)
共軛函數(shù)是凸分析中的一個(gè)重要概念，常用于在凸優(yōu)化問題的理論與算法中。任一適當(dāng)函數(shù)的共軛函數(shù)定義為：
。
次梯度
設(shè)為適當(dāng)凸函數(shù)，為定義域中的一點(diǎn)，若向量滿足：
，
則稱為函數(shù)在點(diǎn)處的一個(gè)次梯度。進(jìn)一步稱集合：
，為在點(diǎn)處的次導(dǎo)數(shù)。
優(yōu)化問題分類
連續(xù)和離散優(yōu)化問題
根據(jù)變量是連續(xù)還是離散，最優(yōu)化問題可以分為連續(xù)和離散優(yōu)化問題兩大類。
連續(xù)優(yōu)化問題
連續(xù)優(yōu)化問題是指決策變量所在的可行集合是連續(xù)的，比如平面、區(qū)間等。如稀疏優(yōu)化問題的約束集合就是連續(xù)的。在連續(xù)優(yōu)化問題中，基于決策變量取值空間以及約束和目標(biāo)函數(shù)的連續(xù)性，可以從一個(gè)點(diǎn)處目標(biāo)和約束函數(shù)的取值來估計(jì)該點(diǎn)可行領(lǐng)域內(nèi)的取值情況，進(jìn)一步地，可以根據(jù)鄰域內(nèi)的取值信息來判斷該點(diǎn)是否最優(yōu)。離散優(yōu)化問題則不具備這個(gè)性質(zhì)，因?yàn)闆Q策變量是在離散集合上取值。因此，在實(shí)際中往往比連續(xù)優(yōu)化問題更難求解。
離散優(yōu)化問題
離散優(yōu)化問題是指決策變量能在離散集合上取值，比如離散點(diǎn)集、整數(shù)集等。常見的離散優(yōu)化問題有整數(shù)規(guī)劃，其對(duì)應(yīng)的決策變量的取值范圍是整數(shù)集合。實(shí)際中的離散優(yōu)化問題往往可以轉(zhuǎn)化為一系列連續(xù)優(yōu)化問題來進(jìn)行求解，比如線性整數(shù)規(guī)劃問題中著名的分支定界方法，就是松弛成一系列線性規(guī)劃問題來進(jìn)行求解。
無約束和約束優(yōu)化問題
最優(yōu)化問題的另外一個(gè)重要的分類標(biāo)準(zhǔn)是約束是否存在。無約束優(yōu)化問題的決策變量沒有約束條件限制，即可行集合。相對(duì)地，約束優(yōu)化問題是指帶有約束條件的問題。
約束優(yōu)化問題
約束非線性優(yōu)化問題是指：
其中，及都是定義在上的實(shí)值連續(xù)函數(shù)，且至少有一個(gè)是非線性的。是一正整數(shù)，是介于和之間的整數(shù)。被稱為目標(biāo)函數(shù)，被稱為約束函數(shù)。如果，則問題被稱為等式約束優(yōu)化問題；如果都是線性函數(shù)，則稱是一個(gè)線性約束優(yōu)化問題；一個(gè)線性約束優(yōu)化問題，如果目標(biāo)函數(shù)是二次函數(shù)，則被稱為二次規(guī)劃問題。
無約束優(yōu)化問題
無約束優(yōu)化問題對(duì)應(yīng)于在歐幾里得空間中求解一個(gè)函數(shù)的最小值點(diǎn)。在某種程度上，約束優(yōu)化問題就是無約束優(yōu)化問題，很多約束優(yōu)化問題的求解也是轉(zhuǎn)化為一系列的無約束優(yōu)化問題來做，常見方式有增廣拉格朗日函數(shù)法、罰函數(shù)法等。
隨機(jī)和確定性優(yōu)化問題
隨機(jī)優(yōu)化問題
隨機(jī)優(yōu)化問題是指目標(biāo)或者約束函數(shù)中涉及隨機(jī)變量而帶有不確定性的問題。隨機(jī)優(yōu)化問題中總是包含一些未知的參數(shù)。隨機(jī)優(yōu)化問題在機(jī)器學(xué)習(xí)、深度學(xué)習(xí)以及強(qiáng)化學(xué)習(xí)中有著重要應(yīng)用，其優(yōu)化問題的目標(biāo)函數(shù)是關(guān)于一個(gè)未知參數(shù)的期望的形式。因?yàn)閰?shù)的未知性，實(shí)際中常用的方法是通過足夠多的樣本來逼近目標(biāo)函數(shù)，得到一個(gè)新的有限和形式的目標(biāo)函數(shù)。
隨機(jī)優(yōu)化問題可以表示成以下形式：
。
確定性優(yōu)化問題
確定性優(yōu)化問題中目標(biāo)和約束函數(shù)都是確定的，計(jì)算步驟相比較隨機(jī)性優(yōu)化算法來說比較復(fù)雜。
線性和非線性規(guī)劃問題
線性規(guī)劃是指問題中目標(biāo)函數(shù)和約束函數(shù)都是線性的。當(dāng)目標(biāo)函數(shù)和約束函數(shù)至少有一個(gè)是非線性的，那么對(duì)應(yīng)的優(yōu)化問題的稱為非線性規(guī)劃問題。
線性規(guī)劃
線性規(guī)劃問題是求一組非負(fù)變量，它們?cè)跐M足一組線性等式或不等式約束的條件下，使一個(gè)線性函數(shù)達(dá)到極小或極大。即：
為了便于研究和求解，便把各種形式的線性規(guī)劃問題化為線性規(guī)劃的標(biāo)準(zhǔn)形式，稱下列形式的線性規(guī)劃問題為線性規(guī)劃的標(biāo)準(zhǔn)型：
其中，為已知常數(shù)，一般，稱條件為非負(fù)約束，稱為成本系數(shù)或價(jià)格系數(shù)。
非線性規(guī)劃
非線性規(guī)劃是最優(yōu)化的一個(gè)重要分支，其形式為：
即在維空間的一個(gè)子集中求函數(shù)的極小值和極小點(diǎn)值。如果，則以上問題被稱為無約束非線性規(guī)劃問題，如果是的真子集，則以上問題被稱為約束非線性規(guī)劃問題。
凸和非凸優(yōu)化問題
凸優(yōu)化問題是指最小化問題中的目標(biāo)函數(shù)和可行域分別是凸函數(shù)和凸集。如果其中有一個(gè)或者兩者都不是凸的，那么相應(yīng)的最小化問題是非凸優(yōu)化問題。因?yàn)橥箖?yōu)化問題的任何局部最優(yōu)解都是全局最優(yōu)解，其相應(yīng)的算法設(shè)計(jì)以及理論分析相對(duì)非凸優(yōu)化問題簡(jiǎn)單很多。
凸優(yōu)化
考慮非線性規(guī)劃問題：
記的約束集為：
。
如果問題的約束集是凸集，目標(biāo)函數(shù)是上的凸函數(shù)，則叫做是非線性凸規(guī)劃或簡(jiǎn)稱凸規(guī)劃。
非凸優(yōu)化
在實(shí)際問題的建模中，經(jīng)常更傾向于得到一個(gè)凸優(yōu)化模型。另外，判斷一個(gè)問題是否是凸問題也很重要。比如，給定一個(gè)非凸優(yōu)化問題，一種方法是將其轉(zhuǎn)化為一系列凸優(yōu)化子問題來求解。此時(shí)需要清楚原非凸問題中的哪個(gè)或哪些函數(shù)導(dǎo)致了非凸性，之后考慮的是如何用凸優(yōu)化模型來逼近原問題。
優(yōu)化問題常用特殊符號(hào)
函數(shù)極值
無約束極值
或。
這里是定義在維空間上的可微函數(shù)。
約束極值
或；
滿足于，。
臨界點(diǎn)與極值的分類
存在性
優(yōu)化問題
。
考慮一個(gè)適當(dāng)且閉的函數(shù)，假設(shè)下面三個(gè)條件中任意一個(gè)成立：
（1）是有界的；
（2）存在一個(gè)常數(shù)使得下水平集是非空且有界的；
（3）是強(qiáng)制的，即對(duì)于任一滿足的點(diǎn)列，都有，那么問題的最小值點(diǎn)集是非空且緊的。
最優(yōu)性條件
一階最優(yōu)性條件
一階必要條件
假設(shè)在全空間可微。如果是一個(gè)局部極小點(diǎn)，那么。
二階最優(yōu)性條件
二階必要條件
如果是的一個(gè)局部極小點(diǎn)，那么。
二階充分條件
如果在點(diǎn)處有，成立，那么為的一個(gè)局部極小點(diǎn)。
理論
主要理論
多目標(biāo)規(guī)劃
在一個(gè)具體的優(yōu)化問題中，有的指標(biāo)可能要求最小化，有的則要求最大化；有的約束可能是“”，有的則可能是“”。但是，總可以通過乘以 ，使它們化成下面多目標(biāo)規(guī)劃的標(biāo)準(zhǔn)形式：
；
，
其中，，稱為決策向量，所在的空間稱為決策空間；稱為目標(biāo)函數(shù)，所在的空間稱為目標(biāo)空間，稱為約束函數(shù)。多目標(biāo)規(guī)劃問題亦稱為向量最優(yōu)化問題。多目標(biāo)規(guī)劃問題實(shí)際上是將決策空間的一個(gè)區(qū)域映射到目標(biāo)空間的一個(gè)區(qū)域，所以問題涉及到兩個(gè)集合概念：
，稱為的可行域；
，稱為值域。
整數(shù)規(guī)劃
不同于線性規(guī)劃，整數(shù)規(guī)劃要求優(yōu)化變量必須取整數(shù)值，而不能是分?jǐn)?shù)值。一般形式如下：
其中，是給定的矩陣和向量，是整數(shù)集合。如果只要求部分是整數(shù)，該問題被稱為混合整數(shù)規(guī)劃問題。
相關(guān)理論
組合優(yōu)化
組合優(yōu)化又稱組合規(guī)劃，是在給定有限集的所有具備某些特性的子集中，按某種目標(biāo)找出一個(gè)最優(yōu)子集的一類最優(yōu)化。
一個(gè)組合最優(yōu)化問題應(yīng)該給出下述參數(shù)：
有窮的變量集合；
有窮的值的集合；
目標(biāo)函數(shù)；
約束條件的集合。
一個(gè)組合優(yōu)化問題的解是對(duì)變量集的一組賦值，并且在滿足中約束條件的前提下使得目標(biāo)函數(shù)取得最大（或最小）值。
二次規(guī)劃
考慮如下特殊的約束優(yōu)化問題：
；
，
，
其中為對(duì)稱矩陣，為維實(shí)向量，為實(shí)數(shù)，稱以上問題為二次規(guī)劃問題。
對(duì)偶定理
考慮如下形式的約束規(guī)劃問題：
在問題中，集合通常是由簡(jiǎn)單約束條件所定義的集合，如，，等等。當(dāng)，問題的可行域記為：
。
問題為原問題，以下引入原問題的對(duì)偶問題。首先針對(duì)原問題引進(jìn)函數(shù)：。
定義如下對(duì)偶函數(shù)（簡(jiǎn)稱對(duì)偶函數(shù)）：。
根據(jù)定義，給定，函數(shù)值通過求解優(yōu)化問題得到，該優(yōu)化問題通常稱為對(duì)偶子問題。易知，對(duì)于滿足的，以及問題的任意可行解，均有成立，故是問題最優(yōu)值的下界，由最大化下界可得如下對(duì)偶問題（簡(jiǎn)稱對(duì)偶問題）：
；
。
設(shè)是原問題的可行解，是其對(duì)偶問題的可行解，則。根據(jù)弱對(duì)偶定理，可以得出如下推論：
推論一：。
推論二：設(shè)是原問題的可行解，是其對(duì)偶問題的可行解。若，則和分別是原問題和對(duì)偶問題的最優(yōu)解，且最優(yōu)值相等。
推論三：若原問題是無界的，則對(duì)于任意滿足的，均有；若對(duì)偶問題是無界的，則原問題不可行。
強(qiáng)對(duì)聯(lián)定理
設(shè)集合為非空凸集，及是凸函數(shù)，均為線性函數(shù)。假設(shè)存在使得且其中，則強(qiáng)對(duì)偶成立，即：
。
主要算法
優(yōu)化算法
單純形法
單純形法同其他的數(shù)值求解方法一樣是一種迭代法，它根據(jù)線性規(guī)劃問題的特點(diǎn)在問題可行域的頂點(diǎn)中逐步確定問題的最優(yōu)解，在每一個(gè)是基本可行解的迭代點(diǎn)，如果它不是最優(yōu)的，單純形法從與該頂點(diǎn)相連結(jié)的邊中確定一個(gè)使目標(biāo)函數(shù)值下降的邊，沿該邊移動(dòng)可以確定一個(gè)與該頂點(diǎn)相鄰且目標(biāo)函數(shù)又優(yōu)于該頂點(diǎn)的新頂點(diǎn)（新的基本可行解）。由于可行域的頂點(diǎn)數(shù)是有限的，如果每一次的移動(dòng)都能使目標(biāo)函數(shù)值下降，則經(jīng)過有限次的移動(dòng)方法必終止于問題的一個(gè)最優(yōu)頂點(diǎn)。
考察線性規(guī)劃問題：
。
設(shè)為一個(gè)基本可行解，單純形方法首先檢驗(yàn)它的最優(yōu)性。如果它不是最優(yōu)的，確定與該頂點(diǎn)相連的一條使目標(biāo)函數(shù)下降的邊；接下來確定沿這個(gè)邊移動(dòng)多遠(yuǎn)可以到達(dá)另一個(gè)更優(yōu)的相鄰頂點(diǎn)，也就是得出一個(gè)新的基本可行解。
啟發(fā)式算法
模擬退火算法
模擬退火算法是一種基于迭代求解策略的隨機(jī)尋優(yōu)算法，其算法思想來源于物理中的固體降溫退火過程與數(shù)學(xué)中的許多組合優(yōu)化問題之間的相似性。物理中固體在退火過程中，主要有三大物理過程：
升溫過程
當(dāng)固體物質(zhì)溫度升高時(shí)，物質(zhì)內(nèi)部粒子能量升高，粒子的運(yùn)動(dòng)增強(qiáng)，當(dāng)溫度升高到一定程度，內(nèi)部粒子運(yùn)動(dòng)脫離其平衡位置，固體就會(huì)熔化成為液體狀態(tài)。
當(dāng)物質(zhì)溫度降低到恰好與周圍環(huán)境相同時(shí)，物質(zhì)將暫時(shí)停止向周圍環(huán)境散發(fā)熱量。此時(shí)，物質(zhì)溫度保持不變，但是物質(zhì)內(nèi)部的粒子自由能會(huì)逐漸降低，當(dāng)物質(zhì)內(nèi)部粒子的自由能降低到當(dāng)前物質(zhì)溫度所蘊(yùn)含的能量能夠維持的最低狀態(tài)時(shí)，物質(zhì)會(huì)進(jìn)入平衡態(tài)。物質(zhì)溫度保持不變，但內(nèi)部粒子自由能減少到達(dá)到平衡態(tài)的整個(gè)過程就是等溫過程。
冷卻過程
物質(zhì)溫度降低到一定程度后，物質(zhì)內(nèi)部的粒子能量逐漸減少，粒子運(yùn)動(dòng)逐漸減弱，直至所有粒子運(yùn)動(dòng)漸趨穩(wěn)定。此時(shí)，物質(zhì)內(nèi)部系統(tǒng)能量下降到當(dāng)前環(huán)境中的最低值，物質(zhì)內(nèi)部粒子將重新進(jìn)入平衡狀態(tài)。表現(xiàn)在外就是物質(zhì)重新凝結(jié)成為固態(tài)，此時(shí)的物質(zhì)內(nèi)部能量比熔化前的固體狀態(tài)更低。
遺傳算法
遺傳算法算法是根據(jù)大自然中生物體進(jìn)化規(guī)律而設(shè)計(jì)提出的，該算法通過數(shù)學(xué)的方式，利用計(jì)算機(jī)仿真運(yùn)算，將問題的求解過程轉(zhuǎn)換成類似生物進(jìn)化中的染色體基因的交叉、變異等過程。
選擇
從群體中選擇優(yōu)勝個(gè)體、淘汰劣質(zhì)個(gè)體的操作叫選擇。選擇映射有時(shí)又稱為再生算子。選擇的目的是把優(yōu)化的個(gè)體（或解）直接遺傳到下一代或通過聯(lián)會(huì)交叉產(chǎn)生新的個(gè)體再遺傳到下一代。選擇操作是建立在群體中個(gè)體的適應(yīng)度評(píng)估基礎(chǔ)上的，目前常用的選擇算子包括適應(yīng)度比例方法、隨機(jī)遍歷抽樣法、局部選擇法。
交叉
在自然界生物進(jìn)化過程中起核心作用的是生物遺傳基因的重組。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。
變異
變異算法的基本內(nèi)容是對(duì)群體中的個(gè)體串的某些基因座上的基因值作變動(dòng)。變異算法的運(yùn)算過程大體如下：
1.將待解決問題的約束與優(yōu)化目標(biāo)等參數(shù)編碼到染色體中，形成問題參數(shù)與染色體的對(duì)應(yīng)關(guān)系，構(gòu)成染色體編碼空間；
2.根據(jù)問題的參數(shù)設(shè)定恰當(dāng)?shù)?a href="/hebeideji/764586016548313774.html">適應(yīng)度函數(shù)；
3.設(shè)置進(jìn)化過程中的相關(guān)操作映射，主要有交叉算子、變異算子、選擇算子等；
4.根據(jù)問題確定合適的遺傳算法參數(shù)，包含種群規(guī)模、交叉概率、變異概率等參數(shù)；
5.生成初始種群；
6.對(duì)種群中的所有個(gè)體進(jìn)行適應(yīng)度函數(shù)值計(jì)算；
7.判斷種群是否滿足算法終止條件，若滿足條件則輸出該種群中適應(yīng)度值最高的個(gè)體；如果不滿足算法終止條件，則繼續(xù)后續(xù)的操作過程；
8.對(duì)種群進(jìn)行選擇、交叉、變異運(yùn)算，產(chǎn)生新的種群；
9.重復(fù)步驟6，7，8產(chǎn)生種群，直至滿足算法終止條件。
迭代法
最速下降法
最速下降法以負(fù)梯度方向作為極小化算法的下降方向，又稱梯度法，是無約束最優(yōu)化中最簡(jiǎn)單的方法。設(shè)函數(shù)在附近連續(xù)可微，且，由展式：
。
可知，若記，則滿足的方向是下降方向。當(dāng)取定后，的值越小，即的值越大，函數(shù)下降得越快。由不等式：，
故當(dāng)且僅當(dāng)時(shí)，最小，從而稱是最速下降方向。最速下降法的迭代格式為：。
這個(gè)方法的計(jì)算步驟如下：
1.給出；
2.計(jì)算；如果，則停止；
3.由一維搜索求步長(zhǎng)因子，使得；
4.計(jì)算；
5.，轉(zhuǎn)步驟。
牛頓法
牛頓法的基本思想是利用目標(biāo)函數(shù)在迭代點(diǎn)處的二次展開作為模型函數(shù)，并利用這個(gè)二次模型函數(shù)的極小點(diǎn)序列去逼近目標(biāo)函數(shù)的極小點(diǎn)。
設(shè)二次連續(xù)可微，，矩陣正定。在附近用二次展開近似，
，
其中為的二次近似。將上式右邊極小化，即令：，
得：，
這就是牛頓法迭代公式，相應(yīng)的算法稱為牛頓法。
擬牛頓法
考慮目標(biāo)函數(shù)在當(dāng)前點(diǎn)處的二次模型：，
其中，是對(duì)稱正定矩陣，是近似，它將在每次迭代中進(jìn)行校正，極小化這個(gè)二次模型得到：，
從而新的迭代點(diǎn)為：，
其中，是線性搜索步長(zhǎng)因子，上述迭代稱為擬牛頓迭代，他與牛頓迭代的主要區(qū)別在于中，用近似代替了艾薩克·牛頓迭代中的矩陣。
設(shè)：在開集上二次連續(xù)可微，在附近的二次近似為：
，
對(duì)上式兩邊求導(dǎo)，有：。
令，得： 。
令：，
成為。
顯然，如果是正定二次函數(shù)，上述關(guān)系式精確成立。要求在擬牛頓法中構(gòu)造出來的近似滿足這種關(guān)系，從而得到：。
上式稱為擬牛頓條件或擬牛頓方程。一般的擬牛頓算法如下：
1.給出初始點(diǎn)；
2.如果，停止；
3.解得搜索方向；（或計(jì)算）；
4.由線性搜索求步長(zhǎng)因子，并令；
5.校正產(chǎn)生（或校正產(chǎn)生），使得擬牛頓條件成立；
6.，轉(zhuǎn)步驟。
共軛梯度法
共軛梯度法是一個(gè)典型的共軛方向法，它的每一個(gè)搜索方向是互相共軛的，而這些搜索方向僅僅是負(fù)梯度方向與上一次迭代的搜索方向的組合。因此，存儲(chǔ)量少，計(jì)算方便。
記：，
左乘，并使得，得。（公式）
另外常用的三個(gè)公式為：
，（公式）
，（公式）
。（公式）
對(duì)于正定縣二次函數(shù)，若采用精確線性搜索，以上幾個(gè)關(guān)于的共軛梯度公式等價(jià)。但在實(shí)際計(jì)算中，公式和公式最常用。由于強(qiáng)線性搜索準(zhǔn)則并不保證方法的方向是下降的，如果定義參數(shù)：，
其中由 定義，則方法具有下降性質(zhì)，這樣的方法稱為方法。
注意到對(duì)于正定二次函數(shù)：，
其中是方程組的殘量，以及
，
給出如下關(guān)于正定縣二次函數(shù)極小化的共軛梯度法算法：
1.初始步：給出，計(jì)算，令；
2.如果，停止；
3.計(jì)算
，
，
，
，
。
4.令，轉(zhuǎn)步驟。
二次罰函數(shù)法
罰函數(shù)法是一類不可行點(diǎn)的方法，對(duì)初始點(diǎn)的選取沒有可行性的限制，對(duì)不可行約束采用不同的懲罰函數(shù)，就形成不同的罰函數(shù)方法。其中最簡(jiǎn)單也經(jīng)常采用的是二次罰函數(shù)方法，二次罰函數(shù)由目標(biāo)函數(shù)加上懲罰項(xiàng)組成，其中懲罰項(xiàng)是約束違反函數(shù)的平方。
對(duì)于等式約束問題：
，
二次罰函數(shù)定義為：
這里是罰參數(shù)，當(dāng)趨于零時(shí)，如果約束不可行，即，則違反約束的懲罰項(xiàng)劇烈地增大。可以證明：當(dāng)時(shí)罰函數(shù)的極小點(diǎn)就是原問題的極小點(diǎn)。因?yàn)閼土P項(xiàng)是二次的，所以光滑可微，這樣可以使用無約束優(yōu)化技術(shù)來求解得罰函數(shù)的近似極小點(diǎn)。二次罰函數(shù)法的算法為：
1.給定，允許參數(shù)值，初始點(diǎn)；
2.從開始，極小化得近似極小點(diǎn)；
3.當(dāng)時(shí)，終止，得近似解；否則，選擇新的罰參數(shù)，令，轉(zhuǎn)步驟。
內(nèi)點(diǎn)障礙函數(shù)法
內(nèi)點(diǎn)障礙函數(shù)法通過在目標(biāo)函數(shù)上引入一個(gè)關(guān)于約束的障礙項(xiàng)，當(dāng)?shù)c(diǎn)由可行域的內(nèi)部接近可行域的邊界時(shí)，障礙項(xiàng)將趨于無窮大來迫使迭代點(diǎn)返回可行域的內(nèi)部，從而保持迭代點(diǎn)的嚴(yán)格可行性。
考慮不等式約束最優(yōu)化問題：
定義嚴(yán)格可行內(nèi)點(diǎn)區(qū)域?yàn)椋海?/p>
并假設(shè)是非空的。對(duì)考慮不等式約束最優(yōu)化問題，障礙函數(shù)具有如下性質(zhì)：
1.在外部的值或者無定義或者是無窮的；
2.在內(nèi)部都是連續(xù)可微的；
3.當(dāng)趨于的邊界，其值趨于。
常用的障礙函數(shù)是對(duì)數(shù)障礙函數(shù)：，
分?jǐn)?shù)障礙罰函數(shù)：，
其中為自然對(duì)數(shù)，為障礙參數(shù)。
應(yīng)用
物流運(yùn)輸
最優(yōu)化問題和方法被廣泛應(yīng)用于物流運(yùn)輸中。電子商務(wù)時(shí)代下的商業(yè)物流運(yùn)輸路徑選擇是一個(gè)極其重要的問題，如何選擇最優(yōu)的物流運(yùn)輸路徑，為企業(yè) 提供最優(yōu)質(zhì)、最快捷、最經(jīng)濟(jì)的物流服務(wù)是所有電商企業(yè)所面臨的難題。最優(yōu)化商業(yè)物流運(yùn)輸路徑選擇的研究具有很大的實(shí)際應(yīng)用價(jià)值，可以幫助物流企業(yè)提高運(yùn)輸效率，降低物流成本，并且實(shí)現(xiàn)更加客戶化的配送服務(wù)。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，最優(yōu)化商業(yè)物流運(yùn)輸路徑的研究也實(shí)現(xiàn)了更好的突破和發(fā)展。
土木工程
最優(yōu)化問題在工程造價(jià)中主要用于成本控制方面。隨著建筑行業(yè)的發(fā)展，工程造價(jià)管理越來越受到重視。建筑工程造價(jià)是指在完成建筑項(xiàng)目時(shí)所需要的全部費(fèi)用，包括各種材料、勞動(dòng)力、設(shè)備和管理費(fèi)用等。在建筑項(xiàng)目中，造價(jià)管理是一個(gè)非常關(guān)鍵的工作環(huán)節(jié)， 直接影響項(xiàng)目的進(jìn)度和經(jīng)濟(jì)效益，實(shí)現(xiàn)建筑工程實(shí)現(xiàn)成本的最優(yōu)化對(duì)于建筑工程造價(jià)的動(dòng)態(tài)管理與成本控制具有重要的理論價(jià)值和實(shí)際意義。
電氣工程
隨著新能源行業(yè)發(fā)展得越來越快速，新能源并網(wǎng)規(guī)模不斷擴(kuò)大，但是電力系統(tǒng)消納能力不足，導(dǎo)致資源過剩。所以，尋求更優(yōu)化的能源配比是非常重要的。如在儲(chǔ)能運(yùn)行方面，可以通過建立最優(yōu)化的模型來保證成本、減少電網(wǎng)的碳排放并提高太陽(yáng)能光伏的消納能力。
金融學(xué)
組合優(yōu)化在金融投資方面應(yīng)用也非常廣泛，如，很多投資者會(huì)用此選擇合適的股票組合，達(dá)到風(fēng)險(xiǎn)最小化和收益最大化。晉中投資中組合優(yōu)化研究主要是從投資收益最大化或者投資風(fēng)險(xiǎn)最小化視角展開，達(dá)到實(shí)現(xiàn)收益最大化，且同時(shí)滿足風(fēng)險(xiǎn)最小化的目的。
人工智能
最優(yōu)化在人工智能方面應(yīng)用較為廣泛，如在空中機(jī)器人飛行軌跡方面。基于傳統(tǒng)最優(yōu)化方法得到的過渡軌跡在尾座式無人機(jī)實(shí)際飛行過程中可行性低和魯棒性差的問題，優(yōu)化過渡軌跡可以提高其可行性。以一種雙發(fā)尾座式無人機(jī)為研究對(duì)象，通過分析機(jī)翼不同區(qū)域之間的迎角差異，構(gòu)建出非線性動(dòng)力學(xué)模型。基于傾轉(zhuǎn)旋翼機(jī)過渡走廊研究思路，設(shè)計(jì)出一種針對(duì)尾座式無人機(jī)的過 渡走廊，并通過限制爬升速率和俯仰角速率來提高過渡走廊的可行性。通過分析模型誤差對(duì)過渡走廊的影響，得到一 條具有最大安全裕度的目標(biāo)過渡軌跡。仿真和實(shí)際飛行結(jié)果表明，所提出的過渡方法能夠引導(dǎo)飛機(jī)快速安全地完成過渡，避免了出現(xiàn)高度增加過大、過渡時(shí)間過長(zhǎng)以及作動(dòng)器飽和等不利情況。
參考資料 >