精华内容
下载资源
问答
  • 遗传算法原理及算法实例

    万次阅读 多人点赞 2017-11-26 09:42:19
    遗传算法原理解析 遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。 借鉴生物进化理论,遗传...

    遗传算法原理解析

    遗传算法(GA)是一种元启发式自然选择的过程,属于进化算法(EA)大类。遗传算法通常是利用生物启发算子,如变异、交叉和选择来生成高质量的优化和搜索问题的解决方案。

    借鉴生物进化理论,遗传算法将问题模拟成一个生物进化过程,通过遗传、交叉、突变、自然选择等操作产生下一代的解,并逐步淘汰适应度函数值低的解,增加适应度函数高的解。这样进化N代后就很有可能会进化出适应度函数值很高的个体。

    与遗传算法有关的生物学概念:

    (1)染色体(chromosome)
    生物是由细胞组成,每一个细胞中都有一套相同的染色体。一条染色体由若干基因(gene) 组成,每个基因控制一种特定的蛋白质,从而决定生物的某种特征。所有染色体合称为基因组(genome)。基因组完全决定了一个生物个体。该个体在微观(基因)层次的表现称为基因型 (genotype),在宏观(特征)层次的表现称为显型 (phenotype)。在简单的遗传算法中,将基因组中的若干条染色体看作一整条染色体。
    (2) 个体复制
    在复制的过程中,父母的染色体通过交叉(crossover)产生子女的染色体。染色体还可以以一定的小概率变异(mutate)。

    遗传算法本质上是一种搜索算法,搜索算法的共同特征为:

    1. 首先组成一组候选解
    2. 依据某些适应性条件测算这些候选解的适应度
    3. 根据适应度保留某些候选解,放弃其他候选解
    4. 对保留的候选解进行某些操作,生成新的候选解

      
    交叉(Crossover):2条染色体交换部分基因,来构造下一代的2条新的染色体。
    交叉前:
    00000|011100000000|10000
    11100|000001111110|00101
    交叉后:
    00000|000001111110|10000
    11100|011100000000|00101
    染色体交叉是以一定的概率发生的,这个概率记为Pc 。
    变异(Mutation):在繁殖过程,新产生的染色体中的基因会以一定的概率出错,称为变异。变异发生的概率记为Pm 。
    变异前:
    000001110000000010000
    变异后:
    000001110000100010000
    适应度函数 ( Fitness Function ):用于评价某个染色体的适应度,用f(x)表示。有时需要区分染色体的适应度函数与问题的目标函数。例如:0-1背包问题的目标函数是所取得物品价值,但将物品价值作为染色体的适应度函数可能并不一定适合。适应度函数与目标函数是正相关的,可对目标函数作一些变形来得到适应度函数。

    遗传算法伪代码

    基本遗传算法伪代码
    /*
    * Pc:交叉发生的概率
    * Pm:变异发生的概率
    * M:种群规模
    * G:终止进化的代数
    * Tf:进化产生的任何一个个体的适应度函数超过Tf,则可以终止进化过程
    */
    初始化Pm,Pc,M,G,Tf等参数。随机产生第一代种群Pop
     
    do
    { 
      计算种群Pop中每一个体的适应度F(i)。
      初始化空种群newPop
      do
      {
        根据适应度以比例选择算法从种群Pop中选出2个个体
        if ( random ( 0 , 1 ) < Pc )
        {
          对2个个体按交叉概率Pc执行交叉操作
        }
        if ( random ( 0 , 1 ) < Pm )
        {
          对2个个体按变异概率Pm执行变异操作
        }
    将2个新个体加入种群newPop中
    } until ( M个子代被创建 )
    用newPop取代Pop
    }until ( 任何染色体得分超过Tf, 或繁殖代数超过G )

    遗传算法优化方法:

    (1)精英主义(Elitist Strategy)选择:是基本遗传算法的一种优化。为了防止进化过程中产生的最优解被交叉和变异所破坏,可以将每一代中的最优解原封不动的复制到下一代中。
    (2)插入操作:可在3个基本操作的基础上增加一个插入操作。插入操作将染色体中的某个随机的片段移位到另一个随机的位置。

    遗传算法实例

    这里选用参考3中的实例:计算函数

    的最小值,其中每个变量的取值区间都是[-1, +1]。

    首先,确定适应度的函数:

    function y = my_fitness(population)
    % population是随机数[0,1]矩阵,下面的操作改变范围为[-1,1]
    population = 2 * (population - 0.5); 
    y = sum(population.^2, 2); % 行的平方和
    遗传算法实现:
    function [best_fitness, elite, generation, last_generation] = my_ga( ...
        number_of_variables, ...    % 求解问题的参数个数
        fitness_function, ...       % 自定义适应度函数名
        population_size, ...        % 种群规模(每一代个体数目)
        parent_number, ...          % 每一代中保持不变的数目(除了变异)
        mutation_rate, ...          % 变异概率
        maximal_generation, ...     % 最大演化代数
        minimal_cost ...            % 最小目标值(函数值越小,则适应度越高)
    )
    
    % 累加概率
    % 假设 parent_number = 10
    % 分子 parent_number:-1:1 用于生成一个数列
    % 分母 sum(parent_number:-1:1) 是一个求和结果(一个数)
    % 分子 10     9     8     7     6     5     4     3     2     1
    % 分母 10+9+...+1=55
    % 相除 0.1818    0.1636    0.1455    0.1273    0.1091    0.0909    0.0727    0.0545    0.0364    0.0182
    % 累加(cumsum) 0.1818    0.3455    0.4909    0.6182    0.7273    0.8182    0.8909    0.9455    0.9818    1.0000
    % 运算结果可以看出: 累加概率函数是一个从0到1增长得越来越慢的函数
    cumulative_probabilities = cumsum((parent_number:-1:1) / sum(parent_number:-1:1)); % 1个长度为parent_number的数列
    best_fitness = ones(maximal_generation, 1);% 记录每一代最佳适应度,先初始化为1
    elite = zeros(maximal_generation, number_of_variables);% 记录每一代的最优解,初始化为0
    
    % 子女数量=种群数量 - 父母数量(父母即每一代中不发生改变的个体)
    child_number = population_size - parent_number; % 每一代子女的数目
    
    % population_size 对应矩阵的行,每一行表示1个个体,行数=个体数(种群数量)
    % number_of_variables 对应矩阵的列,列数=参数个数(个体特征由这些参数表示)
    population = rand(population_size, number_of_variables);% 初始化种群
    last_generation = 0; % 记录跳出循环时的代数
    
    for generation = 1 : maximal_generation % 演化循环开始
        
        % feval把数据带入到一个定义好的函数句柄中计算
        % 把population矩阵带入fitness_function函数计算
        cost = feval(fitness_function, population); % 计算所有个体的适应度(population_size*1的矩阵)
    
        % index记录排序后每个值原来的行数
        [cost, index] = sort(cost); % 将适应度函数值从小到大排序
    
        % index(1:parent_number) 
        % 前parent_number个cost较小的个体在种群population中的行数
        % 选出这部分(parent_number个)个体作为父母,其实parent_number对应交叉概率
        population = population(index(1:parent_number), :); % 先保留一部分较优的个体
        % population矩阵是不断变化的
        % cost在经过前面的sort排序后,矩阵已经改变为升序的
        % cost(1)即为本代的最佳适应度
        best_fitness(generation) = cost(1); % 记录本代的最佳适应度
    
        % population矩阵第一行为本代的最优解(精英)
        elite(generation, :) = population(1, :); % 记录本代的最优解(精英)
    
        % 若本代的最优解已足够好,则停止演化
        if best_fitness(generation) < minimal_cost; 
            last_generation = generation;
            break; 
        end
        
        % 交叉变异产生新的种群,染色体交叉开始
        for child = 1:2:child_number % 步长为2是因为每一次交叉会产生2个孩子
            
            % cumulative_probabilities 长度为 parent_number
            % 从中随机选择2个父母出来  (child+parent_number)
            mother = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的母亲
            father = find(cumulative_probabilities > rand, 1); % 选择一个较优秀的父亲
            
            % ceil:向上取整
            % rand 生成一个随机数
            % 即随机选择了一列,这一列的值交换
            crossover_point = ceil(rand*number_of_variables); % 随机地确定一个染色体交叉点
            
            % 假如crossover_point=3, number_of_variables=5
            % mask1 = 1     1     1     0     0
            % mask2 = 0     0     0     1     1
            mask1 = [ones(1, crossover_point), zeros(1, number_of_variables - crossover_point)];
            mask2 = not(mask1);
            
            % 获取分开的4段染色体
            mother_1 = mask1 .* population(mother, :); % 母亲染色体的前部分
            mother_2 = mask2 .* population(mother, :); % 母亲染色体的后部分
            
            father_1 = mask1 .* population(father, :); % 父亲染色体的前部分
            father_2 = mask2 .* population(father, :); % 父亲染色体的后部分
            
            % 得到下一代
            population(parent_number + child, :) = mother_1 + father_2; % 一个孩子
            population(parent_number+child+1, :) = mother_2 + father_1; % 另一个孩子
            
        end % 染色体交叉结束
        
        
        % 染色体变异开始,变异种群
        mutation_population = population(2:population_size, :); % 精英不参与变异,从2开始    
        number_of_elements = (population_size - 1) * number_of_variables; % 全部基因数目
        number_of_mutations = ceil(number_of_elements * mutation_rate); % 变异的基因数目(基因总数*变异率)
        
        % rand(1, number_of_mutations) 生成number_of_mutations个随机数(范围0-1)组成的矩阵(1*number_of_mutations)
        % 数乘后,矩阵每个元素表示发生改变的基因的位置(元素在矩阵中的一维坐标)
        mutation_points = ceil(number_of_elements * rand(1, number_of_mutations)); % 确定要变异的基因
        
        % 被选中的基因都被一个随机数替代,完成变异
        mutation_population(mutation_points) = rand(1, number_of_mutations); % 对选中的基因进行变异操作
        population(2:population_size, :) = mutation_population; % 发生变异之后的种群
        % 染色体变异结束
    end % 演化循环结束
    函数测试:
    clc,clear all,close all;
    
    % 调用 my_ga 进行计算
    % 求解问题的参数个数         10
    % 自定义适应度函数名         my_fitness
    % 种群规模                  100
    % 每一代中保持不变的数目     50 (即交叉率0.5)
    % 变异概率                  0.1 (1/10的个体发生变异)
    % 最大演化代数              10000 10000代
    % 最小目标值                1.0e-6 个体适应度函数值 < 0.000001结束
    [best_fitness, elite, generation, last_generation] = my_ga(10, 'my_fitness', 100, 50, 0.1, 10000, 1.0e-6);
    
    % 输出后10行
    disp(last_generation); 
    i_begin = last_generation - 9;
    disp(best_fitness(i_begin:last_generation,:));
    % disp(best_fitness(9990:10000,:));
    % disp(elite(9990:10000,:))
    % 不要写成这样,因为GA常常在中间就跳出循环了
    
    % 将elite值转化为问题范围内
    my_elite = elite(i_begin:last_generation,:);
    my_elite = 2 * (my_elite - 0.5);
    disp(my_elite);
    
    % 最佳适应度的演化情况
    figure
    loglog(1:generation, best_fitness(1:generation), 'linewidth',2)
    xlabel('Generation','fontsize',15);
    ylabel('Best Fitness','fontsize',15);
    set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);
    
    % 最优解的演化情况
    figure
    semilogx(1 : generation, 2 * elite(1 : generation, :) - 1)
    xlabel('Generation','fontsize',15);
    ylabel('Best Solution','fontsize',15);
    set(gca,'fontsize',15,'ticklength',get(gca,'ticklength')*2);
    

    参考:
    http://blog.jobbole.com/110913/
    http://blog.csdn.net/dazhong159/article/details/7908531

    http://blog.sciencenet.cn/blog-3102863-1029280.html

    https://github.com/Shuai-Xie/genetic-algorithm

    https://github.com/yanshengjia/artificial-intelligence/tree/master/genetic-algorithm-for-functional-maximum-problem/src


    展开全文
  • 遗传算法原理及应用实例

    热门讨论 2010-04-10 14:35:51
    遗传算法是一种用来解决需要搜索复杂解空间的问题的 启发式算法。它通常包含了一系列的参数。如交叉运算和变异运 算的参数,种群的大小以及不同的交叉和变异的算子等。随着这 些因素的不同,遗传算法的结构也在发生...
  • 遗传算法原理及应用详细地介绍了遗传算法的原理,并用实例进行了讲解,通俗易懂……
  • 在平时的研究之余,希望每天晚上闲下来的时候,都学习一个机器学习算法,今天看到几篇不错的遗传算法的文章,在这里总结一下。 1 神经网络基本原理 图1. 人工神经元模型 图中x1~xn是从其他神经元传来的...

      在平时的研究之余,希望每天晚上闲下来的时候,都学习一个机器学习算法,今天看到几篇不错的遗传算法的文章,在这里总结一下。

    1 神经网络基本原理

     

    图1. 人工神经元模型

     

           图中x1~xn是从其他神经元传来的输入信号,wij表示表示从神经元j到神经元i的连接权值,θ表示一个阈值 ( threshold ),或称为偏置( bias )。则神经元i的输出与输入的关系表示为:

     

      图中 yi表示神经元i的输出,函数f称为激活函数 ( Activation Function )或转移函数 ( Transfer Function ) ,net称为净激活(net activation)。若将阈值看成是神经元i的一个输入x0的权重wi0,则上面的式子可以简化为:

     

      若用X表示输入向量,用W表示权重向量,即:

    X = [ x0 , x1 , x2 , ....... , xn ]

     

      则神经元的输出可以表示为向量相乘的形式:

     

     

           若神经元的净激活net为正,称该神经元处于激活状态或兴奋状态(fire),若净激活net为负,则称神经元处于抑制状态。

           图1中的这种“阈值加权和”的神经元模型称为M-P模型 ( McCulloch-Pitts Model ),也称为神经网络的一个处理单元( PE, Processing Element )

    2. 常用激活函数 

           激活函数的选择是构建神经网络过程中的重要环节,下面简要介绍常用的激活函数。

    (1) 线性函数 ( Liner Function )

     

    (2) 斜面函数 ( Ramp Function )

     

    (3) 阈值函数 ( Threshold Function )

     

     

     

           以上3个激活函数都属于线性函数,下面介绍两个常用的非线性激活函数。

    (4) S形函数 ( Sigmoid Function )

      该函数的导函数:

    (5) 双极S形函数 

      该函数的导函数:

      S形函数与双极S形函数的图像如下:


    图3. S形函数与双极S形函数图像

      双极S形函数与S形函数主要区别在于函数的值域,双极S形函数值域是(-1,1),而S形函数值域是(0,1)。

      由于S形函数与双极S形函数都是可导的(导函数是连续函数),因此适合用在BP神经网络中。(BP算法要求激活函数可导)

    3. 神经网络模型 

           神经网络是由大量的神经元互联而构成的网络。根据网络中神经元的互联方式,常见网络结构主要可以分为下面3类:

    (1) 前馈神经网络 ( Feedforward Neural Networks )

           前馈网络也称前向网络。这种网络只在训练过程会有反馈信号,而在分类过程中数据只能向前传送,直到到达输出层,层间没有向后的反馈信号,因此被称为前馈网络。感知机( perceptron)与BP神经网络就属于前馈网络。

           图4 中是一个3层的前馈神经网络,其中第一层是输入单元,第二层称为隐含层,第三层称为输出层(输入单元不是神经元,因此图中有2层神经元)。

    图4. 前馈神经网络

     

      对于一个3层的前馈神经网络N,若用X表示网络的输入向量,W1~W3表示网络各层的连接权向量,F1~F3表示神经网络3层的激活函数。

      那么神经网络的第一层神经元的输出为:

    O1 = F1( XW1 )

      第二层的输出为:

    O2 = F2 ( F1( XW1 ) W2 )

      输出层的输出为:

    O3 = F3( F2 ( F1( XW1 ) W2 ) W3 )

           若激活函数F1~F3都选用线性函数,那么神经网络的输出O3将是输入X的线性函数。因此,若要做高次函数的逼近就应该选用适当的非线性函数作为激活函数。

    (2) 反馈神经网络 ( Feedback Neural Networks )

           反馈型神经网络是一种从输出到输入具有反馈连接的神经网络,其结构比前馈网络要复杂得多。典型的反馈型神经网络有:Elman网络和Hopfield网络。

    图5. 反馈神经网络

     

    (3) 自组织网络 ( SOM ,Self-Organizing Neural Networks )

           自组织神经网络是一种无导师学习网络。它通过自动寻找样本中的内在规律和本质属性,自组织、自适应地改变网络参数与结构。

    图6. 自组织网络

     

    4. 神经网络工作方式 

           神经网络运作过程分为学习和工作两种状态。

    (1)神经网络的学习状态 

           网络的学习主要是指使用学习算法来调整神经元间的联接权,使得网络输出更符合实际。学习算法分为有导师学习( Supervised Learning )无导师学习( Unsupervised Learning )两类。

           有导师学习算法将一组训练集 ( training set )送入网络,根据网络的实际输出与期望输出间的差别来调整连接权。有导师学习算法的主要步骤包括:

    1)  从样本集合中取一个样本(Ai,Bi);

    2)  计算网络的实际输出O;

    3)  求D=Bi-O;

    4)  根据D调整权矩阵W;

    5) 对每个样本重复上述过程,直到对整个样本集来说,误差不超过规定范围。

      BP算法就是一种出色的有导师学习算法。

           无导师学习抽取样本集合中蕴含的统计特性,并以神经元之间的联接权的形式存于网络中。

           Hebb学习律是一种经典的无导师学习算法。

    (2) 神经网络的工作状态 

           神经元间的连接权不变,神经网络作为分类器、预测器等使用。

      下面简要介绍一下Hebb学习率与Delta学习规则 。

    (3) 无导师学习算法:Hebb学习率 

       Hebb算法核心思想是,当两个神经元同时处于激发状态时两者间的连接权会被加强,否则被减弱。 

           为了理解Hebb算法,有必要简单介绍一下条件反射实验。巴甫洛夫的条件反射实验:每次给狗喂食前都先响铃,时间一长,狗就会将铃声和食物联系起来。以后如果响铃但是不给食物,狗也会流口水。

     

      受该实验的启发,Hebb的理论认为在同一时间被激发的神经元间的联系会被强 化。比如,铃声响时一个神经元被激发,在同一时间食物的出现会激发附近的另一个神经元,那么这两个神经元间的联系就会强化,从而记住这两个事物之间存在着 联系。相反,如果两个神经元总是不能同步激发,那么它们间的联系将会越来越弱。

      Hebb学习律可表示为:

           其中wij表示神经元j到神经元i的连接权,yi与yj为两个神经元的输出,a是表示学习速度的常数。若yi与yj同时被激活,即yi与yj同时为正,那么Wij将增大。若yi被激活,而yj处于抑制状态,即yi为正yj为负,那么Wij将变小。

    (4) 有导师学习算法:Delta学习规则

      Delta学习规则是一种简单的有导师学习算法,该算法根据神经元的实际输出与期望输出差别来调整连接权,其数学表示如下:

     

           其中Wij表示神经元j到神经元i的连接权,di是神经元i的期望输出,yi是神经元i的实际输出,xj表示神经元j状态,若神经元j处于激活态则xj为 1,若处于抑制状态则xj为0或-1(根据激活函数而定)。a是表示学习速度的常数。假设xi为1,若di比yi大,那么Wij将增大,若di比yi小, 那么Wij将变小。

           Delta规则简单讲来就是:若神经元实际输出比期望输出大,则减小所有输入为正的连接的权重,增大所有输入为负的连接的权重。反之,若神经元实际输出比 期望输出小,则增大所有输入为正的连接的权重,减小所有输入为负的连接的权重。这个增大或减小的幅度就根据上面的式子来计算。

    (5)有导师学习算法:BP算法 

      采用BP学习算法的前馈型神经网络通常被称为BP网络。

    图8. 三层BP神经网络结构

     

      BP网络具有很强的非线性映射能力,一个3层BP神经网络能够实现对任意非线性函数进行逼近(根据Kolrnogorov定理)。一个典型的3层BP神经网络模型如图7所示。

      BP网络的学习算法占篇幅较大,我打算在下一篇文章中介绍。

     

    5 实例

      Hebb学习规则代表一种纯向前的非监督学习。这里用一个简单的例子来说明具有简单网络的二进制和连续激活函数的Hebb学习情况。如图:

           D.D.Hebb学习规则举例——神经网络的训练算法
      假定具有以下初始权向量的网络如上图所示。
      初始权向量   W1 = [1, -1, 0, 0.5]T
     
      输入  X = [x1, x2, x3, x4]T
      训练集用以下三个输入向量  X1 = [1, -2, 1.5, 0]T  ; X2 = [1, -0.5, -2, -1.5]T  ; X3 = [0, 1, -1, 1.5]T
     

      学习常数在这里则设为 η = 1。因为初始权重具有非零值,这意味着这个网络事先已经明显受过训练。这里我们采用双机二进制神经元,

      那么 f(net) = sgn(net)。

      学习过程有以下步骤:

      第一步 加到网络的输入X1产生如下的net

          net1 = (W1)TX1 = [1, -1, 0, 0.5]*[1, -2, 1.5, 0]T  = 3

        更新的权是

          W2 = W1 + sgn(net1)X1 = W1 + X1 = [1, -1, 0, 0.5]T + [1, -2, 1.5, 0]T = [2, -3, 1.5, 0.5]T

        其中在表达式右边的下标表示当前调节步数。

     

      第二步 这次学习使用X2作输入,重复第一步的步骤  W3 = [1, -2.5, 3.5, 2]

     

      第三步 这次学习使用X3作输入,重复第一步的步骤  W4 = [1, -3.5, 4.5, 0.5]

      由上可见,具有离散f(net)和η = 1的学习分别产生加整个输入模式向量到权向量中或者从权中减去整个输入模式向量。在连续f(net)的情况,权增加/减少向量按比例缩小到输入模式的分数值。

     

      下面看一个具有连续双极激活函数f(net),用输入X1和初始权W1的Hebb学习例子。

      同在第一步概况那样,我们得到神经元输出值和对于 λ=1 更新权,和以前的情况比较,不同的是f(net), 现在的激活函数如下式f(net) = 2/[1+exp(-λ*net)] - 1

      通过计算可得

        f(net1) = 0.905   f(net2) = -0.077 f(net3) = -0.932

        W2 = [1.905, -2.81, 1.357, 0.5]T   W3 = [1.828, -2.772, 1.512, 0.616]T         W4 = [1.828, -3.70, 2.44, -0.783]T

      通过对比离散的和连续的激活函数,可见 对于连续的激活函数,权调节成锥形,但是一般是在同一方向上的。

     

     

     文章来自  http://www.cnblogs.com/heaad/archive/2011/03/07/1976443.html

     

    转载于:https://www.cnblogs.com/rongyux/p/5392837.html

    展开全文
  • 包含了遗传算法、模拟褪火算法、免疫算法、神经网络、粒子群算法、蜂群算法等7种算法,详细的PDF文档原理介绍matlab源码实例
  • 遗传算法实例解析

    2020-07-22 23:08:13
    遗传算法实例及MATLAB程序解析 遗传算法Genetic Algorithms,GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目标的优化。遗传算法的实质是...

    遗传算法实例及MATLAB程序解析

           遗传算法Genetic Algorithms,GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目标的优化。遗传算法的实质是通过群体搜索技术,根据适者生存的原则逐代进化,最终得到最优解或准最优解。它必须做以下操作∶初始群体的产生、求每一个体的适应度、根据适者生存的原则选择优良个体、被选出的优良个体两两配对,通过随机交叉其染色体的基因并随机变异某些染色体的基因生 成下一代群体,按此方法使群体逐代进化,直到满足进化终止条件。其实现方法如下∶

    (1)根据具体问题确定可行解域,确定一种编码方法,能用数值串或字符串表示可行解域的每一解。
    (2)对每一解应有一个度量好坏的依据,它用一函数表示,叫做适应度函数,一般由目标函数构成。
    (3)确定进化参数群体规模M、交叉概率 Pc、变异概率Pm、进化终止条件。为便于计算,一般来说,每一代群体的个体数目都取相等。群体规模越大,越容易找到最优解,但由于受到计算机的运算能力的限制,群体规模越大,计算所需要的时间也相应地增加。进化终止条件指的是当进化到什么时候结束,它可以设定到某一代进化结束,也可以根据找出近似最优解是否满足精度要求来确定。

    实例解析

    已知100个目标的经纬度信息如下(第一列为经度,第二例为纬度,以此类推):

    53.7121   15.3046	51.1758    0.0322	46.3253   28.2753	30.3313    6.9348
    56.5432   21.4188	10.8198   16.2529	22.7891   23.1045	10.1584   12.4819
    20.1050   15.4562	1.9451    0.2057	26.4951   22.1221	31.4847    8.9640
    26.2418   18.1760	44.0356   13.5401	28.9836   25.9879	38.4722   20.1731
    28.2694   29.0011	32.1910    5.8699	36.4863   29.7284	0.9718   28.1477
    8.9586   24.6635	16.5618   23.6143	10.5597   15.1178	50.2111   10.2944
    8.1519    9.5325	22.1075   18.5569	0.1215   18.8726	48.2077   16.8889
    31.9499   17.6309	0.7732    0.4656	47.4134   23.7783	41.8671    3.5667
    43.5474    3.9061	53.3524   26.7256	30.8165   13.4595	27.7133    5.0706
    23.9222    7.6306	51.9612   22.8511	12.7938   15.7307	4.9568    8.3669
    21.5051   24.0909	15.2548   27.2111	6.2070    5.1442	49.2430   16.7044
    17.1168   20.0354	34.1688   22.7571	9.4402    3.9200	11.5812   14.5677
    52.1181    0.4088	9.5559   11.4219	24.4509    6.5634	26.7213   28.5667
    37.5848   16.8474	35.6619    9.9333	24.4654    3.1644	0.7775    6.9576
    14.4703   13.6368	19.8660   15.1224	3.1616    4.2428	18.5245   14.3598
    58.6849   27.1485	39.5168   16.9371	56.5089   13.7090	52.5211   15.7957
    38.4300    8.4648	51.8181   23.0159	8.9983   23.6440	50.1156   23.7816
    13.7909    1.9510	34.0574   23.3960	23.0624    8.4319	19.9857    5.7902
    40.8801   14.2978	58.8289   14.5229	18.6635    6.7436	52.8423   27.2880
    39.9494   29.5114	47.5099   24.0664	10.1121   27.2662	28.7812   27.6659
    8.0831   27.6705	9.1556   14.1304	53.7989    0.2199	33.6490    0.3980
    1.3496   16.8359	49.9816    6.0828	19.3635   17.6622	36.9545   23.0265
    15.7320   19.5697	11.5118   17.3884	44.0398   16.2635	39.7139   28.4203
    6.9909   23.1804	38.3392   19.9950	24.6543   19.6057	36.9980   24.3992
    4.1591    3.1853	40.1400   20.3030	23.9876    9.4030	41.1084   27.7149
    

           我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为1000km/h。我方派一架飞机从基地出发,侦察完所有目标,再返回原来的基地。在每一目标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。
            这是一个旅行商问题。给我方基地编号为1,目标依次编号为2,,…,101,最后我方基地再重复编号为102(这样便于程序中计算)。距离矩阵D=(dij)102×102D=(d_{ij})_{102\times102},其中dijd_{ij}表示i,j两点的距离,i、j=1,2,…,102,这里DD为实对称矩阵。则问题是求一个从点1出发,走遍所有中间点,到达点102的一个最短路径。
           上面问题中给定的是地理坐标(经度和纬度),必须求两点间的实际距离。设A,B两点的地理坐标分别为x1y1x2y2(x_{1},y_{1}),(x_{2},y_{2})过A,B两点的大圆的劣弧长即为两点的实际距离。以地心为坐标原点OO,以赤道平面为XOYXOY平面,以0度经线圈所在的平面为XOZXOZ平面建立三维直角坐标系。则A,B两点的直角坐标分别为:

    A(Rcosx1cosy1,Rsinx1cosy1,Rsiny1),A(Rcosx_{1}cosy_{1},Rsinx_{1}cosy_{1},Rsiny_{1}), B(Rcosx2cosy2,Rsinx2cosy2,Rsiny2),B(Rcosx_{2}cosy_{2},Rsinx_{2}cosy_{2},Rsiny_{2}),

    式中∶R=6370为地球半径。
    
A,B两点的实际距离:
    d=Rarccos(OAOBOAOB),d=Rarccos(\frac{OA \cdot OB}{|OA| \cdot |OB|}),

    用MATLAB求解程序如下:

    %遗传算法
    clc,clear
    sj0=load('sj.txt');       %加载100个目标的数据
    x=sj0(:,1:2:8); x=x(:);   %取经度
    y=sj0(:,2:2:8); y=y(:);   %取纬度
    sj=[x y]; d1=[70,40];     %基地经纬度(70,40)
    sj=[d1;sj;d1]; sj=sj*pi/180;  %单位化成弧度
    d=zeros(102); %距离矩阵d的初始值 100个目标+两次经过起点
    
    for i=1:101    %计算相邻两点间距离,注意飞机飞行轨迹为弧
      for j=i+1:102
      d(i,j)=6370*acos(cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2))); 
      end
    end
    
    d=d+d';                    %d为一个实对称矩阵,表示两点间的双向距离
    w=50; g=100;               %w为种群的个数,g为进化的代数
    rand('state',sum(clock));  %初始化随机数发生器
    
    for k=1:w                  %通过改良圈算法选取初始种群
        c=randperm(100);       %产生1...100的一个随机排列  
        c1=[1,c+1,102];        %生成初始解
        for t=1:102            %该层循环是修改圈 
            flag=0;            %修改圈退出标志
        for m=1:100
          for n=m+2:101
            if d(c1(m),c1(n))+d(c1(m+1),c1(n+1))<d(c1(m),c1(m+1))+d(c1(n),c1(n+1))
               c1(m+1:n)=c1(n:-1:m+1);  flag=1; %修改圈
            end
          end
        end
       if flag==0
          J(k,c1)=1:102; break %记录下较好的解并退出当前层循环
       end
       end
    end
    
    J(:,1)=0; J=J/102;   %把整数序列转换成[0,1]区间上的实数,即转换成染色体编码
    for k=1:g            %该层循环进行遗传算法的操作 
        A=J;             %交配产生子代B的初始染色体
        c=randperm(w);   %产生下面交叉操作的染色体对 
        for i=1:2:w  
            F=2+floor(100*rand(1));   %产生交叉操作的地址
            temp=A(c(i),[F:102]);     %中间变量的保存值
            A(c(i),[F:102])=A(c(i+1),[F:102]); %交叉操作
            A(c(i+1),F:102)=temp;  
        end
        by=[];                  %为了防止下面产生空地址,这里先初始化
    while ~length(by)
        by=find(rand(1,w)<0.1); %产生变异操作的地址
    end
    B=A(by,:);                 %产生变异操作的初始染色体
    for j=1:length(by)
       bw=sort(2+floor(100*rand(1,3)));  %产生变异操作的3个地址
       B(j,:)=B(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]); %交换位置
    end
       G=[J;A;B];           %父代和子代种群合在一起
       [SG,ind1]=sort(G,2); %把染色体翻译成1...,102的序列ind1
       num=size(G,1); long=zeros(1,num); %路径长度的初始值
       for j=1:num
           for i=1:101
               long(j)=long(j)+d(ind1(j,i),ind1(j,i+1)); %计算每条路径长度
           end
       end
         [slong,ind2]=sort(long); %对路径长度按照从小到大排序
         J=G(ind2(1:w),:);       %精选前w个较短的路径对应的染色体
    end
    path=ind1(ind2(1),:), flong=slong(1)  %解的路径及路径长度
    xx=sj(path,1);yy=sj(path,2);
    plot(xx,yy,'-V')                       %画出路径
    
    

    运行结果如下:

    path =
    
      1281    17     3    45    67     2    92    87    83    82    48    72    14    27    10    84    18    40    20    30    74    42    15     9     5    60    79    77
    
      295631    97    85    65    64    11    76    69    94    70    19    63    62    26    29    34    66    90    86     8    39    78    47    23    58    81    25    68
    
      57847    22    71    37    32    13    24    61    49    28    57    88    16    91    41     4    73    33    75    54    53    12    89     6    96    55    44    38
    
      8510250    80    51    98   100    56    21    99   101    52    46    59    93    43    36    35    95   102
    
    
    flong =
    
       4.0096e+04
    

    在这里插入图片描述注:这是我用Markdown写的第一篇文章,之中难免有所纰漏,还望指出.

    展开全文
  • 详解遗传算法(含MATLAB代码)

    万次阅读 多人点赞 2019-05-29 11:30:47
    三、遗传算法的基本流程实现技术 3.1 遗传算法的基本流程 3.2 遗传算法的实现技术 1.编码 2.适应度函数 3.选择算子 4.交叉算子 5.变异算子 6.运行参数 四、遗传算法的基本原理 4.1 模式定理 4.2 积木块...

    目录

    一、遗传算法概述

    二、遗传算法的特点和应用

    三、遗传算法的基本流程及实现技术

    3.1 遗传算法的基本流程

    3.2 遗传算法的实现技术

    1.编码

    2.适应度函数

    3.选择算子

    4.交叉算子

    5.变异算子

    6.运行参数

    四、遗传算法的基本原理

    4.1 模式定理

    4.2 积木块假设

    五、遗传算法编程实例(MATLAB)


    一、遗传算法概述

            遗传算法(Genetic Algorithm,GA)是进化计算的一部分,是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型,是一种通过模拟自然进化过程搜索最优解的方法。该算法简单、通用,鲁棒性强,适于并行处理。

    二、遗传算法的特点和应用

       遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法,与传统的优化算法相比,具有以下特点:

    1. 以决策变量的编码作为运算对象。

        传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算,但遗传算法是使用决策变量的某种形式的编码作为运算对象。这种对决策变量的编码处理方式,使得我们在优化计算中可借鉴生物学中染色体和基因等概念,可以模仿自然界中生物的遗传和进化激励,也可以很方便地应用遗传操作算子。

    2. 直接以适应度作为搜索信息。

        传统的优化算法不仅需要利用目标函数值,而且搜索过程往往受目标函数的连续性约束,有可能还需要满足“目标函数的导数必须存在”的要求以确定搜索方向。

        遗传算法仅使用由目标函数值变换来的适应度函数值就可确定进一步的搜索范围,无需目标函数的导数值等其他辅助信息。直接利用目标函数值或个体适应度值也可以将搜索范围集中到适应度较高部分的搜索空间中,从而提高搜索效率。

    3. 使用多个点的搜索信息,具有隐含并行性

        传统的优化算法往往是从解空间的一个初始点开始最优解的迭代搜索过程。单个点所提供的搜索信息不多,所以搜索效率不高,还有可能陷入局部最优解而停滞;

        遗传算法从由很多个体组成的初始种群开始最优解的搜索过程,而不是从单个个体开始搜索。对初始群体进行的、选择、交叉、变异等运算,产生出新一代群体,其中包括了许多群体信息。这些信息可以避免搜索一些不必要的点,从而避免陷入局部最优,逐步逼近全局最优解。

    4. 使用概率搜索而非确定性规则。

       传统的优化算法往往使用确定性的搜索方法,一个搜索点到另一个搜索点的转移有确定的转移方向和转移关系,这种确定性可能使得搜索达不到最优店,限制了算法的应用范围。

       遗传算法是一种自适应搜索技术,其选择、交叉、变异等运算都是以一种概率方式进行的,增加了搜索过程的灵活性,而且能以较大概率收敛于最优解,具有较好的全局优化求解能力。但,交叉概率、变异概率等参数也会影响算法的搜索结果和搜索效率,所以如何选择遗传算法的参数在其应用中是一个比较重要的问题

    综上,由于遗传算法的整体搜索策略和优化搜索方式在计算时不依赖于梯度信息或其他辅助知识,只需要求解影响搜索方向的目标函数和相应的适应度函数,所以遗传算法提供了一种求解复杂系统问题的通用框架。它不依赖于问题的具体领域,对问题的种类有很强的鲁棒性,所以广泛应用于各种领域,包括:

    • 函数优化
    • 组合优化生产调度问题
    • 自动控制
    • 机器人学
    • 图像处理(图像恢复、图像边缘特征提取......)
    • 人工生命
    • 遗传编程
    • 机器学习

    三、遗传算法的基本流程及实现技术

       基本遗传算法(Simple Genetic Algorithms,SGA)只使用选择算子、交叉算子和变异算子这三种遗传算子,进化过程简单,是其他遗传算法的基础。

    3.1 遗传算法的基本流程

    1.  通过随机方式产生若干由确定长度(长度与待求解问题的精度有关)编码的初始群体;
    2. 通过适应度函数对每个个体进行评价,选择适应度值高的个体参与遗传操作,适应度低的个体被淘汰;
    3. 经遗传操作(复制、交叉、变异)的个体集合形成新一代种群,直到满足停止准则(进化代数GEN>=?);
    4. 将后代中变现最好的个体作为遗传算法的执行结果。

                                                       

    其中,GEN是当前代数;M是种群规模,i代表种群数量。

    3.2 遗传算法的实现技术

    基本遗传算法(SGA)由编码、适应度函数、遗传算子(选择、交叉、变异)及运行参数组成。

    1.编码

    (1)二进制编码

    二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。

    优点:编、解码操作简单,遗传、交叉便于实现

    缺点:长度大

    (2)其他编码方法

    格雷码、浮点数编码、符号编码、多参数编码等

    2.适应度函数

    适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。

    3.选择算子

    通过选择算子模拟“优胜劣汰”,适应度高的个体被遗传到下一代的概率较大,适应度低的算子被遗传到下一代的概率较小。

    常用的选择算法:轮盘赌选择法,即令\sum f_i表示群体的适应度函数值的总和,f_i表示群体中第i个染色体的适应度值,则它产生后代的能力刚好为其适应度值所占的份额\frac{f_i}{\sum f_i}

    4.交叉算子

    • 交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因,从而形成两个新的个体;
    • 交叉运算是遗传算法区别于其他进化算法的重要特征,是产生新个体的主要方法。

    在交叉之前需要将群体中的个体进行配对,一般采取随机配对原则。

    常用的交叉方式:

    • 单点交叉
    • 双点交叉(多点交叉,交叉点数越多,个体的结构被破坏的可能性越大,一般不采用多点交叉的方式)
    • 均匀交叉
    • 算术交叉

    5.变异算子

    遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换,从而形成一个新的个体。

    就遗传算法运算过程中产生新个体的能力方面来说,交叉运算是产生新个体的主要方法,它决定了遗传算法的全局搜索能力;而变异运算只是产生新个体的辅助方法,但也是必不可少的一个运算步骤,它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索,从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。

    6.运行参数

    • 编码长度。编码长度取决于问题解的精度,精度越高,编码越长;
    • 种群规模。规模小,收敛快但降低了种群的多样性,N=20-200
    • 交叉概率。较大的交叉概率容易破坏种群中已形成的优良结构,使搜索具有太大随机性;较小的交叉概率发现新个体的速度太慢,一般取值为P_c=0.4-0.99
    • 变异概率。变异概率太小,则变异操作产生新个体的能力和抑制早熟现象的能力会较差;变异概率过高随机性过大,一般建议取值范围为0.005~0.01
    • 终止进化代数。算法运行结束的条件之一,一般取100~1000

    四、遗传算法的基本原理

    4.1 模式定理

    定义1:模式H是由{0,1,*}中的元素组成的一个编码串,其中“*”表示通配符,既能被当作0,也能被当作1。e.g. H=10**1

    定义2:模式的阶,是指模式中所含有0,1的数量,记作O(H)  e.g. O(11*00**)=4

    定义3:模式的矩,即模式的长度,是指模式中从左到右第一个非*位和最后一个非*位之间的距离,记作\delta (H)

              e.g. \delta (01**1)=3;\delta (**0*1)=2;\delta (***1**)=1

    定义4:模式的适应度值,是群体中所包含的全部个体的适应度值的平均值。

    定义5:在选择、交叉、变异遗传算子的作用下,低阶、长度短、超过群体平均适应值的模式的生存数量,将随迭代次数以指数规律增长。

    模式定理不仅说明基因块的样本呈指数增长,也说明用遗传算法寻求最优样本的可能性,但它并未指出遗传算法一定能够寻求到最优解,积木块假设说明了遗传算法的寻找最优解的能力。

    4.2 积木块假设

    具有低阶、定义长度短,且适应度值高于群体平均适应度值的模式称为基因块或积木块。

    积木块假设:个体的基因块通过选择、交叉、变异等遗传算子的作用,能够相互拼接在一起,形成适应度更高的个体编码串。

    积木块假设说明了用遗传算法求解各类问题的基本思想,即通过积木块直接相互拼接在一起能够产生更好的解。

    五、遗传算法编程实例(MATLAB)

    https://github.com/strawberry-magic-pocket/Genetic-Algorithm.git

     

    展开全文
  • 上一篇实例讲解遗传算法——基于遗传算法的自动组卷系统【理论篇】讲了遗传算法原理及在自己动组卷系统中的应用,本篇将给出上一篇中所述理论的实践。 先上两张运行后的效果图吧: 基于遗传算法的自动组卷系统...
  • 详述遗传算法原理、推导应用实例。详述遗传算法原理、推导应用实例
  • GATBX遗传算法工具箱函数及实例讲解

    千次阅读 2015-02-09 18:39:13
    遗传算法是一种典型的启发式算法,属于非数值算法范畴。它是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。它是采用简单的编码技术来表示各种复杂的结构,并通过对一组编码表示进行简单的遗传操作...
  • 书系统介绍MATLAB遗传算法和直接搜索工具箱的功能特点、编程原理及使用方法。全书共分为9章。第一章至第四章介绍遗传算法的基础知识,包括遗传算法的基本原理,编码、选择、交叉、变异,适应度函数,控制参数选择,...
  • 本书系统介绍MATLAB遗传算法和直接搜索工具箱的功能特点、编程原理及使用方法。全书共分为9章。第一章至第四章介绍遗传算法的基础知识,包括遗传算法的基本原理,编码、选择、交叉、变异,适应度函数,控制参数选择...
  • NSGA-II在常规遗传算法上的改进,关键步骤就3步。 1)快速非支配排序算子的设计 多目标优化问题的设计关键在于求取Pareto最优解集。NSGA-II算法中的快速非支配排序是根据个体的非劣解水平对种群分层,其作用是指引...
  • 本书系统介绍MATLAB遗传算法和直接搜索工具箱的功能特点、编程原理及使用方法。全书共分为9章。第一章至第四章介绍遗传算法的基础知识,包括遗传算法的基本原理,编码、选择、交叉、变异,适应度函数,控制参数选择...
  • 本书系统介绍MATLAB遗传算法和直接搜索工具箱的功能特点、编程原理及使用方法。全书共分为9章。第一章至第四章介绍遗传算法的基础知识,包括遗传算法的基本原理,编码、选择、交叉、变异,适应度函数,控制参数选择...
  • 本书系统介绍MATLAB遗传算法和直接搜索工具箱的功能特点、编程原理及使用方法。全书共分为9章。第一章至第四章介绍遗传算法的基础知识,包括遗传算法的基本原理,编码、选择、交叉、变异,适应度函数,控制参数选择...
  • 第四章 遗传算法的基本原理与方法 45 4.1 编码 45 4.1.1 编码方法 46 4.1.2 编码评估策略 48 4.2 选择 48 4.3 交叉 52 4.4 变异 55 4.5 适应度函数 57 4.5.1 适应度函数的作用 57 4.5.2 适应度函数的设计...
  • 摘要:阐述了基于多目标优化的免疫遗传算法基本原理,合理地在抗原聚类算法中引入孤立度算法。在该算法中,将优化问题的可行解对应于抗体pareto 最优个体对应于抗原,并运用改进的抗原聚类算法不断更新抗原群中的...
  • 1.《遗传算法原理及应用》 2.https://www.cnblogs.com/LoganChen/p/7509702.html 求下列二元函数的最大值: 运算过程如下: (1)个体编码 ​ 将x1,x2的定义域编码为一种符号串,该例题使用二进制编码。将编码后...
  • matlab遗传算法工具箱

    2012-10-27 11:00:35
    介绍遗传算法的基本原理和 Matlab的遗传算法优化工具箱 ( GAOT) ,分析了优化工具函数。探讨 Matlab遗传算法工具箱在 参数优化和非线性规划中的应用 。通过优化实例 ,说明遗传算法是一种具有良好的全局寻优性能的优化...
  • 分析了遗传算法的基本原理、特点运行步骤,并运用Matlab软件遗传算法工具箱进行求解,结合蜗轮齿固体积优化机械设计实例遗传算法和传统优化方法中的序列二次规划法进行对比,得出传统优化后体积是常规设计的75....
  • 正是由于遗传算法独具的工作原理,使它能够在复杂空间进行全局优化搜索,并且具有较强的鲁棒性。 遗传算法应用于神经网络的一个方面是用来优化人工神经网络的结构,另一个方面是用GA学习ANN的权重,也就是用遗传...
  • 探讨了遗传算法原理及本身参数优化特性,总结了参数的简便设置技术,并针对该法的寻优效果明显依赖于模型参数的初始变化区间的大小,及可能会出现过早收敛的问题,提出了自适应加速遗传算法.通过实例应用,进行了本文...
  • 1.本文源代码来自书目《智能优化算法及其MATLAB实例(第3版)》,目的在于为MATLAB初学者提供更简明的代码解析,方便读者了解算法及MATLAB编程基本原理。 2.文中代码每一行后都有相应注释,因此本文是一篇适合所有...
  • 为了实现可调节变量产品族的优化设计,在建立可调节变量产品族原理模型优化模型的基础上,提出基于非支配排序遗传算法(NSGA-H)的产品族优化设计流程.根据产品族优化设计的数学模型,用NSGA-H算法求得多目标优化...

空空如也

空空如也

1 2 3 4
收藏数 67
精华内容 26
关键字:

遗传算法原理及算法实例