生物啟發(fā)式方法

生物啟發(fā)式優(yōu)化方法

及其在管理中的應(yīng)用牛奔Email:drniuben@報(bào)告內(nèi)容啟發(fā)式優(yōu)化方法研究背景生物啟發(fā)式優(yōu)化方法群體智能優(yōu)化方法（SI）SI算法在管理中的應(yīng)用實(shí)例研究2報(bào)告內(nèi)容1啟發(fā)式計(jì)算方法研究背景2生物啟發(fā)式計(jì)算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實(shí)例研究3最優(yōu)化問題模型啟發(fā)式計(jì)算方法背景全局最優(yōu)與局部最優(yōu)實(shí)際生活中的優(yōu)化問題4經(jīng)典的計(jì)算方法17世紀(jì)Newtown微積分1847年Cauchy最速下降法1947年Dantzig單純形方法1939年Kantorovich下料問題和運(yùn)輸問題問題求解5啟發(fā)式計(jì)算方法【定義1-1】啟發(fā)式算法是一種基于直觀或經(jīng)驗(yàn)構(gòu)造的算法，在可接受的耗費(fèi)（指計(jì)算時(shí)間、占用空間等）下給出待解決優(yōu)化問題每一實(shí)例的一個(gè)可行解，該可行解與最優(yōu)解的偏離程度未必可事先估計(jì)?！径x1-2】啟發(fā)式算法是一種技術(shù)，該技術(shù)使得能在可接受的計(jì)算費(fèi)用內(nèi)去尋找盡可能好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法描述所得解與最優(yōu)解的近似程度。經(jīng)典的啟發(fā)式方法基本原理:根據(jù)問題的部分已知信息來啟發(fā)式地探索該問題的解決方案，在探索解決方案的過程中將發(fā)現(xiàn)的有關(guān)信息記錄下來，不斷積累和分析，并根據(jù)越來越豐富的已知信息來指導(dǎo)下一步的動(dòng)作并修正以前的步驟，從而獲得在整體上較好的解決方案。6啟發(fā)式計(jì)算方法分類物理啟發(fā)式模擬退火算法（模擬固體熔化狀態(tài)下由逐漸冷卻至最終達(dá)到結(jié)晶狀態(tài)的物理過程）量子計(jì)算（模擬量子態(tài)的疊加性和相干性以及量子比特之間的糾纏性）社會(huì)與文化啟發(fā)文化算法（模擬人類社會(huì)的演化過程）人口遷移算法（模擬人口流動(dòng)與人口遷移）7報(bào)告內(nèi)容1啟發(fā)式計(jì)算方法研究背景2生物啟發(fā)式計(jì)算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實(shí)例研究8生物啟發(fā)式優(yōu)化方法遺傳算法神經(jīng)網(wǎng)絡(luò)模糊邏輯。。。。。生物啟發(fā)式計(jì)算是指以生物界的各種自然現(xiàn)象或過程為靈感，而提出的一系列啟發(fā)式智能計(jì)算方法。遺傳算法進(jìn)化過程優(yōu)化過程生物進(jìn)化過程是一個(gè)自然，并行，穩(wěn)健的優(yōu)化過程，這一優(yōu)化過程的目的在于使生命體達(dá)到適應(yīng)環(huán)境的最佳結(jié)構(gòu)與效果，而生物種群通過”“優(yōu)勝劣汰”及遺傳變異來達(dá)到進(jìn)化（優(yōu)化）目的的。10遺傳算法生物的進(jìn)化機(jī)制自然選擇適應(yīng)環(huán)境的個(gè)體具有更高的生存能力，同時(shí)染色體特征被保留下來雜交隨機(jī)組合來自父代的染色體上的遺傳物質(zhì)，產(chǎn)生不同于它們父代的染色體突變隨機(jī)改變父代的染色體基因結(jié)構(gòu)，產(chǎn)生新染色體11神經(jīng)計(jì)算樹突

突觸

軸突

細(xì)胞體人工神經(jīng)網(wǎng)絡(luò)是由具有適應(yīng)性的簡(jiǎn)單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對(duì)真實(shí)世界物體所作出的交互反應(yīng)。12神經(jīng)計(jì)算

人工神經(jīng)網(wǎng)絡(luò)（ArtificialNeuralNetworks,ANN），一種模擬動(dòng)物神經(jīng)網(wǎng)絡(luò)行為特征，進(jìn)行分布式并行信息處理的算法數(shù)學(xué)模型。這種網(wǎng)絡(luò)依靠系統(tǒng)的復(fù)雜程度，通過調(diào)整內(nèi)部大量節(jié)點(diǎn)之間相互連接的關(guān)系，從而達(dá)到處理信息的目的。人工神經(jīng)網(wǎng)絡(luò)具有自學(xué)習(xí)和自適應(yīng)的能力。INx>T？I1I2I3S13模糊邏輯是

A1集結(jié)器去模糊化y規(guī)則1y是

B1y是

B2y是

Br是

A2是

Ar規(guī)則2規(guī)則r模糊推理系統(tǒng)是建立在模糊集合理論、模糊if-then規(guī)則和模糊推理等概念基礎(chǔ)上的先進(jìn)的計(jì)算框架。模糊推理系統(tǒng)的基本結(jié)構(gòu)由三個(gè)重要部件組成：一個(gè)規(guī)則庫，包含一系列模糊規(guī)則；一個(gè)數(shù)據(jù)庫，定義模糊規(guī)則中用到的隸屬度函數(shù)（MembershipFunctions,MF）；以及一個(gè)推理機(jī)制，按照規(guī)則和所給事實(shí)執(zhí)行推理過程求得合理的輸出或結(jié)論。14其它生物啟發(fā)式計(jì)算技術(shù)進(jìn)化規(guī)劃算法進(jìn)化編程人工免疫系統(tǒng)DNA計(jì)算膜計(jì)算等15報(bào)告內(nèi)容1啟發(fā)式計(jì)算方法研究背景2生物啟發(fā)式計(jì)算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實(shí)例研究16群體智能（SwarmIntelligence）生物學(xué)家研究表明：在這些群居生物中雖然每個(gè)個(gè)體的智能不高，行為簡(jiǎn)單，也不存在集中的指揮，但由這些單個(gè)個(gè)體組成的群體，似乎在某種內(nèi)在規(guī)律的作用下，卻表現(xiàn)出異常復(fù)雜而有序的群體行為。AC18AC19AC20軌跡更新:Visibility:

ij=1/dij螞蟻算法表示軌跡的相對(duì)重要性表示能見度的相對(duì)重要性軌跡的持久性表示第K只螞蟻在本次循環(huán)中留在路徑ij上的信息量21生物社會(huì)學(xué)家E.O.Wilson指出：“至少從理論上，在搜索食物過程中群體中個(gè)體成員可以得益于所有其他成員的發(fā)現(xiàn)和先前的經(jīng)歷。當(dāng)食物源不可預(yù)測(cè)地零星分布時(shí)，這種協(xié)作帶來的優(yōu)勢(shì)是決定性的，遠(yuǎn)大于對(duì)食物的競(jìng)爭(zhēng)帶來的劣勢(shì)?！濒~群覓食模型22避免碰撞速度匹配

中心聚集鳥群的飛行行為23鳥群覓食模型FoodGlobalBestSolutionPastBestSolution24Randomly

searchingfoods社會(huì)型行為的模擬25認(rèn)知行為（CognitionBehavior）先前經(jīng)驗(yàn)26Max26社會(huì)行為（SocialBehavior）Wetendtoadjustourbeliefsandattitudestoconformwiththoseofoursocialpeers.１２５Max人類社會(huì)系統(tǒng)27粒子群算法介紹每個(gè)尋優(yōu)的問題解都被想像成一支鳥，也稱為“Particle”。所有的Particle都有一個(gè)fitnessfunction以判斷目前的位置之好壞，每一個(gè)Particle具有記憶性，能記得所搜尋到最佳位置。每一個(gè)Particle還有一個(gè)速度以決定飛行的距離與方向。28局部最優(yōu)解全局最優(yōu)解運(yùn)動(dòng)向量慣性向量StudyFactorHereIam!Thebest

positionofteamMybestpositionx(t)pgpivPBestgBestx(t+1)速度與位置更新29算法流程Initialization

：將群族做初始化，以隨機(jī)的方式求出每一Particle之初始位置與速度。Evaluation：依據(jù)fitnessfunction計(jì)算出其fitnessvalue以作為判斷每一個(gè)Particle之好壞。FindPbest

：找出每一個(gè)Particle到目前為止的搜尋過程中最佳解，這個(gè)最佳解稱之為Pbest。FindtheGbest：找出所有群體中的最佳解，此最佳解稱之為Gbest。UpdatetheVelocityandposition：

根據(jù)速度與位置公式

更新每一Particle的速度與位置。Termination.返回步驟2繼續(xù)執(zhí)行，直到獲得一個(gè)令人滿意的結(jié)果或符合終止條件為止。30參數(shù)選擇粒子數(shù):一般取20–40.其實(shí)對(duì)于大部分的問題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果,不過對(duì)于比較難的問題或者特定類別的問題,粒子數(shù)可以取到100或200粒子的維數(shù):這是由優(yōu)化問題決定,就是問題解的長度粒子的范圍:由優(yōu)化問題決定,每一維可是設(shè)定不同的范圍Vmax:最大速度,決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離,通常設(shè)定為粒子的范圍寬度學(xué)習(xí)因子:c1和c2通常等于2.不過在文獻(xiàn)中也有其他的取值.但是一般c1等于c2并且范圍在0和4之間中止條件:最大循環(huán)數(shù)以及最小錯(cuò)誤要求.

31PSO與遺傳算法的比較相同點(diǎn)都是基于種群的都需要適應(yīng)度函數(shù).都是隨機(jī)計(jì)算技術(shù)

不能保證100%收斂

不同點(diǎn)PSO沒有交叉變異等進(jìn)化操作.PSO中通過粒子的競(jìng)爭(zhēng)與協(xié)作實(shí)現(xiàn)種群進(jìn)化粒子具有記憶能力

優(yōu)點(diǎn)PSO容易實(shí)現(xiàn)具有較小的調(diào)整參數(shù)收斂速度快、解質(zhì)量高、魯棒性好

32Schwefel'sfunction3