. E0 ` h! y5 o
; _" H. V. A+ w! g* u% l
从中选出具有更高优先级的结点6作为结点1下一步需要访问的结点。 ( f6 w) D5 p9 Q4 Z- F' i* m1 K 2 Y. g4 q& i2 I( ~以此类推,最终得到完整的访问路径为:. ~% a- B. U( E6 o8 o
! ]" V8 O$ E: l( G# E
1 → 3 → 6 → 7 → 8 → 10。 , I7 d+ @& ~/ ]% i# I2 t& i+ b' x* |4 a, ~& o( V3 b
有了解码得到路径,如何求个体的适应度?5 {6 y7 O0 ?' B) [+ K- {
3 Q& s! w, d- N. P' v$ b% }1 q想要求个体的适应度,首先要定一个优化目标。本题是要让路径最短,于是我们便要根据访问结点求出路径长度,把这个作为优化目标。有了优化目标,便可利用基于目标函数值排序的适应度分配(ranking)求出适应度值。当然,这类单目标优化问题也可以直接让个体的适应度等于优化目标函数值(即路径长度)。而路径长度即为访问路径上各条有向边的权值之和。 & o n) K1 z Q: q0 | $ h6 S. X. F: l3 ^代码实现:1 H% o2 o u" B/ ^9 C0 l
- G9 `8 o5 w1 I# C. n1 k# L! [首先编写问题类,把待优化模型写在问题类中。然后编写执行脚本,调用“soea_SEGA_templet“(增强精英保留的遗传算法模板)进行进化优化。该算法模板的源码及算法流程详见: / f( e" d. B9 Y, W0 ~) r: d' c! n! Y, x. ^
https://github.com/geatpy-dev/geatpy/blob/master/geatpy/templates/soeas/GA/SEGA/soea_SEGA_templet.py# o. v, K: t0 E) }6 ~6 z
4 Y3 E/ n8 [% {由于本题比较简单,故用4个个体、10代的进化即可得到很好的结果。完整的实验代码如下: ( z" u0 ?0 L0 D% x2 N4 Z; U F/ }* n
# -*- coding: utf-8 -*- 7 A8 p) Q8 M! `+ I5 b7 C3 n. bimport numpy as np 1 p, Y& I8 ^, c* Vimport geatpy as ea! q3 p' p/ {! V( w E( T
class MyProblem(ea.Problem): # 继承Problem父类7 d- `! F: E5 E7 u+ B: t7 p
def __init__(self): ' `) Y+ r Y( S& j+ r# b8 L name = 'Shortest_Path' # 初始化name(函数名称,可以随意设置) & P/ q# y$ ^- {- U4 }8 y# T j M = 1 # 初始化M(目标维数) $ o5 H; R2 R) U( j4 G' y2 P maxormins = [1] # 初始化maxormins(目标最小最大化标记列表,1:最小化该目标;-1:最大化该目标)0 q, L& }9 H6 A4 {8 G7 N/ `
Dim = 10 # 初始化Dim(决策变量维数) # X% Y& B ~, |- r varTypes = [1] * Dim # 初始化varTypes(决策变量的类型,元素为0表示对应的变量是连续的;1表示是离散的)7 i! n% t! F3 A" X* \
lb = [0] * Dim # 决策变量下界/ I! y7 N& s, k' }; j5 T Q- S
ub = [9] * Dim # 决策变量上界0 B2 _/ B O3 {% P( f; G
lbin = [1] * Dim # 决策变量下边界; g9 P: ^! j" X/ M4 K* |, W
ubin = [1] * Dim # 决策变量上边界1 i7 f+ F% z+ Q/ f* E- Q
# 调用父类构造方法完成实例化 , r- S$ F5 b4 ^' m ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin) 3 d: _7 y2 L" ?! t7 _0 ]2 G, {* T # 设置每一个结点下一步可达的结点(结点从1开始数,因此列表nodes的第0号元素设为空列表表示无意义) : Z8 t# s: H) B, o) q. r, j self.nodes = [[], [2,3], [3,4,5], [5,6], [7,8], [4,6], [7,9], [8,9], [9,10], [10]]0 V" O5 c) L: F4 ]
# 设置有向图中各条边的权重 / g* s0 A8 H5 Y6 V: a8 }6 J6 I self.weights = {'(1, 2)':36, '(1, 3)':27, '(2, 4)':18, '(2, 5)':20, '(2, 3)':13, '(3, 5)':12, '(3, 6)':23,8 M9 u, I: A8 `- ?' N$ _
'(4, 7)':11, '(4, 8)':32, '(5, 4)':16, '(5, 6)':30, '(6, 7)':12, '(6, 9)':38, '(7, 8)':20,8 @6 s! N& z6 O y0 v4 [& b
'(7, 9)':32, '(8, 9)':15, '(8, 10)':24, '(9, 10)':13}5 o! l* c+ V" C
def decode(self, priority): # 将优先级编码的染色体解码得到一条从节点1到节点10的可行路径 7 q J) T+ j4 y: R edges = [] # 存储边" E R; d! H/ u1 a# y& w
path = [1] # 结点1是路径起点( m5 l9 k' p2 o
while not path[-1] == 10: # 开始从起点走到终点+ N& ~9 v5 i, A! b) W* R/ u
currentNode = path[-1] # 得到当前所在的结点编号 . H/ H( `, M! q) h2 G/ Q nextNodes = self.nodes[currentNode] # 获取下一步可达的结点组成的列表2 C$ U q: n- P- D. g0 Y
if len(nextNodes) == 0:7 w$ s$ Z+ v2 {
raise RuntimeError("Error in decode: No way to go. (当前结点出度为0,无路可走。)") ; d; F4 F5 F' ~6 L- I2 \ chooseNode = nextNodes[np.argmax(priority[np.array(nextNodes) - 1])] # 从NextNodes中选择优先级更高的结点作为下一步要访问的结点,因为结点从1数起,而下标从0数起,因此要减去1 ) X6 j, I1 K8 ?# B path.append(chooseNode)' `5 }5 w0 z$ [' b- [3 `; R
edges.append((currentNode, chooseNode)) + j! @" F' ~& j) ~, u4 }0 g return path, edges: n/ K/ o; P. [" i; I. l6 c& e! F
def aimFunc(self, pop): # 目标函数- q- \5 @. x U* v
pop.ObjV = np.zeros((pop.sizes, 1)) # 初始化ObjV 8 g4 }$ Y! X w- ` for i in range(pop.sizes): 5 d' b3 _ m" [& \2 u priority = pop.Phen[i, :] ' ^( [9 ^( C' E9 Y7 \( n# d3 k path, edges = self.decode(priority) # 将优先级编码的染色体解码得到访问路径及经过的边. [$ T! x. {% @; r/ k
pathLen = 02 `1 C! p8 a( k, j
for edge in edges: 5 b, h% y. A4 [- ^; K, {' G key = str(edge) # 根据路径得到键值,以便根据键值找到路径对应的长度" ?( R% K! [: e& i' l3 f
if not key in self.weights: * z n! I* ?1 f' j. Z raise RuntimeError("Error in aimFunc: The path is invalid. (当前路径是无效的。)", path)0 d- \4 ?: Y! s
pathLen += self.weights[key] # 将该段路径长度加入 ' N. p* L- P' m) H3 k" m. x! m pop.ObjV = pathLen # 计算目标函数值,赋值给pop种群对象的ObjV属性% z4 \; l6 h2 `$ ^
: n7 r" V2 E- W* B* b1 X; l! _
if __name__ == "__main__":% ^. A! d% Q7 |0 v. @6 y0 U
problem = MyProblem() # 生成问题对象 8 Y8 c" C8 h" y+ l9 _' l. Z """=================================种群设置=================================""" N5 y8 U# C2 D1 M/ \' A Encoding = 'P' # 编码方式8 w% [( F, D7 G# U$ a
NIND = 4 # 种群规模 , z6 E* B ?9 i( ^) i Field = ea.crtfld(Encoding, problem.varTypes, problem.ranges, problem.borders) # 创建区域描述器; ?; m1 w# L# r4 ?5 q/ B
population = ea.Population(Encoding, Field, NIND) # 实例化种群对象(此时种群还没被初始化,仅仅是完成种群对象的实例化)+ k; e5 V1 w2 M2 X$ y$ x% f8 g
"""===============================算法参数设置==============================="""2 A/ J( Q6 r; V& X
myAlgorithm = ea.soea_SEGA_templet(problem, population) # 实例化一个算法模板对象 6 ]7 @- q4 r, Z( z9 g myAlgorithm.MAXGEN = 10 # 最大进化代数 : f# L+ U1 d i myAlgorithm.recOper = ea.Xovox(XOVR = 0.8) # 设置交叉算子 6 i9 D; E3 w: O. ~" @+ D myAlgorithm.mutOper = ea.Mutinv(Pm = 0.1) # 设置变异算子 : V, ?. a4 o" P) d5 Q$ G- @& T3 Z myAlgorithm.drawing = 1 # 设置绘图方式(0:不绘图;1:绘制结果图;2:绘制过程动画) 9 ?8 z. T1 T1 ^ """==========================调用算法模板进行种群进化=========================="""! u5 ]- F; |6 \$ v
[population, obj_trace, var_trace] = myAlgorithm.run() # 执行算法模板,得到最后一代种群以及进化记录器 ) D9 y7 b9 E( J3 j/ k- K* V population.save() # 把最后一代种群的信息保存到文件中 3 v; a! t: X1 M, W # 输出结果" E7 u" p. `1 \+ v' E" Y7 p
best_gen = np.argmin(obj_trace[:, 1]) # 记录最优种群是在哪一代 6 M9 V: q% p1 x1 i best_ObjV = np.min(obj_trace[:, 1]) . U" A: h7 S) j& e' i( m4 X. ? print('最短路程为:%s'%(best_ObjV))7 l: m* q+ a! @5 t: K0 h
print('最佳路线为:') 6 m! ^ e# V' ?& ~7 V best_journey, edges = problem.decode(var_trace[best_gen, :]) & B; [2 N J! M for i in range(len(best_journey)): : i9 m% [7 `- c print(int(best_journey), end = ' ')( C# p6 D! H. v
print() , P7 O' u- E% [2 b4 D8 e; _; |9 [: Z print('有效进化代数:%s'%(obj_trace.shape[0])) E" R ~( @5 ]3 k2 D( s; F
print('最优的一代是第 %s 代'%(best_gen + 1)) 2 N2 \3 X. z$ w: B print('评价次数:%s'%(myAlgorithm.evalsNum))* j I2 J) U7 X" {9 i2 j8 X
print('时间已过 %s 秒'%(myAlgorithm.passTime))6 h" \- g, y- b8 f- W
在有向图中表现为: 1 H- W/ r A- u* ?7 Q7 e! R/ v+ R. W, k% m
# y# q) ^8 ?' Y
4 ]- R4 v$ F6 r# r: y后记# n; N, a+ R" J% C" a
) a& ~9 x! F# b. h
值得注意的是:上面题目中的有向图并不存在回路,实际上,复杂的有向图往往会存在许多回路,此时需要进行一定的处理来避免陷入回路当中,即避免一直在回路上“打转”。处理方式有很多,例如在解码过程中对已经访问过的结点的有限度进行惩罚等等。这里暂时就不深入探讨了,待之后讲述无向图最短路径及机器人寻路问题时再展开叙述。 ; q. ?; N6 h9 M" x: _. D0 B2 @ C# i' Y8 Q. B% J U- }! I
最后回顾一下上一篇博客提到的”遗传算法套路“:* w1 q; C( w2 }; _: h# c
8 N: P+ `! `8 I8 Z6 h8 F1 `5 Q
% z. |. K5 O* e. Y7 ]
该套路实现了具体问题、使用的算法以及所调用的相关算子之间的脱耦。而Geatpy工具箱已经内置了众多进化算法模板类以及相关的算子,直接调用即可。对于实际问题的求解,只需关心如何把问题写在自定义问题类中就好了。 p. h9 _, f! n1 p, H8 Q- P b
% E4 W* [6 I3 }5 B9 Z- s
———————————————— # }$ k2 j( x3 b# a- M( o$ N0 b; P$ N9 M" H) s7 c X, I- Z