1、目錄1選題依據(jù)和意義(2)1.1研究背景及意義(2)1.2免疫算法的概述(2)1.3免疫算法的研究現(xiàn)狀(3)1.4物流配送中心選址的概述(4)1.5物流配送中心的研究現(xiàn)狀：(4)1.6論文組織結構(5)2基本的免疫算法(5)2.1免疫算法的相關概念介紹：(6)2.2免疫算法的步驟(7)2.3免疫算法流程圖：(8)2.4選擇參數(shù)(11)2.5免疫算法與遺傳算法的比較：(12)3物流配送中心選址的數(shù)學模型的建立(13)4免疫算法物流配送中心選址中的應用：(14)5實驗：(15)小結(18)6總結與展望(18)1選題依據(jù)和意義研究背景及意義科技日新月異的發(fā)展的21世紀，學科之間的融合成為了各學者的研

2、究新方向，各學科之間相互滲透、相互影響、相互作用成為了新世紀科技發(fā)展的新特征。其中，由計算機科學與生命學科相互結合而產(chǎn)生的新型智能算一免疫算法就是其中的代表之一。近年來，隨著我國經(jīng)濟的快速發(fā)展并逐漸走向全球化的道路，物流已成為了經(jīng)濟發(fā)展的重要產(chǎn)業(yè)之一，現(xiàn)如今各大城市都建設有自己的物流配送網(wǎng)絡，這對于城市的招商引資，資源的優(yōu)化配置，經(jīng)濟產(chǎn)業(yè)的運行效率都有著促進作用。物流配送中心作為物流業(yè)重要的環(huán)節(jié)，其選址問題吸引著專家學者投身研究當中。由于物流配送中心一旦選定并進行建設，其位置是固定的，所以在地址的選定上尤為重要。相比較于傳統(tǒng)的選址方法，免疫算法以其收斂速度快，魯棒性強等特點，得到專家學者們的青

3、睞。免疫算法是模仿生物免疫機制，結合基因的進化機理，人工地構造出的一種新型智能搜索算法。免疫算法具有一般免疫系統(tǒng)的特征，免疫算法采用群體搜索策略，一般遵循幾個步月聚產(chǎn)生初始化種群T適應度的計算評價T種群間個體的選擇、交叉、變異T產(chǎn)生新種群”。通過這樣的迭代計算，最終以較大的概率得到問題的最優(yōu)解。相比較于其他算法，免疫算法利用自身產(chǎn)生多樣性和維持機制，保證了種群的多樣性，克服了一般尋優(yōu)過程中特別是多峰值的尋優(yōu)過程中不可避免的“早熟”問題，求得全局最優(yōu)解。大量表明，免疫算法能在較少的迭代數(shù)能快速收斂到全局最優(yōu)。因此，免疫算法在物流配送中心選址問題的研究具有一定的應用價值和參考價值。1.2免疫算法的

4、概述人們對人工免疫算法的研究從免疫學的基礎上開始的。對免疫算法的深入研究，發(fā)現(xiàn)其在解決復雜問題上西安實處了強大的信息處理能力。1958年澳大利亞學者Burnet率先提出了克隆選擇原理21,1960年因此獲得諾貝爾獎。Famer于1986年基于免疫網(wǎng)絡學說理論構造出來的免疫系統(tǒng)的動態(tài)模型，展示了免疫系統(tǒng)與其他人工智能方法相結合的可能性，開創(chuàng)了免疫系統(tǒng)研究的先河。1996年，在日本舉行的國際專題研討會上，提出了免疫系統(tǒng)的概念。1997年IEEE的SMC組織專門成立了人工免疫系統(tǒng)及應用的分會組織。免疫算法,是受生物免疫系統(tǒng)的啟發(fā),推出的一種新型的智能搜索算法。對外界入侵的抗原,受抗原的刺激,生物上淋

5、巴細胞會分泌出相應的抗體,其目標是盡可能保證整個生物系統(tǒng)的基本生理功能得到正常運轉，并產(chǎn)生記憶細胞，以預防下次相同的抗原入侵時，能夠快速的做出反應。借鑒其相關內(nèi)容和知識,并將其應用于工程科學的某些領域,收到了良好的效果。1.3免疫算法的研究現(xiàn)狀雖然起步較晚,但免疫算法已成為當今智能計算的研究熱點之一。已在函數(shù)優(yōu)化，人工神經(jīng)網(wǎng)絡設計，智能控制等領域獲得了成功的應用。近幾年，網(wǎng)絡和智能成為免疫算法發(fā)展的的特征之一,也是其重要應用領域。免疫算法在增強系統(tǒng)的魯棒性，維持機體動態(tài)平衡方面有明顯的成效。經(jīng)過各位學者的不斷專研，免疫算法于其他算法的并行性得到充分發(fā)揮。例如免疫遺傳算法,免疫粒子群算法。這些算

6、法的產(chǎn)生，增加了算法的靈活行。現(xiàn)主要的應用有機器學習，故障診斷，網(wǎng)絡安全，優(yōu)化設計。國內(nèi)雖然對免疫算法的研究起步較晚,但在免疫算法的研究及其應用上也取得了不錯的成果。經(jīng)研究歸納,免疫算法可分為3種情況：（1）基本免疫算法,模擬免疫系統(tǒng)中抗原與抗體的結合原理。（2）基于免疫系統(tǒng)中其他特殊機制抽象出來的免疫算法,如克隆選擇算法。（3）免疫算法與其他智能算法的結合形成的新的算法,如免疫遺傳算法。基于這三種主流的算法,國內(nèi)對免疫算法的研究有對免疫算法的參數(shù)問題的研究1,有對多維教育免疫網(wǎng)絡的研究，增強了教育網(wǎng)絡的安全忸2。有TSP問題求解3、裝配序列規(guī)劃問題求解4、工程項目多目標優(yōu)化研究5、應用免疫算

7、法進行電網(wǎng)規(guī)劃研究6。基于混沌免疫進化算法的物流配送中心選址方案7。目前國內(nèi)的研究主要集中在算法的優(yōu)化改進上,與其他智能算法相結合的研究。1.4物流配送中心選址的概述物流配送中心是物流網(wǎng)絡的基礎節(jié)點,是物流能夠正常運作的前提,同時,配送中心面向客戶,其工作效率不僅直接影響到企業(yè)的業(yè)績，而且還影響客戶的評價。物流配送中心選址的重要性：由于物流配送中心的投資規(guī)模大，占用大量的城市面積，而且其位置一旦建成后，其地理位置相對固定，對物流業(yè)今后的運營情況產(chǎn)生長遠的影響。因此物流配送中心選址的決策必須進行科學的論證后再做定奪。失敗的選址對于物流業(yè)來說是致命的，不僅會導致商品運輸處于無秩序、低效率的狀態(tài)，還

8、可能在運輸成本上吃緊，如果不能滿足客戶的需要，還會影響到企業(yè)的利潤。因此，科學的物流配送中心選址是很有必要的。物流配送中心選址問題，要考慮的因素很多，一般地，主要考慮以下幾個方面：運營成本:縮減成本一直是企業(yè)追求利潤的主要方法之一，在創(chuàng)造相同價值的情況下，成本的縮減成為了企業(yè)間競爭力的決定性因素。運輸效率：降低運輸成本主要的途徑之一就是運輸效率，協(xié)調(diào)好各部門的工作能有效的解決這一問題。服務質(zhì)量：客戶的好評是企業(yè)無形的資產(chǎn)，提供優(yōu)質(zhì)的服務質(zhì)量是一個有遠見的企業(yè)必做的事情。1.5物流配送中心的研究現(xiàn)狀：經(jīng)過幾十年的研究，國內(nèi)外在物流配送中心選址問題的研究日趨成熟，形成了相對完善選址方法，大體可歸納

9、為：(1)定性分析法:定性分析法主要依賴專家和決策者的先知經(jīng)驗、知識，經(jīng)過綜合分析，統(tǒng)籌規(guī)劃來確定其地理位置，這些方法主要有專家分析法、德爾菲法。定性分析法的優(yōu)點在于利于操作，簡單易行，在一定程度上能夠利用豐富的經(jīng)驗來解決選址問題。其確定在于，由于這種選址方法帶有個人主觀因素，往往會犯主觀主義或經(jīng)驗主義的錯誤。缺乏科學性，客觀性。導致選址方案的可靠性不高。定量分析法:定量分析法使用數(shù)學模塊對數(shù)據(jù)進行的分析，通過分析可提供給決策者科學合理的建議，讓并做出投資判斷。這種方法主要有重心法，混合0-1整數(shù)規(guī)劃法，遺傳算法。其優(yōu)點是能通過科學的計算分析，求出比較可靠的解。1.6論文組織結構本論文是以下的

10、結構進行組織的。本論文的第二部分主要介紹免疫算法的原理，并與遺傳算法做對比，比較兩者的優(yōu)劣勢。討論了針對物流配送中心選址問題免疫算法的實現(xiàn)過程。第三部分主要描述物流配送中心選址問題，并且構造出數(shù)學模型、設置約束條件。本文的第四部分描述了在MATLAB平臺上通過免疫算法求解物流配送中心選址問題實驗的結果，并做出分析。本文的第五部分，總結了本論文的研究內(nèi)容，指出本論文的優(yōu)缺點，提出自己的看法。2基本的免疫算法基本免疫算法基于生物免疫系統(tǒng)基本機制，模仿了人體的免疫系統(tǒng)。基本免疫算法從體細胞理論和網(wǎng)絡理論得到啟發(fā)，實現(xiàn)了類似于生物免疫系統(tǒng)的抗原識別、細胞分化、記憶和自我調(diào)節(jié)的功能。一般來說，免疫反應就

11、是當病原體入侵到人體時，受病原體刺激，人體免疫系統(tǒng)以排除抗原為目的而發(fā)生的一系列生理反應。其中B細胞和T細胞起著重要的作用：B細胞的主要功能是產(chǎn)生抗體，且每種B細胞只產(chǎn)生一種抗體。免疫系統(tǒng)主要依靠抗體來對入侵抗原進行攻擊以保護有機體。T細胞不產(chǎn)生抗體，它的直接與抗原結合并實施攻擊，同時還兼顧這調(diào)節(jié)B細胞的活動的作用。成熟的B細胞產(chǎn)生于骨髓中，成熟的T細胞產(chǎn)生于胸腺之中。B細胞和T細胞成熟之后進行克隆增殖、分化并表達功能正是由于這兩種淋巴細胞之間相互影響，相互控制的關系，才使得機體得以維持機體反饋的免疫網(wǎng)絡。IG選掙B細胞免疫算法保留著生物免疫系統(tǒng)中一些主要的元素，免疫算法各元素與生物免疫系統(tǒng)一

12、一對應，如下表所示:生物免疫系統(tǒng)人匸免疫系統(tǒng)抗原待求問題的目標函數(shù)抗體卷求訶題的解抗原識別叵題的識別從記憶細胞產(chǎn)生抗體從先知的成攻經(jīng)驗中產(chǎn)生解淋巴鈿胞分化保持優(yōu)良肉解”抗休的抑制消除剩余候選解2.1免疫算法的相關概念介紹：利用遺焙算子產(chǎn)生新抗依抗原：在生命科學中，能夠誘發(fā)機體的免疫系統(tǒng)產(chǎn)生免疫應答，產(chǎn)生抗體進行免疫作用的物質(zhì)。在算法中特指的是非最優(yōu)個體的基因或錯誤基因。抗體：在生命科學中，是指免疫系統(tǒng)受抗原刺激后，免疫細胞轉化為T細胞并產(chǎn)生能與抗原發(fā)生特異性結合的免疫球蛋白，該免疫球蛋白即為抗體。疫苗：在生物學中指保留了能刺激生物免疫系統(tǒng)的特性，使免疫應答做出反應的預防性生物制品。在免疫算法中

13、指根據(jù)待已有求問題的先知經(jīng)驗中得到的對最佳個體基因的估計。免疫算子：和生命科學中的免疫理論相對應，免疫算子分為全免疫和目標免疫，前者對應著生命科學中的非特異性免疫，后者則對應的是特異性免疫。免疫調(diào)節(jié)：在免疫反應過程中，抗原對免疫細胞的刺激會增強抗體的分化和繁殖。但大量的抗體的產(chǎn)生會降低這一刺激，從而控制抗體的濃度。同時產(chǎn)生的抗體之間也存在著相互刺激和抑制的作用，這種抗原與抗體親和力、抗體與抗體之間的排斥力使抗體免疫反應維持在一定的強度，保證機體的動態(tài)平衡。免疫記憶：能與抗原發(fā)生反應的抗體會成功的作為記憶細胞保存記憶下來，當相似的抗原再次侵入時，這類記憶細胞會被當成功的經(jīng)驗，受刺激并產(chǎn)生大量的抗

14、體，從而大量縮短免疫反應時間。2.2免疫算法的步驟識別抗原：對問題進行可行性分析，構造出合適的目標函數(shù)和制定各種約束條件，作為抗原。產(chǎn)生初始抗體群產(chǎn)生：免疫算法不能直接解決問題空間中的參數(shù)，因此必須通過編碼把問題的可行解表示成解空間中的抗體，一般在解的空間內(nèi)隨機產(chǎn)生的解中作為初始抗體。釆用簡單的編碼可以方便計算，實數(shù)編碼不需要進行數(shù)值的轉換，因此是比較理想的編碼方法，每個抗體為一個實數(shù)向量。對群體中的抗體進行多樣性評價：計算親和力和排斥力，免疫算法對抗體的評價是以期望繁殖概率為標準的，其中包括親和力的計算和抗體濃度的計算。(4)形成父代群體：更新記憶細胞，保留與抗原親和力高的抗體并將它存入記憶

15、細胞中，利用抗體間排斥力的計算，淘汰掉與之親和力最高的抗體。判斷是否滿足結束條件：如果產(chǎn)生的抗體中有與抗原相匹配的的抗體，或滿足結束條件，則停機。利用免疫算子產(chǎn)生新種群：免疫算子包括選擇、交叉和變異等操作。按照優(yōu)勝劣汰”的自然法則選擇。親和力大的抗體有較大的機會被選中。交叉和變異操作以下會介紹到。轉至(3)。如果記憶庫非空，則初始抗體從記憶庫中選擇生成。否則，在隨機產(chǎn)生初始抗體群。每個選址方案用一個長度鄭(各方案選中的配送中心總數(shù)目)的編號序列表示，每個方案編號代表被選為配送中心的需求點的序列。本案例中，釆用實數(shù)編碼方式，由31個城市組成的配送中心，則編號1,2,31代表各配送中心如考慮包含3

16、1個配送中心的問題。1,2,31代表配送中心的編號，從中選出6個作為配送中心。抗體57121629116個元素，表示其編號對應的城市被選為配送中心了。2、解的多樣性評價-親和度計算(1)抗體-抗原親和度(即匹配度)11Iv=min()1,0ViijijijiNjMiiNjMiFCAwdzzGGGG=-其中C是一個較大的正數(shù)，表示如果距離過長，超過了約束條件中的解，則給予懲罰，屬于懲罰函數(shù)。親和團v介于0和1之間，當抗體與(2)抗體-抗體親和度(即相似度)此例中釆用R位連續(xù)方法計算抗體與抗體間的親和力。R位連續(xù)方法實際是一種部分匹配規(guī)則。首先先確定一個R值，R表示親和度的閾值。抗體間的相似度高的

17、判斷條件為兩個編碼中有超過R位或連續(xù)R位相同，否則表示兩個不同的個體。,kvsSvsL其中kv,s表示抗體v與抗體s中相同的位數(shù)，L為一般抗體的長度。如兩個抗體為271861916101215872661921912，共有7,6,19三個中心相同，則kv,s=3,其長度L為9,故其相似度即親和度為1/3。這種相似度好象可用數(shù)據(jù)挖掘中的相似度來計算。3、抗體濃度指的是群體中相似抗體(釆用以上提到的R位連續(xù)方法計算)，在群體抗體中所占的比例，即1,jNCvSvsN6=ZCv表示抗體v的濃度，n表示抗體的總數(shù)，N為抗體的集合。其中：10,=Svs，當Sv,s=1時，Sv,sT,T是一個預定的閥值。4

18、、期望繁殖率在群體中，每個個體的期望繁殖率，由抗體與抗原間親和力Av和該抗體的濃度Cv確定。(1)AvCvPaaAvCv=+-H其中a為多樣性評價參數(shù)(常為0.95),由上式可看出，個體濃度與期望繁殖率成反比，個體的親和度與期望繁殖率成正比。5、免疫算子操作：免疫算子的操作類似于遺傳操作，包括選擇(selection)、交叉(crossover)、變異(mutation)。(1)選擇(selection):選擇操作也稱為復制操作，根據(jù)期望繁殖率來判斷哪些個體會被選中進行克隆。一般來說期望繁殖率大的個體有較大的幾率存在于下一代，而期望繁殖率的的個體在下一代中被淘汰的幾率較大。按照輪盤選擇機制，令

19、Yfi表示群體期望繁殖率之和，fi群體中第i個染色體的期望繁殖率。它的后代在期望繁殖率上占到總期望繁殖率為fi/Zf。(2)交叉(crossover):釆用單點交叉，簡單來說交叉操作就是將各個個體分別作為下一代的父母個體，將它們的部分染色體進行交換。例如:有兩個個體A1和A2:a1:隨機生成一個小于8位的交叉的位數(shù)c，例如c=3，將al和a2的低3位進行交換，al高5位和a2的低3位組成串10001001，a2的高5位與a1的低3位組成串11011110。這兩個就是a1和a2的后代A1、A2。變異：簡單的變異操作主要隨機選擇變異位，然后改變這個變異位上的數(shù)碼。以二進制編碼為例，二進制編碼的每一

20、位只有0或1的取值可能，所以變異可表示為:10100110隨機選擇變異位1到8之間的數(shù)c，假如是c=5,從右往左數(shù)第5位進行變異操作，第5位為0，把0變成1，得到的結果為變異后的結果:1“1”10I”102.4選擇參數(shù)合理的選擇參數(shù)，能夠大幅度提高算法的效率。經(jīng)過各學者多年的實驗，交叉概率取0.6到0.95之間，變異概率取0.001到0.01之間。種群的規(guī)模對算法的效率的影響也是比較大的。種群規(guī)模太小不利于進化，規(guī)模太大使得程序運行時間過長。一般的種群規(guī)模定為30到100為宜。2.5免疫算法與遺傳算法的比較:遺傳算法相對于免疫算法起步比較早，發(fā)展比較成熟，但有時候，免疫算法在求解多峰值的優(yōu)化問

21、題上展現(xiàn)出顯著的優(yōu)勢11。免疫算法類似于遺傳算法，釆用群體搜索策略，在大體的算法步驟上一樣。主要的區(qū)別在于對個體的評價上。遺傳算法對個體的評價上主要通過個體的適應度的計算得到的，包括個體的選擇也是以適應度為指標。它更著重于問題的全局最優(yōu)解。而免疫算法則通過計算親和度得到的，親和度包括抗原與抗體的親和度(親和力)，抗體與抗體間的親和度(排斥力)。所以在保持全局的多樣性以及收斂速度方面免疫算法要更優(yōu)于遺傳算法，因此在求解多峰值函數(shù)尋優(yōu)問題上也更具優(yōu)勢。相比較i于遺傳算法，免疫算法更真實的反應了免疫系統(tǒng)的多樣性，對個體的評價各全面，對個體的選擇更合理。免疫算法擁有遺傳算法中沒有的記憶細胞10。它具有

22、特殊的免疫記憶的特性，在每一次迭代之后，可以將有利于解決問題的特征信息存入記憶細胞中，以便下次遇到同樣問題上能夠利用先前的特征信息或成功經(jīng)驗，更快的找出問題的解決辦法，提高了解決問題的速度。另一方面，免疫算法還克服了早熟的現(xiàn)象9。用遺傳算法求解問題是，當種群規(guī)模較小時，如果在進化初期出現(xiàn)適應度較高的個體，由于該個體的繁殖率過快，往往不利于種群多樣性的產(chǎn)生，從而出現(xiàn)早熟收斂的情況。所謂早熟，是指當種群規(guī)模較小時，如果在進化初期出現(xiàn)適應度較高的個體，由于該個體繁殖率過快，往往不利于種群多樣性的產(chǎn)生，從而出現(xiàn)早熟收斂的情況。免疫算法引進了濃度機制，計算抗體的濃度，通過對抗體的促進或抑制，調(diào)節(jié)抗體的濃

23、度，特別是對濃度過大的抗體的抑制作用，有效的預防了由于濃度過大而導致算法過早的收斂到全局最優(yōu)，降低群體的多樣性。經(jīng)過對比以上兩種算法，不能片面地說那個算法更好，哪個算法更優(yōu)，要根據(jù)具體問題具體分析，甚至可以結合兩種算法進行求解，揚長補短。有人提出來要，將免疫概念及其理論應用于遺傳算法，在保留原算法優(yōu)良特性的前提下，力圖有選擇、有目的地利用待求問題中的一些特征信息或知識來抑制其優(yōu)化過程中出現(xiàn)的退化現(xiàn)象。3物流配送中心選址的數(shù)學模型的建立為了方便建立數(shù)學模型，物流配送中心選址問題應該滿足以下條件：(1)配送中心的庫存量能滿足其所覆蓋服務區(qū)域客戶的需求量。(2)一個客戶僅由一個配送中心服務，不得跨區(qū)

24、域送貨。(3)已知各客戶的需求量。費用由配送中心到客戶的運輸費用決定，不考慮工廠到配送中心的運輸費用。基于以上的設計思路，可構造出以下的數(shù)學模型：問題的目標函數(shù)為各配送中心到其所服務的客戶的需求量和距離的乘積=達到最小，即：miniijijiiNjMFwdzGG=ZZ;(1)約束條件為：1ijijMzG=ZiNW;(2)ijjhz,iN6,ijMW(3)jjMhpG=Zijz，0,1jhG,iN6,ijMG,(5)ijds(6)1,2,3.nN6是所有需求點的序列集合iw表示需求點i的需求量，ijd表示需求點i離它最近的需求點j的距離。ijZ是0-1變量，表示需求點與配送中心的配送關系，如果j

25、Z=1表示需求點i由配送中心j供應，否則ijZ=0;jh為0-1變量，當jh=1時，表示j被選為配送中心，否則為0。S表示配送中心所能夠服務到的最大距離。iM表示被需求點i小于的距離小于最大距離S的配送中心的集合。P表示配送中心的數(shù)目。各約束條件的含義為：公式(2)表示一個需求點只能由一個配送中心進行配送。公式(3)保證各需求點只能由配送中心配送，也就是說，只有配送中心才能有配送的權利，沒有配送中心的地方不會有需求點。公式(4)確定了配送中心的個數(shù)。公式(5)是0-1變量。公式(6)保證了配送中心的配送距離不會超過配送所能達到的上限。4免疫算法物流配送中心選址中的應用：Step1:識別抗原，將

26、種群信息定義成一個結構體。包括：個體適應度，個體濃度，個體繁殖概率。Step2:產(chǎn)生初始抗體群，記錄下每個個體的最優(yōu)適應度和平均適應度。Step3:抗體的多樣性評價，需要的操作有：抗原與抗體親和度(適應度)的計算，抗體濃度的計算。對親和度和抗體濃度的綜合分析，可求得個體的繁殖概率。Step4:根據(jù)個體繁殖概率，可知個體的優(yōu)劣情況更新父代種群，更新記憶庫。這里釆用精英選擇策略，將適應度值較高的前S個個體保存起來，避免因濃度過高而被淘汰。Step5：經(jīng)過選擇、交叉、變異操作，在從記憶庫中的抗體，形成新種群。下面根據(jù)以上的思路，在MATLAB上進行仿真實驗，驗證其正確性。5實驗：為證明算法的可行性，

27、將國內(nèi)31個城市作為研究對象8，各城市的坐標以及各需求點的需求量由下表所示，從31個城市中選擇6個城市作為配送中心。城市編號、坐標、各需求點的需求量如下表所示。物流配送中心選址方案:ixW11(Uj,Vj)Ji(Uj,Vj)Ji(Uj,Vj)j1(1304,2312)2012(2562,1756)4023(3429,1908)802(3639.1315)9013(2788,1491)40M(3507,2376)703(4177.2244)9014(2381,1676)4025(3394,2643)SO44、6.7LIL12s13.15.16.本文在對物流配送中心選址問題所構造的數(shù)學模型的基礎上，通過免疫算法對問題的進行求解，在算法中結合遺傳算法，引入了克隆選擇、抗體抑制等思想，使算法的尋優(yōu)能力更強。從實驗的結果看出，算法的迭代次數(shù)較少，收斂速度快，能在較短時間內(nèi)得出全局最優(yōu)，彰顯出算法獨特的優(yōu)勢。實驗結果