1.3 智能優(yōu)化方法

1.3.1 智能優(yōu)化方法簡介

隨著科技的快速發(fā)展，多學(xué)科的分布式合作在制造業(yè)中越來越流行。資源分配規(guī)模迅速增長，從設(shè)計(jì)、仿真到生產(chǎn)、運(yùn)維的整個(gè)生產(chǎn)周期越來越復(fù)雜。為了進(jìn)一步縮短工業(yè)周期，提高運(yùn)作效率，改善資源和信息的利用率，很多宏觀和微觀過程中的復(fù)雜問題有待解決和優(yōu)化。從數(shù)學(xué)的角度，這些問題均可以根據(jù)變量、特性等內(nèi)容分解為連續(xù)的數(shù)值優(yōu)化問題和離散的組合優(yōu)化問題。例如，復(fù)變函數(shù)優(yōu)化、控制和仿真領(lǐng)域的非線性方程、復(fù)雜非線性規(guī)劃均可以劃歸為連續(xù)數(shù)值優(yōu)化問題；生產(chǎn)過程和系統(tǒng)管理領(lǐng)域的車間/任務(wù)調(diào)度、服務(wù)組合最優(yōu)選擇、合作伙伴選擇和資源分配問題均可以劃歸為離散組合優(yōu)化問題。由于計(jì)算方法和決策方式直接決定了生產(chǎn)系統(tǒng)的效率，各領(lǐng)域的專家都致力于將約束條件下的復(fù)雜問題進(jìn)行建模，然后設(shè)計(jì)確定性或近似算法來解決它們。對于解空間規(guī)模較小的問題，很多確定性算法就可以高效地給出最優(yōu)解。然而，在實(shí)際情況中，大多數(shù)優(yōu)化問題都是NP難題，隨著問題規(guī)模的增大，傳統(tǒng)確定性算法的搜索時(shí)間呈指數(shù)增長，這就意味著沒有一個(gè)確定性算法能在多項(xiàng)式時(shí)間內(nèi)找到最優(yōu)解。在這種情況下，以遺傳算法（GA）、模擬退火法（SAA）、蟻群算法（ACO）、粒子群算法（PSO）等為典型代表的智能優(yōu)化算法，為大規(guī)模NP難題的解決帶來了新的思路。

智能優(yōu)化方法是由多個(gè)相對獨(dú)立的技術(shù)領(lǐng)域融合發(fā)展而來，它已成為優(yōu)化領(lǐng)域和人工智能領(lǐng)域的主要研究方向之一。當(dāng)前的主流智能優(yōu)化算法都是基于種群迭代模式，它們產(chǎn)生包含一組個(gè)體的初始種群，在每一代中保持解空間的優(yōu)良信息，并通過迭代步步趨近較好位置。這一類算法獨(dú)立于特定問題，可以廣泛應(yīng)用于傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜優(yōu)化問題，并具有一些共同特征：

1）所有操作作用于每一代中的當(dāng)前個(gè)體；

2）搜索機(jī)制是基于迭代演進(jìn)的；

3）可以通過多種群機(jī)制實(shí)現(xiàn)并行優(yōu)化；

4）多數(shù)情況下可以給出較為滿意的近優(yōu)解，而不保證能得到全局最優(yōu)解；

5）算法尋優(yōu)具有一定的隨機(jī)性，不能保證高效搜索到近優(yōu)解。

智能優(yōu)化方法的一般性過程如下：首先，根據(jù)問題描述、問題特性、約束條件等信息，設(shè)計(jì)編碼方式。編碼方式是問題變量的映射，它直接決定了算法的演進(jìn)速度。當(dāng)選擇了合適的編碼機(jī)制后，算法進(jìn)行初始化，根據(jù)問題變量的定義生成包含一定數(shù)目個(gè)體的種群。每個(gè)個(gè)體是在定義范圍內(nèi)隨機(jī)產(chǎn)生的，其適應(yīng)度值根據(jù)問題的目標(biāo)函數(shù)（適應(yīng)度函數(shù)）計(jì)算。在迭代過程中，各個(gè)演進(jìn)操作的組合起到了主要作用，比如遺傳算法中的選擇操作、交叉操作、變異操作，蟻群算法中的路徑選擇和信息素更新操作。不同的操作在算法中具有不同的影響，因此不同操作的組合在解決問題時(shí)往往具有不同的效果。經(jīng)過幾步操作后，種群中的一部分或全部個(gè)體發(fā)生了改變，通過新個(gè)體的解碼即可產(chǎn)生一組新解，再由適應(yīng)度函數(shù)評估出種群中的最優(yōu)合體和最差個(gè)體。其次，采用隨機(jī)迭代、精英代替、合并最優(yōu)個(gè)體等策略更新整個(gè)種群，并引發(fā)新一輪迭代。當(dāng)?shù)螖?shù)達(dá)到最大值或找到令人滿意的近優(yōu)解或最優(yōu)解時(shí)，算法跳出循環(huán)迭代并輸出全局最優(yōu)解。

在這種演進(jìn)模式下，問題變量和目標(biāo)值反映在編碼方式和適應(yīng)度函數(shù)上，而約束條件則往往以懲罰函數(shù)的形式體現(xiàn)在適應(yīng)度函數(shù)上，或以定義取值邊界的形式體現(xiàn)在編碼過程中。算法中的操作獨(dú)立于特定問題，并且易于實(shí)現(xiàn)。這種統(tǒng)一的迭代過程使得智能優(yōu)化方法的設(shè)計(jì)、改進(jìn)和混合研究變得更容易、更直觀、更靈活，并且基于迭代的多點(diǎn)優(yōu)化搜索機(jī)制，使得智能優(yōu)化方法可以高效地解決NP難題，避免組合爆炸效應(yīng)。當(dāng)然，并不是所有的操作都可以任意組合成高效算法。由于演進(jìn)過程具有隨機(jī)性，各操作在探索和開發(fā)能力上具有不同的特點(diǎn)和缺陷，很多智能優(yōu)化方法具有早熟收斂、易陷入局優(yōu)解等缺點(diǎn)。因此，不同領(lǐng)域的研究者在編碼方式、演進(jìn)操作、算法融合等方面進(jìn)行著不斷探索，以期以較小的迭代次數(shù)和種群規(guī)模獲得更好的解。

1.3.2 智能優(yōu)化方法的分類

近年來，包含不同演進(jìn)機(jī)制的多種智能優(yōu)化方法得到空前發(fā)展，研究者針對特定問題的不同背景和目標(biāo)，在算法設(shè)計(jì)方面做了大量工作，并涌現(xiàn)出很多研究成果。按照不同的標(biāo)準(zhǔn)，智能優(yōu)化方法可以被分為多個(gè)類別。根據(jù)研究重點(diǎn)的不同，智能優(yōu)化算法方面的主流工作大體可以分為四類：①算法革新；②算法改進(jìn)；③算法融合；④算法應(yīng)用。另外，根據(jù)不同算法的搜索機(jī)制，基本的智能優(yōu)化方法又可以分為三類：①演進(jìn)學(xué)習(xí)算法；②鄰域搜索算法；③群智能算法。

1）演進(jìn)學(xué)習(xí)算法包括遺傳算法、演進(jìn)規(guī)劃、人工免疫算法、DNA計(jì)算等，它們來源于自然的學(xué)習(xí)演進(jìn)機(jī)制。種群中的個(gè)體根據(jù)不同的啟發(fā)式操作，通過每一代內(nèi)個(gè)體間的相互學(xué)習(xí)進(jìn)行更新。在這一類方法中，應(yīng)用最廣泛的代表是遺傳算法和人工免疫算法。

2）鄰域搜索算法包括模擬退火法、禁忌搜索和可變鄰域搜索。這一類算法中的鄰域搜索一般通過隨機(jī)或規(guī)則的步進(jìn)變化實(shí)現(xiàn)。在搜索過程中，附加的控制參數(shù)或個(gè)體接受規(guī)則逐漸變化以達(dá)到收斂。因此，這類算法的主要特征是個(gè)體的獨(dú)立局域搜索，目前，它們主要作為其他算法的改進(jìn)策略應(yīng)用。

3）群智能算法包括蟻群算法、粒子群算法、人工魚群算法等，它們通過模擬群居動物（如蟻群、蜜蜂、鳥群等）的自組織行為進(jìn)行算法設(shè)計(jì)。通常它們通過傳播從個(gè)體中獲得的社會信息實(shí)現(xiàn)組織結(jié)構(gòu)的優(yōu)化，目前最流行的群智能算法是蟻群算法和粒子群算法。

另外，一些具有不同特征的算法改進(jìn)策略相繼提出。研究者在算法收斂性、探索和開發(fā)能力等方面做了相關(guān)工作，以期指導(dǎo)算法找到更好的近優(yōu)解。根據(jù)策略的不同功效，也可以將策略分為三類：自適應(yīng)改進(jìn)、開發(fā)改進(jìn)和探索改進(jìn)。

自適應(yīng)改進(jìn)旨在平衡前期的搜索廣度和后期的挖掘深度。參數(shù)自適應(yīng)改進(jìn)、模糊自適應(yīng)改進(jìn)和基于目標(biāo)的自適應(yīng)改進(jìn)是這類策略的典型代表。開發(fā)改進(jìn)主要提高算法的挖掘能力，主要表現(xiàn)為優(yōu)化搜索方向和小范圍遍歷。探索改進(jìn)又稱為全局搜索改進(jìn)，它主要用來增加算法搜索到的種群多樣性，防止算法陷入局部最優(yōu)解。混沌策略、多種變異策略是這一類改進(jìn)的典型代表。

1.3.3 典型的智能優(yōu)化方法

1.遺傳算法

遺傳算法（Genetic Algorithm，GA）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法。遺傳算法是從代表問題潛在解集的一個(gè)種群開始的，一個(gè)種群是由經(jīng)過編碼的一定數(shù)目的個(gè)體（染色體）組成。一個(gè)個(gè)體實(shí)際上是一個(gè)可能解的編碼映射。染色體作為遺傳物質(zhì)的主要載體，即多個(gè)基因的集合，其內(nèi)部表現(xiàn)（即基因型）是某種基因組合，它決定了個(gè)體形狀的外部表現(xiàn)，實(shí)際代表了問題變量的組合方式。因此，在一開始需要實(shí)現(xiàn)從表現(xiàn)型到基因型的映射，即編碼工作。由于仿照基因編碼工作很復(fù)雜，往往進(jìn)行簡化，如二進(jìn)制編碼，初代種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個(gè)體的適應(yīng)度大小選擇個(gè)體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉（crossover）和變異，產(chǎn)生出代表新的解集的種群。這個(gè)過程將導(dǎo)致種群像自然進(jìn)化一樣，后代種群比前代更加適應(yīng)于環(huán)境，末代種群中的最優(yōu)個(gè)體經(jīng)過解碼，可以作為問題近似最優(yōu)解。

遺傳算法的基本運(yùn)算過程如下：

1）初始化：設(shè)進(jìn)化代數(shù)計(jì)數(shù)器位t，初始時(shí)刻t=0；設(shè)置最大進(jìn)化代數(shù)T；設(shè)置種群規(guī)模為M，隨機(jī)生成M個(gè)個(gè)體作為初始群體P（0）。

2）個(gè)體評價(jià)：根據(jù)適應(yīng)度函數(shù)（目標(biāo)函數(shù)或其變體）計(jì)算種群P（t）中每個(gè)個(gè)體的適應(yīng)度值，用于衡量個(gè)體的優(yōu)劣程度。

3）選擇運(yùn)算：采用合適的選擇算子作用于種群。其目的是把優(yōu)質(zhì)的個(gè)體選擇出來，使其有機(jī)會作為父體，把優(yōu)良的全部或部分基因遺傳到下一代。選擇操作包括輪盤賭選擇策略、精英選擇策略等，它是建立在種群中個(gè)體的適應(yīng)度評估基礎(chǔ)上的。

4）交叉運(yùn)算：設(shè)置交叉概率，產(chǎn)生隨機(jī)數(shù)，當(dāng)時(shí)以某種方式交換兩個(gè)父體的部分基因，產(chǎn)生新個(gè)體進(jìn)入下一代種群。交叉操作是算法迭代進(jìn)化的關(guān)鍵步驟，包括單點(diǎn)交叉、多點(diǎn)交叉等多種方式，其作用是繼承優(yōu)良個(gè)體的部分基因，并產(chǎn)生新個(gè)體，增加種群的多樣性。

5）變異運(yùn)算：設(shè)置變異概率，產(chǎn)生隨機(jī)數(shù)，以某種方式將當(dāng)前個(gè)體的某一位基因變成其等位基因。變異操作旨在通過基因突變的方式發(fā)現(xiàn)更優(yōu)解，增加了算法跳出局部最優(yōu)解并向更優(yōu)區(qū)域搜索的可能性。

群體P（t）經(jīng)過選擇、交叉、變異運(yùn)算之后得到下一代群體P（t+1）。

6）終止條件判斷：若t=T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算，否則跳轉(zhuǎn)步驟2），進(jìn)行新一輪迭代。

2.模擬退火法

模擬退火法來自冶金學(xué)的專有名詞退火。退火是將材料加熱后再經(jīng)特定速率冷卻，目的是增大晶粒的體積，并且減少晶格中的缺陷。材料中的原子原來會停留在使內(nèi)能有局部最小值的位置，加熱使能量變大，原子會離開原來位置，而隨機(jī)在其他位置中移動。退火冷卻時(shí)速度較慢，使得原子有較多可能可以找到內(nèi)能比原先更低的位置。

模擬退火的原理也和金屬退火的原理近似：將熱力學(xué)的理論套用到統(tǒng)計(jì)學(xué)上，將搜尋空間內(nèi)每一點(diǎn)想像為空氣內(nèi)的分子；分子的能量，就是它本身的動能；而搜尋空間內(nèi)的每一點(diǎn)，也像空氣分子一樣帶有“能量”，以表示該點(diǎn)對命題的合適程度。算法先以搜尋空間內(nèi)一個(gè)任意點(diǎn)作起始：每一步先選擇一個(gè)“鄰居”，然后再計(jì)算從現(xiàn)有位置到達(dá)“鄰居”的概率。

模擬退火的基本思想：

1）初始化：初始溫度T（充分大），初始解狀態(tài)S（是算法迭代的起點(diǎn)），每個(gè)T值的迭代次數(shù)L。

2）對k=1，…，L，做第3）至第6）步：

3）產(chǎn)生新解S′。

4）計(jì)算增量Δt′=C（S）-C（S′），其中C（S′）為評價(jià)函數(shù)。

5）若Δt′<0，則接受S′作為新的當(dāng)前解，否則以概率exp（-Δt′/T）接受S′作為新的當(dāng)前解。

6）如果滿足終止條件，則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序，當(dāng)連續(xù)若干個(gè)新解都沒有被接受時(shí)，終止算法。

7）T逐漸減少，且T→0，然后轉(zhuǎn)第2）步。

模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟：

1）由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對構(gòu)成當(dāng)前解的全部或部分元素進(jìn)行置換、互換等，產(chǎn)生新解的變換方法決定當(dāng)前新解的鄰域結(jié)構(gòu)。

2）計(jì)算與新解所對應(yīng)的目標(biāo)函數(shù)差。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。對大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。

3）判斷新解是否被接受，判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropolis準(zhǔn)則：若Δt′<0，則接受S′作為新的當(dāng)前解S，否則以概率exp（-Δt′/T）接受S′作為新的當(dāng)前解S。

4）當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代。可在此基礎(chǔ)上開始下一輪試驗(yàn)。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。

模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S（是算法迭代的起點(diǎn)）無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種依概率收斂于全局最優(yōu)解的全局優(yōu)化算法。另外，模擬退火算法具有并行性。

3.粒子群算法

粒子群（Particle Swarm Optimization，PSO）算法是基于種群的進(jìn)化計(jì)算方法，它的靈感來自于鳥群和魚群等生物體的行為。在PSO算法中，每個(gè)元素稱作一個(gè)粒子，每個(gè)粒子根據(jù)個(gè)體經(jīng)驗(yàn)和鄰域經(jīng)驗(yàn)或種群經(jīng)驗(yàn)持續(xù)更新自己的速度向量，以此在多維搜索空間中移向有利位置。在搜索過程中，個(gè)體間共享社會信息，指導(dǎo)搜索方向朝最優(yōu)解的位置趨近。總體來講，PSO算法自適應(yīng)考慮全局和局部探索能力，是具有較好的平衡機(jī)制的簡單啟發(fā)式算法。與遺傳算法相比，可以更迅速地收斂到最優(yōu)解。與梯度下降法、擬牛頓法等經(jīng)典優(yōu)化算法不同，PSO算法不需要優(yōu)化問題是可微的，并且可應(yīng)用于非正規(guī)的、含噪聲的優(yōu)化問題。由于思想簡單、易于實(shí)現(xiàn)、收斂迅速，PSO算法被成功應(yīng)用于各個(gè)領(lǐng)域，如神經(jīng)網(wǎng)絡(luò)訓(xùn)練、任務(wù)分配、排序問題等。

在PSO算法中，隨機(jī)產(chǎn)生初始種群并初始化參數(shù)。在評價(jià)適應(yīng)度值后，PSO算法按如下步驟迭代：

1）如果粒子發(fā)現(xiàn)了更好值，則更新個(gè)體最優(yōu)值（每個(gè)個(gè)體到目前為止找到的最好值）；

2）按照下式，根據(jù)個(gè)體最優(yōu)值和全局最優(yōu)值更新所有粒子的速度，并據(jù)此更新每個(gè)粒子的位置；

式中，代表了粒子i在第t輪迭代中第j維速度（j=1，…，n）。代表了粒子i在第t輪迭代中第j維位置。c₁和c₂是正加速參數(shù)，分別稱為認(rèn)知參數(shù)和社會參數(shù)，γ₁和γ₂是（0，1）之間的隨機(jī)數(shù)。ω是慣性權(quán)重，按照下式更新：

ω^t=ω^t-1×α

式中，α是一個(gè)縮減因數(shù)。ω的值越大，先前速度對于當(dāng)前速度的影響越大。

3）計(jì)算每個(gè)解的適應(yīng)度值，重復(fù)迭代過程，直到達(dá)到最大迭代次數(shù)。