多目标优化拥挤距离计算
多目标优化拥挤距离计算
演化计算与人工智能
发布于 2020-08-14 00:23:20
发布于 2020-08-14 00:23:20
多目标优化拥挤距离计算
- 拥挤距离主要是维持种群中个体的多样性。具体而言，一般来说是指种群按照支配关系[1]进行非支配排序[2]后,单个 Rank 层中个体的密集程度。常用于支配关系的多目标算法中，例如NSGA-II[3].
- 主要步骤如下：
- 取单个前沿中个体按照一个目标上的值从小到大排序
- 将最大目标值作为 max,最小目标值保留作为 min。并且这两个极值点的拥挤距离都被设置为 inf 即无穷大。因此注意，一个层中可能有多个具有 inf 的点，即如果层中有多个点在至少一个目标上相等，并且最大或最小，那么这些点的拥挤距离都是无穷大！！因为目标上呈现垂直的关系也是属于非支配的关系！！如果出现这种情况，说明你算法的多样性很烂！~或者在某些算法早期可能出现这种情况
- 在这个目标上计算每个个体最相邻个体之间的距离，即 i-1 和 i+1 的目标值的差。并使用 max 和 min 对次值进行归一化。
- 遍历目标，将目标上已经归一化的拥挤距离相加。
- 进入下一层 front 前沿
- 拥挤距离越大越好，最后按照拥挤距离重新排序各层，进而排序种群
matlab
function CrowdDis = CrowdingDistance(PopObj)
% Calculate the crowding distance of each solution in the same front
[N,M] = size(PopObj);
CrowdDis = zeros(1,N);
Fmax = max(PopObj,[],1);
Fmin = min(PopObj,[],1);
for i = 1 : M
[~,rank] = sortrows(PopObj(:,i));
CrowdDis(rank(1)) = inf;
CrowdDis(rank(end)) = inf;
for j = 2 : N-1
CrowdDis(rank(j)) = CrowdDis(rank(j))+(PopObj(rank(j+1),i)-PopObj(rank(j-1),i))/(Fmax(i)-Fmin(i));
end
end
endjmetal
public void crowdingDistanceAssignment(SolutionSet solutionSet, int nObjs) {
int size = solutionSet.size();
if (size == 0)
return;
if (size == 1) {
solutionSet.get(0).setCrowdingDistance(Double.POSITIVE_INFINITY);
return;
} // if
if (size == 2) {
solutionSet.get(0).setCrowdingDistance(Double.POSITIVE_INFINITY);
solutionSet.get(1).setCrowdingDistance(Double.POSITIVE_INFINITY);
return;
} // if
// Use a new SolutionSet to evite alter original solutionSet
SolutionSet front = new SolutionSet(size);
for (int i = 0; i < size; i++) {
front.add(solutionSet.get(i));
}
for (int i = 0; i < size; i++)
front.get(i).setCrowdingDistance(0.0);
double objetiveMaxn;
double objetiveMinn;
double distance;
for (int i = 0; i < nObjs; i++) {
// Sort the population by Obj n
front.sort(new ObjectiveComparator(i));
objetiveMinn = front.get(0).getObjective(i);
objetiveMaxn = front.get(front.size() - 1).getObjective(i);
// Set de crowding distance
front.get(0).setCrowdingDistance(Double.POSITIVE_INFINITY);
front.get(size - 1).setCrowdingDistance(Double.POSITIVE_INFINITY);
for (int j = 1; j < size - 1; j++) {
distance = front.get(j + 1).getObjective(i) - front.get(j - 1).getObjective(i);
distance = distance / (objetiveMaxn - objetiveMinn);
distance += front.get(j).getCrowdingDistance();
front.get(j).setCrowdingDistance(distance);
} // for
} // for
} // crowdingDistanceAssing参考资料
[1]支配关系: https://blog.csdn.net/u013555719/article/details/91356078
[2]非支配排序: https://blog.csdn.net/u013555719/article/details/105564693
[3]NSGA-II: https://blog.csdn.net/u013555719/article/details/82936554
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-17，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录