Author: Community

In recent research, hyper-heuristics have attracted increasing attention in various fields. The most appealing feature of hyper-heuristics is that they aim to provide more generalized solutions to optimization problems by searching in a high-level space of heuristics instead of direct problem domains. Despite the promising findings in hyper-heuristics, the design of more general search methodologies still presents a key research. Evolutionary multitasking is a relatively new evolutionary paradigm which attempts to solve multiple optimization problems simultaneously. It exploits the underlying similarities among different optimization tasks by transferring information among them, thus accelerating the optimization of all tasks. Inherently, hyper-heuristics and evolutionary multitasking are similar in the following three ways: 1) they both operate on third-party search spaces; 2) high-level search methodologies are universal; and 3) they both conduct cross-domain optimization. To integrate their advantages effectively, i.e., the knowledge-transfer and cross-domain optimization of evolutionary multitasking and the search in the heuristic spaces of hyper-heuristics, in this article, a unified framework of evolutionary multitasking graph-based hyper-heuristic (EMHH) is proposed. To assess the generality and effectiveness of the EMHH, population-based graph-based hyper-heuristics integrated with evolutionary multitasking to solve exam timetabling and graph-coloring problems, separately and simultaneously, are studied. The experimental results demonstrate the effectiveness, efficiency, and increased the generality of the proposed unified framework compared with single-tasking hyper-heuristics.

Evolutionary computation has brought great progress to rule-based learning but this progress is often blind to the optimality of the system design. This article theoretically reveals an optimal learning scheme on the most popular evolutionary rule-based learning approach—the accuracy-based classifier system (or XCS). XCS seeks to form accurate, maximally general rules that together classify the state space of a given domain. Previously, setting up the system to perform well has been a “blackart” as no systematic approach to XCS parameter tuning existed. We derive a theoretical approach that mathematically guarantees that XCS identifies the accurate rules, which also returns a theoretically valid XCS parameter setting. Then, we demonstrate our theoretical setting derives the maximum correctness of rule-identification in the fewest iterations possible. We also experimentally show that our theoretical setting enables XCS to easily solve several challenging problems where it had previously struggled.

Most evolutionary many-objective optimization (EMaO) algorithms start with a description of a number of the predefined set of reference points on a unit simplex. So far, most studies have used the Das and Dennis’s structured approach for generating well-spaced reference points. Due to the highly structured nature of the procedure, this method cannot produce an arbitrary number of points, which is desired in an EMaO application. Although a layer-wise implementation has been suggested, EMO researchers always felt the need for a more generic approach. Motivated by earlier studies, we introduce a metric for defining well-spaced points on a unit simplex and propose a number of viable methods for generating such a set. We compare the proposed methods on a variety of performance metrics such as hypervolume (HV), deviation in triangularized simplices, distance of the closest point pair, and variance of the geometric means to nearest neighbors in up to 15-D spaces. We show that an iterative improvement based on Riesz $s$ -energy is able to effectively find an arbitrary number of well-spaced points even in higher-dimensional spaces. Reference points created using the proposed Riesz $s$ -energy method for a number of standard combinations of objectives and reference points as well as a source code written in Python are available publicly at https://www.egr.msu.edu/coinlab/blankjul/uniform.

Feature extraction is essential for solving image classification by transforming low-level pixel values into high-level features. However, extracting effective features from images is challenging due to high variations across images in scale, rotation, illumination, and background. Existing methods often have a fixed model complexity and require domain expertise. Genetic programming (GP) with a flexible representation can find the best solution without the use of domain knowledge. This article proposes a new GP-based approach to automatically learning informative features for different image classification tasks. In the new approach, a number of image-related operators, including filters, pooling operators, and feature extraction methods, are employed as functions. A flexible program structure is developed to integrate different functions and terminals into a single tree/solution. The new approach can evolve solutions of variable depths to extract various numbers and types of features from the images. The new approach is examined on 12 different image classification tasks of varying difficulty and compared with a large number of effective algorithms. The results show that the new approach achieves better classification performance than most benchmark methods. The analysis of the evolved programs/solutions and the visualization of the learned features provide deep insights on the proposed approach.

This article investigates the properties of ratio and difference-based indicators under the Minkovsky distance and demonstrates that a ratio-based indicator with infinite norm is the best for solution evaluation among these indicators. Accordingly, a promising-region-based evolutionary many-objective algorithm with the ratio-based indicator is proposed. In our proposed algorithm, a promising region is identified in the objective space using the ratio-based indicator with infinite norm. Since the individuals outside the promising region are of poor quality, we can discard these solutions from the current population. To ensure the diversity of population, a strategy based on the parallel distance is introduced to select individuals in the promising region. In this strategy, all individuals in the promising region are projected vertically onto the normal plane so that crowded distances between them can be calculated. Afterward, two solutions with a smaller distance are selected from the candidate solutions each time, and the solution with the smaller indicator fitness value is removed from the current population. Empirical studies on various benchmark problems with 3–20 objectives show that the proposed algorithm performs competitively on all test problems. Compared with a number of other state-of-the-art evolutionary algorithms, the proposed algorithm is more robust on these problems with various Pareto fronts.

Advertisement, IEEE.

In preference-based optimization, knee points are considered the naturally preferred tradeoff solutions, especially when the decision maker has little a priori knowledge about the problem to be solved. However, identifying all convex knee regions of a Pareto front remains extremely challenging, in particular in a high-dimensional objective space. This article presents a new evolutionary multiobjective algorithm for locating knee regions using two localized dominance relationships. In the environmental selection, the $alpha $ -dominance is applied to each subpopulation partitioned by a set of predefined reference vectors, thereby guiding the search toward different potential knee regions while removing possible dominance resistant solutions. A knee-oriented-dominance measure making use of the extreme points is then proposed to detect knee solutions in convex knee regions and discard solutions in concave knee regions. Our experimental results demonstrate that the proposed algorithm outperforms the state-of-the-art knee identification algorithms on a majority of multiobjective optimization test problems having up to eight objectives and a hybrid electric vehicle controller design problem with seven objectives.

Constrained multiobjective optimization abounds in practical applications and is gaining growing attention in the evolutionary computation community. Artificial test problems are critical to the progress in this research area. Nevertheless, many of them lack important characteristics, such as scalability and variable dependencies, which may be essential in benchmarking modern evolutionary algorithms. This article first proposes a new framework for constrained test problem construction. This framework splits a decision vector into position and distance variables and forces their optimal values to lie on a nonlinear hypersurface such that the interdependencies can be introduced among the position ones and among the distance ones individually. In this framework, two kinds of constraints are designed to introduce convergence-hardness and diversity-hardness, respectively. The first kind introduces infeasible barriers in approaching the optima, and at the same time, makes the position and distance variables interrelate with each other. The second kind restricts the feasible optimal regions such that different shapes of Pareto fronts can be obtained. Based on this framework, we construct 16 scalable and constrained test problems covering a variety of difficulties. Then, in the second part of this article, we evaluate the performance of some state of the art on the proposed test problems, showing that they are quite challenging and there is room for further enhancement of the existing algorithms. Finally, we discuss in detail the source of difficulties presented in these new problems.