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

智能優(yōu)化算法

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

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

第三章遺傳算法基本理論

第四章蟻群算法基本理論

第五章蜂群算法基本理論

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

第七章魚群算法基本理論

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

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

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

1.1.3優(yōu)化的分類

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

1.1.5

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

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

1.3.1群體智能的概念1.3.2群體智能的分類

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

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

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

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

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

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

幾個定義

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

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

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

①對于任意，有，當且僅當，；

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

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

p-范數(shù)：對于任意，，定義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)化的分類

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

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

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

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

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

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

按照最優(yōu)化解是否變化分類?靜態(tài)最優(yōu)化問題：最優(yōu)化問題的解不隨時間而變。?動態(tài)最優(yōu)化問題：最優(yōu)化問題的解隨時間而變化。

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

一般思路

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

①給定初始點，即令；

②確定處的下降方向，使得點沿方向移動時函數(shù)值有所下降；

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

影響算法收斂的條件

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

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

?

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

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

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

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

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

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

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

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

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

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

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

的最佳值

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

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

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

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

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

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

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

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

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