0 引言

我国海洋运输行业不断发展，船运公司和港口运营企业，每天需要产生和存储海量的船舶运输数据，例如船舶类型、货物类型、目的地、离港时间等。同时，为了统一协调各艘船舶和各个运输任务正常运转，往往需要智能决策系统为船运公司和港口的运营提供决策支持。为此，部分企业和学者提出并设计了船舶运输决策系统，该系统结合了决策支持系统与数据库管理系统，由于该系统中存储的数据种类多，数据量大，因此数据库的读写速率将直接关系到整个系统的运行效率^{[1 -3]}。

在数据库管理系统中，在处理查询时，用户的查询被发送到查询处理器模块以确定最小化开销的最佳访问方法。索引可以大大加快数据检索和选择，但是索引可能对数据修改产生影响，因为随着数据的改变，索引条目也必须跟着改变，并且这些改变必须被记录。查询处理器模块在选择最佳访问方法时使用现有索引集，在数据库的生命周期中，用户的使用可基于日常操作/要求而改变。因此它可能不是静态的，并且现有索引集需要根据需求更改^[4]。

创建合理的索引是实现船舶运输决策良好性能的关键之一，为了创建合理的索引，需要对数据的使用频率，要执行的查询的类型和频率等进行全面的了解。在为当前访问需求创建或更新合理的索引之后，能够实现船舶运输决策系统的良好性能^[5]。

1 数据库索引集创建方法

本文采用遗传算法作为数据库索引表创建的核心算法。遗传算法设计用于搜索大空间以获得最佳函数值，遗传算法采用与自然选择个体适应其环境的相同方式，来求解给定函数的最优值。遗传算法基于自然选择的机制，并结合随机化信息交换的字符串结构和适应度函数，以形成搜索算法。即使遗传算法使用基随机搜索方法，其性能表现仍然优于简单的随机游走方法，因为遗传算法使用历史信息来推测搜索空间中的新区域，并据此改进性能。

本文提出了一种成本最优的遗传算法数据库索引集（CEGODIS）系统，该系统通过数据访问概率，来创建合理的索引，从而提高船舶运输决策支持系统（DSS）的性能。整个系统的基本原理如图 1所示。

CEGODIS系统由C#在.NET中开发，并在Microsoft SQL Server 2000上实现。成本最优遗传算法数据库索引集（CEGODIS）系统在船舶运输决策系统中的实现方法如下：

1）CEGODIS系统通过连接主数据库和访问系统数据库表，提供可用的数据库列表，并从中选择合适的数据库；

2）通过连接所选数据库和访问系统对象表，在由CEGODIS系统提供的数据列表中选择可选项；

3）从CEGODIS系统提供的值列表中选择遗传参数，即群体大小，突变概率，交叉概率和生成的克隆数；

4）CEGODIS系统通过连接所选数据库并访问syscolumns表来获取所选数据库中选定表的属性数量和属性名称；

5）从CEGODIS系统提供的值列表中，选择所选表格中每个属性的访问概率；

6）选择编码方法，即二进制字符串来表示索引集合和查询中的属性集合的染色体，即数据单元ship具有称为type，name，nation和destination的4个属性。索引集染色体1010指示在type和nation属性上的索引的存在。例如，选择来自其中type=“transportation”且name=“HOD”的船舶的国家被表示为查询染色体0110。查询染色体0110指示在访问时对属性type和name的依赖性。查询染色体和索引集染色体的染色体大小等于所选数据库中所选表的属性数；

7）利用所选择的属性访问概率，随机生成群体大小数量相等的查询染色体种群，然后随机生成群体大小数量相等的索引集合染色体种群，其中至少一个属性在具有高访问概率的属性的前30%；

8）用来激励数据库最优索引集的适应性函数，定义为如下形式：

$ \begin{split}\\[-12pt] & FitnessFunction:\\ & f(X,Y) = 1 - (numberOfNoIndexMatches(X,Y)+ \\ & \quad \quad \quad \quad errorIndexes(X,Y) \bullet 0.5) \bullet penalty \end{split} $

(1)

其中：X为查询染色体，Y为索引集染色体。惩罚函数penalty定义为：

$ penalty = \frac{1}{{number of attributes in the selected table}}\text{。} $

(2)

$numberOfNoIndexMatches(X,Y)$ 表示被查询染色体X中被选中，但是没有被索引集染色体Y选中的属性。 $errorIndexes(X,Y)$ 表示被索引集染色体Y选中，但是没有被索引集染色体Y选中的属性。

例如，查询染色体为0110，索引集染色体为1010，那么penalty=1/4=0.25，且此时可以得到其他参数为 $numberOfNoIndexMatches(X,Y) = 1$ ，以及 $errorIndexes(X,Y) = 1$ 。

9）通过使用适应度函数f（X_i ，Y_i ）对每个查询染色体X_i 和相应的索引集合染色体Y_i ，在群体中计算适应度值，其中i=1，2，……。

10）根据适应度函数值f（X_i ，Y_i ）的降序排列X_i 和Y_i 集合的群体，其中i=1，2，……。

11）CEGODIS系统选择最高适应度函数值索引集染色体，作为初始生成群体的最佳索引集，并计算初始群体的平均适应度函数值。

12）对于特定的子代

① 迭代：将最后30%的索引集染色体，即坏索引集染色体或较低适应度索引集染色体替换为索引集染色体的前30%，即良好索引集色度体或更高适应度索引集染色体（即按降序基于适应度函数值的顺序）；

② 交叉：具有少量修改的稳态选择方法用于选择交叉操作的父节点。在当前可用的索引集种群中，每个索引染色体根据交叉概率被选择为父节点，那么一旦选定了2个父节点，则应用交叉操作，即采用了具有少量修改的单点交叉方法。在该方法中，随机选择一个交叉点，然后交换选择的交叉点与2个选定亲本的索引集染色体末端之间的所有值；

③ 突变：对于群体中的每个索引集染色体，应用突变操作。在索引集染色体中随机选择一个比特，然后基于所选择的突变概率，将随机应用的突变（即将值从‘0’改变为‘1’或从‘1’改变为‘0’），应用于选择的索引集染色体；

④ 生成：使用所选择的属性/数据访问概率，随机生成群体大小数量相等的查询染色体。

⑤ 测试：通过使用适应度函数f（X_i ，Y_i ）为每个查询染色体X_i 与相应的索引集染色体Y_i ，在群体中计算适应度值，其中i=1，2，……。根据f（X_i ，Y_i ）的适应度函数值的降序排列X和Y集合的群体；

⑥ 选择：CEGODIS系统选择具有最高适应度函数值索引集合染色体，作为生成总体的最佳索引集合，并找到当前总体的平均适应度函数值。

13）CEGODIS System选择最后一代中的最佳索引集染色体作为推荐的最佳数据库索引集，并且它基于决策支持系统中的当前需求，给出选择用于索引的属性的名称；

14）CEGODIS系统通过连接所选数据库并访问sysindexkeys和sysindexes表来获取现有索引集，并显示现有索引集中属性的名称；

15）CEGODIS系统通过连接所选数据库和访问sysforeignkeys表来查找参考键列表，并显示外键属性的名称；

16）后期，CEGODIS系统连接到所选数据库，并且在推荐索引列表中的属性上创建索引。

2 性能测试

表 1显示了CEGODIS系统的性能测试结果，进行数据查询的性能测试结果。测试的指标包括查询处理的成本，即估计的I/O成本，估计的CPU成本和估计的成本以及执行的操作，表格左侧数据，是基于现有索引集的查询结果，即没有CEGODIS系统时的性能表现。而右侧数据，是通过CEGODIS系统提供的最佳索引，进行测试获得的查询结果。

3 结语

本文针对船舶运输决策系统中的数据库读写和索引技术进行了研究，提出了一种成本最优遗传算法数据库索引集（CEGODIS）系统，能够显著提高船舶运输决策系统中数据库的查询、读写速率，提升了船舶运输决策系统的运行效率。