A novel approach for multi-constraints knapsack problem using cluster particle swarm optimization. (December 2021)

• Record Type: Journal Article
• Authors: Babukarthik, R.G.; Dhasarathan, Chandramohan; Kumar, Manish; Shankar, Achyut; Thakur, Sanjeev; Cheng, Xiaochun
• Is Part Of: Computers & electrical engineering. Volume 96:Part A(2021)
• Publication Date: 2021-12
• Subjects: Particle swarm optimization -- Knapsack problem -- Genetic algorithm -- Evolutionary algorithm -- Ant colony optimization -- Master-slave particle swarm optimization -- Energy optimization; Computer engineering -- Periodicals; Electrical engineering -- Periodicals; Electrical engineering -- Data processing -- Periodicals; Ordinateurs -- Conception et construction -- Périodiques; Électrotechnique -- Périodiques; Électrotechnique -- Informatique -- Périodiques; Computer engineering; Electrical engineering; Electrical engineering -- Data processing; Periodicals; Electronic journals; 621.302854
• DOI: 10.1016/j.compeleceng.2021.107399
• Languages: English
• ISSNs: 0045-7906

Abstract

Highlights: Cluster particle swarm optimization (CPSO) uses BVA techniques for evaluation of optimal solution. The boundary value is chosen from the benchmark standard, in CPSO algorithm. By using ackley function, BVA values. The performance is evaluated for multi-dimensional knapsack instance based on evaluation criteria such as optimal solution, computation time, convergence rate, error rate, and average convergence rate and convergence diversity. To enhance the CPSO for supplementary combinatorial optimization problems, machine learning and deep convolution neural network is considered as an alternative for the gradient descent. Abstract: Cluster particle swarm optimization (CPSO) is distinct approach of PSO, in which each sub-swarm points an exact region with a particular diverse situation, to perform on-demand computing. Particularly, it is used for problems based on a cluster, which contains many locally optimal solutions to reduce wastage of energy and improve energy sustainability. Among the combinatorial optimization problems, the knapsack problem is widely studied. There are several variants and techniques devised over the times, to get the optimal solutions for solving multiple constrain problems by considering weight and capacity to minimize energy consumption. Still, the multi-constraint Knapsack problem (KP) remains the major challenge. The proposed cluster-based Particle swarm optimization (PSO) algorithm is used for solving problems having multiple energy preserving constraints. The proposed algorithm incorporates Boundary value analysis (BVA) techniques and is compared with the standard knapsack dataset for effective energy optimization. The proposed algorithm is evaluated based on performance criteria, thereby, achieving 100% accuracy for minimum dimension and approximately more than 85% for higher dimension of energy minimization problems. The proposed techniques are compared with Simulated annealing (SA) and Genetic algorithm (GA). It is evident that the proposed techniques out performed well to compare to other algorithms. Future research focuses on applying proposed techniques, to machine learning and deep convolutional neural network for quicker searching process. Furthermore, plan to utilize the proposed techniques for other combinatorial optimization problems. Graphical abstract: Image, graphical abstract