第1章優(yōu)化算法基本理論

智能優(yōu)化算法

第一章優(yōu)化算法基本理論

第二章神經(jīng)網(wǎng)絡(luò)基本理論

第三章遺傳算法基本理論

第四章蟻群算法基本理論

第五章蜂群算法基本理論

第六章粒子群算法基本理論

第七章魚(yú)群算法基本理論

第八章其他群智能優(yōu)化算法課程結(jié)構(gòu)及學(xué)時(shí)安排1.1

優(yōu)化的概念與方法

1.1.1優(yōu)化的概念1.1.2優(yōu)化的一般數(shù)學(xué)模型

1.1.3優(yōu)化的分類(lèi)

1.1.4優(yōu)化問(wèn)題的求解方法

1.1.5

常用的無(wú)約束優(yōu)化方法1.2智能優(yōu)化的概念及分類(lèi)

1.2.1智能優(yōu)化的概念1.2.2智能優(yōu)化的分類(lèi)1.3群體智能的概念及分類(lèi)

1.3.1群體智能的概念1.3.2群體智能的分類(lèi)

1.3.3群體智能的特點(diǎn)1.3.2群體智能算法的一般流程第1章優(yōu)化算法基本理論1.1優(yōu)化的概念及方法

1.1.1優(yōu)化的概念優(yōu)化、最優(yōu)化均是一個(gè)術(shù)語(yǔ)，是指關(guān)于求解一個(gè)問(wèn)題的“最優(yōu)”解的計(jì)算科學(xué)的一個(gè)分支，也就是從各種可能方案中選取一個(gè)最好的，以達(dá)到最優(yōu)目標(biāo)。從數(shù)學(xué)意義上說(shuō)，最優(yōu)化方法是一種求極值的方法，即在一組約束為等式或不等式的條件下，使系統(tǒng)的目標(biāo)函數(shù)達(dá)到極值，即最大值或最小值。從經(jīng)濟(jì)意義上說(shuō)，是在一定的人力、物力和財(cái)力資源條件下，使經(jīng)濟(jì)效果達(dá)到最大（如產(chǎn)值、利潤(rùn)），或者在完成規(guī)定的生產(chǎn)或經(jīng)濟(jì)任務(wù)下，使投入的人力、物力和財(cái)力等資源為最少。1.1優(yōu)化的概念及方法

優(yōu)化技術(shù)是一種以數(shù)學(xué)為基礎(chǔ)、用于求解各種工程問(wèn)題優(yōu)化解的應(yīng)用技術(shù)。1.1.2優(yōu)化的一般數(shù)學(xué)模型

數(shù)學(xué)模型

s.t.式中，，即為n維矢量，也稱(chēng)為決策變量；、和均為的函數(shù)，稱(chēng)為目標(biāo)函數(shù)，稱(chēng)為等式約束函數(shù)，稱(chēng)為不等式約束函數(shù)；s.t.為英文subjectto的縮寫(xiě)，表示“受限制于”。對(duì)于求目標(biāo)函數(shù)極大值的問(wèn)題，可以轉(zhuǎn)化為求極小值。

1.1優(yōu)化的概念及方法

幾個(gè)定義

?可行解：又稱(chēng)為可行點(diǎn)或容許解，是指滿足約束條件的。?可行域：又稱(chēng)為容許集，是指全體可行解構(gòu)成的集合，即若和為連續(xù)函數(shù)，則D是閉集。?最優(yōu)解：一般分為整體最優(yōu)解（總體最優(yōu)解）、嚴(yán)格整體最優(yōu)解、局部最優(yōu)解、嚴(yán)格局部最優(yōu)解。?整體最優(yōu)解：若，對(duì)于一切恒有，則稱(chēng)為最優(yōu)問(wèn)題的整體最優(yōu)解。1.1優(yōu)化的概念及方法1.1優(yōu)化的概念及方法

?嚴(yán)格整體最優(yōu)解：若，對(duì)于一切和恒有，則稱(chēng)為最優(yōu)問(wèn)題的嚴(yán)格整體最優(yōu)解。?局部最優(yōu)解：若，存在的某鄰域（），使得對(duì)于一切，恒有，則稱(chēng)為最優(yōu)問(wèn)題的局部整體最優(yōu)解。?嚴(yán)格局部最優(yōu)解：若，存在的某鄰域（），使得對(duì)于一切，恒有，則稱(chēng)為最優(yōu)問(wèn)題的嚴(yán)格局部整體最優(yōu)解。?最優(yōu)值：最優(yōu)解對(duì)應(yīng)的目標(biāo)函數(shù)值稱(chēng)為最優(yōu)值。

?范數(shù)：在n維線性空間中，定義實(shí)函數(shù)，使其滿足以下三個(gè)條件：

①對(duì)于任意，有，當(dāng)且僅當(dāng)，；

②對(duì)于任意及實(shí)數(shù)，有；

③對(duì)于任意，有。則稱(chēng)函數(shù)為上的向量范數(shù)。?

p-范數(shù)：對(duì)于任意，，定義p-范數(shù)為1.1優(yōu)化的概念及方法

?∞-范數(shù)：

?2-范數(shù)：，通常記作

整體最優(yōu)解與局部最優(yōu)解的關(guān)系整體最優(yōu)解一定是局部最優(yōu)解，而局部最優(yōu)解不一定是整體最優(yōu)解。1.1優(yōu)化的概念及方法1.1.3優(yōu)化的分類(lèi)

根據(jù)約束條件分類(lèi)?無(wú)約束最優(yōu)化問(wèn)題：沒(méi)有約束條件限制的最優(yōu)化問(wèn)題。?約束最優(yōu)化問(wèn)題：有約束條件的最優(yōu)化問(wèn)題。約束最優(yōu)化問(wèn)題又可分為

?等式約束最優(yōu)化問(wèn)題：

?不等式約束最優(yōu)化問(wèn)題：?混合約束最優(yōu)化問(wèn)題：既有等式約束，又有不等式約束最優(yōu)化問(wèn)題。即1.1優(yōu)化的概念及方法1.1優(yōu)化的概念及方法根據(jù)決策變量取值的狀態(tài)分類(lèi)?連續(xù)最優(yōu)化問(wèn)題：決策變量取值是連續(xù)的優(yōu)化問(wèn)題。?離散最優(yōu)化問(wèn)題：決策變量取值是離散的優(yōu)化問(wèn)題。

根據(jù)決策變量取值的性質(zhì)分類(lèi)?確定性最優(yōu)化問(wèn)題：每個(gè)決策變量取值是確定的。?隨機(jī)性最優(yōu)化問(wèn)題：某些決策變量取值是不確定的，但知道決策變量取某值而服從一定的概率分布。

按照目標(biāo)函數(shù)和約束函數(shù)的勞累性分類(lèi)?線性最優(yōu)化問(wèn)題：目標(biāo)函數(shù)和所有約束條件中的函數(shù)都是決策變量的線性函數(shù)，即、和均為的線性函數(shù)。1.1優(yōu)化的概念及方法

?非線性最優(yōu)化問(wèn)題：目標(biāo)函數(shù)或約束條件中至少有一個(gè)是決策變量的非線性函數(shù)，即、和中至少有一個(gè)是的非線性函數(shù)。

按照最優(yōu)化解是否變化分類(lèi)?靜態(tài)最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題的解不隨時(shí)間而變。?動(dòng)態(tài)最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題的解隨時(shí)間而變化。

按照目標(biāo)函數(shù)的個(gè)數(shù)分類(lèi)?單目標(biāo)最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題中只有一個(gè)目標(biāo)函數(shù)。?多目標(biāo)最優(yōu)化問(wèn)題：最優(yōu)化問(wèn)題中含有多個(gè)目標(biāo)函數(shù)。1.1.4優(yōu)化問(wèn)題的求解方法

一般思路

最優(yōu)化問(wèn)題的一般求解方法是迭代算法。首先給定一個(gè)初始可行點(diǎn)（即初始值），然后從此點(diǎn)出發(fā)，依次產(chǎn)生一個(gè)可行點(diǎn)列，記作，使得某個(gè)恰好是問(wèn)題的一個(gè)最優(yōu)解，或者說(shuō)該點(diǎn)列收斂到問(wèn)題的一個(gè)最優(yōu)解。一般步驟包括：

①給定初始點(diǎn)，即令；

②確定處的下降方向，使得點(diǎn)沿方向移動(dòng)時(shí)函數(shù)值有所下降；

③確定步長(zhǎng)，令使得；1.1優(yōu)化的概念及方法1.1優(yōu)化的概念及方法④若滿足某種終止準(zhǔn)則，則停止迭代，以為近似最優(yōu)解。否則令轉(zhuǎn)①。

影響算法收斂的條件

?如果某算法構(gòu)造出的點(diǎn)列能夠在有限步之內(nèi)得到最優(yōu)化問(wèn)題的最優(yōu)解，或者說(shuō)點(diǎn)列有極限點(diǎn)，且其極限點(diǎn)就是最優(yōu)解，則稱(chēng)算法是收斂的。算法收斂的影響因素較多，包括初始點(diǎn)的選取、下降方向的確定、迭代步長(zhǎng)的選擇以及目標(biāo)函數(shù)自身的影響。除要求收斂外，一般還要求收斂速度要快。?收斂：設(shè)序列，對(duì)于，存在正整數(shù)N，當(dāng)時(shí)，有，則稱(chēng)收斂于。1.1優(yōu)化的概念及方法

?線性收斂：設(shè)序列收斂于，且若，則稱(chēng)序列為線性收斂，為收斂比；若，則稱(chēng)序列為超線性收斂；若，則稱(chēng)序列為次線性收斂。

?

p階收斂：設(shè)序列收斂于，若對(duì)于某個(gè)實(shí)數(shù)，有則稱(chēng)序列為p階收斂，一般情況下，稱(chēng)為二階收斂。1.1優(yōu)化的概念及方法常用的終止準(zhǔn)則

?（，預(yù)先給定）或；?，；?；

?上述三種終止準(zhǔn)則的組合。1.1.5常用的無(wú)約束優(yōu)化方法

常用的無(wú)約束最優(yōu)化方法包括最速下降法和牛頓法等。

最速下降法最速下降法又稱(chēng)為梯度法、梯度下降法，是1847年由著名數(shù)學(xué)家Cauchy推導(dǎo)而出。根據(jù)泰勒公式得由此可見(jiàn)，當(dāng)時(shí)，，符合迭代要求。1.1優(yōu)化的概念及方法

由于，為和的夾角。故當(dāng)時(shí)，取得極小值，下降最快。一般取，得到即負(fù)梯度方向使目標(biāo)函數(shù)下降最快，稱(chēng)為最速下降法。

牛頓（Newton）法牛頓（Newton）法最初由艾薩克·牛頓（IsaacNewton，1643年1月4日~1727年3月31日）在《流數(shù)法》（MethodofFluxions）首次提出（1671年完成，在牛頓死后的1736年公開(kāi)發(fā)表），同時(shí)約瑟夫·拉弗森（JosephRaphson，1648年~1715年）也曾于1690年在AnalysisAequationum中提出此方法。故有時(shí)稱(chēng)為牛頓-拉弗森法。1.1優(yōu)化的概念及方法

設(shè)二階連續(xù)可導(dǎo)，對(duì)在處進(jìn)行泰勒展開(kāi)，得設(shè)為的近似最優(yōu)解，得到即得到牛頓迭代公式為1.1優(yōu)化的概念及方法

最速下降法的應(yīng)用以最小均方算法（簡(jiǎn)稱(chēng)LMS）為例。如圖1-1為一橫向?yàn)V波器圖中，為輸入矢量，為抽頭系數(shù)矢量。1.1優(yōu)化的概念及方法圖1-1橫向?yàn)V波器結(jié)構(gòu)圖

設(shè)為系統(tǒng)的期望響應(yīng)信號(hào)，為濾波器實(shí)際輸出相對(duì)于的誤差，即按照最小均方誤差準(zhǔn)則（簡(jiǎn)稱(chēng)MMSE），定義濾波器的輸出與期望響應(yīng)之間的均方誤差（簡(jiǎn)稱(chēng)MSE）為代價(jià)函數(shù)，即定義為濾波器輸入序列的自相關(guān)矩陣，是一個(gè)L×L階方陣；為互相關(guān)矩陣。于是，上式可表示為1.1優(yōu)化的概念及方法

根據(jù)最小均方誤差準(zhǔn)則，使上式對(duì)W的梯度（即偏導(dǎo)）為零，即則可得到

的最佳值

應(yīng)滿足方程式中，稱(chēng)為橫向?yàn)V波器的維納解，即最佳濾波器系數(shù)矢量。由于均方誤差函數(shù)（即代價(jià)函數(shù)）是濾波器系數(shù)的二次方程，故形成了一個(gè)多維的超拋物曲面，好象一個(gè)碗狀曲面且只有唯一的碗底最小點(diǎn)，通常稱(chēng)為濾波器的誤差性能曲面。當(dāng)給定初始值時(shí)，均方誤差就位于誤差性能曲面上的某一點(diǎn)，系數(shù)的自適應(yīng)調(diào)節(jié)使得均方誤差超碗底的最小點(diǎn)方向移動(dòng)，最終到達(dá)碗底的最小點(diǎn)，實(shí)現(xiàn)了最佳維納濾波。1.1優(yōu)化的概念及方法

在自適應(yīng)算法中，人們提出了不少梯度估計(jì)的方法，其中最著名、應(yīng)用最廣的是B.Widrow提出的LMS算法。其算法的核心思想是用平方誤差代替均方誤差，即代價(jià)函數(shù)變?yōu)楦鶕?jù)最陡下降法得到LMS自適應(yīng)均衡算法公式為式中，為步長(zhǎng)因子。1.1優(yōu)化的概念及方法1.2智能優(yōu)化的概念及方法1.2智能優(yōu)化的概念及方法

1.2.1智能優(yōu)化的概念人工智能（ArtificialIntelligent，簡(jiǎn)稱(chēng)AI）是在計(jì)算機(jī)科學(xué)、控制論、信息論、哲學(xué)、語(yǔ)言學(xué)等多種學(xué)科研究基礎(chǔ)上發(fā)展起來(lái)的一門(mén)綜合性交叉學(xué)科。即人工智能就是用人工的方法在機(jī)器（計(jì)算機(jī)）上實(shí)現(xiàn)的智能，或者說(shuō)是人們使機(jī)器具有類(lèi)似于人的智能。智能優(yōu)化算法（intelligentoptimizationalgorithms）是以模擬物質(zhì)變化過(guò)程或模擬生命體而設(shè)計(jì)的搜索方式為基礎(chǔ)的各類(lèi)算法的總稱(chēng)。有時(shí)也稱(chēng)為啟發(fā)式算法（modernheuristicalgorithms）、仿生算法、演化算法或進(jìn)化算法。1.2智能優(yōu)化的概念及方法

智能優(yōu)化算法的本質(zhì)都屬于隨機(jī)性算法，最大優(yōu)點(diǎn)是不需要目標(biāo)函數(shù)具有可導(dǎo)性，甚至不需要目標(biāo)函數(shù)有明確的表達(dá)形式，只要知道輸入輸出即可。1.2.2智能優(yōu)化的分類(lèi)兔子理論：為了找出地球上最高的山，一群兔子開(kāi)始想辦法。

兔子朝著比現(xiàn)在高的地方跳去。他們找到了不遠(yuǎn)處的最高山峰。但是這座山不一定是珠穆朗瑪峰。這就是局部搜索，它不能保證局部最優(yōu)值就是全局最優(yōu)值。

兔子喝醉了。他隨機(jī)地跳了很長(zhǎng)時(shí)間。這期間，它可能走向高處，也可能踏入平地。但是，他漸漸清醒了并朝最高方向跳去。這就是模擬退火。1.2智能優(yōu)化的概念及方法兔子們吃了失憶藥片，并被發(fā)射到太空，然后隨機(jī)落到了地球上的某些地方。他們不知道自己的使命是什么。但是，如果你過(guò)幾年就殺死一部分海拔低的兔子，多產(chǎn)的兔子們自己就會(huì)找到珠穆朗瑪峰。這就是遺傳算法。

兔子們知道一個(gè)兔的力量是渺小的。他們互相轉(zhuǎn)告著，哪里的山已經(jīng)找過(guò)，并且找過(guò)的每一座山他們都留下一只兔子做記號(hào)。他們制定了下一步去哪里尋找的策略。這就是禁忌搜索。1.3群體智能的概念及方法1.3群體智能的概念及方法

1.3.1群體智能的概念群體智能（SI）簡(jiǎn)稱(chēng)群智能，指的是簡(jiǎn)單智能的個(gè)體通過(guò)合作表現(xiàn)出復(fù)雜智能行為的特性，也就是無(wú)智能的主體通過(guò)合作表現(xiàn)出智能行為的特性。其本質(zhì)上是一種概率搜索，不需要問(wèn)題的梯度信息。群體智能算法的基本思想是模擬自然界生物的群體行為來(lái)構(gòu)造隨機(jī)優(yōu)化算法。將搜索和優(yōu)化過(guò)程模擬成個(gè)體的進(jìn)化或覓食過(guò)程，用搜索空間中的點(diǎn)模擬自然界中的個(gè)體，將求解問(wèn)題的目標(biāo)函數(shù)度量成個(gè)體對(duì)環(huán)境的適應(yīng)能力，將個(gè)體的優(yōu)勝劣汰過(guò)程或覓食過(guò)程類(lèi)比為搜索和優(yōu)化過(guò)程中用好的可行解取代較差可行解的迭代過(guò)程。1.2智能優(yōu)化的概念及方法

因此，形成一種以“生成+檢驗(yàn)”特征的迭代搜索算法，是一種求解極值問(wèn)題的自適應(yīng)人工智能技術(shù)。也可以說(shuō)，群智能是一種自下而上的優(yōu)化方法，即首先設(shè)計(jì)單個(gè)實(shí)體的感知、行為機(jī)制，然后將一個(gè)或一群實(shí)體置于環(huán)境中，讓它們?cè)谂c環(huán)境的交互作用中解決問(wèn)題。1.3.2群體智能的分類(lèi)由于群體智能是由社會(huì)性動(dòng)物的自組織行為產(chǎn)生的，因此新算法不斷涌現(xiàn)。根據(jù)目前的有關(guān)報(bào)道，主要有粒子群算法、蟻群算法、魚(yú)群算法、蜂群算法、蛙跳算法、布谷鳥(niǎo)算法、螢火蟲(chóng)算法、蝙蝠算法、磷蝦群算法、細(xì)菌覓食算法、煙花算法、頭腦風(fēng)暴算法、智能水滴算法、磁鐵算法等等。1.2智能優(yōu)化的概念及方法1.3