小生境帕累托遗传算法（NPGA）

一、算法简介

NPGA（Niched Pareto Genetic Algorithm） 是由 Horn、Nafpliotis 和 Goldberg 于 1994 年提出的早期多目标遗传算法。
它在多目标优化中引入了 小生境技术（Niching） 或 共享函数（Fitness Sharing），
用于保持 Pareto 前沿上解的多样性，防止解聚集在局部区域。

其核心思想是：

“用支配关系进行选择，用共享函数保持多样性。”

---

二、算法核心：小生境共享机制

1. 研究动机

在多目标优化中，算法往往会收敛到 Pareto 前沿的一小段区域，
导致前沿分布不均，缺少多样性。
NPGA 为此引入了 共享函数机制，惩罚拥挤区域，鼓励稀疏区域。

---

2. 小生境共享思想

每个个体 $x_i$ 在目标空间中都有一个向量：

$$F(x_i) = [f_1(x_i), f_2(x_i), \dots, f_m(x_i)]$$

个体之间的“接近程度”用距离度量：

$$d_{ij} = \|F(x_i) - F(x_j)\|$$

如果两个个体的目标值相近，则它们位于同一“小生境”（niche）。
算法将削弱这些密集区个体的适应度，使得解能在整个 Pareto 前沿上均匀分布。

---

3. 共享函数（Sharing Function）

定义如下：

$$sh(d_{ij}) = \begin{cases} 1 - \left( \dfrac{d_{ij}}{\sigma_{share}} \right)^\alpha, & d_{ij} < \sigma_{share} \\ 0, & d_{ij} \ge \sigma_{share} \end{cases}$$

• $\sigma_{share}$：共享半径（控制“邻近”的范围）
• $\alpha$：衰减参数，常取 $1$ 或 $2$

该函数描述了解的相似程度：距离越近，$sh(d_{ij})$ 越大。

---

4. 共享数（Niche Count）

每个个体的共享数定义为：

$$m_i = \sum_{j=1}^N sh(d_{ij})$$

$m_i$ 表示该个体周围有多少邻居。
$m_i$ 越大，说明该区域越拥挤。

---

5. 修正适应度（Shared Fitness）

在 NPGA 中，共享数用于调整个体的“生存机会”：

$$f'_i = \frac{f_i}{m_i}$$

或在锦标赛选择中：

• 若两解的支配关系相同，则比较 $m_i$；
• $m_i$ 小（稀疏区）的个体更容易胜出。

从而实现了解的均匀分布与多样性保持。

---

三、参数设置建议

参数	含义	推荐取值
$\sigma_{share}$	小生境半径	0.1 ~ 0.3（目标空间归一化后）
$\alpha$	共享函数指数	1 或 2
$p_c$	交叉概率	0.8 ~ 0.9
$p_m$	变异概率	0.01 ~ 0.1
$	C	$

---

四、NPGA 算法流程（简化）

1. 初始化种群 $P^{(0)}$
2. 计算目标函数值
3. 选择操作（Pareto锦标赛）：
   • 随机选两个个体 $a,b$
   • 随机取一参考集 $C$
   • 若 $a$ 被 $C$ 支配而 $b$ 未被支配，则选 $b$；反之亦然
   • 若两者支配情况相同，则比较其共享密度 $m_i$
     稀疏区个体优先
4. 交叉与变异生成子代
5. 更新种群并重复步骤 2–4
6. 输出非支配解集

---

五、Python 示例：共享函数部分

import numpy as np

def sharing_distance(F, sigma_share=0.2, alpha=1):
    """计算每个个体的小生境密度 m_i"""
    N = len(F)
    m = np.zeros(N)
    for i in range(N):
        for j in range(N):
            d = np.linalg.norm(F[i] - F[j])
            if d < sigma_share:
                m[i] += 1 - (d / sigma_share) ** alpha
    return m

# 示例：3个解在目标空间的距离
F = np.array([[0.1, 0.9],
              [0.2, 0.8],
              [0.8, 0.2]])
m = sharing_distance(F)
print("小生境密度 m_i =", m)

输出示例：

小生境密度 m_i = [1.7, 1.6, 1.0]

可见前两个解靠得近，密度高；第三个解独立，密度低。

六、总结

• NPGA 的关键创新在于：
  在多目标进化中引入了“小生境共享机制”保持解集多样性。
• 共享函数通过距离衡量相似度，
  并惩罚密集区个体，奖励稀疏区个体。
• 它为后来的 NSGA 与 NSGA-II 的“拥挤距离”机制 奠定了基础。