遗传算法(GA)的matlab实现

时间:2021-06-25 09:52:54

一、TASK

compute the maximum value:

 遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现

二、实现过程

1.     编码与解码

编码:

在编码之前需要确定求解的精度,设定求解的精度为小数点后六位,即10^6。这样可以将每个自变量x的解空间划分为(1-0)*10^6=1000000个等分。使n满足 (1-0)*10^6<2^n-1,这里n表示使上式成立的最小整数,即表示自变量x的基因串的长度。因为2^19<40000<2^20 ,所以n取20。解码:

二进制基因串转变成十进制:例如基因串 可以翻译为:

x=0+decimal( ) 。

2.      初始化种群

设种群大小为pop_size,每个染色体或个体的长度为chromo_size,假设生成的初始种群为(v1, v2, …, vpop_size)。

 

3.      选择操作

选择操作即从前代种群中选择个体到下一代种群的过程。一般根据个体适应度的分布来选择个体。以初始种群(v1, v2, …, vpop_size)为例,假设每个个体的适应度为(fitness(v1), fitness(v2),…,fitness(vpop_size)),一般适应度可以按照解码的过程进行计算。以轮盘赌的方式选择个体。

随机转动一下轮盘,当轮盘停止转动时,若指针指向某个个体,则该个体被选中。很明显,具有较高适应度的个体比具有较低适应度的个体更有机会被选中。但是这种选择具有随机性,在选择的过程中可能会丢失掉比较好的个体,所以可以使用精英机制,将前代最优个体直接选到下一代中。

轮盘赌选择具体算法如下(这里假定种群中个体是按照适应度从小到大进行排列的,如果不是,可以按照某种排序算法对种群个体进行重排):

Selection Algorithm

var pop, pop_new;/*pop为前代种群,pop_new为下一代种群*/

var fitness_value, fitness_table;/*fitness_value为种群的适应度,fitness_table为种群累积适应度*/

for i=1:pop_size

    r = rand*fitness_table(pop_size);/*随机生成一个随机数,在0和总适应度之间,因为fitness_table(pop_size)为最后一个个体的累积适应度,即为总适应度*/

        first = 1;

            last = pop_size;

            mid = round((last+first)/2);

            idx = -1;

        /*下面按照排中法选择个体*/

            while (first <= last) && (idx == -1)

                if r > fitness_table(mid)

                    first = mid;

                elseif r < fitness_table(mid)

                    last = mid;    

                else

                    idx = mid;

                    break;

                end if

                mid = round((last+first)/2);

                if (last - first) == 1

                    idx = last;

                    break;

                end if

           end while

  

           for j=1:chromo_size

                pop_new(i,j)=pop(idx,j);

           end for

end for

/*是否精英选择*/

if elitism

        p = pop_size-1;

else

        p = pop_size;

end if

for i=1:p

       for j=1:chromo_size

            pop(i,j) = pop_new(i,j);/*若是精英选择,则只将pop_new前pop_size-1个个体赋给pop,最后一个为前代最优个体保留*/

       end for

end for

 

4.      交叉操作

交叉操作是对任意两个个体进行的。随机选择两个个体, 然后随机生成一个实数0<=r<=1, 如果r<cross_rate, 0<cross_rate<1为交叉概率,则对这两个个体进行交叉,否则则不进行。如果需要进行交叉,再随机选择交叉位置(rand*chromo_size),如果等于0或者1,将不进行交叉。否则将交叉位置以后的二进制串进行对换(包括交叉位置)。

单点交叉具体算法如下:

Crossover algorithm

for i=1:2:pop_size

            if(rand < cross_rate)/*cross_rate为交叉概率*/

                cross_pos = round(rand * chromo_size);/*交叉位置*/

                if or (cross_pos == 0, cross_pos == 1)

                    continue;/*若交叉位置为0或1,则不进行交叉*/

                end if

                for j=cross_pos:chromo_size

                    pop(i,j)<->pop(i+1,j);/*交换*/

                end for

            end if

end for

 

5.      变异操作

变异操作是对单个个体进行的。首先生成一个随机实数0<=r<=1, 如果r<mutate_rate,则对此个体进行变异操作, 0<mutate_rate<1为变异概率,一般为一个比较小的实数。对每一个个体,进行变异操作。如个体需要进行变异操作,首先需要确定变异位置(rand*chromo_size),若为0则不进行变异,否则则对该位置的二进制数字进行变异:1变成0, 0变成1.

单点变异的具体算法描述如下:

Mutation algorithm

for i=1:pop_size

            if rand < mutate_rate/*mutate_rate为变异概率*/

                mutate_pos = round(rand*chromo_size);/*变异位置*/

                if mutate_pos == 0

                    continue;/*若变异位置为0,则不进行变异*/

                end if

                pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*将变异位置上的数字至反*/

            end if

end for

 

6.  设置遗传算法相关参数

遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现

遗传算法(GA)的matlab实现

三、结果与分析

当设置参数为

遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现

遗传算法(GA)的matlab实现

结果如图所示:

遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现

得到的最大值为19.8949

最优解为0.12749

 

改变迭代次数

遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现

发现并不影响结果

遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现遗传算法(GA)的matlab实现

得到的最大值为19.8949

最优解为0.12749

 

小结:
遗传算法中最重要的过程就是选择和交叉。遗传算法在函数优化方面发挥了重大的作用,大大提高了问题求解的效率。