Java教程

【备战美赛】遗传算法

本文主要是介绍【备战美赛】遗传算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

和模拟退火算法类似,遗传算法的本质也是通过一定地策略去寻找最优解。模拟退火运用了动力学原理,遗传算法则是运用了生物学自然选择的原理,思路巧妙。遗传算法是一种随机全局搜索优化,通过模拟自然选择和遗传中的复制、交叉、变异来实现“优胜劣汰”,最终找到最优解。

遗传算法步骤

1 染色体编码

对于每一个状态,要进行相应的编码来完成对数据的处理。这一点和状态压缩的处理方法有相似之处。一个状态对应一个编码,反之,一个编码也能解码出一个唯一的状态。好的编码可以使得后续模拟遗传中的复制、交叉、变异时更加方便。一般采用的编码方法有二进制编码、格雷码等。

2 生成初始群体

要初始化的变量包括

T 遗传代数(终止条件)

M 初始种群个体数量

Pc与Pm 代表交叉和变异的概率(生物知识告诉我们变异的概率一般都不大)这里Pc一般取0.4~0.99,Pm一般取小于0.1

3 个体适应度评价

如何进行“优胜劣汰”这个过程呢?也就是说怎样去量化一个个体的适应度呢?这里我们需要根据实际情况来自定义一个个体适应度评价的标准。例如NP旅行商问题里,某一个方案的路程之和便是该方案的适应度,通过比较多种方案的路程的大小筛选出较小的继续“繁衍”,淘汰路程较大的状态。

4 遗传算子

也就是模拟选择、交叉、变异的过程,因为生物中的遗传变异是随机的,所以模拟的时候也是随机化的。我们会根据设置的概率参数,随机选择交叉的个体和变异的个体,从而生成一个新的问题的解。之后重复“优胜劣汰”的过程,淘汰不好的解。每进行一次后,遗传代数+1。

5 终止判断条件

当模拟的遗传代数达到预设的最大遗传代数T时,我们认为已经获得了最优解,便终止进程,获取该最优解。由于遗传算法仍旧没有对全局进行遍历,所得到的解仍可能是一个局部最优解,但是相比模拟退火和爬山算法,获得全局最优解的概率已经大大提高。

 

(NP)旅行商问题

简而言之,旅行商问题要求找到一条最短的恰好经过了n个城市的路径(每个城市只能经过一次且城市两两相连)。旅行商问题是经典的NP完全问题,目前除了暴力地遍历(时间复杂度为O(n!))还没有一个完美的解法,但是我们可以通过遗传算法来获取一个近似解(实际上很可能是最优解)。

参照遗传算法的定义,这里的编码可设置为城市的顺序(一个一维数组),适应度设置为沿着该顺序需要走的总路程,路程越短适应度越好。遗传的过程便是通过模拟这个一维数组的排列变换来实现。通过T代的循环模拟之后,以最终得出的最优解作为结果。

这篇关于【备战美赛】遗传算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!