A reinforcement learning based computational intelligence approach for binary optimization problems: The case of the set-union knapsack problem. (February 2023)

• Record Type: Journal Article
• Authors: Ozsoydan, Fehmi Burcin; Gölcük, İlker
• Is Part Of: Engineering applications of artificial intelligence. Volume 118(2023)
• Publication Date: 2023-02
• Subjects: Machine learning -- Q-learning -- Genetic algorithm -- Particle swarm optimization -- Binary optimization -- Knapsack problem; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2022.105688
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: As today's one of the hottest topics, machine learning brings about opportunities in various research areas. Moreover, computational intelligence and metaheuristics open up new strategies, which are shown to be efficient in solving optimization problems. However, studies bringing such remarkable approaches together are still lacking. In this context, the present paper introduces a Q-learning reinforcement learning strategy for binary optimization problems. The developed algorithm works as a reinforcement and recommendation system that evaluates the used algorithms, assigns rewards, promotes or demotes them. Thus, it invokes more promising optimizers more frequently. The proposed Q-learning algorithm uses Particle Swarm Optimization (PSO), Genetic Algorithm and a hybrid of these algorithms, namely, genetic-based PSO (gbPSO) as optimizers. Therefore, it is aimed to avoid local optima by using various optimizers and gathering additional statistical data. Secondarily, all optimizers are further enhanced by adopting an initial solution generation technique and triggered random immigrants mechanism to preserve swarm diversity. In addition to these procedures, a mutation procedure that decreases the diversity is adopted. Thus, more intensified search is encouraged towards the end of search. Moreover, while PSO requires for transfer functions in order to perform in binary spaces, the adopted and further improved gbPSO does not necessarily need such auxiliary procedures. Finally, the performances of all used algorithms are analysed on a recently caught on binary problem, namely, the set-union knapsack problem, which has a wide range of real-life applications. As demonstrated by the comprehensive experimental study and appropriate statistical tests, promising improvements are achieved. Highlights: A machine learning algorithm as a recommendation/validation system. Promising metaheuristic algorithms for binary domains. Auxiliary procedures for swarm-based algorithm. Comprehensive experimental results. Statistical demonstrations.