一種改進(jìn)型粒子群算法求解資源優(yōu)化配置問(wèn)題(共5頁(yè))

1、第卷 第期蘭 州 交 通 大學(xué)學(xué)報(bào)年月 文章編號(hào)：（ ）：一種改進(jìn)型粒子群算法(sun f)求解資源優(yōu)化配置問(wèn)題孫宏飛， 吳澤兵(z bn)（蘭州交通大學(xué)(dxu) 交通運(yùn)輸學(xué)院，甘肅 蘭州 ）摘 要：針對(duì)粒子群算法在求解優(yōu)化問(wèn)題時(shí)難以兼顧收斂精度與收斂速度這一問(wèn)題，提出對(duì)目標(biāo)的慣性權(quán)重進(jìn)行 修正和引入隨著慣性權(quán)重變化的慣性學(xué)習(xí)因子的方法，該算法充分利用了上一代速度與位置、自我認(rèn)知和群體間 信息共享部分內(nèi)容，來(lái)影響算法的優(yōu)化結(jié)果，提高了算法的全局和局部的搜索能力最后將改進(jìn)的粒子群算法應(yīng) 用于工程項(xiàng)目中的資源優(yōu)化配置問(wèn)題中，證明了該算法的有效性關(guān)鍵詞：資源優(yōu)化配置；粒子群算法；網(wǎng)絡(luò)計(jì)劃；慣性學(xué)習(xí)

2、因子中圖分類號(hào)：文獻(xiàn)標(biāo)志碼： ， （ ， ， ，）： ， ， ， ：； 工程項(xiàng)目以工程建設(shè)為載體，是建設(shè)單位在一 定資源條件約束下對(duì)建筑物或構(gòu)建物實(shí)施的過(guò)程及 結(jié)果，一個(gè)成功的項(xiàng)目必須滿足在限定的資源、時(shí)間 和成本等條件約束下完成既定目標(biāo)而在這些條 件當(dāng)中，資源約束可以說(shuō)是重中之重，不僅需要調(diào)整 網(wǎng)絡(luò)計(jì)劃中非關(guān)鍵路線上的作業(yè)開(kāi)始時(shí)間，還要調(diào) 整各項(xiàng)資源的使用次序，使資源分配動(dòng)態(tài)曲線的高 峰盡可能降低，低谷盡可能地增高，從而使單位時(shí)間 內(nèi)使用的資源數(shù)量趨于均等，從而達(dá)到資源的均衡利用這類問(wèn)題屬于一類組合的完全多項(xiàng)式非確定性問(wèn)題（問(wèn)題 ），求解這類問(wèn)題的 時(shí)間隨著問(wèn)題規(guī)模的增大、網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目的

3、增多呈指數(shù)曲線上升近年來(lái)，隨著工程項(xiàng)目結(jié)構(gòu)越 來(lái)越復(fù)雜，傳統(tǒng)的優(yōu)化方法有很大的局限性，已無(wú)法 滿足建設(shè)單位的需要，這就需要一種全新的解決方 法來(lái)處理這類問(wèn)題于是學(xué)者們提出了一些不依賴 于問(wèn)題本身的直接搜索方法，如進(jìn)化策略、遺傳算法 和粒子群算法等，他們可以利用自身強(qiáng)大的搜索能收稿日期：學(xué)報(bào)網(wǎng)址： ： 作者簡(jiǎn)介：孫宏飛（），女，河北邢臺(tái)人，碩士生，主要研究方向?yàn)楣芾砜茖W(xué)與工程：第期：孫宏飛等 一種改進(jìn)型粒子群算法求解資源優(yōu)化配置問(wèn)題力來(lái)解決(jiju)此類問(wèn)題相對(duì)于其他(qt)算法而言，粒子(lz)群算 法（ ，）中每個(gè)成員 通過(guò)學(xué)習(xí)自己的經(jīng)驗(yàn)與群體之間共享的信息來(lái)尋求 最優(yōu)解，具有結(jié)構(gòu)簡(jiǎn)單、參

4、數(shù)少和易于實(shí)現(xiàn)等優(yōu)點(diǎn)， 被廣泛應(yīng)用于求解最優(yōu)化問(wèn)題，并在很多優(yōu)化實(shí)踐 中表現(xiàn)出較好的實(shí)用性本文的基本思想主要源于文獻(xiàn)，具體內(nèi)容 是以初始的粒子群算法為基礎(chǔ)，首先對(duì)速度更新公 式中的慣性權(quán)重進(jìn)行了修正來(lái)平衡算法的全局和局 部搜索能力；其次，又在公式的自我認(rèn)知項(xiàng)和社會(huì) 經(jīng)驗(yàn)項(xiàng)中引入了隨著慣性權(quán)重變化的慣性學(xué)習(xí)因 子，充分利用這兩部分來(lái)影響算法的優(yōu)化結(jié)果；最后將改進(jìn)的粒子群算法用于給出的實(shí)際工程中，對(duì)該工程的資源配置進(jìn)行優(yōu)化，以驗(yàn)證該算法可以用 較少的計(jì)算時(shí)間找到收斂精度很好的結(jié)果 資源均衡問(wèn)題的數(shù)學(xué)模型在資源配置過(guò)程中，如果已知項(xiàng)目的初始網(wǎng)絡(luò) 計(jì)劃圖，就能夠計(jì)算出各個(gè)工序的時(shí)間參數(shù)，并根據(jù) 本文中

5、提出的方法，不斷調(diào)整網(wǎng)絡(luò)圖中的非關(guān)鍵路 線上的作業(yè)開(kāi)始時(shí)間，調(diào)整各項(xiàng)資源的使用次序，使 得資源達(dá)到均衡利用本文以單位時(shí)間內(nèi)資源需求量的方差 為目 標(biāo)函數(shù)，以各項(xiàng)工作的時(shí)間限制及資源需求限量為 約束條件建立模型方差越小說(shuō)明該項(xiàng)目資源利用 的均衡程度越好，該問(wèn)題的數(shù)學(xué)語(yǔ)言描述為目標(biāo)函數(shù)：（）（） （）（）（） 約束條件：（） （） 其中：，；（）；表示該項(xiàng)目的作業(yè)數(shù)；表示該項(xiàng)目的工期；表示所有資源在第；日需求量 表示所有資源在工期內(nèi)平均每日的需求量；表示作業(yè) 的最早結(jié)束時(shí)間；表示作業(yè) 的最遲結(jié)束時(shí)間；表示作業(yè) 的實(shí)際開(kāi)工時(shí)間；表示作業(yè) 的持續(xù)時(shí)間；表示作業(yè) 的最早開(kāi)始時(shí)間；表示作業(yè) 的時(shí)差；表示在

6、作業(yè)；表示每日的資源限量；在第日的資源消耗量 （）表示活動(dòng) 所有的緊前活動(dòng)根據(jù)各種作業(yè)時(shí)間時(shí)差之間的關(guān)系，很容易得出：式（）表示網(wǎng)絡(luò)圖中各項(xiàng)作業(yè)的關(guān)系(gun x)為結(jié)束開(kāi)始型，即作業(yè)(zuy) 在作業(yè)之前(zhqin)完成；式（）表示應(yīng)基于 該作業(yè)的時(shí)差對(duì)其進(jìn)行調(diào)整；式（）表示單位時(shí)間內(nèi)正在進(jìn)行的活動(dòng)所需的資源總數(shù)不能超過(guò)其限量；式（）表示作業(yè)的開(kāi)始時(shí)間應(yīng)在緊前工序完成之后和本作業(yè)最遲開(kāi)始時(shí)間之前 粒子群算法優(yōu)化 標(biāo)準(zhǔn)的粒子群算法粒子群算法（ ）通過(guò)模仿鳥(niǎo)群覓食行為，種群中每個(gè)成員通過(guò)學(xué)習(xí)自己與其他成員的經(jīng)驗(yàn)，在搜索空間內(nèi)尋找最優(yōu)解初始粒子群采用隨機(jī)方法 產(chǎn)生，每個(gè)粒子就代表該空間內(nèi)的一個(gè)可

7、行解，每一 個(gè)解都包含速度和位置兩種屬性，其優(yōu)劣由優(yōu)化函 數(shù)所決定的適應(yīng)值決定粒子在搜索空間內(nèi)通過(guò)速 度和位置的更新跟蹤個(gè) “極值點(diǎn)”：一個(gè)是個(gè)體歷 史最好點(diǎn)，即粒子個(gè)體目前所找到的最優(yōu) 解；另一個(gè)是全局歷史最好點(diǎn)，即整個(gè)種群目 前找到的最優(yōu)解，通過(guò)一次次的循環(huán)迭代，最終找到 的全局極值即為全局最優(yōu)點(diǎn)每個(gè)粒子的位置和速度分別通過(guò)式（）和（）進(jìn)行更新：（ ） （）（） （） 其中：為慣性權(quán)值；，為學(xué)習(xí)因子，取值較低的 粒子容易使其在目標(biāo)的區(qū)域外邊徘徊，而取值較高 則會(huì)導(dǎo)致粒子突然地沖向或越過(guò)目標(biāo)區(qū)域，一般取，并且范圍在和之間；，是，之 間的隨機(jī)數(shù)；是粒子在優(yōu)化過(guò)程中適應(yīng)值最優(yōu)的位置，即個(gè)體最優(yōu)位

8、置；是全局最優(yōu)位 置 粒子群算法的改進(jìn)由于標(biāo)準(zhǔn)粒子群優(yōu)化算法存在易早熟收斂陷于 局部最優(yōu)點(diǎn)、后期進(jìn)化慢甚至停止進(jìn)化等缺點(diǎn)，本文通過(guò)調(diào)整慣性系數(shù)和引入慣性學(xué)習(xí)因子對(duì)該算法 進(jìn)行了改進(jìn)，能夠較好的改善上述不足，提高算法的 收斂精度與速度，同時(shí)也平衡了算法的全局和局部 搜索能力 調(diào)整慣性權(quán)重根據(jù)進(jìn)化算法的性質(zhì)，當(dāng)粒子速度較大時(shí)算法 的全局搜索能力較強(qiáng)；相反地當(dāng)粒子速度變小時(shí)算 法的局部搜索能力就加強(qiáng)了在進(jìn)化的初期，算 法注重全局搜索能力，大的 值能避免種群總是在蘭 州 交 通 大 學(xué) 學(xué) 報(bào)第卷某個(gè)局部區(qū)域(qy)進(jìn)行搜索而陷入到局部最優(yōu)點(diǎn)；而到 了進(jìn)化的后期算法注重的則是能夠(nnggu)進(jìn)一步搜

9、索到精 確解的能力尹呈 等提出(t ch)了慣性權(quán)值隨進(jìn)化代數(shù) 而作余弦規(guī)律變化的方法，這一改變使得搜索初期 保持較大值，提高了全局搜索能力保證了較好的 廣度；而搜索后期保持較小值，提高了局部搜索能 力保證了較高的精度慣性權(quán)值的數(shù)學(xué)表達(dá)式如下：（） （）（） 其中： 表示當(dāng)前進(jìn)化代數(shù)； 表示所需進(jìn)化的 總代數(shù) 引入慣性學(xué)習(xí)因子根據(jù)鳥(niǎo)群覓食的生物學(xué)特性，個(gè)體在覓食過(guò) 程中，往往通過(guò)學(xué)習(xí)自身以往的經(jīng)驗(yàn)和群體的經(jīng)驗(yàn) 來(lái)改進(jìn)自己下一步的計(jì)劃，而在這個(gè)學(xué)習(xí)過(guò)程中個(gè) 體存在著一定的慣性思維，因此在改進(jìn)粒子群算法 的過(guò)程中，有必要將慣性學(xué)習(xí)因子引入粒子速度更 新公式中，這樣就可以充分利用算法中自我認(rèn)知的 部

10、分和社會(huì)認(rèn)知部分在尋優(yōu)過(guò)程中所起的作用來(lái)影 響算法的優(yōu)化結(jié)果改進(jìn)如下：（ ） （）（） （）（ ） （ ） 其中： ，表示慣性學(xué)習(xí)因子 通過(guò)上述對(duì)慣性權(quán)重和慣性學(xué)習(xí)因子的改進(jìn)，：使得該算法具有更好的實(shí)用性其優(yōu)點(diǎn)表現(xiàn)在 在搜索初期， 取值較大，算法具有較強(qiáng)的全局搜索能力，此時(shí) 較小， 較大，即對(duì)速度更新而言，群 體間信息共享比自我認(rèn)知重要，這樣就可以較好地得到全局歷史最優(yōu)點(diǎn)；隨著搜索的一步步進(jìn)行， 取值越來(lái)越小，算法具有較強(qiáng)的局部搜索能力，此時(shí)較大， 較小，即對(duì)速度更新而言，自我認(rèn)知比 群體間信息共享重要，這樣就可以較好地得到個(gè)體 歷史最優(yōu)點(diǎn)這樣就充分利用了上一代速度、自身認(rèn) 知和群體間信息共享

11、部分內(nèi)容，算法能夠較大程 度地得到滿意的全局最優(yōu)點(diǎn)該粒子群算法的主要流程如下所示： ：設(shè)定算法參數(shù)，種群大小 ，學(xué)習(xí)因子，最大進(jìn)化代數(shù)； ：初始化粒子群，對(duì)其中的每個(gè)粒子的位置和速度進(jìn)行隨即初始化； ：計(jì)算每個(gè)粒子的適應(yīng)度值；：將每個(gè)粒子的適應(yīng)度值分別與其經(jīng)歷的個(gè)體最優(yōu)位置 和已知的全局最優(yōu)位置 的適應(yīng)度值進(jìn)行比較，若該適應(yīng)值較好，則替 換其為當(dāng)前的個(gè)體最優(yōu)位置和全局最優(yōu) 位置；：按照上述改進(jìn)的位置式（）和速度式（） 來(lái)對(duì)每個(gè)粒子進(jìn)行更新；：判斷終止條件（通常設(shè)置一個(gè)確定的進(jìn) 化代數(shù)），如果沒(méi)有達(dá)到結(jié)束條件，則返回，否 則終止 實(shí)例分析圖為一個(gè)包含了項(xiàng)作業(yè)項(xiàng)目的初始網(wǎng)絡(luò) 計(jì)劃圖，要求網(wǎng)絡(luò)計(jì)劃中

12、的每項(xiàng)作業(yè)不能拆分，作業(yè) 的持續(xù)時(shí)間固定，而且每項(xiàng)作業(yè)都有一個(gè)固定的資 源需求量圖中個(gè)節(jié)點(diǎn)之間表示一項(xiàng)作業(yè)，其中包 含的信息為（資源單位數(shù)，工期），例如（，）表示 作業(yè)在單位時(shí)間內(nèi)需要的資源為個(gè)單位，且持 續(xù)時(shí)間為在本項(xiàng)目中要求單位時(shí)間內(nèi)所需資源 不超過(guò)個(gè)單位，即為A(10，2)E(2，2)H(8，6)23I(2，2)1 B(8，3) 4F(10，5) 5G(12，4)6 K(10，2) 8C(8，4)D(6，3)J(6，4)7圖 項(xiàng)目的初始網(wǎng)絡(luò)圖 根據(jù)本文建立的數(shù)學(xué)模型可得到以下描述： （ ） 烄 烅 烆 資源平衡之前單位時(shí)間內(nèi)資源需求見(jiàn)圖，從 圖中可以看到，單位時(shí)間內(nèi)最多消耗資源個(gè)單第期：

13、孫宏飛等 一種改進(jìn)型粒子群算法求解資源優(yōu)化配置問(wèn)題位，最少消耗(xioho)資源個(gè)單位(dnwi)，最多與最少之間相差(xin ch) 個(gè)單位，此時(shí)的目標(biāo)函數(shù)值 而在資源 平衡之后每天資源需求量見(jiàn)圖，在此次運(yùn)算中將 學(xué)習(xí)因子， 的取值都設(shè)置為，進(jìn)化代數(shù)為 代，平衡后的資源在單位時(shí)間內(nèi)的最大需求量 才是個(gè)單位，而最少消耗量也達(dá)到了個(gè)單位， 落差僅僅個(gè)單位，此時(shí)的目標(biāo)函數(shù)值 相比 較而言，資源的需求量也已得到較好的優(yōu)化，能夠較 大程度地幫助建設(shè)單位對(duì)資源進(jìn)行管理，避免資源 的不均衡使用3530252015105012 3 4 5 6 7 8 9 10 11 12 13 14圖 資源平衡前資源需求量

14、 25201510512 3 4 5 6 7 8 9 10 11 12 13 14圖 資源均衡后資源需求量 結(jié)語(yǔ)本文對(duì)現(xiàn)有的粒子群算法進(jìn)行一定的改進(jìn)，通過(guò)引入慣性學(xué)習(xí)因子和對(duì)慣性因子的改進(jìn)，使得算 法更貼近實(shí)際，具有更強(qiáng)的實(shí)用性但是由于本文給 出的實(shí)例前提是網(wǎng)絡(luò)中的作業(yè)不能拆分、作業(yè)持續(xù) 時(shí)間固定，這就不像實(shí)際操作那么靈活工程單位在一個(gè)實(shí)際項(xiàng)目的建設(shè)中，往往可以根據(jù)實(shí)際情況對(duì) 各項(xiàng)作業(yè)進(jìn)行一定的修正，如非關(guān)鍵路徑上的非關(guān) 鍵作業(yè)是可以分割，而且可以在不同的時(shí)段以不同 的速率進(jìn)行，這就在一定程度上限制了資源平衡的 進(jìn)一步優(yōu)化，從這個(gè)角度講，本文的算法還可以做進(jìn) 一步優(yōu)化，以更加符合工程實(shí)際參考文獻(xiàn)：王要武，李曉東，孫立新 工程項(xiàng)目信息化管理 版 北京：中國(guó)建筑工業(yè)出版社， ：畢星，翟麗 項(xiàng)目管理 版 上海：復(fù)旦大學(xué)出版 社，：， ， （）： 尹呈，郭觀七，李文彬，等 基于自適應(yīng)學(xué)習(xí)的多目標(biāo)粒 子群優(yōu)化算法計(jì)算機(jī)應(yīng)用研究， （）： 秦洪德，石麗麗 一種新型被動(dòng)啟發(fā)式粒子群優(yōu)化算法 哈爾濱工程大學(xué)學(xué)報(bào)， ， （ ）： 張連營(yíng)，張金平，王亮 工程項(xiàng)目管理資源均衡的遺傳 算法及其實(shí)現(xiàn) 管理工程學(xué)報(bào)， ，（）： 成虎 工程項(xiàng)目管理江蘇：東南大學(xué)， ： 馮偉 基于粒子群算