遗传算法(Genetic Algorithm,GA)实现数据排序，python

深碍√TFBOYSˉ_ 2023-09-24 17:16 50阅读 0赞

## 遗传算法(Genetic Algorithm,GA)实现数据排序，python ##

遗传算法是一种比较广泛、通用的算法体系，为了说明遗传算法的原理和实现，现在用GA解决一个计算机科学最基本、最古老的问题：排序问题。

需要特别说明的是，遗传算法虽然可以用来解决排序问题，但与熟知的排序算法（快排、选择排序、冒泡等等经典排序算法）相比较，遗传算法解决排序问题效率低、且不稳定（耗时）。用遗传算法排序，只是开拓了一个解决问题的思路，并演示、说明其运作原理。遗传算法的特点是利用强大的算力，不断试错，直至找出接近最佳解的最优解。

import random
    import time
    
    
    def get_fitness(genes):
        fitness = 1
    
        for i in range(1, len(genes)):
            # 如果这里是 > ，则是逆序结果。
            if genes[i] < genes[i - 1]:
                fitness += 1
    
        return fitness
    
    
    def mutate(parent):
        child = parent[:]
        while True:
            # 从0到N中随机选择两个数作为数组下标
            idx1, idx2 = random.sample(list(range(len(child))), 2)
    
            if child[idx1] < child[idx2]:
                continue
            else:
                # 相当于交叉
                child[idx1], child[idx2] = child[idx2], child[idx1]
                break
    
        return child
    
    
    def sorted(data):
        print("原始数据", data)
        parent = data
        seq = 0
        start_time = (int(round(time.time() * 1000)))  # 毫秒级时间戳
    
        while True:
            # print('第', seq, '轮', child)
    
            child = mutate(parent)
            fitness = get_fitness(child)
            # 适应度1为进化目标
            if fitness <= 1:
                break
            else:
                # 进化到下一代
                parent = child
    
            seq = seq + 1
    
        end_time = (int(round(time.time() * 1000)))  # 毫秒级时间戳
        print('总计', seq, '轮')
        print('算法耗时', end_time - start_time, '毫秒')
        print('排序结果', child)
    
    
    if __name__ == '__main__':
        data = [1, 2, 3, 4, 5, 6, 7, 8]
    
        for i in range(10):
            print('-----')
            random.shuffle(data)
            sorted(data)

代码运行输出：

> \-----  
> 原始数据 \[1, 5, 3, 7, 8, 6, 2, 4\]  
> 总计 9187 轮  
> 算法耗时 47 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[8, 7, 3, 1, 6, 4, 5, 2\]  
> 总计 11847 轮  
> 算法耗时 63 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[8, 6, 7, 1, 2, 4, 3, 5\]  
> 总计 127271 轮  
> 算法耗时 627 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[1, 6, 8, 7, 5, 4, 3, 2\]  
> 总计 19282 轮  
> 算法耗时 95 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[1, 3, 8, 5, 7, 4, 2, 6\]  
> 总计 200925 轮  
> 算法耗时 1077 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[2, 6, 4, 7, 1, 3, 5, 8\]  
> 总计 18535 轮  
> 算法耗时 95 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[8, 4, 3, 7, 5, 1, 2, 6\]  
> 总计 22467 轮  
> 算法耗时 94 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[3, 8, 7, 5, 1, 6, 4, 2\]  
> 总计 71436 轮  
> 算法耗时 377 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[5, 8, 2, 1, 3, 7, 4, 6\]  
> 总计 82190 轮  
> 算法耗时 392 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]  
> \-----  
> 原始数据 \[2, 5, 4, 8, 3, 1, 6, 7\]  
> 总计 18916 轮  
> 算法耗时 110 毫秒  
> 排序结果 \[1, 2, 3, 4, 5, 6, 7, 8\]

把12345678这8个数字打乱顺序，排序，跑10轮。

遗传算法完成排序：

（1）在mutate函数里面对传递过来的亲代染色体进行“变异”。具体方法是随机选择数组长度范围内的两个下标，然后比较下标对应的两个值大小关系，如果第1个小于第2个，跳过；否则，交换这两个数值。

（2）在sorted函数里面，循环迭代的对亲代数组变异，因为进化的目标适应度是1，所以，当变异后的子代染色体适应度为1时候，退出循环，也即排序结束。若适应度不为1，那么将子代染色体放回亲代，继续变异，直到适应度为1。

[遗传算法(Genetic Algorithm，GA)的轮盘赌选择，python\_zhangphil的博客-CSDN博客程序跑了10次，每一次在rws()函数中产生一个随机概率数值r，然后在rws()函数内部比较r与累积概率的大小，确定被选中的概率是p\[?输出结果证实了我们的猜想，p\[1\]=0.49被选中的概率最高，在10次的随机筛选中，p\[1\]=0.49被选中了4次(4/10)。显然，p(s2)=0.49概率最大，被选中的概率最高。遗传算法(Genetic Algorithm，GA)的轮盘赌选择，python。一个简单的例子说明在遗传算法中使用的轮盘赌方法。![favicon32.ico][]https://blog.csdn.net/zhangphil/article/details/128906624][Genetic Algorithm_GA_python_zhangphil_-CSDN_10_rws_r_rws_r_p_p_1_0.49_10_p_1_0.49_4_4_10_p_s2_0.49_Genetic Algorithm_GA_python_favicon32.ico_https_blog.csdn.net_zhangphil_article_details_128906624]

[favicon32.ico]: https://g.csdnimg.cn/static/logo/favicon32.ico
[Genetic Algorithm_GA_python_zhangphil_-CSDN_10_rws_r_rws_r_p_p_1_0.49_10_p_1_0.49_4_4_10_p_s2_0.49_Genetic Algorithm_GA_python_favicon32.ico_https_blog.csdn.net_zhangphil_article_details_128906624]: https://blog.csdn.net/zhangphil/article/details/128906624