如何优化拉伸并均匀化带标签一维整数点（含约束与多目标优化）

问题梳理 #

• 数据说明：输入是带标签的整数数组X，数值范围[0, 2000000]，约3000个元素，标签为[A,B,C]，例：[(13, 'A'), (16, 'B'), ...]
• 约束条件：
  • 每个元素可在原始值±50范围内调整，结果为整数
  • 调整后数组的整数值严格递增（因整数特性，等价于x_{i+1} ≥ x_i +1）
  • 标签顺序与原数组一致（只需保持数组元素顺序即可满足）
• 优化目标：
  1. 最小化相邻元素差值（gaps）的方差（权重1.0）
  2. 最大化相邻元素的平均间距（权重0.1）
     组合目标：minimize(1.0 * var(gaps) - 0.1 * mean(gaps))

原方案局限 #

scipy.optimize.minimize()不支持整数约束，无法直接生成符合要求的整数解。

可行解决方案 #

方案1：使用scipy.optimize.milp（线性近似目标） #

由于milp仅支持线性目标与约束，需将原二次方差目标近似为线性的绝对偏差最小化（核心逻辑是让gaps尽可能均匀），转化后的目标函数为：

minimize(1.0 * Σ|g_i - μ| - 0.1 * μ)

其中g_i = x_{i+1} - x_i，μ = (x[-1] - x[0])/(n-1)（平均间距）。为将绝对值转化为线性约束，引入辅助变量d_i ≥ 0，满足：

• g_i - μ ≤ d_i
• μ - g_i ≤ d_i

以下是具体实现代码：

import numpy as np
from scipy.optimize import milp, Bounds, LinearConstraint

def optimize_with_milp(initial_array, weight_var=1.0, weight_avg=0.1):
    n = len(initial_array)
    original_vals = initial_array[:, 0].astype(int)
    
    # 总变量数：n个x变量 + n-1个辅助d变量
    num_total_vars = n + (n-1)
    # 目标系数初始化
    c = np.zeros(num_total_vars)
    
    # 1. 设置变量边界
    # x变量的范围：原始值±50，且为整数
    x_bounds_lb = original_vals - 50
    x_bounds_ub = original_vals + 50
    # 辅助d变量的范围：≥0
    d_bounds_lb = np.zeros(n-1)
    d_bounds_ub = np.full(n-1, np.inf)
    
    bounds = Bounds(
        np.concatenate([x_bounds_lb, d_bounds_lb]),
        np.concatenate([x_bounds_ub, d_bounds_ub]),
        integrality=np.concatenate([[True]*n, [False]*(n-1)])  # x为整数，d可为实数
    )
    
    # 2. 递增约束：x_{i+1} - x_i ≥ 1
    constraints = []
    for i in range(n-1):
        row = np.zeros(num_total_vars)
        row[i] = -1
        row[i+1] = 1
        constraints.append(LinearConstraint(row, lb=1, ub=np.inf))
    
    # 3. 设置目标系数
    # 绝对偏差的权重：每个d_i的系数为weight_var
    for i in range(n-1):
        c[n + i] = weight_var
    # 平均间距的权重：最大化μ等价于最小化 -weight_avg*(x[-1]-x[0])/(n-1)
    c[-1] = -weight_avg / (n-1)
    c[0] = weight_avg / (n-1)
    
    # 4. 绝对偏差的线性约束转化
    for i in range(n-1):
        # 约束1：(n-1)(x_{i+1}-x_i) - (x[-1]-x_0) ≤ (n-1)d_i
        row1 = np.zeros(num_total_vars)
        row1[i] = -(n-1)
        row1[i+1] = (n-1)
        row1[0] = 1
        row1[n-1] = -1
        row1[n + i] = -(n-1)
        constraints.append(LinearConstraint(row1, lb=-np.inf, ub=0))
        
        # 约束2：(x[-1]-x_0) - (n-1)(x_{i+1}-x_i) ≤ (n-1)d_i
        row2 = np.zeros(num_total_vars)
        row2[i] = (n-1)
        row2[i+1] = -(n-1)
        row2[0] = -1
        row2[n-1] = 1
        row2[n + i] = -(n-1)
        constraints.append(LinearConstraint(row2, lb=-np.inf, ub=0))
    
    # 求解milp
    result = milp(c=c, bounds=bounds, constraints=constraints)
    
    # 提取优化后的x值并转为整数
    optimized_x = result.x[:n].round().astype(int)
    
    # 验证递增约束（可选）
    assert np.all(np.diff(optimized_x) >=1), "优化结果不满足递增约束"
    
    # 组合标签返回
    return list(zip(optimized_x, initial_array[:,1]))

方案2：启发式算法（模拟退火） #

针对3000个元素的规模，模拟退火适合处理非线性目标和整数约束，能更贴近原方差最小化的目标：

import numpy as np
import random

def optimize_with_simulated_annealing(initial_array, weight_var=1.0, weight_avg=0.1, max_iter=15000, temp_start=1200, temp_end=0.5):
    n = len(initial_array)
    original_vals = initial_array[:,0].astype(int)
    labels = initial_array[:,1]
    
    # 初始化合法解：确保递增且在±50范围内
    current_x = original_vals.copy()
    for i in range(1, n):
        if current_x[i] <= current_x[i-1]:
            current_x[i] = current_x[i-1] + 1
    current_x = np.clip(current_x, original_vals-50, original_vals+50)
    
    # 定义目标函数计算
    def calculate_objective(x):
        gaps = np.diff(x)
        var = np.var(gaps)
        mean = np.mean(gaps)
        return weight_var * var - weight_avg * mean
    
    current_obj = calculate_objective(current_x)
    best_x = current_x.copy()
    best_obj = current_obj
    
    temp = temp_start
    alpha = (temp_end / temp_start) ** (1/max_iter)
    
    for _ in range(max_iter):
        # 随机选择一个元素调整
        idx = random.randint(0, n-1)
        new_val = random.randint(original_vals[idx]-50, original_vals[idx]+50)
        new_x = current_x.copy()
        new_x[idx] = new_val
        
        # 检查递增合法性
        valid = True
        if idx > 0 and new_x[idx] <= new_x[idx-1]:
            valid = False
        if idx < n-1 and new_x[idx] >= new_x[idx+1]:
            valid = False
        
        if not valid:
            continue
        
        # 计算新目标值并判断是否接受
        new_obj = calculate_objective(new_x)
        delta = new_obj - current_obj
        
        if delta < 0 or random.random() < np.exp(-delta/temp):
            current_x = new_x
            current_obj = new_obj
            if new_obj < best_obj:
                best_x = new_x.copy()
                best_obj = new_obj
        
        # 降温
        temp *= alpha
    
    # 返回结果
    return list(zip(best_x, labels))

方案选择建议 #

• 若需严格符合线性规划逻辑的解，选择方案1，但目标是原问题的近似；
• 若需更贴近原方差最小化的目标，且能接受启发式的近似最优解，选择方案2，3000元素规模下运行效率良好。

内容的提问来源于stack exchange，提问作者Mat