資源描述：
《遺傳算法基于路徑優(yōu)化問題應(yīng)用的改進(jìn)探索研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、遺傳算法基于路徑優(yōu)化問題應(yīng)用的改進(jìn)探索研究摘要：遺傳算法是一種應(yīng)用很廣泛的智能優(yōu)化算法，對(duì)遺傳算法進(jìn)行了分析研究，針對(duì)遺傳算法的一些缺陷提出了相應(yīng)的改進(jìn)方法。在上述研究基礎(chǔ)上，基于遺傳算法，研究了物流系統(tǒng)中的庫(kù)存優(yōu)化問題及車輛路徑問題。將車輛路徑問題看做是組合優(yōu)化問題，并應(yīng)用遺傳算法進(jìn)行求解。關(guān)鍵詞：路徑優(yōu)化；遺傳算法；禁忌搜索算法引言隨著企業(yè)成本絕大部分在于運(yùn)輸過程中產(chǎn)生，有效地路徑優(yōu)化能夠幫助物流企業(yè)很好的解決成本節(jié)約問題。從而遺傳算法等高效簡(jiǎn)潔的優(yōu)化算法成為人們?cè)絹?lái)越關(guān)注的對(duì)象。一、研究背景近年來(lái)，隨著人工智能應(yīng)用
2、領(lǐng)域的不斷擴(kuò)大，傳統(tǒng)的基于符號(hào)處理的人工智能方法在知識(shí)表示、信息處理和解決組合爆炸等方面遇到的困難越來(lái)越明顯，從而使得尋求一種適合于大規(guī)模問題并具有自組織、自適應(yīng)、自學(xué)習(xí)能力的算法成為有關(guān)學(xué)科的一個(gè)研究目標(biāo)。遺傳算法（geicalgorithms，簡(jiǎn)稱ga）是j.holland與1975年提出的。ga是基于“適者生存”的一種高度并行、隨機(jī)和自適應(yīng)的優(yōu)化算法，它將問題的求解表示成“染色體”的適者生存過程，通過“染色體”群的一代代不斷進(jìn)化，包括復(fù)制、交叉和變異等操作，最終收斂到“最適應(yīng)環(huán)境”的個(gè)體，從而求得問題的最優(yōu)解或滿意
3、解。二、遺傳算法ga是一種通用的優(yōu)化算法，其編碼技術(shù)和遺傳操作比較簡(jiǎn)單，優(yōu)化不受限制性條件的約束，其兩個(gè)顯著性特點(diǎn)是隱含并行性和全局解空間搜索。它是一類隨機(jī)優(yōu)化算法，但它不是簡(jiǎn)單的隨機(jī)比較搜索，而是通過對(duì)染色體的評(píng)價(jià)和對(duì)染色體中基因的作用，有效地利用已有信息來(lái)指導(dǎo)搜索有希望改善優(yōu)化質(zhì)量的狀態(tài)。lOCalHosT遺傳算法主要借鑒了生物進(jìn)化的一些特征，它的主要生物進(jìn)化特征體現(xiàn)在：（1）進(jìn)化發(fā)生在解的編碼上。這些編碼用生物術(shù)語(yǔ)稱為染色體。由于一開始要進(jìn)行編碼，優(yōu)化問題的一切性質(zhì)都通過編碼來(lái)研究。編碼和解碼是遺傳算法的一個(gè)主題。
4、（2）自然選擇規(guī)律決定哪些染色體產(chǎn)生超過平均數(shù)的后代。而在遺傳算法中，通過優(yōu)化問題的目標(biāo)而人為地構(gòu)造適應(yīng)函數(shù)以達(dá)到好的染色體產(chǎn)生超過平均數(shù)的后代。（3）當(dāng)染色體結(jié)合時(shí)，雙親的遺傳基因結(jié)合使得子女保持有父母的特征。（4）染色體結(jié)合以后，隨機(jī)的變異會(huì)造成子代與父代產(chǎn)生不同的特征。遺傳算法主要包含以下處理步驟：第一是對(duì)優(yōu)化問題的解編碼。此外，稱一個(gè)解的編碼為一個(gè)染色體，組成編碼的元素成為基因。編碼的目的主要是用于優(yōu)化問題的表現(xiàn)形式和利于之后遺傳算法中的計(jì)算。第二是適應(yīng)函數(shù)的構(gòu)造和應(yīng)用。適應(yīng)函數(shù)基本上依據(jù)優(yōu)化問題的目標(biāo)函數(shù)而定。
5、適應(yīng)函數(shù)確定以后，自然選擇規(guī)律是以適應(yīng)函數(shù)值的大小決定的概率分布來(lái)確定哪些染色體適應(yīng)生存，哪些被淘汰。生存下來(lái)的染色體就組成了一個(gè)種群，形成一個(gè)可以繁衍下一代的種群。第三是染色體的結(jié)合。雙親的遺傳基因之間的結(jié)合是通過編碼之間的交配（crossover）達(dá)到下一代的產(chǎn)生。遺傳算法作為一個(gè)全局性優(yōu)化算法具有很大的優(yōu)越性，具體體現(xiàn)在：（1）遺傳算法適合求解那些帶有多參數(shù)、多變量、多目標(biāo)和在多區(qū)域但連通性較差的np難（非多項(xiàng)式確定性問題）優(yōu)化問題。對(duì)多參數(shù)、多變量的np難優(yōu)化問題，通過解析求解或計(jì)算求最優(yōu)解的可能性很小，主要依賴
6、于數(shù)值求解。遺傳算法就是一種數(shù)值求解的算法，具有普遍性并且對(duì)目標(biāo)函數(shù)的性質(zhì)幾乎沒有要求，并且它可以一次記錄多個(gè)解。（2）遺傳算法在求解很多組合優(yōu)化問題時(shí)，不需要有很強(qiáng)的技巧和對(duì)問題有非常深入的了解。如路線調(diào)度問題、排序等。遺傳算法再給這些問題的決策變量編碼后，起計(jì)算過程是比較簡(jiǎn)單的，并且可以較快的得到一個(gè)滿意解。（3）遺傳算法同求解問題的其他啟發(fā)式算法有較好的兼容性。當(dāng)然遺傳算法也不可避免地存在著它的不足之處：（1）存在編碼不規(guī)范及表示不準(zhǔn)確等問題。（2）單一的遺傳編碼不能全面地將優(yōu)化問題的約束表示出來(lái)。（3）大量研究也
7、表明，ga存在早熟、算法參數(shù)敏感等缺點(diǎn)，取得良好的性能需要依賴較大的種群并對(duì)算法進(jìn)行精心設(shè)計(jì)。采用遺傳算法等智能優(yōu)化算法來(lái)求解帶能力約束的車輛路徑問題（capacitatedvehicleroutingproblem，即cvrp），一般能在較短的計(jì)算時(shí)間內(nèi)獲得質(zhì)量較高的近似解。三、問題描述cvrp可描述如下:配送中心有m輛貨車，每輛車的能力為q；配送中心需為n個(gè)客戶提供貨物配送任務(wù)，每個(gè)客戶的需求量為gi（i=1，2，…，n），gi有1個(gè)配送中心和8個(gè)商店，商店0表示配送中心，配送中心有兩輛載重量為8噸的貨車，要求合理安
8、排車輛行駛路徑，使總運(yùn)輸距離最小。商店之間的相互距離及各商店的商品需求量（見表1、表2）：表1各需求點(diǎn)對(duì)貨物需求量單位：噸表2配送中心與各需求點(diǎn)之間的距離單位：km四、算法改進(jìn)在現(xiàn)有遺傳算法中，個(gè)體的染色體編碼還需要用到最優(yōu)車輛數(shù)。這兩種編碼方案有三個(gè)缺點(diǎn):（1）由于染色體維數(shù)變長(zhǎng)，使組合空間變大，從而降低了搜索到最
