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

一种基于遗传算法的副本优化问题求解方法.doc一种基于遗传算法的副本优化问题求解方法
:针对分布式存储系统中的副本优化问题,本文提出一种利用遗传算法进行求解的方法。首先对副本优化问题进行了数学描述和建模,其次介绍了如何设计遗传算法中的编码、适应度函数以及选择、交叉和变异方法,最后通过实例进行了验证。结果表明,该方法能有效求解副本优化问题。
关键词:分布式存储系统;遗传算法;副本分发

1引言
遗传算法(Geic Algorithm,GA)是根据自然界的“物竞天择,适者生存”现象而提出的一种随机搜索方法,最早由美国Michigan大学的Holland教授于20世纪70年代提出。该算法将优化问题的求解看成是自然界中生物的进化过程,通过模拟生物进化过程中的遗传规律,引入选择、交叉和变异等方法,从而达到寻优的目的。
近年来,遗传算法作为一种有效的工具,已经被广泛应用于最优化问题的求解中。副本优化问题是一个NP完全问题。对此,本文提出一种基于遗传算法的副本优化问题求解方法,并设计了遗传算法的编码、适应度函数以及选择、交叉和变异方法。
2遗传算法
在遗传算法中,首先对问题的可能解按照某种形式进行编码,并随机生成初始种群,然后根据预定的评价函数对每一个体计算适应值,从中选择适应度高的个体进行复制,再通过遗传操作来产生新的种群。如此反复迭代进化,最后收敛到适应环境的染色体上。
遗传算法维持由一群个体组成的种***(t)(t为遗传的代数),每一个体均代表优化问题的一个潜在的解,它们被评价优劣并得到其适应值。其中,某些个体要经历称作遗传操作的随机变换,并由此产生新的个体。主要有两种变换方法:(1)杂交的方法是将两个父代个体的部分结构加以替换重组而生成新的个体;(2)变异的方法是将一个个体改变从而获得新的个体。新产生的后代C(t) 继续被评价优劣,然后从父代种***(t) 和C(t) 中选择比较优秀的个体形成新的种群。这样,经过若干代以后,算法收敛到一个最优个体,该个体很有可能就是问题的最优或次优解。
3基于遗传算法的副本分发模型求解方法

在分布式存储系统中,一个合理优化的副本方案,应该能够以最小的副本数使得各个节点的单个请求响应时间满足给定的约束条件,并且在此基础上尽可能地使得系统总的请求响应时间最小化。由此,可以描述为如下集合覆盖问题(Set Covering Problem, SCP):
其中,bi=0或1,aji=0或1,n为节点的个数,1≤i≤n 。约定:当节点Si包含文件的副本时,bi=1,否则bi=0;当节点Sj从Si处访问文件的时间满足用户给定要求时,aji=1,否则aji=0。
SCP是一个经典的组合优化问题,已经被证明是一个NP完全问题。对此,本文将采用遗传算法进行求解。

编码
在副本优化问题中,将需要创建副本的节点标记为1,其它节点标记为0。这样,问题的解就可以表示为一组由0、1组成的二进制串。记rs为采用二进制进行编码后的个体,则其可表示为b1b2
…bn。其中,n为个体基因总数,也即总的节点个数。
适应度函数
对于任意个体rs,只要某个节点的单个请求响应时间不能够满足用户给定的要求,则该个体应予以淘汰,相应的适应值应该尽可能小。反之,当所有节