生物啟發(fā)式方法課件

1、生物啟發(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ā)式算法是一種基于直觀

2、或經(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ā)式 模擬退火

3、算法 （模擬固體熔化狀態(tài)下由逐漸冷 卻至最終達(dá)到結(jié)晶狀 態(tài)的物理過程） 量子計(jì)算 （模擬量子態(tài)的疊加性和相 干性 以及 量子 比特之間的糾纏性）社會(huì)與文化啟發(fā) 文化算法 （模擬人類社會(huì)的演化過程） 人口遷移算法（模擬人口流動(dòng)與人口遷移）7遺傳算法進(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)生不同于它們父代的染色體突

4、變 隨機(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報(bào)告內(nèi)容1啟發(fā)式計(jì)算方法研究背景2生物啟發(fā)式計(jì)算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實(shí)例研究16群體智能（Swarm Intelligence）生物學(xué)家研究表明：在這些群居生物中雖然每個(gè)個(gè)體的智能不高，行為簡(jiǎn)單，也不存在集中的指揮，但由這些單個(gè)個(gè)體組成的群體，似乎在某種內(nèi)在規(guī)律的作用下，卻表現(xiàn)出異常復(fù)雜而有序的群體行為。AC18AC19避免碰撞速度匹配 中心聚集鳥群的

5、飛行行為23鳥群覓食模型FoodGlobal Best SolutionPast Best Solution24Randomly searching foods社會(huì)型行為的模擬25認(rèn)知行為 （Cognition Behavior）先前經(jīng)驗(yàn)26Max26社會(huì)行為 （Social Behavior）We tend to adjust our beliefs and attitudes to conform with those of our social peers.Max人類社會(huì)系統(tǒng)27粒子群算法介紹 每個(gè)尋優(yōu)的問題解都被想像成一支鳥，也稱為“Particle”。所有的Particle 都有一個(gè)

6、fitness function 以判斷目前的位置之好壞，每一個(gè)Particle具有記憶性，能記得所搜尋到最佳位置。每一個(gè)Particle 還有一個(gè)速度以決定飛行的距離與方向。28局部最優(yōu)解全局最優(yōu)解運(yùn)動(dòng)向量慣性向量Study FactorHere I am!The best position of teamMy best positionx(t)pgpivPBestgBestx(t+1)速度與位置更新29算法流程Initialization ：將群族做初始化，以隨機(jī)的方式求出每一Particle 之初始位置與速度。Evaluation：依據(jù)fitness function 計(jì)算出其fitne

7、ss value 以作為判斷每一個(gè)Particle之好壞。Find Pbest ：找出每一個(gè)Particle 到目前為止的搜尋過程中最佳解，這個(gè)最佳解稱之為Pbest。Find the Gbest：找出所有群體中的最佳解，此最佳解稱之為Gbest。Update the Velocity and position：根據(jù)速度與位置公式 更新每一Particle的速度與位置。Termination. 返回步驟2繼續(xù)執(zhí)行，直到獲得一個(gè)令人滿意的結(jié)果或符合終止條件為止。30參數(shù)選擇粒子數(shù): 一般取 20 40. 其實(shí)對(duì)于大部分的問題10個(gè)粒子已經(jīng)足夠可以取得好的結(jié)果, 不過對(duì)于比較難的問題或者特定類別的

8、問題, 粒子數(shù)可以取到100 或 200粒子的維數(shù): 這是由優(yōu)化問題決定, 就是問題解的長(zhǎng)度粒子的范圍: 由優(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ò)誤要求. 31初始狀態(tài)345代后3510代后3615代后37100代后38500代后39最終結(jié)果迭代次數(shù)搜尋結(jié)果0416.2455995515.74879610759.40400615793.73201920834.8

99115355000837.965771最優(yōu)解837.965840414243報(bào)告內(nèi)容1啟發(fā)式計(jì)算方法研究背景2生物啟發(fā)式計(jì)算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實(shí)例研究44 SI算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化間題的通用框架，它不依賴于問題的具體領(lǐng)域，對(duì)問題的種類有很強(qiáng)的魯棒性，所以廣泛應(yīng)用于很多學(xué)科。下面是SI的一些主要應(yīng)用領(lǐng)域： (1) 管理領(lǐng)域的組合優(yōu)化問題 隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò) 大，有時(shí)在目前的計(jì)算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對(duì)這類復(fù)雜問題，人們己意識(shí)到應(yīng)把主要精力放在尋求其滿意解上，而SI算法

10、是尋求這種滿意解的最佳工具之一。實(shí)踐證明，SI算法對(duì)于組合優(yōu)化中的NP完全問題非常有效。 例如，SI已經(jīng)在求解旅行商問題、背包問題、裝箱問題、指派問題等方面得到成功的應(yīng)用。SI算法在管理中應(yīng)用45（2）物流與供應(yīng)鏈管理中應(yīng)用 物流與供應(yīng)鏈管理中，在很多情況下所建立起來的數(shù)學(xué)模型難以精確求解，即使經(jīng)過一些簡(jiǎn)化之后可以進(jìn)行求解，也會(huì)因簡(jiǎn)化得太多而使得求解結(jié)果與實(shí)際相差甚遠(yuǎn)。 而目前在現(xiàn)實(shí)管理中也主要是靠一些經(jīng)驗(yàn)來進(jìn)行管理?，F(xiàn)在群體智能算法已成為復(fù)雜問題的有效工具，在生產(chǎn)計(jì)劃調(diào)度、運(yùn)輸問題、車輛路徑調(diào)度問題、物流配送管理問題，多級(jí)庫(kù)存優(yōu)化控制策略，供應(yīng)鏈需求預(yù)測(cè)優(yōu)化模型研究，都得到了有效的應(yīng)用.SI

11、算法在管理中應(yīng)用46 (3) 知識(shí)管理中的應(yīng)用 知識(shí)管理是企業(yè)為實(shí)現(xiàn)其管理目標(biāo)，運(yùn)用現(xiàn)代的管理理論和技術(shù)，對(duì)企業(yè)內(nèi)部和外部知識(shí)資源進(jìn)行發(fā)現(xiàn)，挖掘，整理，整合，并實(shí)施科學(xué)的管理和維護(hù)，將最合理的知識(shí)在最恰當(dāng)?shù)臅r(shí)候提供給最需要的人，以便做出最科學(xué)的決策。 目前基于群體思想的方法應(yīng)用于知識(shí)管理的主要方向有：客戶關(guān)系管理中的客戶行為聚類分析，關(guān)聯(lián)分析， 文檔分類，屬性約簡(jiǎn).SI算法在管理中應(yīng)用47 (5) 項(xiàng)目管理 項(xiàng)目管理網(wǎng)絡(luò)計(jì)劃中的工期限定-資源均衡問題 項(xiàng)目合作伙伴的選擇問題 (4) 風(fēng)險(xiǎn)管理 傳統(tǒng)的風(fēng)險(xiǎn)管理大都是憑借主觀經(jīng)驗(yàn)，采用定性的判斷方 法，大多數(shù)情況下只考慮信用風(fēng)險(xiǎn)最低而忽略投資投資組

12、 合理論在此過程中的重要。研究如何在各種復(fù)雜的、不確 定的環(huán)境中對(duì)資產(chǎn)進(jìn)行有效的配置，實(shí)現(xiàn)資產(chǎn)的回報(bào)最大 化與所承擔(dān)風(fēng)險(xiǎn)的最小化的均衡，將是SI應(yīng)用研究的一個(gè) 重要方向。SI算法在管理中應(yīng)用48報(bào)告內(nèi)容1啟發(fā)式計(jì)算方法研究背景2生物啟發(fā)式計(jì)算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實(shí)例研究49配送中心選址問題 配送中心是將取貨，集貨，包裝，倉(cāng)庫(kù)，裝卸，分貨，配貨，加工，信息服務(wù)，送貨等多種服務(wù)功能融為一體的物流據(jù)點(diǎn)。 配送中心是進(jìn)行物流配活動(dòng)的最主要的硬件設(shè)施，所有的物流活動(dòng)都是基于配送中心這個(gè)平臺(tái)來進(jìn)行的，它是供應(yīng)鏈中非常重要的節(jié)點(diǎn)。配送中心的定位幾乎決定 配送業(yè)務(wù)所需要的成

13、本和費(fèi)用水平。 本例研究的是多配送中心選址50配送中心選址問題 物流配送總費(fèi)用 從配送中心 到需求點(diǎn) 的單位費(fèi)用 從配送中心 到需求點(diǎn) 運(yùn)輸量 在點(diǎn) 設(shè)置配送中心的固定費(fèi)用及管理費(fèi)用等需求點(diǎn) 的需求量可興建配送中心的最多個(gè)數(shù)配送中心 的容量51配送中心選址模型52配送中心選址模型53粒子的編碼 物流配送選址問題主要是在一系列需求點(diǎn)中確定配送中心的最佳位置，目標(biāo)是使各項(xiàng)費(fèi)用總和最小。因此對(duì)于每個(gè)需求點(diǎn)而言，就有兩個(gè)問題 是不是配送中心 隸屬于哪個(gè)配送中心。需求點(diǎn)號(hào)：1 2 3 4 5 6 7 0 1 0 2 3 0 0 3 1 2 2 3 2 1 2： 2 74： 3 4 65： 1 5需求點(diǎn)隸

14、屬情況：54約束處理55算法流程初始化 一群鳥，每個(gè)鳥位置向量X的每一維隨機(jī)?。?-m）（配送中心數(shù)）之間的實(shí)數(shù)，每個(gè)速度向量V的每一維隨機(jī)取-(m-1),(m-1)之間的整數(shù)對(duì)每個(gè)鳥進(jìn)行整數(shù)規(guī)范化，計(jì)算其適應(yīng)度值，將初始評(píng)價(jià)值作為個(gè)體歷史最優(yōu)解，并尋找全局最優(yōu)值位置與速度的更新對(duì)X進(jìn)行整數(shù)規(guī)范化，再更新個(gè)體與全局最好值得到終終止條件，則返回56實(shí)例研究 現(xiàn)有一個(gè)12需求點(diǎn)的物流網(wǎng)絡(luò)，要求從中選擇出3個(gè)作為配送中心，使各項(xiàng)費(fèi)用總和最小。已知在和建設(shè)配送中心的固定費(fèi)用分別為 11，16，14，14，15，13，18，12，11，14，16，11個(gè)單位，合配送中心的容量均為13個(gè)單位，各點(diǎn)的需求量分別為5，4，2，3，2，4，3，5，4，3，2，2個(gè)單位。需求點(diǎn)的間距見下表57需求點(diǎn)費(fèi)用表12345678910111210167434669892105654577109103650369101212151415476303101113131615125456307810101312963491