模块一·评价:
挑出好的父代,对遗传算法是否收敛具有决定性的作用。只有找到好的父代才能让子代变得更好。然而,咱们也应该意识到,如果让一个最好的父代占据了所有交配资源,那么要不了几代时间,所有人都会长得和他一模一样,这样就失去了种群的多样性也很有可能只是找到了一个‘看似’最好的结果(局部最优解)。一个好的遗传算法,一定会在加快收敛速度和保持多样性(避免局部解)上做思考和权衡。
那么首先,怎么评价一个个体并给所有个体进行排序呢?很简单,对这个个体在优化目标上的表现打分就好。例如,我们觉得1只长颈鹿要在族群里存活下来,最需要具备的特征是脖子要长,那我们就对这只长颈鹿的脖子长度进行打分。打分有两种方式。假设我们有三只长颈鹿,分别脖子长1米,1.01米,0.3米。
·记录排名,这时候1.01米长的排在第一名,1米的排在第二名,而0.3米的排第三名。
·记录绝对长度,1米长就是1米长,1.1米就是1.1米,0.3米就是0.3米。
发现没,如果是第一种打分方式,ABC三只长颈鹿在排序上的相对距离是均等的。这样的结果是损失了一些非常有用的信息。例如一棵1米高的树有100片叶子,那按照第二种情况判断,就是脖子长1米和1.1米的长颈鹿把树上的叶子都吃光了也不会给0.5米的长颈鹿剩下啥。但是按照第一种情况呢?第三名的长颈鹿说不定还能被分到20片叶子吃。这是不合情理的。
所以,通过计算每个个体健康值(fitness value)来记录个体之间实际距离的评价方式是更真实的评价方式。
模块二·挑选
在完成了对每个父代个体的评价后,我们接下来就要随机的挑选个体准备交配了。这里简单介绍三种方法:
-
赌场轮盘法:在一张桌子上,放一个圆形的轮盘,轮盘上分割出很多大小不一的扇形区域,然后有一个固定在桌上的指针。游戏者转动轮盘,轮盘停止时指针会指向其中的某一块扇形区域。目标选中。
用计算机实现的话可分为以下5步:
1. 对所有个体的健康值做规范化处理:求出父代所有个体的健康值总和,再把每个个体的健康值除以总和。这样的目的是为了让规范化后的健康值总和等于1。
2. 对个体根据健康值降序排序,并生成列表。(轮盘扇形区域画好了)
3. 在0-1之间随机生成一个数字R。(开始转轮盘了)
4. 从列表头开始叠加健康值,直到健康值叠加的和等于R。(轮盘停止)
5. 叠加的最后一个个体即为挑选出的个体。(查看指针指向区域)
挑选的过程虽然完全随机,每个父代个体被选中的概率也就是在轮盘上占的扇形区域大小其实是不一样的。
当然这样挑选方式也有可能是很不幸的最优秀的个体每次都不会被选到。那为了解决这样的问题,我们可以在轮盘的几个角度都布上指针。这样每转一次轮盘,我们就能得到几个距离相等的结果,这也保证了最健康的个体一定会被选中。
-
奖励法:在奖励法里,被选中的概率是和从先祖那里积累起来的奖励有关的。大概就是官二代或者军三代的概念了。拥有了历史的记忆,能加速我们朝正确梯度方向收敛的速度。当然其需要的存储空间也更大。 -
角斗场法:顾名思义,就是随机的抽取几个人把他们丢到角斗场里,相互pk直到最后剩下来最强壮的一个。这种方法的优势在于竞争的压力是可以通过选择参赛人数的多少来自由调节的。同时,也非常适用于并行计算。
模块三·交配
交配过程如前文提到,会有几种不同的基因生成方式– 交叉,变异,复制。
-
A. 交叉
在选出了一对父母后,我们会通过对父母的染色体的某一部分进行交叉互换,来形成新的基因序列并完成交配。在拼接时我们有不同的方式:
对于2进制变量,我们主要有单点交叉,多点交叉和随机交叉等方式。
单点交叉-
多点交叉-
随机交叉-
对于实数变量,我们的交叉方式是:离散交换,连线式插值和区域性插值。
所谓离散交换就是父母的同一变量直接交换。假设现在有一组2维变量:{鼻子,眼睛}。那离散交换就只有4种可能:
1. 你的鼻子 = 你爸的鼻子,你的眼睛 = 你爸的眼睛。
2. 你的鼻子 = 你妈的鼻子,你的眼睛 = 你妈的眼睛。
3. 你的鼻子 = 你爸的鼻子,你的眼睛 = 你妈的眼睛。
4. 你的鼻子 = 你妈的鼻子,你的眼睛 = 你爸的眼睛。
那区域式插值是什么呢?就是在你的鼻子和眼睛在你爸和你妈规定的这个大小范围内取值。你的眼睛有可能比你妈小点儿但比你爸大点儿。
和区域式对应的还有连线式,这种方式比较把原本的区域取值限定的范围更窄了。
值得注意的是我们可以对交叉的空间大小进行调节:意思是你爸黑,你妈肤色白,你的肤色可能比你爸还黑一点,不一定就非得是黑和白中间的颜色。
-
B. 突变
突变就是,你爸妈明明都很矮,结果生出你直接长的比姚明还高。
突变是为了维持基因的多样性,探索更多的可能性。但是突变的概率一般应该设置的非常小。过大的突变率会让破坏程序,使其随机混乱无法收敛。一般对于实数的变异可分为随机和高氏变异等。在高氏变异里,我们可以设置放大倍数和收缩速率。放大倍数可以用来控制变异空间范围的大小,越大的话种群的多样性越好。在初期的几代搜索里,有一个比较宽广的搜索范围很重要。但随着遗传代数的增加,我们不再需要很大的变异范围,这时候通过收缩速率的调节我们又可以实现变异空间的缩小。
改进版本
到这里,遗传算法的大体介绍就已经完成了。当然,这只是最经典的遗传算法。随着越来越多的应用,研究者们又提出了很多改进的方式。以现今非常流行的多目标优化的遗传算法NSGA-II为例,它就提出了以下的三种改进方式:
1. 整体上看,引入预测反馈的概念,把通过经典手段得到的(伪)子代和父代再次混合排序,并选出优质部分完成(真)子代生成,以实现加速收敛和保留种群多样性的目的。
2. 在排序上,针对多目标排序时的计算复杂度进行优化,实现快速的支配分层;
3. 在保存种群多样性上,引入拥挤度的概念,来更好的表现同一层个体间不同的分布位置;
实例:电机优化
在明白了遗传算法的原理后,我们就可以用一门语言来实现它并且用它来优化电机了:
在文章里作者需要优化这种标贴式电机的齿槽转矩。下图右侧是优化之前,左侧是优化之后,可以看到每一块磁钢的大小不变,但是位置发生了变化。
作者是通过调整每一块磁钢所在的位置来实现的优化。总共八块磁钢,每块磁钢被定义了从0到18度的变化范围,1度每步。也就是说如果是使用枚举法的话,我们大概要计算19的8次方,大约170亿次。因为是扫描齿槽转矩,网格要密时间步长也要小。假设半个电周期的计算,我们需要大约半分钟。那要全部扫完的话,大约需要一台电脑连续不断的工作1.6万年。这显然是不现实的。当然,为了解决问题,我们也可以租用国家超算中心,用1.6万个cpu同时计算,这样我们就可以在一年的时间完成解算,假定一切稳定运行。
那如果采用优化算法的方式来解题呢?作者把种群大小定为100,最大进化代数设为200。仅仅通过20000次的迭代,也就是一周不到的时间就完成了计算。结果也是相当不错,齿槽转矩下降到了原来的25%。
来看在另一个案例:K. Yamazaki在文章里针对下图的电机,利用Rosenbrock的寻优方法定义了27个变量来寻找最低铁损的方案。我想平时我们设计电机时,用来优化的变量可能连他的1/5都不到吧。这,就是算法的强大:所以只有拥有了先进的优化算法,我们也才有可能在复杂的电机结构中找到理想的方案。
关于电机的优化算法,到今天还在不断的进化:例如前期结合统计学Taguchi方法后期结合surrogate方法的较NSGA-II收敛速度更快的多步遗传优化,还有已经完全不再需要预定义特定变量的‘古怪’算法-拓扑优化,还有遗传算法从出生开始的老对头-粒子群算法等等。这些有趣的东西,咱们后续有空再聊吧。
随着产品设计压力驱动下的多物理边界的耦合越来越紧密,电机设计的复杂度呈几何倍数的增加。我想,相比于一个精通电机理论有几十年设计经验的老专家,说不定胜出的一方会是配上了一台强劲的电脑和软件的一个懂得优化的年轻工程师。
当然电机设计外,遗传算法也被广泛应用在别的工程,经济,工业等等领域。
机器学习
优化算法仅仅是个开始,它和其它工具相结合将带来更大的设计革命。它的和神经网络相结合我们就可以来教机器怎样迅速通关马里奥或者自动驾驶货车:
通过两个例子,我们能够憧憬一下未来的电机设计,将越来愈多的依赖数据和AI。
结语
本文首先解释了什么是优化,然后描绘了其多样的应用场景。再带大家从整体上认识了遗传算法的关键步骤– 评价,选择,交配,再竞争。接着对每一个步骤涉及到的不同方法进行了相关的介绍。最后咱们还分析了优化算法在电机设计里的两处应用,看到了它的强大。
希望读完本文,‘优化软件’这个黑盒子已经变成了灰盒子,大家对电机设计的未来也有了一点新的认识。
引文:
Deb K , PratapA , Agarwal S , et al. A fast and elitist multiobjective genetic algorithm:NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2):0-197.
Ho S L , Chen N, Fu W N . An Optimal Design Method for the Minimization of Cogging Torques ofa Permanent Magnet Motor Using FEM and Genetic Algorithm. IEEE Transactionson Applied Superconductivity, 2010, 20(3):861-864.
Yamazaki K ,Togashi Y . Shape Optimization Procedure of Interior Permanent Magnet MotorsConsidering Carrier Harmonic Losses Caused by Inverters. IEEE Transactionson Magnetics, 2017:1-4.
Stanley K O ,Miikkulainen R . Evolving Neural Networks through Augmenting Topologies.Evolutionary Computation, 2002, 10(2):99-127.
死磕自己,服务大家,我是核动力蜗牛,每周分享技术干货。