A New Constructive Heuristic Driven by Machine Learning for the Traveling Salesman Problem

A Ferroelectric Memristor-Based Transient Chaotic Neural Network for Solving Combinatorial Optimization Problems

A transient chaotic neural network (TCNN) is particularly useful for solving combinatorial optimization problems, and its hardware implementation based on memristors has attracted great attention recently. Although previously used filamentary memristors could provide the desired nonlinearity for implementing the annealing function of a TCNN, the controllability of filamentary switching still remains relatively poor, thus limiting the performance of a memristor-based TCNN. Here, we propose to use ferroelectric memristor to implement the annealing function of a TCNN. In the ferroelectric memristor, the conductance can be tuned by switching the lattice non-centrosymmetry-induced polarization, which is a nonlinear switching mechanism with high controllability. We first establish a ferroelectric memristor model based on a ferroelectric tunnel junction (FTJ), which exhibits the polarization-modulated tunnel conductance and the nucleation-limited-switching (NLS) behavior. Then, the conductance of the ferroelectric memristor is used as the self-feedback connection weight that can be dynamically adjusted. Based on this, a ferroelectric memristor-based transient chaotic neural network (FM-TCNN) is further constructed and applied to solve the traveling salesman problem (TSP). In 1000 runs for 10-city TSP, the FM-TCNN achieves a shorter average path distance, a 32.8% faster convergence speed, and a 2.44% higher global optimal rate than the TCNN.

Hyper-Heuristic Based on ACO and Local Search for Dynamic Optimization Problems

Hyper-heuristics comprise a set of approaches that are motivated (at least in part) by the objective of intelligently combining heuristic methods to solve hard optimization problems. Ant colony optimization (ACO) algorithms have been proven to deal with Dynamic Optimization Problems (DOPs) properly. Despite the good results obtained by the integration of local search operators with ACO, little has been done to tackle DOPs. In this research, one of the most reliable ACO schemes, the MAX-MIN Ant System (MMAS), has been integrated with advanced and effective local search operators, resulting in an innovative hyper-heuristic. The local search operators are the Lin–Kernighan (LK) and the Unstringing and Stringing (US) heuristics, and they were intelligently chosen to improve the solution obtained by ACO. The proposed method aims to combine the adaptation capabilities of ACO for DOPs and the good performance of the local search operators chosen in an adaptive way and based on their performance, creating in this way a hyper-heuristic. The travelling salesman problem (TSP) was the base problem to generate both symmetric and asymmetric dynamic test cases. Experiments have shown that the MMAS provides good initial solutions to the local search operators and the hyper-heuristic creates a robust and effective method for the vast majority of test cases.

Special Issue “2021 Selected Papers from Algorithms’ Editorial Board Members”

This is the second edition of a special issue of Algorithms that is of a rather different nature compared to other Special Issues in the journal, which are usually dedicated to a particular subject in the area of algorithms [...]