按年被提到
20172017 · 1 次2026
强化学习与智能体›进化策略与探索·arXiv:1704.01665 · cs.LG

Learning Combinatorial Optimization Algorithms over Graphs

Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, Le Song · 2017
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2017-12-07 · 最近 2018-06-25
2不同的人
2活跃月份
2讨论串
1,067被引(OpenAlex)
arXiv 摘要(候选层不写导读)

The design of good heuristics or approximation algorithms for NP-hard combinatorial optimization problems often requires significant specialized knowledge and trial-and-error. Can we automate this challenging, tedious process, and learn the algorithms instead? In many real-world applications, it is typically the case that the same optimization problem is solved again and again on a regular basis, maintaining the same problem structure but differing in the data. This provides an opportunity for learning heuristic algorithms that exploit the structure of such recurring problems. In this paper, we propose a unique combination of reinforcement learning and graph embedding to address this challenge. The learned greedy policy behaves like a meta-algorithm that incrementally constructs a solution, and the action is determined by the output of a graph embedding network capturing the current state of the solution. We show that our framework can be applied to a diverse range of optimization problems over graphs, and learns effective algorithms for the Minimum Vertex Cover, Maximum Cut and Traveling Salesman problems.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论_raoulcousins · 2018-06

“Absolutely. People are using ML for plenty of difficult problems. In operations research, a lot of time is spent coming up with heuristic solutions to hard optimization problems. This problem is plenty hard for people to do. There has been some recent work in using ML to create solution methods, like the paper Learning Combinatorial Optimization Algorithm…”

Ways to think about machine learning原评论 ↗
被提交为 story · 1 次