虽然之前已经接触过遗传算法了,但这还是第一次 真刀真枪的在MATLAB上面写,记录一下,以供参考
总的来说遗传算法是一个基于随机过程的算法,其目标是为了max或min一个目标函数的值,求解的过程不是严格的推导,而是类似于随机产生个体,筛选最优解,不断的迭代,以此达到求解最优值。下面对其思想和理论做一些我个人的理解
遗传算法是为了求解目标函数的最优值(max=f(x1,x2,…xn)),而目标函数的最优值通过参数x1 x2…xn控制,那么我们把x1 x2 … xn等每个参数都表示为一个基因,如此一来,我们就有了n个基因构成一组解,我们把这n个基因构成的一组解称为染色体,而许多染色体组成了种群,下面梳理一下:
- 基因——参数
- 染色体——解
- 种群——一系列解
所以,我们的目标就是,找到一个最优的染色体,那么如何找到这个最优的染色体呢?下面就讲解一下流程
1.首先,我们初始化一组解,这最开始的一组解可以随机的生成
2.然后我们计算这一组解的适应度,适应度其实就是我们要max或min的函数转换成的,一般来说,一个染色体的适应度越高,那么他存活的几率最高,所以,如果我们的目标是max f(x1 … xn) 那么可以直接用目标函数求出的解作为适应度,如果目标是min的话,用其倒数。
3.筛选,找到适应度后,从这一代的种群里面筛选,采用随机的方法,把适应度不太好的解都随机地筛掉,选取出适应度比较好的解
4.杂交,随机的选择染色体进行杂交,杂交是如何来理解的呢,可以类似的理解为,参数的随机组合,比如说现在有一个染色体x1 x2 x3… xn=a1 a2 a3 … an 另外有一个染色体是b1 b2 b3 … bn 那么这两条染色体进行杂交,产生的结果可能是两个染色体的随机组合,a1 a2 b3 b4 ……,会有什么作用呢?这就要想一下遗传算法的总过程了,遗传算法会筛选出优秀的解,那么这些优秀的解里面的参数可能就是一些比较优秀的参数,这样让他们直接互换,互相杂交,就可能会把两个解的优秀基因融合在一起,这样就生成了一个更优的个体,这个更优的染色体就更可能被遗传下去,如此反复迭代,最终生成一个接近于最优的染色体。
5.变异,变异是随机的使解里面的基因产生变化,这样就可以产生新的基因以供筛选
6.如果迭代到一定代数,或达到一个比较稳定的值(连续n带没有发生变化),那么可以结束遗传算法,并从最后一代里面选取最优染色体作为整个算法最终的解。如果没有达到这个值,那么就把筛选、杂交、变异产生的新的一组解作为新的一代,然后返回第2步,对着新的一代重新进行筛选、杂交、变异,如此反复;
这就是遗传算法的大致过程了,上面也掺杂了很多个人的理解,下面解释一下贯穿整个算法的问题——如何用基因表示参数,用染色体表示解,答案就是编码
编码——把一组解编制为一串特色的编码,方式有很多。较为常用的是二进制编码、实数编码、符号编码,以二进制编码为例,我们知道一组解是由参数组成的,那么参数应该有对应的取值范围和取值粒度,我们把这些参数离散化,比如说x1取值范围是0-1,精确到小数点后3位,那么离散化之后x1的取值就是0、0.001、0.002、0.003、……0.999、1.0,一共有1001个可能的取值,那么我们用一个10位的二进制串表示这1001个可能的取值,00000000对应0 00000001对应0.001、0000000010对应0.002、……
解码——编码的逆过程
杂交和变异都在这些被编码过后的串上面进行,生成新一代的种群后,在进行下一次评估的时候,把种群里面的基因解码为参数,然后计算适应度
筛选也有多种筛选方法,通常来说,各个方法基本都是筛选出适应度较大的解,可以通过随机选择个体比较、直接排序筛选、轮盘筛选等方法
杂交也有很多不同的方法,不过大同小异,基本上都是选择染色体上面的区间,两个染色体交换区间里面的内容
变异也有很大不同的方法,某个基因的某个位置变异、局部顺序颠倒等,变异的目的是为了基因的多样性,所以选择如何变异影响不大,主要是变异的概率,如果变异概率太高,那么优良基因很可能会遭到破坏,如果变异概率过低,种群多样性下降太快,要选取一个合适的值,一般可以取0.001·0.2
下面以2011B实操一下:
待补充……