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

一种基于遗传算法的副本优化问题求解方法
<a rel='nofollow' onclick="();return false;"
href="#">


　　摘要：针对分布式存储系统中的副本优化问题，本文提出一种利用遗传算法进行求解的方法。首先对副本优化问题进行了数学描述和建模，其次介绍了如何设计遗传算法中的编码、适应度函数以及选择、交叉和变异方法，最后通过实例进行了验证。结果表明，该方法能有效求解副本优化问题。
　　关键词：分布式存储系统；遗传算法；副本分发
　　
　　1引言
　　遗传算法（Genetic 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处访问文件的时间满足用户给