[發(fā)明專利]基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法、裝置及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201710855366.0
• 申請日: 2017-09-20
• 公開（公告）號(hào): CN107609650B
• 公開（公告）日: 2020-10-30
• 發(fā)明（設(shè)計(jì)）人: 侯守明;張玉珍;王留芳;郅芬香;常莉
• 申請（專利權(quán)）人: 河南理工大學(xué)
• 主分類號(hào): G06N3/12
• 分類號(hào): G06N3/12;G06N3/00
• 代理公司: 鄭州大通專利商標(biāo)代理有限公司 41111
• 代理人: 陳勇

1.基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法，其特征在于，包括以下步驟：

步驟1：構(gòu)建粒子種群；

步驟2：對各粒子的位置和速度進(jìn)行更新，并設(shè)定迭代次數(shù)，得出達(dá)到設(shè)定迭代次數(shù)的粒子個(gè)體最優(yōu)位置和粒子全局最優(yōu)位置；

所述步驟2包括：

步驟2.1：計(jì)算各粒子的適應(yīng)度值，獲得當(dāng)前個(gè)體最優(yōu)位置及當(dāng)前全局最優(yōu)位置的適應(yīng)度值，所述當(dāng)前個(gè)體最優(yōu)位置指每個(gè)粒子的位置，所述當(dāng)前全局最優(yōu)位置指適應(yīng)度函數(shù)值最大的粒子的位置；

各粒子的適應(yīng)度函數(shù)如下所示：

其中，f為粒子適應(yīng)度，Q為常數(shù)，T為粒子序列中任務(wù)完成總時(shí)間，T_j為j節(jié)點(diǎn)任務(wù)完成時(shí)間，k₁和k₂分別為任務(wù)完成時(shí)間和時(shí)間負(fù)載均衡的權(quán)重；

T_j及T公式分別如下：

其中，i表示任務(wù)編號(hào)，j表示節(jié)點(diǎn)編號(hào)，t_ij表示完成j節(jié)點(diǎn)i任務(wù)的時(shí)間，利用規(guī)模為m×n的矩陣t來存儲(chǔ)t_ij的值，e_ij表示若任務(wù)i在節(jié)點(diǎn)j上執(zhí)行其值為1，否則為0，m為總?cè)蝿?wù)數(shù)，l_i表示任務(wù)i的長度，cp_j為節(jié)點(diǎn)j的處理能力，n為總節(jié)點(diǎn)數(shù)；

步驟2.2：對各粒子的粒子速度和粒子位置進(jìn)行更新及元素規(guī)范化，并計(jì)算更新及元素規(guī)范化后各粒子的適應(yīng)度值，所述粒子位置指所有任務(wù)被執(zhí)行時(shí)對應(yīng)的節(jié)點(diǎn)序列，粒子位置中每一維元素的值都是對應(yīng)的節(jié)點(diǎn)編號(hào)；

所述步驟2.2包括：

a.對各粒子的粒子速度進(jìn)行更新：

其中，表示第s個(gè)粒子在第k+1次迭代中第i維的速度，表示第s個(gè)粒子在第k次迭代中第i維的速度，x和η為設(shè)定的常數(shù)，k是迭代次數(shù)，r₁和r₂是均勻分布在[0,1]之間的隨機(jī)數(shù)；ω為權(quán)重因子，NC為總迭代次數(shù)，為第s個(gè)粒子第k次迭代后的個(gè)體歷史最優(yōu)位置，是個(gè)體歷史最優(yōu)解位置所對應(yīng)的第i維的值，為第k次迭代后的全局最優(yōu)解位置，是個(gè)體歷史最優(yōu)解位置所對應(yīng)的第i維的值，為第s個(gè)粒子在第k+1次迭代更新后位置的第i維的值；f_max是迭代后的當(dāng)前最大適應(yīng)度值；

b.對各粒子的粒子位置進(jìn)行更新：

其中，為第s個(gè)粒子在第k+1次迭代更新后位置的第i維的值，為第s個(gè)粒子在第k次迭代更新后位置的第i維的值，表示第s個(gè)粒子在第k+1次迭代中第i維的速度；

c.對更新后各粒子的粒子速度進(jìn)行元素規(guī)范化：

其中，v_si為第s個(gè)粒子在第k次迭代中第i維的速度元素規(guī)范化后的粒子速度，n為節(jié)點(diǎn)的個(gè)數(shù)，v_si為第s個(gè)粒子在第k次迭代中第i維的粒子速度；

d.對更新后各粒子的粒子位置進(jìn)行元素規(guī)范化：

其中，x_si為第s個(gè)粒子在第k次迭代中第i維的位置元素規(guī)范化后的粒子位置，C為常數(shù)，x_si為第s個(gè)粒子在第k次迭代中第i維的粒子位置，e為自然常數(shù)；

e.計(jì)算更新及元素規(guī)范化后各粒子的適應(yīng)度值；

步驟2.3：判斷更新及元素規(guī)范化后各粒子的適應(yīng)度值是否大于當(dāng)前個(gè)體最優(yōu)位置及全局最優(yōu)位置的適應(yīng)度值，若是，則更新粒子的當(dāng)前個(gè)體最優(yōu)位置及全局最優(yōu)位置；若否，則不進(jìn)行更新；

步驟2.4：判斷是否達(dá)到設(shè)定的迭代次數(shù)，若是，則得出最終的粒子個(gè)體最優(yōu)位置和粒子全局最優(yōu)位置；若否，則重復(fù)步驟2.1至步驟2.3；

步驟3：對粒子種群進(jìn)行交叉操作和變異操作，得出最終的粒子個(gè)體最優(yōu)位置和粒子全局最優(yōu)位置。

2.根據(jù)權(quán)利要求1所述的基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法，其特征在于，所述構(gòu)建粒子種群指部分粒子的生成方式根據(jù)節(jié)點(diǎn)均勻分配法，使得每個(gè)節(jié)點(diǎn)上所分配的任務(wù)個(gè)數(shù)相差不超過1，剩余部分粒子隨機(jī)生成。