یادگیری تقویتی عمیق کاربردی
ترجمه نشده

یادگیری تقویتی عمیق کاربردی

عنوان فارسی مقاله: یادگیری تقویتی عمیق کاربردی برای مشکل k-server
عنوان انگلیسی مقاله: Deep reinforcement learning applied to the k-server problem
مجله/کنفرانس: سیستم های خبره با کابردهای مربوطه – Expert Systems with Applications
رشته های تحصیلی مرتبط: مهندسی کامپیوتر
گرایش های تحصیلی مرتبط: هوش مصنوعی، مهندسی الگوریتم و محاسبات
کلمات کلیدی فارسی: یادگیری تقویتی عمیق، مشکل آنلاین، مشکل k-server، بهینه سازی ترکیبی، موقعیت رقابتی
کلمات کلیدی انگلیسی: Deep reinforcement learning، Online problem، The k-server problem، Combinatorial optimization، Competitive location
نوع نگارش مقاله: مقاله پژوهشی (Research Article)
شناسه دیجیتال (DOI): https://doi.org/10.1016/j.eswa.2019.06.015
دانشگاه: Federal University of Rio Grande do Norte, Department of Computer Engineering and automation, Rio Grande do Norte, Natal, Brazil
صفحات مقاله انگلیسی: 7
ناشر: الزویر - Elsevier
نوع ارائه مقاله: ژورنال
نوع مقاله: ISI
سال انتشار مقاله: 2019
ایمپکت فاکتور: 5.891 در سال 2018
شاخص H_index: 162 در سال 2019
شاخص SJR: 1.190 در سال 2018
شناسه ISSN: 0957-4174
شاخص Quartile (چارک): Q1 در سال 2018
فرمت مقاله انگلیسی: PDF
وضعیت ترجمه: ترجمه نشده است
قیمت مقاله انگلیسی: رایگان
آیا این مقاله بیس است: بله
آیا این مقاله مدل مفهومی دارد: دارد
آیا این مقاله پرسشنامه دارد: ندارد
آیا این مقاله متغیر دارد: ندارد
کد محصول: E13565
رفرنس: دارای رفرنس در داخل متن و انتهای مقاله
فهرست مطالب (انگلیسی)

Abstract

1. Introduction

2. The k-server problem

3. Proposed approach

4. Case study

5. Conclusion

CRediT authorship contribution statement

Declaration of Competing Interest

Acknowledgments

References

بخشی از مقاله (انگلیسی)

Abstract

The reinforcement learning paradigm has been shown to be an effective approach in solving the k-server problem. However, this approach is based on the Q-learning algorithm, being subjected to the curse of dimensionality problem, since the action-value function (Q-function) grows exponentially with the increase in the number of states and actions. In this work, a new algorithm based on the deep reinforcement learning paradigm is proposed. For this, the Q-function is defined by a multilayer perceptron neural network that extracts the information of the environment from images that encode the dynamics of the problem. The applicability of the proposed algorithm is illustrated in a case study in which different nodes and servers problem configurations are considered. The agents behavior is analyzed during the training phase and its efficiency is evaluated from performance tests that quantify the quality of the generated server displacement policies. The results obtained provide a new algorithm promising view as an alternative solution to the k-server problem.

Introduction

In online computation a computer algorithm must decide how to act from the currently available input, without being aware of the entire set of inputs (Allan & El-Yaniv, 1998). Several current issues can be inserted in this type of problem, for example, given the price of Bitcoin, must the crypto currency be sold or bought? How to assign and reassign processes in a parallel processing so that there is load balancing on all processors? How to move a facility into an online transportation service minimizing the total cost involved in the process? Problems like these are complex since after a decision is made, it cannot be revoked, influencing the solution as a whole. Proposed by Manasse, McGeoch, and Sleator (1988) the k-server problem (KSP) is the problem of moving k servers over n nodes on a graph (or metric space) in order to satisfy the requests that appear online (sequentially) minimizing some cost function determined by the problem. Its conceptual simplicity contrasts with its complexity that grows exponentially with the increase in number of nodes and servers, being perhaps the most influential online problem, serving as a propeller for the development of new algorithms (Bansal, Buchbinder, Madry, & Naor, 2015; Gupta, Kamali, & López-Ortiz, 2016). Initially, the works related to the k-server problem focused on special metric spaces such as the uniform metric space, which corresponds to the paging problem in which high-performance algorithms are known (Sleator & Tarjan, 1985). For general metrics, Koutsoupias (2009) proposed the work function algorithm which is suitable for any metric space, obtaining results close to optimal solutions.