一種基於二叉空間分割樹的資源調度優化方法
2023-05-18 13:06:36 2
一種基於二叉空間分割樹的資源調度優化方法
【專利摘要】本發明實施例提供了一種基於二叉空間分割樹的資源調度優化方法，本方法採取基於二叉空間分割樹驅動搜索，並在選擇算子作用產生重複個體出現時，實現遺傳算法的有方向性在搜索空間內進行局域搜索、鄰域搜索和跨域搜索的自變異驅動，從而有效避免了重複個體的出現，維持了種群的多樣性和改變了遺傳算法隨機搜索的特性。
【專利說明】—種基於二叉空間分割樹的資源調度優化方法
【技術領域】
[0001]本發明涉及信息【技術領域】，具體涉及一種基於二叉空間分割樹的資源調度優化方法。
【背景技術】
[0002]遺傳算法是以達爾文進化論思想和孟德爾遺傳理論為基礎，模擬生物進化繁殖、變異、競爭、選擇的基本特性，提出通過選擇、重組和變異三種操作求解現實問題的自組織和自適應的人工智慧算法。染色體作為遺傳算法的主要載體，是由若干個具有一定特徵的基因組合而成。遺傳算法藉助遺傳算子對當代種群染色體進行交叉和變異操作，產生子代種群；交叉算子具有較強的搜索能力，且種群的多樣性決定交叉算子的搜索能力；變異算子則通過變異操作可以產生當代種群中沒有的染色體基因，以維持種群個體的多樣性
[137]，且實驗發現，若取消變異作用，遺傳算法無法趨於收斂。
[0003]本方案發明在對傳統的遺傳算法進行研究的過程中發現，，因為傳統遺傳算法變異操作只有一個固定的經驗概率值，變異操作具有隨機性，導致了參數空間的搜索無方向性，且帶來大量的無效計算，造成了算法的收斂性較差；並且標準遺傳算法在選擇和交叉遺傳算子的作用下，進化過程中不可避免產生大量的重複出現的個體，且變異操作具有隨機性和盲目性的缺陷。因此，現有技術有待改進和提高。
【發明內容】
[0004]本發明實施例提供一種基於二叉空間分割樹的資源調度優化方法，以期提供一種可以進行空間局域搜索、鄰域搜索和跨域搜索遞進性方向引導的自編譯方法，從而有效避免重複個體的出現。
[0005]本發明實施例提供一種基於二叉空間分割樹的資源調度優化方法，所述方法包括:
[0006]初始化種群:對種群S= {S (I),S (2)，…，S (t)}中的t個種類資源進行對應編碼，並生成前後隨機排列的染色體個體，設D為第i個染色體個體S (i)的總維度，R是基因取值解析度，則整個搜索空間的大小為RD ；
[0007]計算個體適應度:根據預設的適應度函數，計算種群中每個染色體個體的適應度值；
[0008]根據二叉空間分割樹在所述搜索空間中插入染色體個體S (i):從二叉空間分割樹的根節點出發，根據第一預設條件確定s (i)屬於左節點空間還是右節點空間，並沿著所在子空間的節點方向繼續向下搜索，搜索到葉子節點為止；
[0009]若所述S (i)與二叉空間分割樹中先前節點都不重複，則直接插入二叉空間分割樹，作為新的葉子節點；其中，若所述S (i)的父節點無左子節點，則所述S (i)作為左子節點直接繼承其父節點搜索子空間，若所述S (i)的父節點已有左子節點S (i ')，則根據第二預設條件進行左子節點和右子節點的位置調整；[0010]若所述S (i)插入二叉空間分割樹且進行了子空間分割操作時，檢查分割後的左子節點和右子節點搜索空間是否已處於不可分割的狀態，若是，則設置所述s (i)位置為關閉狀態；
[0011]若在插入新染色體個體S (j)時出現S (j)與S (i)重複，則在S (i)所映射的搜索子空間Subspace (S (i))範圍內對S (j)進行變異操作，或者在Subspace (S (i))的鄰域範圍內對S (j)進行變異操作,或者不受Subspace (S (i))範圍的限制對S (j)進行變異操作。
[0012]其中，所述若所述S (i)的父節點已有左子節點S (i ')，則根據第二預設條件進行左子節點和右子節點的位置調整包括:
[0013]將S (i)和S (i』)進行維度比較，選擇比較維度最大的基因位，所述比較維度為
[0014]^axi d(S(i), S(HIk),
[0015]其中，d(S(i)，S(i' )|k)為S (i)和S (i』)在第k個基因位的維度距離，且d(S(i),S(i/ ) |k)=S(i)-S(i/ );
[0016]從所選擇的基因位所映射的維度，對左子節點的搜索空間進行等距離的子空間分害I]，並依據S (i)和S (i』)在基因位的基因值大小，按照左節點小於右節點的原則，進行左子節點和右子節點的位置調整。
[0017]所述對種群S= {S (I),S (2)，…，S (t)}中的t個種類資源進行對應編碼包括:對所述種群S= {S (I),S (2)，…，S (t)}中的t個種類資源採取四位十六進位編碼，或者六位十六進位編碼，或者整數編碼。
[0018]進一步的，在計算個體適應度之前包括:將編碼的種群S={S (I), S (2)，…，S(t)}中的t個種類資源進行解碼。
[0019]其中，所述若在插入染色體個體S (j)時出現S (j)與S (i)重複，則在S (i)所映射的搜索子空間Subspace (S (i))範圍內對S (j)進行變異操作包括:
[0020]確定Subspace (S (i))開關位置是否為開放狀態，若是，則當S (i)的左子節點或右子節點為空，則選擇Subspace (S (i))維度空間最大的基因位，S (j)在所述Subspace(S (i))維度空間範圍內對選擇的相應基因位進行基因變異。
[0021]所述若在插入染色體個體S (j)時出現S (j)與S (i)重複,則在Subspace (S(i))的鄰域範圍內對S (j)進行變異操作包括:
[0022]確定所述S (i)所映射的搜索子空間Subspace (S (i))開關位置是否為關閉狀態，若是，則回退至所述S (i)的父節點，並判斷所述S (i)的兄弟節點S (r)所映射的搜索子空間Subspace (S (r))開關位置是否為開放狀態,若是，
[0023]則掃描新染色體S (j)的每個基因是否屬於Subspace (S (r))，將不屬於的基因在Subspace (S (r))所對應的維度空間內進行隨機變異。
[0024]所述若在插入染色體個體S (j)時出現S (j)與S (i)重複，，則不受Subspace(S (i))範圍的限制對S (j)進行變異操作包括:
[0025]確定所述S (i)的左子節 點空間和右子節點空間是否均為關閉狀態，若是，
[0026]則新染色體S ( j)的基因在其初始維度空間範圍內隨機變異為S ( j』)，從二叉空間分割樹的根節點搜索S (j』)所屬節點子空間。[0027]本發明實施例提供的基於二叉空間分割樹的資源調度優化方法，採取基於二叉空間分割樹驅動搜索，並在選擇算子作用產生重複個體出現時，實現遺傳算法的有方向性在搜索空間內進行局域搜索、鄰域搜索和跨域搜索的自變異驅動，從而有效避免了重複個體的出現，維持了種群的多樣性和改變了遺傳算法隨機搜索的特性。
【專利附圖】
【附圖說明】
[0028]圖1是本發明實施例提供的一種基於二叉空間分割樹的資源調度優化方法流程示意圖。
【具體實施方式】
[0029]本發明實施例提供一種基於二叉空間分割樹的資源調度優化方法，以期提供一種可以進行空間局域搜索、鄰域搜索和跨域搜索遞進性方向引導的自編譯方法，有效避免重複個體的出現。
[0030]為了使本【技術領域】的人員更好地理解本發明方案，下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分的實施例，而不是全部的實施例。基於本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都應當屬於本發明保護的範圍。
[0031]本發明實施例提供一種基於二叉空間分割樹的資源調度優化方法，包括:
[0032]初始化種群:對種群S= {S (I),S (2)，…，S (t)}中的t個種類資源進行對應編碼，並生成前後隨機排列的染色體個體，設D為第i個染色體個體S (i)的總維度，R是基因取值解析度，則整個搜索空間的大小為RD ；
[0033]計算個體適應度:根據預設的適應度函數，計算種群中每個染色體個體的適應度值；
[0034]根據二叉空間分割樹在所述搜索空間中插入染色體個體S (i):從二叉空間分割樹的根節點出發，根據第一預設條件確定S (i)屬於左節點空間還是右節點空間，並沿著所在子空間的節點方向繼續向下搜索，搜索到葉子節點為止；
[0035]若所述S (i)與二叉空間分割樹中先前節點都不重複，則直接插入二叉空間分割樹，作為新的葉子節點；其中，若所述S (i)的父節點無左子節點，則所述S (i)作為左子節點直接繼承其父節點搜索子空間，若所述S (i)的父節點已有左子節點S (i ')，則根據第二預設條件進行左子節點和右子節點的位置調整；
[0036]若所述S (i)插入二叉空間分割樹且進行了子空間分割操作時，檢查分割後的左子節點和右子節點搜索空間是否已處於不可分割的狀態，若是，則設置所述S (i)位置為關閉狀態；
[0037]若在插入新染色體個體S (j)時出現S (j)與S (i)重複，則在S (i)所映射的搜索子空間Subspace (S (i))範圍內對S (j)進行變異操作，或者在Subspace (S (i))的鄰域範圍內對S (j)進行變異操作,或者不受Subspace (S (i))範圍的限制對S (j)進行變異操作。
[0038]所述若所述S (i)的父節點已有左子節點S (i』)，則根據第二預設條件進行左子節點和右子節點的位置調整包括:
[0039]將所述S (i)和所述S (i』)進行維度比較，選擇比較維度最大的基因位，所述比較維度為
[0040]^iaxi d(S(i); S(V)Ik),
[0041]其中，所述d(s(i)，s(i' )|k)為s (i)和s (i』)在第k個基因位的維度距離，且d(S(i),S(i/ ) |k)=S(i)-S(i/ );
[0042]從所選擇的基因位所映射的維度，對左子節點的搜索空間進行等距離的子空間分害I]，並依據所述S (i)和所述S (i ')在所述基因位的基因值大小，按照左節點小於右節點的原則，進行左子節點和右子節點的位置調整。
[0043]其中，所述對種群S= {S (I),S (2)，…，S (t)}中的t個種類資源進行對應編碼包括:對所述種群S= {S (I), S (2)，…，S (t)}中的t個種類資源採取四位十六進位編碼，或者六位十六進位編碼，或者整數編碼。
[0044]在此基礎上，在計算個體適應度之前包括:將編碼的種群S={S (I), S (2)，…，S(t)}中的t個種類資源進行解碼。
[0045]進一步的，所述若在插入染色體個體S (j)時出現S (j)與S (i)重複，則在S (i)所映射的搜索子空間Subspace (S (i))範圍內對S (j)進行變異操作包括:
[0046]確定Subspace (S (i))開關位置是否為開放狀態，若是，則當S (i)的左子節點或右子節點為空，則選擇S ubspace (S (i))維度空間最大的基因位，S (j)在所述Subspace(S (i))維度空間範圍內對選擇的相應基因位進行基因變異。
[0047]同時，所述S (j)在所述Subspace (S (i))維度空間範圍內對選擇的相應基因位進行基因變異後，若變異後的S (j)依然與S (i)相同，，則停止對S (j)再進行變異操作。
[0048]所述若在插入染色體個體S (j)時出現S (j)與S (i)重複,貝U在Subspace (S
(i))的鄰域範圍內對S (j)進行變異操作包括:
[0049]確定所述S (i)所映射的搜索子空間Subspace (S (i))開關位置是否為關閉狀態，若是，則回退至所述S (i)的父節點，並判斷所述S (i)的兄弟節點S (r)所映射的搜索子空間Subspace (S (r))開關位置是否為開放狀態,若是，
[0050]則掃描新染色體S (j)的每個基因是否屬於Subspace (S (r))，將不屬於的基因在Subspace (S (r))所對應的維度空間內進行隨機變異。
[0051]所述若在插入染色體個體S (j)時出現S (j)與S (i)重複，，則不受Subspace(S (i))範圍的限制對S (j)進行變異操作包括:
[0052]確定所述S (i)的左子節點空間和右子節點空間是否均為關閉狀態，若是，
[0053]則新染色體S ( j)的基因在其初始維度空間範圍內隨機變異為S ( j』)，從二叉空間分割樹的根節點搜索S (j』)所屬節點子空間。
[0054]由上可見，本發明實施例提供的基於二叉空間分割樹的資源調度優化方法，採取基於二叉空間分割樹驅動搜索，並在選擇算子作用產生重複個體出現時，實現遺傳算法的有方向性在搜索空間內進行局域搜索、鄰域搜索和跨域搜索的自變異驅動，從而有效避免了重複個體的出現，維持了種群的多樣性和改變了遺傳算法隨機搜索的特性。
[0055]本發明實施例還提供一種基於二叉空間分割樹的資源調度優化方法，參見圖1所示，包括:
[0056]S100、初始化種群:對種群S={S (I), S (2)，…，S⑴}中的t個種類資源進行對應編碼，並生成前後隨機排列的染色體個體，設D為第i個染色體個體S (i)的總維度，R是基因取值解析度，則整個搜索空間的大小為RD ；
[0057]其中，本發明實施例中所說的S (i)的總維度D是指染色體個體S (i)的基因數量，基因取值解析度是指基因可能取值數。
[0058]S200、計算個體適應度:根據預設的適應度函數，計算種群中每個染色體個體的適
應度值；
[0059]S300、根據二叉空間分割樹在所述搜索空間中插入染色體個體S (i)0
[0060]二叉空間分割樹(Binary Space Partitioning,簡稱BSP)是一種空間分割技術，即任何平面都可以將空間分割為兩個半空間，如果任何半空間中有一個平面，可進一步將此半空間分割為更小的兩個子空間，通過這種遞歸方法將空間使用超平面劃分為凸面體集合，採用多邊形列表將子空間分割得越來越小，最終構造一個BSP 二叉空間分割樹。BSP樹是一種用來對N維空間中的元素進行快速有效的排序和查找的數據結構，BSP樹表示整個空間，BSP樹中任一節點表示一個子空間，每個節點對應一個超平面，將這個節點表示的空間分割成兩個子空間。最初，整個區域被定義為BSP樹的根，之後，繼續劃分區域，一旦把凹形區域劃分為兩個凸形區域(在最好情況下)或凹多邊形，命名這些區域成為其父節點的子節點。
[0061]本文算法將整個參數空間定義為BSP樹根空間，BSP樹每個節點數據結構包含個體的染色體信息、所代表的搜索空間、節點開關以及指針群這四個信息，其中指針群用於關聯父節點和左右兩個子節點，節點開關表示該節點是否已經處於原子狀態，其所有維度搜索空間是否可再分割。
[0062]步驟S300包括:
[0063]a、從BSP樹的根節點出發，面對兩個節點方向時，首先判斷新染色體個體屬於左節點空間，還是屬於右節點空間，不斷沿著所在子空間的節點方向繼續向下搜索，直到葉子節點為止；
[0064]b、若該染色體個體與BSP樹中先前節點都不重複，則說明該染色體個體是全新的，可以直接插進BSP樹，作為新的葉子節點；
[0065]C、若父節點無左子節點，新染色體個體作為左葉子節點，則直接繼承其父節點搜索子空間；
[0066]d、若父節點已經存在左子節點，則應將新染色體和已有的左子節點進行維度比較，選擇比較維度最大的基因位，即
[0067]
【權利要求】
1.一種基於二叉空間分割樹的資源調度優化方法，其特徵在於，所述方法包括: 初始化種群:對種群S= {S (I), S (2)，…，S (t)}中的t個種類資源進行對應編碼，並生成前後隨機排列的染色體個體，設D為第i個染色體個體S (i)的總維度，R是基因取值解析度，則整個搜索空間的大小為RD ； 計算個體適應度:根據預設的適應度函數，計算種群中每個染色體個體的適應度值； 根據二叉空間分割樹在所述搜索空間中插入染色體個體S (i):從二叉空間分割樹的根節點出發，根據第一預設條件確定S (i)屬於左節點空間還是右節點空間，並沿著所在子空間的節點方向繼續向下搜索，搜索到葉子節點為止； 若所述S (i)與二叉空間分割樹中先前節點都不重複，則直接插入二叉空間分割樹，作為新的葉子節點；其中，若所述S (i)的父節點無左子節點，則所述S (i)作為左子節點直接繼承其父節點搜索子空間，若所述S (i)的父節點已有左子節點S (i ')，則根據第二預設條件進行左子節點和右子節點的位置調整； 若所述S (i)插入二叉空間分割樹且進行了子空間分割操作時，檢查分割後的左子節點和右子節點搜索空間是否已處於不可分割的狀態，若是，則設置所述S (i)位置為關閉狀態； 若在插入新染色體個體S (j)時出現S (j)與S (i)重複，則在S (i)所映射的搜索子空間Subspace (S (i))範圍內對S (j )進行變異操作,或者在Subspace (S (i))的鄰域範圍內對S (j)進行變異操作,或者不受Subspace (S (i))範圍的限制對S (j)進行變異操作。
2.根據權利要求1所述的方法，其特徵在於，所述若所述S(i)的父節點已有左子節點S (i』)，則根據第二預設條 件進行左子節點和右子節點的位置調整包括: 將S (i)和S (i』)進行維度比較，選擇比較維度最大的基因位，比較維度為
max d(S(i), S(i')|k), kc[l,Dl' 其中，d(s(i)，s(i' ) |k)為s (i)和s (i』)在第k個基因位的維度距離，且d(S(i),S(i/ ) |k)=S(i)-S(i/ ); 從所選擇的基因位所映射的維度，對左子節點的搜索空間進行等距離的子空間分割，並依據S (i)和S (i』)在基因位的基因值大小，按照左節點小於右節點的原則，進行左子節點和右子節點的位置調整。
3.根據權利要求1所述的方法，其特徵在於，所述對種群S={S (I),S (2)，…，S (t)}中的t個種類資源進行對應編碼包括:對所述種群S={S (I),S (2)，…，S (t)}中的t個種類資源採取四位十六進位編碼，或者六位十六進位編碼，或者整數編碼。
4.根據權利要求3所述的方法，其特徵在於，在計算個體適應度之前包括:將編碼的種群S={S (I),S (2)，-,S (t)}中的t個種類資源進行解碼。
5.根據權利要求1所述的方法，其特徵在於，所述若在插入染色體個體S(j)時出現S(j)與S (i)重複，則在S (i)所映射的搜索子空間Subspace (S (i))範圍內對S (j)進行變異操作包括: 確定Subspace (S (i))開關位置是否為開放狀態，若是，則當S (i)的左子節點或右子節點為空，則選擇Subspace (S (i))維度空間最大的基因位,S (j)在所述Subspace (S(i))維度空間範圍內對選擇的相應基因位進行基因變異。
6.根據權利要求5所述的方法，其特徵在於，所述S(j)在所述Subspace (S (i))維度空間範圍內對選擇的相應基因位進行基因變異後，若變異後的S (j)依然與S (i)相同，則停止對S (j)再進行變異操作。
7.根據權利要求1所述的方法，其特徵在於，所述若在插入染色體個體S(j)時出現S(j)與S (i)重複，則在Subspace (S (i))的鄰域範圍內對S (j)進行變異操作包括: 確定所述S (i)所映射的搜索子空間Subspace (S (i))開關位置是否為關閉狀態，若是，則回退至所述S (i)的父節點，並判斷所述S (i)的兄弟節點S (r)所映射的搜索子空間Subspace (S (r))開關位置是否為開放狀態，若是，則掃描新染色體S (j)的每個基因是否屬於Subspace (S (r)),將不屬於的基因在Subspace (S (r))所對應的維度空間內進行隨機變異。
8.根據權利要求1所述的方法，其特徵在於，所述若在插入染色體個體S(j)時出現S(j)與S (i)重複，則不受Subspace (S (i))範圍的限制對S (j)進行變異操作包括: 確定所述S (i)的左子節點空間和右子節點空間是否均為關閉狀態，若是， 則新染色體S (j)的基因在其初始維度空間範圍內隨機變異為S (j ')，從二叉空間分割樹的根節點搜索s (j y)所屬節 點子空間。
【文檔編號】G06F17/30GK103886375SQ201410156332
【公開日】2014年6月25日 申請日期:2014年4月17日 優先權日:2014年4月17日
【發明者】張黎明 申請人:張黎明