QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 3323|回复: 0
打印 上一主题 下一主题

组合优化算法-现代优化算法(四):改进的遗传算法

[复制链接]
字体大小: 正常 放大
浅夏110 实名认证       

542

主题

15

听众

1万

积分

  • TA的每日心情
    开心
    2020-11-14 17:15
  • 签到天数: 74 天

    [LV.6]常住居民II

    邮箱绑定达人

    群组2019美赛冲刺课程

    群组站长地区赛培训

    群组2019考研数学 桃子老师

    群组2018教师培训(呼伦贝

    群组2019考研数学 站长系列

    跳转到指定楼层
    1#
    发表于 2020-5-22 15:31 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta |邮箱已经成功绑定
    无人机航路规划问题实际上是一个组合优化问题,是优化理论中的 NP—hard 问题。 因为其解空间不连续,解邻域表达困难,所以难以用通常的算法求解。遗传算法作为现代优化算法之一[1],其主要特点是对非线性极值问题能以概率 1 跳出局部最优解,找 到全局最优解。而遗传算法这种跳出局部最优寻找全局最优特性都基于算法中的交叉和 变异。在传统遗传算法的结构中,变异操作在交叉操作基础上进行,强调的是交叉作用, 认为变异只是一个生物学背景机制[2]。在具体交叉操作中,人们通常采用断点交叉法 (段交叉)多点交叉与均匀交叉,其中断点交叉是指随机地在基因序列中选择一个断点, 然后交换双亲上断点右端的所有染色体。在变异操作中,变异算子一般是用 Guassian 分 布的随机变异来实现[3,4]。近年来,也有学者尝试用 Cauchy 分布的随机序列来实现变异[5], 希望通过 Cauchy 分布宽大的两翼特性实现更大范围的变异,以利于找到全局最 优解。[6]从理论上分析了采用 Cauchy 分布随机变异进化算法的局部收敛性。[7]进一 步把二者结合起来, 采用两种分布的线性叠加,但仿真结果显示,算法改进效果并不十 分明显。文献[8]将生物进化看成是随机性加上反馈,并指出其中的随机性主要是由系 统的内在因素所引起,而不是由外部环境的随机扰动所造成。而混沌系统在其混沌域中 表现为随机性,它是确定系统内部随机性的反映,不同于外在的随机特性。
    : w  t1 B6 m3 N2 [" o8 F' j1 J" I  \9 e
    本文根据以 上特点对基于求解航路规划的遗传算法进行改进,首先将变异操作从交叉操作中分离出 来,使其成为独立的并列于交叉的寻优操作,在具体遗传操作中,混沌与遗传操作联系 在一起,在交叉操作中,以“门当户对”原则进行个体的配对,利用混沌序列确定交叉 点,实行强度最弱的单点交叉,以确保算法收敛精度,削弱和避免寻优抖振问题;在变异操作中,利用混沌序列对染色体中多个基因进行变异,以避免算法早熟。
    2 w# {2 b* e0 Z2 L
    . D0 Q8 ]3 r9 P. M! w1 ^" a下面我们研究 1.2 中同样的问题。
    % ?6 b+ U, q" Q. e& k: \5 @0 \: ?6 ^
    $ P) a/ V  I) U  }/ ^" v

    8 n/ d" e/ I$ f% M7 N- R
    4 O% A0 i( s; S
    6 n: |$ F" }* e! A$ B: o1 [9 Z1 t我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。
      ?- w; R8 f6 s5 K! ~) v
    + i2 B( ~  s* E/ d- J5 w6 u6 Z8 ~5 m* N- ]1 G0 v; Y3 `& a
    ; x! ^% _9 w+ O) P% g
    2)我方有三个基地,经度、纬度分别为(70,40),(72,45),(68,48)。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标, 怎样划分任务,才能使时间最短,且任务比较均衡。
    + o+ T) O; Q& U" T
    : I# {( X3 J6 I. U8 u2 模型及算法2 m# `% o/ @- ^. U
    与标准的遗传算法相比,我们做了如下的两点改进。
    ( n4 L& A2 f+ V. c# w+ w0 @- V4 `% Y5 w! ]+ q/ V/ K% m
    (1)交叉操作
    , Y* j8 I& o. c
    5 r+ w9 f2 \5 x$ `/ V2 Z3 ~; Z: M/ O. [" k  T" }, V  {4 ?4 h( v

    + Y. A1 |/ ]) {) u) @& s5 Q' _- D5 r0 _4 E& m3 `0 \

    1 U& D1 U, Y- s# ~' r8 U很明显这种单点交叉对原来的解改动很小,这可以削弱避免遗传算法在组合优化应用中 产生的寻优抖振问题,可以提高算法收敛精度。
    " E8 `* [2 P, V. o6 [- F) S! q' ~' j/ |& s$ {) C
    (2)变异操作
    8 J! k( |. [/ \" p5 Z变异也是实现群体多样性的一种手段,是跳出局部最优,全局寻优的重要保证。在 本文具体变异算子设计如下,首先根据给定的变异率(本文选为 0.02),随机地取两个在 2 到 101 之间的整数,对这两个数对应位置的基因进行变异,具体变异以当前的基因值 为初值利用混沌序列 x(n +1) = 4x(n)(1− x(n)) 进行适当次数的迭代,得到变异后新的基因 值,从而得到新的染色体。- e0 n3 ^# o# \, R% t0 h# {1 V
    8 g% \- m. [% M4 |3 G! [
    3 仿真结果对比及算法性能分析/ E9 p5 x! V; W, Y$ i( O: q
    计算的 MATLAB 程序如下:4 w9 S# V* ^/ v9 V- Y
    , L5 ^. t+ `# y0 F; u7 l
    tic
    ) U6 K1 y7 S! `$ w4 t4 ^clc,clear
    $ ^0 o0 m) ~4 |% m; I0 ]8 w, I% g1 xload sj.txt %加载敌方 100 个目标的数据# N  I' P. M1 B9 {' P4 Z
    x=sj(:,1:2:8);x=x(;% b7 c( i9 H; J
    y=sj(:,2:2:8);y=y(;" L! m5 L8 C3 g3 R
    sj=[x y];+ o* z5 K* ?$ u. e' C4 Y
    d1=[70,40];
    * {& u5 S7 d3 C. B+ \/ msj=[d1;sj;d1];$ }. K7 w# u" c7 c5 i* @+ U7 @4 x) b* `
    %距离矩阵 d& O( P2 m1 W. L8 Q. ?9 T
    sj=sj*pi/180;
    # v: G- i. b9 q1 X7 w, Bd=zeros(102);
    ( ?6 R7 N7 R# b1 D( ofor i=1:101  H- M% X6 D" V8 k' k
        for j=i+1:102" f  J$ c0 ^, d6 r" Y
            temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
    - r9 A) M4 B8 T+ a  Y. Z        d(i,j)=6370*acos(temp);" X4 U$ s$ x% ?# x7 \! C
        end: V+ @; ?! i. G3 @2 R7 F% C4 a
    end
    ( s. f$ X$ v/ P% u4 jd=d+d';L=102;w=50;dai=100;
    6 @" j2 N( N5 y%通过改良圈算法选取优良父代 A
    9 S. d+ ^' d! @8 b2 O  I' @for k=1:w1 o% o* Z& I, h  t+ b: c
        c=randperm(100);' d  U) y6 B- w  U
        c1=[1,c+1,102]; " O% b1 l, y; Y5 o, Z
        flag=1;
    % T; G$ v8 `' u% k& O3 p6 n% y: u    while flag>0
    ) @7 y' N+ \( e; ?8 o/ }5 m        flag=0;: o2 _- l0 H  Q/ Z5 n$ B7 Z( P6 |
            for m=1-3! @+ a# g# |  W5 a
                for n=m+2-1. q% Z6 D, e6 c* O% C  q
                    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))
    , _9 l8 Z* X- {$ P                    flag=1;
    , N6 ]8 h1 z2 Q" j. H7 J3 B8 Q; t5 n                    c1(m+1:n)=c1(n:-1:m+1);3 ^. |" W, E+ Q6 s* n/ J
                    end0 {6 E* o! d& e# D! G
                end
    - u& B: j. v8 ^( `0 u+ d        end1 w% `% t* A" u8 }( \! X8 m
         end/ l4 P6 N" p5 I; T7 N
        J(k,c1)=1:102;$ G" t2 e! K4 G
    end/ C: R+ P1 d8 \, ^0 i+ Y, n; ?
    J=J/102;) c  x  w1 T$ O) p* v, {& ?
    J(:,1)=0;J(:,102)=1;& ?+ s- C6 N. f& \) ?
    rand('state',sum(clock));
    ; s8 D) B6 Q5 [6 R  w%遗传算法实现过程
    5 n+ }5 n& O3 g( H0 l( z; FA=J;9 O: ^  a2 c! N! M. ^  @6 r5 K
    for k=1:dai %产生 0~1 间随机数列进行编码
    ! o1 A, D& a8 h8 L    B=A;
    + R+ w! i+ y0 [/ z5 X %交配产生子代 B
    , Y1 V' y! m. v- c' s    for i=1:2:w+ J; v9 K0 i8 Z+ t% J- @
            ch0=rand;ch(1)=4*ch0*(1-ch0);) @' g- `6 M& Y
            for j=2:50
    & {, p5 C( H1 d( ?' V. H5 d            ch(j)=4*ch(j-1)*(1-ch(j-1));0 s/ Q1 B0 `) |' |: C
            end8 ]8 L9 v. x- g. \* h0 ^
            ch=2+floor(100*ch);! U: x; ]9 w7 i8 \$ A
            temp=B(i,ch);
    + p, a- ?: U- S9 Y5 c8 L        B(i,ch)=B(i+1,ch);
    * b7 u- d% l% K0 g: u6 {) @        B(i+1,ch)=temp;# h3 }, m4 m+ R& i* G
        end0 R5 Q, S+ X8 u3 O8 M
    %变异产生子代 C
    * g9 y5 k5 m) M: Z& I4 O    by=find(rand(1,w)<0.1);. M1 h& E" }) g! C# d5 A
        if length(by)==02 O$ O* ?. L; ^6 F% S
            by=floor(w*rand(1))+1;   
    + D" m% m. O% s1 ]3 J! R    end
    3 w+ w1 `7 ~8 h9 m% Q    C=A(by,;
    6 @) M7 v" m/ n3 w    L3=length(by);, M; a% m6 V8 y. L/ m
        for j=13
    $ K8 y- Q! Z# Q/ a* X+ G     bw=2+floor(100*rand(1,3));
    " X, a6 c* `$ F3 C     bw=sort(bw);9 Q2 C# k2 U3 C6 f- W* j8 K
         C(j,=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
    : ?5 @/ D' V. }8 H' S3 xend
    8 s3 r1 m& ^4 H1 T, H    G=[A;B;C];
    ( |: I' O& H! _; Y5 P1 U5 Z    TL=size(G,1);
    4 h; n, N) N  |  e %在父代和子代中选择优良品种作为新的父代9 [- s4 c8 B+ A+ {# g' p& f
        [dd,IX]=sort(G,2);temp(1:TL)=0;
    1 W* v; c2 h3 v7 B; q1 i5 B; I    for j=1:TL$ }# h3 M+ Q" s9 l
            for i=1:101. S3 H4 j7 \  }8 ~; e; k- K
                temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));5 l5 J2 B$ d8 Q
            end
    ! _" B$ j  \) Q    end
    . k* S* Q2 l5 E! ]8 v; S  |9 R    [DZ,IZ]=sort(temp);
    1 ?. g+ h  C1 b; I    A=G(IZ(1:w),;
    $ B9 a2 B% ^1 D6 a" Aend/ I' t, [& J9 r( p/ y
    path=IX(IZ(1),+ v2 g& g/ I( e/ K
    long=DZ(1)
    # I4 Q3 a) V. ^! r8 S3 {& v+ [" stoc
      E( ?( E3 q8 [# n& }- }- _# V3 C4 t
    ' @$ T4 l7 {/ J$ J
    在仿真试验中,我们对文中航路规划问题分别利用断点交叉和换位变异结合的遗传 算法,多点交叉和移位变异结合的遗传算法[10]和文中提出的改进算法进行求解比较。 表 1 是各种算法种群规模( M = 50)和迭代次数(G = 100 )都相同时连续 20 次求 解的平均值(公里),算法平均运算时间(秒)。
    4 S4 e! T3 R; H* K. A, U$ p3 Q1 }, o( X/ P5 H8 X
    $ X, f4 L8 i; a- d1 n* H. ^

    ! ?& K( `5 g) R& W# t8 Z* P* W4 `& }. M' k5 q4 v& h
    本文从算法结构到具体的遗传操作都进行了改进,其中变异操作从交叉操作中分离 出来,使得遗传算法也可以通过并行计算实现,提高算法实现效率。其次改进后的算法, 分别采用变化强度不同的交叉操作和变异操作,其中交叉操作采用强度最弱的单点交 叉,保证了算法收敛精度,削弱和避免算法因交叉强度大而产生的寻优抖振问题。当然 单一的单点交叉很容易使算法早熟,文中采用较大强度的多个基因变异正好解决早熟问 题。从仿真结果可以看到改进后的算法效果较为明显。# N2 Y( k8 k% a: n; N
    % i. y) ?+ ?* `

    " b* ~- K4 O' ^5 K7 x  E. F# o6 u( P* l2 }; c( k) J
    ————————————————
    3 @3 W/ _& n1 j7 Q版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。5 C# z7 {7 ]# N
    原文链接:https://blog.csdn.net/qq_29831163/article/details/89672986
    7 _1 B  L: K: B4 `
    ; z: F: T# N$ `) v/ \) }" t9 H" |& c. A! `1 J* u5 Q
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-20 23:06 , Processed in 0.421827 second(s), 51 queries .

    回顶部