Shengye Yan

The multi-objective traveling salesman problem (MOTSP) is a typical challenging multi-objective combinatorial optimization problem. Numerous advanced deep reinforcement learning algorithms have been developed to solve it. Existing learning-based methods can share information across subproblems through mechanisms such as parameter transfer. This paper investigates explicit graph-based modeling of preference relationships within a shared policy and proposes a graph-relation-driven deep reinforcement learning algorithm for MOTSP. The proposed algorithm trains a model to map problem instances to approximate Pareto sets under a collection of preference vectors. Specifically, the graph weight encoder combines global and objective-specific city representations with preference features learned on a fixed graph whose edges are defined by distances between weight vectors. A graph co-guided fusion module then combines global and objective-specific city embeddings with the learned preference representations to generate preference-conditioned city embeddings. The resulting problem embeddings and contextual embeddings are supplied to the decoder to generate candidate tours in parallel, providing an approximation to the Pareto set. Furthermore, a Top-p training baseline is introduced to adaptively select reference candidates according to their scalarized costs. Finally, extensive experiments are conducted on various MOTSP instances. Comparisons are carried out between the proposed algorithm and heuristic and learning-based algorithms. Experimental results demonstrate the solution quality of the proposed algorithm on the evaluated multi-objective traveling salesman problems. Its computational cost is reported under the specified hardware, decoding budgets, and evaluation settings.

Aiming at the problem when both positive and negative training set are enormous, this paper proposes a novel matrix-structural learning (MSL) method, as an extension to Viola and Jones' cascade learning method for object detection. Briefly speaking, unlike Viola and Jones' method that learn linearly by bootstrapping only negative samples, the proposed MSL method bootstraps both positive and negative samples in a matrix-like structure. Moreover, an accumulative way is further presented to improve the training efficiency of MSL by inheriting features learned previously during training procedure. The proposed method is evaluated on face detection problem. On a positive set containing 230000 face samples, only 12 hours are needed on a common PC with a 3.20 GHz Pentium IV processor to learn a classifier with false alarm rate less than 1/1000000. What's more, the accuracy of the learned detector exceeds the state-of-the-art results on the CMU+MIT frontal face test set.