如何对二进制矩阵进行行子集划分以最大化‘唯一性’？

需求与参数定义 #

我们需要从二进制矩阵中选择行子集，核心目标是最大化列覆盖范围同时最小化重复行数，定义以下参数：

• p：被覆盖的列数（值越大越好）
• q：重复行数（值越小越好，计算公式：选中总行数 - 选中行的唯一数量）
• r：为增加p而引入重复行的惩罚系数

最终优化目标为最大化唯一性评分：score = p - q*r

示例说明 #

示例1（最优行子集：[2,3,4]） #

A = [
[1,0,0,0,0],
[0,0,0,0,0],
[1,0,1,0,0],
[0,1,0,1,0],
[0,0,0,0,1],
]

• p = 5（覆盖所有列）
• q = 0（无重复行）

示例2（最优行子集：[0,2,3]） #

B = [
[1,1,0,1,0],
[0,0,0,0,0],
[1,0,0,0,1],
[0,0,1,0,0],
[0,0,0,0,1],
]

• p = 5（覆盖所有列）
• q = 1（存在1个重复行）

示例3（最优行子集：[0,1]、[1,3]） #

C = [
[1,0,0,1,0],
[0,1,1,0,1],
[0,1,0,0,1],
[1,0,0,1,0],
[0,0,0,0,1],
]

非暴力实现方案 #

核心问题修正 #

先指出你测试代码中的关键错误：原代码计算p的方式len(set(selected_rows.flatten()))完全无效——二进制矩阵扁平化后仅包含0和1，集合长度最多为2，无法反映实际覆盖的列数。正确的p计算应为统计至少包含1个1的列的数量，即np.sum(np.any(selected_rows, axis=0))。

以下是基于Python库的可行实现方案：

1. 基于Platypus的单目标遗传算法 #

直接针对唯一性评分score = p - q*r做最大化优化，用二进制变量表示行的选中状态（更贴合问题本质）：

from platypus import NSGAII, Problem, Binary
import numpy as np

A = np.asarray([
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
])
r = 0.1  # 自定义惩罚系数

def objective(x):
    # 转换为布尔掩码筛选选中行
    selected_mask = np.array(x, dtype=bool)
    selected_rows = A[selected_mask]
    
    if len(selected_rows) == 0:
        return [-0]  # 未选行时评分为0
    
    # 计算覆盖列数p
    col_coverage = np.any(selected_rows, axis=0)
    p = np.sum(col_coverage)
    
    # 计算重复行数q
    unique_rows = set(tuple(row) for row in selected_rows)
    q = len(selected_rows) - len(unique_rows)
    
    # 返回负评分（适配算法默认最小化逻辑）
    return [-(p - r * q)]

# 定义问题：5个二进制变量（对应5行），1个优化目标
problem = Problem(5, 1)
problem.types[:] = Binary()
problem.function = objective
problem.directions[:] = Problem.MINIMIZE

# 运行遗传算法
algorithm = NSGAII(problem)
algorithm.run(10000)

# 提取最优解
best_sol = min(algorithm.result, key=lambda s: s.objectives[0])
selected_indices = [i for i, val in enumerate(best_sol.variables) if val == 1]

# 输出结果
print(f"最优行子集索引：{selected_indices}")
print(f"覆盖列数p：{np.sum(np.any(A[selected_indices], axis=0))}")
print(f"重复行数q：{len(selected_indices) - len(set(tuple(row) for row in A[selected_indices]))}")
print(f"唯一性score：{np.sum(np.any(A[selected_indices], axis=0)) - r*(len(selected_indices) - len(set(tuple(row) for row in A[selected_indices])))}")

2. 基于SciPy的模拟退火算法 #

将行选中状态编码为整数（二进制位对应每行的选中与否），用模拟退火搜索最优解：

import numpy as np
from scipy.optimize import dual_annealing

A = np.asarray([
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
])
r = 0.1
n_rows = A.shape[0]

def objective(x):
    # 将整数解码为行选中掩码
    x_int = int(x[0])
    selected_mask = np.array([(x_int >> i) & 1 for i in range(n_rows)], dtype=bool)
    selected_rows = A[selected_mask]
    
    if len(selected_rows) == 0:
        return -0
    
    col_coverage = np.any(selected_rows, axis=0)
    p = np.sum(col_coverage)
    
    unique_rows = set(tuple(row) for row in selected_rows)
    q = len(selected_rows) - len(unique_rows)
    
    score = p - r * q
    return -score  # 适配最小化逻辑

# 搜索范围：0到2^行数 -1（所有可能的行组合）
bounds = [(0, 2**n_rows - 1)]
result = dual_annealing(objective, bounds)

# 解析最优解
best_x = int(result.x[0])
selected_indices = [i for i in range(n_rows) if (best_x >> i) & 1]

# 输出结果
print(f"最优行子集索引：{selected_indices}")
print(f"覆盖列数p：{np.sum(np.any(A[selected_indices], axis=0))}")
print(f"重复行数q：{len(selected_indices) - len(set(tuple(row) for row in A[selected_indices]))}")
print(f"唯一性score：{np.sum(np.any(A[selected_indices], axis=0)) - r*(len(selected_indices) - len(set(tuple(row) for row in A[selected_indices])))}")

3. 多目标优化（保留帕累托前沿） #

如果需要同时观察p和q*r的权衡关系，可以用Platypus的NSGA-II算法做双目标优化：

from platypus import NSGAII, Problem, Binary
import numpy as np

A = np.asarray([
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1],
])
r = 0.1

def objective(x):
    selected_mask = np.array(x, dtype=bool)
    selected_rows = A[selected_mask]
    
    col_coverage = np.any(selected_rows, axis=0)
    p = np.sum(col_coverage)
    
    unique_rows = set(tuple(row) for row in selected_rows)
    q = len(selected_rows) - len(unique_rows)
    
    return [p, q * r]

# 定义双目标问题：最大化p，最小化q*r
problem = Problem(5, 2)
problem.types[:] = Binary()
problem.function = objective
problem.directions[:] = [Problem.MAXIMIZE, Problem.MINIMIZE]

algorithm = NSGAII(problem)
algorithm.run(10000)

# 输出帕累托前沿解
for idx, sol in enumerate(algorithm.result):
    selected_indices = [i for i, val in enumerate(sol.variables) if val == 1]
    print(f"解{idx+1}：行子集{selected_indices}，p={sol.objectives[0]}，q*r={sol.objectives[1]:.2f}")

方案选择建议 #

• 小规模矩阵（行数<20）：可以用暴力枚举或整数规划（如PuLP库），保证找到全局最优解。
• 中大规模矩阵：优先选择遗传算法（Platypus）或模拟退火（SciPy），在合理时间内找到近似最优解。
• 需要权衡目标：用双目标遗传算法生成帕累托前沿，手动选择符合需求的解。

内容的提问来源于stack exchange，提问作者O.rka