A deep learning approach to predicting solutions in streaming optimisation domains
| Autor: | Emma Hart, Mohamad Alissa, Kevin Sim |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Heuristic
Computer science Bin packing problem Heuristic (computer science) business.industry Deep learning Scheduling (production processes) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Field (computer science) Set (abstract data type) Packing problems 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Artificial intelligence business Algorithm |
| Zdroj: | GECCO |
| DOI: | 10.1145/3377930.3390224 |
| Popis: | In the field of combinatorial optimisation, per-instance algorithm selection still remains a challenging problem, particularly with respect to streaming problems such as packing or scheduling. Typical approaches involve training a model to predict the best algorithm based on features extracted from the data, which is well known to be a difficult task and even more challenging with streaming data. We propose a radical approach that bypasses algorithm-selection altogether by training a Deep-Learning model using solutions obtained from a set of heuristic algorithms to directly predict a solution from the instance-data. To validate the concept, we conduct experiments using a packing problem in which items arrive in batches. Experiments conducted on six large datasets using batches of varying size show the model is able to accurately predict solutions, particularly with small batch sizes, and surprisingly in a small number of cases produces better solutions than any of the algorithms used to train the model. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|