非支配排序

一、非支配排序算法

非支配排序算法（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 ++; // 進入下一層
    }
}