Learning to sample initial solution for solving 0-1 discrete optimization problem by local search

扫码查看

原文链接

万方数据
维普

外文摘要：Local search methods are convenient alternatives for solving discrete optimization problems(DOPs).These easy-to-implement methods are able to find approximate optimal solutions within a tolerable time limit.It is known that the quality of the initial solution greatly affects the quality of the approximated solution found by a local search method.In this paper,we propose to take the initial solution as a random variable and learn its preferable probability distribution.The aim is to sample a good initial solution from the learned distribution so that the local search can find a high-quality solution.We develop two different deep network models to deal with DOPs established on set(the knapsack problem)and graph(the maximum clique problem),respectively.The deep neural network learns the representation of an optimization problem instance and transforms the representation to its probability vector.Experimental results show that given the initial solution sampled from the learned probability distribution,a local search method can acquire much better approximate solutions than the randomly-sampled initial solution on the synthesized knapsack instances and the Erdös-Rényi random graph instances.Furthermore,with sampled initial solutions,a classical genetic algorithm can achieve better solutions than a random initialized population in solving the maximum clique problems on DIMACS instances.Particularly,we emphasize that the developed models can generalize in dimensions and across graphs with various densities,which is an important advantage on generalizing deep-learning-based optimization algorithms.

外文关键词：

discrete optimizationdeep learninggraph convolutional networklocal search

作者：

Xin Liu、Jianyong Sun、Zongben Xu

展开 >

作者单位：

School of Mathematics and Statistics,Xi'an Jiaotong University,Xi'an 710049,China

基金：

National Natural Science Foundation of ChinaNational Natural Science Foundation of ChinaKey Research and Development Project of Shaanxi Province

项目编号：

11991023620761972022GXLH-01-15

出版年：

2024

DOI：

10.1007/s11425-023-2290-y

中国科学:数学(英文版)

中国科学院

中国科学:数学(英文版)

CSTPCD

影响因子：0.36

ISSN：1674-7283

年,卷(期)：2024.67(6)