基于多目标遗传算法的云数据放置策略

时间:2019-09-27

　　本篇文章目录导航：

　　【题目】探究云存储系统的云数据放置优化方法??
　　【第一章】面向云存储系统的云数据放置方法研究绪论
　　【第二章】云存储及其相关技术
　　【第三章】云数据多目标存储模型
　　【第四章】基于多目标遗传算法的云数据放置策略
　　【第五章】云数据放置实验与分析
　　【第六章】云数据放置优化方法的结论与参考文献

第四章 基于多目标遗传算法的云数据放置策略

　　本章将通过采用多目标遗传算法来解决上一章提出的云数据的放置问题，即同时最小化检索时间和最大化安全水平。对于遗传算法，本章进行了详细的研究，包括算法的发展及原理。同时对于该特定的多目标优化问题，本章将遗传算法的每一个步骤进行了适当的设计，从而保证该云数据放置策略的效率。

　　4.1遗传算法简介

　　早在20世纪40年代，就有学者开始模拟生物活动研究计算机技术。

　　20世纪50年代，进化计算第一次被作为一种优化策略被使用，当时的计算机科学家将达尔文提出的生物进化论思想应用于候选解所构成的种群。他们建立理论，认为有可能应用进化算子，如交叉（模拟生物界的繁殖行为）和变异（模拟生物界的基因突变现象）。在这些算子和自然选择的共同作用下，通过进化思想在进行多代进化后，进化出新的解。在20世纪60年代，“进化策略”最初由Rechenberg提出，他的想法后来被Schwefel发展。其他计算机科学家当时在类似的研究领域独立地工作，如Fogel L J、Owens以及Walsh,他们将进化策略引入了进化编程的领域，应用变异来创建新解。

　　Holland教授在20世纪70年代首先提出并发展了“遗传算法”的概念，并于1975年在其开创性着作《自然系统和人工系统的自适应》（Adaptation in Natural and Artificial Systems）中正式定义了遗传算法[63].

　　Holland在书中展示了达尔文的进化论可以如何被抽象并用计算机建模用于优化策略。书中解释了染色体如何建模为1和0的序列，通过实现自然选择中的选择、交叉以及变异操作，使得拥有这些染色体的种群实现进化。

　　遗传算法是基于达尔文进化论的启发以模拟生物界物种进化而形成的启发式算法，其目的是求取全局最优解，具有随机性的特征。其不依赖梯度信息的特点被广泛应用于无约束优化问题，一旦初始参数被确定后，遗传算法将以与问题本身无关的方式求取解。在不断的优化过程中使得其同样可以处理约束优化问题。遗传算法具有算法复杂度低、鲁棒性强、易扩展等特性，使得其能够广泛的运用在机器学习、函数优化、自适应控制、生物科学、图像处理等各种领域。

　　近些年来，国内外对于遗传算法的研究仍在继续。其中包括对于算法的改进以及与其他不同算法的结合。遗传算法的改进主要在于编码模式的设计，适应度函数的定义，选择算子、交叉重组算子、变异算子的设计，优化收敛速度以及遗传算法的并行运算。另外一些研究将遗传算法与其他算法进行融合，增强算法的全局搜索能力。

　　4.2遗传算法原理

　　4.2.1 算法原理遗传

　　算法的基本思想是以自然选择和遗传理论为基础模仿一个种群的繁殖进化行为，由父代的染色体通过交叉，变异得到后代的过程。在过程中根据达尔文的适者生存理论淘汰掉比较差的后代（不符合线性收敛或者在可行域之外的个体），存活下来的个体不仅继承了父代的优点，并且更加适应环境、更加的优秀。子代中优秀的个体再不断的进行繁殖进化。每一次迭代都能够得到比前一代更好的个体,最终能够获得最优解[64].

　　遗传算法的核心操作是选择、交叉和变异这三个操作。其过程是通过编码将解转换为可以进行交叉变异的染色体结构，给定满足约束条件的初始解种群进行繁殖操作，并遵循适者生存、优胜劣汰的自然选择法则剔除相对较差的后代，保存比父代更好的近似解。种群在每一代的繁殖中通过相同的选择、交叉以及变异操作，而仅仅通过个体的适应度进行筛选直到产生满足条件的最优解时终止算法。

　　4.2.2 遗传算法的全局最优性实现

　　优化算法时，必须要考虑一个障碍，即该算法能否很好地逃离搜索空间的局部最优位置从而搜索到最优解。如图4.1所示我们可以看到该波峰图横坐标为解空间、纵坐标为解的适应度值，该图有A、B、C三个峰值。其中A和C为局部最优解，B为全局最优解。通常由于优化算法具有收敛性，且无法观测到整个适应度景观。相反，当它找到A和C这2个解时，它认为这些解可能处于搜索空间的最佳位置。正是这些原因，优化算法通常在找到A和C后就停止搜索，从而停留在了局部最优解上[65].包括很多启发式算法如粒子群算法、模拟退火法等都存在这一问题。

　　在避免局部最优和取得接近最有解这一方面，遗传算法具有很强的效率。能够保证这一做法的是遗传算法所采取的种群包含了解空间各个地方的初始可行解，这些解位于不同的收敛区域，从而能够保证能够找到各个区域的局部最优解，即包含全局最优解。通常经过几代后，种群就开始趋向于最优解，这是由于相对较差的解会在选择的过程中被移除，越接近最优解的次优解会被保留。

　　而遗传算法中的变异操作同样起到了避免陷入局部最优解的作用。变异允许一个解从当前位置跳到另一个搜索空间。这个过程往往会导致在搜索空间的较优收敛区域中发现更好的可行解。

　　遗传算法流程4.3.1 算法参数遗传算法中具有多种参数，其具体参数及描述如表4.1所示：

　　4.3.2 算法流程

　　整个遗传算法流程中先后需要确定遗传算法的编码方案、适应度函数选取、交叉策略、变异策略、选择策略以及算法终止准则。并且还要考虑算法能够支持并行运算，以确保算法的运行效率。其具体流程如图4.2所示：

　　4.3.3 算法终止条件

　　遗传算法可以通过迭代不断的得到新的候选解，前提是有充足的时间。根据问题的性质，遗传算法的运行时间可以从几秒到几分钟甚至是几天。我们将遗传算法完成搜索的条件称为终止条件。一般的遗传算法终止条件包括以下几点：

　　（1）计算出一个满足问题要求的解。

　　（2）该算法已经达到了一定的收敛性。

　　（3）到达指定的迭代次数。

　　（4）超过了实际的分配时间。

　　实际编程中算法可能包含很多终止条件。例如，如果已经设置最大的搜索时间或者指定的迭代次数，算法仍然可能提前找到最优解并终止。

　　4.4 基于多目标遗传算法的云数据放置策略

　　4.4.1 染色体的编码

　　由于本文设计的系统数据是被切分为N个长短不一的数据块分别存放在不同的数据节点

　　4.4.2 适应度函数

　　适应度函数给定了最优解的搜索方向，并且直接关系到最终解的质量和搜索效率。对于单目标优化问题，一般直接采用其目标函数作为适应度函数。但是对于多目标最优化问题，要进行单目标化变换，同编码一样，适应度函数的确定也需要充分了解并准确把握实际问题的构造和性质。

　　由于遗传算法中并不是完全否定所有的非可行解，而是在后代中保留少数的候选非可行解。这是因为在非可行解中也有可能包含靠近最优解的元素。因此，采用惩罚函数[67]

　　可以解决约束优化问题中产生的非可行解的问题，它通过对非可行解施加惩罚，从而降低其在下一代的生存率。

　　对某个个体所对应的数据放置方案效果的评价，首先是要看其是否满足优化模型中的约束条件，其次是计算其目标函数的值是否优秀。根据基于数据安全约束最小化检索时间的特征要求所确定的编码方法，隐含了存放在各数据节点中数据的尺寸之和等于原始数据的尺寸，并且各数据节点中所存储的数据块的尺寸一定是小于该数据节点的容量的信息。另外，存放数据块的数据节点之间一定满足式（3.3）中安全水平的要求，此处设定一个安全水平阈值j.

　　在设计数据的放置策略时需要同时考虑这几个约束条件，若不满足则判定为该方案不可行解，最后计算其适应度值。首先根据式（3.7）（3.8），由于两个目标函数分别求最小值和最大值，我们将其目标函数改进如式（4.1）：

　　4.4.3 交叉

　　在生成初始种群后，首先选择交叉操作来进化种群。在这个环节，种群中的个体相互进行交叉，交换染色体中的DNA片段，生成新的个体。

　　在交叉过程中，需要考虑种群中是否每个个体都参与交叉，这时需要定义一个交叉率p1,通过比较交叉率和每一个个体的随机数，我们能够决定该个体是否需要参与交叉，还是直接进入下一代。

　　交叉的基本方法有单点交叉、复点交叉、均匀交叉等，由于这些交叉方法生成的子染色体往往是非可行解。因此，本文在参与交叉的个体集合中随机选取两个个体，对其采用部分一致交叉法[69]

　　（Partial-Mapped Crossover,PMX），该方法交叉过程如图4.4所示。

　　第一步，从种群中随机选择两个个体，在这两个个体的染色体中选择相同地方的等长DNA片段；第二步，交换这两个DNA片段的位置；第三步，进行冲突检测，根据交换的两组染色体建立相应的映射关系，可以看出子代1中的基因10、8、5各出现两次。这时，通过映射关系转变这些重复的基因，直到没有基因冲突为止。

　　本文对于遗传算法交叉操作过程具体如下：

　　4.4.4 变异

　　在交叉操作完成后，种群将继续采取变异操作进化种群。在这一过程中，处于染色体上的基因片段会出现突变，变异后形成的个体将可能拥有更好的性能。

　　在变异过程中，需要考虑选择哪些个体进行变异。首先，我们需要定义一个变异率p2,一般地，p2在0到1的范围内取一个较小的值。然后对父代的每一个个体产生一个随机数，如果个体的随机数小于p2,我们将对该个体进行变异操作。

　　变异的方法需要根据具体的编码方式来确定。例如若采用二进制的编码方式，可以选择染色体中任意位置的基因进行取反。若采用数值和文字的编码，则可以选择染色体中任意一段基因与该染色体其他位置的已经进行调换。由于本文采取了数字优先级的编码方式，因此采用两个基因位置交换（Gene Swapping,GS）的变异方法，该方法操作如图 4.5 所示。

　　首先，选择需要进行变异操作的两个位置以及基因长度，这两个基因片段长度可以相同，也可以不同，然后，进行两个基因片段位置的调换，完成变异操作。

　　本文对于遗传算法操作的具体过程如下：

　　4.4.5 选择

　　在交叉、变异操作完成后，将从初始种群D和交叉产生的种群 D?以及变异产生的种群D?所形成的新种群中选取P个个体组成初始种群的子代，并继续进行遗传操作。

　　选择操作的目的是让适应度较高的个体具有更高的成活概率以进入下一代种群。常用的选择策略包括轮盘赌选择法、期望值选择法、排序选择法和精英保存法等。轮盘赌选择法[70]

　　又称为蒙特卡罗模型，其原理是根据每个染色体适应度的比例来确定该个体被选择的概率。

　　期望值选择法是通过种群中每个个体在下一代中生存的期望值进行选择。如果某个个体进行了交叉或变异操作，则它的期望值将减去0.5.排序选择法是将种群中每个个体根据其适应度排序，然后选择前P个个体作为下一代种群。精英保存法[71]

　　是将种群中适应度最高的个体保存到下一代。

　　本文所采用的是精英保存法和轮盘赌选择法结合的选择方式。首先，将种群中的个体进行适应度排序，排在第一位的个体性能最优，将其复制直接进入到下一代。同时采用轮盘赌

　　4.5本章小结

　　本章为了解决多目标云数据存储模型的优化问题，提出了遗传算法，用于优化云存储系统中的检索效率和云数据的安全性能。遗传算法考虑了分布式存储模型的特点，主要考虑了存储节点的网络拓扑结构，通过云数据放置的节点集解结构确定了遗传算法的编码方式、交叉算子以及变异算子。该算法根据节点内存、链路带宽、传输路径这些要素，建立了合适的适应度函数，用以求取最优解，并且采取了惩罚函数法用于保护非可行解的生存，可以避免算法过早的陷入局部最优解，以达到全局收敛的目标。本章提出的遗传算法在适应度函数上采用了加权的方法将多目标优化根据实际情况转化为单目标优化，虽然在加权系数上可以采取变化，但不够灵活。加权法主观性过强，人为影响较大，客观性不足，从而导致缺乏无法反映某些评价指标所具有的突出影响。所以该算法还需要更深入的研究与分析，以便能真正的运用在云存储系统中，促进云计算的发展。

TAG标签：

上一篇：云数据多目标存储模型
下一篇：云数据放置实验与分析