精华内容
下载资源
问答
  • 设势函数=每个点所管区间内互异值的个数总和 一开始势能最大nlogn 操作1使得势能最多增加logn 操作2我们这样处理:每个点记录一下最大值和次大值,若x大于最大值退掉,若x在最大值与次大值之间则打一个tag,若x...

    这里写图片描述

    比如这题
    设势函数=每个点所管区间内互异值的个数总和
    一开始势能最大nlogn
    操作1使得势能最多增加logn
    操作2我们这样处理:每个点记录一下最大值和次大值,若x大于最大值退掉,若x在最大值与次大值之间则打一个tag,若x小于次大值则递归下去。
    可以发现,每次递归下去时势函数都至少减1,这时我们要花费向下走左右子树,共2的时间。

    那么,总的时间复杂度就控制在了势函数最大值(n+m) log n上。
    但是题解的分析是n log^2 n的,不知道这个奇妙的分析方法有没有问题。

    2019 UPD

    这种线段树叫吉司机线段树。
    复杂度的确是 O ( ( n + m ) l o g n ) O((n + m) log n) O((n+m)logn)
    假如有区间加操作,那么复杂度可以证明为 O ( n l o g 2 n ) O(n log^2 n) O(nlog2n)
    但是实践上效率更接近于 O ( n l o g n ) O(n log n) O(nlogn),并没有能卡成log^2的数据(没准他本来就是一个log呢?)

    展开全文
  • 贪心算法经典例题1:区间取点 问题描述: 数轴上有n个闭区间[ai,bi]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)请输出所有所取的点。 思路: 把所有区间按b从小到大排列(b相同...

    贪心算法经典例题1:区间取点

    问题描述:
    数轴上有n个闭区间[ai,bi]。取尽量少的点,使得每个区间内都至少有一个点(不同区间内含的点可以是同一个)请输出所有所取的点。
    思路:
    把所有区间按b从小到大排列(b相同时a从大到小排列),第一个区间取最后一个点。
    代码:

    #include<iostream>
    #include<algorithm>
    #include<climits>
    
    using namespace std; 
    bool comp(pair<int,int>a,pair<int,int>b)
    {
    	if(a.second==b.second)
    		return a.first>b.first;	
    	return a.second<b.second;
    }
    
    int main()
    {
    	int n;
    	while(cin>>n)
    	{
    
    		pair<int,int> v[n];
    		for(int i =0;i<n;i++)
    		{
    			cin>>v[i].first>>v[i].second;
    		}
    		
    		sort(v,v+n,comp);
    	
    		int count=0;
    		int  pos=INT_MIN;
    		for(int i=0;i<n;i++)
    		{
    			if(v[i].first>pos)
    			{
    				count++;
    				pos=v[i].second;
    				//cout<<i<<" ";
    			 } 
    		} 
    		cout<<count;
    		
    
    	}
    		 
    }
    
    
    展开全文
  • 允许两个操作,add(min,max)和del(min,max),一开始区间内为空,每个操作后算出区间内的集合,要求能自动合并、拆分集合。例如: 操作1:add(1,7) 区间内的集合:(1,7) 操作2:add(9,10) 区间内的集合:(1,7)、(9,10...
  • 粒子群算法及其改进算法

    万次阅读 多人点赞 2019-07-01 19:27:08
    由式(7)可知,xi(t) 在一个固定区间内波动,即在 该区间中寻找每个粒子第 t 次迭代后的位置,位置函数 xi(t) 没有振荡收敛,算法容易陷入局部最优。 例如,令 C1=1,C2=1, φ1+φ2 =1 ,可得位置函数 xi(t)=cos(t)...

    标准粒子群算法及其改进算法

    首先在这里介绍一下,这个里主要介绍粒子群算法以及一个改进的二阶振荡粒子群算法。

    原理

    粒子群优化(PSO)算法是Kennedy和Eberhart受 鸟群群体运动的启发于1995年提出的一种新的群智能优化算法[1]。大概的意思就是一片森林里有一群鸟在找一块食物,它们不知道食物具体在哪,但是可以通过感官(例如嗅觉)去察觉到自己当前位置距离食物的远近。鸟可以记住自己走过的位置并且知道自己做过的最优位置。这一群鸟的运动都是随机的,这类似于一种穷举法。

    标准粒子群算法

    粒子群算法一般用来找一个函数的最优值。这个函数一般就是适应度函数。
    函数中未知量的个数就是这个查找的空间维度。

    假设有N个粒子组成一个种群S

    Xi是代表粒子i所在的位置,i=1,2,…,N

    Vi代表粒子i在位置Xi处的速度,i=1,2,…,N

    pi是记录粒子i到走过的最优位置,i=1,2,…,N

    pg是所有粒子走过的最优的位置,i=1,2,…,N

    w 为惯性权重

    c1 、 c2 为学习因子

    r1,r2为[ 0 , 1 ]之间均匀分布的参数

    接下来种群中每个粒子按照公式更新速度和位置:

    Vi( t +1 ) =w * Vi( t ) + c1 * r1 * (pi - xi( t ) ) + c2 * r2 * ( pg - xi( t ) ) (1)
    xi( t + 1 ) = xi( t ) + vi( t + 1 ) (2)

    PS:这里的r1、r2是每一步迭代都需要更新的随机数
    c1、c2和w =则是一开始给定的一些参数,至于参数的给定取决于你自己每次测试这个程序所得到的经验–即哪些参数你跑出的结果比较好就选择哪些参数。
    在这里再插一句,在我的实践中认为没有必要去限制迭代过程中速度和位置是否超过最大值,如果在给定区间内存在最优值那么最后还是会迭代回来。只需要在给定的区间内初始化就OK了。在我最开始的测试过程中限制速度和位置是使程序变慢了的,但是我一开始的思路出了问题,到很后面才改正过来也么有再去测试这个,所以就不加评论了。

    算法流程

    在这里插入图片描述

    标准PSO算法代码

    function [xm,fv]=Pso(N,c1,c2,w,M,D)
    %c1:自我学习因子
    %c2:社会学习因子

    %w:惯性权重
    %N:种群数量`
    %M:最大迭代次数
    %D:维数

    %初始化种群、速度和位置
    tic
    for i=1:N
    for j=1:D
    x(i,j)=unifrnd(-10,10);
    v(i,j)=unifrnd(-10,10);
    end
    end

    %根据适应度计算适应度值,初始化pi和pg
    for i=1:N
    y(i)=test(x(i,:));
    pi(i,:)=x(i,:); %y(i,:)为最优位置
    end
    k = find( y == min(y) ) ;
    pg=x(k(1), : ) ;
    %更新位置与速度
    for t=1:M
    for i=1:N
    v(i,:)=wv(i,:)+c1rand*(pi(i,:)-x(i,:))+c2rand(pg-x(i,:));
    x(i,:)=x(i,:)+v(i,:);
    if test(x(i,:))<y(i)
    y(i)=test(x(i,:));
    pi(i,:)=x(i,:);
    end
    if y(i)<test(pg)
    pg=pi(i,:);
    end
    end
    pbest(t)=test(pg);
    end

    %输出结果
    disp(‘最优位置’);
    xm=pg
    disp(‘最优值’);
    fv=test(pg)
    plot(pbest)
    toc

    test函数–就是适应度函数

    function y = test( V )
    y=0;
    b=length(V);
    for i=1:b
    y=y+i*V(i)^2;
    end

    标准粒子群算法的局限性

    为进一步说明标准粒子群算法的局限性,做如下推理:
    设 φ1=c1*r1 ,φ2=c2r2 ,w=1,由式(1)、(2)可转化 为式(3)、(4):
    Vi( t+1) =Vi( t) +φ1(pi -xi(t))+φ2(pg -xi(t)) (3)
    xi(t+1)=xi(t)+vi(t+1) (4)
    已知速度公式Vi+1=Vi +a×Δt ,可得: a=φ1(pi -xi(t))+φ2(pg -xi(t))=xi(t)″ (5)
    化简可得: xi(t)″+(φ1+φ2)xi(t)-(φ1pi +φ2pg)=0 (6)
    式(6)是二阶微分方程,通过二阶微分方程求解公式,求得搜索位置在 t 代的 x(t)的位置路径公式: xi(t)=C1 cos( φ1+φ2t)+C2 sin( φ1+φ2t) (7)
    由式(7)可知,xi(t) 在一个固定区间内波动,即在 该区间中寻找每个粒子第 t 次迭代后的位置,位置函数 xi(t) 没有振荡收敛,算法容易陷入局部最优。
    例如,令 C1=1,C2=1, φ1+φ2 =1 ,可得位置函数 xi(t)=cos(t)+ sin(t)的图像,如图1所示。在该图像中, 对于t∈[ -∞,+∞] , xi(t) 始终在固定上下限 [- 2, 2] 内范围波动,没有振 荡收敛,容易陷入局部最优。因此,在算法中加入振荡 收敛,是跳出局部最优解,提高粒子群算法搜索性能和精度较有效的方法。[1]

    在这里插入图片描述

    改进标准粒子群算法的思想

    胡建秀,曾建潮通过在标准二阶粒子群算法速度迭 代方程中引入二阶振荡环节的方法改进算法,来增加粒 子的多样性,提高算法的全局搜索能力,是改进位置函 数搜索区域较好的改进方法。使用二阶振荡环节后,算法前期具有较强的全局搜索能力,振荡收敛;而在后期强局部搜索,渐近收敛。 该粒子群算法的进化方程如下:
    Vi( t+1) =w×Vi( t ) + φ1(pi -(1+ξ1)xi(t)+ξ1xi(t-1))+ φ2(pg -(1+ξ2)xi(t)+ξ2xi(t-1)) (8) xi(t+1)=xi(t)+vi(t+1) (9) 算法振荡收敛:
    ξ1<2 φ1 -1 φ1 ,
    ξ2<2 φ2 -1 φ2 (10)
    算法渐进收敛:
    ξ1 ≥2 φ1 -1 φ1 ,
    ξ2 ≥2 φ2 -1 φ2 (11) 振荡收敛和渐进收敛示意图如图2和图3所示。[ 1 ]
    在这里插入图片描述

    改进后二阶振荡粒子群算法的迭代公式

    Vi( t+1 ) =w×Vi( t ) + φ1(pi -(1+ξ1)xi(t)+ξ2xi(t-1))+ φ2(pg -(1+ξ3)xi(t)+ξ4xi(t-1)) (12) xi(t+1)=xi(t)+vi(t+1)

    这个公式的实在上面的二阶振荡粒子群算法的基础上进行的改进,这里ξ虽然是随机数但是取值是有限制的:
    设最大迭代次数为Gmax ,
    0<ξ2<1+ξ1 2 ,0<ξ4 <1+ξ3 2 ,0<ξ1<1,0<ξ3<1 当 t < Gmax / 2时,
    ξ1<ξ2-1,ξ3<ξ4 -1,0<ξ2<1,0<ξ4 <1 当 t > Gmax / 2 时
    这么做的意义在于可以时算法在迭代的前半段振荡收敛;
    在迭代的后半段使其渐进收敛。
    这里的证明和上面的二阶振荡粒子群算法的类似,我这就不展开了,感兴趣的可以自己去找我参考的文献。
    PS:关于改进算法的流程图和标准算法的类似,无非就是加了一个迭代次数前一半和后一半参数的改变,这里就不加上去了。

    改进二阶振荡粒子群算法代码

    function [ z , best ] = PSO_1( w , Gmax ,lizishu , weidu ,a , b )
    %这个测试函数的最小值是0,取值范围是[-10 , 10]
    % z是最优点的适应值,best是记录最优位置的坐标

    %lizishu输入需要的粒子数
    %weidu函数的自变量个数
    %a下界
    %b上界
    q=zeros(1,Gmax);
    tic
    p = inf * ones( 1 , lizishu ) ;%初始的最优解默认为inf
    % pg = 0 ;
    A = unifrnd( a , b , lizishu , weidu ) ;%A矩阵是位置矩阵,用于储存每一步计算出的位置
    B = unifrnd( a , b , lizishu , weidu ) ;%B是速度矩阵,用于储存每一布计算出的V
    C = A ;%用于记录每个粒子的最优位置
    D = unifrnd( a , b , lizishu , weidu ) ;%位置矩阵,用于记录上一次迭代的位置
    c = 2 ; %c通常取1.5 , 这是一个经验值
    y = [] ;%给y申请空间
    for i = 1 : lizishu
    y = [ y , test( A( i ,: ) ) ] ;
    end

    for i = 1 : lizishu
    if p( i ) > y( i )
    C( i , : ) = A( i , : ) ;
    end
    p( i ) = min( [ p( i ) , y( i ) ] ) ;%更新局部最优解
    end

    %初始化全局最优解
    k = find( p == min( p ) ) ;
    pg = C( k( 1 ) , : ) ;
    q( i ) = test( pg ) ;

    for i = 1 : Gmax
    i
    r1 = unifrnd( 0 , 1 ) ;
    r2 = unifrnd( 0 , 1 ) ;
    u1 = r1 * c ;
    u2 = r2 * c ;
    if i < Gmax / 2
    g1 = unifrnd( 0 , 1 ) ; % 这里g1是[ 0 , 1 ]上均匀分布的随机数
    g2 = ( 1 + g1 ) / 2 ;
    g3 = unifrnd( 0 , 1 ) ;
    g4 = ( 1 + g3 ) / 2 ;
    for j = 1 : lizishu
    B( j , : ) = w * B( j , : ) + u1 * ( C( j , : ) - ( 1 + g1 ) * A( j , : ) + g2 * D( j , : ) ) + u2 * ( pg - ( 1 + g3 ) * A( j , : ) + g4 * D( j , : ) ) ;
    D = A ;
    A( j , : ) = A( j , : ) + B( j , : ) ;
    end
    else
    g2 = unifrnd( 0 , 1 ) ; % 这里g2是[ 0 , 1 ]上均匀分布的随机数
    g1 = ( g2 - 1 ) / 4 ;
    g4 = unifrnd( 0 , 1 ) ;
    g3 = ( g4 - 1 ) / 4 ;
    for j = 1 : lizishu
    B( j , : ) = w * B( j , : ) + u1 * ( C( j , : ) - ( 1 + g1 ) * A( j , : ) + g2 * D( j , : ) ) + u2 * ( pg - ( 1 + g3 ) * A( j , : ) + g4 * D( j , : ) ) ;
    D = A ;
    A( j , : ) = A( j , : ) + B( j , : ) ;
    end
    end
    y = [] ;%下一次迭代前清空y
    for j = 1 : lizishu
    y = [ y , test( A( j ,: ) ) ] ;
    end

       for j = 1 : lizishu
          if p( j ) > y( j )
            C( j , : ) = A( j , : ) ;
          end
            p( j ) = min( [ p( j ) , y( j ) ] ) ;
       end
    
        k = find( p == min( p ) ) ;%找到最优解的位置
        pg = C( k( 1 ) , : ) ; %保存最优解坐标
        q(i) = test( pg ) ;
    

    end
    z = q( Gmax ) ;
    best = pg ;
    toc
    plot(q)

    test函数

    function y = test( V )
    y=0;
    b=length(V);
    for i=1:b
    y=y+i*V(i)^2;
    end

    两个算法的比较

    PS:上面我只给了一个test函数,要测试其他的函数直接更改test函数即可。
    下面是两个维度跑出来的结果
    1、标准PSO算法:
    在这里插入图片描述
    在这里插入图片描述
    2、改进的二阶振荡PSO算法:
    在这里插入图片描述

    在这里插入图片描述
    在低维度上这两个算法没有太大差别,改进的算法速度上要稍微快一点。

    下面把维度提升到100维:
    PS:为了便于观看我改了一下程序,最后都只输出一个最优值。
    1、这是标准PSO算法跑出的结果:在这里插入图片描述
    很明显这并没有达到最优值,只是一个局部最优。

    2、改进的PSO算法:
    在这里插入图片描述
    可以看到改进的算法的结果在100维下依旧不错,而且很快。

    下面我们尝试1000维:
    改进的PSO算法结果如下:在这里插入图片描述

    我也试过一些最小值是无穷的函数(X^3),以及一些振荡函数(sinx+cosx),都可以跑出结果,这里就不一个个的给出结果了。

    PS:因为第一个算法不是我写的原因,是我同学写的我拿来用的,所以两个代码在风格上差别有点大。
    这个博客的证明部分基本上我都是从下面的文献里直接拿过来的。
    最后如果找出我的错误请告诉我,我会及时改正的。

    参考文献

    [ 1 ] 蒋丽,叶润周,梁昌勇等,改进的二阶振荡粒子群算法[J],计算机工程与应用,2009,55(9):130-139

    展开全文
  • 遗传算法

    万次阅读 多人点赞 2019-04-06 21:41:47
    当然,也存在较小的概率选出适应度较低的个体,为了避免这种情况,本文引入了竞争机制,即一次选择的过程选出2个个体,再其中适应度较高的那个个体,具体的程序如下: /* 基因选择函数 ga 遗传算法器指针 ...

    使用遗传算法求解多峰函数的最大值,是我的一项课程作业,做完之后,顺便把文档整理出来做个记录。全部内容如下:

    1、问题描述

    编程实现遗传算法,并求解多峰函数的最大值。多峰函数的表达式如下所示:
    在这里插入图片描述
    用MATLAB做出函数的图像如下:
    在这里插入图片描述

    2、算法描述及实现

    2.1、遗传算法概述

    遗传算法(GA,Genetic Algorithm),也称为进化算法。遗传算法是受达尔文的进化论的启发,借鉴生物进化过程而提出的一种启发式搜索算法。其主要特点是直接对结构对象进行操作,因此不同于其他求解最优解的算法,遗传算法不存在求导和对函数连续性的限定,采用概率化的寻优方法,不需要确定的规则就能自动获取和指导优化的搜索空间,自适应地调整搜索方向。

    以上是对遗传算法相对抽象的总结,为了更具体形象的解释遗传算法的一般原理,我们首先介绍一些生物学上的概念

    ①种群:不同生物个体形成的群体,生物的进化以群体的形式进行,这样的一个群体称为种群;

    ②个体:组成种群的单个生物;

    ③基因:带有遗传信息的DNA片段,可以通俗的将基因理解为一段信息,这段信息决定的生物个体的性状;

    ④表现型:根据基因形成的个体的外部表现;

    ⑤适应度:生物个体对于生存环境的适应程度,越适应那么其得以存活和繁衍的概率就越大;

    ⑥遗传:通过繁殖过程,子代将从父母双方各获取一部分基因,形成新的自己的基因,这个过程中,会发生基因的复制、交叉,也会以较低的概率发生基因突变;

    ⑦自然选择:物竞天择,适者生存的自然淘汰机制。具体为对环境适应度高的个体参与繁殖的机会比较多,后代就会越来越多。适应度低的个体参与繁殖的机会比较少,后代就会越来越少;

    ⑧进化:种群通过代际繁衍不断适应生存环境的过程,在这个过程中,以对外界环境的适应度为评判标准,生物的性状不断得到改良。

    了解了这些术语的含义,我们就可以进一步说说生物进化的过程了。由于自然选择是客观存在的,即生物只能改变自己去适应环境,那么在自然选择的过程中,适应度低的个体会被淘汰,适应度高的个体被保留,高适应度的父体与母体又有更高的概率繁衍出适应度高的子代,因此在一代又一代的繁衍之后,高适应度的个体在种群中所占的比例越来越大,种群就这样完成了进化。

    现在我们要参考生物进化的过程来设计算法解决求最优解的问题。对此,遗传算法的思路是,将要解决的问题模拟成一个生物进化的过程,通过进化来寻找最优解。以我们题目中寻找多峰函数的最大值这个问题为例

    将(x, y)这一可能的解作为一个个体;将多峰函数的函数值f(x, y)作为个体的适应度;对(x, y)进行编码作为个体的基因;以适应度为标准不断筛选生物个体;通过遗传算子(如复制、交叉、变异等)不断产生下一代。如此不断循环迭代,完成进化。最终,根据设定的迭代次数,可得到最后一代种群,该种群中的个体适应度都较高,而多峰函数的最大值就有比较大的概率存在于这一群解中,以种群中适应度最高的个体作为问题的解,则可以说该解有比较高的概率就是我们希望求得的最优解。

    文字述说终究还是不如图表好理解,因此还是看图吧(下图将本题与自然遗传联系了起来):
    在这里插入图片描述
    通过以上描述,我们不难看出,遗传算法不能保证一定能求得最优解,而只能以一定的概率求最优解。但是使用遗传算法时,我们可以不用关心具体如何去找最优解,要做的只是简单的否定一些表现不好的个体。这一优点也是遗传算法能够取得广泛应用的原因之一。

    2.2、算法的流程

    通过上文的阐述,对于如何模拟自然进化来求题中多峰函数的最优解已经比较明晰了。这里我将列出遗传算法的主要步骤,并一一解析:

    第一步:随机产生一个种群,作为问题的初代解(通常,初代解可能与最优解相差较大,这是可以容忍的,只要保证初代解是随机产生的,以确保个体基因的多样性即可);

    第二步:寻找一种合适的编码方案对种群中的个体进行编码,可以选择如浮点数编码或二进制编码等常用编码方案(需要指出的是,不同的编码方案直接影响后续遗传算子的实现细节);

    第三步:以多峰函数的函数值 作为个体的适应度,计算种群中每个个体的适应度(算出的适应度将为后续的个体选择提供依据);

    第四步:根据适应度的高低选择参与繁衍的父体与母体,选择的原则是适应度越高的个体越可能被选中(以此不断淘汰适应度低的个体);

    第五步:对被选出的父体与母体执行遗传操作,即复制父体与母体的基因,并采用交叉、变异等算子产生出子代(在较大程度保留优秀基因的基础上,变异增加了基因的多样性,从而提高找到最优解的概率);

    第六步:根据一定的准则判断是继续执行算法,还是找出所有子代中适应度最高个体作为解返回并结束程序(判断的准则可以是设定的解的阈值、指定的迭代次数等)。
    在这里插入图片描述

    2.3、算法的编码实现

    2.3.1、编码

    本文采用的是二进制编码方式,这种编码方式编解码过程简单易行,相应的交叉算子、变异算子等操作用位运算即可实现。当然,它也有一定的缺点,比如连续性不够强。为保证求解的精度,本文使用14个bit为 编码,使用11个bit为 编码,两者组合成25个bit的最终结果。不难算出,该方式的编码精度可达千分位。具体的编码操作可总结为,将 或 的取值区间映射到0~2n-1这一整数范围,其中n表示编码位数, 或 在其取值区间的某点,相应的映射到整数区间中的某点,改点即为 或 的基因编码。程序如下:

    /*
        基因编码
        gene1       输入型参数,待编码的基因段1
        gene2       输入型参数,待编码的基因段2
        gene_code   输出型参数,基因编码
    
        返回值:当输入的基因不符合要求时返回false,否则返回true
    */
    static bool gene_encode(const double gene1, const double gene2, unsigned int *gene_code)
    {
        /* 判断基因是否合法 */
        if (!is_gene_legal(gene1, gene2))
            return false;
    
        /* 若基因合法则对其进行编码 */
        unsigned int gene1_code = (gene1 - GENE1_RANGE_LEFT) * (GENE1_CODE_MAX - 1) / (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT);
        unsigned int gene2_code = (gene2 - GENE2_RANGE_LEFT) * (GENE2_CODE_MAX - 1) / (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT);
        
        /* 组合基因片段 */
        *gene_code = (gene1_code << 11) | gene2_code;
    
        return true;
    }
    

    2.3.2、解码

    解码是编码的逆过程,无需赘述,程序如下:

    /*
        基因解码
        gene_code   输入型参数,基因编码
        gene1       输出型参数,解码后的基因段1
        gene2       输出型参数,解码后的基因段2
    
        返回值:当输入的基因编码不符合要求时返回false,否则返回true
    */
    static bool gene_decode(const unsigned int gene_code, double *gene1, double *gene2)
    {
        /* 判断基因编码是否合法 */
        if (!is_gene_code_legal(gene_code))
            return false;
    
        /* 若基因编码合法则对其进行解码 */
        unsigned int gene1_code = GET_GENE1_CODE(gene_code);
        unsigned int gene2_code = GET_GENE2_CODE(gene_code);
    
        *gene1 = (double)gene1_code * (GENE1_RANGE_RIGHT - GENE1_RANGE_LEFT) / (GENE1_CODE_MAX - 1) + GENE1_RANGE_LEFT;
        *gene2 = (double)gene2_code * (GENE2_RANGE_RIGHT - GENE2_RANGE_LEFT) / (GENE2_CODE_MAX - 1) + GENE2_RANGE_LEFT;
    
        return true;
    }
    

    2.3.3、计算适应度

    适应度函数也称评价函数,通常用于区分群体中个体好坏的标准。适应度高的,也就是优秀的个体有更大的几率参与繁衍,遗传自己的基因。一般的,适应度函数根据目标函数来确定,有时候直接将目标函数值作为适应度。这里,考虑到待求解的多峰函数,尖峰分布密集而且峰的直径很窄,这不利于遗传算法的收敛,因此本文不直接将多峰函数值作为适应度,而是利用对数函数将多峰函数进行平缓,并将平缓后的函数值作为目标函数。具体做法是,将多峰函数进行两次求对数,因此,多峰函数与适应度的关系可如下表示:
    在这里插入图片描述
    用MATLAB做出适应度函数图像如下:
    在这里插入图片描述
    对比前文中的图不难看出,图像得到了有效的平缓,同时不同峰之间也保持着一定的高低之别。值得一提的是,这里更主要的是给出优化遗传算法的一个思路,即可以在适应度函数上做文章。本题的适应度函数只是对多峰函数本身做了一个简单的变换,读者不妨思考一下,就本题而言有没有什么非常好的适应度函数。

    据上文所述,适应度求值函数如下:

    /*
        多峰函数:z = 21.5 + x *sin(4 * 3.1415926 * x) + y * sin(20 * 3.1415926 * y)
        适 应 度:log(log(z))
        约    束:-3.0 <= x <= 12.1; 4.1 <= y <= 5.8
        精    度:精确到千分位
    */
    double get_fitness(const double x, const double y)
    {
        return log(log(21.5 + x * sin(4 * PI * x) + y * sin(20 * PI * y)));
    }
    

    2.3.4、选择算子

    本文的选择算法采用了非常常用的“轮盘赌算法”,赌盘算法的原理非常简单明了。创建赌盘时,我们将种群中所有个体的适应度求和,不妨将得到的结果称为总和适应度。然后,将每个个体的适应度除以总和适应度,然后将得到的商逐个累加,每加一次就得到赌盘的一个边界,累加完成后总和为1。如下的饼状图可以更形象的表明赌盘的原理:
    在这里插入图片描述
    由上文所述,赌盘创建函数可如下编写:

    /*
        创建赌盘
        ga      遗传算法器指针
    */
    static void create_roulette(GA *ga)
    {
        /* 计算赌盘中的概率 */
        ga->roulette[0] = ga->fitness[0] / ga->sum_fitness;
    
        for (int num = 1; num < ga->population_num - 1; num++)
        {
            ga->roulette[num] = ga->roulette[num - 1] + ga->fitness[num] / ga->sum_fitness;
        }
    
        ga->roulette[ga->population_num - 1] = 1.0;
    }
    

    再回到选择算子,选择算子需要赌盘作为基础,其运行时,会产生一个0到1的随机数,然后在赌盘中找到该数所在的区间,这个区间对应的个体即为被选中的个体。因此,适应度越高的个体被选中的几率越大,这是合理的。当然,也存在较小的概率选出适应度较低的个体,为了避免这种情况,本文引入了竞争机制,即一次选择的过程选出2个个体,再取其中适应度较高的那个个体,具体的程序如下:

    /*
        基因选择函数
        ga      遗传算法器指针
        返回值:返回使用轮盘赌的方式选出的个体(编号)
        说  明:选择策略为轮盘赌+随机竞争
    */
    static unsigned int select(GA *ga)
    {
        unsigned int index1 = 0, index2 = 0;
    
        /* 产生一个[0.0, 1.0]之间的浮点数 */
        double selector1 = rand() * 1.0 / RAND_MAX;
        double selector2 = rand() * 1.0 / RAND_MAX;
    
        /* 找出被选中的个体的索引 */
        for (; selector1 > ga->roulette[index1]; index1++);
        for (; selector2 > ga->roulette[index2]; index2++);
    
        return (ga->fitness[index1] > ga->fitness[index2] ? index1 : index2);
    }
    

    2.3.5、交叉算子

    遗传算法的交叉操作实质上是按某种方式交换父体和母体的部分基因,常见的交叉算子有单点交叉、两点交叉、多点交叉、均匀交叉及算术交叉等。本文选用两点交叉法,实现过程既不复杂,也有较好的随机性,该方法可由下图示意:
    在这里插入图片描述
    图中虚线指出的两个交叉点是随机产生的。具体程序如下:

    /*
        交叉函数
        ga          遗传算法器指针
        one         输出型参数,待交叉基因
        another     输出型参数,待交叉基因
        说明:
        1.对传入的基因编码执行两点交叉操作
    */
    static void cross(GA *ga, unsigned int *one, unsigned int *another)
    {
        /* 1.随机产生两个交叉点的位置 */
        unsigned char pos1 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char pos2 = rand() % GENE_CODE_LENGTH + 1;
        unsigned char min_pos = min(pos1, pos2);
        unsigned char max_pos = max(pos1, pos2);
    
        /* 2.截出需要交换的基因段 */
        unsigned int one_gene_seg = get_bits(*one, min_pos, max_pos) << (min_pos - 1);
        unsigned int another_gene_seg = get_bits(*another, min_pos, max_pos) << (min_pos - 1);
        unsigned int mask = ~(get_bits(~(0U), min_pos, max_pos) << (min_pos - 1));
    
        /* 3.执行交叉操作 */
        *one = (*one & mask) | another_gene_seg;
        *another = (*another & mask) | one_gene_seg;
    }
    

    2.3.6、变异算子

    在自然界中,基因变异可以增加个体的多样性,这对于遗传算法来说是增加了个体的随机性,可以增加找到最优解的概率。本文采用的变异算子所做的操作是随机选择基因的某一位进行反转,程序如下:

    /*
        变异函数
        gene_code       输入型参数
        说明:
        1.对传入的基因编码执行变异操作
        2.随机选择基因编码中的一位做反转操作
    */
    static void mutate(unsigned int *gene_code)
    {
        unsigned int mutate_bit = 1 << (rand() % GENE_CODE_LENGTH);
        *gene_code ^= mutate_bit;
    }
    

    2.3.7、繁殖函数及进化函数

    遗传算法的主要算子都在上文中分析过了,下面要做的就是根据遗传算法的流程将这些算子整合起来以实现算法功能。在本文中,这其中涉及到两个关键的函数,即繁殖函数和进化函数。繁殖函数包括基因的复制、交叉及变异,同时本文还采用了子代竞争策略,即父代产生的两个子代个体仅保留适应度最高的,程序如下:

    /*
        繁殖函数
        ga       遗传算法器指针
        father   从种群中选出的父体
        mother   从种群中选出的母体
        返回值:  适应度最高的子代的基因编码
        说明: 
        1.一对父体与母体将繁殖出一对子代
        2.选择出适应性更好的子代返回
    */
    static unsigned int inherit(GA *ga, unsigned int father, unsigned int mother)
    {
        unsigned int son1 = ga->gene_code[father];
        unsigned int son2 = ga->gene_code[mother];
    
        /* 1.交叉 */
        cross(ga, &son1, &son2);
    
        /* 2.变异 */
        mutate(&son1);
        mutate(&son2);
    
        /* 3.子代竞争 */
        double son1_gene1, son1_gene2, son2_gene1, son2_gene2;
        gene_decode(son1, &son1_gene1, &son1_gene2);
        gene_decode(son2, &son2_gene1, &son2_gene2);
    
        return (ga->get_fitness(son1_gene1, son1_gene2) > ga->get_fitness(son2_gene1, son2_gene2)) ? son1 : son2;
    }
    

    进化函数则实现了遗传算法的一次完整的迭代过程,根据上文给出的遗传算法流程图,不难进行如下编码:

    /*
        进化函数
        ga      遗传算法器指针
    */
    static void evolve(GA *ga)
    {
        /* 1.申请暂存子代基因编码的内存 */
        unsigned int *descendants = (unsigned int *)calloc(ga->population_num, sizeof(unsigned int));
        
        /* 2.精英保留(将上一代中适应度最高的个体的基因编码保留) */
        descendants[0] = ga->gene_code[ga->best_individual];
        
        /* 3.选择合适的父体与母体 */
        unsigned int father = select(ga);
        unsigned int mother = select(ga);
    
        /* 4.繁殖(包含交叉与变异) */
        for (int num = 1; num < ga->population_num; num++)
            descendants[num] = inherit(ga, father, mother);
    
        /* 5.将子代记录到ga中并进行基因解码(使新一代的基因编码与基因对应) */
        for (int num = 0; num < ga->population_num; num++)
        {
            ga->gene_code[num] = descendants[num];
            gene_decode(ga->gene_code[num], &ga->gene[num].gene1, &ga->gene[num].gene2);
        }
        
        /* 5.更新种群适应度 */
        fit(ga);
        
        /* 6.更新赌盘 */
        create_roulette(ga);
    
        /* 7.释放之前申请的空间 */
        free(descendants);
    }
    

    3、运行结果及分析

    至此,本文已经给出了一个遗传算法的C语言实现的所有关键程序。下面就调用编写的遗传算法进行测试。本文将创建含有100个个体的种群,并进行100代迭代以求解多峰函数的最大值,一次完整的调用本文实现的遗传算法的程序如下所示:

    /* 创建遗传算法器 */
    GA *ga = create_ga(get_fitness, 100);
    
    /* 初始化遗传算法器 */
    ga->init(ga);
    
    /*迭代100代*/
    for (int i = 0; i < 100; i++)
    ga->evolve(ga);
    
    /*销毁遗传算法器*/
    delete_ga(ga);
    

    经多次调用测试,算法执行的结果较为稳定,所得的多峰函数最大值大多在38以上,多次运行结果中最好的解为38.849744,对应的坐标为(11.625331, 5.725256)。将迭代求得的最大值用MATLAB作图如下:
    在这里插入图片描述
    为验证是否找到了最优解,用MATLAB遍历求出该多峰函数在给定定义域内的最大值为38.8501,与本文求出的结果相差0.000356,可见本文实现的遗传算法表现还不算太差。

    文中给出的程序比较散,这里给出完整程序的下载链接

    展开全文
  • 测试开发笔记

    万次阅读 多人点赞 2019-11-14 17:11:58
    测试开发笔记 第一章 测试基础 7 什么是软件测试: 7 ★软件测试的目的、意义:(怎么做好软件测试) 7 3.软件生命周期: 7 第二章 测试过程 8 1.测试模型 8 H模型: 8 V模型 9 2.内部测试 10 ...
  • JAVA实现指定区间取N个不重复随机数

    千次阅读 2018-03-17 11:15:36
    近日在面试中多次被问到从规定区间取N个随机数的问题,所以今日将实现方式整理一下,代码如下: 传统双重循环去重的方式 /** * 功能:产生min-max中的n个不重复的随机数 * * min:产生随机数的其实位置 *...
  • ORACLE 连续值、时间段的区间

    千次阅读 2018-09-15 01:53:24
    连续值区间 --测试数据 CREATE TABLE Z_NUMS AS SELECT LEVEL AS NUM1 FROM DUAL CONNECT BY LEVEL &amp;amp;amp;lt;=1000; DELETE FROM Z_NUMS WHERE NUM1 LIKE '%7%'; COMMIT; SELECT MIN...
  • random.randint(min, max)

    2019-11-30 11:42:09
    python 中生成区间随机数的时候,使用的random.randint(min, max) 居然是包括最大数的, 又被坑了
  • 第3周编程作业 本作业是在线评测形式。提交源程序,系统自动评测,可多次提交。...2.学生可以在作业截止时间之前不限次数提交答案,系统将其中的最高分作为最终成绩。 本作业是 13-1打印3个相邻...
  • 浅谈傅里叶变换、小波变换、HHT变换

    千次阅读 多人点赞 2019-08-29 12:18:42
    ,基函数的选取的不同可能会造成分析结果的不一致,分析结果的准确性决于选取合适的小波基函数。 最优小波基的选取方法研究 。现在国内外已经有一些最优基选取方法,但是缺乏系统规范的最佳小波基的选取方法,即...
  • Python蒙特卡洛算法

    千次阅读 多人点赞 2019-09-05 18:52:40
    这时我们可以用一个比较容易算得面积的矩型罩在函数的积分区间上(假设其面积为 A r e a Area A r e a )。然后随机地向这个矩形框里面投点,其中落在函数 f ( x ) f(x) f ( x ) 下方的点为绿色,其它点为红色。...
  • iOS 取区间

    2017-03-01 16:15:00
    candleWidth = MIN(MAX(1, candleWidth),15); 1~15 转载于:https://www.cnblogs.com/zhangxiaozhe/p/6484786.html
  • Math.random()一个区间的随机数

    千次阅读 2016-04-10 19:47:11
    Math.random()是[0,1)之间的随机数,包括0但是不包括1,,强转为int时,只到0,如果特定区间的随机数: int num=(int)(min+Math.random()*(max-min));包括min但是不包括max;例如1~11之间的随机数,即包括1...
  • /** 获取区间内的一个随机整数 原理:要得到的随机数的范围是[110,130],返回的伪随机... 将得到的随机数取余,控制最大值为区间的差数[max-min],这样就可以得到一个区间差数内的一个随机数[min-min,max-min], ...
  • 线性回归

    万次阅读 多人点赞 2016-06-03 10:22:43
    多项式曲线拟合的一个缺陷就是这个模型是一个输入变量的全局函数,这使得对输入空间的一个区间的改动会影响到其他的区间,这个问题可以通过将输入空间切分成不同的区域,对不同的区域各自在各自的区域中做曲线拟合来...
  • Java 一个日期区间与一个日期区间集合的差集 代码实现0. 解决思路1. 定义包含[开始日期~结束日期]的对象DateObject2. 初始化DateObject集合对象3. DateObject集合中的日期区间合并4. 已知日期区间`date`与日期区间...
  • 【LeetCode】区间(合并、插入、重叠区间、最小区间······) 汇总区间★ LeetCode228. 汇总区间 【题目】给定一个无重复元素的有序整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。...
  • 在闭区间[0, 1]内,我们随机取出两点(服从均匀分布)A和B,形成一个新的闭区间[min{A,B}, max{A,B}]。如此反复n次,我们就有了n个随机闭区间。那么这n个闭区间不出现重叠的概率是多大呢? 将问题可以简单转化为2n个...
  • python数值区间处理的几个函数

    千次阅读 2019-12-05 21:16:40
    分享几个自己编写的处理数值区间的函数 合并多个区间 def merge(intervals): ''' @msg: 合并多个区间 @param intervals {list} 一个二维数组,每一项代表一个区间 @return: {list} 返回合并后的区间列表 ''' ...
  • js获取一个区间随机数

    千次阅读 2018-12-24 11:03:13
    var max = 70; var min = 30; var random = Math.random()*(max-min)+min; console.log(random);
  • 1.区间列表求交集、差集、并集 比如区间列表{[10-100],[120-200]} 减去 {[50-60],[65-70],[75-80]} 用代码怎么实现? 已经写了两个区间之间的计算方法,代码如下,但是列表相减会出现问题,有没有大佬解决过类型...
  • //要想更新该区间下面的子区间,就要把上次更新该区间的值向下更新 if(tree[index].add){ //替换原来的值 /* tree[index].sum = (tree[index].r-tree[index].l+1)*tree[index].add; tree[index|1].sum = ...
  • 灰色关联度矩阵模型及其MATLAB实现

    千次阅读 多人点赞 2019-12-06 10:41:15
    之值位于[0,1]区间,同时上下对称的结构可以消除量纲不同和数值悬殊的问题。 ③ ∣ x j ( k ) − x i ( k ) ∣ |x_{j}(k)-x_{i}(k)| ∣ x j ​ ( k ) − x i ​ ( k ) ∣ 式被称之为“Hamming”距离,Hamming距离的...
  • Elasticsearch聚合学习之二:区间聚合

    千次阅读 2019-05-03 01:13:35
    本文是《Elasticsearch聚合学习》系列的第二篇,上一篇是我们熟悉了聚合的基本操作,本篇的内容是按照区间聚合的实战操作;
  • LeetCode上关于动态规划的题目众多,除了前述文章的最小路径、股票买卖等问题,区间型动态规划也是一类经典题目。本节将分析LeetCode上两道区间型动态规划题目。 关于动态规划: [LeetCode]动态规划及LeetCode题解...
  • 线段树 区间更新 区间求和以及最值

    千次阅读 2016-07-23 09:36:55
    #include #include #include #include #include #include #define MAXN 100010 #define inf 0x3f3f3f3f using namespace std; struct node{ int l,r;//区间[l,r] ...//区间的延时标记 ...//区间
  • 优化算法——遗传算法

    万次阅读 多人点赞 2015-05-10 17:09:28
    对于每一个变量的二进制位串的长度决于变量的定义域所要求的精度。 二进制位串的长度的计算方法如下: 假设 a j ≤ x j ≤ b j a_j\leq x_j\leq b_j ,所要求的精度是小数点后 t t 位。这要求将区间划分为...
  • 对于数组中的每个数,用单调栈去...那么在开区间(i , j )中,这个数是最小的。 ans = min(sum(i + 1, j - 1) * num[index]) --> (0 <= index < n) 转载于:https://www.cnblogs.com/liqiniuniu/p/1053081...
  • N个区间求交集

    千次阅读 2018-07-30 11:14:53
    博主遇​​到一个问题,要对文章根据用户阅读记录进行... 最终博主想到了一个优化策略,在redis中缓存用户阅读的文章ID区间(文章ID是递增方式存入数据库)取代之间对文章ID校验去重的方式进行去重,这时就涉及到对用...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,249
精华内容 23,699
关键字:

区间取min