29 November 2018 in IEEE Transactions on Cybernetics
Pareto local search (PLS) is a basic building block in many metaheuristics for a multiobjective combinatorial optimization problem. In this paper, an enhanced PLS variant called parallel PLS based on decomposition (PPLS/D) is proposed. PPLS/D improves the efficiency of PLS using the techniques of parallel computation and problem decomposition. It decomposes the original search space into L subregions and executes L parallel processes searching in these subregions simultaneously. Inside each subregion, the PPLS/D process is guided by a unique scalar objective function. PPLS/D differs from the well-known two phase PLS in that it uses the scalar objective function to guide every move of the PLS procedure in a fine-grained manner. In the experimental studies, PPLS/D is compared against the basic PLS and a recently proposed PLS variant on the multiobjective unconstrained binary quadratic programming problems and the multiobjective traveling salesman problems with, at most, four objectives. The experimental results show that regardless of whether the initial solutions are randomly generated or generated by heuristic methods, PPLS/D always performs significantly better than the other two PLS variants.
18 November 2022 in IEEE Transactions on Emerging Topics in Computational Intelligence
The performance of an evolutionary algorithm (EA) is deeply affected by its control parameter's setting. It has become a trend in recent studies to treat the control parameter as a random variable. In these studies, the associated distribution of the control parameter is updated at each generation and new parameter setting is sampled from the distribution. The distribution's parameter (called hyper-parameter) is thus critical to the algorithmic performance. In this paper, we propose a variational learning framework to tune the hyper-parameters of EA, in which the expectation-maximization (EM) algorithm and a reinforcement learning algorithm are combined. To verify the effectiveness of the proposed method which is named Reinforcement EM (REM), we apply it to tune the hyper-parameters of the distributions of two important parameters, i.e. the scaling parameter ( $F$ ) and crossover rate ( $CR$ ), of differential evolution (DE) and an adaptive DE algorithm. In addition, we propose to use the meta-learning technique to learn good initial distributions for the hyper-parameters of $F$ and $CR$ so that the REM can effectively adapt to a new optimization problem. Experimental results obtained on the CEC 2018 test suite show that with the tuned hyper-parameters, DE and the adaptive DE can achieve significantly better performance than their counterparts with empirical parameter settings and with parameters tuned by some widely-used tuning methods, including ParamILS, F-Race and Bayesian optimization algorithm.
20 December 2022 in IEEE Transactions on Cybernetics
Pareto local search (PLS) is a natural extension of local search for multiobjective combinatorial optimization problems (MCOPs). In our previous work, we improved the anytime performance of PLS using parallel computing techniques and proposed a parallel PLS based on decomposition (PPLS/D). In PPLS/D, the solution space is searched by multiple independent parallel processes simultaneously. This article further improves PPLS/D by introducing two new cooperative process techniques, namely, a cooperative search mechanism and a cooperative subregion-adjusting strategy. In the cooperative search mechanism, the parallel processes share high-quality solutions with each other during the search according to a distributed topology. In the proposed subregion-adjusting strategy, a master process collects useful information from all processes during the search to approximate the Pareto front (PF) and redivide the subregions evenly. In the experimental studies, three well-known NP-hard MCOPs with up to six objectives were selected as test problems. The experimental results on the Tianhe-2 supercomputer verified the effectiveness of the proposed techniques.
11 March 2023 in Information Sciences
3 April 2020 in IEEE Transactions on Cybernetics
This article proposes a novel landscape smoothing method for the symmetric traveling salesman problem (TSP). We first define the homotopic convex (HC) transformation of a TSP as a convex combination of a well-constructed simple TSP and the original TSP. The simple TSP, called the convex-hull TSP, is constructed by transforming a known local or global optimum. We observe that controlled by the coefficient of the convex combination, with local or global optimum: 1) the landscape of the HC transformed TSP is smoothed in terms that its number of local optima is reduced compared to the original TSP and 2) the fitness distance correlation of the HC transformed TSP is increased. Furthermore, we observe that the smoothing effect of the HC transformation depends highly on the quality of the used optimum. A high-quality optimum leads to a better smoothing effect than a low-quality optimum. We then propose an iterative algorithmic framework in which the proposed HC transformation is combined within a heuristic TSP solver. It works as an escaping scheme from local optima aiming to improve the global searchability of the combined heuristic. Case studies using the 3-Opt and the Lin-Kernighan local search as the heuristic solver show that the resultant algorithms significantly outperform their counterparts and two other smoothing-based TSP heuristic solvers on most of the test instances with up to 20,000 cities.
6 November 2024 in Expert Systems with Applications