基于正交自適應(yīng)鯨魚(yú)優(yōu)化的云計(jì)算任務(wù)調(diào)度

張金泉，徐壽偉，李信誠(chéng)，王重洋，徐景芝

（1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 山東 青島 266590； 2.山東科技大學(xué) 科技產(chǎn)業(yè)管理處， 山東 青島 266590）（?通信作者電子郵箱skd306@163.com）

基于正交自適應(yīng)鯨魚(yú)優(yōu)化的云計(jì)算任務(wù)調(diào)度

張金泉1，徐壽偉1，李信誠(chéng)1，王重洋1，徐景芝2*

（1.山東科技大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 山東 青島 266590； 2.山東科技大學(xué) 科技產(chǎn)業(yè)管理處， 山東 青島 266590）（?通信作者電子郵箱skd306@163.com）

針對(duì)任務(wù)調(diào)度中存在的任務(wù)完成時(shí)間長(zhǎng)、系統(tǒng)執(zhí)行任務(wù)成本高且系統(tǒng)負(fù)載不均衡等問(wèn)題，提出了一種基于正交自適應(yīng)鯨魚(yú)優(yōu)化算法（OAWOA）的云計(jì)算任務(wù)調(diào)度方法。首先，將正交試驗(yàn)設(shè)計(jì)（OED）應(yīng)用于種群初始化和全局搜索階段，以提升和維持種群的多樣性，避免算法過(guò)早陷入局部收斂狀態(tài)；然后，利用自適應(yīng)指數(shù)遞減因子和雙向搜索機(jī)制，來(lái)進(jìn)一步加強(qiáng)算法的全局搜索能力；最后，對(duì)適應(yīng)度函數(shù)進(jìn)行優(yōu)化，從而使算法實(shí)現(xiàn)多目標(biāo)優(yōu)化。通過(guò)仿真實(shí)驗(yàn)將所提的算法與鯨魚(yú)優(yōu)化算法（WOA）、粒子群優(yōu)化（PSO）算法、蝙蝠算法（BA）以及其他兩種改進(jìn)的WOA進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，在任務(wù)規(guī)模為50和500時(shí)所提算法都取得了更好的收斂效果，并且得到的系統(tǒng)執(zhí)行任務(wù)的總時(shí)間和總成本均低于其他幾種算法，同時(shí)負(fù)載均衡度僅低于BA。可見(jiàn)，所提算法在降低系統(tǒng)執(zhí)行任務(wù)的總時(shí)間和總成本以及提高系統(tǒng)負(fù)載均衡方面均表現(xiàn)出了顯著的優(yōu)勢(shì)。

云計(jì)算；任務(wù)調(diào)度；鯨魚(yú)優(yōu)化算法；正交試驗(yàn)設(shè)計(jì)；多目標(biāo)優(yōu)化

0 引言

云計(jì)算是互聯(lián)網(wǎng)技術(shù)、計(jì)算機(jī)技術(shù)以及分布式技術(shù)等多種技術(shù)相互融合和發(fā)展產(chǎn)生的一種新興技術(shù)。云計(jì)算憑借其超大規(guī)模、可伸縮、虛擬化、按需服務(wù)、高可靠性、高性價(jià)比的特點(diǎn)給個(gè)人的生活、學(xué)習(xí)和工作都帶來(lái)了極大的便利［1］，其中虛擬化技術(shù)的應(yīng)用，使得云系統(tǒng)中的資源可以打破傳統(tǒng)物理資源的使用限制，使資源配置可以更加靈活地進(jìn)行［2］。但是，由于云資源本身的異構(gòu)性和動(dòng)態(tài)性，以及用戶任務(wù)請(qǐng)求的復(fù)雜性、多樣性以及不確定性等特點(diǎn)［3］，云計(jì)算任務(wù)調(diào)度問(wèn)題已經(jīng)成為一種多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題（即NP（Nondeterministic Polynomially）完全問(wèn)題）［4］。

如何更好地解決云計(jì)算任務(wù)調(diào)度問(wèn)題，是當(dāng)前云計(jì)算發(fā)展亟需解決的問(wèn)題，現(xiàn)有的一些可用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題的算法大致可以分為啟發(fā)式算法、元啟發(fā)式算法以及混合式算法三大類［5］。在這三類算法中，元啟發(fā)式算法和混合式算法是現(xiàn)在研究和應(yīng)用最為廣泛的兩類方法，其中，元啟發(fā)式算法主要包括：遺傳算法（Genetic Algorithm， GA）［6］、粒子群優(yōu)化（Particle Swarm Optimization， PSO）算法［7］、蟻群優(yōu)化（Ant Colony Optimization， ACO）算法［8］等。但是，通常情況下，元啟發(fā)式算法都存在或多或少的缺陷，單純地采用一種元啟發(fā)式算法往往難以取得令人滿意的結(jié)果。在這種情況下，混合式算法越來(lái)越受到人們的關(guān)注，混合式算法即將多種方法和算法結(jié)合到一起而產(chǎn)生的新算法，如混沌松鼠搜索算法（Chaotic Squirrel Search Algorithm， CSSA）［9］、基于遺傳算法的混合電子搜索（Hybrid Electro Search with Genetic Algorithm， HESGA）算法［10］以及基于性能代價(jià)的灰狼優(yōu)化（Performance Cost Grey Wolf Optimization， PCGWO）算法［11］等，往往能取得比單一元啟發(fā)式算法更好的優(yōu)化效果。

鯨魚(yú)優(yōu)化算法（Whale Optimization Algorithm， WOA）是由Mirjalili等［12］提出的一種新的基于群體智能的元啟發(fā)式優(yōu)化算法，與其他已有的一些元啟發(fā)式算法相比，WOA擁有尋優(yōu)策略簡(jiǎn)單、收斂較快的特點(diǎn)，但同時(shí)也不可避免地存在全局搜索能力較弱、搜索精度較低且容易陷入局部收斂狀態(tài)的缺陷。為了更充分地發(fā)揮WOA的優(yōu)勢(shì)，克服WOA原有的一些缺陷，更好地解決云計(jì)算任務(wù)調(diào)度問(wèn)題，本文結(jié)合正交試驗(yàn)設(shè)計(jì)（Orthogonal Experimental Design， OED）［13］、自適應(yīng)指數(shù)遞減因子以及雙向搜索機(jī)制，提出了一種新的正交自適應(yīng)鯨魚(yú)優(yōu)化算法（Orthogonal Adaptive Whale Optimization Algorithm， OAWOA），并將其應(yīng)用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題。

1 云計(jì)算任務(wù)調(diào)度與鯨魚(yú)優(yōu)化算法

1.1 云計(jì)算任務(wù)調(diào)度

在云系統(tǒng)中，任務(wù)調(diào)度就是云計(jì)算中心在接收到用戶提交的任務(wù)請(qǐng)求之后，為用戶的任務(wù)請(qǐng)求合理地分配云資源，并且實(shí)現(xiàn)系統(tǒng)執(zhí)行任務(wù)的時(shí)間最小化和系統(tǒng)執(zhí)行任務(wù)的成本最小化以及系統(tǒng)的平均負(fù)載率最大化等目標(biāo)的過(guò)程。

常用的云計(jì)算任務(wù)調(diào)度模型可以劃分為4個(gè)階段，即用戶提交任務(wù)請(qǐng)求、系統(tǒng)為任務(wù)請(qǐng)求分配資源（虛擬機(jī)）、將虛擬機(jī)分配給物理服務(wù)器以及云系統(tǒng)向用戶返回計(jì)算結(jié)果。在這4個(gè)階段中，第2個(gè)階段，即系統(tǒng)為任務(wù)請(qǐng)求分配資源（虛擬機(jī)）階段又被稱為“任務(wù)調(diào)度”階段，這也是本文要研究的內(nèi)容。

設(shè)用戶提交的n個(gè)任務(wù)的集合為：

云系統(tǒng)中m個(gè)虛擬機(jī)的集合為：

則任務(wù)調(diào)度的結(jié)果為：

根據(jù)云計(jì)算任務(wù)調(diào)度的目標(biāo)，一個(gè)任務(wù)調(diào)度結(jié)果的優(yōu)劣取決于該任務(wù)調(diào)度結(jié)果在云系統(tǒng)中執(zhí)行時(shí)所需的執(zhí)行時(shí)間的長(zhǎng)短、成本的大小以及資源利用率和負(fù)載均衡程度的高低，同時(shí)，如何能夠更好地對(duì)這些指標(biāo)進(jìn)行優(yōu)化也是當(dāng)前云計(jì)算任務(wù)調(diào)度所面臨的重要問(wèn)題。為了能夠得到更好的任務(wù)調(diào)度結(jié)果，更有效地實(shí)現(xiàn)降低系統(tǒng)執(zhí)行任務(wù)的時(shí)間和成本以及提高系統(tǒng)的平均負(fù)載率等目標(biāo)，本文利用改進(jìn)的鯨魚(yú)優(yōu)化算法即OAWOA對(duì)任務(wù)調(diào)度問(wèn)題進(jìn)行求解，并取得了顯著的效果。

1.2 鯨魚(yú)優(yōu)化算法

鯨魚(yú)優(yōu)化算法［12］是受自然界中鯨魚(yú)的捕食行為啟發(fā)而提出的一種優(yōu)化算法，它通過(guò)人工模擬鯨魚(yú)捕食行為來(lái)尋求最優(yōu)解。

鯨魚(yú)優(yōu)化算法主要包括：包圍獵物、泡泡網(wǎng)攻擊獵物（開(kāi)發(fā)階段）和搜尋獵物（探索階段）這3個(gè)階段，具體過(guò)程描述如下。

1）包圍獵物。

WOA假設(shè)當(dāng)前最佳候選解是目標(biāo)獵物，而座頭鯨可以識(shí)別獵物的位置并包圍它們。在確定目標(biāo)獵物之后，其他座頭鯨將因此嘗試向處于目標(biāo)獵物位置的座頭鯨方向更新它們的位置，在此階段，鯨魚(yú)的位置更新方式如式（1）～（2）所示：

2）泡泡網(wǎng)攻擊獵物（開(kāi)發(fā)階段）。

在該階段，鯨魚(yú)利用氣泡網(wǎng)向獵物發(fā)起攻擊，并逐漸收縮包圍圈。為了實(shí)現(xiàn)這一過(guò)程，需要包圍獵物過(guò)程和螺旋更新位置機(jī)制協(xié)同進(jìn)行，實(shí)現(xiàn)方式如式（7）所示：

3）搜尋獵物（探索階段）。

為了增強(qiáng)算法的全局搜索能力，擴(kuò)大鯨魚(yú)的搜索范圍，在該階段，WOA根據(jù)隨機(jī)選擇的搜索個(gè)體來(lái)更新搜索代理在探索階段的位置，而不是根據(jù)找到的最佳搜索個(gè)體，本階段的鯨魚(yú)位置更新方式如式（8）所示：

2 本文方法

在云計(jì)算資源調(diào)度問(wèn)題中，系統(tǒng)執(zhí)行任務(wù)的時(shí)間、系統(tǒng)執(zhí)行任務(wù)的成本以及系統(tǒng)的平均負(fù)載率等是檢驗(yàn)云計(jì)算系統(tǒng)服務(wù)能力的重要指標(biāo)，WOA在解決這類問(wèn)題中有顯著的優(yōu)勢(shì)［14-15］，但是由于WOA本身存在的一些缺陷，在解決云計(jì)算任務(wù)調(diào)度問(wèn)題時(shí)仍存在許多局限性。為克服WOA的局限性，實(shí)現(xiàn)云計(jì)算任務(wù)調(diào)度問(wèn)題的多目標(biāo)優(yōu)化，本文對(duì)WOA的種群初始化、擴(kuò)展搜索機(jī)制以及適應(yīng)度函數(shù)的設(shè)計(jì)進(jìn)行了優(yōu)化。

2.1 正交自適應(yīng)鯨魚(yú)優(yōu)化算法

為克服WOA在處理云計(jì)算任務(wù)調(diào)度問(wèn)題時(shí)存在的全局搜索能力弱且易陷入局部最優(yōu)的缺陷，本文提出了一種新的正交自適應(yīng)鯨魚(yú)優(yōu)化算法（OAWOA）。在OAWOA中，首先利用正交試驗(yàn)設(shè)計(jì)對(duì)WOA的鯨魚(yú)種群位置初始化以及全局搜索機(jī)制進(jìn)行了優(yōu)化，提出了一種正交擴(kuò)展搜索機(jī)制；其次，本文對(duì)WOA的關(guān)鍵參數(shù)向量和進(jìn)行了優(yōu)化，進(jìn)一步提高算法的尋優(yōu)能力和尋優(yōu)精度，具體過(guò)程如下。

2.1.1 基于正交試驗(yàn)設(shè)計(jì)的種群初始化和正交擴(kuò)展搜索機(jī)制

針對(duì)WOA全局搜索能力較差且易陷入局部最優(yōu)的缺陷，本文使用正交試驗(yàn)設(shè)計(jì)對(duì)算法的種群初始化和全局搜索機(jī)制進(jìn)行優(yōu)化，增強(qiáng)算法全局搜索和避免陷入局部最優(yōu)的能力。

正交試驗(yàn)設(shè)計(jì)（OED），簡(jiǎn)稱正交設(shè)計(jì)（Orthogonal Design， OD），是研究多因素多水平的一種試驗(yàn)設(shè)計(jì)方法，它根據(jù)正交性從全面試驗(yàn)中挑選出部分具備均勻分散、齊整可比特點(diǎn)的點(diǎn)。現(xiàn)在正交設(shè)計(jì)已經(jīng)應(yīng)用于遺傳算法、差分進(jìn)化算法來(lái)提高算法的性能［16］。在進(jìn)行正交設(shè)計(jì)過(guò)程中，正交表是一個(gè)必不可少的部分，本文使用的是正交表（如表1所示），即一個(gè)由7個(gè)因素（每個(gè)因素2種水平）、共計(jì)8次實(shí)驗(yàn)組成的正交序列。由于在云計(jì)算任務(wù)調(diào)度問(wèn)題中，可行方案的維度一般要比正交試驗(yàn)的因素?cái)?shù)大很多，因此需要對(duì)任務(wù)調(diào)度的可行方案進(jìn)行進(jìn)一步處理，具體任務(wù)調(diào)度問(wèn)題的正交設(shè)計(jì)過(guò)程具體如下。

表1 正交表Tab. 1 orthogonal table

表1 正交表Tab. 1 orthogonal table

試驗(yàn)號(hào)12345671111111121112222312211224122221152121212621221217221122182212112

1）隨機(jī)將種群平均分為兩組，記為X、Y。

2）分別從X、Y中隨機(jī)選擇一個(gè)鯨魚(yú)位置，記為和，其中為一個(gè)鯨魚(yú)位置向量的維度。

4）將3）分解產(chǎn)生的兩組子向量，根據(jù)表1中的正交表進(jìn)行正交試驗(yàn)，產(chǎn)生8組正交試驗(yàn)的結(jié)果。

6）重復(fù)過(guò)程2）～5），直到所有原始種群的各個(gè)位置向量均參與過(guò)正交試驗(yàn)。

7）返回產(chǎn)生的新種群的位置向量集合。

為充分發(fā)揮正交設(shè)計(jì)的優(yōu)勢(shì)，本文首先將正交設(shè)計(jì)應(yīng)用于種群初始化過(guò)程，增強(qiáng)種群多樣性，使得種群能夠更加均勻地分布于解空間中，提高算法的搜索精度；其次，由于在每次WOA迭代完成之后，種群的多樣性都會(huì)有所下降，當(dāng)種群多樣性過(guò)低時(shí)，算法容易陷入局部收斂狀態(tài)，因此，本文在每次迭代完成之后增加一次正交擴(kuò)展搜索過(guò)程，使用正交設(shè)計(jì)來(lái)維持種群的多樣性，增強(qiáng)算法的全局搜索和避免陷入局部收斂的能力，并且正交試驗(yàn)過(guò)程中會(huì)保留當(dāng)前最優(yōu)解，因此不會(huì)影響算法的收斂速度。

使用正交設(shè)計(jì)進(jìn)行鯨魚(yú)種群位置初始化時(shí)，首先采用純隨機(jī)策略產(chǎn)生特定個(gè)數(shù)的初始位置，然后對(duì)產(chǎn)生的初始位置進(jìn)行正交試驗(yàn)，直至所有的初始位置均完成正交試驗(yàn)，將新產(chǎn)生的鯨魚(yú)位置向量集合作為種群初始化的結(jié)果返回，并應(yīng)用于WOA的迭代過(guò)程?；谡辉囼?yàn)設(shè)計(jì)的鯨魚(yú)種群位置初始化算法流程如算法1所示。

算法1 利用OD初始化種群位置向量集合。

8） end for

將正交設(shè)計(jì)用于正交擴(kuò)展搜索的算法流程與算法1相似，區(qū)別在于在進(jìn)行初始化時(shí)，需要采用純隨機(jī)策略先產(chǎn)生一組隨機(jī)解，而在正交擴(kuò)展搜索階段，直接使用每次算法迭代完產(chǎn)生的位置向量集進(jìn)行正交試驗(yàn)，正交擴(kuò)展搜索的具體算法流程如算法2所示。

算法2 正交擴(kuò)展搜索。

7） end for

2.1.2 基于自適應(yīng)指數(shù)遞減因子的位置更新機(jī)制

2.1.3 雙向搜索機(jī)制

2.2 適應(yīng)度函數(shù)設(shè)計(jì)

適應(yīng)度函數(shù)是對(duì)具體問(wèn)題的抽象表述，用一個(gè)數(shù)學(xué)模型來(lái)對(duì)具體問(wèn)題進(jìn)行表示，它是各種優(yōu)化算法的優(yōu)化目標(biāo)。適應(yīng)度函數(shù)設(shè)計(jì)是否合理，決定了一個(gè)具體問(wèn)題經(jīng)過(guò)算法求解之后能否得到需要的解決方案。由于本文需要對(duì)云計(jì)算任務(wù)調(diào)度問(wèn)題的總執(zhí)行時(shí)間、總成本以及平均負(fù)載率進(jìn)行多目標(biāo)優(yōu)化，因此在設(shè)計(jì)適應(yīng)度函數(shù)時(shí)要綜合考慮系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本以及平均負(fù)載率等多個(gè)指標(biāo)，具體的適應(yīng)度函數(shù)設(shè)計(jì)過(guò)程如下所述。

1）系統(tǒng)執(zhí)行任務(wù)的總時(shí)間。

系統(tǒng)執(zhí)行任務(wù)的總時(shí)間即每個(gè)虛擬機(jī)（Virtual Machine， VM）執(zhí)行任務(wù)所需的時(shí)間之和，計(jì)算式如式（17）所示：

2）系統(tǒng)執(zhí)行任務(wù)的總成本。

系統(tǒng)執(zhí)行任務(wù)的總成本即每個(gè)虛擬機(jī)執(zhí)行任務(wù)所耗費(fèi)的成本之和，其計(jì)算式如式（20）所示：

3）系統(tǒng)平均負(fù)載率。

系統(tǒng)平均負(fù)載率是描述當(dāng)前系統(tǒng)工作狀態(tài)的重要指標(biāo)，在云系統(tǒng)中，系統(tǒng)的平均負(fù)載越高，表明系統(tǒng)中的資源利用得越充分，系統(tǒng)的綜合執(zhí)行效率越高。本文中系統(tǒng)平均負(fù)載率是各個(gè)虛擬機(jī)負(fù)載率的均值，計(jì)算式如式（22）所示：

4）多目標(biāo)適應(yīng)度函數(shù)。

為了實(shí)現(xiàn)對(duì)系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本和平均負(fù)載率的多目標(biāo)優(yōu)化，本文采用線性加權(quán)法將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)換成單目標(biāo)優(yōu)化問(wèn)題，為了能夠更好地將系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本和平均負(fù)載率使用線性加權(quán)法轉(zhuǎn)化成單目標(biāo)問(wèn)題，需要對(duì)系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本和平均負(fù)載率進(jìn)行歸一化處理。對(duì)系統(tǒng)執(zhí)行任務(wù)的總時(shí)間和總成本進(jìn)行歸一化處理的過(guò)程如式（25）～（26）所示：

由于對(duì)系統(tǒng)執(zhí)行任務(wù)的總時(shí)間和總成本的優(yōu)化目標(biāo)是盡可能地獲得它們的最小值，而對(duì)于系統(tǒng)平均負(fù)載率而言，則是需要盡可能地取其最大值，因此，為了能夠?qū)⑾到y(tǒng)平均負(fù)載率與系統(tǒng)執(zhí)行任務(wù)的總時(shí)間和總成本一起進(jìn)行優(yōu)化，本文先對(duì)系統(tǒng)平均負(fù)載取其倒數(shù)，然后再進(jìn)行歸一化處理，過(guò)程如式（27）～（28）所示：

由此可以得到本文的適應(yīng)度函數(shù)如式（29）所示：

基于此得到本文的優(yōu)化目標(biāo)如式（30）所示：

2.3 基于正交自適應(yīng)鯨魚(yú)優(yōu)化的云計(jì)算任務(wù)調(diào)度

為了更好地解決云計(jì)算中的任務(wù)調(diào)度問(wèn)題，提高云系統(tǒng)的服務(wù)水平和服務(wù)能力，本文將正交自適應(yīng)鯨魚(yú)優(yōu)化算法用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題，具體過(guò)程描述如下。

2.3.1 云計(jì)算任務(wù)調(diào)度問(wèn)題的編碼

為將OAWOA應(yīng)用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題，首先需要對(duì)云計(jì)算任務(wù)調(diào)度問(wèn)題進(jìn)行編碼，使云計(jì)算任務(wù)調(diào)度問(wèn)題可以輸入到OAWOA中進(jìn)行求解。

本文對(duì)云計(jì)算任務(wù)調(diào)度問(wèn)題的編碼過(guò)程如式（31）～（32）所示：

即將云計(jì)算任務(wù)調(diào)度問(wèn)題編碼為一個(gè)由虛擬機(jī)編號(hào)組成且維數(shù)為任務(wù)數(shù)的位置向量，其中位置向量每一維的索引號(hào)為任務(wù)編號(hào)，表示1～m的一個(gè)隨機(jī)數(shù)，表示一個(gè)鯨魚(yú)的位置向量，為鯨魚(yú)種群中每個(gè)鯨魚(yú)的位置向量的集合。

2.3.2 基于OAWOA的云計(jì)算任務(wù)調(diào)度過(guò)程

基于OAWOA的云計(jì)算任務(wù)調(diào)度流程如圖1所示，具體過(guò)程如下：

步驟1 構(gòu)建鯨魚(yú)的位置向量：將云系統(tǒng)中的任務(wù)和虛擬機(jī)按式（31）～（32）進(jìn)行編碼。

圖1 基于OAWOA的云計(jì)算任務(wù)調(diào)度流程Fig. 1 Flow chart of cloud computing task scheduling based on OAWOA

步驟4 包圍獵物：該階段鯨魚(yú)位置向量的更新方式與WOA的包圍獵物階段位置更新策略一致。

步驟5 泡泡網(wǎng)攻擊獵物：該階段鯨魚(yú)位置向量的更新方式與WOA的泡泡網(wǎng)攻擊獵物階段位置更新策略一致。

步驟6 搜尋獵物：該階段鯨魚(yú)位置向量的更新方式與WOA的搜尋獵物階段位置更新策略一致。

步驟7 更新最優(yōu)位置向量：計(jì)算經(jīng)過(guò)步驟6更新后的鯨魚(yú)種群的位置向量的適應(yīng)度，記錄適應(yīng)度函數(shù)值最小的鯨魚(yú)的位置向量及其適應(yīng)度函數(shù)值，若當(dāng)前的最優(yōu)解比當(dāng)前全局最優(yōu)位置向量更好，則更新當(dāng)前全局最優(yōu)位置向量。

步驟8 正交擴(kuò)展搜索：將經(jīng)過(guò)步驟6更新后的鯨魚(yú)種群的位置向量，進(jìn)行正交擴(kuò)展搜索，增強(qiáng)種群的多樣性，避免陷入局部最優(yōu)狀態(tài)，該階段的具體過(guò)程如算法2所述。

步驟9 判斷算法是否達(dá)到終止條件：若是則終止算法，并返回最優(yōu)解作為云計(jì)算任務(wù)調(diào)度問(wèn)題的解決方案；否則返回步驟3進(jìn)入下一次迭代過(guò)程。

3 仿真實(shí)驗(yàn)與結(jié)果分析

為驗(yàn)證正交自適應(yīng)鯨魚(yú)優(yōu)化算法在解決云計(jì)算任務(wù)調(diào)度問(wèn)題中的性能，將本文提出的OAWOA與傳統(tǒng)鯨魚(yú)優(yōu)化算法（WOA）［12］、粒子群優(yōu)化（PSO）算法［7］、蝙蝠算法（Bat Algorithm， BA）［18］以及其他兩種改進(jìn)的鯨魚(yú)優(yōu)化算法：改進(jìn)互利共生鯨魚(yú)優(yōu)化算法（Whale Optimization Algorithm with a modified Mutualism， WOAmM）［19］和改進(jìn)的鯨魚(yú)優(yōu)化算法（Improved Whale Optimization Algorithm， IWOA）［20］進(jìn)行了對(duì)比。

3.1 實(shí)驗(yàn)設(shè)計(jì)

3.1.1 實(shí)驗(yàn)環(huán)境設(shè)置

為驗(yàn)證OAWOA在解決云計(jì)算任務(wù)調(diào)度問(wèn)題中的可靠性和有效性，本文使用Python 3.9作為編程語(yǔ)言，實(shí)驗(yàn)環(huán)境為PyCharm Community 2021.1，操作系統(tǒng)為Windows 10，CPU型號(hào)為Intel Core i5-7400 CPU @ 3.00 GHz，內(nèi)存為8 GB。云系統(tǒng)中虛擬機(jī)分為低性能組、中性能租和高性能組這3個(gè)組，每組5個(gè)虛擬機(jī)，共計(jì)15個(gè)虛擬機(jī)，每組虛擬機(jī)的編號(hào)、執(zhí)行速度和單位定價(jià)如表2所示。

表2 虛擬機(jī)信息Tab. 2 Virtual machine information

云系統(tǒng)中任務(wù)規(guī)模共分為兩組，分別為50個(gè)任務(wù)和500個(gè)任務(wù)，用來(lái)模擬任務(wù)量較小和任務(wù)量較大兩種情況，其中每一個(gè)任務(wù)的大小都在［1 000，100 000］隨機(jī)產(chǎn)生。

3.1.2 算法及適應(yīng)度函數(shù)參數(shù)設(shè)置

在實(shí)驗(yàn)過(guò)程中，WOA、PSO算法、BA、WOAmM、IWOA以及OAWOA的種群規(guī)模均設(shè)置為50，算法的迭代次數(shù)均為100，對(duì)于其他參數(shù)，WOA、PSO算法、BA、WOAmM以及IWOA分別參照文獻(xiàn)［12］、文獻(xiàn)［7］、文獻(xiàn)［18］、文獻(xiàn)［19］以及文獻(xiàn)［20］設(shè)置。同時(shí)，為綜合考慮系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本和系統(tǒng)平均負(fù)載率這3個(gè)指標(biāo)，本文取，即：

3.2 結(jié)果分析

在實(shí)驗(yàn)過(guò)程中，由于任務(wù)是隨機(jī)產(chǎn)生的，因此為消除隨機(jī)性對(duì)于實(shí)驗(yàn)結(jié)果的影響，本文在每種任務(wù)規(guī)模條件下均進(jìn)行20次實(shí)驗(yàn)，然后取其平均值進(jìn)行分析。各算法在不同任務(wù)規(guī)模下的實(shí)驗(yàn)結(jié)果如表3所示。

表3 任務(wù)規(guī)模為50和500時(shí)適應(yīng)度函數(shù)的最優(yōu)值Tab. 3 Optimal values of fitness function when task scale is 50 and 500

圖2～3給出了當(dāng)任務(wù)規(guī)模為50時(shí)的實(shí)驗(yàn)結(jié)果。

圖2為任務(wù)規(guī)模為50時(shí)的算法收斂過(guò)程，從圖2中可以得出，WOA、PSO算法、WOAmM、IWOA在算法前期都保持著較快的收斂，而B(niǎo)A的收斂則相對(duì)較慢；在對(duì)局部收斂狀態(tài)處理中，WOA、PSO算法、WOAmM、IWOA以及BA都沒(méi)有取得較好的效果。OAWOA不僅在算法前期保持著與WOA、PSO算法、WOAmM以及IWOA相似的較快收斂，而且在其他算法都逐漸陷入局部收斂狀態(tài)時(shí)，OAWOA仍憑借正交擴(kuò)展搜索機(jī)制、自適應(yīng)指數(shù)遞減因子以及雙向搜索機(jī)制，不斷地嘗試對(duì)適應(yīng)度函數(shù)進(jìn)行優(yōu)化，并且在避免陷入局部收斂狀態(tài)，以及對(duì)云計(jì)算任務(wù)調(diào)度問(wèn)題解決方案的優(yōu)化中取得了更好的效果。

圖2 任務(wù)規(guī)模為50時(shí)不同算法的收斂情況Fig. 2 Convergence of different algorithms when task scale is 50

圖3為任務(wù)規(guī)模為50時(shí)各算法對(duì)于系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本以及系統(tǒng)平均負(fù)載率等指標(biāo)的優(yōu)化效果。從圖3中可以看出，當(dāng)任務(wù)規(guī)模為50時(shí)，BA雖然取得了較高的平均負(fù)載率，但卻在成本和時(shí)間方面付出了較大的代價(jià)，并且從表3中也可以看出，BA在解決問(wèn)題中取得的綜合指標(biāo)（適應(yīng)度函數(shù)值）并不是太好，因此在此處不再與BA進(jìn)行具體對(duì)比。對(duì)于除BA之外的其他幾種算法，從圖3中可以看出，當(dāng)任務(wù)規(guī)模為50時(shí)，相較于WOA、PSO算法、WOAmM、IWOA，OAWOA都取得了更好的效果。由此可見(jiàn)，當(dāng)任務(wù)規(guī)模較小時(shí)，在對(duì)于云計(jì)算任務(wù)調(diào)度的多目標(biāo)優(yōu)化問(wèn)題的求解中，OAWOA取得了較為顯著的優(yōu)勢(shì)。

圖4～5給出了當(dāng)任務(wù)規(guī)模為500時(shí)的實(shí)驗(yàn)結(jié)果。

圖4為任務(wù)規(guī)模為500時(shí)的算法收斂過(guò)程，從圖4中可以看出，當(dāng)任務(wù)規(guī)模較大時(shí)，BA已經(jīng)難以取得較好的效果，而其他幾種算法仍保持著較快的收斂，并且取得了較好的優(yōu)化效果。相較于其他幾種算法，本文的OAWOA不僅在算法前期依舊保持著較快的收斂，并且在后期處理局部收斂問(wèn)題時(shí)，依舊取得了相較其他算法更好的效果。

圖4 任務(wù)規(guī)模為500時(shí)不同算法的收斂情況Fig. 4 Convergence of different algorithms when task scale is 500

圖3 任務(wù)規(guī)模為50時(shí)各個(gè)指標(biāo)的優(yōu)化情況Fig. 3 Optimization of each index when task scale is 50

圖5為任務(wù)規(guī)模為500時(shí)各算法對(duì)于系統(tǒng)執(zhí)行任務(wù)的總時(shí)間、總成本以及系統(tǒng)平均負(fù)載率等指標(biāo)的優(yōu)化效果。從圖5可以看出，當(dāng)任務(wù)規(guī)模為500時(shí)，BA同樣存在與任務(wù)規(guī)模為50時(shí)相同的情況，因此在此處也不再與BA進(jìn)行對(duì)比。對(duì)于除BA外的其他幾種算法，當(dāng)任務(wù)規(guī)模為500時(shí)，WOA、WOAmM、IWOA和本文的OAWOA都取得了較好的結(jié)果，并且OAWOA在執(zhí)行任務(wù)的總時(shí)間、總成本以及系統(tǒng)平均負(fù)載率等方面均取得了比WOA、PSO算法、WOAmM和IWOA更好的效果。

圖5 任務(wù)規(guī)模為500時(shí)各個(gè)指標(biāo)的優(yōu)化情況Fig. 5 Optimization of each index when task scale is 500

綜上，無(wú)論任務(wù)規(guī)模較小時(shí)，還是任務(wù)規(guī)模較大時(shí)，本文提出的OAWOA在處理云計(jì)算任務(wù)調(diào)度問(wèn)題時(shí)都可以取得比較顯著的優(yōu)化效果。

4 結(jié)語(yǔ)

本文基于正交設(shè)計(jì)的種群初始化機(jī)制、正交擴(kuò)展搜索機(jī)制、自適應(yīng)指數(shù)遞減因子和雙向搜索機(jī)制提出了一種新的正交自適應(yīng)鯨魚(yú)優(yōu)化算法（OAWOA），并將其應(yīng)用于求解云計(jì)算任務(wù)調(diào)度問(wèn)題。為驗(yàn)證OAWOA的有效性，本文將OAWOA與WOA等五種其他的算法進(jìn)行了對(duì)比，通過(guò)在任務(wù)規(guī)模小和任務(wù)規(guī)模大兩種情況下的實(shí)驗(yàn)結(jié)果表明，本文所提的OAWOA在求解云計(jì)算任務(wù)調(diào)度問(wèn)題時(shí)，在降低任務(wù)執(zhí)行總時(shí)間和總成本與提高系統(tǒng)平均負(fù)載率的多目標(biāo)優(yōu)化方面都取得了更為顯著的優(yōu)勢(shì)。在下一步的研究中，我們將考慮在更為復(fù)雜的情況下（如考慮內(nèi)存、帶寬等因素的影響）如何更好地解決云計(jì)算任務(wù)調(diào)度問(wèn)題，提高云系統(tǒng)的服務(wù)性能。

[1] 王冠宇，王慶生，趙騰.混合蛙跳算法在云計(jì)算資源調(diào)度的策略改進(jìn)［J］.科學(xué)技術(shù)與工程，2018，18（4）：297-303.（WANG G Y， WANG Q S，ZHAO T. The improved strategy of shuffled frog leaping algorithm in the resource scheduling of cloud computing ［J］. Science Technology and Engineering， 2018， 18（4）： 297-303.）

[2] ALDOSSARY M. A review of dynamic resource management in cloud computing environments ［J］. Computer Systems Science and Engineering，2021， 36（3）： 461-476.

[3] KUMAR M， SHARMA S C， GOEL A， et al. A comprehensive survey for scheduling techniques in cloud computing ［J］. Journal of Network and Computer Applications， 2019， 143： 1-33.

[4] HU H Y， LI Z J， HU H， et al. Multi-objective scheduling for scientific workflow in multicloud environment ［J］. Journal of Network and Computer Applications， 2018， 114： 108-122.

[5] ZHANG G H， ODBAL， ABNOOSIAN K. Scheduling mechanisms in the cloud environment： a methodological analysis ［J］. Kybernetes， 2020，49（12）： 2977-2992.

[6] ARORA M， KUMAR V， DAVE M. Task scheduling in cloud infrastructure using optimization technique genetic algorithm ［C］// Proceedings of the 2020 4th World Conference on Smart Trends in Systems， Security and Sustainability. Piscataway：IEEE， 2020： 788-793.

[7] KENNEDY J， EBERHART R. Particle swarm optimization ［C］// Proceedings of the 1995 International Conference on Neural Networks. Piscataway： IEEE， 1995：1942-1948.

[8] DORIGO M， MANIEZZO V， COLORNI A. Ant system： optimization by a colony of cooperating agents ［J］. IEEE Transactions on Systems， Man， and Cybernetics， Part B （Cybernetics）， 1996，26（1）： 29-41.

[9] SANAJ M S， JOE PRATHAP P M. Nature inspired Chaotic Squirrel Search Algorithm （CSSA） for multi objective task scheduling in an IAAS cloud computing atmosphere ［J］. Engineering Science and Technology， an International Journal， 2020， 23（4）： 891-902.

[10] VELLIANGIRI S， KARTHIKEYAN P， ARUL XAVIER V M， et al. Hybrid electro search with genetic algorithm for task scheduling in cloud computing ［J］. Ain Shams Engineering Journal， 2021， 12（1）： 631-639.

[11] NATESAN G， CHOKKALINGAM A. An improved grey wolf optimization algorithm based task scheduling in cloud computing environment ［J］. The International Arab Journal of Information Technology，2020， 17（1）： 73-81.

[12] MIRJALILI S， LEWIS A. The whale optimization algorithm ［J］. Advances in Engineering Software， 2016， 95： 51-67.

[13] XU Z Z， HU Z Y， HEIDARI A A， et al. Orthogonally-designed adapted grasshopper optimization： a comprehensive analysis ［J］. Expert Systems with Applications， 2020， 150： Article No.113282.

[14] SREENU K， SREELATHA M. W-Scheduler： whale optimization for task scheduling in cloud computing ［J］. Cluster Computing， 2019， 22（S1）： 1087-1098.

[15] CHEN X， CHENG L， LIU C， et al. A WOA-based optimization approach for task scheduling in cloud computing systems ［J］. IEEE Systems Journal， 2020， 14（3）： 3117-3128.

[16] 閤大海，李元香，祝婕.基于正交設(shè)計(jì)的反向?qū)W習(xí)差分進(jìn)化算法［J］.華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，45（5）：23-27，44.（XIA D H， LI Y X， ZHU J. Differential evolution algorithm using orthogonal design opposition-based learning ［J］. Journal of Huazhong University of Science and Technology （Natural Science Edition）， 2017， 45（5）： 23-27， 44.）

[17] 郝曉弘，宋吉祥，周強(qiáng)，等.混合策略改進(jìn)的鯨魚(yú)優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（12）：3622-3626，3655.（HAO X H， SONG J X， ZHOU Q， et al. Improved whale optimization algorithm based on hybrid strategy ［J］. Application Research of Computers， 2020， 37（12）： 3622-3626， 3655.）

[18] YANG X S， HOSSEIN GANDOMI A. Bat algorithm： a novel approach for global engineering optimization ［J］. Engineering Computations， 2012，29（5）： 464-483.

[19] CHAKRABORTY S， SAHA A K， SHARMA S， et al. A novel enhanced whale optimization algorithm for global optimization ［J］. Computers and Industrial Engineering， 2021， 153： Article No.107086.

[20] 武澤權(quán)，牟永敏.一種改進(jìn)的鯨魚(yú)優(yōu)化算法［J］.計(jì)算機(jī)應(yīng)用研究，2020，37（12）：3618-3621.（WU Z Q， MU Y M. Improved whale optimization algorithm ［J］. Application Research of Computers， 2020， 37（12）： 3618-3621.）

Cloud computing task scheduling based on orthogonal adaptive whale optimization

ZHANG Jinquan1， XU Shouwei1， LI Xincheng1， WANG Chongyang1， XU Jingzhi2*

（1.College of Computer Science and Engineering，Shandong University of Science and Technology，Qingdao Shandong266590，China；2.Science and Technology Industry Management Office，Shandong University of Science and Technology，Qingdao Shandong266590，China）

Aiming at the problems such as long task completion time， high task execution cost and unbalanced system load in task scheduling， a new cloud computing task scheduling method based on Orthogonal Adaptive Whale Optimization Algorithm （OAWOA）was proposed. Firstly， the Orthogonal Experimental Design （OED） was applied to the population initialization and global search stages to improve and maintain the population diversity， avoid the algorithm from falling into local convergence too early. Then， the adaptive exponential decline factor and bidirectional search mechanism were used to further strengthen the global search ability of the algorithm. Finally， the fitness function was optimized to enable the algorithm to achieve multi-objective optimization. Through the simulation experiments， the proposed algorithm was compared with Whale Optimization Algorithm （WOA）， Particle Swarm Optimization （PSO） algorithm， Bat Algorithm （BA）and two other improved WOAs. Experimental results show that， when the task scale is 50 and 500， the proposed algorithm achieves better convergence effect，has the total time and total cost of the obtained system executing tasks lower than those of other algorithms， and has the load balancing degree only lower than that of BA. In conclusion， the proposed algorithm shows significant advantages in reducing the total time and cost of system executing tasks and improving the system load balancing.

cloud computing; task scheduling; Whale Optimization Algorithm (WOA); Orthogonal Experimental Design (OED); multi-objective optimization

TP399

A

1001-9081（2022）05-1516-08

10.11772/j.issn.1001-9081.2021050806

2021?05?17；

2021?09?15；

2021?09?16。

教育部人文社科基金資助項(xiàng)目（20YJAZH078， 20YJAZH127）；同濟(jì)大學(xué)嵌入式系統(tǒng)與服務(wù)計(jì)算教育部重點(diǎn)實(shí)驗(yàn)室開(kāi)放課題（ESSCKF 2019?06，ESSCKF 2019?08）。

張金泉（1972—），男，四川南充人，副教授，博士，CCF會(huì)員，主要研究方向：云計(jì)算、大數(shù)據(jù)分析與處理、隱私保護(hù)； 徐壽偉（1996—），男，山東煙臺(tái)人，碩士研究生，CCF會(huì)員，主要研究方向：云計(jì)算、邊緣計(jì)算、任務(wù)調(diào)度； 李信誠(chéng)（1997—），男，山東泰安人，碩士研究生，CCF會(huì)員，主要研究方向：云計(jì)算、邊緣計(jì)算、任務(wù)調(diào)度； 王重洋（1996—），男，山東濰坊人，碩士研究生，CCF會(huì)員，主要研究方向：云計(jì)算、隱私保護(hù)； 徐景芝（1973—），女，山東濟(jì)南人，講師，碩士，主要研究方向：云計(jì)算、大數(shù)據(jù)分析與處理。

This work is partially supported by Humanity and Social Science Fund of Ministry of Education （20YJAZH078， 20YJAZH127）， Open Project of Key Laboratory of Embedded System and Service Computing， Ministry of Education （Tongji University） （ESSCKF 2019-06， ESSCKF 2019-08）.

ZHANG Jinquan， born in 1972， Ph. D.， associate professor. His research interests include cloud computing， big data analysis and processing， privacy protection.

XU Shouwei， born in 1996， M. S. candidate. His research interests include cloud computing， edge computing， task scheduling.

LI Xincheng， born in 1997， M. S. candidate. His research interests include cloud computing， edge computing， task scheduling.

WANG Chongyang， born in 1996， M. S. candidate. His research interests include cloud computing， privacy protection.

XU Jingzhi， born in 1973， M. S.， lecturer. Her research interests include cloud computing， big data analysis and processing.