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

ethernet 发布于2019-06-26 18:13 / 2271人阅读

摘要：开篇先提到一些生物学的观点是因为，人工智能中遗传算法的灵感来源于生物学，它是一种仿生的概念。我理解的遗传算法，就是一个多点的不定向搜索。

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

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

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

三.代码及说明
Java代码：

import java.math.BigDecimal;
import java.util.Random;

public class Genetic {
    int geneSize = 20;
    int populationSize = 50;
    int iterationNum =100;
    double crossoverPro =0.8;
    double mutationPro = 0.05;
    int [][] individual = new int[populationSize][geneSize];
    double [] realValue =new double[populationSize];
    double [] fitness =new double [50];
    double [] fitnessPro =new double [populationSize];
    double currentOpt =0;
    int currentX =0;
    Random random =new Random();
    double [] max =new double[iterationNum];

    public void init(){
        for(int i =0;i=3;j--){
                decimal = decimal/2+individual[i][j];
            }
            realValue[i] += decimal/2; 
        }
    }
    
    private void CalFitnessAndFitnessPro(){
        double sum =0;
        currentOpt =0;
        currentX =0;
        for(int i =0;i=pro){
                    for(int k =0;k=pro){
                    for(int k =0;k
这里我使用了二进制编码，单点交叉，轮盘赌加精英选择（没代向下完整保留最优个体）。我目标是计算f(x) = x+ 10sin5x + 7cos4x 在[0,9]区间上的极大值，之所以在适应度函数里加入还加了17是因为f(x)在某些位置的时候是取到负数（最小-17），而参与轮盘赌计算的函数必须是正数，所以我加了17.
四.小尝试
二进制编码在0.001这样的数的时候是不精确的，于是我想能不能用十进制来解决这个问题呢？下面我尝试做了十进制编码（精确度是0.00001）
Java代码：
import java.math.BigDecimal;
import java.util.Random;

public class DecimalGenetic {
    int geneSize = 6;
    int populationSize = 50;
    int iterationNum =100;
    double crossoverPro =0.8;
    double mutationPro = 0.01;
    int [][] individual = new int[populationSize][geneSize];
    double [] realValue =new double[populationSize];
    double [] fitness =new double [50];
    double [] fitnessPro =new double [populationSize];
    double currentOpt =0;
    int currentX =0;
    Random random =new Random();
    double []max =new double[iterationNum];
    
    public void init(){
        for(int i =0;i0;j--){
                decimal = decimal/10+individual[i][j];
            }
            realValue[i] += decimal/10; 
        //    System.out.println(realValue[i]+"   "+i);
        }
    }
    
    private void CalFitnessAndFitnessPro(){
        double sum =0;
        currentOpt =0;
        currentX =0;
        for(int i =0;i=pro){
                    for(int k =0;k=pro){
                    for(int k =0;k
实现和二进制大部分一致，但是在变异部分我用了取随机数这个方法。
五.思考：
关于编码，我在做完之后有一些思考，想和大家分享.我们编码一个数据，用0-1串表示，每一位是没有差别的，但是转换为数字的时候，每一位的权值是不同的。对于真正的自然界，每个性状对于生物的存活几率的影响也是不同的。比如果蝇的翅膀大小和眼色对于它的生存几率的影响是不同的，那反应成我们这里的编码就是位置不同，权重不同.这里算是遗传算法的奇妙之处吧.
下面推荐一个讲述比较完整的博客：https://segmentfault.com/a/1190000004155021

私有云云服务器学习遗传算法遇到的问题最优化方法大作业遗传算法论文最优化问题算法最优化问题与算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/19602.html

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

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

ivan_qhz 2019-08-14 15:38 评论0 收藏0
100 个基本 Python 面试问题第二部分(21-40)

摘要：为我们提供了许多内置函数，例如并提供了创建用户定义函数的能力。会将该变量视为函数级作用域中的局部变量。回到目录中函数的用途是什么是中的内置函数之一。请注意，这种类型的参数语法不允许将命名参数传递给函数。函数接受一个称为的可选参数。 ...

2450184176 2021-10-11 10:59 评论0 收藏0
寻优算法之粒子群

摘要：遗传算法回顾核心算子其中代表第个粒子的速度，代表惯性权值和表示学习参数，表示在之间的随机数代表第个粒子搜索到的历史最优值代表整个集群搜索到的最优值代表第个粒子的当前位置。导言粒子群PSO算法相比遗传算法实现会简单一点，核心就是根据算子更新个体历史最优和全局最优。粒子群用的不多，给我的感觉是收敛很快的一种算法。这种算法较为容易陷入局部最优，若问题具有欺骗性（具有多个假峰，且优化资源集...

wangshijun 2019-07-30 16:22 评论0 收藏0
世界冠军之路：菜鸟车辆路径规划求解引擎研发历程

摘要：已有的经典求解算法可以分为精确解算法和启发式算法两大类。所以还有一大部分研究集中于启发式算法领域。此外，经过不断的探索研究，元启发式算法被证明在求解方面具有很好的效果和效率。 showImg(https://segmentfault.com/img/remote/1460000018814897); 阿里妹导读：车辆路径规划问题（Vehicle Routing Problem, VR...

CoreDump 2019-06-24 18:23 评论0 收藏0