优化算法——遗传算法

与遗传算法的第一次接触

遗传算法是我进入研究生阶段接触的第一个智能算法,从刚开始接触,到后来具体去研究,再到后来利用遗传算法完成了水利水电的程序设计比赛,整个过程中对遗传算法有了更深刻的理解,在此基础上,便去学习和研究了粒子群算法,人工蜂群算法等等的群体智能算法。想利用这个时间,总结下我对于遗传算法的理解,主要还是些基本的知识点的理解。

遗传算法的基本概念

遗传算法(Genetic Algorithm, GA)是由Holland提出来的,是受遗传学中的自然选择和遗传机制启发发展起来的一种优化算法,它的基本思想是模拟生物和人类进化的方法求解复杂的优化问题。

基本定义

  1. 个体(individual):在遗传学中表示的是基因编码,在优化问题中指的是每一个解。
  2. 适应值(fitness):评价个体好坏的标准,在优化问题中指的是优化函数。
  3. 群体(population): 由个体组成的集合
  4. 遗传操作:遗传操作的主要目的是用于在当前的群体中产生新的群体,主要的操作包括:选择(selection)、交叉(crossover)、变异(mutation)。

遗传算法的基本流程

遗传算法的过程中主要包括这样几个要素:1、参数的编码。2、初始群体的设定。3、适应度函数的设计。4、遗传操作设计。5、控制参数的设定。 基本遗传算法的具体过程如下:

遗传算法过程中的具体操作

参数的编码

遗传算法中的参数编码的方式主要有:1、二进制编码。2、Gray编码。3、实数编码。4、有序编码。

二进制编码

二进制编码是最原始的编码方式,遗传算法最初是在二进制编码的方式下进行运算的。二进制编码也是遗传算法中使用最为直接的运算编码方式。二进制编码是指利用00和11对问题的解向量进行编码。例如,对于如下的优化问题:

其三维图像如下图所示:

在对这样的优化问题进行二进制编码的过程中,是将问题的可能解编码为二进制位串,例如问题的可能解为实数对(x1,x2),首先必须将x1和x2分别使用二进制位串表示,然后将他们的二进制位串组合在一起。对于每一个变量的二进制位串的长度取决于变量的定义域所要求的精度。


此时,个体可以表示为:

其中,前1818位表示的是x1x_1,后1515位表示的是x2x_2。

Gray编码

这种编码方式在求解优化问题时,本人基本上没做过任何研究。

实数编码

在二进制编码的过程中存在这样的一个问题,即在计算适应值的时候需要将二进制编码转换成十进制的编码进行运算,这样,很显然会想到能否直接使用十进制编码直接进行运算,如上例中的(x1,x2)\left ( x_1,x_2 \right )这样的编码方式。

有序编码

有序编码主要使用在TSP问题中,在本文中主要涉及二进制编码和实数编码

初始群体的设定

在解决了个体的编码问题后,需要解决的问题是如何利用个体表示群体。在上述中,我们知道,群体是个体的集合。假设初始群体的大小为N=20。对于二进制编码方式与实数编码方式产生20个初始解。如:

v1=(010001001011010000111110010100010) 对应的实数编码的方式则为:

v1=(1.052426,5.755330)

对于二进制编码则是随机初始化20组这样的初始解,每组初始解随机初始化33位的0−1编码。而对于实数编码方式,则是在区间上随机初始化20组初始解。

适应度函数的计算

适应度函数的目的是评价个体的好坏,如上面的优化问题中,即为最终的优化目标函数。对于二进制编码,则需要先将二进制编码转换成实数编码,再进行适应值函数的计算,对于实数编码方式,则直接进行适应值函数的计算。

遗传操作设计

遗传操作主要包括:选择(selection)、交叉(crossover)、变异(mutation),遗传操作的主要目的是从当前的群体中产生新的群体,这样便能使得产生新的更优的个体。

选择(selection)

选择操作的目的是选择出父体,用于参加交叉(crossover)和变异(mutation)操作。一般使用较多的方式是轮盘赌的选择策略(Roulette Wheel Selection)。根据每个个体的适应值,计算出相对适应值大小,即:

相对适应值又称为选择概率,将一个圆盘划分成NN份,即群体的大小。每个扇面的面积与其选择概率成正比。轮盘如下图所示:

交叉(crossover)

交叉操作也称为杂交,其目的是产生新的个体。 对于二进制编码方式,主要有单点杂交和多点杂交。单点杂交是指在二进制串中随机选择一位,交换两个父体中该位以后的二进制串,用以产生新的个体,操作如下图所示:

多点杂交是指在二进制串中选择某几位进行杂交,其中以两点杂交最为常见,其过程如下图所示:

变异(mutation)

控制参数的设定

控制参数主要包括种群的规模N,演化代数T,杂交概率pc,变异概率pm等等。


在实现遗传算法时,一个常用的方法是将到当前代为止演化的最好个体单独存放起来,在遗传算法结束后,将演化过程中发现的最好个体作为问题的最优解或近似最优解。


求解优化问题的实例

问题描述

问题分析

这是一道不带约束条件的函数优化的问题,既可以采用二进制编码方式,也可以采用十进制的编码方式,在本题的解决过程中,采用十进制的编码方式。首先通过Matlab得到的函数图像大致如下,从图像中可以观察到当n=2n=2时,我们可以在(0,0)(0,0)附近取得函数的最小值。

算法设计

基于以上的分析,当n=2时,以下分别从个体的编码、适应值函数、选择策略、杂交算子、变异算子、参数设置、初始化以及终止条件这八个方面对程序的设计作简要的描述:

个体编码

采用实数向量编码,每一个个体是一实数对(x1,x2)。

适应值函数

该优化问题是一个极小化问题,可对目标函数作简单变换,同时考虑到在选择策略时选择的是轮盘赌的选择策略,轮盘赌的选择策略有一个要求就是个体的适应值要为正数,因此,可以作如下的变换:F=30−f(x1,x2),这里的3030是取的一个上界。这样,既保证了变换后的适应值函数式中为正,而且我们可以将极小化问题转换成一个极大值问题考虑。

选择策略

采用轮盘赌的选择策略,因为在计算适应值时已经作了处理,即适应值始终为正,这样就可以使用轮盘赌的选择策略。轮盘赌的选择策略是一种基于适应值比例的选择策略,适应值越大被选择到下一代的概率也会越大。

初始化

在区间内随机初始化种群的个体,并置个体的适应值,适应值之和以及相对适应值比例为00。

终止条件

采用代数作为终止条件,当算法运行到指定的最大代数时,程序停止。

实验代码

#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<cmath>
#include<fstream>

using namespace std;


const int COLONY_SIZE=100;  //个体数目
const int Size=2;//个体的长度
const int Generation=3000;//代数
const double OVER=0.7;//杂交的概率
const double MUTATE=0.1;//变异的概率
const double UPPER=30.0;//函数的上界

struct Indival
{
    double code[Size];
    double fitness;
    double cfitness;
    double rfitness;
}Group[COLONY_SIZE];

Indival newGroup[COLONY_SIZE];

Indival bestChrom;//记录最好的个体

int GenNum=0;

double random(double, double);
void initiate();
void calvalue();
void select();
void crossOver();
void xOver(int,int);
void mutate();
double delta(int,double,double,double);
void sort();

/*****************主函数***************/
int main()
{
    ofstream output;
    srand((unsigned)time(NULL));
    initiate();
    calvalue();
    output.open("data.txt");
    while(GenNum<=Generation)
    {
        GenNum++;
        select();   
        crossOver();
        mutate();   
        calvalue(); 
        sort();
        if (bestChrom.fitness<Group[0].fitness)
        {
            bestChrom.code[0]=Group[0].code[0];
            bestChrom.code[1]=Group[0].code[1];
            bestChrom.fitness=Group[0].fitness;
        }
//      output<<"gen: "<<GenNum<<"最优解为:"<<endl;
//      output<<"x1: "<<bestChrom.code[0]<<"  x2: "<<bestChrom.code[1]<<"   函数值为: "<<(30-bestChrom.fitness)<<endl;
        output<<GenNum<<"   "<<(30-bestChrom.fitness)<<endl;
    }
    output.close();
    cout<<"运行结束!"<<endl;//提示运行结束
    return 0;
}


/******************************函数的实现*****************************************/


double random(double start, double end){//随机产生区间内的随机数   
    return start+(end-start)*rand()/(RAND_MAX + 1.0);
}

void initiate()//初始化
{
    for(int i=0;i<COLONY_SIZE;i++)
    {
        Group[i].code[0]=random(-30,30);
        Group[i].code[1]=random(-30,30);
        Group[i].fitness=0;//适应值
        Group[i].cfitness=0;//相对适应值比例之和
        Group[i].rfitness=0;//相对适应值比例
    }
}

void calvalue()//计算适应值
{
    double x1,x2;
    double sum=0;
    double part1,part2;//将函数分成几个部分
    for(int i=0;i<COLONY_SIZE;i++)
    {
        x1=Group[i].code[0];
        x2=Group[i].code[1];
        part1=-0.2*sqrt((x1*x1+x2*x2)/Size);
        part2=(cos(2*3.1415926*x1)+cos(2*3.1415926*x2))/Size;
        Group[i].fitness=UPPER-(-20*exp(part1)-exp(part2)+20+2.71828);//适应值
        sum+=Group[i].fitness;//计算适应值之和
    }
    for(int mem=0;mem<COLONY_SIZE;mem++)//轮盘赌选择机制里所要求的几个参数
    {
        Group[mem].rfitness=Group[mem].fitness/sum;//适应值的比例
    }
    Group[0].cfitness=Group[0].rfitness;
    for(mem=1;mem<COLONY_SIZE;mem++)
    {
        Group[mem].cfitness=Group[mem-1].cfitness+Group[mem].rfitness;//模拟轮盘
    }


}
void select()
{
    double p;
    for(int i=0;i<COLONY_SIZE;i++)//挑选出N个个体
    {
        p=random(0,1);//随机产生0到1之间的随机数
        if(p<Group[0].cfitness)
            newGroup[i]=Group[0];
        else
        {
            for(int j=1;j<COLONY_SIZE;j++)//往轮盘后走
            {
                if(p>=Group[j-1].cfitness&&p<Group[j].cfitness)
                {
                    newGroup[i]=Group[j];
                    break;
                }
            }
        }
    }
    for(i=0;i<COLONY_SIZE;i++)//从newGroup复制到Group中
        Group[i]=newGroup[i];
}
void crossOver()
{
    int mem,one;
    int first=0;//记录杂交的数目
    double x;
    for(mem=0;mem<COLONY_SIZE;mem++)
    {
        x=random(0,1);
        if(x<OVER)
        {
            ++first;
            if(first%2==0)//若为偶数
                xOver(one,mem);
            else 
                one=mem;
        }
    }
}
void xOver(int one,int two)
{
    double point;
    point=random(0,1);
    Group[one].code[0]=Group[one].code[0]*point+Group[two].code[0]*(1-point);
    Group[one].code[1]=Group[one].code[1]*point+Group[two].code[1]*(1-point);
    Group[two].code[0]=Group[one].code[0]*(1-point)+Group[two].code[0]*point;
    Group[two].code[1]=Group[one].code[1]*(1-point)+Group[two].code[1]*point;
}
void mutate()
{
    double x;
    for(int i=0;i<COLONY_SIZE;i++)
    {
        for(int j=0;j<Size;j++)
        {
            x=random(0,1);
            if (x<MUTATE)
            {
                Group[i].code[j]=delta(GenNum,Group[i].code[0],30,-30);
            }
        }
    }
}


double delta(int t,double x,double u,double l)
{
    double temp1;
    double temp2;
    double y;
    double r=random(0,1);
    temp1=pow((1-t/Generation),4);
    temp2=pow(r,temp1);
    int a=(int)random(0,2);
    if(a==0)
    {
        y=u-x;
        return (x+y*(1-temp2));
    }else
    {
        y=x-l;
        return (x-y*(1-temp2));
    }
}

void sort()//排序
{
    Indival temp;
    for(int i=0;i<COLONY_SIZE-1;i++)
    {
        for(int j=i+1;j<COLONY_SIZE;j++)
        {
            if(Group[i].fitness<Group[j].fitness)
            {
                temp=Group[i];
                Group[i]=Group[j];
                Group[j]=temp;
            }
        }
    }
}

最终结果

我在这里简单介绍了遗传算法,遗传算法是一个研究较多的算法,还有利用遗传算法求解组合优化问题,带约束的优化问题,还有一些遗传算法的理论知识,如模式定理,积木块假设,在这里就不一一列举了,希望我的博文对你的学习有帮助,也欢迎转载,谢谢,有不到位的地方还请指出。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏生信技能树

二代测序数据拼接之原理篇

前前后后接触了一些基因组和转录组拼接的工作,而且后期还会持续进行。期间遇到了各种各样莫名其妙的坑,也尝试了一些不同的方法和软件,简单做一个阶段性小结,本篇是原理...

1.7K50
来自专栏蜉蝣禅修之道

优化后的Levensthein distance算法实现

42350
来自专栏技术总结

算法(3)

22770
来自专栏潇涧技术专栏

Python Algorithms - C7 Greedy

Python算法设计篇(7) Chapter 7: Greed is good? Prove it!

13720
来自专栏Small Code

Python-NumPy基础

前言 这两天读完《利用Python进行数据分析》 这本书的第4章:NumPy 基础:数组和矢量计算 后,在进行下一步阅读高级应用前,先整理本章内容,做个笔记备查...

368100
来自专栏老马说编程

(34) 随机 / 计算机程序的思维逻辑

随机 本节,我们来讨论随机,随机是计算机程序中一个非常常见的需求,比如说: 各种游戏中有大量的随机,比如扑克游戏洗牌 微信抢红包,抢的红包金额是随机的 北京购...

27560
来自专栏数据结构与算法

cf932E. Team Work(第二类斯特灵数 组合数)

$$m^n = \sum_{i = 0}^m C_{n}^i S(n, i) i!$$

11340
来自专栏漫漫深度学习路

tensorflow学习笔记(四十):tensorflow语音识别 及 python音频处理库

tensorflow 语音识别 最近在做语音识别的项目,现在项目告一段落,就把最近碰到的东西做一个总结。 python中关于语音处理的库 scipy.io.wa...

1.3K90
来自专栏温安适的blog

以回溯解高速公路重建与正序全排列

39660
来自专栏hadoop学习笔记

HanLP 关键词提取算法分析详解

l 参考论文:《TextRank: Bringing Order into Texts》

19160

扫码关注云+社区

领取腾讯云代金券