设为首页收藏本站
开启辅助访问

在路上

 找回密码
 立即注册
在路上 › 站点首页 ›学习 › 查看内容

基于遗传算法的优化问题求解

2016-8-29 13:27| 发布者: zhangjf| 查看: 559| 评论: 0

摘要: 生物学中的进化论的核心为“物竞天择，适者生存”，暗含了的规则是生物能否生存是不定的，但是适应环境的生物更容易生存。生物的多样性能够保持来源于繁殖和变异。没错，你没有点错，这的确是一篇有关人工智能入门的 ...

生物学中的进化论的核心为“物竞天择，适者生存”，暗含了的规则是生物能否生存是不定的，但是适应环境的生物更容易生存。生物的多样性能够保持来源于繁殖和变异。
没错，你没有点错，这的确是一篇有关人工智能入门的博客。开篇先提到一些生物学的观点是因为，人工智能中遗传算法的灵感来源于生物学，它是一种仿生的概念。

一.遗传算法
那么，什么是遗传算法呢？我们来举个栗子吧。
在爬虫动物园里有着各种各样的蚂蚁，我想选出一种蚂蚁来代表动物园去参加全城动物园的蚂蚁战斗比赛。那我该怎么选呢？这里有一个聪明人提出了一个方法：首先，我们从各个蚂蚁的种群中选择出一部分来（选择初代种群），让他们相互打架，然后把胜者留下来互相繁殖（交叉产生子代，选择了比较好的基因进行遗传）。把小蚂蚁养大，然后再让它们打架，胜者繁殖（不断生成子代）。通过多次的繁殖和选择，动物园有极大的可能选出的蚂蚁是所有蚂蚁中打架最厉害的。
好吧，这个例子不是特别的好。我理解的遗传算法，就是一个多点的不定向搜索。它通过多次的实验，来找到符合适应度函数的个体。

二.基本步骤
基本的步骤如下：
1.编码：将我们可以用来搜索的部分编码，常用二进制串
2.产生初代：
3.计算每个个体的适应度及适应度占总体的比例（这里我使用了轮盘赌方案）：
4.以交叉概率选择父代母代进行交叉
5.以变异概率进行变异
6.生成满足种群容量的子代
7.进化多代

三.代码及说明
java代码：

  1. import java.math.BigDecimal;
  2. import java.util.Random;
  4. public class Genetic {
  5. int geneSize = 20;
  6. int populationSize = 50;
  7. int iterationNum =100;
  8. double crossoverPro =0.8;
  9. double mutationPro = 0.05;
  10. int [][] individual = new int[populationSize][geneSize];
  11. double [] realValue =new double[populationSize];
  12. double [] fitness =new double [50];
  13. double [] fitnessPro =new double [populationSize];
  14. double currentOpt =0;
  15. int currentX =0;
  16. Random random =new Random();
  17. double [] max =new double[iterationNum];
  19. public void init(){
  20. for(int i =0;i<populationSize;i++){
  21. for(int j =0;j<geneSize;j++){
  22. if(random.nextBoolean())
  23. individual[i][j] =1;
  24. else
  25. individual[i][j] =0;
  26. }
  27. }
  28. }
  30. private void CalRealValue(){
  31. for(int i =0;i<populationSize;i++){
  32. realValue[i] =0;
  33. double decimal = 0;
  34. for(int j =0;j<3;j++){
  35. realValue[i] = realValue[i]*2+individual[i][j];
  36. }
  37. for(int j =geneSize-1;j>=3;j--){
  38. decimal = decimal/2+individual[i][j];
  39. }
  40. realValue[i] += decimal/2;
  41. }
  42. }
  44. private void CalFitnessAndFitnessPro(){
  45. double sum =0;
  46. currentOpt =0;
  47. currentX =0;
  48. for(int i =0;i<populationSize;i++){
  49. fitness[i] = realValue[i]+10*Math.sin(5*realValue[i])+7*Math.cos(4*realValue[i])+17;
  50. if(currentOpt<fitness[i]){
  51. currentOpt =fitness[i];
  52. currentX =i;
  53. }
  54. sum+=fitness[i];
  56. }
  57. double section =0;
  58. for(int i =0;i<populationSize;i++){
  59. section +=fitness[i];
  60. fitnessPro[i] = section/sum;
  61. }
  62. }
  64. private void Reproduction(){
  65. int [][] temp =new int [populationSize][geneSize];
  67. //交叉
  68. for(int i =0;i<populationSize-1;i=i+2){
  69. int [] father =new int [geneSize];
  70. double pro = random.nextDouble();
  71. for(int j=0;j<populationSize;j++){
  72. if(fitnessPro[j]>=pro){
  73. for(int k =0;k<geneSize;k++)
  74. father[k] = individual[j][k];
  75. break;
  76. }
  77. }
  78. pro =random.nextDouble();
  79. int [] mother =new int [geneSize];
  80. for(int j=0;j<populationSize;j++){
  81. if(fitnessPro[j]>=pro){
  82. for(int k =0;k<geneSize;k++)
  83. mother[k] = individual[j][k];
  84. break;
  85. }
  86. }
  87. double pm =random.nextDouble();
  88. if(pm<crossoverPro){
  89. int changePosition =random.nextInt(geneSize);
  90. for(int j=0;j<geneSize;j++){
  91. if(j<changePosition){
  92. temp[i][j] =father[j];
  93. temp[i+1][j] = mother[j];
  94. }
  95. else {
  96. temp[i][j] = mother[j];
  97. temp[i+1][j] = father[j];
  98. }
  99. }
  100. }else{
  101. for(int j=0;j<geneSize;j++){
  102. temp[i][j] =father[j];
  103. temp[i+1][j] = mother[j];
  104. }
  105. }
  106. }
  108. for(int i =0;i<geneSize;i++){
  109. individual[populationSize-1][i] = individual[currentX][i];
  110. }
  112. //变异
  113. for(int i =0;i<populationSize-1;i++){
  114. for(int j =0;j<geneSize;j++){
  115. if(random.nextDouble()<mutationPro)
  116. individual[i][j] = 1- temp[i][j];
  117. else
  118. individual[i][j] = temp[i][j];
  119. }
  120. }
  121. }
  123. public Genetic(){
  124. init();
  125. for(int i =0;i<iterationNum;i++){
  126. CalRealValue();
  127. CalFitnessAndFitnessPro();
  128. BigDecimal optTemp =new BigDecimal(currentOpt-17);
  129. BigDecimal valueTemp =new BigDecimal(realValue[currentX]);
  130. optTemp =optTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
  131. valueTemp =valueTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
  132. System.out.println("第"+i+"代，最大值为："+optTemp+" 对应X是："+valueTemp);
  133. max[i] = currentOpt-17;
  134. Reproduction();
  135. }
  136. }
  138. public double[] getMax(){
  139. return max;
  140. }
  142. public static void main(String[] args) {
  144. Genetic genetic =new Genetic();
  145. }
  146. }
复制代码

这里我使用了二进制编码，单点交叉，轮盘赌加精英选择（没代向下完整保留最优个体）。我目标是计算f(x) = x+ 10sin5x + 7cos4x 在[0,9]区间上的极大值，之所以在适应度函数里加入还加了17是因为f(x)在某些位置的时候是取到负数（最小-17），而参与轮盘赌计算的函数必须是正数，所以我加了17.

四.小尝试
二进制编码在0.001这样的数的时候是不精确的，于是我想能不能用十进制来解决这个问题呢？下面我尝试做了十进制编码（精确度是0.00001）
Java代码：

  1. import java.math.BigDecimal;
  2. import java.util.Random;
  4. public class DecimalGenetic {
  5. int geneSize = 6;
  6. int populationSize = 50;
  7. int iterationNum =100;
  8. double crossoverPro =0.8;
  9. double mutationPro = 0.01;
  10. int [][] individual = new int[populationSize][geneSize];
  11. double [] realValue =new double[populationSize];
  12. double [] fitness =new double [50];
  13. double [] fitnessPro =new double [populationSize];
  14. double currentOpt =0;
  15. int currentX =0;
  16. Random random =new Random();
  17. double []max =new double[iterationNum];
  19. public void init(){
  20. for(int i =0;i<populationSize;i++){
  21. for(int j =0;j<geneSize;j++){
  22. if(j == 0)
  23. individual[i][j] =random.nextInt(9);
  24. else
  25. individual[i][j] =random.nextInt(10);
  26. }
  27. }
  28. }
  30. private void CalRealValue(){
  31. for(int i =0;i<populationSize;i++){
  32. realValue[i] =0;
  33. realValue[i]+=individual[i][0];
  34. double decimal = 0;
  35. for(int j =geneSize-1;j>0;j--){
  36. decimal = decimal/10+individual[i][j];
  37. }
  38. realValue[i] += decimal/10;
  39. // System.out.println(realValue[i]+" "+i);
  40. }
  41. }
  43. private void CalFitnessAndFitnessPro(){
  44. double sum =0;
  45. currentOpt =0;
  46. currentX =0;
  47. for(int i =0;i<populationSize;i++){
  48. fitness[i] = realValue[i]+10*Math.sin(5*realValue[i])+7*Math.cos(4*realValue[i])+17;
  49. if(currentOpt<fitness[i]){
  50. currentOpt =fitness[i];
  51. currentX =i;
  52. }
  53. sum+=fitness[i];
  54. }
  55. double section =0;
  56. for(int i =0;i<populationSize;i++){
  57. section +=fitness[i];
  58. fitnessPro[i] = section/sum;
  59. }
  60. }
  62. private void Reproduction(){
  63. int [][] temp =new int [populationSize][geneSize];
  65. //产生交叉
  66. for(int i =0;i<populationSize-1;i=i+2){
  67. int [] father =new int [geneSize];
  68. double pro = random.nextDouble();
  69. for(int j=0;j<populationSize;j++){
  70. if(fitnessPro[j]>=pro){
  71. for(int k =0;k<geneSize;k++)
  72. father[k] = individual[j][k];
  73. break;
  74. }
  75. }
  76. pro =random.nextDouble();
  77. int [] mother =new int [geneSize];
  78. for(int j=0;j<populationSize;j++){
  79. if(fitnessPro[j]>=pro){
  80. for(int k =0;k<geneSize;k++)
  81. mother[k] = individual[j][k];
  82. break;
  83. }
  84. }
  85. double pm = random.nextDouble();
  86. if(pm<crossoverPro){
  87. int changePosition =random.nextInt(geneSize);
  88. for(int j=0;j<geneSize;j++){
  89. if(j<changePosition){
  90. temp[i][j] =father[j];
  91. temp[i+1][j] =mother[j];
  92. }
  93. else {
  94. temp[i][j] = mother[j];
  95. temp[i+1][j] = father[j];
  96. }
  97. }
  98. }
  99. else{
  100. for(int j=0;j<geneSize;j++){
  101. temp[i][j] =father[j];
  102. temp[i+1][j] =mother[j];
  103. }
  104. }
  105. }
  107. for(int i =0;i<geneSize;i++){
  108. individual[populationSize-1][i] = individual[currentX][i];
  109. }
  111. //变异
  112. for(int i =0;i<populationSize-1;i++){
  113. for(int j =0;j<geneSize;j++){
  114. if(random.nextDouble()<mutationPro)
  115. individual[i][j] = random.nextInt(10);
  116. else
  117. individual[i][j] = temp[i][j];
  118. }
  119. }
  120. }
  122. public DecimalGenetic(){
  123. init();
  124. for(int i =0;i<iterationNum;i++){
  125. CalRealValue();
  126. CalFitnessAndFitnessPro();
  127. BigDecimal optTemp =new BigDecimal(currentOpt-17);
  128. optTemp =optTemp.setScale(5, BigDecimal.ROUND_HALF_UP);
  129. System.out.println("第"+i+"代，最大值为："+optTemp+" 对应X是："+realValue[currentX]);
  130. max[i] = currentOpt-17;
  131. Reproduction();
  132. }
  133. }
  135. public double[] getMax(){
  136. return max;
  137. }
  140. public static void main(String[] args) {
  141. DecimalGenetic decimalGenetic =new DecimalGenetic();
  142. }
  144. }
复制代码

实现和二进制大部分一致，但是在变异部分我用了取随机数这个方法。

五.思考：
关于编码，我在做完之后有一些思考，想和大家分享.我们编码一个数据，用0-1串表示，每一位是没有差别的，但是转换为数字的时候，每一位的权值是不同的。对于真正的自然界，每个性状对于生物的存活几率的影响也是不同的。比如果蝇的翅膀大小和眼色对于它的生存几率的影响是不同的，那反应成我们这里的编码就是位置不同，权重不同.这里算是遗传算法的奇妙之处吧.

下面推荐一个讲述比较完整的博客：https://segmentfault.com/a/1190000004155021

收藏 邀请
上一篇：Chain of Responsibility Pattern（译）下一篇：Java 线程池详解

最新评论

相关分类

小黑屋|在路上 ( 蜀ICP备15035742号-1 )  

;

GMT+8, 2025-7-8 00:43

Copyright 2015-2025 djqfx

返回顶部