【正文】 發(fā)展給社會(huì)的發(fā)展 、生產(chǎn)和管理，人們的生活和就業(yè)乃至整個(gè)政府部門的職能以及整個(gè)社會(huì)的法律制度都帶來了巨大的影響， 因此物流業(yè)被認(rèn)為是國民經(jīng)濟(jì)發(fā)展的動(dòng)脈和基礎(chǔ)產(chǎn)業(yè)，被形象地喻為促進(jìn)經(jīng)濟(jì)發(fā)展的 “ 加速器 ” 。 在物流系統(tǒng)的運(yùn)作中，配送中心的任務(wù)就是根據(jù)各個(gè)用戶的需求及時(shí)、準(zhǔn)確和經(jīng)濟(jì)地配送商品貨物。配送中心是連接供應(yīng)商與客戶的中間橋梁，其選址方式往往決定著物流的配送距離和配送模式，進(jìn)而影響著物流系統(tǒng)的運(yùn)作效率；另外物流中心的位置一旦被確定，其位置難以再改變。因此，研究物流配送中心的選址具有重要的理論和現(xiàn)實(shí)應(yīng)用意義，一般說來，物流中心選址 模型是非凸和非光滑的帶有復(fù)雜約束的非線性規(guī)劃模型，屬 NPhard 問題。 免疫算法 （ Immune Algorithm， IA） 的基本思想 生物免疫系統(tǒng)是一個(gè)高度進(jìn)化的生物系統(tǒng)，它旨在區(qū)分外部有害抗原和自身組織，從而保持有機(jī)體的穩(wěn)定。從計(jì)算的角度來看，生物免疫系統(tǒng)是一個(gè)高度并行、分布、自適應(yīng)和自組織的系統(tǒng)，具有很強(qiáng)的學(xué)習(xí)、識別和記憶能力。 （ 1）基于免疫響應(yīng)過程的 IA，如圖 圖 生物免疫機(jī)制的抽象模型 . 1 Abstract model of biological immune mechanism 模仿這一過程，免疫遺傳算法是一種改進(jìn)的具有免疫功能的優(yōu)化算法。算法將待求 16 解問題的目標(biāo)函數(shù)對應(yīng)為抗原，問題的解對應(yīng)為抗體，在抗體與抗原自適應(yīng)迭代過程中尋找問題的最優(yōu)解。在解決實(shí)際問題時(shí)，各個(gè)步驟有對應(yīng)形式；抗原對應(yīng)待解決問題的輸入，如目標(biāo)函數(shù)，問題約束；抗體對應(yīng)優(yōu)化問題的最優(yōu)解；親和力對應(yīng)解的評估；記憶細(xì)胞分化對應(yīng)保留優(yōu)化解；抗體促進(jìn)和抑制對應(yīng)優(yōu)化解的促進(jìn)、非有化解的刪除；抗體產(chǎn)生對 應(yīng)優(yōu)化解的出現(xiàn)等。與遺傳算法相比，人工免疫遺傳算法通過細(xì)胞的分裂會(huì)產(chǎn)生大量的抗體，使種群呈現(xiàn)出多樣性，有效的避免了遺傳算法陷入局部收斂的現(xiàn)象；人工免疫算法是將目標(biāo)函數(shù)作為抗原，使抗體直接與問題相關(guān)聯(lián)，解決了遺傳算法中收斂方向無法控制的缺陷；通過記憶與抗原親和力高的抗體，促進(jìn)了問題快速求解，當(dāng)遇到侵入的抗原同類或相似時(shí)，可快速生成相應(yīng)的抗體，從而提高總體的搜索能力 [13]。 ① 抗原識別以及初始抗體的產(chǎn)生 針對待求解問題的特征，判別系統(tǒng)是否曾經(jīng)求解過此類問題，如有則從記憶細(xì)胞庫中搜尋該類問題的記憶抗體，否則隨機(jī) 產(chǎn)生初始抗體。 ② 抗體產(chǎn)生 由于抗原的出現(xiàn)，抗體產(chǎn)生細(xì)胞（ B 細(xì)胞）不斷分化、增殖，形成大量抗體。抗體的產(chǎn)生方式主要由新陳代謝作用和交叉與變異產(chǎn)生。在免疫調(diào)節(jié)機(jī)制下，抗體群體不斷更新進(jìn)化，最終消滅抗原，即搜索到問題的解。 ③ 抗體間產(chǎn)生的刺激與抑制 基于濃度的調(diào)節(jié)機(jī)制，抗體的濃度定義為群體中相似抗體所占的比率。群體更新時(shí)，親和度高的抗體的濃度不斷提高，到達(dá)一定的值時(shí)，則抑制這種抗體的產(chǎn)生，反之則相應(yīng)提高濃度低的抗體的產(chǎn)生和選擇概率。保證抗體的多樣性，避免早熟。 （ 2）免疫系統(tǒng)具有如下的特征： ① 產(chǎn)生多種抗體的能力。通 過細(xì)胞的分裂和分化作用，免疫系統(tǒng)可以產(chǎn)生大量的抗體來抵御各種抗原。 ② 自我調(diào)節(jié)機(jī)構(gòu)。免疫系統(tǒng)具有維持免疫平衡的機(jī)制，通過對抗體的抑制作用和促進(jìn)作用，能自我調(diào)節(jié)產(chǎn)生各種適當(dāng)數(shù)量的必要的抗體。 ③ 免疫記憶功能。產(chǎn)生抗體的部分細(xì)胞會(huì)作為記憶細(xì)胞被保存下來，對于以后侵入的同類抗原，相應(yīng)的記憶細(xì)胞會(huì)迅速激發(fā)產(chǎn)生大量的抗體。 免疫算法正是受生物免疫系統(tǒng)啟發(fā)，在免疫學(xué)理論基礎(chǔ)上發(fā)展起來的一種新型的智能的計(jì)算方法。他利用免疫系統(tǒng)的多樣性產(chǎn)生和維持機(jī)制來保持群體的多樣性，克服了一般尋優(yōu)過程尤其是多峰函數(shù)尋優(yōu)過程中很難處理的“早熟 ”問題，最終求得全局最優(yōu)解。與其他智能算法相比，免疫算法的研究起步相當(dāng)晚，其發(fā)展歷史只有二十幾年。Fanmer 等于 1986 年率先基于免疫網(wǎng)絡(luò)學(xué)說構(gòu)造了免疫系統(tǒng)的動(dòng)態(tài)模型，并討論了免疫系統(tǒng)與其他人工智能算法的聯(lián)系，從而開創(chuàng)了免疫系統(tǒng)的研究。 免疫算法和遺傳算法都是采用群體搜索策略，并且強(qiáng)調(diào)群體中個(gè)體之間的信息交換，因此有許多相似之處，比如兩者具有大致相同的算法結(jié)構(gòu)，都有經(jīng)過“初始種群產(chǎn)生→評價(jià)標(biāo)準(zhǔn)計(jì)算→種群間個(gè)體信息交換→新種群產(chǎn)生”這一循環(huán)過程，最終以較大的 17 概率獲得問題的最優(yōu)解；另外，兩者之間本質(zhì)上具有并行 性，并且具有與其他智能算法相結(jié)合的固有優(yōu)勢。 免疫算法和遺傳算法之間也存在一些區(qū)別，主要表現(xiàn)為對個(gè)體的評價(jià)、選擇及產(chǎn)生的方式不同。遺傳算法中個(gè)體的評價(jià)是通過計(jì)算個(gè)體適應(yīng)度得到的，算法選擇父代個(gè)體的唯一標(biāo)準(zhǔn)時(shí)個(gè)體的適應(yīng)度；而免疫算法對個(gè)體的評價(jià)是通過計(jì)算親和度得到的，個(gè)體的選擇也是通過以親和度為基礎(chǔ)來進(jìn)行的。個(gè)體的親和度包括抗體 — 抗原之間的親和度（匹配程度）和抗體 — 抗體之間的親和度（相似度），他反應(yīng)了真實(shí)的免疫系統(tǒng)的多樣性，因此免疫算法對個(gè)體的評價(jià)更加的具體全面，其個(gè)體選擇方式也更加合理。此外，遺傳算法通過交 叉、變異等等遺傳操作產(chǎn)生新個(gè)體，而在免疫算法中，雖然也存在交叉、變異等等固有的遺傳操作也存在廣泛地應(yīng)用，但是新抗體的產(chǎn)生還可以借助克隆選擇，免疫記憶，疫苗接種等遺傳算法中所欠缺的機(jī)理，同時(shí)免疫算法中還對抗體的產(chǎn)生進(jìn)行促進(jìn)或者抑制，體現(xiàn)免疫反應(yīng)的自我調(diào)節(jié)功能，保證了個(gè)體的多樣性。 本案例把免疫優(yōu)化算法用于物流配送中心選址問題中。在考慮問題中的約束條件和優(yōu)化目標(biāo)的基礎(chǔ)上，建立了物流配送中心選址問題的數(shù)學(xué)模型，并采用了免疫優(yōu)化算法求解最佳物流配送中心選址模型。 問題描述 在物流配送中心選址中作如下假設(shè) [14]： （ 1）配送中心的規(guī)模容量總能夠滿足需求點(diǎn)的需求，并根據(jù)配送輻射范圍內(nèi)的需求量確定； （ 2）一個(gè)需求點(diǎn)僅由一個(gè)配送中心供應(yīng)； （ 3）不考慮工廠到配送中心的運(yùn)輸費(fèi)用。 基于以上假設(shè)，建立如下模型。該模型是一個(gè)選址 /分配模型，在滿足距離上限的情況下，需要從 N 需求點(diǎn)中找出配送中心并向各需求點(diǎn)配送物品，目標(biāo)函數(shù)是個(gè)配送中心到需求點(diǎn)的需求量和距離的乘積之和最小目標(biāo)函數(shù)為 [15] ? ?? ?? N Mj ijijii ZdF imin ? （ 3. 1） 約束條件為 NiZiMj j???? ,1i （ 3. 2） Ijj MjNihZ ??? ,i （ 3. 3） phIMj j??? （ 3. 4） ? ? ijij MjNihZ ??? ,1,0, （ 3. 5） sdij ? （ 3. 6） 模型中有兩類符號 ， 即模型的決策變量和模型參數(shù) 。 18 記憶細(xì)胞產(chǎn)生 Y N 抗原識別 初始抗體適應(yīng)度計(jì)算 初始抗體產(chǎn)生過 是否滿足終止條件 抗體產(chǎn)生（選擇、交叉、變異） 抗體產(chǎn)生的促進(jìn)和抑制 輸出結(jié)果 決策變量： ijZ 為 01 決策變量，表示用戶和物流中心的服務(wù)需求分配關(guān)系，當(dāng)其為 1 時(shí)，需求點(diǎn) i由配送中心 j 供應(yīng)，否則 ijZ 為 0； jh 也為 01 變量，當(dāng)其位 1 時(shí)，表示點(diǎn) j 被選為配送中心； 模型參數(shù)： ? ??2,1?N 是所有需求點(diǎn)的序號集合； iM 為到需求點(diǎn) i的距離小于 s 的備選配送中心集合， ；, NMNi i ?? i? 表示需求點(diǎn)的需求量；表示從需求點(diǎn) i 到離它距離最近的配送中心 j 的距離； s 為新建配送中心離它服務(wù)的需求點(diǎn)的距離的上限 [16]。 解決 基本 思路 和求解 步驟 （ 1） 算法流程如圖 所示： 圖 3. 2 免 疫算法流程圖 . 2 Immune Algorithm flow chart 免疫算法具體實(shí)現(xiàn)步驟如下： Step l：分析問題：對問題及其解的特性進(jìn)行分析，設(shè)計(jì)解的合適表達(dá)形式； Step2：產(chǎn)生初始抗體群：群體產(chǎn)生 N 個(gè)個(gè)體并從記憶庫中提取 m 個(gè)個(gè)體構(gòu)成初始種群，其中的 m 為記憶庫中個(gè)體的數(shù)量； Step3：對上述群體中各個(gè)抗體進(jìn)行評價(jià)：在本算法中對個(gè)體的評價(jià)是以個(gè)體的期望繁殖率 P 為標(biāo)準(zhǔn)的； Step 4：形成父代群體：將初始群體按期望繁殖率 P 進(jìn)行降序排列，并取前 N 個(gè)個(gè)體構(gòu)成父代種群 ；同時(shí)取前 m 個(gè)個(gè)體存入記憶庫中； 19 Step 5：判斷是否滿足結(jié)束條件，是則結(jié)束；反之，則繼續(xù)下一步操作； Step6：新群體的產(chǎn)生：給予步驟 Step4 的計(jì)算結(jié)果對抗體群體進(jìn)行選擇、交叉、變異操作得到新種群，在從記憶庫中取出記憶的個(gè)體，共同構(gòu)成新一代群體； Step7：轉(zhuǎn)去執(zhí)行 Step3。 （ 2）初始抗體群的產(chǎn)生 如果記憶庫非空，則初始抗體群從記憶庫中選擇生成。否則，在可行解空間中隨機(jī)產(chǎn)生初始抗體群。此處采用簡單編碼方式。每個(gè)選址方案可形成一個(gè)長度為 p 的抗體（ p表示配送中心數(shù)量），每個(gè)抗體代表被選為配送中心的 需求點(diǎn)的序列。 （ 3）解的多樣性評價(jià) 抗體與抗原間親和力 抗體抗原之間的親和力用于表示抗體對抗原的識別程度，此處針對上述配送中心選址的模型設(shè)計(jì)親和力函數(shù) VA ? ? ? ?? ? ? ? ?????????? ???????? ????Ni Mj NiijijVViCZdFA0,1Zmin11iMjiji? （ 3. 7） 其中， VF 為目標(biāo)函數(shù)；分母中第二項(xiàng)表示為違反距離約束的解給予懲罰， C 取一個(gè)較大的正數(shù)。 ① 抗體與抗體之間親和力 抗體與抗 體之間的親和力反映了抗體之間的相似程度。此外借鑒由 Forrest 等提出的 R位連續(xù)方法計(jì)算抗體與抗體之間的親和力。 R位連續(xù)方法實(shí)際是一種部分匹配原則。該方法的關(guān)鍵是確定一個(gè) R 值，代表親和度判斷的閥值。兩種個(gè)體編碼有超過 R 位或者連續(xù) R 位的編碼相同，則表示這兩種抗體近似“相同”，否則表示這兩種個(gè)體不同。此處抗原的編碼方法各位之間不需要考慮排序，可參考變形的 R 位連續(xù)方法計(jì)算抗體之間的親和度，即 LkS SVSV , ? （ 3. 8） 其中， SVk, 為抗體 V 與抗體 S 中相同的位數(shù)； L 為抗體的長度。 ② 抗體濃度 抗體的濃度 vC 即群體中相似抗體所占的比例，即 ??? N SVSNC j ,v1 （ 3. 9） 其中， N 為抗體總數(shù)； ；其他,0,1 , ??? ?? TSS SVSVT 為預(yù)先設(shè)定的一個(gè)閥值。 ③ 期望繁殖率 在群體中，每個(gè)個(gè)體的期望繁殖率由抗體與抗原間的親和力 VA 和體 濃度 vC 兩部分 20 共同決定，即 VVACP ??????（ 1 ） （ ） 其中， ? 為常數(shù)。由上式可見，個(gè)體適應(yīng)度越高，則期望繁殖率越大；個(gè)體濃度越大，則期望繁殖率越小。這樣既鼓勵(lì)了適應(yīng)度高的個(gè)體，同時(shí)也抑制了濃度高的個(gè)體，從而確保了個(gè)體多樣性。 免疫算法在抑制高濃度個(gè)體時(shí)，與抗原親和度最高的個(gè)體也可能因其濃度高而受到抑制，從而導(dǎo)致已求得的最優(yōu)解丟失，因此采取精英保留策略，在每次更新記憶庫時(shí)先將與抗 原親和度高的若干個(gè)個(gè)體存入記憶庫，在按照期望繁殖率將剩余群體中優(yōu)秀個(gè)體存入記憶庫中。 （ 4）免疫操作 ① 選擇：按照輪盤賭選擇機(jī)制進(jìn)行選擇操作，個(gè)體被選擇的概率即為式子計(jì)算出的期望繁殖率 ② 交叉：本文采用單點(diǎn)交叉法進(jìn)行交叉操作 ③ 變異：采用常用的變異方法，即隨機(jī)選擇變異位進(jìn)行變異 仿真實(shí)驗(yàn) 及結(jié)果分析 為了證明算法的可行性和有效性，采集了全國 31 個(gè)城市的坐標(biāo)，每個(gè)用戶的位置及其物資需求量由表 給 出，這里的物資需求量是經(jīng)過規(guī)范處理后的數(shù)值，并不代表實(shí)際值，從中選擇 6 個(gè)作為物流配送中心。 表 用戶的位置及其物資需求量 . 1 The location of the user and demand for goods j Uj Vj bj j Uj Vj bj j Uj Vj bj 1 1304 1688 20 12 2562 2244 40 23 3429 1624 80 2 3639 2685 90 13 2788 2509 40 24 3507 1357 70 3 4177 1756 90 14 2381 2324 40 25 3394 799 80 4 3712 2601 60 15 1332 3305 20 26 3439 760 40 5 3488 2465 70 16 3715 2322 80 27 2935 450 40 6 3326 2444 70 17 3918 1821 90 28 3140 1643 60 7 3238 2771 40 18 4061 1630 70 29 2545 1174 70 8 4196 2956 90 19 3780 1788 100 30 2778 1025 50 9 4312 3210 90 20 3676 1422 50 31 2370 1624 30 10 4386 3430 70 21 4029 1162 50 11 3007 2030