基于遺傳算法的計算機系統優化方案

何永琴

（內蒙古財經大學 內蒙古 150100）

0 引言

在計算機數據庫系統中時間成本舉足輕重，很多傳統數據庫優化方案都基于時間代價，時間的影響因素有很多，但這種傳統優化并不適用于實時性要求較高的系統。在此情況下，我們借鑒生物學中的遺傳算法來優化這類實時性較高的系統。

1 遺傳算法

利用遺傳算法來解決最優化問題時，首先對可行域中的待選點編碼，在可行域中隨機選取一組編碼作為優化起點，并設定一個適應度變量。接著從初始編碼組中選擇編碼作為繁殖前的樣本。同時利用交叉和變異算子對樣本進行交換。重復上面的過程，直到達到設定的適應度要求。

遺傳算法的基本流程圖如下：

圖1 遺傳算法流程圖

2 遺傳算法對實時數據庫系統的優化方案

2.1 查詢優化處理流程

結合內存數據庫的優點，最大限度地節省內存，建立查詢樹T、逆波蘭式F、數據對象表t、記錄r，具體算法如下：

語法分析后的樹形結構，遺傳算法的處理僅限于理論階段，所以要對其進行編碼，下面分析遺傳算法的流程：

2.2 查詢優化策略

借鑒細胞核中染色體的組成，每一個編碼查詢可表示為一個基因，系統結構就是一個長為L的獨立個體，A=＜A1,A2,…AL＞,第i位基因上存在一組等位基因，所有等位基因構成了整體的結構空間：

V代表可能存在的結構組的最大空間，實際的正確查詢一般為其真子集。

在ERTDBMS的RTQP基于內存數據庫中，充分發揮自身的特點,并且根據查詢引擎重于節省內存的特點，利用遺傳算法并結合實時數據庫的一些規則作為優化方法進行查詢優化，其規則為：

基于規則的邏輯優化：邏輯優化時仍將采用傳統數據庫中常用的一些方法，進行關系代數的變換。評分標準為同一個選擇操作，執行時間越早分數就越少。在RTQP中是由變異算子來控制遺傳下推選擇操作的，所以變異參數Pm最好接近1。

利用專為連接的基表和外表設立的規則，來進行物理路徑方面的優化。若要進行多表連接，那么只判斷連接中最里面的一組表的分數：

1.ROWID=常數

2.唯一索引列=常數

3.全體唯一組合索引碼=常數

4.全體非唯一組合索引碼=常數

5.非唯一索引=常數

6.唯一索引列Between低值And高值或like ‘C%’（限定范圍）

7.唯一索引列＞常數或＜常數

8.非唯一索引列＞常數或＜常數

9.分類/合并（僅對連接）

10.Order by整個索引

11.全表掃描

得到編碼后的查詢語法樹后，將其轉化成n個and子句,把or操作過程提到頂層,再進行接下來的各種遺傳算法操作,對結果中的每一個and子句依據上述規則來判定優化方案的好壞,最終結果的適應度是得分最少的那個。

2.3 算法實現

2.3.1 選擇

選擇一般比較簡單，通過對個體的適應度的比較，使適應度大的被選中的幾率更大，以保證基因始終向適應度更高的方向發展。

2.3.2 交叉

交叉操作的過程是：隨機選取同一代的兩個個體，進行基因權重的比較，決定誰的基因進入下一代。

算法描述如下：

2.3.3 變異

交叉后，通過變異操作來改變查詢中挑選的順序，進行下推選擇，將結果作為下一次連接操作的輸入目的。算法描述如下：

2.4 算法性能分析

測試實驗使用的是ERTDBMS數據庫，測試用例包含的限制條件有5-10個，涉及的表有4-10個，共20組用例。

算法中的兩個參數Pc和Pm分別控制交叉和變異發生的概率。以Pc為例，測試了時間（5，10，15，20，25）（ms）和20個優化組的平均時間（ms），結果如下：

表1 交叉率Pc的優化結果

由于交叉過程是按規則進行的，所以PC的值應盡量大，但過大的會導致結果不穩定，由表1，理想的Pc=0.7。

3 結語

本文以ERTDBMS為例，結合遺傳算法，提出了RTQP方案，使查詢可以根據不同的業務、事務進行處理。但它還存在許多需要改進的地方。

[1]劉云生,遲巖.基于遺傳算法的實時內存數據庫查詢優化[J].小型微型計算機系統,2005,26(3):466-469.DOI:10.3969/j.issn.1000-1220.2005.03.034.

[2]曾杰,陳芳炯,韋崗等.基于遺傳算法的IP網流量優化算法[J].計算機工程與應用,2006,42(4):125-127,134.

[3]鄔毅松,談恩民.基于遺傳算法的IP核測試調度優化[J].計算機系統應用,2011,20(8):181-183.DOI:10.3969/j.issn.1003-3254.2011.08.040.