非常小规模0-1规划问题无可行解

[qiutingqiushan]

我的模型如下：

在2X2小规模路网实验：

代码如下：

import numpy as np
import geatpy as ea

class MyProblem(ea.Problem):  # 继承Problem父类

    def __init__(self):
        self.links_num = 12
        self.routes_num = 6
        self.path_link_incidence = {
            (0, 0): 1, (0, 1): 1, (0, 2): 0, (0, 3): 0, (0, 4): 0, (0, 5): 0, (0, 6): 0,
            (0, 7): 0, (0, 8): 0, (0, 9): 0, (0, 10): 1, (0, 11): 1, (1, 0): 1, (1, 1): 0,
            (1, 2): 0, (1, 3): 1, (1, 4): 0, (1, 5): 0, (1, 6): 0, (1, 7): 0, (1, 8): 1,
            (1, 9): 0, (1, 10): 0, (1, 11): 1, (2, 0): 1, (2, 1): 0, (2, 2): 0, (2, 3): 0,
            (2, 4): 0, (2, 5): 1, (2, 6): 0, (2, 7): 0, (2, 8): 1, (2, 9): 1, (2, 10): 0,
            (2, 11): 0, (3, 0): 0, (3, 1): 0, (3, 2): 0, (3, 3): 0, (3, 4): 1, (3, 5): 1,
            (3, 6): 1, (3, 7): 1, (3, 8): 0, (3, 9): 0, (3, 10): 0, (3, 11): 0, (4, 0): 0,
            (4, 1): 0, (4, 2): 1, (4, 3): 0, (4, 4): 0, (4, 5): 1, (4, 6): 1, (4, 7): 0,
            (4, 8): 0, (4, 9): 1, (4, 10): 0, (4, 11): 0, (5, 0): 0, (5, 1): 0, (5, 2): 1,
            (5, 3): 1, (5, 4): 0, (5, 5): 0, (5, 6): 1, (5, 7): 0, (5, 8): 0, (5, 9): 0,
            (5, 10): 0, (5, 11): 1}

        name = 'MyProblem_CompModel1'
        M = 1  # 目标维数
        maxormins = [1]  # 初始化maxormins（目标最小最大化标记列表，1：最小化该目标；-1：最大化该目标）
        Dim = self.links_num  # 初始化Dim（决策变量维数）
        varTypes = [1] * Dim  # 初始化varTypes（决策变量的类型，元素为0表示对应的变量是连续的；1表示是离散的）
        lb = [0] * Dim  # 决策变量下界
        ub = [1] * Dim  # 决策变量上界
        lbin = [1] * Dim  # 决策变量下边界（0表示不包含该变量的下边界，1表示包含）
        ubin = [1] * Dim  # 决策变量上边界（0表示不包含该变量的上边界，1表示包含）
        # 调用父类构造方法完成实例化
        ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin)

    def aimFunc(self, pop):
        Vars = pop.Phen  # 得到决策变量矩阵

        x = {}
        cnt = 0
        for i in range(self.links_num):
            x[i] = Vars[:, [cnt]]
            cnt += 1

        # 计算目标函数值
        f = sum(x[i] for i in range(self.links_num))
        pop.ObjV = f

        # 计算约束
        cv_list = []
        for j in range(self.routes_num):
            for k in range(self.routes_num):
                cv_list.append(-sum(
                    abs(self.path_link_incidence[j, i] - self.path_link_incidence[k, i]) * x[i] for i in
                    range(self.links_num)) + 1)
        pop.CV = np.hstack(cv_list)


# 实例化问题对象
problem = MyProblem()  # 生成问题对象
# 快速构建算法
algorithm = ea.soea_DE_rand_1_L_templet(
    problem,
    ea.Population(Encoding='RI', NIND=20),
    MAXGEN=200,  # 最大进化代数。
    logTras=0)  # 表示每隔多少代记录一次日志信息，0表示不记录。
algorithm.mutOper.F = 0.7  # 差分进化中的参数F。
algorithm.recOper.XOVR = 0.7  # 交叉概率。
# 先验知识
initial_sol = [0] * 12
location_links = [2, 5, 8] # 原模型最优解
for link_id in location_links:
    initial_sol[link_id] = 1
prophetVars = np.array([initial_sol])  # 假设已知initial_sol为一组比较优秀的变量。
# prophetVars = None
# 求解
res = ea.optimize(algorithm,
                  prophet=prophetVars,
                  verbose=True,
                  drawing=1,
                  outputMsg=True,
                  drawLog=True,
                  saveFlag=True)
print(res)

但是即使我把Gurobi求解器求出的最优解作为先验值代入，结果也是未找到可行解。不太清楚该怎么debug。之前也看到有人问了类似的问题，但是本模型也没有等式约束，只是0-1规划问题，是否是geatpy不太适合求解整数规划问题？

[qiutingqiushan]

@geatpy-dev

[geatpy-dev]

这个只跟使用的算法有关，跟用什么库、工具箱是无关的。

[qiutingqiushan]

1. 那您的意思是更换下算法模板或者自定义算法模板吗？我之前有试过差分进化算法里的一系列模板，不过只是简单调用，没有仔细调参。
2. 我不太理解这里我都把最优解输入到先验信息了，为什么还是找不到可行解。希望您能指点一二

[geatpy-dev]

单步调试予以解决。