SadDE: Self-Adaptive discrete Differential Evolution for Combinatorial Optimization Problems
International journal of intelligent engineering and systems · 2025
Differential Evolution (DE) is a stochastic population-based algorithm that tackles continuous optimization problems with decision variables having their values in a continuous domain.The diligent employment of DE also helped to resolve diverse combinatorial optimization problems (COPs), with discrete domains of values for their decision variables, with promising results.However, DE's application in solving permutation-based COPs has not been widely reported in the literature.This paper presents two new DE frameworks with two proposed mapping approaches for solving permutation-based COPs.Firstly, a DE framework named PdDE (Probabilistic discrete Differential Evolution) with a proposed cooperative guided mapping approach is designed and investigated.In PdDE the genes of the mutant vector and selected individuals from the population are selected in a probabilistic method and mapped with the genes of multiple best individuals.This approach improved the searching capability of DE for solving COPs but often resulted in premature convergence.To address this challenge, an extended DE framework named SadDE (Self-adaptive discrete Differential Evolution) with a proposed self-adaptive cooperative guided mapping strategy is designed.The SadDE focuses on developing a guided mapping framework for DE that utilizes a selfadaptive guided strategy to enhance DE's exploration and exploitation capability for solving COPs, suitably.It involves substituting selected genes of the mutant vector and chosen individuals from the population with selected genes from multiple best individuals adaptively.This approach facilitates cooperative guidance of the vectors and directs them towards the optimal solution.The effectiveness of the PdDE and SadDE frameworks is evaluated with 15 instances of the benchmarking travelling salesperson problem (TSP) and 8 instances of the 0/1-Knapsack problem (0/1 KP).Comprehensive empirical and statistical analyses are conducted, comparing PdDE and SadDE against six state-of-theart DE mapping variants, viz., Truncation process and its variants (TP, TPL, TPI), Rank Based (RB) method, Lowest Rank Value (LRV) method, and Best Matched Value (BMV) method.The experiments are also extended to compare PdDE and SadDE with four well-established metaheuristic algorithms, such as Bee Colony Optimization (BCO), Genetic Algorithm (GA), Firefly Algorithm (FA), and Grey Wolf Optimizer (GWO).On solving the benchmarking TSP instances, the SadDE outperformed the state-of-the-art DE mapping variants by giving the lowest average error percentages of the best solutions.The performance improvements shown by SadDE in comparison with TP, TPL, TPI, RB, LRV, and BMV are 57.49%,58.28%, 53.82%, 56.74%, 56.79%, and 31.79%,respectively.The comparative study with the metaheuristic algorithms showed that the algorithms integrated with the SadDE mapping approach could outperform the corresponding classical metaheuristic algorithms.The SadDE integrated versions of the BCO, GA, FA, and GWO algorithms demonstrated 29.93%, 28.15%, 32.87%, and 9.14% of performance improvement compared to their classical versions, respectively.These observations proved that the proposed SadDE mapping approach helps to improve the performance of classical optimization algorithms for solving COPs.