改进遗传算法在云计算中的应用

吉林大学 刘文博

本文采用了并行遗传算法作为基本算法进行任务调度。并行遗传算法分为主从式遗传算法、细粒度遗传算法和粗粒度遗传算法三种。在经过对三者的优缺点进行比较之后，本文采用粗粒度遗传算法作为基本的调度算法。但使粗粒度遗传算法本身有收敛速度慢的缺点，会导致任务完成时间略长，因此本文在这方面做了新的改进工作。通过提高初始种群质量和改进交叉方法两方面改善了算法本身收敛速度慢的问题，而且不影响算法本身的寻优。提高初始种群的质量，具体是通过将要生成的初始种群中的个体按照其适应度参数进行排序，选择个体适应度较高的个体组成初始种群，这个过程的算法复杂度极低，对整体算法在时间上的影响基本可以忽略，是可以被接受的。改进交叉方法，具体是指不再使用原始的随机交叉办法，而是在一定迭代次数内，采用判断汉明距离进行交叉的策略。两个个体之间的汉明距离越大，说明二者的相似度越低，尽量选择相似度低的个体进行交叉，可以在很大程度上避免无用子个体的产生，从而加快整体算法的收敛，并且能够提高最终解的质量。而这个交叉过程仅在一定的迭代次数之前使用，迭代次数视具体问题而定。

改进遗传算法在云计算中的应用