优化算法 | 遗传算法之随机遍历抽样（附matlab代码）

pc8888888 · 发表于 2022-5-19 09:57

今天为各位讲解遗传算法（GA）中一种常见的选择算子-随机遍历抽样（Stochastic Universal Sampling，SUS）。因为SUS是基于轮盘赌选择（Roulette Wheel Selection，RWS）而改进的，所以首先介绍RWS，然后再介绍SUS。
▎轮盘赌选择（RWS）

在RWS中，首先将个体适应度值映射到轮盘中，个体的适应度值越大，其在轮盘中分配到的角度就越大，因此被选中的概率就越大。
假设有5个个体，各适应度值分别为[6.82,1.11,8.48,2.57,3.08]，总适应度值为22.06。分别计算各个适应度值占总适应度值之比，即为[0.31,0.05,0.38,0.12,0.14]。适应度值占比示意图和轮盘赌选择示意图分别如下图所示。

轮盘指针所指位置为个体3，此时执行一次轮盘赌选择操作所选择的个体为个体3。假设需要选择5个个体，则需转动5次转盘，每次转动轮盘指针所指位置即为被选择的个体。
▎随机遍历抽样（SUS）

从轮盘赌选择过程可以看出：如果需要选择N个个体，则需转动N次转盘。为了改进这一问题，SUS被提出。
在SUS中，如果需要选择N个个体，则只需一次生成N个等间距的标记指针位置，即可选择出N个个体。假设总适应度值为F，选择个体数目为N，则SUS具体步骤如下：
STEP1：计算指针的间距P=F/N；
STEP2：随机生成起点指针位置Start=[0~P之间的随机数]；
STEP3：计算各指针的位置Pointers=[Start+i*P(其中i=[0,1,...N-1])]；
STEP4：根据各指针位置，选择出N个个体。
▎SUS实例讲解

继续以上述例子为例，5个个体的适应度值分别为[6.82,1.11,8.48,2.57,3.08]，总适应度值为F=22.06。假设选择的个体数目为5，则SUS执行步骤如下：
STEP1：计算指针的间距P=F/N=22.06/5=4.41；
STEP2：假设随机生成起点指针位置Start=2；
STEP3：计算各指针的位置Pointers=[2+0*4.41,2+1*4.41,2+2*4.41,2+3*4.41,2+4*4.41]=[2,6.41,10.82,15.23,19.64]；
STEP4：根据各指针位置，选择出N个个体，选择的个体序号为[1,1,3,3,5]。
上述SUS执行过程如下图所示：

SUS matlab代码如下所示：
% 输入:
%FitnV 个体的适应度值
%Nsel 被选择个体的数目
% 输出:
%NewChrIx 被选择个体的索引号
function NewChrIx = Sus(FitnV,Nsel)
% Identify the population size (Nind)
[Nind,ans] = size(FitnV);
% Perform stochastic universal sampling
cumfit = cumsum(FitnV);
trials = cumfit(Nind) / Nsel * (rand + (0:Nsel-1)&#39;);
Mf = cumfit(:, ones(1, Nsel));
Mt = trials(:, ones(1, Nind))&#39;;
[NewChrIx, ans] = find(Mt < Mf & [ zeros(1, Nsel); Mf(1:Nind-1, :) ] <= Mt);
% Shuffle new population
[ans, shuf] = sort(rand(Nsel, 1));
NewChrIx = NewChrIx(shuf);
% End of function
end
▎参考

[1]Baker J E. Reducing bias and inefficiency in the selection algorithm[C]//Proceedings of the second international conference on genetic algorithms. 1987, 206: 14-21.
[2]Pencheva T, Atanassov K, Shannon A. Modelling of a stochastic universal sampling selection operator in genetic algorithms using generalized nets[C]//Proceedings of the tenth international workshop on generalized nets, Sofia. 2009: 1-7.
咱们下期再见
▎近期你可能错过了的好文章：
新书上架 | 《MATLAB智能优化算法：从写代码到算法思想》
优化算法 | 灰狼优化算法（文末有福利）
优化算法 | 鲸鱼优化算法
遗传算法（GA）求解带时间窗的车辆路径（VRPTW）问题MATLAB代码
粒子群优化算法（PSO）求解带时间窗的车辆路径问题（VRPTW）MATLAB代码
▎作者新书购买链接

京东自营购买链接
当当自营购买链接

		自动登录	找回密码
密码			立即注册

优化算法 | 遗传算法之随机遍历抽样（附matlab代码）

本帖子中包含更多资源