Applying deep convolutional neural networks to the dragon boat partition problem

We investigate approximating the Dragon Boat Partition problem, a practical real-worldvariant of the Partition problem. A team of dragon boat participants must be partitionedwith an approximately balanced arrangement with a preferable weight difference of 0. Wepresent two approaches that capture the participant characteristics. The first approach takesa heuristic route. The second approach applies Deep Convolutional Neural Networks to theproblem, with two versions. In our 10,000 episodes per experiment, our heuristic imple-mentation had an average episode runtime of 1.84ms, an average of 7.39 steps per episode,perfect left-right approximation rate of 98.53%, perfect front-back approximation rate of89.16%, and a perfect combined approximation rate of 90.15%. Whereas our best deeplearning model has an average episode runtime of 1.23ms, an average of 4.65 steps perepisode, perfect left-right approximate rate of 98.00%, perfect front-back approximationrate of 95.13%, and a perfect combined approximation rate of 94.28%.

Authors

• Regnier, Brett
• University of Lethbridge. Faculty of Arts and Science

• Research Subject Categories::TECHNOLOGY
• Research Subject Categories::TECHNOLOGY::Information technology::Computer science::Computer science
• Machine Learning
• Deep Convolutional Neural Networks
• Convolutional Neural Networks
• Optimization
• Deep Learning
• Approximation algorithms
• Artificial intelligence
• Computer science
• Dragon boat festivals
• Neural networks (Computer science)
• Dissertations, Academic

Identifier

hdl:10133/6029

OAI identifier oai:identifier

oai:opus.uleth.ca:10133/6029