基于內(nèi)存映射文件的進(jìn)化算法數(shù)據(jù)存儲(chǔ)引擎

姜三義，代真真，李 陽(yáng)，周愛(ài)民

華東師范大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)系，上海 200241

1 引言

基于統(tǒng)計(jì)和機(jī)器學(xué)習(xí)的進(jìn)化算法目前日益引起人們的重視。進(jìn)化算法[1]是一種通過(guò)多次迭代搜索來(lái)獲取全局最優(yōu)解的隨機(jī)優(yōu)化算法[2]。作為一類啟發(fā)式搜索算法，是否具備良好的搜索記憶功能，即通過(guò)一定方式存儲(chǔ)并利用已搜索的解空間，是評(píng)價(jià)算法好壞的關(guān)鍵之一。從本質(zhì)上來(lái)說(shuō)，進(jìn)化算法維護(hù)的種群和其他信息實(shí)際上可以看作是一個(gè)動(dòng)態(tài)變化的數(shù)據(jù)集（數(shù)據(jù)庫(kù)）。當(dāng)前及歷史數(shù)據(jù)集隱含了進(jìn)化算法搜索的規(guī)律，因此可以通過(guò)模式識(shí)別和機(jī)器學(xué)習(xí)的方法來(lái)挖掘隱含在這些數(shù)據(jù)集中的規(guī)律并指導(dǎo)進(jìn)化算法的搜索。有效存儲(chǔ)和組織當(dāng)前和歷史群體信息，是實(shí)現(xiàn)這類算法的前提。

由于進(jìn)化算法的搜索空間往往比較大，存儲(chǔ)記憶時(shí)需要平衡算法效率和磁盤(pán)空間[3]。隨著計(jì)算機(jī)磁盤(pán)容量的迅速增長(zhǎng)和單位容量成本的降低，可以將更多的算法數(shù)據(jù)存儲(chǔ)到磁盤(pán)中。但是在性能上，現(xiàn)有的通用數(shù)據(jù)庫(kù)技術(shù)或傳統(tǒng)文件存儲(chǔ)方式并不能很好地滿足這種需求。使用通用數(shù)據(jù)庫(kù)時(shí)，需要額外搭建專有的數(shù)據(jù)服務(wù)系統(tǒng)，進(jìn)行數(shù)據(jù)庫(kù)維護(hù)，并且由于數(shù)據(jù)庫(kù)索引等機(jī)制的存在，數(shù)據(jù)庫(kù)對(duì)于大量實(shí)時(shí)算法數(shù)據(jù)的存儲(chǔ)效率并不理想。算法設(shè)計(jì)人員因而往往將數(shù)據(jù)以文件的形式直接存儲(chǔ)到磁盤(pán)上。由于磁盤(pán)I/O的效率問(wèn)題，采用傳統(tǒng)文件方式保存數(shù)據(jù)會(huì)大量增加算法的執(zhí)行時(shí)間?，F(xiàn)代操作系統(tǒng)支持基于虛擬內(nèi)存技術(shù)的內(nèi)存映射文件機(jī)制。通過(guò)使用內(nèi)存映射文件，存儲(chǔ)速度相比于傳統(tǒng)文件I/O方式可以得到極大提升[4]。

內(nèi)存映射是將磁盤(pán)上的文件或部分文件內(nèi)容映射到進(jìn)程地址空間內(nèi)部區(qū)域的一種機(jī)制。通過(guò)創(chuàng)建內(nèi)存映射文件，應(yīng)用程序可以直接讀寫(xiě)內(nèi)存來(lái)訪問(wèn)磁盤(pán)文件數(shù)據(jù)，相比于使用文件的讀寫(xiě)函數(shù)具有更快的I/O速度。在Windows和Linux操作系統(tǒng)中都支持內(nèi)存映射文件機(jī)制，通過(guò)使用系統(tǒng)提供的編程接口，應(yīng)用程序可以利用內(nèi)存映射機(jī)制提高I/O效率。

內(nèi)存映射文件可以被直接應(yīng)用于程序中，對(duì)于一些簡(jiǎn)單的程序是完全可行的。但是在進(jìn)行復(fù)雜數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)組織，并且需要確保大量數(shù)據(jù)和文件的可靠和安全時(shí)，需要進(jìn)行復(fù)雜的代碼設(shè)計(jì)和編碼調(diào)試工作，以解決合理分配和動(dòng)態(tài)擴(kuò)展數(shù)據(jù)文件，存儲(chǔ)不同數(shù)據(jù)結(jié)構(gòu)等問(wèn)題，這對(duì)程序編碼人員提出了很高的要求，在很大程度上限制了內(nèi)存映射文件技術(shù)被廣泛利用。

本文介紹了使用C++編程語(yǔ)言實(shí)現(xiàn)的嵌入式數(shù)據(jù)存儲(chǔ)引擎（EADB），EADB利用內(nèi)存映射文件實(shí)現(xiàn)了數(shù)據(jù)存儲(chǔ)，支持Linux和Windows這兩個(gè)不同平臺(tái)，提供統(tǒng)一的讀寫(xiě)接口，支持復(fù)雜數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)組織。通過(guò)使用EADB，應(yīng)用程序在獲得I/O性能提升的同時(shí)，可以減少編碼工作量。通過(guò)在進(jìn)化算法中使用EADB，提高了進(jìn)化算法執(zhí)行過(guò)程中的數(shù)據(jù)存儲(chǔ)效率。

2 算法記錄

本文稱進(jìn)化算法迭代過(guò)程中產(chǎn)生的解為“算法記錄”。不同進(jìn)化算法的執(zhí)行框架基本相同，首先進(jìn)行種群隨機(jī)初始化和個(gè)體適應(yīng)度計(jì)算，然后進(jìn)行有限次數(shù)的迭代使得群體在搜索空間中不斷進(jìn)化。每一次迭代包含的步驟包括：重組、變異、適應(yīng)值評(píng)估和選擇等。每一次迭代產(chǎn)生的解包含染色體、適應(yīng)值或其他信息[5]。

進(jìn)化算法的種群個(gè)體（即染色體）可以表示為確定長(zhǎng)度的二進(jìn)制位串或格雷碼，也可以使用符號(hào)集、實(shí)數(shù)或?qū)崝?shù)數(shù)組來(lái)表示。進(jìn)化算法作為一類啟發(fā)式搜索算法，也被成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域[6-7]。每個(gè)種群個(gè)體的適應(yīng)值，在單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問(wèn)題中的表示方式是不一樣的。在單目標(biāo)優(yōu)化問(wèn)題中，適應(yīng)值是一維的變量；而在多目標(biāo)優(yōu)化問(wèn)題中，適應(yīng)值則一般是多維的向量。由此分析，算法記錄中的內(nèi)容在形式上包括一維變量和多維向量，所以可以使用數(shù)組來(lái)統(tǒng)一存儲(chǔ)記錄內(nèi)容[8-9]。

同一個(gè)進(jìn)化算法在每一次迭代中需要保存的數(shù)據(jù)記錄的數(shù)量有可能不同，例如在基于分解技術(shù)的多目標(biāo)進(jìn)化算法（Decomposition based Multi-Objective Evolutionary Algorithm，MOEA/D）求解背包問(wèn)題的算法中，每一代最優(yōu)群體的個(gè)體數(shù)量可能是不同的[10]。但是，在同一個(gè)進(jìn)化算法的一次執(zhí)行過(guò)程中，算法記錄的內(nèi)容在結(jié)構(gòu)上是一致的。

3 內(nèi)存映射文件

內(nèi)存映射文件的實(shí)現(xiàn)借助于操作系統(tǒng)底層的虛擬內(nèi)存機(jī)制[11]。使用虛擬內(nèi)存的目的是為了彌補(bǔ)物理內(nèi)存的容量不足問(wèn)題。在虛擬內(nèi)存系統(tǒng)中，每個(gè)進(jìn)程擁有獨(dú)立的連續(xù)完整的地址空間。基于程序的局部性原理，操作系統(tǒng)僅將運(yùn)行進(jìn)程所必需的一部分指令裝入內(nèi)存，在進(jìn)程執(zhí)行時(shí)通過(guò)請(qǐng)求調(diào)入和置換功能進(jìn)行內(nèi)外存數(shù)據(jù)交換，使進(jìn)程能夠持續(xù)運(yùn)行。

虛擬內(nèi)存技術(shù)不僅僅解決了物理內(nèi)存容量不足的問(wèn)題，它的出現(xiàn)使得操作系統(tǒng)發(fā)生了巨大的變化。當(dāng)今大部分操作系統(tǒng)（包括Windows和Linux）在I/O系統(tǒng)中均采用了文件緩存機(jī)制（在Windows中稱為系統(tǒng)緩存，在Linux中稱為頁(yè)面緩存），在內(nèi)核虛擬地址空間中分配一個(gè)分段用于文件數(shù)據(jù)緩存。操作系統(tǒng)進(jìn)一步將該分段劃分為塊，每一塊包含若干分頁(yè)（在32位Windows系統(tǒng)中，頁(yè)面大小是4 KB，分塊大小是256 KB；在32位Linux系統(tǒng)中，頁(yè)面大小是4 KB，分塊大小也是4 KB）。在訪問(wèn)文件時(shí)，操作系統(tǒng)始終按塊為單位（即使只訪問(wèn)一個(gè)字節(jié)數(shù)據(jù)）將文件數(shù)據(jù)拷貝到文件緩存中。當(dāng)文件緩存中的頁(yè)面被調(diào)度到物理內(nèi)存中后，內(nèi)存與磁盤(pán)文件之間建立了字節(jié)上一對(duì)一的關(guān)系，在頁(yè)內(nèi)的數(shù)據(jù)訪問(wèn)都是在物理內(nèi)存中完成的，避免了頻繁的文件I/O，極大提高了讀寫(xiě)能力。同時(shí)，由于虛擬內(nèi)存的“按需調(diào)度”原則，只將一部分?jǐn)?shù)據(jù)而非整個(gè)文件調(diào)入內(nèi)存，因而可以節(jié)約大量物理內(nèi)存[12-13]。

內(nèi)存映射文件在此基礎(chǔ)上進(jìn)一步加快了文件訪問(wèn)速度。使用傳統(tǒng)文件I/O方式時(shí)，仍然需要通過(guò)系統(tǒng)調(diào)用（即文件讀寫(xiě)函數(shù)）從內(nèi)核空間將數(shù)據(jù)復(fù)制到用戶空間，即讀操作使用的內(nèi)存緩沖區(qū)。而建立內(nèi)存映射文件后，操作系統(tǒng)將進(jìn)程的虛擬頁(yè)面直接映射到系統(tǒng)文件緩存上，使得進(jìn)程可以直接訪問(wèn)這一部分內(nèi)存。通過(guò)建立內(nèi)存映射文件，一方面避免了使用系統(tǒng)調(diào)用，訪問(wèn)速度得到數(shù)量級(jí)的提升；另一方面，在用戶空間中無(wú)需對(duì)文件內(nèi)容進(jìn)行緩沖，不僅減少了物理內(nèi)存復(fù)制工作，還節(jié)省了一半的物理內(nèi)存空間[14]。

內(nèi)存映射文件帶來(lái)的另一個(gè)優(yōu)點(diǎn)是在編寫(xiě)數(shù)據(jù)存儲(chǔ)程序的時(shí)候，在內(nèi)存及外存中只需要定義一套數(shù)據(jù)結(jié)構(gòu)，可以直接將內(nèi)存映射區(qū)域中的數(shù)據(jù)看作程序中定義的數(shù)據(jù)結(jié)構(gòu)類型對(duì)應(yīng)的對(duì)象[15]。

內(nèi)存映射文件允許將文件的一部分映射到內(nèi)存中，從而可以處理非常大的文件。Windows支持的文件大小最大達(dá)到16 EB。Linux支持的最大文件大小在不同的文件系統(tǒng)上略有差別，大部分系統(tǒng)都實(shí)現(xiàn)了LFS（大文件系統(tǒng)）技術(shù)，文件大小可以達(dá)到或超過(guò)2 TB。

4 存儲(chǔ)引擎的實(shí)現(xiàn)與使用

4.1 存儲(chǔ)引擎的數(shù)據(jù)表示方法

本研究定義了一種數(shù)據(jù)描述方法：ASON（Algorithm Structured Object Notation），即算法結(jié)構(gòu)化對(duì)象表示法，來(lái)描述算法記錄，可以滿足進(jìn)化算法記錄的數(shù)據(jù)存儲(chǔ)要求。每一個(gè)ASON所描述的算法記錄可以包含若干個(gè)數(shù)據(jù)字段，每一個(gè)數(shù)據(jù)字段都是一個(gè)鍵值對(duì)（key-value pair），每個(gè)鍵名是一串字符串，鍵值是一個(gè)數(shù)值數(shù)組。例如，ASON可以表示如下使用鍵值對(duì)描述的算法記錄：

記錄中的“popsiz”、“gen”、“fitness”、“chromo”分別表示種群大小、當(dāng)前迭代值、個(gè)體適應(yīng)度和染色體。使用ASON可以實(shí)現(xiàn)對(duì)象內(nèi)數(shù)據(jù)字段的靈活組合，不僅可以包含進(jìn)化算法的適應(yīng)度及染色體，還可以包含其他的數(shù)據(jù)字段。本文為簡(jiǎn)單起見(jiàn)，只考慮染色體和適應(yīng)度值信息。

使用C++宏“ASON”在程序中按照C++數(shù)據(jù)流的序列化方式構(gòu)建算法記錄，采用STL的std：：vector容器作為數(shù)組類型。宏ASON的使用方法參見(jiàn)如下代碼：

宏“ASON”返回的是抽象數(shù)據(jù)結(jié)構(gòu)類型ASONObj的對(duì)象實(shí)例。在內(nèi)存中，一個(gè)ASONObj對(duì)象表示為二進(jìn)制字節(jié)序列。首先是4個(gè)字節(jié)表示對(duì)象長(zhǎng)度，緊接著是若干個(gè)數(shù)據(jù)字段，最后是結(jié)束標(biāo)志符。每個(gè)數(shù)據(jù)字段的第一個(gè)1個(gè)字節(jié)表示字段值類型；然后是一條字符串，表示字段名稱，由字符’

雅安市| 万安县| 陆川县| 榆树市| 汉源县| 日喀则市| 万州区| 会昌县| 汶川县| 文水县| 临西县| 常山县| 怀仁县| 德阳市| 株洲市| 原平市| 黄龙县| 淮北市| 泗洪县| 宁晋县| 万荣县| 如皋市| 平山县| 博兴县| 陕西省| 沂水县| 天门市| 澜沧| 孝感市| 增城市| 广西| 乐都县| 开江县| 丰台区| 双柏县| 翁牛特旗| 健康| 海林市| 淳化县| 康保县| 静海县|