交通運(yùn)輸系統(tǒng)管理02第1頁/共75頁規(guī)范分析認(rèn)識(shí)問題探尋目標(biāo)綜合方案模型化優(yōu)化或仿真系統(tǒng)評(píng)價(jià)決策(分析)NY初步分析規(guī)范分析綜合分析第2頁/共75頁系統(tǒng)模型化通過模型來表述系統(tǒng)的要素和結(jié)構(gòu)，以進(jìn)行后續(xù)的系統(tǒng)分析工作。模型是優(yōu)化仿真的基礎(chǔ)系統(tǒng)評(píng)價(jià)與決策分析也需要模型第3頁/共75頁模型定義模型：現(xiàn)實(shí)系統(tǒng)的替代物，對(duì)現(xiàn)實(shí)系統(tǒng)抽象（或模仿）表達(dá)的結(jié)果；在一定應(yīng)用條件下，應(yīng)能反映系統(tǒng)的組成部分（要素）；組成部分之間的相互關(guān)系；系統(tǒng)中蘊(yùn)含的因果推理關(guān)系。第4頁/共75頁模型的特征是現(xiàn)實(shí)世界（被研究系統(tǒng)）部分的抽象；抽象的出發(fā)點(diǎn)通常是被研究系統(tǒng)的某方面的結(jié)構(gòu)或功能特性；模型的構(gòu)成只考慮（1）與要分析的問題有關(guān)的因素（要素）；（2）有關(guān)因素（要素）之間的相互關(guān)系;（2）與問題有關(guān)的因果關(guān)系;第5頁/共75頁建立模型的一般原則描述現(xiàn)實(shí)（現(xiàn)實(shí)性）高于現(xiàn)實(shí)（減低分析問題的復(fù)雜性）兩者兼顧只包括與研究目的相關(guān)的信息考慮模型的精度（準(zhǔn)確性）要求考慮模型的粒度（分解層次）要求第6頁/共75頁模型化的優(yōu)勢利用模型可以進(jìn)行虛擬試驗(yàn)(推理與計(jì)算)有如下優(yōu)勢：模型簡潔、形式化。（方便）可以通過模擬快速反應(yīng)自然條件下漫長的過程（快速）可以反復(fù)試驗(yàn)（可重復(fù)）試驗(yàn)的成本相對(duì)來說比較低（經(jīng)濟(jì)）特別是，對(duì)某些不允許進(jìn)行試驗(yàn)的系統(tǒng)進(jìn)行模擬研究（突破制約）第7頁/共75頁模型的局限性模型的“局部描述”本質(zhì)決定其局限性只是在某些方面可以用模型分析來替代對(duì)現(xiàn)實(shí)系統(tǒng)的研究但是，模型的有些方面不能替代現(xiàn)實(shí)系統(tǒng)。通過模型推出的理論結(jié)果必須再拿到現(xiàn)實(shí)中去檢驗(yàn)----實(shí)驗(yàn)比如CAD模型第8頁/共75頁構(gòu)造模型的步驟明確目的和要求進(jìn)行一般語言描述抓住主要變量及關(guān)系確定模型結(jié)構(gòu)估計(jì)模型參數(shù)進(jìn)行實(shí)驗(yàn)研究是否與現(xiàn)實(shí)相符？結(jié)束修正模型第9頁/共75頁形象模型物理模型第10頁/共75頁形象模型CAD模型第11頁/共75頁概念模型第12頁/共75頁數(shù)學(xué)模型132023/3/2D=50,000D=100,000D=50,000Cap=60,000Cap=200,000$4$5$2$3$4$5$2$1$2$0問題：如何調(diào)配，運(yùn)輸費(fèi)用最少？第13頁/共75頁數(shù)學(xué)模型線性規(guī)劃模型142023/3/2GoalFunction:minTC=0x(p1,w1)+5x(p1,w2)+4x(p2,w1)+2x(p2,w2)+3x(w1,c1)+4x(w1,c2)+5x(w1,c3)+2x(w2,c1)+1x(w2,c2)+2x(w2,c3)subjectto:x(p2,w1)+x(p2,w2)60000x(p1,w1)+x(p2,w1)=x(w1,c1)+x(w1,c2)+x(w1,c3)x(p1,w2)+x(p2,w2)=x(w2,c1)+x(w2,c2)+x(w2,c3)x(w1,c1)+x(w2,c1)=50000x(w1,c2)+x(w2,c2)=100000x(w1,c3)+x(w2,c3)=50000allvariablesgreaterthanorequaltozero.第14頁/共75頁優(yōu)化物流網(wǎng)絡(luò)最優(yōu)配送策略啟發(fā)式規(guī)則線性規(guī)劃MSSolverFoundationinExcel152023/3/2第15頁/共75頁Heuristicsand

theNeedforExactAlgorithms單一產(chǎn)品兩個(gè)生產(chǎn)廠p1和p2生產(chǎn)廠p1產(chǎn)能為每年200,000件。生產(chǎn)廠p2產(chǎn)能為每年60,000件。兩個(gè)生產(chǎn)廠有同樣的生產(chǎn)成本。有兩個(gè)倉庫分別為w1和w2具有相等的倉庫搬運(yùn)成本

。有三個(gè)區(qū)域市場c1,c2和c3年需求分別為50,000,100,000和50,000件。第16頁/共75頁圖示化模型生產(chǎn)成本相同

倉儲(chǔ)成本相同第17頁/共75頁求解技術(shù)1.準(zhǔn)確算法：尋找最優(yōu)方案2.啟發(fā)式：尋找“滿意”方案，不一定最優(yōu)第18頁/共75頁HeuristicsAlgorithmsAheuristicmethodisparticularlyusedtorapidlycometoasolutionthatishopedtobeclosetothebestpossibleanswer,or'optimalsolution'.Heuristicsare"rulesofthumb",educatedguesses,intuitivejudgmentsorsimplycommonsense.Aheuristicisageneralwayofsolvingaproblem.第19頁/共75頁啟發(fā)式方法1:

將每個(gè)市場區(qū)分配給最近的倉庫。根據(jù)運(yùn)輸成本分配每個(gè)生產(chǎn)廠的供應(yīng)。總成本=$1,120,000第20頁/共75頁啟發(fā)式方法2:

根據(jù)到每個(gè)生產(chǎn)廠到各市場的總運(yùn)輸成本分配P1-W1-C1 $3P1-W2-C1 $7P2-W1-C1 $7P2-W2-C1 $4P1-W1-C2 $4P1-W2-C2 $6P2-W1-C2 $8P2-W2-C2 $3P1-W1-C3 $5P1-W2-C3 $7P2-W1-C3 $9P2-W2-C3 $4C1從W1進(jìn)貨，C2和C3從W2進(jìn)貨第21頁/共75頁啟發(fā)式方法#2:

根據(jù)到每個(gè)市場的總運(yùn)輸成本分配總成本=$920,000P1-W1-C1 $3P1-W2-C1 $7P2-W1-C1 $7P2-W2-C1 $4P1-W1-C2 $4P1-W2-C2 $6P2-W1-C2 $8P2-W2-C2 $3P1-W1-C3 $5P1-W2-C3 $7P2-W1-C3 $9P2-W2-C3 $4第22頁/共75頁運(yùn)籌學(xué)算法 前面描述的問題可以用以下線性規(guī)劃問題表示。

設(shè)如下的運(yùn)輸流量變量x(p1,w1),x(p1,w2),x(p2,w1)和x(p2,w2)表示從不同生產(chǎn)廠到不同倉庫的年流量。x(w1,c1),x(w1,c2),x(w1,c3)代表從倉庫w1到顧客區(qū)c1,c2和c3的年流量。x(w2,c1),x(w2,c2),x(w2,c3)代表從倉庫w2到c1,c2和c3的年流量。第23頁/共75頁最小成本的目標(biāo)函數(shù)為:min0x(p1,w1)+5x(p1,w2)+4x(p2,w1)+2x(p2,w2)+3x(w1,c1)+4x(w1,c2)+5x(w1,c3)+2x(w2,c1)+1x(w2,c2)+2x(w2,c3)滿足以下約束:x(p2,w1)+x(p2,w2)60000x(p1,w1)+x(p2,w1)=x(w1,c1)+x(w1,c2)+x(w1,c3)x(p1,w2)+x(p2,w2)=x(w2,c1)+x(w2,c2)+x(w2,c3)x(w1,c1)+x(w2,c1)=50000x(w1,c2)+x(w2,c2)=100000x(w1,c3)+x(w2,c3)=50000所有的流量變量大于或等于零.精確算法

線性規(guī)劃制造廠P1的產(chǎn)能限制<=20萬？？第24頁/共75頁線性規(guī)劃第25頁/共75頁最優(yōu)模型

線性規(guī)劃第26頁/共75頁EXCELSolver方法TransportationProblem272023/3/2第27頁/共75頁282023/3/2第28頁/共75頁EXCELSolverApproach292023/3/2第29頁/共75頁EXCELSolverApproach302023/3/2第30頁/共75頁312023/3/2第31頁/共75頁EXCELSolverApproachHerewespecify:TheobjectiveistotalcostatcellJ16Thevariables????,j

arelocatedinthetableE16:G17Theconstraintsareformedbycalculatingthesums∑??????,??and∑i????,??andcomparingthosequantitieswiththeavailablesupplyandrequireddemand.Theconditions????,j

≥0arespecifiedintheoptionsdialogwherewecheckthe“assumenon-negative”option.Inadditionwespecifythemodeltobelinearbychecking“assumelinearmodel”.322023/3/2第32頁/共75頁EXCELSolverApproachDisadvantage:Itisdifficulttorecognizethemodel332023/3/2第33頁/共75頁EXCELSolverApproach342023/3/2第34頁/共75頁群智能理論352023/3/2第35頁/共75頁SwarmIntelligenceSwarmIntelligence(SI)的概念最早由Beni、Hackwood和在分子自動(dòng)機(jī)系統(tǒng)中提出。分子自動(dòng)機(jī)中的主體在一維或二維網(wǎng)格空間中與相鄰個(gè)體相互作用，從而實(shí)現(xiàn)自組織。1999年，Bonabeau、Dorigo和Theraulaz在他們的著作《SwarmIntelligence:FromNaturaltoArtificialSystems中對(duì)群智能進(jìn)行了詳細(xì)的論述和分析，給出了群智能的一種不嚴(yán)格定義：任何一種由昆蟲群體或其它動(dòng)物社會(huì)行為機(jī)制而激發(fā)設(shè)計(jì)出的算法或分布式解決問題的策略均屬于群智能。第36頁/共75頁SwarmIntelligence(續(xù))Swarm可被描述為一些相互作用相鄰個(gè)體的集合體，蜂群、蟻群、鳥群都是Swarm的典型例子。

魚聚集成群可以有效地逃避捕食者，因?yàn)槿魏我恢霍~發(fā)現(xiàn)異常都可帶動(dòng)整個(gè)魚群逃避。螞蟻成群則有利于尋找食物，因?yàn)槿我恢晃浵伆l(fā)現(xiàn)食物都可帶領(lǐng)蟻群來共同搬運(yùn)和進(jìn)食。第37頁/共75頁SwarmIntelligence(續(xù))一只蜜蜂或螞蟻的行為能力非常有限，它幾乎不可能獨(dú)立存在于自然世界中，而多個(gè)蜜蜂或螞蟻形成的Swarm則具有非常強(qiáng)的生存能力，且這種能力不是通過多個(gè)個(gè)體之間能力簡單疊加所獲得的。

社會(huì)性動(dòng)物群體所擁有的這種特性能幫助個(gè)體很好地適應(yīng)環(huán)境，其根本原因在于個(gè)體之間存在著信息交互能力。第38頁/共75頁SwarmIntelligence(續(xù))

信息的交互過程不僅僅在群體內(nèi)傳播了信息，而且群內(nèi)個(gè)體還能處理信息，并根據(jù)所獲得的信息（包括環(huán)境信息和附近其它個(gè)體的信息）改變自身的一些行為模式和規(guī)范，這樣就使得群體涌現(xiàn)出一些單個(gè)個(gè)體所不具備的能力和特性，尤其是對(duì)環(huán)境的適應(yīng)能力。這種對(duì)環(huán)境變化所具有適應(yīng)的能力可以被認(rèn)為是一種智能，也就是說動(dòng)物個(gè)體通過聚集成群而涌現(xiàn)出了智能。

因此，Bonabeau將SI的定義進(jìn)一步推廣為：無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為。第39頁/共75頁SwarmIntelligence(續(xù))JamesKennedy和RussellC.Eberhart在2001年出版了《SwarmIntelligence》，是群智能發(fā)展的一個(gè)重要?dú)v程碑，因?yàn)榇藭r(shí)已有一些群智能理論和方法得到了應(yīng)用。他們不反對(duì)Bonabeau關(guān)于SI定義，贊同其定義的基本精神，但反對(duì)定義中使用“主體”一詞。其理由是“主體”所帶有自治性和特殊性是許多Swarm的個(gè)體所不具備和擁有的，這將大大限制Swarm的定義范圍。他們認(rèn)為暫時(shí)無法給出合適的定義，贊同由MarkMillonas（1994）提出的構(gòu)建一個(gè)SI系統(tǒng)所應(yīng)滿足的五條基本原則：第40頁/共75頁SwarmIntelligence(續(xù))[1]ProximityPrinciple:群內(nèi)個(gè)體具有能執(zhí)行簡單的時(shí)間或空間上的評(píng)估和計(jì)算的能力。[2]QualityPrinciple:群內(nèi)個(gè)體能對(duì)環(huán)境（包括群內(nèi)其它個(gè)體）的關(guān)鍵性因素的變化做出響應(yīng)。[3]PrincipleofDiverseResponse:群內(nèi)不同個(gè)體對(duì)環(huán)境中的某一變化所表現(xiàn)出的響應(yīng)行為具有多樣性。[4]StabilityPrinciple:不是每次環(huán)境的變化都會(huì)導(dǎo)致整個(gè)群體的行為模式的改變。[5]AdaptabilityPrinciple:環(huán)境所發(fā)生的變化中，若出現(xiàn)群體值得付出代價(jià)進(jìn)行改變的機(jī)遇，群體必須能夠改變其行為模式。第41頁/共75頁SwarmIntelligence(續(xù))《SwarmIntelligence》最重要的觀點(diǎn)是：Mindissocial，也就是認(rèn)為人的智能是源于社會(huì)性的相互作用，文化和認(rèn)知是人類社會(huì)性不可分割的重要部分，這一觀點(diǎn)成為了群智能發(fā)展的基石。群智能已成為有別于傳統(tǒng)人工智能中連接主義和符號(hào)主義的一種新的關(guān)于智能的描述方法。群智能的思路，為在沒有集中控制且不提供全局模型的前提下尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。在計(jì)算智能領(lǐng)域已取得成功的兩種基于SI的優(yōu)化算法是蟻群算法和粒子群算法。第42頁/共75頁SwarmIntelligence(續(xù))

目前，已有的基于SI的優(yōu)化算法都是源于對(duì)動(dòng)物社會(huì)通過協(xié)作解決問題行為的模擬，它主要強(qiáng)調(diào)對(duì)社會(huì)系統(tǒng)中個(gè)體之間相互協(xié)同作用的模擬。這一點(diǎn)與EC不同，EC是對(duì)生物演化中適者生存的模擬。與EC一樣的是，SI的目的并不是為了忠實(shí)地模擬自然現(xiàn)象，而是利用他們的某些特點(diǎn)去解決實(shí)際問題。另一個(gè)與EC的相同點(diǎn)是,基于SI的優(yōu)化算法也是概率搜索算法。第43頁/共75頁SwarmIntelligence(續(xù))

目前，已有的群智能理論和應(yīng)用研究證明群智能方法是一種能夠有效解決大多數(shù)優(yōu)化問題的新方法，更重要是,群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是應(yīng)用研究的角度分析,群智能理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。第44頁/共75頁SwarmIntelligence(續(xù))

由于SI的理論依據(jù)是源于對(duì)生物群落社會(huì)性的模擬，因此其相關(guān)數(shù)學(xué)分析還比較薄弱，這就導(dǎo)致了現(xiàn)有研究還存在一些問題。首先，群智能算法的數(shù)學(xué)理論基礎(chǔ)相對(duì)薄弱，缺乏具備普遍意義的理論性分析，算法中涉及的各種參數(shù)設(shè)置一直沒有確切的理論依據(jù)，通常都是按照經(jīng)驗(yàn)型方法確定，對(duì)具體問題和應(yīng)用環(huán)境的依賴性比較大。其次，同其它的自適應(yīng)問題處理方法一樣，群智能也不具備絕對(duì)的可信性，當(dāng)處理突發(fā)事件時(shí),系統(tǒng)的反應(yīng)可能是不可測的,這在一定程度上增加了其應(yīng)用風(fēng)險(xiǎn)。另外,群智能與其它各種先進(jìn)技術(shù)(如:神經(jīng)網(wǎng)絡(luò)、模糊邏輯、禁忌搜索和支持向量機(jī)等)的融合還不足。第45頁/共75頁

粒子群算法(particleswarmoptimization，PSO)由Kennedy和Eberhart在1995年提出，該算法模擬鳥集群飛行覓食的行為，鳥之間通過集體的協(xié)作使群體達(dá)到最優(yōu)目的，是一種基于SwarmIntelligence的優(yōu)化方法。同遺傳算法類似，也是一種基于群體疊代的，但并沒有遺傳算法用的交叉以及變異，而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。PSO的優(yōu)勢在于簡單容易實(shí)現(xiàn)同時(shí)又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用，并且沒有許多參數(shù)需要調(diào)整。PSO算法簡介第46頁/共75頁JamesKennedyreceivedthePh.D.degreefromtheUniversityofNorthCarolina,ChapelHill,in1992.HeiswiththeU.S.DepartmentofLabor,Washington,DC.HeisaSocialPsychologistwhohasbeenworkingwiththeparticleswarmalgorithmsince1994.Hehaspublisheddozensofarticlesandchaptersonparticleswarmsandrelatedtopics,incomputerscienceandsocialsciencejournalsandproceedings.HeisacoauthorofSwarmIntelligence(SanMateo,CA:MorganKaufmann,2001),withR.C.EberhartandY.Shi,nowinitsthirdprinting.第47頁/共75頁RussellC.Eberhart(M’88–SM’89–F’01)receivedthePh.D.degreeinelectricalengineeringfromKansasStateUniversity,Manhattan.HeistheChairandProfessorofElectricalandComputerEngineering,PurdueSchoolofEngineeringandTechnology,IndianaUniversity–PurdueUniversityIndianapolis(IUPUI),Indianapolis,IN.HeiscoeditorofNeuralNetworkPCTools(1990),coauthorofComputationalIntelligencePCTools(1996),coauthorofSwarmIntelligence(2001),ComputationalIntelligence:ConceptstoImplementations(2004).Hehaspublishedover120technicalpapers.Dr.EberhartwasawardedtheIEEEThirdMilleniumMedal.In2002,hebecameaFellowoftheAmericanInstituteforMedicalandBiologicalEngineering.第48頁/共75頁P(yáng)SO產(chǎn)生背景之一：復(fù)雜適應(yīng)系統(tǒng)CAS理論的最基本的思想可以概述如下：

我們把系統(tǒng)中的成員稱為具有適應(yīng)性的主體(AdaptiveAgent)，簡稱為主體。所謂具有適應(yīng)性，就是指它能夠與環(huán)境以及其它主體進(jìn)行交流，在這種交流的過程中“學(xué)習(xí)”或“積累經(jīng)驗(yàn)”，并且根據(jù)學(xué)到的經(jīng)驗(yàn)改變自身的結(jié)構(gòu)和行為方式。整個(gè)系統(tǒng)的演變或進(jìn)化，包括新層次的產(chǎn)生，分化和多樣性的出現(xiàn)，新的、聚合而成的、更大的主體的出現(xiàn)等等，都是在這個(gè)基礎(chǔ)上出現(xiàn)的。第49頁/共75頁復(fù)雜適應(yīng)系統(tǒng)（CAS）續(xù)CAS的四個(gè)基本特點(diǎn)：(1)首先，主體(AdaptiveAgent)是主動(dòng)的、活的實(shí)體；(2)與環(huán)境(包括個(gè)體之間)的相互影響，相互作用，是系統(tǒng)演變和進(jìn)化的主要?jiǎng)恿Γ?3)這種方法不象許多其他的方法那樣，把宏觀和微觀截然分開，而是把它們有機(jī)地聯(lián)系起來；(4)這種建模方法還引進(jìn)了隨機(jī)因素的作用，使它具有更強(qiáng)的描述和表達(dá)能力。第50頁/共75頁P(yáng)SO產(chǎn)生背景之二:人工生命

人工生命是來研究具有某些生命基本特征的人工系統(tǒng)。人工生命包括兩方面的內(nèi)容：①研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象；②研究如何利用生物技術(shù)研究計(jì)算問題(NatureComputation)。我們現(xiàn)在關(guān)注的是第二部分的內(nèi)容?，F(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計(jì)算技巧，例如,人工神經(jīng)網(wǎng)絡(luò)是簡化的大腦模型.遺傳算法是模擬基因進(jìn)化過程的。現(xiàn)在我們討論另一種生物系統(tǒng)：社會(huì)系統(tǒng)，更確切地說，是由簡單個(gè)體組成的群落與環(huán)境以及個(gè)體之間的互動(dòng)行為，也可稱做"群智能"。第51頁/共75頁基本PSO算法

粒子群優(yōu)化算法源于1987年Reynolds對(duì)鳥群社會(huì)系統(tǒng)boids的仿真研究，boids是一個(gè)CAS。在boids中，一群鳥在空中飛行，每個(gè)鳥遵守以下三條規(guī)則：1）避免與相鄰的鳥發(fā)生碰撞沖突；2）盡量與自己周圍的鳥在速度上保持協(xié)調(diào)和一致；3）盡量試圖向自己所認(rèn)為的群體中靠近。僅通過使用這三條規(guī)則，boids系統(tǒng)就出現(xiàn)非常逼真的群體聚集行為，鳥成群地在空中飛行，當(dāng)遇到障礙時(shí)它們會(huì)分開繞行而過，隨后又會(huì)重新形成群體。第52頁/共75頁基本PSO算法（續(xù)）Reynolds僅僅將其作為CAS的一個(gè)實(shí)例作仿真研究，而并未將它用于優(yōu)化計(jì)算中。

Kennedy和Eberhart在中加入了一個(gè)特定點(diǎn)，定義為食物，鳥根據(jù)周圍鳥的覓食行為來尋找食物。他們的初衷是希望通過這種模型來模擬鳥群尋找食源的現(xiàn)象，然而實(shí)驗(yàn)結(jié)果卻揭示這個(gè)仿真模型中蘊(yùn)涵著很強(qiáng)的優(yōu)化能力，尤其是在多維空間尋優(yōu)中。第53頁/共75頁基本PSO算法(續(xù))PSO中，每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥。稱之為“粒子(Particle)”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.PSO初始化為一群隨機(jī)粒子。然后通過疊代找到最優(yōu)解。在每一次疊代中，粒子通過跟蹤兩個(gè)"極值"來更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值pBest.另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值gBest。另外,也可以不用整個(gè)種群而只是用其中一部分的鄰居。第54頁/共75頁粒子群算法第55頁/共75頁算法步驟第56頁/共75頁應(yīng)用實(shí)例1求函數(shù)f=x^2+y^2+z^2+x*y+x^2*y的最小值({x,y,z}∈{{-2,2},{-2,3},{-2,4}})迭代次數(shù)xyzf當(dāng)前最優(yōu)1

0.359707

0.220272

-0.222421

0.3351142

2-1.94700.03195

-3.89033

2-

2

-0.0859

-3.99210

2-

2

0.00065-4100

2-

20.0004-4第57頁/共75頁應(yīng)用實(shí)例2求f(x)=Exp[-0.1x]*Sin[x]的最小值,(x∈{-10,10})在x=-7.95259時(shí)取得最小值搜索次數(shù)最小值1

-1.129942

-1.173063

-2.1687510

-2.20425100

-2.20425第58頁/共75頁算法實(shí)踐及其解釋依概率1搜索到最優(yōu)解，即在統(tǒng)計(jì)意義上能較好的收斂到全局最優(yōu)解，一般情況100次實(shí)驗(yàn)?zāi)苡?0次搜索成功。早熟問題：若粒子的當(dāng)前位置恰是全局最好位置,那么速度更新方程式就只剩下自身，這將會(huì)導(dǎo)致早熟。應(yīng)用方面還結(jié)合了其它智能算法進(jìn)行改進(jìn)、傳統(tǒng)優(yōu)化算法的結(jié)合等。第59頁/共75頁基本PSO算法(續(xù))

粒子群初始位置和速度隨機(jī)產(chǎn)生，然后按公式(1)(2)進(jìn)行迭代，直至找到滿意的解。目前，常用的粒子群算法將全體粒子群(Global)分成若干個(gè)有部分粒子重疊的相鄰子群，每個(gè)粒子根據(jù)子群(Local)內(nèi)歷史最優(yōu)Pl調(diào)整位置，即公式(2)中Pgd換為Pld。第60頁/共75頁P(yáng)articleSwarm研究熱點(diǎn)IEEETRANSACTIONONEVOLUTIONARYCOMPUTION于2004年出版了第3卷：SPECIALISSUEONPSO。RussellC.Eberhart,YuhuiShi在卷首語中指出了當(dāng)前PSO研究的幾個(gè)主要方向及熱點(diǎn)：1。算法分析；2。粒子群拓?fù)浣Y(jié)構(gòu)；3。參數(shù)選擇與優(yōu)化；4。與其他演化計(jì)算的融合；5。應(yīng)用。第61頁/共75頁車輛路徑問題

車輛路徑問題(VehicleRoutingProblem，VRP)由Dantzig和Ramser于1959年首次提出的，它是指對(duì)一系列發(fā)貨點(diǎn)(或收貨點(diǎn))，組成適當(dāng)?shù)男熊嚶窂剑管囕v有序地通過它們，在滿足一定約束條件的情況下，達(dá)到一定的目標(biāo)(諸如路程最短、費(fèi)用最小，耗費(fèi)時(shí)間盡量少等)，屬于完全NP問題，在運(yùn)籌、計(jì)算機(jī)、物流、管理等學(xué)科均有重要意義。第62頁/共75頁帶時(shí)間窗車輛路徑問題帶時(shí)間窗的車輛路徑問題(VehicleRoutingProblemwithTimeWindows,VRPTW)是在VRP問題上加了客戶要求訪問的時(shí)間窗口。許多問題都可以歸結(jié)為VRPTW問題來處理(如郵政投遞、火車及公共汽車的調(diào)度等)，所以對(duì)它的研究越來越受到人們的重視。先后出現(xiàn)了一般啟發(fā)式算法和神經(jīng)網(wǎng)絡(luò)、遺傳算法、禁忌搜索和模擬退火等現(xiàn)代啟發(fā)式算法。第63頁/共75頁帶時(shí)間窗車輛路徑問題（續(xù)）

時(shí)間窗車輛路徑問題一般描述為：（1）有一個(gè)中心倉庫，擁有K輛車，有L個(gè)發(fā)貨點(diǎn)運(yùn)輸任務(wù)需要完成。（2）第k輛車的最大載重量為qk

(k=1,..,K)；（4）第i個(gè)發(fā)貨點(diǎn)的貨運(yùn)量為gi(i=1,…,L)，(max(gi)≤max(qi))，（5）完成發(fā)貨點(diǎn)i任務(wù)需要的時(shí)間(裝貸或卸貨)表示為Ti，且任務(wù)i必須在時(shí)間窗口[ETi,LTi]完成，其中ETi為任務(wù)i的允許最早開始時(shí)間，LTi為任務(wù)i的允許最遲開始時(shí)間。如果車輛到達(dá)發(fā)貨點(diǎn)i的時(shí)間早于ETi，則車輛需在i處等待；如果車輛到達(dá)時(shí)間晚于LTi，任務(wù)i將被延遲進(jìn)行。（6）求滿足貨運(yùn)要求的運(yùn)行費(fèi)用最少的車輛行駛線路。第64頁/共75頁VRPTW的整數(shù)規(guī)劃描述：第65頁/共75頁VRPTW模型的退化

這個(gè)模型通用性很強(qiáng)，經(jīng)過參數(shù)的不同設(shè)定，可以將其轉(zhuǎn)換為其他組合優(yōu)化問題的數(shù)學(xué)模型：（1）若(1)中ETi=0,LTi→∞，則VRPTW模型就變成了普通的VRP模型；（2）若僅有一個(gè)車輛被利用，則該問題就變成了TSP問題；（3）若去掉約束(2)，則變成了m－TSPTW問題。第66頁/共75頁帶時(shí)間窗車輛路徑問題（續(xù)）

如何找到一個(gè)合適的表達(dá)方法，使粒子與解解向量對(duì)應(yīng)，是實(shí)現(xiàn)算法的關(guān)鍵問題之一。構(gòu)造一個(gè)2L維的空間對(duì)應(yīng)有L個(gè)發(fā)貨點(diǎn)任務(wù)的VRP問題，每個(gè)發(fā)貨點(diǎn)任務(wù)對(duì)應(yīng)兩維：完成該任務(wù)車輛的編號(hào)k，該任務(wù)在k車行駛路徑中的次序r。為表達(dá)和計(jì)算方便，將每個(gè)粒子對(duì)應(yīng)的2L維向量X分成兩個(gè)L維向量：Xv(表示各任務(wù)對(duì)應(yīng)的車輛)和Xr(表示各任務(wù)在對(duì)應(yīng)的車輛路徑中的執(zhí)行次序)。第67頁/共75頁例如，設(shè)VRP問題中發(fā)貨點(diǎn)任務(wù)數(shù)為7，車輛數(shù)為3，若某粒子的位置向量X為：發(fā)貨點(diǎn)任務(wù)號(hào):1234567Xv

：1222233Xr：1431221則該粒子對(duì)應(yīng)解路徑為：車1：010車2：045320車3：0760粒子速度向量V與之對(duì)應(yīng)表示為Vv和Vr。第68頁/共75頁

該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車輛的配送服務(wù)，并限制每個(gè)發(fā)貨點(diǎn)的需求僅能由某一車輛來完成，使解的可行化過程計(jì)算大大減少。雖然該表示方法的維數(shù)較高，但由于PSO算法在多維尋優(yōu)問題有著非常好的特性，維數(shù)的增加并未增加計(jì)算的復(fù)雜性，這一點(diǎn)在實(shí)驗(yàn)結(jié)果中可以看到。第69頁/共75頁VRP