一种基于遗传算法的副本优化问题求解方法

《一种基于遗传算法的副本优化问题求解方法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种基于遗传算法的副本优化问题求解方法：针对分布式存储系统中的副本优化问题，本文提出一种利用遗传算法进行求解的方法。首先对副本优化问题进行了数学描述和建模，其次介绍了如何设计遗传算法中的编码、适应度函数以及选择、交叉和变异方法，最后通过实例进行了验证。结果表明，该方法能有效求解副本优化问题。　　关键词：分布式存储系统；遗传算法；副本分发　　　　1引言　　遗传算法（GeicAlgorithm，GA）是根据自然界的“物竞天择，适者生存”现象而提出的一种随机搜索方法，最早由美国Michigan大学的Holland教授于2

2、0世纪70年代提出。该算法将优化问题的求解看成是自然界中生物的进化过程，通过模拟生物进化过程中的遗传规律，引入选择、交叉和变异等方法，从而达到寻优的目的。　　近年来，遗传算法作为一种有效的工具，已经被广泛应用于最优化问题的求解中。副本优化问题是一个NP完全问题。对此，本文提出一种基于遗传算法的副本优化问题求解方法，并设计了遗传算法的编码、适应度函数以及选择、交叉和变异方法。　　2遗传算法　　在遗传算法中，首先对问题的可能解按照某种形式进行编码，并随机生成初始种群，然后根据预定的评价函数对每一个体计算适应值，从中选择

3、适应度高的个体进行复制，再通过遗传操作来产生新的种群。如此反复迭代进化，最后收敛到适应环境的染色体上。　　遗传算法维持由一群个体组成的种群P（t）（t为遗传的代数），每一个体均代表优化问题的一个潜在的解，它们被评价优劣并得到其适应值。其中，某些个体要经历称作遗传操作的随机变换，并由此产生新的个体。主要有两种变换方法：（1）杂交的方法是将两个父代个体的部分结构加以替换重组而生成新的个体；（2）变异的方法是将一个个体改变从而获得新的个体。新产生的后代C（t）继续被评价优劣，然后从父代种群P（t）和C（t）中选择比较优秀

4、的个体形成新的种群。这样，经过若干代以后，算法收敛到一个最优个体，该个体很有可能就是问题的最优或次优解。　　3基于遗传算法的副本分发模型求解方法　　3.1副本优化问题描述及建模　　在分布式存储系统中，一个合理优化的副本方案，应该能够以最小的副本数使得各个节点的单个请求响应时间满足给定的约束条件，并且在此基础上尽可能地使得系统总的请求响应时间最小化。由此，可以描述为如下集合覆盖问题（SetCoveringProblem,SCP）：　　其中，bi=0或1，aji=0或1，n为节点的个数，1≤i≤n。约定：当节点Si包含

5、文件的副本时，bi=1，否则bi=0；当节点Sj从Si处访问文件的时间满足用户给定要求时，aji=1，否则aji=0。　　SCP是一个经典的组合优化问题，已经被证明是一个NP完全问题。对此，本文将采用遗传算法进行求解。　　3.2副本分发模型求解　　3.2.1编码　　在副本优化问题中，将需要创建副本的节点标记为1，其它节点标记为0。这样，问题的解就可以表示为一组由0、1组成的二进制串。记rs为采用二进制进行编码后的个体，则其可表示为b1b2…bn。其中，n为个体基因总数，也即总的节点个数。　　3.2.2适应度函数　　

6、对于任意个体rs，只要某个节点的单个请求响应时间不能够满足用户给定的要求，则该个体应予以淘汰，相应的适应值应该尽可能小。反之，当所有节点的单个请求响应时间均能满足用户给定的要求时，rs所需创建的副本数越少，则表明其优良程度越高，相应的适应值应该越大。此外，当两个个体所需创建的副本数相同时，总的请求响应时间越少的个体，其适应值应该越大。于是，本文设计的适应度函数定义为：　　其中，ε为一充分小的正数，T为在没有创建任何副本情况下系统总的请求响应时间，T'为系统实际总的请求响应时间，RTi为节点i的访问时间，Tthres

7、hold为给定的时间要求。　　3.2.3选择　　首先根据适应度函数依次计算当前种群中个体的适应值，适应值大的个体将直接保留到下一代种群中。然后根据个体的适应值计算出其相对适应值，并作为该个体的选择概率。不妨设种群规模为m，则个体rsi被选中遗传到下一代种群的概率为：　　最后，采用轮盘赌选择（roulette（即变异率）随机地改变染色体串上的一位或多位基因，其作用是增加种群的多样性，扩大搜索空间。具体过程如下：　　1）首先生成一随机数k，k作为随机变量服从于[0，1]上的均匀分布；　　2）如果k≤pm，则对该个体进行

8、变异；否则，不进行变异。　　变异过程如下：　　1）用随机函数产生一个变异位（例子中变异位为3）；　　2）将变异个体的变异位取反，其它基因保持不变。　　例如：0000011100→0010011100　　3.2.6终止条件　　在迭代过程中，如果解空间连续3次保持不变，称此为收敛。当满足上述条件时，如果迭代次数少于某个预设下限，则为收敛过早，此时应重新生成新的初