Instance-specific selection of AOS methods for solving combinatorial optimisation problems via neural networks

• Main Authors: TENG, Teck Hou (DENG Dehao), LAU, Hoong Chuin, GUNAWAN, Aldy
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2018
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/4285; https://ink.library.smu.edu.sg/context/sis_research/article/5288/viewcontent/LION_2018___Instance_Specific_Selection_of_AOS_Methods_for_Solving_Combinatorial_Optimisation_Problems_via_Neural_Network.pdf
• Institution: Singapore Management University

Solving combinatorial optimization problems using a fixed set of operators has been known to produce poor quality solutions. Thus, adaptive operator selection (AOS) methods have been proposed. But, despite such effort, challenges such as the choice of suitable AOS method and configuring it correctly for given specific problem instances remain. To overcome these challenges, this work proposes a novel approach known as I-AOS-DOE to perform Instance-specific selection of AOS methods prior to evolutionary search. Furthermore, to configure the AOS methods for the respective problem instances, we apply a Design of Experiment (DOE) technique to determine promising regions of parameter values and to pick the best parameter values from those regions. Our main contribution lies in the use a self-organizing neural network as the offline-trained AOS selection mechanism. This work trains a variant of FALCON known as FL-FALCON using performance data of applying AOS methods on training instances. The performance data comprises derived fitness landscape features, choices of AOS methods and feedback signals. The hypothesis is that a trained FL-FALCON is capable of selecting suitable AOS methods for unknown problem instances. Experiments are conducted to test this hypothesis and compare I-AOS-DOE with existing approaches. Experiment results reveal that I-AOS-DOE can indeed yield the best performance outcome for a sample set of quadratic assignment problem (QAP) instances.