基於GAPSO算法的最優自適應策略決策方法與流程

2023-07-04 20:02:56 5

本發明屬於計算機技術領域，涉及一種最優自適應策略決策方法，具體涉及一種基於gapso算法的自適應策略空間中最優自適應策略的決策方法。適用於自適應策略空間巨大、搜索過程耗時較長的自適應軟體系統中，滿足了自適應軟體需要快速決策的系統需求。

背景技術：

隨著越來越多的軟體系統運行在網際網路、雲計算、大數據等動態、開放、多變、難以預測和控制的環境中，軟體系統面臨的變化越來越多，也越來越複雜。自適應系統是為了使軟體系統能夠在上述複雜環境中正常運行而提出來的。自適應軟體系統的核心功能之一是當變化發生時，系統能夠快速地對該變化做出響應使軟體可保持正常運行。因此，能夠在由數量巨大的、表示對已經發生的變化的調整方法的自適應策略構成的策略空間中快速決策出最優自適應策略就成了影響自適應軟體系統功能和性能的關鍵因素。

目前，國內外的相關學者及研究人員多採用基於並行任務分配調度機制的決策方法和基於強化學習技術的決策方法來解決該問題。2008年，局部合作的多智能體q-learning算法被提出，該算法在存在合作關係的agent之間進行聯合動作的選取，否則，執行單個agent的q-learning算法，局部合作的多智能體q-learning算法未度量每個agent對系統的影響並且依靠經驗區分agent之間的合作與獨立狀態，導致在訓練周期不斷增大的情況下算法性能下降。

在基於並行任務分配調度機制的決策方法中，根據調度策略在執行過程中是否可以變化，基於並行任務分配調度機制的決策方法可分為基於靜態分配調度方法的決策方法和基於動態分配調度方法的決策方法。基於靜態分配調度方法的決策方法無法對系統中實時產生的任務實現較好的調度和負載均衡。基於動態分配調度算法的決策方法可在系統運行階段接受新的任務，將任務分配給相應的處理機並對處理機上的任務進行動態調整，該動態調整過程即為從自適應策略空間中決策產生最優自適應策略的過程，該過程決策出一個使系統中各處理機上的負載達到均衡狀態的最優自適應策略。在自適應策略空間較為巨大的情況下，基於動態分配調度算法的決策方法在決策產生最優自適應策略時耗時較長，效率較低。

授權公告號為cn104778507b、名稱為「一種基於自適應粒子群算法的樓宇智能用電策略獲取方法」的中國專利，公開了一種基於自適應粒子群算法的樓宇智能用電策略獲取方法，該方法針對擁有至少兩種供電源的樓宇，首先在符合各個供電源特性要求的前提下，獲取預設數量該樓宇在預設未來應用實施時間內各個時間段中的用電方法，然後根據各個用電方案進行迭代，分別獲取每一次迭代過程中最低的用電成本，最後在所有迭代過程分別對應的最低用電成本中，獲取最低的用電成本，該用電成本對應用電方案即為該樓宇在預設未來應用實施時間內各個時間段中的最優用電策略。該方法在供電源較多、用電方案空間巨大的情況下，算法效率十分低下；同時該算法局限於智能用電策略的獲取，適用範圍狹窄，並且沒有考慮供電源間可能發生的衝突。

技術實現要素：

本發明的目的在於克服上述已有技術的不足，提出了一種基於gapso算法的最優自適應策略決策方法，用於解決現有技術在自適應策略空間中策略數量較為巨大的情況下決策效率低的技術問題。

為實現上述目的，本發明採取的技術方案包括如下步驟：

(1)獲取自適應系統的決策需求：

根據自適應系統的決策目標及自適應系統或計算機因素對決策目標的影響，獲取對決策目標產生影響的因素和每個因素的取值，若每個因素的取值為非連續取值，則這些影響因素和每個因素的取值即為自適應系統的決策需求，若因素的取值為連續取值，對連續取值進行離散化，則這些影響因素和離散後的取值即為自適應系統的決策需求；

(2)建立自適應策略空間：

根據自適應系統的決策需求，利用多維表結構中的各個維度分別表示對決策目標產生影響的不同因素，並將決策需求中每個影響因素的取值分別放入到多維表結構表示該影響因素的維度中，得到所有自適應策略，所有自適應策略構成自適應策略空間；

(3)構造適應度函數：

利用自適應系統的決策需求、決策需求中的每個因素對決策目標的影響和每個因素的調整方式，在自適應系統和決策目標的限制和約束下，構造適應度函數；

(4)利用gapso算法對自適應策略空間進行並行搜索：

(4a)建立存放自適應策略的中間策略空間和目標策略空間，並令中間策略空間和目標策略空間均為空；

(4b)利用適應度函數，計算自適應策略空間中不同自適應策略的適應度函數值，得到多個自適應策略的適應度函數值；

(4c)利用ga算法，從自適應策略空間中並行選擇最好適應度函數值對應的自適應策略，並將這些策略加入到目標策略空間中；

(4d)利用ga算法，對步驟(4c)選擇剩餘的適應度函數值對應的自適應策略並行進行交叉，得到進行交叉後的自適應策略；

(4e)利用ga算法，對交叉後的自適應策略並行進行變異，並將變異後的自適應策略加入到中間策略空間中；

(4f)利用pso算法，對中間策略空間中的自適應策略並行進行更新，並將並行更新後的自適應策略加入到目標策略空間中，得到包含更新後的自適應策略的目標策略空間；

(5)獲取最優自適應策略：

(5a)確定最優自適應策略決策的終止閾值：

重複執行步驟(4)，得到多個目標策略空間，並利用適應度函數計算多個目標策略空間中所有自適應策略的適應度函數值，然後將滿足決策目標及限制和約束條件的適應度函數值作為最優自適應策略決策終止時的適應度值閾值，同時將滿足決策目標及限制和約束條件的迭代次數值作為最優自適應策略決策終止時的迭代次數閾值；

(5b)判斷最優自適應策略決策過程是否結束：

若目標策略空間的迭代次數達到迭代次數閾值或目標策略空間中存在一個策略其適應度值達到適應度值閾值，最優自適應策略決策過程結束，目標策略空間中適應度值最優的策略即為最優自適應策略；否則，重複執行步驟(4)至步驟(5)。

本發明與現有技術相比，具有如下優點：

第一，本發明使用ga算法對自適應策略空間並行進行計算得到中間策略空間，然後使用ga算法和pso算法對中間策略空間並行進行計算得到目標策略空間，並從目標策略空間中決策得到最優自適應策略，該決策過程使用了並行任務分配調度機制、ga算法和pso算法，在策略空間十分巨大時，降低了決策過程需要的時間，有效地提高了決策的效率，使自適應系統能夠迅速對變化做出響應，滿足了自適應系統需要迅速對變化做出調整以保證軟體正常運行的需求。

第二，本發明在ga算法之前計算了自適應策略空間中每一個自適應策略的適應度函數值，根據適應度函數值從自適應策略空間中選擇最優適應度函數值對應的自適應策略進入到目標策略空間，在迭代過程中，也是根據適應度函數值從中間策略空間中選擇最優適應度函數值對應的自適應策略進入到目標策略空間，有效避免了自適應系統中多個變化同時發生的情況下，多個變化的自適應策略相互衝突的情況，可有效解決多個變化同時發生時自適應策略的決策問題，為變化的調整提供策略支撐。

第三，本發明可被應用在多個領域中，適用範圍廣。

第四，本發明可使用迭代次數閾值或適應度值閾值作為最優自適應策略決策過程的結束條件，與使用單個結束條件相比，使用兩種結束條件的方式更加靈活，得到的最優自適應策略也更能滿足自適應系統的需求。

附圖說明

圖1為本發明的實現流程圖。

具體實施方式

以下結合附圖和具體實施例，對本發明作進一步詳細說明：

參照圖1、基於gapso算法的最優自適應策略決策方法，包括如下步驟：

步驟1、獲取自適應系統的決策需求：

根據自適應系統的決策目標及自適應系統或計算機因素對決策目標的影響，獲取對決策目標產生影響的因素和每個因素的取值，若每個因素的取值為非連續取值，則這些影響因素和每個因素的取值即為自適應系統的決策需求，若因素的取值為連續取值，對連續取值進行離散化，則這些影響因素和離散後的取值即為自適應系統的決策需求，並對決策需求進行存儲，可使用xml、excel和文本文檔txt三種格式中的任何一種格式存儲決策需求，本實例使用文本文檔txt存儲決策需求。

步驟2、建立自適應策略空間：

根據自適應系統的決策需求，利用多維表結構中的各個維度分別表示對決策目標產生影響的不同因素，並將決策需求中每個影響因素的取值分別放入到多維表結構表示該影響因素的維度中，得到所有自適應策略，所有自適應策略構成自適應策略空間；

步驟3、構造適應度函數：

利用自適應系統的決策需求、決策需求中的每個因素對決策目標的影響和每個因素的調整方式，在自適應系統和決策目標的限制和約束下，構造適應度函數；本實例使用將自適應策略各個維度上的取值直接相加的和函數作為適應度函數。

步驟4、利用gapso算法對自適應策略空間進行並行搜索：

步驟4a)建立由自適應策略構成的中間策略空間和目標策略空間，中間策略空間存儲由ga算法的交叉和變異產生的自適應策略，目標策略空間存儲經ga算法的選擇和pso算法的更新產生的自適應策略。每一代迭代開始時，令中間策略空間和目標策略空間均為空；

步驟4b)利用適應度函數，計算自適應策略空間中不同自適應策略的適應度函數值，得到多個自適應策略的適應度函數值；

步驟4c)利用ga算法，根據自適應策略空間中自適應策略的適應度函數的值，從自適應策略空間中按照選擇概率並行選擇最好適應度函數值對應的自適應策略，並將這些策略加入到目標策略空間中；

步驟4d)利用ga算法，根據交叉概率，從步驟(4c)選擇剩餘的適應度函數值對應的自適應策略中並行選擇出偶數個自適應策略，並在選擇出的偶數個自適應策略中每兩個自適應策略為一組，在每一組中的兩個自適應策略中選擇同一維度，將該組中的兩個自適應策略在該維度上的值交換，得到兩個新的自適應策略；從步驟(4c)選擇剩餘的適應度函數值對應的自適應策略中選擇未進行交換操作的自適應策略和由交換操作產生的自適應策略組成自適應策略空間；

步驟4e)利用ga算法，根據變異概率，從執行步驟(4d)後得到的自適應策略空間中並行選擇出若干個策略，再對每一個策略選擇出一個維度，將該維度上的取值更改為該維度表示的因素的取值集合中與當前取值相異的值；由自適應策略空間中未進行更改的自適應策略和由更改產生的自適應策略組成中間策略空間；

步驟4f)利用pso算法，對中間策略空間中的自適應策略並行進行更新：並將並行更新後的自適應策略加入到目標策略空間中，得到包含更新後的自適應策略的目標策略空間：

(4f1)對第t代自適應策略空間中的任一自適應策略xid(t)進行ga算法的選擇、交叉和變異，得到自適應策略xga(t)，再計算每一代的自適應策略xid(j)、xga(j)的適應度函數值，然後將適應度函數值中最大適應度函數值對應的自適應策略作為自適應策略xid(t)的局部最優自適應策略pid(t)，其中，t≥1，j＝1,2,...,t；

(4f2)計算第t，t≥1代自適應策略空間和中間策略空間中每一個自適應策略的適應度函數值，然後將適應度函數值中最大適應度函數值對應的自適應策略作為第t代的全局最優自適應策略pgd(t)，若第t+1代的全局最優自適應策略pgd(t+1)的適應度函數值劣於pgd(t)的適應度函數值，則將pgd(t)賦值給pgd(t+1)，否則，pgd(t+1)保持不變；

(4f3)計算第t代中間策略空間中自適應策略xi'd(t)的策略更新步長vid(t)，計算公式如下：

vid(t)＝w×vid(t-1)+c1×r1×(pi'd(t-1)-xi'd(t-1))+c2×r2×(pgd(t-1)-xi'd(t-1))

其中，t≥2，w為慣性因子，取值範圍為[0,1]；c1、c2為加速因子，是正常數；r1、r2為隨機數，取值位於區間[0,1]內，pi'd(t)是xi'd(t)局部最優自適應策略；

(4f4)計算第t+1代中由自適應策略xid(t)產生的自適應策略xid(t+1)，計算公式為：

xid(t+1)＝xid(t)+vid(t+1)

該公式使用自適應策略xid(t)和自適應策略xid(t)的策略更新步長vid(t+1)計算得到自適應策略xid(t+1)，使自適應策略逐漸靠近最優自適應策略；其中，vid(t+1)為第t+1代自適應策略xi'd(t+1)的策略更新步長，計算公式為：

vid(t+1)＝w×vid(t)+c1×r1×(pid(t)-xid(t))+c2×r2×(pgd(t)-xid(t))

該公式綜合使用了自適應策略xid(t)，自適應策略xid(t)的策略修改步長vid(t)、局部最優策略pid(t)和全局最優策略pgd(t)計算策略修改步長vid(t+1)，使自適應策略沿著朝向最優自適應策略的方向前進，其中，t≥1，w為慣性因子，取值範圍為[0,1]；c1、c2為加速因子，是正常數；r1、r2為隨機數，取值位於區間[0,1]內。

(5)獲取最優自適應策略：

(5a)確定最優自適應策略決策的終止閾值：

重複執行步驟(4)，得到多個目標策略空間，並利用適應度函數計算多個目標策略空間中所有自適應策略的適應度函數值，然後將滿足決策目標及限制和約束條件的適應度函數值作為最優自適應策略決策終止時的適應度值閾值，同時將滿足決策目標及限制和約束條件的迭代次數值作為最優自適應策略決策終止時的迭代次數閾值；這裡採用迭代次數作為最優自適應策略決策終止條件；

(5b)判斷最優自適應策略決策過程是否結束：

若目標策略空間的迭代次數達到迭代次數閾值或目標策略空間中存在一個策略其適應度值達到適應度值閾值，最優自適應策略決策過程結束，目標策略空間中適應度值最優的策略即為最優自適應策略；否則，重複執行步驟(4)至步驟(5)。