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

1、生物啟發(fā)式優(yōu)化方法及其在管理中的應(yīng)用牛 奔Email: drniuben報告內(nèi)容啟發(fā)式優(yōu)化方法研究背景生物啟發(fā)式優(yōu)化方法群體智能優(yōu)化方法（SI）SI算法在管理中的應(yīng)用實例研究2報告內(nèi)容1啟發(fā)式計算方法研究背景2生物啟發(fā)式計算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實例研究3最優(yōu)化問題模型啟發(fā)式計算方法背景全局最優(yōu)與局部最優(yōu) 實際生活中的優(yōu)化問題4經(jīng)典的計算方法17世紀Newtown 微積分1847年 Cauchy 最速下降法1947年 Dantzig 單純形方法1939年 Kantorovich下料問題和運輸問題 問題求解5啟發(fā)式計算方法【定義1-1】 啟發(fā)式算法是一種基于直觀

2、或經(jīng)驗構(gòu)造的算法，在可接受的耗費（指計算時間、占用空間等）下給出待解決優(yōu)化問題每一實例的一個可行解，該可行解與最優(yōu)解的偏離程度未必可事先估計。【定義1-2】 啟發(fā)式算法是一種技術(shù)，該技術(shù)使得能在可接受的計算費用內(nèi)去尋找盡可能好的解，但不一定能保證所得解的可行性和最優(yōu)性，甚至在多數(shù)情況下，無法描述所得解與最優(yōu)解的近似程度。經(jīng)典的啟發(fā)式方法基本原理:根據(jù)問題的部分已知信息來啟發(fā)式地探索該問題的解決方案，在探索解決方案的過程中將發(fā)現(xiàn)的有關(guān)信息記錄下來，不斷積累和分析，并根據(jù)越來越豐富的已知信息來指導(dǎo)下一步的動作并修正以前的步驟，從而獲得在整體上較好的解決方案。6啟發(fā)式計算方法分類物理啟發(fā)式 模擬退火

3、算法 （模擬固體熔化狀態(tài)下由逐漸冷 卻至最終達到結(jié)晶狀 態(tài)的物理過程） 量子計算 （模擬量子態(tài)的疊加性和相 干性 以及 量子 比特之間的糾纏性）社會與文化啟發(fā) 文化算法 （模擬人類社會的演化過程） 人口遷移算法（模擬人口流動與人口遷移）7遺傳算法進化過程優(yōu)化過程生物進化過程是一個自然，并行，穩(wěn)健的優(yōu)化過程，這一優(yōu)化過程的目的在于使生命體達到適應(yīng)環(huán)境的最佳結(jié)構(gòu)與效果，而生物種群通過” “優(yōu)勝劣汰”及遺傳變異來達到進化（優(yōu)化）目的的。10遺傳算法生物的進化機制自然選擇 適應(yīng)環(huán)境的個體具有更高的生存能力，同時染色體特征被保留下來雜交 隨機組合來自父代的染色體上的遺傳物質(zhì)，產(chǎn)生不同于它們父代的染色體突

4、變 隨機改變父代的染色體基因結(jié)構(gòu)，產(chǎn)生新染色體11神經(jīng)計算樹突 突觸 軸突 細胞體人工神經(jīng)網(wǎng)絡(luò)是由 具有適應(yīng)性的簡單單元組成的廣泛并行互連的網(wǎng)絡(luò)，它的組織能夠模擬生物神經(jīng)系統(tǒng)對真實世界物體所作出的交互反應(yīng)。12報告內(nèi)容1啟發(fā)式計算方法研究背景2生物啟發(fā)式計算方法3群體智能優(yōu)化方法（SI）4SI算法在管理中的應(yīng)用5實例研究16群體智能（Swarm Intelligence）生物學(xué)家研究表明：在這些群居生物中雖然每個個體的智能不高，行為簡單，也不存在集中的指揮，但由這些單個個體組成的群體，似乎在某種內(nèi)在規(guī)律的作用下，卻表現(xiàn)出異常復(fù)雜而有序的群體行為。AC18AC19避免碰撞速度匹配 中心聚集鳥群的

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

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

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

8、問題, 粒子數(shù)可以取到100 或 200粒子的維數(shù): 這是由優(yōu)化問題決定, 就是問題解的長度粒子的范圍: 由優(yōu)化問題決定,每一維可是設(shè)定不同的范圍Vmax: 最大速度,決定粒子在一個循環(huán)中最大的移動距離,通常設(shè)定為粒子的范圍寬度學(xué)習(xí)因子: c1 和 c2 通常等于 2. 不過在文獻中也有其他的取值. 但是一般 c1 等于 c2 并且范圍在0和4之間中止條件: 最大循環(huán)數(shù)以及最小錯誤要求. 31初始狀態(tài)345代后3510代后3615代后37100代后38500代后39最終結(jié)果迭代次數(shù)搜尋結(jié)果0416.2455995515.74879610759.40400615793.73201920834.8

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

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

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

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

13、本和費用水平。 本例研究的是多配送中心選址50配送中心選址問題 物流配送總費用 從配送中心 到需求點 的單位費用 從配送中心 到需求點 運輸量 在點 設(shè)置配送中心的固定費用及管理費用等需求點 的需求量可興建配送中心的最多個數(shù)配送中心 的容量51配送中心選址模型52配送中心選址模型53粒子的編碼 物流配送選址問題主要是在一系列需求點中確定配送中心的最佳位置，目標(biā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需求點隸

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