亚洲免费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
        基于遺傳-模擬退火算法的城市軌道交通快慢車停站方案
        具有直覺模糊信息的任務指派問題研究
        九九精品视频在线观看| 人妻色中文字幕免费视频| 精品国产女主播一区在线观看| 亚洲精品宾馆在线精品酒店| 精品香蕉一区二区三区| 日本爽快片100色毛片| 国产精品jizz在线观看老狼| 狠狠色婷婷久久一区二区| 精品国产AⅤ一区二区三区4区| 熟女人妻一区二区在线观看| 亚洲精品女人天堂av麻| 亚洲一区第二区三区四区| 国产色在线 | 日韩| 精品水蜜桃久久久久久久 | 谷原希美中文字幕在线| 国产黄色av一区二区三区| 岳好紧好湿夹太紧了好爽矜持 | 亚洲综合第一页中文字幕| 色综合天天综合欧美综合 | 久久99精品中文字幕在| 国产一区二区三区观看视频| 91成人黄色蘑菇视频| 在线成人爽a毛片免费软件| 丰满岳乱妇久久久| 亚洲美女影院| 久久久精品国产亚洲av网不卡| 久久熟妇少妇亚洲精品| 亚洲av片在线观看| 久久中文字幕乱码免费| av草草久久久久久久久久久| 日本久久黄色高清视频| 国产精品人妻熟女男人的天堂| 亚洲无av在线中文字幕| 毛多水多www偷窥小便| 91精品国产综合成人| av天堂手机在线免费| 本道天堂成在人线av无码免费 | 一区二区三区视频亚洲| 波多野结衣在线播放| 伊人久久无码中文字幕| 欧美日韩国产成人综合在线影院|