我正在学习如何使用强化学习进行优化。我选择的问题是最大匹配 https://en.wikipedia.org/wiki/Maximum_cardinality_matching在二分图中，因为我可以轻松计算出真正的最优值。
回想一下，图中的匹配是边的子集，其中没有两条边入射到同一节点/顶点上。目标是找到最大的此类子集。
我在下面展示了完整的代码，但首先让我解释一下其中的部分内容。
num_variables = 1000
g = ig.Graph.Random_Bipartite(num_variables, num_variables, p=3/num_variables)
g_matching = g.maximum_bipartite_matching()
print("Matching size", len([v for v in g_matching.matching if v < num_variables and v != -1]))
这将生成一个随机二部图，两组节点中每组都有 1000 个节点。然后它打印出真正最大匹配的大小。
在下面的代码中，self.agent_pos是一个数组，表示当前找到的匹配项。它的长度是原图中的边数，索引处有一个1i如果边缘i包含在内，否则为 0。self.matching是增长匹配中的边集。self.matching_nodes是增长匹配中的节点集，用于检查是否可以添加特定边。
import igraph as ig
from tqdm import tqdm
import numpy as np
import gym
from gym import spaces
from stable_baselines3 import PPO
from stable_baselines3.common.env_util import make_vec_env
class MaxMatchEnv(gym.Env):
metadata = {'render.modes': ['console']}
def __init__(self, array_length=10):
super(MaxMatchEnv, self).__init__()
# Size of the 1D-grid
self.array_length = array_length
self.agent_pos = [0]*array_length
self.action_space = spaces.Discrete(array_length)
self.observation_space = spaces.Box(low=0, high=1, shape=(array_length,), dtype=np.uint8)
self.matching = set() # set of edges
self.matching_nodes = set() # set of node ids (ints)
self.matching_size = len([v for v in g_matching.matching if v < num_variables and v != -1])
self.best_found = 0
def reset(self):
# Initialize the array to have random values
self.time = 0
#print(self.agent_pos)
self.agent_pos = [0]*self.array_length
self.matching = set()
self.matching_nodes = set()
return np.array(self.agent_pos)
def step(self, action):
self.time += 1
reward = 0
edge = g.es[action]
if not(edge.source in self.matching_nodes or edge.target in self.matching_nodes):
self.matching.add(edge)
self.matching_nodes.add(edge.source)
self.matching_nodes.add(edge.target)
self.agent_pos[action] = 1
if sum(self.agent_pos) > self.best_found:
self.best_found = sum(self.agent_pos)
print("New max", self.best_found)
reward = 1
elif self.agent_pos[action] == 1:
#print("Removing edge", action)
self.matching_nodes.remove(edge.source)
self.matching_nodes.remove(edge.target)
self.matching.remove(edge)
self.agent_pos[action] = 0
reward = -1
done = sum(self.agent_pos) == self.matching_size
info = {}
return np.array(self.agent_pos), reward, done, info
def render(self, mode='console'):
print(sum(self.agent_pos))
def close(self):
pass
if __name__ == '__main__':
num_variables = 1000
g = ig.Graph.Random_Bipartite(num_variables, num_variables, p=3/num_variables)
g_matching = g.maximum_bipartite_matching()
print("Matching size", len([v for v in g_matching.matching if v < num_variables and v != -1]))
env = make_vec_env(lambda: MaxMatchEnv(array_length=len(g.es)), n_envs=12)
model = PPO('MlpPolicy', env, verbose=1).learn(10000000)
这存在很多问题，但最主要的问题是它优化得不好。这段代码给出了刚刚超过 550 的结果，然后在真正的最佳值超过 900 的地方停止改进（它是由代码在开始时打印出来的）。
主要问题是：
如何才能做得更好，从而达到更好的匹配？
一个附属问题是，如何打印迄今为止找到的最佳匹配？我尝试使用 self.best_found 来保持最佳分数不起作用，因为它似乎会定期重置。
没有帮助的改变
- 将 PPO 更改为 DQN 只会产生微小的差异。
- 我尝试更改代码以便
done1000 步后为 True。
变化如下：
if self.time == 1000:
done = True
else:
done = False
添加后print(max(env.get_attr("best_found")))代替print("New max", self.best_found)此更改为done完全没有显示出任何优势。
