基于Pymoo构建车辆子集优化问题：采样、交叉、变异实现问询

问题背景 #

现有N=100辆具备cost、rank、mpg属性的车辆，需找出k=5个rank与mpg更优的车辆子集（N和k可自定义）。使用Pymoo框架构建遗传算法求解，以rank和mpg为最大化目标。

最初编写的评估函数：

def _evaluate(self, x, out, *args, **kwargs):
    out["F"] = np.array([x["rank"], x["mpg"]], dtype=float)

核心疑问 #

需明确三类遗传算子的实现逻辑：

• Sampling：是否需要实现从车辆集合中随机选取k辆并返回的方法？
• Crossover：该子集选择场景下应如何实现？
• Mutation：该场景下应设计何种变异逻辑？

现有代码及运行错误 #

已编写更新后的代码，但运行报错，代码如下：

from pymoo.algorithms.soo.nonconvex.ga import GA
from pymoo.optimize import minimize
from pymoo.core.crossover import Crossover
from pymoo.core.mutation import Mutation
from pymoo.core.sampling import Sampling
import numpy as np
from pymoo.core.problem import ElementwiseProblem

class SubsetProblem(ElementwiseProblem):
    def __init__(self,L,n_max):
        super().__init__(n_var=len(L), n_obj=2, n_ieq_constr=0)
        self.L = L
        self.n_max = n_max

    def _evaluate(self, x, out, *args, **kwargs):
        out["F"] = np.array([self.L[x][0], self.L[x][1]], dtype=float)
        #out["G"] = (self.n_max - np.sum(x)) ** 2
        

class MySampling(Sampling):

    def _do(self, problem, n_samples, **kwargs):
        X = np.full((n_samples, problem.n_var), False, dtype=bool)

        for k in range(n_samples):
            I = np.random.permutation(problem.n_var)[:problem.n_max]
            X[k, I] = True

        return X

class BinaryCrossover(Crossover):
    def __init__(self):
        super().__init__(2, 1)

    def _do(self, problem, X, **kwargs):
        n_parents, n_matings, n_var = X.shape

        _X = np.full((self.n_offsprings, n_matings, problem.n_var), False)

        for k in range(n_matings):
            p1, p2 = X[0, k], X[1, k]

            both_are_true = np.logical_and(p1, p2)
            _X[0, k, both_are_true] = True

            n_remaining = problem.n_max - np.sum(both_are_true)

            I = np.where(np.logical_xor(p1, p2))[0]

            S = I[np.random.permutation(len(I))][:n_remaining]
            _X[0, k, S] = True

        return _X


class MyMutation(Mutation):
    def _do(self, problem, X, **kwargs):
        for i in range(X.shape[0]):
            X[i, :] = X[i, :]
            is_false = np.where(np.logical_not(X[i, :]))[0]
            is_true = np.where(X[i, :])[0]
            X[i, np.random.choice(is_false)] = True
            X[i, np.random.choice(is_true)] = False

        return X

# create the actual problem to be solved
np.random.seed(1)
L = np.array([[9,13],[9,14],[7,15],[6,12],[8,16],[8,14],[6,12],[3,18],[4,14],[5,14],[8,11],[8,18]])
n_max = 3
problem = SubsetProblem(L, n_max)


algorithm = GA(
    pop_size=12,
    sampling=MySampling(),
    crossover=BinaryCrossover(),
    mutation=MyMutation(),
    eliminate_duplicates=True)

res = minimize(problem,
               algorithm,
               ('n_gen', 60),
               seed=1,
               verbose=True)

print("Function value: %s" % res.F[0])
print("Subset:", np.where(res.X)[0])

算子实现思路及代码修正建议 #

1. 评估函数修正 #

• 原代码中self.L[x]索引错误：x是布尔数组，直接索引会返回所有选中车辆的属性矩阵，需计算目标值的总和/均值（此处以总和为例）。
• Pymoo默认最小化目标，最大化需对目标值取负值。
• 添加约束确保选中车辆数严格等于k：

class SubsetProblem(ElementwiseProblem):
    def __init__(self,L,n_max):
        # 新增2个不等式约束：选中数不能大于/小于n_max
        super().__init__(n_var=len(L), n_obj=2, n_ieq_constr=2)
        self.L = L
        self.n_max = n_max

    def _evaluate(self, x, out, *args, **kwargs):
        selected = self.L[x]
        # 取负值转为最小化问题，目标为选中车辆的rank、mpg总和
        out["F"] = -np.array([selected[:,0].sum(), selected[:,1].sum()], dtype=float)
        # 约束：选中数不能超过n_max，也不能少于n_max
        out["G"] = np.array([np.sum(x) - self.n_max, self.n_max - np.sum(x)])

2. Sampling算子实现 #

你的思路完全正确：从所有车辆中随机选k辆，用布尔数组标记选中状态。当前MySampling代码无需修改。

3. Crossover算子优化 #

原逻辑存在边界问题（比如双亲共同选中的车辆数超过k），优化后逻辑：

class BinaryCrossover(Crossover):
    def __init__(self):
        super().__init__(2, 1)

    def _do(self, problem, X, **kwargs):
        n_parents, n_matings, n_var = X.shape
        _X = np.full((self.n_offsprings, n_matings, problem.n_var), False)

        for k in range(n_matings):
            p1, p2 = X[0, k], X[1, k]
            both_true = np.logical_and(p1, p2)
            both_true_count = np.sum(both_true)
            
            if both_true_count > problem.n_max:
                # 共同选中数超k，随机保留k个
                keep = np.random.choice(np.where(both_true)[0], size=problem.n_max, replace=False)
                _X[0, k, keep] = True
            else:
                # 保留共同选中的，从双亲差异部分补全
                _X[0, k, both_true] = True
                n_remaining = problem.n_max - both_true_count
                xor_idx = np.where(np.logical_xor(p1, p2))[0]
                
                if n_remaining > 0:
                    if len(xor_idx) >= n_remaining:
                        select = np.random.choice(xor_idx, size=n_remaining, replace=False)
                    else:
                        # 差异部分不够，从未选中车辆里补
                        not_selected = np.where(np.logical_not(np.logical_or(p1, p2)))[0]
                        select = np.concatenate([xor_idx, np.random.choice(not_selected, size=n_remaining - len(xor_idx), replace=False)])
                    _X[0, k, select] = True
        return _X

4. Mutation算子修正 #

原逻辑正确，但需增加边界判断（避免空索引报错）：

class MyMutation(Mutation):
    def _do(self, problem, X, **kwargs):
        for i in range(X.shape[0]):
            current = X[i, :]
            true_idx = np.where(current)[0]
            false_idx = np.where(np.logical_not(current))[0]
            # 确保有选中和未选中的车辆再交换
            if len(true_idx) > 0 and len(false_idx) > 0:
                t = np.random.choice(true_idx)
                f = np.random.choice(false_idx)
                X[i, t] = False
                X[i, f] = True
        return X

5. 算法替换与结果处理 #

原代码使用单目标GA，多目标场景需替换为NSGA2：

from pymoo.algorithms.moo.nsga2 import NSGA2

algorithm = NSGA2(
    pop_size=20,
    sampling=MySampling(),
    crossover=BinaryCrossover(),
    mutation=MyMutation(),
    eliminate_duplicates=True)

res = minimize(problem,
               algorithm,
               ('n_gen', 60),
               seed=1,
               verbose=True)

# 打印帕累托前沿的目标值（还原为最大化数值）
print("帕累托前沿目标值（rank总和, mpg总和）：")
print(-res.F)

# 打印每个最优解对应的子集索引
for idx, x in enumerate(res.X):
    print(f"解{idx+1}的子集索引：{np.where(x)[0]}")

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