基于遗传算法的计算机系统优化方案

何永琴

（内蒙古财经大学 内蒙古 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.