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

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

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

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




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

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

继续以上述例子为例,5个个体的适应度值分别为,总适应度值为F=22.06。假设选择的个体数目为5,则SUS执行步骤如下:
STEP1:计算指针的间距P=F/N=22.06/5=4.41;
STEP2:假设随机生成起点指针位置Start=2;
STEP3:计算各指针的位置Pointers==;
STEP4:根据各指针位置,选择出N个个体,选择的个体序号为。
上述SUS执行过程如下图所示:


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

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

京东自营购买链接
当当自营购买链接
页: [1]
查看完整版本: 优化算法 | 遗传算法之随机遍历抽样(附matlab代码)