- 在线时间
- 791 小时
- 最后登录
- 2022-11-28
- 注册时间
- 2017-6-12
- 听众数
- 15
- 收听数
- 0
- 能力
- 120 分
- 体力
- 35382 点
- 威望
- 11 点
- 阅读权限
- 255
- 积分
- 13558
- 相册
- 0
- 日志
- 0
- 记录
- 1
- 帖子
- 621
- 主题
- 542
- 精华
- 10
- 分享
- 0
- 好友
- 225
TA的每日心情 | 开心 2020-11-14 17:15 |
---|
签到天数: 74 天 [LV.6]常住居民II
群组: 2019美赛冲刺课程 群组: 站长地区赛培训 群组: 2019考研数学 桃子老师 群组: 2018教师培训(呼伦贝 群组: 2019考研数学 站长系列 |
遗传算法简介
9 x1 h, d% n4 n遗传算法(Genetic Algorithms,简称 GA)是一种基于自然选择原理和自然遗传机制的搜索(寻优)算法,它是模拟自然界中的生命进化机制,在人工系统中实现特定目 标的优化。遗传算法的实质是通过群体搜索技术,根据适者生存的原则逐代进化,终 得到优解或准优解。它必须做以下操作:初始群体的产生、求每一个体的适应度、 根据适者生存的原则选择优良个体、被选出的优良个体两两配对,通过随机交叉其染色 体的基因并随机变异某些染色体的基因后生成下一代群体,按此方法使群体逐代进化, 直到满足进化终止条件。其实现方法如下:& S! L; H3 P8 q: R
4 n U$ e1 h- O& ]! ^
(1) 根据具体问题确定可行解域,确定一种编码方法,能用数值串或字符串表示 可行解域的每一解。
+ V% p' C, }1 F. q' l
1 N( V! o3 f6 c0 p V# r, [5 H(2) 对每一解应有一个度量好坏的依据,它用一函数表示,叫做适应度函数,适应度函数应为非负函数。
* h2 s! o/ Q3 I7 L2 H, ^' ~/ J0 C) S6 N
(3) 确定进化参数群体规模M 、交叉概率 、变异概率 、进化终止条件。0 x7 A9 p: w7 c+ K; I) _
+ j! G4 j6 H3 p% @. ^为便于计算,一般来说,每一代群体的个体数目都取相等。群体规模越大、越容易找到优解,但由于受到计算机的运算能力的限制,群体规模越大,计算所需要的时 间也相应的增加。进化终止条件指的是当进化到什么时候结束,它可以设定到某一代进 化结束,也可能根据找出近似优是否满足精度要求来确定。表 2 列出了生物遗传概念 在遗传算法中的对应关系。
5 h, T4 t( e8 P, p* {) A6 y) F! j, w
6 V) z' Z( _+ n5 q6 p- Q, j
3 d1 S8 C1 k) Y2 模型及算法 我们用遗传算法研究 1.2 中的问题。 (1)研究 1.2 中同样的问题。
# k7 `: A3 ~: n, d: R1 |& M1 l8 G* p
! h4 E4 t& I- X! k0 `
! `2 \. ^- T% b0 o* s我方有一个基地,经度和纬度为(70,40)。假设我方飞机的速度为 1000 公里/小时。 我方派一架飞机从基地出发,侦察完敌方所有目标,再返回原来的基地。在敌方每一目 标点的侦察时间不计,求该架飞机所花费的时间(假设我方飞机巡航时间可以充分长)。
' a) h! ~4 {$ V% d* ]
) T7 } g+ W/ Y4 m. ~1 ^/ w
$ \/ X$ e+ S, x! E- C2 k" _+ W B& Q) v6 N8 K% D; n
问题(2)我方有三个基地,经度、纬度分别为(70,40),(72,45),(68,48)。假设我方 所有无人侦察机的速度都为 1000 公里/小时。三个基地各派出一架飞机侦察敌方目标, 怎样划分任务,才能使时间最短,且任务比较均衡。
3 p( E# t0 N- b
) n7 c6 }* F5 d; ~, V/ @& C7 `2 g) ^; S! d
" Q" E- F0 L# x# K/ |(2) 初始种群
$ G! q3 O) h5 B5 Z$ u' x9 G7 Z. a; b& x* T2 J4 X* G5 A+ o
5 i: @( h) |& \
+ k' k( z5 s }$ } c' E(3) 目标函数
( L2 H. h! L1 R" F! t/ I
+ D4 }& [( h, B
1 P+ G0 `2 i* B7 q1 G3 u(4) 交叉操作
! b) m9 y" E: f/ N
6 Q& @) T& _( N7 f4 f
* c; l4 Y' w; O' C! h. x. H, ^
8 n$ L- ^9 f# |4 `交叉操作的方式有很多种选择,我们应该尽可能选取好的交叉方式,保证子代能继 承父代的优良特性。同时这里的交叉操作也蕴含了变异操作。 (5) 变异操作 " ]7 A5 l1 m" f. G; R) p
4 ^. I( W+ N) A9 {(6) 选择 采用确定性的选择策略,也就是说选择目标函数值最小的 M 个个体进化到下一代,这 样可以保证父代的优良特性被保存下来。 2.3 模型求解及结论 编写 MATLAB 程序如下:
$ o& P' x% ?1 S; P% m) otic
. i6 F, h/ k9 m+ T8 C8 Uclc,clear
2 p9 C: Z) I4 A5 hload sj.txt %加载敌方 100 个目标的数据$ c, M/ I- k! y9 V
x=sj(:,1:2:8);x=x(;
% K' C5 N4 f7 Y% C- xy=sj(:,2:2:8);y=y(;* d) w- A* i3 r8 E) b
sj=[x y];2 [ K) a: v3 O2 J
d1=[70,40];. N( F% m6 v: `9 s
sj0=[d1;sj;d1];
! o( l; I9 u$ A$ m5 B%距离矩阵 d2 I$ r& F9 |, r+ y/ [! u
sj=sj0*pi/180;
1 q) ?2 f! f( a5 a, [d=zeros(102);
& [( V k- n: x5 gfor i=1:101
. B: F$ i3 G2 G9 U! I8 u f( v for j=i+1:102
0 \) L% F# L2 ^( D temp=cos(sj(i,1)-sj(j,1))*cos(sj(i,2))*cos(sj(j,2))+sin(sj(i,2))*sin(sj(j,2));
) Z5 j; r( }9 v$ M( f' m d(i,j)=6370*acos(temp);: [2 D, h' D% O1 E0 R6 s9 n
end
! L* }: T: v* v0 Q1 j0 v+ hend. R+ k4 E4 Q- l) ]
d=d+d';L=102;w=50;dai=100;; q9 }7 r9 B5 f1 v' N
%通过改良圈算法选取优良父代 A
' @5 i2 T$ j6 O" _- C8 N- T' I& I. q0 Afor k=1:w
- h( D' Q3 d* [( Q c=randperm(100);3 s- J2 e7 h& P$ L
c1=[1,c+1,102];
9 U0 k. H# |" I) l flag=1;
1 p& f" ?) R+ Y0 V$ h: O while flag>0+ V/ f& e8 n+ T) v2 N0 n. ~
flag=0;
/ O, o, @8 Q4 J& Z for m=1-3
3 W, {, M7 A: r9 K6 P. o for n=m+2-1( t0 a- u7 P. i a0 d I
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))
. B$ ~" E: P$ ^+ d0 d$ F' n, V flag=1;% `; `6 M a3 E% k6 w
c1(m+1:n)=c1(n:-1:m+1);
0 q$ y* A0 T9 S8 b end/ t: J6 u/ O& s: w. C
end d8 F0 q, G |
end
8 F8 I8 a8 B; W end$ W0 @7 A9 X; T) O6 j7 C$ {, s
J(k,c1)=1:102;
* h w: z; C. l) u9 P1 _end
# P0 o, f$ h% V6 uJ=J/102;
" n0 v7 @1 \3 T5 rJ(:,1)=0;J(:,102)=1;& n0 |& G& H" y/ o1 q: U
rand('state',sum(clock));/ c# d" r6 p0 Q/ R: c8 ^/ `
%遗传算法实现过程
+ t# i1 M% I0 m- y( dA=J;% s3 ~! V; ^0 [4 P% ?' j) t! `
for k=1:dai %产生 0~1 间随机数列进行编码; w, g- L6 K! n, f% ?: a
B=A;
4 l% u+ Q# ~7 ? c=randperm(w);
0 S, v3 @8 ~, d% {6 ?% Y%交配产生子代 B) b8 Z. e; r" d* T
for i=1:2:w
- A. c4 H6 r# X, ` F=2+floor(100*rand(1));. z/ y7 t9 `+ j1 e' g: [+ \# Q- g9 x, E
temp=B(c(i),F:102);
& v* s3 A6 t4 j% V! s7 L B(c(i),F:102)=B(c(i+1),F:102);
$ g- |& R! }6 S9 y2 z ]4 H B(c(i+1),F:102)=temp;: Q q( T. x1 O
end
/ K- D. L6 L3 |/ P4 | s%变异产生子代 C
( M3 z3 F# V0 ?' l. P! c& X, rby=find(rand(1,w)<0.1);
- Q K, S e/ v4 Vif length(by)==00 w+ v" E Q/ J
by=floor(w*rand(1))+1;6 y6 ?) L0 g. r2 v6 T' k [: _# U( J
end. M% t, W5 @+ N. P# z" C2 F
C=A(by,;8 k, W0 U" c( ~4 n5 d! D4 u q- d) I
L3=length(by);
: Q* r6 N" M& E1 u/ \for j=13" V4 G+ ~1 T& e9 [" g \
bw=2+floor(100*rand(1,3));
( R+ P& |, W& g3 G! o; r: Y bw=sort(bw);
2 J, Y/ s1 [. A9 }9 w- F0 r C(j,=C(j,[1:bw(1)-1,bw(2)+1:bw(3),bw(1):bw(2),bw(3)+1:102]);
% H h* l' z4 F) rend
% w* u/ ~: `5 H1 t) ~ G=[A;B;C];
7 W# F7 m- u* W D, x TL=size(G,1);
1 S2 @( S$ h: w8 h %在父代和子代中选择优良品种作为新的父代9 K) z3 ^+ z/ a4 d! f) C- @2 E
[dd,IX]=sort(G,2);temp(1:TL)=0;
* q1 H. a7 T2 t( M0 F8 D for j=1:TL- c" y0 L0 e. F/ ^5 z* s; }; n: L
for i=1:101
/ ?9 t5 @2 b* b temp(j)=temp(j)+d(IX(j,i),IX(j,i+1));8 _& T# ^1 W9 t) H" q! z
end
! T3 U L2 _, `% T end* B( I. g8 L; `4 x/ { ^
[DZ,IZ]=sort(temp);( H* j, g' Y- T7 K% a
A=G(IZ(1:w),;
' @7 V6 J6 Y+ U) [) O+ A3 T9 Kend
. w% V: n+ l& Cpath=IX(IZ(1),3 Q0 t7 E- E p3 \/ y# {# Z
long=DZ(1)4 z# Z9 c4 R6 E+ }$ u9 w
toc
: P7 ?& o9 p3 Z, M& D$ Wxx=sj0(path,1);yy=sj0(path,2);
+ H( O+ {* ^7 c$ e- y5 N! f2 |% Qplot(xx,yy,'-o')
7 |5 ]9 F( n5 N) X0 M+ G5 I- P( Q' ~
计算结果为 40 小时左右。其中的一个巡航路径如图 2 所示。6 y7 v/ x/ p) W5 h3 M
" l" l% q* H) a* l7 d' Z' l0 a
2 b% ^' ]3 ^; {7 F7 A
6 k3 \6 N1 R5 r2 H————————————————/ ^ b' X5 C! d6 X1 U; Z8 L
版权声明:本文为CSDN博主「wamg潇潇」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
/ L- f) E3 Q C1 T& r6 a+ S原文链接:https://blog.csdn.net/qq_29831163/article/details/894595030 z0 w! u! X6 _: j9 i; W6 R
, d- N7 R2 F1 k; j4 |% V! o
* B5 i2 D# L% Y
|
zan
|