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

有效

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

本發(fā)明屬于計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法、裝置及系統(tǒng)?；跁r(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法，包括：構(gòu)建粒子種群；對各粒子的位置和速度進(jìn)行更新，并設(shè)定迭代次數(shù)，得出達(dá)到設(shè)定迭代次數(shù)的粒子個(gè)體最優(yōu)位置和粒子全局最優(yōu)位置；對粒子種群進(jìn)行交叉操作和變異操作，得出最終的粒子個(gè)體最優(yōu)位置和粒子全局最優(yōu)位置。基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化裝置，包括：構(gòu)建模塊；更新模塊；交叉變異模塊?；跁r(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化系統(tǒng)，包括多個(gè)節(jié)點(diǎn)服務(wù)器和至少一個(gè)終端。本發(fā)明解決了云任務(wù)調(diào)度中耗時(shí)長、時(shí)間負(fù)載不均衡和資源利用率低的問題。

技術(shù)領(lǐng)域

本發(fā)明屬于計(jì)算機(jī)技術(shù)領(lǐng)域，尤其涉及基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法、裝置及系統(tǒng)。

背景技術(shù)

云計(jì)算是網(wǎng)格計(jì)算、分布式計(jì)算和并行計(jì)算的商業(yè)發(fā)展，具備了其他計(jì)算模式所不具有的先天優(yōu)勢。云計(jì)算系統(tǒng)根據(jù)任務(wù)請求以及任務(wù)屬性為其分配資源，然而復(fù)雜的云計(jì)算環(huán)境使得任務(wù)的調(diào)度成為極具挑戰(zhàn)性的問題。同時(shí)，任務(wù)調(diào)度完成的時(shí)間和成本等成為衡量算法的標(biāo)準(zhǔn)和追求目標(biāo)。

在云計(jì)算環(huán)境中，任務(wù)與節(jié)點(diǎn)有異構(gòu)和動態(tài)的特征，存在著隨機(jī)性。粒子群算法是一種基于群體智能的隨機(jī)優(yōu)化算法，種群中每一個(gè)粒子都代表問題的一個(gè)可能解，且群體內(nèi)部可以進(jìn)行信息交互，促使粒子改變自身的位置，進(jìn)而實(shí)現(xiàn)求解的智能性。由于粒子群優(yōu)化算法存在早熟收斂、易陷入局部最優(yōu)等問題，文獻(xiàn)[1]加入遺傳算法的交叉和變異操作，擴(kuò)展粒子的搜索空間，來克服粒子易陷入局部最優(yōu)問題。文獻(xiàn)[2]采用了反向?qū)W習(xí)和局部學(xué)習(xí)的思想優(yōu)化收斂速度，并提高解的精度，但依然存在著負(fù)載均衡、節(jié)能的問題。文獻(xiàn)[3]在前者的基礎(chǔ)上引入了混沌擾動思想，可有效地跳出局部最優(yōu)現(xiàn)象。另外，由于傳統(tǒng)的粒子初始化方法是隨機(jī)生成若干個(gè)粒子，生成的粒子質(zhì)量往往不佳，造成各節(jié)點(diǎn)上任務(wù)數(shù)偏差較大，文獻(xiàn)[4]通過加入負(fù)載均衡模型，提高節(jié)點(diǎn)任務(wù)個(gè)數(shù)的均衡性，但這只是節(jié)點(diǎn)上任務(wù)個(gè)數(shù)的均衡，依然存在著節(jié)點(diǎn)時(shí)間負(fù)載不均衡、運(yùn)行效率低等現(xiàn)象。

目前，雖然云計(jì)算任務(wù)調(diào)度優(yōu)化算法層出不窮，但基本上以任務(wù)完成時(shí)間、成本為目標(biāo)，而對節(jié)點(diǎn)時(shí)間負(fù)載均衡的關(guān)注仍為不足。

參考文獻(xiàn)：

文獻(xiàn)[1]：Xu J,Tang Y.Research of Improved Particle Swarm OptimizationBased on Genetic Algorithm for Hadoop Task Scheduling Problem[M]//Algorithmsand Architectures for Parallel Processing.Springer International Publishing,2015:60-66vol.2；

文獻(xiàn)[2]：Guo-Long Y U,Cui Z W,Zuo Y.Cloud Platform Scheduling MethodBased on Optimized Particle Swarm Optimization Algorithm[J].Journal of InnerMongolia Normal University,2016；

文獻(xiàn)[3]：夏學(xué)文,劉經(jīng)南,高柯夫,李元香,曾輝.具備反向?qū)W習(xí)和局部學(xué)習(xí)能力的粒子群算法[J]. 計(jì)算機(jī)學(xué)報(bào),2015,(07):1397-1407；

文獻(xiàn)[4]：Yizhen Wang,Yongqiang Sun,Yi Sun。Task Scheduling Algorithm inCloud Computing Based on Fairness Load Balance and Minimum Completion Time[J]//Advances in Engineering Research,2016。

發(fā)明內(nèi)容

本發(fā)明的目的在于克服上述云任務(wù)調(diào)度中的不足，提供了基于時(shí)間負(fù)載均衡的粒子遺傳算法優(yōu)化方法、裝置及系統(tǒng)，解決了云任務(wù)調(diào)度中耗時(shí)長、時(shí)間負(fù)載不均衡和資源利用率低的問題。