Java学习者论坛

 找回密码
 立即注册

QQ登录

只需一步,快速开始

手机号码,快捷登录

恭喜Java学习者论坛(https://www.javaxxz.com)已经为数万Java学习者服务超过8年了!积累会员资料超过10000G+
成为本站VIP会员,下载本站10000G+会员资源,购买链接:点击进入购买VIP会员
JAVA高级面试进阶视频教程Java架构师系统进阶VIP课程

分布式高可用全栈开发微服务教程

Go语言视频零基础入门到精通

Java架构师3期(课件+源码)

Java开发全终端实战租房项目视频教程

SpringBoot2.X入门到高级使用教程

大数据培训第六期全套视频教程

深度学习(CNN RNN GAN)算法原理

Java亿级流量电商系统视频教程

互联网架构师视频教程

年薪50万Spark2.0从入门到精通

年薪50万!人工智能学习路线教程

年薪50万!大数据从入门到精通学习路线年薪50万!机器学习入门到精通视频教程
仿小米商城类app和小程序视频教程深度学习数据分析基础到实战最新黑马javaEE2.1就业课程从 0到JVM实战高手教程 MySQL入门到精通教程
查看: 7046|回复: 0

[默认分类] 简单遗传算法MATLAB实现

[复制链接]
  • TA的每日心情
    开心
    2021-12-13 21:45
  • 签到天数: 15 天

    [LV.4]偶尔看看III

    发表于 2018-7-12 14:17:41 | 显示全部楼层 |阅读模式
    遗传算法的概念最早是由Bagley J.D 于1967年提出的。后来Michigan大学的J.H.Holland教授于1975年开始对遗传算法(Genetic Algorithm, GA)的机理进行系统化的研究。遗传算法是对达尔文生物进化理论的简单模拟,其遵循“适者生存”、“优胜略汰”的原理。遗传算法模拟一个人工种群的进化过程,并且通过选择、杂交以及变异等机制,种群经过若干代以后,总是达到最优(或近最优)的状态。
    自从遗传算法被提出以来,其得到了广泛的应用,特别是在函数优化、生产调度、模式识别、神经网络、自适应控制等领域,遗传算法更是发挥了重大的作用,大大提高了问题求解的效率。遗传算法也是当前“软计算”领域的重要研究课题。
    本文首先结合MATLAB对遗传算法实现过程进行详细的分析,然后通过1个实际的函数优化案例对其应用进行探讨。
    1. 遗传算法实现过程
    现实生活中很多问题都可以转换为函数优化问题,所以本文将以函数优化问题作为背景,对GA的实现过程进行探讨。大部分函数优化问题都可以写成求最大值或者最小值的形式,为了不是一般性,我们可以将所有求最优值的情况都转换成求最大值的形式,例如,求函数f(x)的最大值,

    若是求函数f(x)的最小值,可以将其转换成g(x)=-f(x),然后求g(x)的最大值,

    这里x可以是一个变量,也可是是一个由k个变量组成的向量, x=(x[sub]1[/sub], x[sub]2[/sub], …, x[sub]k[/sub])。每个x[sub]i[/sub], i=1,2,…,k, 其定义域为D[sub]i[/sub]D[sub]i[/sub]=[a[sub]i[/sub], b[sub]i[/sub]]
    一般规定f(x)在其定义域内只取正值,若不满足,可以将其转换成以下形式,

    其中C是一个正常数。
    1.1 编码与解码
    要实现遗传算法首先需要弄清楚如何对求解问题进行编码和解码。对于函数优化问题,一般来说,有两种编码方式,一是实数编码,一是二进制编码,两者各有优缺点,二进制编码具有稳定性高、种群多样性大等优点,但是需要的存储空间大,需要解码过程并且难以理解;而实数编码直接用实数表示基因,容易理解并且不要解码过程,但是容易过早收敛,从而陷入局部最优。本文以最常用的二进制编码为例,说明遗传编码的过程。
    从遗传算法求解的过程来看,需要处理好两个空间的问题,一个是编码空间,另一个是解空间,如下图所示

    从解空间到编码空间的映射过程成为编码过程;从编码空间到解空间的映射过程成为解码过程。下面就以求解一个简单的一维函数f(x) = -(x-1)^2+4, x的取值范围为[-1,3]最大值为例,来说明编码及解码过程。
    编码:
    在编码之前需要确定求解的精度,在这里,我们设定求解的精度为小数点后四位,即1e-4。这样可以将每个自变量x[sub]i[/sub]的解空间划分为个等分。以上面这个函数为例,即可以将x的解空间划分为(3-(-1))*1e+4=40000个等分。使n[sub]i[/sub]满足,这里n[sub]i[/sub]表示使上式成立的最小整数,即表示自变量x[sub]i[/sub]的基因串的长度。因为2[sup]15[/sup]<40000<2[sup]16 [/sup],这里n[sub]i[/sub]取16。例如0000110110000101就表示一个解空间中的基因串。表示所有自变量x=(x[sub]1[/sub], x[sub]2[/sub], …, x[sub]k[/sub])的二进制串的总长度称为一个染色体(Chromosome)的长度或者一个个体(Individual)的长度,。编码过程一般在实现遗传算法之前需要指定。
    解码:
    解码即将编码空间中的基因串翻译成解空间中的自变量的实际值的过程。对于二进制编码而言,每个二进制基因串都可以这样翻译成一个十进制实数值,。例如基因串0000110110000101,可以翻译为,这里二进制基因串转变成十进制是从左至右进行的。
    1.2 初始化种群
    在开始遗传算法迭代过程之前,需要对种群进行初始化。设种群大小为pop_size,每个染色体或个体的长度为chromo_size,种群的大小决定了种群的多样性,而染色体的长度则是由前述的编码过程决定的。一般随机生成初始种群,但是如果知道种群的实际分布,也可以按照此分布来生成初始种群。假设生成的初始种群为(v[sub]1[/sub], v[sub]2[/sub], …, v[sub]pop_size[/sub])
    1.3 选择操作
    选择操作即从前代种群中选择个体到下一代种群的过程。一般根据个体适应度的分布来选择个体。以初始种群(v[sub]1[/sub], v[sub]2[/sub], …, v[sub]pop_size[/sub])为例,假设每个个体的适应度为(fitness(v[sub]1[/sub]), fitness(v[sub]2[/sub]),…, fitness(v[sub]pop_size[/sub])),一般适应度可以按照解码的过程进行计算。以轮盘赌的方式选择个体,如下图

    随机转动一下轮盘,当轮盘停止转动时,若指针指向某个个体,则该个体被选中。很明显,具有较高适应度的个体比具有较低适应度的个体更有机会被选中。但是这种选择具有随机性,在选择的过程中可能会丢失掉比较好的个体,所以可以使用精英机制,将前代最优个体直接选到下一代中。
    轮盘赌选择具体算法如下(这里假定种群中个体是按照适应度从小到大进行排列的,如果不是,可以按照某种排序算法对种群个体进行重排):
    1. [b]Selection Algorithm[/b]
    2. var pop, pop_new;/*pop为前代种群,pop_new为下一代种群*/
    3. var fitness_value, fitness_table;/*fitness_value为种群的适应度,fitness_table为种群累积适应度*/
    4. for i=1:pop_size
    5.     r = rand*fitness_table(pop_size);/*随机生成一个随机数,在0和总适应度之间,因为fitness_table(pop_size)为最后一个个体的累积适应度,即为总适应度*/
    6.         first = 1;
    7.             last = pop_size;
    8.             mid = round((last+first)/2);
    9.             idx = -1;
    10.         /*下面按照排中法选择个体*/
    11.             while (first <= last) && (idx == -1)
    12.                 if r > fitness_table(mid)
    13.                     first = mid;
    14.                 elseif r < fitness_table(mid)
    15.                     last = mid;     
    16.                 else
    17.                     idx = mid;
    18.                     break;
    19.                 end if
    20.                 mid = round((last+first)/2);
    21.                 if (last - first) == 1
    22.                     idx = last;
    23.                     break;
    24.                 end if
    25.            end while
    26.    
    27.            for j=1:chromo_size
    28.                 pop_new(i,j)=pop(idx,j);
    29.            end for
    30. end for
    31. /*是否精英选择*/
    32. if elitism
    33.         p = pop_size-1;
    34. else
    35.         p = pop_size;
    36. end if
    37. for i=1:p
    38.        for j=1:chromo_size
    39.             pop(i,j) = pop_new(i,j);/*若是精英选择,则只将pop_new前pop_size-1个个体赋给pop,最后一个为前代最优个体保留*/
    40.        end for
    41. end for
    复制代码
    1.3 交叉操作
    交叉操作是对任意两个个体进行的(在这里我们实现的算法是直接对相邻的两个个体进行的)。随机选择两个个体,如下图所示

    然后随机生成一个实数0<=r<=1, 如果r<cross_rate, 0<cross_rate<1为交叉概率,则对这两个个体进行交叉,否则则不进行。如果需要进行交叉,再随机选择交叉位置(rand*chromo_size),如果等于0或者1,将不进行交叉。否则将交叉位置以后的二进制串进行对换(包括交叉位置)。(注意:有时候还可以进行多点交叉,但是这里只讨论单点交叉的情况)
    单点交叉具体算法如下:
    1. [b]Crossover algorithm[/b]
    2. for i=1:2:pop_size
    3.             if(rand < cross_rate)/*cross_rate为交叉概率*/
    4.                 cross_pos = round(rand * chromo_size);/*交叉位置*/
    5.                 if or (cross_pos == 0, cross_pos == 1)
    6.                     continue;/*若交叉位置为0或1,则不进行交叉*/
    7.                 end if
    8.                 for j=cross_pos:chromo_size
    9.                     pop(i,j)<->pop(i+1,j);/*交换*/
    10.                 end for
    11.             end if
    12. end for
    复制代码
    1.4 变异操作
    变异操作是对单个个体进行的。首先生成一个随机实数0<=r<=1, 如果r<mutate_rate,则对此个体进行变异操作, 0<mutate_rate<1为变异概率,一般为一个比较小的实数。对每一个个体,进行变异操作,如下图所示

    如个体需要进行变异操作,首先需要确定变异位置(rand*chromo_size),若为0则不进行变异,否则则对该位置的二进制数字进行变异:1变成0, 0变成1.(当然也可以选择多点进行变异)
    单点变异的具体算法描述如下:
    1. [b]Mutation algorithm[/b]
    2. for i=1:pop_size
    3.             if rand < mutate_rate/*mutate_rate为变异概率*/
    4.                 mutate_pos = round(rand*chromo_size);/*变异位置*/
    5.                 if mutate_pos == 0
    6.                     continue;/*若变异位置为0,则不进行变异*/
    7.                 end if
    8.                 pop(i,mutate_pos) = 1 - pop(i, mutate_pos);/*将变异位置上的数字至反*/
    9.             end if
    10. end for
    复制代码
    1.5 遗传算法流程
    遗传算法计算流程图如下图所示

    1.6 MATLAB程序实现
    初始化:
    1. %初始化种群
    2. %pop_size: 种群大小
    3. %chromo_size: 染色体长度
    4. function initilize(pop_size, chromo_size)
    5. global pop;
    6. for i=1:pop_size
    7.     for j=1:chromo_size
    8.         pop(i,j) = round(rand);
    9.     end
    10. end
    11. clear i;
    12. clear j;
    复制代码
    计算适应度:(该函数应该根据具体问题进行修改,这里优化的函数是前述的一维函数)
    1. %计算种群个体适应度,对不同的优化目标,此处需要改写
    2. %pop_size: 种群大小
    3. %chromo_size: 染色体长度
    4. function fitness(pop_size, chromo_size)
    5. global fitness_value;
    6. global pop;
    7. global G;
    8. for i=1:pop_size
    9.     fitness_value(i) = 0.;   
    10. end
    11. for i=1:pop_size
    12.     for j=1:chromo_size
    13.         if pop(i,j) == 1
    14.             fitness_value(i) = fitness_value(i)+2^(j-1);
    15.         end        
    16.     end
    17.      fitness_value(i) = -1+fitness_value(i)*(3.-(-1.))/(2^chromo_size-1);
    18.      fitness_value(i) = -(fitness_value(i)-1).^2+4;
    19. end
    20. clear i;
    21. clear j;
    复制代码
    对个体按照适应度大小进行排序:
    1. %对个体按适应度大小进行排序,并且保存最佳个体
    2. %pop_size: 种群大小
    3. %chromo_size: 染色体长度
    4. function rank(pop_size, chromo_size)
    5. global fitness_value;
    6. global fitness_table;
    7. global fitness_avg;
    8. global best_fitness;
    9. global best_individual;
    10. global best_generation;
    11. global pop;
    12. global G;
    13. for i=1:pop_size   
    14.     fitness_table(i) = 0.;
    15. end
    16. min = 1;
    17. temp = 1;
    18. temp1(chromo_size)=0;
    19. for i=1:pop_size
    20.     min = i;
    21.     for j = i+1:pop_size
    22.         if fitness_value(j)<fitness_value(min);
    23.             min = j;
    24.         end
    25.     end
    26.     if min~=i
    27.         temp = fitness_value(i);
    28.         fitness_value(i) = fitness_value(min);
    29.         fitness_value(min) = temp;
    30.         for k = 1:chromo_size
    31.             temp1(k) = pop(i,k);
    32.             pop(i,k) = pop(min,k);
    33.             pop(min,k) = temp1(k);
    34.         end
    35.     end
    36.    
    37. end
    38. for i=1:pop_size
    39.     if i==1
    40.         fitness_table(i) = fitness_table(i) + fitness_value(i);   
    41.     else
    42.         fitness_table(i) = fitness_table(i-1) + fitness_value(i);
    43.     end
    44. end
    45. fitness_table
    46. fitness_avg(G) = fitness_table(pop_size)/pop_size;
    47. if fitness_value(pop_size) > best_fitness
    48.     best_fitness = fitness_value(pop_size);
    49.     best_generation = G;
    50.     for j=1:chromo_size
    51.         best_individual(j) = pop(pop_size,j);
    52.     end
    53. end
    54. clear i;
    55. clear j;
    56. clear k;
    57. clear min;
    58. clear temp;
    59. clear temp1;
    复制代码
    选择操作:
    1. %轮盘赌选择操作
    2. %pop_size: 种群大小
    3. %chromo_size: 染色体长度
    4. %cross_rate: 是否精英选择
    5. function selection(pop_size, chromo_size, elitism)
    6. global pop;
    7. global fitness_table;
    8. for i=1:pop_size
    9.     r = rand * fitness_table(pop_size);
    10.     first = 1;
    11.     last = pop_size;
    12.     mid = round((last+first)/2);
    13.     idx = -1;
    14.     while (first <= last) && (idx == -1)
    15.         if r > fitness_table(mid)
    16.             first = mid;
    17.         elseif r < fitness_table(mid)
    18.             last = mid;     
    19.         else
    20.             idx = mid;
    21.             break;
    22.         end
    23.         mid = round((last+first)/2);
    24.         if (last - first) == 1
    25.             idx = last;
    26.             break;
    27.         end
    28.    end
    29.    
    30.    for j=1:chromo_size
    31.         pop_new(i,j)=pop(idx,j);
    32.    end
    33. end
    34. if elitism
    35.     p = pop_size-1;
    36. else
    37.     p = pop_size;
    38. end
    39. for i=1:p
    40.    for j=1:chromo_size
    41.         pop(i,j) = pop_new(i,j);
    42.    end
    43. end
    44. clear i;
    45. clear j;
    46. clear pop_new;
    47. clear first;
    48. clear last;
    49. clear idx;
    50. clear mid;
    复制代码
    复制代码
    交叉操作:
    1. %单点交叉操作
    2. %pop_size: 种群大小
    3. %chromo_size: 染色体长度
    4. %cross_rate: 交叉概率
    5. function crossover(pop_size, chromo_size, cross_rate)
    6. global pop;
    7. for i=1:2:pop_size
    8.     if(rand < cross_rate)
    9.         cross_pos = round(rand * chromo_size);
    10.         if or (cross_pos == 0, cross_pos == 1)
    11.             continue;
    12.         end
    13.         for j=cross_pos:chromo_size
    14.             temp = pop(i,j);
    15.             pop(i,j) = pop(i+1,j);
    16.             pop(i+1,j) = temp;
    17.         end
    18.     end
    19. end
    20. clear i;
    21. clear j;
    22. clear temp;
    23. clear cross_pos;
    复制代码
    复制代码
    变异操作:
    1. %单点变异操作
    2. %pop_size: 种群大小
    3. %chromo_size: 染色体长度
    4. %cross_rate: 变异概率
    5. function mutation(pop_size, chromo_size, mutate_rate)
    6. global pop;
    7. for i=1:pop_size
    8.     if rand < mutate_rate
    9.         mutate_pos = round(rand*chromo_size);
    10.         if mutate_pos == 0
    11.             continue;
    12.         end
    13.         pop(i,mutate_pos) = 1 - pop(i, mutate_pos);
    14.     end
    15. end
    16. clear i;
    17. clear mutate_pos;
    复制代码
    打印算法迭代过程:
    1. %打印算法迭代过程
    2. %generation_size: 迭代次数
    3. function plotGA(generation_size)
    4. global fitness_avg;
    5. x = 1:1:generation_size;
    6. y = fitness_avg;
    7. plot(x,y)
    复制代码
    算法主函数:
    1. %遗传算法主函数
    2. %pop_size: 输入种群大小
    3. %chromo_size: 输入染色体长度
    4. %generation_size: 输入迭代次数
    5. %cross_rate: 输入交叉概率
    6. %cross_rate: 输入变异概率
    7. %elitism: 输入是否精英选择
    8. %m: 输出最佳个体
    9. %n: 输出最佳适应度
    10. %p: 输出最佳个体出现代
    11. %q: 输出最佳个体自变量值
    12. function [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate, elitism)
    13. global G ; %当前代
    14. global fitness_value;%当前代适应度矩阵
    15. global best_fitness;%历代最佳适应值
    16. global fitness_avg;%历代平均适应值矩阵
    17. global best_individual;%历代最佳个体
    18. global best_generation;%最佳个体出现代
    19. fitness_avg = zeros(generation_size,1);
    20. disp "hhee"
    21. fitness_value(pop_size) = 0.;
    22. best_fitness = 0.;
    23. best_generation = 0;
    24. initilize(pop_size, chromo_size);%初始化
    25. for G=1:generation_size   
    26.     fitness(pop_size, chromo_size);  %计算适应度
    27.     rank(pop_size, chromo_size);  %对个体按适应度大小进行排序
    28.     selection(pop_size, chromo_size, elitism);%选择操作
    29.     crossover(pop_size, chromo_size, cross_rate);%交叉操作
    30.     mutation(pop_size, chromo_size, mutate_rate);%变异操作
    31. end
    32. plotGA(generation_size);%打印算法迭代过程
    33. m = best_individual;%获得最佳个体
    34. n = best_fitness;%获得最佳适应度
    35. p = best_generation;%获得最佳个体出现代
    36. %获得最佳个体变量值,对不同的优化目标,此处需要改写
    37. q = 0.;
    38. for j=1:chromo_size
    39.     if best_individual(j) == 1
    40.             q = q+2^(j-1);
    41.     end
    42. end
    43. q = -1+q*(3.-(-1.))/(2^chromo_size-1);
    44. clear i;
    45. clear j;
    复制代码
    复制代码
    2.  案例研究
    对上一节中的函数进行优化,设置遗传算法相关参数,程序如下
    1. function run_ga()
    2. elitism = true;%选择精英操作
    3. pop_size = 20;%种群大小
    4. chromo_size = 16;%染色体大小
    5. generation_size = 200;%迭代次数
    6. cross_rate = 0.6;%交叉概率
    7. mutate_rate = 0.01;%变异概率
    8. [m,n,p,q] = GeneticAlgorithm(pop_size, chromo_size, generation_size, cross_rate, mutate_rate,elitism);
    9. disp "最优个体"
    10. m
    11. disp "最优适应度"
    12. n
    13. disp "最优个体对应自变量值"
    14. q
    15. disp "得到最优结果的代数"
    16. p
    17. clear;
    复制代码
    复制代码
    结果如下:
    "最优个体"
    m =
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0
    "最优适应度"
    n =
    4.0000
    "最优个体对应自变量值"
    q =
    1.0000
    "得到最优结果的代数"
    p =
    74
    此结果非常准确。
    算法迭代过程图形:

    从上图中可以看出,随着迭代次数的增加,算法逐渐收敛。
    3. 总结
    本文详细的介绍了简单遗传算法的实现过程,并以一个简单的函数优化作为案例说明了其应用。但是由于该测试函数过于简单,在实际的应用过程中,还需要对相关参数进行调整,使其效率得到更大的提高。
    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|手机版|Java学习者论坛 ( 声明:本站资料整理自互联网,用于Java学习者交流学习使用,对资料版权不负任何法律责任,若有侵权请及时联系客服屏蔽删除 )

    GMT+8, 2024-3-28 23:36 , Processed in 0.370463 second(s), 46 queries .

    Powered by Discuz! X3.4

    © 2001-2017 Comsenz Inc.

    快速回复 返回顶部 返回列表