多粒子群混合算法求解虛擬組織服務(wù)資源配置

［摘 要］ 為了提高虛擬組織服務(wù)資源配置的效率，本文提出了一種多粒子群混合算法。該混合算法將多種群與線性搜索相結(jié)合，在算法優(yōu)化過程中，通過多個(gè)粒子種群協(xié)同來控制種群的多樣性，將多種群中較優(yōu)的粒子進(jìn)行復(fù)制，同時(shí)在每個(gè)種群中對(duì)單個(gè)粒子進(jìn)行維變量變換。實(shí)驗(yàn)結(jié)果表明該方法具有可行性。

［關(guān)鍵詞］ 虛擬組織； 資源配置； 多粒子群

doi : 10 . 3969 / j . issn . 1673 - 0194 . 2011 . 09 . 020

［中圖分類號(hào)］F270； C931.1 ［文獻(xiàn)標(biāo)識(shí)碼］A ［文章編號(hào)］1673 - 0194（2011）09- 0080 - 03

近年來，大型企業(yè)通過不斷重構(gòu)內(nèi)部流程和信息系統(tǒng)來減少浪費(fèi)、降低成本和提高利潤。但中小型組織成本依然很高，所以組織內(nèi)部的協(xié)作就變得極其重要，如虛擬組織在面臨任務(wù)的時(shí)候能在短時(shí)間內(nèi)快速形成［１］。通過虛擬組織達(dá)到資源和技能的共享，以此來完成總體目標(biāo)［２］。虛擬組織滿足了敏捷企業(yè)迅速聚集新資源的需求，特別是在生產(chǎn)制造企業(yè)提供的產(chǎn)品及服務(wù)往往是全局性的，而為了滿足大范圍顧客不確定的個(gè)性化服務(wù)需求，單靠企業(yè)本身的力量是無法完成的，企業(yè)必須創(chuàng)新服務(wù)運(yùn)營模式，充分利用外部力量，建立基于產(chǎn)品及服務(wù)的虛擬組織。目前虛擬組織理論與方法的研究主要集中在生產(chǎn)制造企業(yè)的伙伴選擇，完成制造資源的優(yōu)化配置，而對(duì)于服務(wù)型資源的優(yōu)化配置研究較少［１－３］。如目前的大型機(jī)器設(shè)備的維修保養(yǎng)、貿(mào)易服務(wù)、大型商務(wù)策劃等是服務(wù)型虛擬組織主要完成的任務(wù)。

在服務(wù)型虛擬組織的構(gòu)建過程中，服務(wù)資源的優(yōu)化配置是一個(gè)非常關(guān)鍵的問題。服務(wù)資源配置屬于非線性、多目標(biāo)混合整數(shù)規(guī)劃問題，在構(gòu)建模型時(shí)應(yīng)考慮多方面的因素，關(guān)于此類模型求解多采用線性規(guī)劃法、遺傳算法、模擬退火算法和群智能算法。其中粒子群優(yōu)化算法是一種全局優(yōu)化算法，能夠通過群體中個(gè)體之間的協(xié)助和信息共享來尋找最優(yōu)解，可以大大減少算法的執(zhí)行時(shí)間。很多研究者從不同的角度對(duì)傳統(tǒng)粒子群算法進(jìn)行了改進(jìn)，以提高算法性能，同時(shí)將其應(yīng)用在多個(gè)領(lǐng)域。王文斌［４］提出一種非均衡變異離散粒子群算法的全局最優(yōu)Wｅｂ服務(wù)選擇方法，提高了服務(wù)選擇質(zhì)量。蔡國榕［５］提出了一種具有自適應(yīng)遷移能力的多種群算法，改善了算法的優(yōu)化性能。Ｒａｊｅｓｈ Ｋｕｍａｒ［６］針對(duì)電力調(diào)度提出了基于混合多代理的粒子群優(yōu)化算法，能夠更加準(zhǔn)確地搜索到最優(yōu)解。Ｒ．Ｊ．Ｋｕｏ［７］將粒子群算法和模糊神經(jīng)網(wǎng)絡(luò)整合在一起用于供應(yīng)商選擇，在選擇中同時(shí)考慮了定量因素和定性因素。雖然目前粒子群算法研究較多，但將粒子群算法應(yīng)用在復(fù)雜服務(wù)資源的有效配置中的文獻(xiàn)很少見。

本文在以上文獻(xiàn)研究的基礎(chǔ)上，采用多粒子群混合算法對(duì)資源共享和配置進(jìn)行求解。文章的第一部分給出問題的數(shù)學(xué)模型；第二部分提出多粒子群混合算法，首先對(duì)子群中較優(yōu)粒子進(jìn)行交叉復(fù)制，同時(shí)采用線性搜索提高算法準(zhǔn)確性；第三部分通過一個(gè)具體實(shí)例對(duì)算法進(jìn)行分析，驗(yàn)證了算法的有效性。

１問題的數(shù)學(xué)模型

問題的數(shù)學(xué)模型可以描述如下：

式（１）中Ｘｉ ｊ表示決策變量，對(duì)于第ｉ個(gè)子任務(wù)如果式（１）中Ｘｉ ｊ表示決策變量，對(duì)于第ｉ個(gè)子任務(wù)如果選擇第ｊ個(gè)候選資源時(shí)決策變量為１，否則為０。Ｔｌｉｎｋｉｊ表示對(duì)于第ｉ個(gè)子任務(wù)如果選擇第ｊ個(gè)候選資源時(shí)，由該虛擬組織單元到客戶的運(yùn)輸時(shí)間。Ｔｓｅｒｖｉｃｅｉｊ表示對(duì)于第ｉ個(gè)子任務(wù)如果選擇第ｊ個(gè)候選資源時(shí)，該候選資源的服務(wù)時(shí)間。Ｔｍａｘ為客戶能接受的最晚服務(wù)完成時(shí)間。ｍ為所有資源的個(gè)數(shù)。式（２）中Ｃｌｉｎｋｉｊ表示對(duì)于第ｉ個(gè)子任務(wù)如果選擇第ｊ個(gè)候選資源的運(yùn)輸成本。Ｃｓｅｒｖｉｃｅｉｊ表示對(duì)于第ｉ個(gè)子任務(wù)如果選擇第ｊ個(gè)候選資源的服務(wù)成本。Ｃｍａｘ表示客戶能接受的最大服務(wù)成本。ｎ為子任務(wù)的個(gè)數(shù)。式（３）中Ｓｉ ｊ表示候選資源的服務(wù)信任度。在式（４）中，將多目標(biāo)最優(yōu)化轉(zhuǎn)化為單目標(biāo)最優(yōu)化，ｗｔ、ｗｃ、ｗｓ表示服務(wù)時(shí)間、服務(wù)成本和服務(wù)質(zhì)量的權(quán)重系數(shù)。式（５）表示權(quán)重系數(shù)總和為１，ｋｉ表示子任務(wù)ｉ的候選資源的數(shù)量。式（６）和（７）表示客戶服務(wù)子任務(wù)只能由一個(gè)資源提供服務(wù)。式（８）、（９）、（１０）表示時(shí)間、成本和服務(wù)質(zhì)量的約束。式（１０）中Ｓｍｉｎ表示客戶可接受的最低服務(wù)滿意度。

２多粒子種群求解模型

基本粒子群算法對(duì)種群多樣性作用比較直接，較難達(dá)到理想的效果，為了解決這個(gè)問題，文獻(xiàn)［５］提出利用群熵的概念，根據(jù)粒子在各個(gè)定長區(qū)間的分布情況來刻畫種群多樣性。本文為了保證種群的多樣性，防止過早收斂，采用低層次種群交叉復(fù)制，高層次種群求解全局最優(yōu)。

２．１編碼設(shè)計(jì)

根據(jù)客戶需求服務(wù)資源的特點(diǎn)，本研究采用整數(shù)編碼方式。在多種群混合算法中，每個(gè)粒子的位置矢量代表一個(gè)問題解。每個(gè)粒子群數(shù)為ｎ，維度為ｍ，則每個(gè)粒子位置矢量ｐｉ ＝ （ｐｉ１，…，ｐｉ ｊ，…，ｐｉｍ），其中ｐｉ ｊ表示一種候選服務(wù)資源。

２．２子群交叉復(fù)制策略設(shè)計(jì)

在粒子群迭代的過程中，最優(yōu)粒子運(yùn)動(dòng)方向較盲目，這樣容易使得算法陷入局部優(yōu)化，且不易跳出。本文建立多個(gè)粒子群以豐富種群多樣性，從而提高全局搜索能力。設(shè)粒子群個(gè)數(shù)為Ｓ，在算法搜索的初期，將所有子群中粒子按適應(yīng)度進(jìn)行排序，選取Ｓ個(gè)較優(yōu)的粒子，將其復(fù)制到每個(gè)子群中，并替換掉每個(gè)子群中適應(yīng)度較差的Ｓ個(gè)粒子。

２．３多粒子群協(xié)同優(yōu)化

多粒子群協(xié)同優(yōu)化算法的基本思想是利用Ｓ（Ｓ ＞ １）個(gè)獨(dú)立的粒子群進(jìn)行協(xié)同優(yōu)化。這是一種雙層的結(jié)構(gòu)：其中底層的（Ｓ － １）個(gè)粒子群根據(jù)本粒子群搜索到的最優(yōu)點(diǎn)來更新粒子的速度，而上次的粒子群是根據(jù)全部粒子的歷史最優(yōu)值來修正速度。這樣通過前（Ｓ － １）個(gè)粒子群的獨(dú)立搜索來保證尋優(yōu)搜索過程可以在問題空間的較大范圍內(nèi)進(jìn)行。

２．４非均衡線性搜索策略

文獻(xiàn)［８］將線性搜索法和標(biāo)準(zhǔn)粒子群算法有機(jī)結(jié)合起來解決復(fù)雜問題，將粒子每一維單獨(dú)進(jìn)行適當(dāng)?shù)淖兓瘉硭阉鳌１疚脑诖嘶A(chǔ)上引入非均衡變異的思想，對(duì)粒子維度變量的變化采用遞減的方法，以此加快算法的收斂。函數(shù)設(shè)計(jì)為：

σ ＝ ０．８，ｔｍａｘ ＝ １ ０００

２．５混合算法設(shè)計(jì)

（１） 設(shè)置初始參數(shù)，包括種群數(shù)Ｓ，子群規(guī)模ｎ，加速因子ｃ１、ｃ２，慣性權(quán)值ｗ，迭代次數(shù)ｔｍａｘ。

（２） 對(duì)于第ｉ個(gè)子群，隨機(jī)產(chǎn)生ｎ個(gè)粒子，為每個(gè)子群隨機(jī)生成位置參數(shù)Ｘｉ，隨機(jī)生成初始速度Ｖｉ。檢查粒子位置的可行性，獲取粒子的個(gè)體最優(yōu)初始位置ｐｂｅｓｔ和群體最優(yōu)位置ｇｂｅｓｔ。

（３） 算法迭代開始：

① 計(jì)算每個(gè)子群粒子的適應(yīng)值，并對(duì)適應(yīng)值進(jìn)行排序，統(tǒng)計(jì)所有子群中較優(yōu)的ｎ個(gè)粒子，將其替換每個(gè)子群中適應(yīng)值較差的ｎ個(gè)粒子。

② 按照非均衡線性搜索策略對(duì)每個(gè)子群的粒子進(jìn)行位置變換。

③ 對(duì)每個(gè)粒子，更新粒子的位置和速度。

④ 若迭代次數(shù)達(dá)到設(shè)定值，則輸出優(yōu)化結(jié)果，否則轉(zhuǎn)（３）。

３實(shí)例分析

在本研究中以某個(gè)生產(chǎn)制造企業(yè)制造服務(wù)資源的需求來分析虛擬服務(wù)組織資源優(yōu)化配置的問題。生產(chǎn)制造企業(yè)的機(jī)器設(shè)備需要定期保養(yǎng)，當(dāng)出現(xiàn)故障時(shí)需要維修，形成客戶服務(wù)任務(wù)。為滿足客戶的需求，虛擬服務(wù)組織必須在有限的時(shí)間內(nèi)完成客戶的服務(wù)任務(wù)，快速完成組織內(nèi)資源的有效配置和調(diào)度，包括人力資源和設(shè)備資源、有形資源和無形資源。在本文中，企業(yè)需要維修的設(shè)備類型有５類，設(shè)為ＳＤ ＝ ｛ＳＤ１，ＳＤ２，ＳＤ３，ＳＤ４，ＳＤ５｝，ＳＤ為設(shè)備類型集合。在此將服務(wù)任務(wù)分成５類子任務(wù)。經(jīng)過對(duì)維修設(shè)備評(píng)估算出每類資源的服務(wù)成本、時(shí)間成本和信任值，本實(shí)例采用Ｃ語言編寫，具體的多種群算法參數(shù)為：子群數(shù)Ｓ ＝ １０，每個(gè)子群包含２０個(gè)粒子；這里的最大的迭代次數(shù)設(shè)定為１ ０００，ｗ ＝ ０．７５，ｃ１ ＝ ｃ２ ＝ １．６２。將本算法與文獻(xiàn)［５-６］進(jìn)行適應(yīng)度對(duì)比發(fā)現(xiàn)，本文提出的多粒子群混合算法是最優(yōu)的。算法比較如表１所示，開發(fā)語言為Ｃ＋＋。求得最優(yōu)的資源配置結(jié)果為［５，２，１，１，２］。

４結(jié)論

本文針對(duì)虛擬組織服務(wù)資源的配置問題進(jìn)行研究，采用多粒子群混合算法對(duì)該問題進(jìn)行求解。在求解的過程中采用了子群交叉復(fù)制和非均衡線性搜索策略，解決了在尋優(yōu)過程中保持種群的多樣性和加快算法收斂速度的問題。最后通過實(shí)例分析驗(yàn)證了本文算法在虛擬組織服務(wù)資源配置中的有效性。

主要參考文獻(xiàn)

［１］ Ｗｕ ＹＷ， Ｓｈｉｈ Ｈ－Ａ， Ｃｈａｎ Ｈ－Ｃ． Ｔｈｅ Ａｎａｌｙｔｉｃ Ｎｅｔｗｏｒｋ Ｐｒｏｃｅｓｓ ｆｏｒ Ｐａｒｔｎｅｒ Ｓｅｌｅｃｔｉｏｎ Ｃｒｉｔｅｒｉａ ｉｎＳｔｒａｔｅｇｉｃ Ａｌｌｉａｎｃｅｓ［Ｊ］． Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ ，２００９，３６（３）：４６４６－４６５３．

［２］ Ｆｅｉ Ｙｅ，Ｙｉ－Ｎａ Ｌｉ． Ｇｒｏｕｐ Ｍｕｌｔｉ－Ａｔｔｒｉｂｕｔｅ Ｄｅｃｉｓｉｏｎ Ｍｏｄｅｌ ｔｏ Ｐａｒｔｎｅｒ Ｓｅｌｅｃｔｉｏｎ ｉｎ ｔｈｅ Ｆｏｒｍａｔｉｏｎ ｏｆ Ｖｉｒｔｕａｌ Ｅｎｔｅｒｐｒｉｓｅ ｕｎｄｅｒ Ｉｎｃｏｍｐｌｅｔｅ Ｉｎｆｏｒｍａｔｉｏｎ［Ｊ］． Ｅｘｐｅｒｔ Ｓｙｓｔｅｍｓ ｗｉｔｈ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００９，３６（５）： ９３５０－９３５７．

［３］ Ｊｕｎｇｔａｅ Ｍｕｎ，Ｍｏｏｎｓｏｏ Ｓｈｉｎ，Ｋｙｕｎｇｈｕｙ Ｌｅｅ，Ｍｏｏｙｏｕｎｇ Ｊｕｎｇ． Ｍａｎｕｆａｃｔｕｒｉｎｇ Ｅｎｔｅｒｐｒｉｓｅ Ｃｏｌｌａｂｏｒａｔｉｏｎ Ｂａｓｅｄ ｏｎ ａ Ｇｏａｌ－Ｏｒｉｅｎｔｅｄ Ｆｕｚｚｙ Ｔｒｕｓｔ Ｅｖａｌｕａｔｉｏｎ Ｍｏｄｅｌ ｉｎ ａ Ｖｉｒｔｕａｌ Ｅｎｔｅｒｐｒｉｓｅ［Ｊ］． Ｃｏｍｐｕｔｅｒ ＆ Ｉｎｄｕｓｔｒｉａｌ Ｅｎｇｉｎｅｅｒｉｎｇ，２００９，５６（３）：８８８－９０１．

［４］ 王文彬，孫其博，趙新超，楊放春． 基于非均衡變異離散粒子群算法的ＱｏＳ全局最優(yōu)Ｗｅｂ服務(wù)選擇方法［Ｊ］． 電子學(xué)報(bào)，２０１０（１２）：２７７４－２７７８．

［５］ 蔡國榕，陳水利，李紹滋，吳云東． 一種具有自適應(yīng)遷移能力的多粒子群協(xié)同優(yōu)化算法［Ｊ］． 廈門大學(xué)學(xué)報(bào)：自然科學(xué)版，２０１０，４９（６）：７７２－７７７．

［６］ Ｒａｊｅｓｈ Ｋｕｍａｒ，Ｄｅｂｅｎｄｒａ Ｓｈａｒｍａ，Ａｂｈｉｎａｖ Ｓａｄｕ． Ａ Ｈｙｂｒｉｄ Ｍｕｌｔｉ－Ａｇｅｎｔ Ｂａｓｅｄ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚｓｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｆｏｒ Ｅｃｏｎｏｍｉｃ Ｐｏｗｅｒ Ｄｉｓｐａｔｃｈ［Ｊ］． Ｅｌｅｃｔｒｉｃａｌ Ｐｏｗｅｒ ａｎｄ Ｅｎｅｒｇｙ Ｓｙｓｔｅｍｓ，２０１１，３３（１）：１１５－１２３．

［７］ Ｒ Ｊ Ｋｕｏ，Ｓ Ｙ Ｈｏｎｇ，Ｙ Ｃ Ｈｕａｎｇ． Ｉｎｔｅｇｒａｔｉｏｎ ｏｆ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ－Ｂａｓｅｄ Ｆｕｚｚｙ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋ ａｎｄ Ａｒｔｉｆｉｃｉａｌ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋ ｆｏｒ Ｓｕｐｐｌｉｅｒ Ｓｅｌｅｃｔｉｏｎ［Ｊ］．Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌｌｉｎｇ，２０２０，３４（１２）：３９７６－３９９０．

［８］ 丁雷． 復(fù)雜約束條件下的混合粒子群優(yōu)化算法［Ｊ］． 計(jì)算機(jī)應(yīng)用研究，２０１０，２７（９）．

Cooperative Particle Swarm Optimization Algorithm for Optimal Service Resource Allocation in a Virtual Organization

MA Shu-gang1，2， YANG Jian-hua1，GUO Ji-dong1

（1.School of Economics and Management， University of Science and Technology Beijing， Beijing 100083， China；

2. School of Business， Hebei University of Economics and Business， Shijiazhuang 050061， China）

Ａｂｓｔｒａｃｔ： Ｃｏｏｐｅｒａｔｉｖｅ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ Ｏｐｔｉｍｉｚａｔｉｏｎ Ａｌｇｏｒｉｔｈｍ ｗａｓ ｐｒｏｐｏｓｅｄ ｉｎ ｏｒｄｅｒ ｔｏ ｉｍｐｒｏｖｅ ｔｈｅ ｅｆｆｉｃｉｅｎｃｙ ｏｆ ｓｅｒｖｉｃｅ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｉｎ ｖｉｒｔｕａｌ ｏｒｇａｎｉｚａｔｉｏｎ． Ｔｈｉｓ ｐａｐｅｒ ｃｏｍｂｉｎｅｄ Ｃｏｏｐｅｒａｔｉｖｅ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ ｗｉｔｈ ｔｈｅ ｌｉｎｅ ｓｅａｒｃｈ ｍｅｔｈｏｄ． Ｃｏｏｐｅｒａｔｉｖｅ Ｐａｒｔｉｃｌｅ Ｓｗａｒｍ ｃｏｎｔｒｏｌｌｅｄ ｔｈｅ ｄｉｖｅｒｓｉｔｙ ｏｆ ｓｗａｒｍ ｂｙ ｃｏｐｙｉｎｇ ｂｅｓｔ ｐａｒｔｉｃｌｅｓ ｉｎ ｔｈｅ ｓｕｂ－ｐｏｐｕｌａｔｉｏｎｓ ｄｕｒｉｎｇ ｔｈｅ ｐｒｏｃｅｓｓ ｏｆ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ａｌｇｏｒｉｔｈｍ ｍｏｄｉｆｉｅｄ ｅａｃｈ ｖａｒｉａｂｌｅ ｏｆ ｔｈｅ ｐａｒｔｉｃｌｅ． Ｔｈｅ ｒｅｓｕｌｔ ｓｈｏｗｓ ｔｈｅ ｐｒｏｐｏｓｅｄ ａｌｇｏｒｉｔｈｍ ｉｓ ｆｅａｓｉｂｉｌｉｔｙ．

Ｋｅｙ ｗｏｒｄｓ： Vｉｒｔｕａｌ Oｒｇａｎｉｚａｔｉｏｎ； Rｅｓｏｕｒｃｅ Aｌｌｏｃａｔｉｏｎ； Cooperative Particle Swarm