遗传算法Python实战 003.数字排序

写在前面的话

写到这一篇，已经是第三章了，大家可能已经发现，遗传算法在效率上几乎是没有什么优势的……它更多的是利用了强大的算力去进行不断的试错，在以往不断追求速度的情况下，似乎并不是一个好的选择。

但是到了今天，算力不在是制约我们发展的关键因素，所以我们有能力调用更加强大算力来为我们服务，而遗传算法的一些优势也慢慢的体系出来：比如它不倚赖于初始条件，他的最终结果与最初的条件没有任何关系，这点是传统算法所做不到的。

还有诸如他的鲁棒性——它可以很容易的移植到任意求解中，而不用过多的修正。

所以，今天我们来看看，计算机算法里面最常见一种：排序算法。

在遗传算法里面，排序比前面两个例子要稍微复杂那么一点点……因为被选择的基因需要进行数值大小的约束，以保证它要比它左边的所有值都要大（排序嘛）

首先声明

本节提供的数据排序算法效率极差，纯粹是拼人品，作用仅用于说明遗传算法原理使用，切勿在实际工作中去用，否则出现的一切问题，概不负责。

遗传进化，本来就是各种巧合的大集合——地球生物圈再来一次，保证类人猿一定能够再次进化成和我们一模一样的智人么？

进入正题

排序是计算机算法里面的基本功，不过到今天为止，已经没有哪个人愿意手写一个排序功能，大部分语言里面都提供了各种千锤百炼的排序算法包，当然，如果你自信你手写的排序算法要比各种官方提供的排序算法效率更高的话，这种大神级人物不在我们的讨论范畴之内。

遗传算法最大的特点，就是在每一次进化中，去选择更优的基因组合，所以我们先要预定两个序列怎么排列会更优的判定方法：

比如用下面这种方式，依次迭代整个list，如果右边的值比坐标值大，则我们的适配性+1，比如：

[3,1,2,6,4]，计算之后就是：2比1大，加1,6比2大，加1，最后fitness = 3 最终排列要是[6,4,3,2,1]，也就是左边一定都比右边大，fiteness =1为最终进化目标。

def get_fitness(genes):
    fitness = 1
    for i in range(1, len(genes)):
        if genes[i] > genes[i - 1]:
            fitness +=1
    return fitness

然后定义承载的染色体类和进化函数：

class Chromosome:
    def __init__(self, genes, fitness):
        self.Genes = genes
        self.Fitness = fitness

注意，这里的进化函数的逻辑是从要排序的下标中，随机选择两个下标，如果后者的值大于前者，则进行交换，否则重新选择。

def mutate(parent, geneSet):
    childGenes = parent.Genes[:]
    while True:
        idx1, idx2 = random.sample(geneSet, 2)
        if childGenes[idx1] < childGenes[idx2]:
            continue
        childGenes[idx1],childGenes[idx2] = childGenes[idx2],childGenes[idx1]
        fitness = get_fitness(childGenes)
        break
    return Chromosome(childGenes, fitness)

然后就是运行函数了：

x = random.sample([i for i in range(100)],10)
genset = [i for i in range(10)]
random.seed()
startTime = datetime.datetime.now()
bestParent = Chromosome(x,get_fitness(x))
if bestParent.Fitness <= 1:
    return bestParent
num = 0
while True:
    num +=1
    child = mutate(bestParent,genset)
    if bestParent.Fitness < child.Fitness:
        continue
    print(bestParent.Genes," {}".format(child.Fitness),datetime.datetime.now()-startTime)
    if child.Fitness <=1:
        bestParent = child
        break
    bestParent = child

运行结果如下：

[64, 12, 40, 44, 39, 81, 14, 89, 98, 54]  6 0:00:00
[64, 14, 40, 44, 39, 81, 12, 89, 98, 54]  6 0:00:00
[64, 98, 40, 44, 39, 81, 12, 89, 14, 54]  4 0:00:00
[64, 98, 40, 44, 39, 14, 12, 89, 81, 54]  3 0:00:00
[64, 40, 98, 44, 39, 14, 12, 89, 81, 54]  3 0:00:00
……
[98, 89, 81, 64, 44, 39, 54, 40, 14, 12]  2 0:00:00.048869
[98, 89, 81, 64, 54, 39, 44, 40, 14, 12]  2 0:00:00.048869
[98, 89, 81, 64, 54, 40, 44, 39, 14, 12]  2 0:00:00.049866
[98, 89, 81, 64, 54, 40, 39, 44, 14, 12]  2 0:00:00.049866
[98, 89, 81, 64, 54, 40, 44, 39, 14, 12]  1 0:00:00.049866

进行了1万多次进化，才得到了最佳结果——10个元素的列表，就算是双重迭代，也最多100次，就完成计算了，所以才有我前面所说的，遗传算法在这里用于排序，是相当相当的不靠谱的……