基于内存映射文件的进化算法数据存储引擎

1、基于内存映射文件的进化算法数据存储引擎姜三义，代真真，李阳，周爱民JIANG Sanyi, DAI Zhenzhen, LI Yang, ZHOU Aimin华东师范大学 计算机科学技术系，上海 200241Department of Computer Science & Technology, East China Normal University, Shanghai 200241, ChinaJIANG Sanyi, DAI Zhenzhen, LI Yang, et al. Data storage engine based on memory-mapped file for

2、evolutionary algorithms. Computer Engineering and Applications, 2015, 51（1）：49-53.Abstract：In order to observe and analyze the execution of Evolutionary Algorithms（EAs）, large volumes of data generatedduring algorithm execution are always stored in disk files. An embedded data storage engine, named

3、as the Evolutionary Algorithm Database（EADB）, provides simple yet flexible data storage interfaces for evolutionary algorithms, and facilitates fast large data storage by using memory-mapped files. Compared to storage methods using traditional file I/O and general database storage engine, EADB is tr

4、emendous faster.Key words：evolutionary algorithm; memory-mapped file; data storage engine; file I/O摘 要：为了观察和分析进化算法的执行情况，往往需要将算法执行过程中产生的大量数据存储在磁盘文件中。用于 进 化 算 法 的 嵌 入 式 数 据 存 储 引 擎 EADB（Evolutionary Algorithm Database）提 供 了 简 便 灵 活 的 数 据 存 储 接 口 ，通 过使用内存映射文件技术来实现数据的快速和大量存储。相较于传统文件 I/O 存储方式和一般的通用数据存储引

5、擎，EADB 大大加快了存储速度。关键词：进化算法；内存映射文件；数据存储引擎；文件 I/O文献标志码：A中图分类号：TP311doi：10.3778/j.issn.1002-8331.1303-01661引言基 于 统 计 和 机 器 学 习 的 进 化 算 法 目 前 日 益 引 起 人 们的重视。进化算法1是一种通过多次迭代搜索来获取 全局最优解的随机优化算法2。作为一类启发式搜索算 法 ，是 否 具 备 良 好 的 搜 索 记 忆 功 能 ，即 通 过 一 定 方 式 存 储 并 利 用 已 搜 索 的 解 空 间 ，是 评 价 算 法 好 坏 的 关 键 之 一。从本质上来说，进化算

6、法维护的种群和其他信息实 际 上 可 以 看 作 是 一 个 动 态 变 化 的 数 据 集（数 据 库）。 当 前及历史数据集隐含了进化算法搜索的规律，因此可以 通 过 模 式 识 别 和 机 器 学 习 的 方 法 来 挖 掘 隐 含 在 这 些 数 据 集 中 的 规 律 并 指 导 进 化 算 法 的 搜 索 。 有 效 存 储 和 组 织当前和历史群体信息，是实现这类算法的前提。由于进化算法的搜索空间往往比较大，存储记忆时 需要平衡算法效率和磁盘空间3。随着计算机磁盘容量的迅速增长和单位容量成本的降低，可以将更多的算法数据存储到磁盘中。但是在性能上，现有的通用数据库 技 术 或 传

7、统 文 件 存 储 方 式 并 不 能 很 好 地 满 足 这 种 需 求。使用通用数据库时，需要额外搭建专有的数据服务 系 统 ，进 行 数 据 库 维 护 ，并 且 由 于 数 据 库 索 引 等 机 制 的 存在，数据库对于大量实时算法数据的存储效率并不理 想 。 算 法 设 计 人 员 因 而 往 往 将 数 据 以 文 件 的 形 式 直 接 存 储 到 磁 盘 上 。 由 于 磁 盘 I/O 的 效 率 问 题 ，采 用 传 统 文 件 方 式 保 存 数 据 会 大 量 增 加 算 法 的 执 行 时 间 。 现 代 操 作 系 统 支 持 基 于 虚 拟 内 存 技 术 的 内

8、 存 映 射 文 件 机 制 。 通 过 使 用 内 存 映 射 文 件 ，存 储 速 度 相 比 于 传 统 文 件 I/O 方式可以得到极大提升4。内 存 映 射 是 将 磁 盘 上 的 文 件 或 部 分 文 件 内 容 映 射到 进 程 地 址 空 间 内 部 区 域 的 一 种 机 制 。 通 过 创 建 内 存基金项目：国家自然科学基金（No.61273313）。作者简介：姜三义（1981），男，硕士研究生，研究领域为进化算法，图像处理；代真真（1987），硕士研究生，研究领域为进化计 算，实验设计；李阳（1989），硕士研究生，研究领域为进化计算；周爱民（1978），副教授，主研

9、领域为进化计算，机器 学习。E-mail：sanyi0127收稿日期：2013-03-14修回日期：2013-06-04文章编号：1002-8331（2015）01-0049-05CNKI 网络优先出版：2013-06-26, 502015，51（1）Computer Engineering and Applications 计算机工程与应用映射文件，应用程序可以直接读写内存来访问磁盘文件数 据 ，相 比 于 使 用 文 件 的 读 写 函 数 具 有 更 快 的 I/O 速 度 。 在 Windows 和 Linux 操 作 系 统 中 都 支 持 内 存 映 射 文 件 机 制 ，通 过

10、使 用 系 统 提 供 的 编 程 接 口 ，应 用 程 序 可 以利用内存映射机制提高 I/O 效率。内存映射文件可以被直接应用于程序中，对于一些 简 单 的 程 序 是 完 全 可 行 的 。 但 是 在 进 行 复 杂 数 据 结 构 的存储组织，并且需要确保大量数据和文件的可靠和安 全 时 ，需 要 进 行 复 杂 的 代 码 设 计 和 编 码 调 试 工 作 ，以 解 决合理分配和动态扩展数据文件，存储不同数据结构等 问 题 ，这 对 程 序 编 码 人 员 提 出 了 很 高 的 要 求 ，在 很 大 程 度上限制了内存映射文件技术被广泛利用。本 文 介 绍 了 使 用 C +

11、编 程 语 言 实 现 的 嵌 入 式 数 据 存 储 引 擎（EADB），EADB 利 用 内 存 映 射 文 件 实 现 了 数 据 存 储 ，支 持 Linux 和 Windows 这 两 个 不 同 平 台 ，提 供 统一的读写接口，支持复杂数据结构的存储组织。通过 使用 EADB，应用程序在获得 I/O 性能提升的同时，可以 减少编码工作量。通过在进化算法中使用 EADB，提高 了进化算法执行过程中的数据存储效率。独立的连续完整的地址空间。基于程序的局部性原理，操作系统仅将运行进程所必需的一部分指令装入内存， 在 进 程 执 行 时 通 过 请 求 调 入 和 置 换 功 能 进 行

12、 内 外 存 数 据交换，使进程能够持续运行。虚 拟 内 存 技 术 不 仅 仅 解 决 了 物 理 内 存 容 量 不 足 的 问题，它的出现使得操作系统发生了巨大的变化。当今 大 部 分 操 作 系 统（包 括 Windows 和 Linux）在 I/O 系 统 中 均 采 用 了 文 件 缓 存 机 制（在 Windows 中 称 为 系 统 缓 存 ， 在 Linux 中称为页面缓存），在内核虚拟地址空间中分配 一 个 分 段 用 于 文 件 数 据 缓 存 。 操 作 系 统 进 一 步 将 该 分 段划分为块，每一块包含若干分页（在 32 位 Windows 系 统 中 ，页 面

13、大 小 是 4 KB，分 块 大 小 是 256 KB；在 32 位 Linux 系 统 中 ，页 面 大 小 是 4 KB，分 块 大 小 也 是 4 KB）。在 访 问 文 件 时 ，操 作 系 统 始 终 按 块 为 单 位（即 使 只 访 问 一个字节数据）将文件数据拷贝到文件缓存中。当文件 缓存中的页面被调度到物理内存中后，内存与磁盘文件 之间建立了字节上一对一的关系，在页内的数据访问都 是在物理内存中完成的，避免了频繁的文件 I/O，极大提 高 了 读 写 能 力 。 同 时 ，由 于 虚 拟 内 存 的“ 按 需 调 度 ”原 则 ，只 将 一 部 分 数 据 而 非 整 个 文

14、 件 调 入 内 存 ，因 而 可 以12-13节约大量物理内存 。内 存 映 射 文 件 在 此 基 础 上 进 一 步 加 快 了 文 件 访 问 速 度 。 使 用 传 统 文 件 I/O 方 式 时 ，仍 然 需 要 通 过 系 统 调 用（即 文 件 读 写 函 数）从 内 核 空 间 将 数 据 复 制 到 用 户 空 间，即读操作使用的内存缓冲区。而建立内存映射文件 后，操作系统将进程的虚拟页面直接映射到系统文件缓 存上，使得进程可以直接访问这一部分内存。通过建立 内 存 映 射 文 件 ，一 方 面 避 免 了 使 用 系 统 调 用 ，访 问 速 度 得 到 数 量 级 的

15、提 升 ；另 一 方 面 ，在 用 户 空 间 中 无 需 对 文 件 内 容 进 行 缓 冲 ，不 仅 减 少 了 物 理 内 存 复 制 工 作 ，还 节2算法记录本 文 称 进 化 算 法 迭 代 过 程 中 产 生 的 解 为“ 算 法 记 录 ”。 不 同 进 化 算 法 的 执 行 框 架 基 本 相 同 ，首 先 进 行 种 群随机初始化和个体适应度计算，然后进行有限次数的 迭 代 使 得 群 体 在 搜 索 空 间 中 不 断 进 化 。 每 一 次 迭 代 包 含的步骤包括：重组、变异、适应值评估和选择等。每一次迭代产生的解包含染色体、适应值或其他信息5。 进化算法的种群个体

16、（即染色体）可以表示为确定长度的二进制位串或格雷码，也可以使用符号集、实数或实 数数组来表示。进化算法作为一类启发式搜索算法，也被成功应用于多目标优化领域6-7。每个种群个体的适应值，在单目标优化和多目标优化问题中的表示方式是不 一 样 的 。 在 单 目 标 优 化 问 题 中 ，适 应 值 是 一 维 的 变 量 ； 而 在 多 目 标 优 化 问 题 中 ，适 应 值 则 一 般 是 多 维 的 向 量 。 由此分析，算法记录中的内容在形式上包括一维变量和 多维向量，所以可以使用数组来统一存储记录内容8-9。同 一 个 进 化 算 法 在 每 一 次 迭 代 中 需 要 保 存 的 数

17、据 记录的数量有可能不同，例如在基于分解技术的多目标 进化算法（Decomposition based Multi-Objective Evolu- tionary Algorithm，MOEA/D）求 解 背 包 问 题 的 算 法 中 ， 每一代最优群体的个体数量可能是不同的10。但是，在 同一个进化算法的一次执行过程中，算法记录的内容在 结构上是一致的。14省了一半的物理内存空间 。内 存 映 射 文 件 带 来 的 另 一 个 优 点 是 在 编 写 数 据 存 储程序的时候，在内存及外存中只需要定义一套数据结 构，可以直接将内存映射区域中的数据看作程序中定义 的数据结构类型对应的对象

18、15。内存映射文件允许将文件的一部分映射到内存中， 从 而 可 以 处 理 非 常 大 的 文 件 。 Windows 支 持 的 文 件 大小 最 大 达 到 16 EB。 Linux 支 持 的 最 大 文 件 大 小 在 不 同的 文 件 系 统 上 略 有 差 别 ，大 部 分 系 统 都 实 现 了 LFS（大 文件系统）技术，文件大小可以达到或超过 2 TB。4存储引擎的实现与使用4.1存储引擎的数据表示方法本 研 究 定 义 了 一 种 数 据 描 述 方 法 ：ASON（Algo- rithm Structured Object Notation），即 算 法 结 构 化 对

19、象 表 示 法 ，来 描 述 算 法 记 录 ，可 以 满 足 进 化 算 法 记 录 的 数据 存 储 要 求 。 每 一 个 ASON 所 描 述 的 算 法 记 录 可 以 包 含 若 干 个 数 据 字 段 ，每 一 个 数 据 字 段 都 是 一 个 键 值 对3内存映射文件内 存 映 射 文 件 的 实 现 借 助 于 操 作 系 统 底 层 的 虚 拟 内 存 机 制 11。 使 用 虚 拟 内 存 的 目 的 是 为 了 弥 补 物 理 内 存的容量不足问题。在虚拟内存系统中，每个进程拥有姜三义，代真真，李 阳，等：基于内存映射文件的进化算法数据存储引擎2015，51（1）51

20、（key-value pair），每 个 键 名 是 一 串 字 符 串 ，键 值 是 一 个数值数组。例如，ASON 可以表示如下使用键值对描述 的算法记录： “popsiz”：200， “gen”：1， “fitness”：100，30，“chromo”：62 000，76 000，58 000，23 000记 录 中 的“popsiz”、“gen”、“fitness”、“chromo”分 别 表 示 种 群 大 小 、当 前 迭 代 值 、个 体 适 应 度 和 染 色 体 。 使 用 ASON 可以实现对象内数据字段的灵活组合，不仅可 以包含进化算法的适应度及染色体，还可以包含其他的

21、数据字段。本文为简单起见，只考虑染色体和适应度值 信息。使用 C+宏“ASON”在程序中按照 C+数据流的序 列化方式构建算法记录，采用 STL 的 std：vector 容器作 为数组类型。宏 ASON 的使用方法参见如下代码：std：vector<double>vec； / 填入数据，使 vec 包含100，30ASONObj obj=ASON（“popsiz”<<200<<“gen”<<1<<“fitness”<<vec）；/构造 ASONObj 对象宏“ASON”返 回 的 是 抽 象 数 据 结 构 类 型 AS

22、ONObj 的 对 象 实 例 。 在 内 存 中 ，一 个 ASONObj 对 象 表 示 为 二 进制字节序列 。首先是 4 个字节表示对象长度 ，紧接着 是若干个数据字段，最后是结束标志符。每个数据字段 的 第 一 个 1 个 字 节 表 示 字 段 值 类 型 ；然 后 是 一 条 字 符 串 ，表 示 字 段 名 称 ，由 字 符 0结 尾 ；接 着 是 4 个 字 节 表 示字段维数，然后是表示数组数据的若干个字节。这种 数据结构支持了对象内数据字段的遍历。ASONObj 对 象的内存结构如图 1 所示。ByteString=20，/变长字节串MaxKey=127；其 中 的 Mi

23、nKey 和 MaxKey 表 示 类 型 代 号 的 最 小 、 最大值，分别是 1 和 127，这样所有的类型值可以用一 个 字 节 表 示 。 因 为 数 据 字 段 的 第 一 个 字 节 表 示 字 段 值 的 类 型 ，所 以 结 束 字 段 只 需 要 一 个 字 节 用 于 存 储 EOO 表示对象结束，而无需作为一个完整的数据字段。ASONObj 提 供 objdata（）和 objsize（）函 数 将 数 据 提 供给调用者，表示整个对象的数据内容和长度。4.2数据文件结构的设计数 据 文 件 的 内 容 包 含 两 部 分 ：文 件 头 和 记 录 列 表 。 文件头部

24、包含数据存储引擎的版本号、文件长度等基本 信息，还包括文件空间的信息。记录顺序的保存在文件 中，每一条算法记录又被封装为一条“文件记录”。类 DataFileHeader 定 义 了 数 据 文 件 的 头 部 数 据 结 构，其中的主要数据成员如图 2 所示。版本号（version）8 Byte文件长度（fileLength）8 Byte未使用位置（unused）8 Byte文件剩余空间长度（unusedLength）定长记录标记（fixed）缓存（cache）数据指针（data）8 Byte1 Byte64 512 Byte4 Byte图 2 文件头数据结构文件的头部占据 64 KB 的空

25、间。预留较大的空间便 于对文件头部数据结构的扩展定义。文件头部数据结构 的头部大小用“file_header_size”表示，值为 65 536。变 量“data”是 C + 中 的 一 种 实 现 手 法 ，变 量“data” 的地址就是指向第一条文件记录的地址。变 量“unused”用 于 存 储 未 使 用 位 置 在 文 件 中 的 地 址 偏 移 量 ，初 始 值 为 file_header_size。 变 量“unused- Length”用于存储文件中尚未使用空间的字节数。数据 文 件 的 大 小 是 按 照 需 求 量 逐 步 扩 充 的 。 当“unused- Length”

26、小 于 下 一 条 文 件 记 录 的 长 度 时 ，存 储 引 擎 自 动 地扩大文件，可以在实际过程中调整扩增的大小。变 量“fixed”用 于 表 明 该 文 件 中 的 所 有 文 件 记 录 是 否长度相等。为了加快数据存储速度，本研究并没有在 数 据 文 件 中 加 入 任 何 索 引 机 制 。 对 于 所 有 文 件 记 录 等 长 的 情 况（fixed 等 于 1），EADB 可 以 通 过 类 似 C+数 组 下标访问的方式快速地访问每一条文件记录，这是最快 的 数 据 寻 址 方 式 。 对 于 变 长 记 录 则 需 要 通 过 遍 历 每 一条文件记录，获取并叠加记

27、录的长度来逐步定位。数据字段 1对象长度数据字段 2结束字段EOO值类型 字段名称 字段名称1 Byte 字符串长 4 Byte度+1 Byte值数组N Byte4 Byte1 Byte图 1 ASONObj 对象的内存结构图中注明了各个域所占用的存储空间大小，单位是 字节（Byte），其中值数组所占用的存储空间大小 N = 值 维数×该类型数值变量所占用字节数。字段值的类型是 一个 C+枚举值：enum Type MinKey=1， EOO=0，/对象结束标志符NumberDouble=1，/双精度（8 Byte 存储空间） NumberFloat=2，/单精度（4 Byte 存储

28、空间） NumberInt=16，/32 位整型（4 Byte 存储空间） NumberUInt=17，/无符号 32 位整型 NumberLong=18，/64 位整型（8 Byte 存储空间） NumberULong=19，/64 为无符号整型52 2015，51（1）Computer Engineering and Applications 计算机工程与应用每 一 条 文 件 记 录 都 包 含 自 身 的 头 部 结 构 和 数 据体。在存储进化算法的算法记录时，文件记录的头部只 需 包 含 文 件 记 录 长 度 。 类 FileRecord 定 义 了 文 件 记 录 的数据结构，

29、如图 3 所示。FILE-WRITE-AT-POSITION 用 于 改 变 文 件 中 的 数据 。 对 于 新 增 加 数 据 记 录 ，则 算 法 的 输 入 address 即 为 变 量“unused”的 值 。 写 入 数 据 时 执 行 内 存 拷 贝 操 作 MEMORY-COPY，然 后 调 整 文 件 头 部 unused 和 unused- Length 两个状态变量的值。FILE-READ-AT-POSITION 用 于 读 取 文 件 中 的 数 据 。 在 数 据 读 取 时 ，创 建 内 存 映 射 区 域 之 后 ，根 据 偏 移 量定位，可以准确获得数据记录在

30、内存中的地址。通过 C+强制类型转换，就可以从该地址构造出指向数据结 构 DataFileHeader 对 象 的 指 针 ，从 而 获 得 记 录 的 数 据 内 容和长度，并最终转换为 ASONObj 对象。4.4 ASON 对象的精简存储每 一 个 ASON 对 象 中 都 添 加 了 字 段 名 称 以 及 其 他 的一些辅助信息，这将造成数据存储空间的浪费。为了 避 免 空 间 浪 费 ，当 DataFileHeader 的“fixed”变 量 为 1 的 时候，利用其中的“cache”字段，将一个完整的 ASONObj 对象保存在“cache”中，然后，在文件记录中仅保存数据 字

31、段 的 值 数 组 。 这 样 可 以 有 效 减 少 所 需 存 储 空 间 。 在 获 取 记 录 的 时 候 ，根 据“cache”中 缓 存 的 ASONObj 结 构 信 息 ，可 以 从 精 简 的 文 件 记 录 中 快 速 的 构 造 出 完 整 的 ASONObj 对象。使 用 上 述 方 法 要 求 算 法 记 录 的 长 度 不 超 过 64 512 字 节 。 此 外 ，若 是 文 件 中 记 录 长 度 不 一 致 ，也 无 法 使 用 如上所属的精简存储方式。4.5 存储引擎程序应用接口EADB 的 应 用 接 口 通 过 C+类 EADB 提 供 ，主 要 包 括

32、 open、close、Add 和 Get 四个方法。Open 和 Close 用于 打开（创建）和关闭一个数据文件；Add 用于向数据文件 中 添 加 算 法 记 录 ；Get 用 于 获 取 算 法 记 录 。 操 作 接 口 使 用的数据结构是 ASONObj。Class EADBbool open（std：string filename，bool fixed，bool fileStepSiz，.）；void close（）；bool Add（ASONObj obj）；ASONObj Ge（t int32_t index）；Open 方 法 参 数“filename”表 示 数 据 文

33、件 名 称 ；参 数 “fixed”用于指示是否所有记录的内容及长度一致：一致 则 可 以 使 用 ASON 对 象 的 精 简 存 储 ；参 数“fileStepSiz” 用 于 指 示 数 据 文 件 扩 容 的 步 长 。 根 据 不 同 算 法 设 定 合 理的步长，可以在一定程度上加快存储速度。4.6 数据文件的查看与数据导出EADB 支 持 通 过 存 入 的 顺 序 来 访 问 数 据 记 录 。 为 了查看数据文件中的数据，本研究开发了 GUI 数据文件 管 理 程 序 ，用 于 显 示 数 据 文 件 的 基 本 信 息 ，例 如 迭 代 次 数、种群数量等，查询算法记录，或

34、者将算法记录根据某 种规则导出为文本文件，用以在 Matlab 或其他程序中使记录长度（length） 4 Byte数据指针（data） 4 Byte图 3 文件记录数据结构记 录 的 数 据 结 构 的 变 量“length”存 放 记 录 的 长 度 ，其值中包含头部自身的长度。变量“data”是 C+中的一 种 实 现 手 法 ，变 量“data”的 地 址 就 是 记 录 中 数 据 的 其 实 地址。文件记录数据结构的头部大小用“record_header_ size”表示，值为 4。4.3内存映射文件的数据访问方法创建内存映射文件的时候，新建文件的大小至少应 为 文 件 头 的 大

35、 小（FileHeaderSize）。 在 执 行 创 建 内 存 映 射文件的步骤之后，需要对文件头部数据结构的字段进 行初始化。在创建内存映射文件时，可以得到内存映射区域的 内 存 地 址 ，通 过 该 地 址 可 以 在 内 存 中 直 接 访 问 文 件 数 据。如果从文件起始处建立内存映射区域，则偏移位置0 就是 DataFileHeader 对象在内存中的起始字节。 对 于 每 一 条 文 件 记 录 ，也 是 相 同 方 法 ，从 文 件 中 偏移位置 65 536 开始，通过类型转换得到文件记录对象的 指针，可以实现文件记录对象的逐条遍历。算法 1 和算法 2 分别描述了对内存

36、映射文件进行数 据写入和读取的操作。同时假定由 MAP-VIEW 算法来 创建内存映射区域，所创建区域的内存地址为 position， MEMORY-COPY 算法执行内存复制。算法 1 内存映射文件数据写入FILE-WRITE-AT-POSITION（address，obj）1. robj->objdata（），obj->objsize（）2. positionMAP-VIEW（address）3. MEMORY-COPY（r，position）4. unusedunused+r->length5. unusedLengthunusedLength-r->length

37、算法 2 内存映射文件数据读取FILE-READ-AT-POSITION（address）1. addressaddress+file_header_size2. positionMAP-VIEW（address）3. rcast position to（FileRecord*）4. objconstruct ASONObj from r->data5. return obj算法 1 和算法 2 通过偏移地址访问数据记录，其中的 对 象“obj”是 ASONObj 类 型 的 实 例 。 偏 移 地 址 address 不包含文件头部长度，需要在访问数据文件内容时将其 纳入。姜三义，代真

38、真，李 阳，等：基于内存映射文件的进化算法数据存储引擎2015，51（1）53用算法记录进行算法可视化等分析工作。2.01.21.00.20文件 I/OEADBLevelDB5实验结果及分析5.1实验 1 基本性能测试为了测试数据存储引擎的性能，本文将 EADB 与采 用 标 准 C 函 数 库 的 文 件 I/O 方 式 和 用 谷 歌 公 司 的 Lev- elDB 用 来 存 储 变 长 字 符 串 进 行 实 验 对 比 ，观 察 其 数 据 存 储 速 度 。 LevelDB 是 谷 歌 公 司 推 出 的 超 高 性 能 文 件 数据库，支持键值

39、对存储和索引。本文分别用较长数据和较短数据做比较，这样更能 对比不同方法的性能。较短数据测试中，随机生成小于201 字节的可读字符串；较长数据测试中，随机生成小于5 001 字节的可读字符串。两个实验各自包含 30 组数据， 每组数据的数量分别为 20 000 的倍数。每次实验时对每 组 数 据 进 行 30 次 测 试 然 后 计 算 耗 时 均 值 。 在 Windows2008 Server R2 64 位 操 作 系 统 上 运 行 ，CPU 为 Intel Xeon X5680，3.33 GHz，96 GB 内 存 ，外 部 存 储 器 为 Promise VessRAID 1 84

40、0 s SCSI RAID5 磁 盘 阵 列 ，其 中 的 磁 盘 驱 动 器 为 西 部 数 据 WD2002FYPS 硬 盘（2 TB，7 200 r/s）。存储较短数据的三种方式的效率曲线如图 4所示。1020304050 60字符串数量/104 条Windows 上较长数据实验结果图 5由 此 可 见 ，对 于 存 储 任 何 数 量 级 别 的 数 据 ，EADB都 表 现 出 明 显 的 优 越 性 ，且 随 着 数 据 的 增 多 ，性 能 优 势 越明显。5.2 实验 2 多目标进化算法实验进化算法有很多分支，本文选取较为复杂的 MOEA/D 算 法 求 解 多 目 标 背 包

41、 问 题 进 行 实 验 。 通 过 选 择 多 个 不 同 的 测 试 题 ，设 定 不 同 的 背 包 个 数（代 表 目 标 数）、物 品 数（即 变 量 数 、决 定 染 色 体 长 度）和 种 群 大 小 ，来 代 表 不 同难易程度的问题。此 次 实 验 是 在 MOEA/D 算 法 的 每 一 代 计 算 之 后 保 存 染 色 体 、适 应 度 以 及 权 重 三 个 指 标 ，这 三 个 指 标 的 数 据 类 型 均 为 实 数 数 组 。 算 法 对 15 个 测 试 题 进 行 6 轮 运 算；测试环境与实验 1 相同。实验结果如表 1 所示。表 1 MOEA/D 算法

42、测试结果1 400文件 I/OEADBLevelDB1 2001 000800600400方法时间/s使用文件 I/O使用 EADB3 473570200由表 1 数据可以看出，在使用 MOEA/D 算法解决问题的过程中存储算法数据时，使用 EADB 耗费的时间仅 仅是文件 I/O 方式的 16%。换句话说，使用文件 I/O 方法 时，算法程序执行所消耗的 84%以上时间是进行文件 I/O 操作，真正执行算法运算的时间不足 16%。由此可以得 出 结 论 ：使 用 EADB 替 代 文 件 I/O 可 以 大 大 提 高 算 法 程 序执行的效率。0102030405060字符串数量/10 条

43、4图 4Windows 上较短数据实验结果图 4 结 果 显 示 出 ，对 于 短 数 据 ，用 EADB 比 文 件 I/O和 LevelDB 的 速 度 快 。 随 着 存 储 数 据 的 数 量 的 增 加 ， EADB 的优势越来越明显。由于各种因素的影响，例如 计算机中同步处理了大量其他任务，导致实验结果的曲 线 有 一 些 跳 跃 ，但 是 可 以 得 出 ，各 种 存 储 方 式 的 存 储 效 率均呈线形变化，这意味着数据存储速度可以在数据量 持 续 增 大 时 基 本 保 持 不 变 。 比 较 来 说 EADB 方 式 性 能 最好，存储速率最高。存储较长数据的三种方式的效

44、率曲线如图 5 所示。 图 5 结 果 显 示 对 于 更 长 数 据 的 存 储 ，EADB 仍 然 比文 件 I/O 和 LevelDB 快 ，并 且 随 着 存 储 数 据 的 数 量 的 增 加 ，EADB 速 度 上 的 优 势 越 来 越 明 显 。 同 时 可 以 看 出 ， 随 着 数 据 量 的 增 多 ，LevelDB 存 储 方 式 越 来 越 不 稳 定 。 比较来说 EADB 方式对长数据的存储性能也是最好，存 储速率最高。6结语进化算法的应用范围十分广泛，已经在众多科学计 算 领 域 和 工 程 领 域 得 到 了 应 用 16。 许 多 进 化 算 法 的 执 行

45、时间往往达到或超过数小时，其执行过程中产生的算 法 记 录 是 进 行 算 法 分 析 的 重 要 依 据 。 EADB 通 过 采 用 内 存 映 射 文 件 技 术 ，实 现 了 快 速 数 据 存 储 ，减 少 进 化 算 法执行过程中因数据存储而带来的时间耗费，有效促进 了进化算法的实现。同时，EADB 作为一个嵌入式数据 存储引擎，不仅使用简便，还可以在多个方面进行优化， 进一步提升速度。（下转 101 页）时间/ms时间/104ms殷凤梅，濮光宁，张 江，等：基于线性方程组的门限匿名认证方案2015，51（1）1014结束语基于线性方程组的求解理论，提出了一种门限匿名 认证方案，其

46、安全性依赖于离散对数求解的困难性。与 已 有 的 方 案 相 比 ，本 文 方 案 不 仅 能 实 现 匿 名 认 证 ，更 能 实 现 匿 名 追 踪 ，且 具 有 门 限 性 质 。 整 个 过 程 中 ，计 算 代 价 相 对 较 小 ，匿 名 认 证 过 程 相 对 较 简 单 。 在 电 子 商 务 、 移动通信等众多领域，本文方案将具有广阔的应用前景。latorC/Proceedings of Communication Systems，Networksand Applications Conference，2010：56-59.6 周彦伟，吴振强，蒋李.分布式网络环境下的跨域匿名

47、认证 机制J.计算机应用，2010，30（8）：2120-2124.7 宋 成 ，孙 宇 琼 ，彭 维 平 ，等.改 进 的 直 接 匿 名 认 证 方 案 J.北 京邮电大学学报，2011，34（3）：62-65.8Hirose S，Yoshida S.A user authentication scheme withidentity and location privacyC/Proceedings of the 6th Australasian Conference on Information Security and Pri- vacy，Sydney，Australia，July 1

48、1-13，2001，2119：235-246.参考文献：1 Ateniese G，Herzberg mobility or how toA，Krawczyk H，et al.Untraceabletravel incognitoJ.Computer Net-9 田子健，王继林，伍云霞.一个动态的可追踪匿名认证方案J.电子与信息学报，2005，27（11）：1737-1740.works，1999，31（8）：871-884.2 Kong J J，Hong X Y，Gerla M.An identity-free and on- demand routing scheme against ano

49、nymity threats in mobile Ad Hoc networksJ.IEEE Transactions on Mobile Com - puting，Frequency，2007，6：888-902.3 Lee C H，Deng X T，Zhu H F.Design and sccurity anal- ysis of anonymous group identification protocolsC/Pro- ceedings of Pulic Key Cryptography，February 2002，Paris， France.Berlin Heidelberg：Spr

50、inger-Verlag，2002：188-198.4 Eliane J，Guillaume P.On the security of homage group authentication protocolC/Proceedings of Cayman Islands， British West Indies，Feb 19-22，2001，2339：106-116.5 Xu Z M，Tian H，Liu D S，et al.A ring-signature anony-10Paik J H，Kim B H，Lee D H.A3RP：anonymous andauthenticated ad

51、hoc routing protocolC/Proceedings of Information Security and Assurance Conference，2008.11 刘 方 斌 ，张 琨 ，李 海 ，等.无 可 信 中 心 的 门 限 追 踪 Ad Hoc网络匿名认证J.通信学报，2012，33（8）：208-213.12 石润华，仲红，黄刘生.公开可验证的门限秘密共享方案J.微电子学与计算机，2008，25（1）：29-33.13 殷凤梅，濮光宁.允许新成员加入的无可信中心秘密共享 方 案 分 析 J. 重 庆 科 技 学 院 学 报 ：自 然 科 学 版 ，2011，13（6