非支配快速排序算法中的拥挤度计算公式
时间: 2023-10-23 20:44:48 浏览: 41
对于非支配快速排序算法中的拥挤度计算公式,其计算方式如下:
假设有m个个体正在进行非支配排序,并且要在第i个目标函数上进行排序。对于第i个目标函数而言,拥挤度的计算方式为:
1. 将m个个体按照第i个目标函数的值从小到大排序;
2. 将第i个目标函数值最小的个体和第i个目标函数值最大的个体拥有的拥挤度设置为∞;
3. 计算其他个体的拥挤度,采用以下公式:拥挤度= (Max_i-Min_i)/(f_k^i(M+1)-f_k^i(m-1));
其中,Max_i和Min_i分别为第i个目标函数值最大和最小的个体在排序后经过第i个目标函数值排序后的第i个目标函数值,f_k^i代表第i个目标函数值为f_k的个体,m代表当前正在进行非支配快速排序的个体数,即m为已排序的个体数加上当前正在排序的个体数,M代表总的个体数,即M为已排序的个体数加上所有待排序的个体数。
希望可以解决您的问题!
相关问题
用python语言写快速非支配排序算法中拥挤距离的代码
以下是用Python语言实现快速非支配排序算法中拥挤距离的代码:
```python
def crowding_distance_sort(population):
n = len(population)
m = len(population[0].fitness.values)
for i in range(n):
population[i].distance = 0
for i in range(m):
population.sort(key=lambda x: x.fitness.values[i])
f_min = population[0].fitness.values[i]
f_max = population[-1].fitness.values[i]
population[0].distance = np.inf
population[-1].distance = np.inf
for j in range(1, n - 1):
population[j].distance += (population[j + 1].fitness.values[i] - population[j - 1].fitness.values[i]) / (f_max - f_min)
population.sort(key=lambda x: x.distance, reverse=True)
return population
```
其中,population是一个个体列表,每个个体都有一个fitness属性,代表其适应度值,以及一个distance属性,代表其拥挤距离。该函数会对每个个体的distance属性进行更新,并且返回按照拥挤距离排序后的个体列表。
该算法的思路是对于每个维度,将所有个体按照该维度的适应度值进行排序,并计算每个个体的拥挤距离。拥挤距离的计算方法是将该个体前后两个个体在该维度的适应度值之差除以该维度最大适应度值和最小适应度值之差的和。最后,将所有个体按照拥挤距离从大到小排序即可。
非支配快速排序遗传算法
非支配排序遗传算法(Non-dominated Sorting Genetic Algorithm, NSGA)是一种基于Pareto最优概念的遗传算法。它通过将种群中的个体进行非支配排序,找到种群中的非支配解集,并根据解集中个体的拥挤度进行排序。这样可以帮助我们在多目标优化问题中找到一组非支配解,即没有其他解能同时在所有目标上优于它们。
NSGA主要包括以下步骤:
1. 初始化种群:随机生成初始解集作为种群。
2. 个体评价:计算每个个体在目标函数上的适应度。
3. 非支配排序:对种群中的个体进行排序,将它们划分为不同的非支配层级。
4. 计算拥挤度:计算每个个体的拥挤度,用于后续的排序。
5. 选择操作:根据非支配排序和拥挤度进行选择,选择出新一代的个体。
6. 交叉操作:对选出的个体进行交叉操作,生成子代个体。
7. 变异操作:对子代个体进行变异操作,引入新的基因组合。
8. 更新种群:用新一代个体替换旧的个体,形成下一代种群。
9. 终止条件判断:判断是否满足终止条件,如果满足则结束算法,否则返回步骤2。