基于遺傳算法的計算機(jī)系統(tǒng)優(yōu)化方案

何永琴

（內(nèi)蒙古財經(jīng)大學(xué) 內(nèi)蒙古 150100）

0 引言

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

1 遺傳算法

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

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

圖1 遺傳算法流程圖

2 遺傳算法對實時數(shù)據(jù)庫系統(tǒng)的優(yōu)化方案

2.1 查詢優(yōu)化處理流程

結(jié)合內(nèi)存數(shù)據(jù)庫的優(yōu)點，最大限度地節(jié)省內(nèi)存，建立查詢樹T、逆波蘭式F、數(shù)據(jù)對象表t、記錄r，具體算法如下：

語法分析后的樹形結(jié)構(gòu)，遺傳算法的處理僅限于理論階段，所以要對其進(jìn)行編碼，下面分析遺傳算法的流程：

2.2 查詢優(yōu)化策略

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

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

在ERTDBMS的RTQP基于內(nèi)存數(shù)據(jù)庫中，充分發(fā)揮自身的特點,并且根據(jù)查詢引擎重于節(jié)省內(nèi)存的特點，利用遺傳算法并結(jié)合實時數(shù)據(jù)庫的一些規(guī)則作為優(yōu)化方法進(jìn)行查詢優(yōu)化，其規(guī)則為：

基于規(guī)則的邏輯優(yōu)化：邏輯優(yōu)化時仍將采用傳統(tǒng)數(shù)據(jù)庫中常用的一些方法，進(jìn)行關(guān)系代數(shù)的變換。評分標(biāo)準(zhǔn)為同一個選擇操作，執(zhí)行時間越早分?jǐn)?shù)就越少。在RTQP中是由變異算子來控制遺傳下推選擇操作的，所以變異參數(shù)Pm最好接近1。

利用專為連接的基表和外表設(shè)立的規(guī)則，來進(jìn)行物理路徑方面的優(yōu)化。若要進(jìn)行多表連接，那么只判斷連接中最里面的一組表的分?jǐn)?shù)：

1.ROWID=常數(shù)

2.唯一索引列=常數(shù)

3.全體唯一組合索引碼=常數(shù)

4.全體非唯一組合索引碼=常數(shù)

5.非唯一索引=常數(shù)

6.唯一索引列Between低值A(chǔ)nd高值或like ‘C%’（限定范圍）

7.唯一索引列＞常數(shù)或＜常數(shù)

8.非唯一索引列＞常數(shù)或＜常數(shù)

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

10.Order by整個索引

11.全表掃描

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

2.3 算法實現(xiàn)

2.3.1 選擇

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

2.3.2 交叉

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

算法描述如下：

2.3.3 變異

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

2.4 算法性能分析

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

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

表1 交叉率Pc的優(yōu)化結(jié)果

由于交叉過程是按規(guī)則進(jìn)行的，所以PC的值應(yīng)盡量大，但過大的會導(dǎo)致結(jié)果不穩(wěn)定，由表1，理想的Pc=0.7。

3 結(jié)語

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

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

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

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