亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于模擬退火遺傳混合算法的指派問題研究

        2011-02-06 01:07:10ZHAOLiFENGYi
        物流科技 2011年12期
        關鍵詞:指派模擬退火遺傳算法

        趙 麗, 馮 毅 ZHAO Li,FENG Yi

        (1.蘭州交通大學,甘肅 蘭州 730070;2.蘭州理工大學,甘肅 蘭州 730050)

        指派問題是物流活動中經(jīng)常遇到的組合性優(yōu)化問題,應用十分廣泛,因此對其研究較多。在實際物流活動中指派問題通常有平衡與非平衡兩種類型,即有n項任務,指派n個人員來分派完成稱為平衡指派問題;有n項任務,指派m個人員來分派完成稱為非平衡指派問題。近幾年來模擬退火算法和遺傳算法對指派問題在優(yōu)化領域得到廣泛深入的研究和應用,并得到很好的效果。在此基礎上本文研究模擬退火遺傳混合算法對指派問題的思路及求解。經(jīng)實例計算該方法收斂較快,搜索效率較高。

        1 指派問題數(shù)學模型

        為方便研究將平衡與非平衡兩種指派問題歸納為如下兩種形式研究:

        設有n項任務,要派m個人去完成,Cij表示第i個人完成第j項任務要付出的代價,tij表示第i個人完成第j項任務所需時間,則如何分派會使整體效益最好,即用時少費用低。

        為建立模型引入0-1變量:

        1.1 人數(shù)大于或等于工作項目時m≥()n

        1.2 人數(shù)小于工作項目時m<()n

        式中b——每人限制的最大工作量

        2 指派問題的模擬退火遺傳混合算法實現(xiàn)

        2.1 模擬退火遺傳混合算法思想

        Step1:選定初始溫度t=t0

        利用模擬退火算法的溫度控制方法選定較合適的初始溫度。如果初始溫度選擇過高會導致計算時間較長,從而降低計算效率。如果初始溫度選擇過低又有可能使最終收斂得不到最優(yōu)解。因此根據(jù) (14)式的條件來確定初始溫度t0。

        式中 Δfij——任意兩個相鄰的溫度差

        Step2:確定初始群體initpop

        首先,用實數(shù)編碼方法對任務數(shù)n進行編碼且不變;

        其次,用實數(shù)編碼方法對人數(shù)m進行編碼且可以隨機抽??;

        最后,利用隨機生成法對l!l=m-()1 個解中隨機選取一個解為初始群體initpop。

        Step3:構造適應函數(shù)f0=fitfun1,ft=fitfun1

        Step4:利用遺傳算法對初始群體initpop進行優(yōu)化,產(chǎn)生種群seedpop1

        (1) 確定評價函數(shù)eval( Vi)

        (2)利用評價函數(shù)可以確定進入種群的個體

        當qi-1≤γ≤qi時 (γ為 (0~1)的偽隨機數(shù)),第i個染色體進入種群,從而形成種群seedpop1。

        Step5:利用模擬退火算法對種群seedpop1進行訓練,產(chǎn)生更優(yōu)的新種群seedpop2

        (1)對seedpop1中1~m個體的適應值與初始群體中f0的值進行比較,滿足條件的進入seedpop2;

        (2)否則,根據(jù)評價函數(shù)來判斷進入seedpop2的個體。當個體的適應值滿足時,則選擇進入seedpop2;

        (3)經(jīng)過優(yōu)化訓練,產(chǎn)生新種群seedpop2。

        Step6:對新種群seedpop2進行交叉、變異,產(chǎn)生子代children

        (1)對新種群seedpop2進行雙親雙子法交叉,交叉率β,生成crosspop;

        (2)再進行變異,交叉率ε,生成mutpop;

        (3)生成子代children。

        Step7:返回Step4,直到滿足終止條件

        Step8:得到最優(yōu)解

        3 算例演示

        某大型生產(chǎn)企業(yè)為生產(chǎn)和人員安全每年都要定期對生產(chǎn)設備進行檢修,檢修分為平時檢修和7月分大檢修?,F(xiàn)取其中一個車間來做算例,該車間只有3個維修工,平時每次平均會有2個地方出現(xiàn)故障,到7月大檢修時該車間5個檢修點都要停止運作重新進行檢查和修理。已知工人維修故障所需時間Pij見表1,每個維修工的基本維修費用Cij見表2,注:在7月份大檢修時天氣比較炎熱為保證維修工安全要求每個工人至多維修兩個故障點。

        表1 完成任務所需時間 單位:小時

        表2 完成任務所付費用 單位:百元

        混合算法相關參數(shù)選擇α、初始時間t0=6、交叉率β=0.2、變異率=0.05。利用前面設計的混合算法進行運算得到結果及比較結果見表3,運行次數(shù)都為10次。按照該方案進行分配所得到的完成任務的花費時間大約要比單一使用模擬退火或遺傳算法獲得最優(yōu)解短五分之二。

        4 結 論

        本文結合模擬退火算法和遺傳算法的優(yōu)點,提出模擬退火遺傳混合算法來解決實際中的指派問題。指派問題屬于組合優(yōu)化問題,很適合用本文研究的算法來實現(xiàn)。這種混合算法能夠準確快速地求解最優(yōu)結果或分配方案,針對較大規(guī)模的指派問題,能夠縮短搜索時間,取得良好的效果。

        表3

        [1] 賀國先.現(xiàn)代物流系統(tǒng)仿真[M].北京:中國鐵道出版社,2008.

        [2] 焦永蘭.管理運籌學[M].北京:中國鐵道出版社,2000.

        [3] 邢文訓,謝金星.現(xiàn)代優(yōu)化計算方法[M].北京:清華大學出版社,2005.

        [4] 謝凡榮.求解指派問題的一個算法[J].運籌與管理,2004(6):24-26.

        [5] 張新輝.任務數(shù)多于人數(shù)的指派問題[J].運籌與管理,1997(3):15-18.

        [6] Cattrysse D G,Van Wassenhove L N.A survey of algoirths for the generalized assignment problem[J].Europena Joumla of Operationla Research,1992,60(3):260-272.

        [7] Marco Dorigo,Vittorio Maniezzo,Alberto Colomi.Ant system:Optimization by a colony of cooperating agents[J].IEEE Transactions on Cybernetics,1996(26):55-57.

        猜你喜歡
        指派模擬退火遺傳算法
        模擬退火遺傳算法在機械臂路徑規(guī)劃中的應用
        測控技術(2018年3期)2018-11-25 09:45:08
        基于自適應遺傳算法的CSAMT一維反演
        一種基于遺傳算法的聚類分析方法在DNA序列比較中的應用
        基于遺傳算法和LS-SVM的財務危機預測
        基于模糊自適應模擬退火遺傳算法的配電網(wǎng)故障定位
        零元素行擴展路徑算法求解線性指派問題
        基于改進的遺傳算法的模糊聚類算法
        SOA結合模擬退火算法優(yōu)化電容器配置研究
        電源技術(2015年5期)2015-08-22 11:18:24
        基于遺傳-模擬退火算法的城市軌道交通快慢車停站方案
        具有直覺模糊信息的任務指派問題研究
        国产综合精品久久99之一| 亚洲αv在线精品糸列| 最新亚洲视频一区二区| 亚洲乱码中文字幕在线| 久久久精品国产sm调教网站| 国产精品视频牛仔裤一区| 亚洲啊啊啊一区二区三区| 人妻少妇艳情视频中文字幕| 国产三级av在线播放| 国产精品亚洲日韩欧美色窝窝色欲| 国产在线高清无码不卡| 人妻中文久久人妻蜜桃| 宅男66lu国产在线观看| 最好看2019高清中文字幕视频| 亚洲24小时在线免费视频网站| 男奸女永久免费视频网站| 成人性生交大片免费看96| 中文字幕免费观看视频| 日韩女同一区在线观看| 久久日日躁夜夜躁狠狠躁| 18禁黄久久久aaa片| 无码午夜剧场| 国产优质av一区二区三区| 波多野无码AV中文专区| 久久狠狠爱亚洲综合影院| 中文字幕av长濑麻美| 黑人巨大精品欧美一区二区 | 亚洲精品国产美女久久久| 亚洲区一区二区中文字幕| 国产肥熟女免费一区二区| 国产女人高潮视频在线观看| 97在线视频免费| 亚洲精品中文字幕91| 国产精品无码一区二区在线观一 | 九色91精品国产网站| 中文字幕人妻被公喝醉在线| 国产大片黄在线观看| 色两性网欧美| 二区三区视频在线观看| 精品卡一卡二乱码新区| 久久人人妻人人做人人爽|