geatpy
geatpy copied to clipboard
非常小规模0-1规划问题无可行解
我的模型如下: 在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不太适合求解整数规划问题?
@geatpy-dev
这个只跟使用的算法有关,跟用什么库、工具箱是无关的。
- 那您的意思是更换下算法模板或者自定义算法模板吗?我之前有试过差分进化算法里的一系列模板,不过只是简单调用,没有仔细调参。
- 我不太理解这里我都把最优解输入到先验信息了,为什么还是找不到可行解。希望您能指点一二
单步调试予以解决。