非支配排序

一、非支配排序算法

非支配排序算法（Non-dominated Sorting Algorithm）是一个拥有多目标函数的优化问题中常用的解决方法。该算法能够将目标函数优化问题转化成一系列非支配解构成的集合，进而为解决者提供一系列具备不同权衡考虑方式的可行解。

// 非支配排序伪代码
for (i=1; i<=N; i++)
{ 
    S[i] = empty;
    n[i] = 0;
    for (j=1; j<=N; j++)
    {
        if (dominates(p[i],p[j]))
        {
            S[i].push(j);
        }
        else if (dominates(p[j],p[i]))
        {
            n[i] ++;
        }
    }
    if (n[i] == 0)
    {
        rank[i] = 1; // rank 1 代表第一层非支配
        F[1].push(i);
    }
}

二、非支配排序是否需要分层

非支配排序不需要分层，但是分层可以使排序过程更加直观和易于理解。分层实现的方式有多种，最常用的是将非支配集合中维度最小的值归为同一层。

// 非支配排序实现分层伪代码
for (i=1; i<=N; i++)
{ 
    S[i] = empty;
    n[i] = 0;
    for (j=1; j<=N; j++)
    {
        if (dominates(p[i],p[j]))
        {
            S[i].push(j);
        }
        else if (dominates(p[j],p[i]))
        {
            n[i] ++;
        }
    }
    if (n[i] == 0)
    {
        rank[i] = 1;
        F[1].push(i);
    }
}
for (i=1; i<=N; i++)
{
    while (!F[i].empty())
    {
        int p = F[i].front();
        F[i].pop();
        for (j=0; j<S[p].size(); j++)
        {
            int q = S[p][j];
            n[q] --;
            if (n[q] == 0)
            {
                rank[q] = i+1;
                F[i+1].push(q);
            }
        }
    }
}

三、非支配排序原理

非支配排序原理主要包括支配和非支配。在多目标函数优化问题中，当一个解能够同时满足多个目标函数时，该解被称为非支配解，而同时只有一个目标函数得到最优解的解则被称为支配解。非支配排序的主要目的就是寻找一系列非支配解，这些解在多个目标函数优化问题中都没有被其它更优解所支配。

四、非支配排序图

下面是一个简单的案例，以帮助读者更好的理解非支配排序算法。我们假设有如下图所示三个点，点的坐标分别为(2，6)、(4，2)和(6，4)。

// 非支配排序图伪代码
import matplotlib.pyplot as plt

X = [[2,6], [4,2], [6,4]]

plt.scatter(X[:,0], X[:,1], s=100, edgecolors='none')
plt.show()

五、非支配排序遗传算法

非支配排序遗传算法（Non-dominated sorting genetic algorithm）是遗传算法的一种，在求解多目标函数优化问题时，非支配排序遗传算法可以对所有满足条件的解进行排序、选择、交叉和变异，从而求出拥有多个目标函数的优化问题的最优解。

// 非支配排序遗传算法伪代码
// 选择
for (i=1; i<=N; i++)
{
    int r1 = RandInt(1, N);
    int r2 = RandInt(1, N);
    if (rank[r1]  rank[r2])
    {
        P1 = r2;
    }
    else
    {
        if (crowd[r1] > crowd[r2])
        {
            P1 = r1;
        }
        else
        {
            P1 = r2;
        }
    }
}

六、非支配排序英文

Non-dominated Sorting

七、非支配排序粒子群

非支配排序粒子群是一个用于求解多目标函数的全局优化问题的一种算法，它通过将非支配排序和粒子群算法相结合，来实现查找多个目标函数下的全局最优解。在该算法中，每个粒子被视为一个可行解，并在多个目标函数下进行评估和排序。

// 非支配排序粒子群算法伪代码
for (i=1; i<=N; i++)
{
    for (j=1; j<=N; j++)
    {
        if (dominates(p[i],p[j]))
        {
            S[i].push(j);
        }
        else if (dominates(p[j],p[i]))
        {
            n[i] ++;
        }
    }
    if (n[i] == 0)
    {
        rank[i] = 1;
        F[1].push(i);
    }
}
for (i=1; i<=N; i++)
{
    while (!F[i].empty())
    {
        int p = F[i].front();
        F[i].pop();
        for (j=0; j<S[p].size(); j++)
        {
            int q = S[p][j];
            n[q] --;
            if (n[q] == 0)
            {
                rank[q] = i+1;
                F[i+1].push(q);
            }
        }
    }
}

八、非支配排序示意图

九、快速非支配排序

快速非支配排序（Fast Non-dominated Sorting）是非支配排序算法的改进版。它通过将算法的时间复杂度从O(N^2)优化到O(Nlog(N))，使得快速非支配排序比传统的非支配排序算法更加快速和实用。

// 快速非支配排序伪代码
for (i=1; i<=N; i++)
{
    for (j=i+1; j<=N; j++)
    {
        if (dominates(p[i],p[j]))
        {
            S[i].push(j);
        }
        else if (dominates(p[j],p[i]))
        {
            S[j].push(i);
        }
    }
}
for (i=1; i<=N; i++)
{
    if (size[i] == 0)
    {
        rank[i] = 1;
        Q.push(i);
    }
}
int k = 1;
while (!Q.empty()) 
{
    int i = Q.top();
    Q.pop();
    F[k].push_back(i);
    for (j=0; j= m)
    {
        k ++; // 进入下一层
    }
}