Виртуальный Эрудит для решения задачи о рюкзаке: обучение автоматическому распределению ресурсов

В этой статье представлено применение метода Виртуального Эрудита (Virtual Savant) для решения проблем распределения ресурсов, широко изученной области с несколькими реальными приложениями. Virtual Savant – это новый метод мягких вычислений, в котором используются методы машинного обучения для вычисления решений данной проблемы оптимизации. Цель Virtual Savant – научиться решать данную проблему с помощью решений, рассчитанных по эталонному алгоритму, а его дизайн позволяет использовать преимущества современных параллельных вычислительных инфраструктур. Предложенный подход оценивается на решении задачи о рюкзаке, которая моделирует различные варианты задач распределения ресурсов, учитывая набор экземпляров разного размера и сложности. Экспериментальный анализ проводился на многоядерном сервере Intel Xeon Phi. Результаты показывают, что Virtual Savant способен вычислять точные решения, демонстрируя хорошие свойства масштабируемости при увеличении объема используемых вычислительных ресурсов.

1. . Luss H. Equitable Resource Allocation. John Wiley & Sons, Inc., 2012.

2. . Vanderster D. C. Resource Allocation and Scheduling Strategies Using Utility and the Knapsack Problem on Computational Grids. PhD thesis, Victoria, B.C., Canada, 2008.

3. . Pinel F., Dorronsoro B., Bouvry, and Khan S. Savant: Automatic parallelization of a scheduling heuristic with machine learning. In Proc. of the World Congress on Nature and Biologically Inspired Computing, 2013, pp. 52–57.

4. . Treffert D. The savant syndrome: an extraordinary condition. A synopsis: past, present, future. Philosophical Transactions of the Royal Society B: Biological Sciences, vol. 364, no. 1522, 2009, pp.1351–1357.

5. . Treffert D. Extraordinary People: Understanding Savant Syndrome. iUniverse, 2006.

6. . Bouvet L., Donnadieu S., Valoptdois S., Caron C., Dawson M., and Mottron L. Veridical mapping in savant abilities, absolute pitch, and synesthesia: an autism case study. Frontiers in Psychology, vol. 5, no.106, 2014.

7. . Pinel F., Dorronsoro B., and Bouvry P. The virtual savant: Automatic generation of parallel solvers. Information Sciences, vol. 432, 2018, pp. 411–430.

8. . Massobrio R., Dorronsoro B., Palomo-Lozano F., Nesmachnow S., and Pinel F. Generación automática de programas: Savant Virtual para el problema de la mochila. In XI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados, pages 1–10, 2016.

9. . Massobrio R., Dorronsoro B., Nesmachnow S., and Palomo-Lozano F. Automatic program generation: Virtual savant for the knapsack problem. In Proc. of the International Workshop on Optimization and Learning, 2018, pp. 1–2

10. . Kellerer H., Pferschy U., and Pisinger D. Knapsack Problems. Springer, 2004.

11. . Pinel F. and Dorronsoro B. Savant: Automatic Generation of a Parallel Scheduling Heuristic for Map-Reduce. International Journal of Hybrid Intelligent Systems, vol. 11, no. 4, 2014, pp. 287–302.

12. . Nemhauser G. L. and Ullmann Z. Discrete dynamic programming and capital allocation. Management Science, vol. 15, no. 9, 1969, pp. 494–505.

13. . Harman M., Krinke J., Medina-Bulo I., Palomo F., Ren J., and Yoo S.. Exact scalable sensitivity analysis for the next release problem. ACM Transactions on Software Engineering and Methodology, vol. 23, no. 2, 2014, pp. 1–31.

14. . Bagnall A., Rayward-Smith V., and Whittley I. The next release problem. Information and Software Technology, vol. 43, no. 14, 2001, pp. 883–890.

15. . Vinyals O., Fortunato M., and Jaitly N. Pointer networks. In Advances in Neural Information Processing Systems 28, pp. 2692–2700, 2015.

16. . Hu H., Zhang X., Yan X., Wang L., and Xu Y. Solving a new 3d bin packing problem with deep reinforcement learning method. CoRR, abs/1708.05930, 2017.

17. . Dorronsoro B. and Pinel F. Combining machine learning and genetic algorithms to solve the independent tasks scheduling problem. In Proc. of the 3rd IEEE International Conference on Cybernetics, 2017, pp. 1–8.

18. . Massobrio R., Dorronsoro B., and Nesmachnow S. Virtual savant for the heterogeneous computing scheduling problem. In Proc. of the International Conference on High Performance Computing & Simulation, 2018 , pp. 1–7.

19. . Chang C.-C. and Lin C.-J. LIBSVM: A library for support vector machines. ACM Transactions on Intelligent Systems and Technology, vol. 2, no. 27, 2011, pp. 1–27.

20. . Massobrio R., Nesmachnow S., and Dorronsoro B. Support Vector Machine Acceleration for Intel Xeon Phi Manycore Processors. In Proc. of the Latin America High Performance Computing Conference, 2017, pp. 1–14.

21. . Jeffers J., Reinders J., and Sodani A. Intel Xeon Phi Processor High Performance Programming: Knights Landing Edition. Elsevier Science, 2016.

22. . Rodríguez, S., Parodi, F., and Nesmachnow, S. Parallel evolutionary approaches for game playing and verification using Intel Xeon Phi. Journal of Parallel and Distributed Computing, 2018. DOI: 10.1016/j.jpdc.2018.07.010