Estimation of Distribution Algorithm for Grammar-Guided Genetic Programming.

Genetic variation operators in grammar-guided genetic programming are fundamental to guide the evolutionary process in search and optimization problems. However, they show some limitations, mainly derived from an unbalanced exploration and local-search trade-off. This article presents an estimation of distribution algorithm for grammar-guided genetic programming to overcome this difficulty and thus increase the performance of the evolutionary algorithm. Our proposal employs an extended dynamic stochastic context-free grammar to encode and calculate the estimation of the distribution of the search space from some promising individuals in the population. Unlike traditional estimation of distribution algorithms, the proposed approach improves exploratory behavior by smoothing the estimated distribution model. Therefore, this algorithm is referred to as SEDA, smoothed estimation of distribution algorithm. Experiments have been conducted to compare overall performance using a typical genetic programming crossover operator, an incremental estimation of distribution algorithm, and the proposed approach after tuning their hyperparameters. These experiments involve challenging problems to test the local search and exploration features of the three evolutionary systems. The results show that grammar-guided genetic programming with SEDA achieves the most accurate solutions with an intermediate convergence speed.

TIVC: An Efficient Local Search Algorithm for Minimum Vertex Cover in Large Graphs.

The minimum vertex cover (MVC) problem is a canonical NP-hard combinatorial optimization problem aiming to find the smallest set of vertices such that every edge has at least one endpoint in the set. This problem has extensive applications in cybersecurity, scheduling, and monitoring link failures in wireless sensor networks (WSNs). Numerous local search algorithms have been proposed to obtain "good" vertex coverage. However, due to the NP-hard nature, it is challenging to efficiently solve the MVC problem, especially on large graphs. In this paper, we propose an efficient local search algorithm for MVC called TIVC, which is based on two main ideas: a 3-improvements (TI) framework with a tiny perturbation and edge selection strategy. We conducted experiments on real-world large instances of a massive graph benchmark. Compared with three state-of-the-art MVC algorithms, TIVC shows superior performance in accuracy and possesses a remarkable ability to identify significantly smaller vertex covers on many graphs.

Optimized Classification of Intelligent Reflecting Surface (IRS)-Enabled GEO Satellite Signals.

The intelligent reflecting surface (IRS) is a cutting-edge technology for cost-effectively achieving future spectrum- and energy-efficient wireless communication. In particular, an IRS comprises many low-cost passive devices that can independently reflect the incident signal with a configurable phase shift to produce three-dimensional (3D) passive beamforming without transmitting Radio-Frequency (RF) chains. Thus, the IRS can be utilized to greatly improve wireless channel conditions and increase the dependability of communication systems. This article proposes a scheme for an IRS-equipped GEO satellite signal with proper channel modeling and system characterization. Gabor filter networks (GFNs) are jointly proposed for the extraction of distinct features and the classification of these features. Hybrid optimal functions are used to solve the estimated classification problem, and a simulation setup was designed along with proper channel modeling. The experimental results show that the proposed IRS-based methodology provides higher classification accuracy than the benchmark without the IRS methodology.

Cost-neutral reduction of infection risk in picker-to-parts warehousing systems.

The rapid and severe outbreak of COVID-19 caused by SARS-CoV-2 has heavily impacted warehouse operations around the world. In particular, picker-to-parts warehousing systems, in which human pickers collect requested items by moving from picking location to picking location, are very susceptible to the spread of infection among pickers because the latter generally work close to each other. This paper aims to mitigate the risk of infection in manual order picking. Given multiple pickers, each associated with a given sequence of picking tours for collecting the items specified by a picking order, we aim to execute the tours in a way that minimizes the time pickers simultaneously spend in the same picking aisles, but without changing the distance traveled by the pickers. To achieve this, we exploit the degrees of freedom induced by the fact that picking tours contain cycles which can be traversed in both directions, i.e., at the entry to each of these cycles, the decision makers can decide between the two possible directions. We formulate the resulting picking tour execution problem as a mixed integer program and propose an efficient iterated local search heuristic to solve it. In extensive numerical studies, we show that an average reduction of 50% of the total temporal overlap between pickers can be achieved compared to randomly executing the picking tours. Moreover, we compare our approach to a zone picking approach, in which infection risk between pickers can be almost eliminated. However, compared to our approach, the results show that the zone picking approach increases the makespan by up to 1066%.

Stagnation Detection with Randomized Local Search.

Recently a mechanism called stagnation detection was proposed that automatically adjusts the mutation rate of evolutionary algorithms when they encounter local optima. The so-called SD-(1+1) EA introduced by Rajabi and Witt (2022) adds stagnation detection to the classical (1+1) EA with standard bit mutation. This algorithm flips each bit independently with some mutation rate, and stagnation detection raises the rate when the algorithm is likely to have encountered a local optimum. In this article, we investigate stagnation detection in the context of the k-bit flip operator of randomized local search that flips k bits chosen uniformly at random and let stagnation detection adjust the parameter k. We obtain improved runtime results compared with the SD-(1+1) EA amounting to a speedup of at least (1-o(1))2πm, where m is the so-called gap size, that is, the distance to the next improvement. Moreover, we propose additional schemes that prevent infinite optimization times even if the algorithm misses a working choice of k due to unlucky events. Finally, we present an example where standard bit mutation still outperforms the k-bit flip operator with stagnation detection.

A Review on Planted (l, d) Motif Discovery Algorithms for Medical Diagnose.

Personalized diagnosis of chronic disease requires capturing the continual pattern across the biological sequence. This repeating pattern in medical science is called "Motif". Motifs are the short, recurring patterns of biological sequences that are supposed signify some health disorder. They identify the binding sites for transcription factors that modulate and synchronize the gene expression. These motifs are important for the analysis and interpretation of various health issues like human disease, gene function, drug design, patient's conditions, etc. Searching for these patterns is an important step in unraveling the mechanisms of gene expression properly diagnose and treat chronic disease. Thus, motif identification has a vital role in healthcare studies and attracts many researchers. Numerous approaches have been characterized for the motif discovery process. This article attempts to review and analyze fifty-four of the most frequently found motif discovery processes/algorithms from different approaches and summarizes the discussion with their strengths and weaknesses.

Deep CNN with Hybrid Binary Local Search and Particle Swarm Optimizer for Exudates Classification from Fundus Images.

Diabetic retinopathy is a chronic condition that causes vision loss if not detected early. In the early stage, it can be diagnosed with the aid of exudates which are called lesions. However, it is arduous to detect the exudate lesion due to the availability of blood vessels and other distractions. To tackle these issues, we proposed a novel exudates classification from the fundus image known as hybrid convolutional neural network (CNN)-based binary local search optimizer-based particle swarm optimization algorithm. The proposed method from this paper exploits image augmentation to enlarge the fundus image to the required size without losing any features. The features from the resized fundus images are extracted as a feature vector and fed into the feed-forward CNN as the input. Henceforth, it classifies the exudates from the fundus image. Further, the hyperparameters are optimized to reduce the computational complexities by utilization of binary local search optimizer (BLSO) and particle swarm optimization (PSO). The experimental analysis is conducted on the public ROC and real-time ARA400 datasets and compared with the state-of-art works such as support vector machine classifiers, multi-modal/multi-scale, random forest, and CNN for the performance metrics. The classification accuracy is high for the proposed work, and thus, our proposed outperforms all the other approaches.

Initial Solution Generation and Diversified Variable Picking in Local Search for (Weighted) Partial MaxSAT.

The (weighted) partial maximum satisfiability ((W)PMS) problem is an important generalization of the classic problem of propositional (Boolean) satisfiability with a wide range of real-world applications. In this paper, we propose an initialization and a diversification strategy to improve local search for the (W)PMS problem. Our initialization strategy is based on a novel definition of variables' structural entropy, and it aims to generate a solution that is close to a high-quality feasible one. Then, our diversification strategy picks a variable in two possible ways, depending on a parameter: continuing to pick variables with the best benefits or focusing on a clause with the greatest penalty and then selecting variables probabilistically. Based on these strategies, we developed a local search solver dubbed ImSATLike, as well as a hybrid solver ImSATLike-TT, and experimental results on (weighted) partial MaxSAT instances in recent MaxSAT Evaluations show that they outperform or have nearly the same performances as state-of-the-art local search and hybrid competitors, respectively, in general. Furthermore, we carried out experiments to confirm the individual impacts of each proposed strategy.

Metaheuristic Algorithms Based on Compromise Programming for the Multi-Objective Urban Shipment Problem.

The Vehicle Routing Problem (VRP) and its variants are found in many fields, especially logistics. In this study, we introduced an adaptive method to a complex VRP. It combines multi-objective optimization and several forms of VRPs with practical requirements for an urban shipment system. The optimizer needs to consider terrain and traffic conditions. The proposed model also considers customers' expectations and shipper considerations as goals, and a common goal such as transportation cost. We offered compromise programming to approach the multi-objective problem by decomposing the original multi-objective problem into a minimized distance-based problem. We designed a hybrid version of the genetic algorithm with the local search algorithm to solve the proposed problem. We evaluated the effectiveness of the proposed algorithm with the Tabu Search algorithm and the original genetic algorithm on the tested dataset. The results show that our method is an effective decision-making tool for the multi-objective VRP and an effective solver for the new variation of VRP.

Iterated local search with partition crossover for computational protein design.

Structure-based computational protein design (CPD) refers to the problem of finding a sequence of amino acids which folds into a specific desired protein structure, and possibly fulfills some targeted biochemical properties. Recent studies point out the particularly rugged CPD energy landscape, suggesting that local search optimization methods should be designed and tuned to easily escape local minima attraction basins. In this article, we analyze the performance and search dynamics of an iterated local search (ILS) algorithm enhanced with partition crossover. Our algorithm, PILS, quickly finds local minima and escapes their basins of attraction by solution perturbation. Additionally, the partition crossover operator exploits the structure of the residue interaction graph in order to efficiently mix solutions and find new unexplored basins. Our results on a benchmark of 30 proteins of various topology and size show that PILS consistently finds lower energy solutions compared to Rosetta fixbb and a classic ILS, and that the corresponding sequences are mostly closer to the native.