一、遗传算法简介
1 引言
2 遗传算法理论
2.1 遗传算法的生物学基础
2.2 遗传算法的理论基础
2.3 遗传算法的基本概念
2.4 标准的遗传算法
2.5 遗传算法的特点
2.6 遗传算法的改进方向
3 遗传算法流程
4 关键参数说明
二、BP神经网络简介
1 BP神经网络概述
BP(Back Propagation)神经网络是1986年由Rumelhart和McCelland为首的科研小组提出,参见他们发表在Nature上的论文 Learning representations by back-propagating errors 。
BP神经网络是一种按误差逆传播算法训练的多层前馈网络,是目前应用最广泛的神经网络模型之一。BP网络能学习和存贮大量的 输入-输出模式映射关系,而无需事前揭示描述这种映射关系的数学方程。它的学习规则是使用最速下降法,通过反向传播来不断 调整网络的权值和阈值,使网络的误差平方和最小。
2 BP算法的基本思想
上一次我们说到,多层感知器在如何获取隐层的权值的问题上遇到了瓶颈。既然我们无法直接得到隐层的权值,能否先通过输出层得到输出结果和期望输出的误差来间接调整隐层的权值呢?BP算法就是采用这样的思想设计出来的算法,它的基本思想是,学习过程由信号的正向传播与误差的反向传播两个过程组成。
正向传播时,输入样本从输入层传入,经各隐层逐层处理后,传向输出层。若输出层的实际输出与期望的输出(教师信号)不符,则转入误差的反向传播阶段。
反向传播时,将输出以某种形式通过隐层向输入层逐层反传,并将误差分摊给各层的所有单元,从而获得各层单元的误差信号,此误差信号即作为修正各单元权值的依据。这两个过程的具体流程会在后文介绍。
BP算法的信号流向图如下图所示
3 BP网络特性分析——BP三要素
我们分析一个ANN时,通常都是从它的三要素入手,即
1)网络拓扑结构;
2)传递函数;
3)学习算法。
每一个要素的特性加起来就决定了这个ANN的功能特性。所以,我们也从这三要素入手对BP网络的研究。
3.1 BP网络的拓扑结构
上一次已经说了,BP网络实际上就是多层感知器,因此它的拓扑结构和多层感知器的拓扑结构相同。由于单隐层(三层)感知器已经能够解决简单的非线性问题,因此应用最为普遍。三层感知器的拓扑结构如下图所示。
一个最简单的三层BP:
3.2 BP网络的传递函数
BP网络采用的传递函数是非线性变换函数——Sigmoid函数(又称S函数)。其特点是函数本身及其导数都是连续的,因而在处理上十分方便。为什么要选择这个函数,等下在介绍BP网络的学习算法的时候会进行进一步的介绍。
单极性S型函数曲线如下图所示。
双极性S型函数曲线如下图所示。
3.3 BP网络的学习算法
BP网络的学习算法就是BP算法,又叫 δ 算法(在ANN的学习过程中我们会发现不少具有多个名称的术语), 以三层感知器为例,当网络输出与期望输出不等时,存在输出误差 E ,定义如下
下面我们会介绍BP网络的学习训练的具体过程。
4 BP网络的训练分解
训练一个BP神经网络,实际上就是调整网络的权重和偏置这两个参数,BP神经网络的训练过程分两部分:
前向传输,逐层波浪式的传递输出值;
逆向反馈,反向逐层调整权重和偏置;
我们先来看前向传输。
前向传输(Feed-Forward前向反馈)
在训练网络之前,我们需要随机初始化权重和偏置,对每一个权重取[ − 1 , 1 ] [-1,1][−1,1]的一个随机实数,每一个偏置取[ 0 , 1 ] [0,1][0,1]的一个随机实数,之后就开始进行前向传输。
神经网络的训练是由多趟迭代完成的,每一趟迭代都使用训练集的所有记录,而每一次训练网络只使用一条记录,抽象的描述如下:
while 终止条件未满足:for record:dataset:trainModel(record)
4.1 逆向反馈(Backpropagation)
4.2 训练终止条件
每一轮训练都使用数据集的所有记录,但什么时候停止,停止条件有下面两种:
设置最大迭代次数,比如使用数据集迭代100次后停止训练
计算训练集在网络上的预测准确率,达到一定门限值后停止训练
5 BP网络运行的具体流程
5.1 网络结构
输入层有n nn个神经元,隐含层有p pp个神经元,输出层有q qq个神经元。
5.2 变量定义
第九步:判断模型合理性
判断网络误差是否满足要求。
当误差达到预设精度或者学习次数大于设计的最大次数,则结束算法。
否则,选取下一个学习样本以及对应的输出期望,返回第三部,进入下一轮学习。
6 BP网络的设计
在进行BP网络的设计是,一般应从网络的层数、每层中的神经元个数和激活函数、初始值以及学习速率等几个方面来进行考虑,下面是一些选取的原则。
6.1 网络的层数
理论已经证明,具有偏差和至少一个S型隐层加上一个线性输出层的网络,能够逼近任何有理函数,增加层数可以进一步降低误差,提高精度,但同时也是网络 复杂化。另外不能用仅具有非线性激活函数的单层网络来解决问题,因为能用单层网络解决的问题,用自适应线性网络也一定能解决,而且自适应线性网络的 运算速度更快,而对于只能用非线性函数解决的问题,单层精度又不够高,也只有增加层数才能达到期望的结果。
6.2 隐层神经元的个数
网络训练精度的提高,可以通过采用一个隐含层,而增加其神经元个数的方法来获得,这在结构实现上要比增加网络层数简单得多。一般而言,我们用精度和 训练网络的时间来恒量一个神经网络设计的好坏:
(1)神经元数太少时,网络不能很好的学习,训练迭代的次数也比较多,训练精度也不高。
(2)神经元数太多时,网络的功能越强大,精确度也更高,训练迭代的次数也大,可能会出现过拟合(over fitting)现象。
由此,我们得到神经网络隐层神经元个数的选取原则是:在能够解决问题的前提下,再加上一两个神经元,以加快误差下降速度即可。
6.3 初始权值的选取
一般初始权值是取值在(−1,1)之间的随机数。另外威得罗等人在分析了两层网络是如何对一个函数进行训练后,提出选择初始权值量级为s√r的策略, 其中r为输入个数,s为第一层神经元个数。
6.4 学习速率
学习速率一般选取为0.01−0.8,大的学习速率可能导致系统的不稳定,但小的学习速率导致收敛太慢,需要较长的训练时间。对于较复杂的网络, 在误差曲面的不同位置可能需要不同的学习速率,为了减少寻找学习速率的训练次数及时间,比较合适的方法是采用变化的自适应学习速率,使网络在 不同的阶段设置不同大小的学习速率。
6.5 期望误差的选取
在设计网络的过程中,期望误差值也应当通过对比训练后确定一个合适的值,这个合适的值是相对于所需要的隐层节点数来确定的。一般情况下,可以同时对两个不同 的期望误差值的网络进行训练,最后通过综合因素来确定其中一个网络。
7 BP网络的局限性
BP网络具有以下的几个问题:
(1)需要较长的训练时间:这主要是由于学习速率太小所造成的,可采用变化的或自适应的学习速率来加以改进。
(2)完全不能训练:这主要表现在网络的麻痹上,通常为了避免这种情况的产生,一是选取较小的初始权值,而是采用较小的学习速率。
(3)局部最小值:这里采用的梯度下降法可能收敛到局部最小值,采用多层网络或较多的神经元,有可能得到更好的结果。
8 BP网络的改进
P算法改进的主要目标是加快训练速度,避免陷入局部极小值等,常见的改进方法有带动量因子算法、自适应学习速率、变化的学习速率以及作用函数后缩法等。 动量因子法的基本思想是在反向传播的基础上,在每一个权值的变化上加上一项正比于前次权值变化的值,并根据反向传播法来产生新的权值变化。而自适应学习 速率的方法则是针对一些特定的问题的。改变学习速率的方法的原则是,若连续几次迭代中,若目标函数对某个权倒数的符号相同,则这个权的学习速率增加, 反之若符号相反则减小它的学习速率。而作用函数后缩法则是将作用函数进行平移,即加上一个常数。
一、遗传算法简介
1 引言
2 遗传算法理论
2.1 遗传算法的生物学基础
2.2 遗传算法的理论基础
2.3 遗传算法的基本概念
2.4 标准的遗传算法
2.5 遗传算法的特点
2.6 遗传算法的改进方向
3 遗传算法流程
4 关键参数说明
二、BP神经网络简介
1 BP神经网络概述
BP(Back Propagation)神经网络是1986年由Rumelhart和McCelland为首的科研小组提出,参见他们发表在Nature上的论文 Learning representations by back-propagating errors 。
BP神经网络是一种按误差逆传播算法训练的多层前馈网络,是目前应用最广泛的神经网络模型之一。BP网络能学习和存贮大量的 输入-输出模式映射关系,而无需事前揭示描述这种映射关系的数学方程。它的学习规则是使用最速下降法,通过反向传播来不断 调整网络的权值和阈值,使网络的误差平方和最小。
2 BP算法的基本思想
上一次我们说到,多层感知器在如何获取隐层的权值的问题上遇到了瓶颈。既然我们无法直接得到隐层的权值,能否先通过输出层得到输出结果和期望输出的误差来间接调整隐层的权值呢?BP算法就是采用这样的思想设计出来的算法,它的基本思想是,学习过程由信号的正向传播与误差的反向传播两个过程组成。
正向传播时,输入样本从输入层传入,经各隐层逐层处理后,传向输出层。若输出层的实际输出与期望的输出(教师信号)不符,则转入误差的反向传播阶段。
反向传播时,将输出以某种形式通过隐层向输入层逐层反传,并将误差分摊给各层的所有单元,从而获得各层单元的误差信号,此误差信号即作为修正各单元权值的依据。这两个过程的具体流程会在后文介绍。
BP算法的信号流向图如下图所示
3 BP网络特性分析——BP三要素
我们分析一个ANN时,通常都是从它的三要素入手,即
1)网络拓扑结构;
2)传递函数;
3)学习算法。
每一个要素的特性加起来就决定了这个ANN的功能特性。所以,我们也从这三要素入手对BP网络的研究。
3.1 BP网络的拓扑结构
上一次已经说了,BP网络实际上就是多层感知器,因此它的拓扑结构和多层感知器的拓扑结构相同。由于单隐层(三层)感知器已经能够解决简单的非线性问题,因此应用最为普遍。三层感知器的拓扑结构如下图所示。
一个最简单的三层BP:
3.2 BP网络的传递函数
BP网络采用的传递函数是非线性变换函数——Sigmoid函数(又称S函数)。其特点是函数本身及其导数都是连续的,因而在处理上十分方便。为什么要选择这个函数,等下在介绍BP网络的学习算法的时候会进行进一步的介绍。
单极性S型函数曲线如下图所示。
双极性S型函数曲线如下图所示。
3.3 BP网络的学习算法
BP网络的学习算法就是BP算法,又叫 δ 算法(在ANN的学习过程中我们会发现不少具有多个名称的术语), 以三层感知器为例,当网络输出与期望输出不等时,存在输出误差 E ,定义如下
下面我们会介绍BP网络的学习训练的具体过程。
4 BP网络的训练分解
训练一个BP神经网络,实际上就是调整网络的权重和偏置这两个参数,BP神经网络的训练过程分两部分:
前向传输,逐层波浪式的传递输出值;
逆向反馈,反向逐层调整权重和偏置;
我们先来看前向传输。
前向传输(Feed-Forward前向反馈)
在训练网络之前,我们需要随机初始化权重和偏置,对每一个权重取[ − 1 , 1 ] [-1,1][−1,1]的一个随机实数,每一个偏置取[ 0 , 1 ] [0,1][0,1]的一个随机实数,之后就开始进行前向传输。
神经网络的训练是由多趟迭代完成的,每一趟迭代都使用训练集的所有记录,而每一次训练网络只使用一条记录,抽象的描述如下:
while 终止条件未满足:for record:dataset:trainModel(record)
4.1 逆向反馈(Backpropagation)
4.2 训练终止条件
每一轮训练都使用数据集的所有记录,但什么时候停止,停止条件有下面两种:
设置最大迭代次数,比如使用数据集迭代100次后停止训练
计算训练集在网络上的预测准确率,达到一定门限值后停止训练
5 BP网络运行的具体流程
5.1 网络结构
输入层有n nn个神经元,隐含层有p pp个神经元,输出层有q qq个神经元。
5.2 变量定义
第九步:判断模型合理性
判断网络误差是否满足要求。
当误差达到预设精度或者学习次数大于设计的最大次数,则结束算法。
否则,选取下一个学习样本以及对应的输出期望,返回第三部,进入下一轮学习。
6 BP网络的设计
在进行BP网络的设计是,一般应从网络的层数、每层中的神经元个数和激活函数、初始值以及学习速率等几个方面来进行考虑,下面是一些选取的原则。
6.1 网络的层数
理论已经证明,具有偏差和至少一个S型隐层加上一个线性输出层的网络,能够逼近任何有理函数,增加层数可以进一步降低误差,提高精度,但同时也是网络 复杂化。另外不能用仅具有非线性激活函数的单层网络来解决问题,因为能用单层网络解决的问题,用自适应线性网络也一定能解决,而且自适应线性网络的 运算速度更快,而对于只能用非线性函数解决的问题,单层精度又不够高,也只有增加层数才能达到期望的结果。
6.2 隐层神经元的个数
网络训练精度的提高,可以通过采用一个隐含层,而增加其神经元个数的方法来获得,这在结构实现上要比增加网络层数简单得多。一般而言,我们用精度和 训练网络的时间来恒量一个神经网络设计的好坏:
(1)神经元数太少时,网络不能很好的学习,训练迭代的次数也比较多,训练精度也不高。
(2)神经元数太多时,网络的功能越强大,精确度也更高,训练迭代的次数也大,可能会出现过拟合(over fitting)现象。
由此,我们得到神经网络隐层神经元个数的选取原则是:在能够解决问题的前提下,再加上一两个神经元,以加快误差下降速度即可。
6.3 初始权值的选取
一般初始权值是取值在(−1,1)之间的随机数。另外威得罗等人在分析了两层网络是如何对一个函数进行训练后,提出选择初始权值量级为s√r的策略, 其中r为输入个数,s为第一层神经元个数。
6.4 学习速率
学习速率一般选取为0.01−0.8,大的学习速率可能导致系统的不稳定,但小的学习速率导致收敛太慢,需要较长的训练时间。对于较复杂的网络, 在误差曲面的不同位置可能需要不同的学习速率,为了减少寻找学习速率的训练次数及时间,比较合适的方法是采用变化的自适应学习速率,使网络在 不同的阶段设置不同大小的学习速率。
6.5 期望误差的选取
在设计网络的过程中,期望误差值也应当通过对比训练后确定一个合适的值,这个合适的值是相对于所需要的隐层节点数来确定的。一般情况下,可以同时对两个不同 的期望误差值的网络进行训练,最后通过综合因素来确定其中一个网络。
7 BP网络的局限性
BP网络具有以下的几个问题:
(1)需要较长的训练时间:这主要是由于学习速率太小所造成的,可采用变化的或自适应的学习速率来加以改进。
(2)完全不能训练:这主要表现在网络的麻痹上,通常为了避免这种情况的产生,一是选取较小的初始权值,而是采用较小的学习速率。
(3)局部最小值:这里采用的梯度下降法可能收敛到局部最小值,采用多层网络或较多的神经元,有可能得到更好的结果。
8 BP网络的改进
P算法改进的主要目标是加快训练速度,避免陷入局部极小值等,常见的改进方法有带动量因子算法、自适应学习速率、变化的学习速率以及作用函数后缩法等。 动量因子法的基本思想是在反向传播的基础上,在每一个权值的变化上加上一项正比于前次权值变化的值,并根据反向传播法来产生新的权值变化。而自适应学习 速率的方法则是针对一些特定的问题的。改变学习速率的方法的原则是,若连续几次迭代中,若目标函数对某个权倒数的符号相同,则这个权的学习速率增加, 反之若符号相反则减小它的学习速率。而作用函数后缩法则是将作用函数进行平移,即加上一个常数。
三、部分源代码
% 清空环境变量clc;clear;close all;%% 样本数据生成jizhanid=load('anchorCfg.mat');data=load('area_sample_test.mat');location=zeros(499,83);location1={'A0000','A83F2','A8418','A8420','A841C'};[al,bl]=size(location1);for ii=1:499[shoudaogeshu,useless]=size(data.blink_frame(ii).anchor_array);for ii2=1:shoudaogeshufor kk=1:82if strcmp(jizhanid.anchorCfg{kk,1},data.blink_frame(ii).anchor_array{ii2, 1}.id)location(ii,kk)=data.blink_frame(ii).anchor_array{ii2, 1}.csi(2);endendendfor ii3=1:blif strcmp(location1(ii3),data.detected_area{ii, 1})location(ii,83)=ii3;endendendrowrank = randperm(size(location, 1)); % 随机打乱行locationend = location(rowrank, :);%%按照rowrank打乱矩阵的行数[a22,b22]=size(locationend);for i=1:a22 %二值化for j=1:b22-1if locationend(i,j)~=0locationend(i,j)=1;endendend%% BP算法%输入数据data=locationend;%训练预测数据data_train=data(1:220,1:83);data_test=data(221:499,1:83);input_train=data_train(:,1:82)';output_train=data_train(:,83)';input_test=data_test(:,1:82)';output_test=data_test(:,83)';%数据归一化[inputn,mininput,maxinput,outputn,minoutput,maxoutput]=premnmx(input_train,output_train); %对p和t进行字标准化预处理 net=newff(minmax(inputn),[10,1],{'tansig','purelin'},'trainlm');net.trainParam.epochs=1000;net.trainParam.lr=0.1;net.trainParam.goal=0.001;net.trainParam.show=200;%网络训练net=train(net,inputn,outputn);%数据归一化inputn_test = tramnmx(input_test,mininput,maxinput);an=sim(net,inputn_test);test_simu=postmnmx(an,minoutput,maxoutput);Yn=test_simu;Yn=round(Yn); figure %绘图plot(Yn,'r*-')%绘制预测值曲线hold on %继续绘图plot(output_test,'bo-') %实际值曲线legend('BP预测值','实际值')%图例wucha1=ones(1,79); %BP时预测误差for ii1=1:79wucha1(ii1)=(Yn(ii1)-output_test(ii1));endfigureplot(wucha1,'b^-')% %% GABP算法% %% 网络结构建立% %读取数据% data=locationend;% % %节点个数% inputnum=10;% hiddennum=65;% outputnum=1;% data_train=data(1:420,1:83);% data_test=data(421:499,1:83);% % input_train=data_train(:,1:82)';% output_train=data_train(:,83)';% % input_test=data_test(:,1:82)';% output_test=data_test(:,83)';%% % %% 遗传算法参数初始化% maxgen=10;%进化代数,即迭代次数% sizepop=6; %种群规模% pcross=[0.3]; %交叉概率选择,0和1之间% pmutation=[0.1];%变异概率选择,0和1之间% % %节点总数% numsum=inputnum*hiddennum+hiddennum+hiddennum*outputnum+outputnum;% % lenchrom=ones(1,numsum); % bound=[-3*ones(numsum,1) 3*ones(numsum,1)]; %数据范围% % %------------------------------------------------------种群初始化--------------------------------------------------------% individuals=struct('fitness',zeros(1,sizepop), 'chrom',[]); %将种群信息定义为一个结构体% avgfitness=[]; %每一代种群的平均适应度% bestfitness=[]; %每一代种群的最佳适应度% bestchrom=[]; %适应度最好的染色体% %初始化种群% for i=1:sizepop%%随机产生一个种群%individuals.chrom(i,:)=Code(lenchrom,bound); %编码(binary和grey的编码结果为一个实数,float的编码结果为一个实数向量)%x=individuals.chrom(i,:);%%计算适应度%individuals.fitness(i)=fun(x,inputnum,hiddennum,outputnum,net,inputn,outputn); %染色体的适应度% end% % %找最好的染色体% [bestfitness, bestindex]=min(individuals.fitness);% bestchrom=individuals.chrom(bestindex,:); %最好的染色体% avgfitness=sum(individuals.fitness)/sizepop; %染色体的平均适应度% % 记录每一代进化中最好的适应度和平均适应度% trace=[avgfitness bestfitness]; % % %% 迭代求解最佳初始阀值和权值% % 进化开始% for i=1:maxgen%%% 选择%individuals=Select(individuals,sizepop); %avgfitness=sum(individuals.fitness)/sizepop;%%交叉%individuals.chrom=Cross(pcross,lenchrom,individuals.chrom,sizepop,bound);%% 变异%individuals.chrom=Mutation(pmutation,lenchrom,individuals.chrom,sizepop,i,maxgen,bound);%%% 计算适应度 %for j=1:sizepop% x=individuals.chrom(j,:); %解码% individuals.fitness(j)=fun(x,inputnum,hiddennum,outputnum,net,inputn,outputn); %end%% %找到最小和最大适应度的染色体及它们在种群中的位置%[newbestfitness,newbestindex]=min(individuals.fitness);%[worestfitness,worestindex]=max(individuals.fitness);%% 代替上一次进化中最好的染色体%if bestfitness>newbestfitness% bestfitness=newbestfitness;% bestchrom=individuals.chrom(newbestindex,:);%end%individuals.chrom(worestindex,:)=bestchrom;%individuals.fitness(worestindex)=bestfitness;%%avgfitness=sum(individuals.fitness)/sizepop;%%trace=[trace;avgfitness bestfitness]; %记录每一代进化中最好的适应度和平均适应度% % end% %% 遗传算法结果分析 % figure% [r, c]=size(trace);% plot([1:r]',trace(:,2),'b--');% title(['适应度曲线 ' '终止代数=' num2str(maxgen)]);% xlabel('进化代数');ylabel('适应度');% legend('平均适应度','最佳适应度');% x=bestchrom;% % %% 把最优初始阀值权值赋予网络预测% % %用遗传算法优化的BP网络进行值预测% w1=x(1:inputnum*hiddennum);% B1=x(inputnum*hiddennum+1:inputnum*hiddennum+hiddennum);% % % net.iw{1,1}=reshape(w1,hiddennum,inputnum);% net.lw{2,1}=reshape(w2,outputnum,hiddennum);% net.b{1}=reshape(B1,hiddennum,1);% net.b{2}=B2;% % %% BP网络训练% %网络进化参数% net.trainParam.epochs=3000;% net.trainParam.lr=0.1;% net.trainParam.goal=0.001;% % %网络训练% [net,per2]=train(net,inputn,outputn);% % %% BP网络预测% %数据归一化% inputn_test2=mapminmax('apply',input_test,inputps);% an2=sim(net,inputn_test2);% test_simu2=mapminmax('reverse',an2,outputps);% % % Yn2=test_simu2; % Yn2=round(Yn2);% figure %绘图% plot(Yn2,'r*-')%绘制预测值曲线% hold on %继续绘图% plot(output_test,'bo-') %实际值曲线% legend('GABP预测值','实际值')%图例% wucha2=ones(1,79); %GABP时预测误差% for ii1=1:79%wucha2(ii1)=((Yn2(ii1)-output_test(ii1))/output_test(ii1));% end% figure% plot(wucha2,'r*--')% %% 画对比图% figure %绘图% plot(Yn,'r*-')%绘制预测值曲线% hold on %继续绘图% plot(Yn2,'g^--')%绘制预测值曲线% hold on % plot(output_test,'bo-') %实际值曲线% legend('BP预测值','GABP预测值','实际值')%图例% figure% plot(wucha1,'b^-')% hold on% plot(wucha2,'r*--')% legend('BP预测误差','GABP预测误差')%图例% % %% 数据存储% % fid=fopen('shuchu.txt','w');% % fprintf(fid,'%g\t',Yn);% % fprintf(fid,'%g\t',Yn2);% % fprintf(fid,'%g\t',wucha1);% % fprintf(fid,'%g\t',wucha2);% % fclose(fid);
四、运行结果
五、matlab版本及参考文献
1 matlab版本
a
2 参考文献
[1] 包子阳,余继周,杨杉.智能优化算法及其MATLAB实例(第2版)[M].电子工业出版社,.
[2]张岩,吴水根.MATLAB优化算法源代码[M].清华大学出版社,.
[3]周品.MATLAB 神经网络设计与应用[M].清华大学出版社,.
[4]陈明.MATLAB神经网络原理与实例精解[M].清华大学出版社,.
[5]方清城.MATLAB Ra神经网络设计与应用28个案例分析[M].清华大学出版社,.