Bai Yan

Qi Zhao, Qiqi Duan, Bai Yan et al.

Metaheuristics have gained great success in academia and practice because their search logic can be applied to any problem with available solution representation, solution quality evaluation, and certain notions of locality. Manually designing metaheuristic algorithms for solving a target problem is criticized for being laborious, error-prone, and requiring intensive specialized knowledge. This gives rise to increasing interest in automated design of metaheuristic algorithms. With computing power to fully explore potential design choices, the automated design could reach and even surpass human-level design and could make high-performance algorithms accessible to a much wider range of researchers and practitioners. This paper presents a broad picture of automated design of metaheuristic algorithms, by conducting a survey on the common grounds and representative techniques in terms of design space, design strategies, performance evaluation strategies, and target problems in this field.

Qi Zhao, Bai Yan, Taiwei Hu et al.

Metaheuristics are widely recognized gradient-free solvers to hard problems that do not meet the rigorous mathematical assumptions of conventional solvers. The automated design of metaheuristic algorithms provides an attractive path to relieve manual design effort and gain enhanced performance beyond human-made algorithms. However, the specific algorithm prototype and linear algorithm representation in the current automated design pipeline restrict the design within a fixed algorithm structure, which hinders discovering novelties and diversity across the metaheuristic family. To address this challenge, this paper proposes a general framework, AutoOpt, for automatically designing metaheuristic algorithms with diverse structures. AutoOpt contains three innovations: (i) A general algorithm prototype dedicated to covering the metaheuristic family as widely as possible. It promotes high-quality automated design on different problems by fully discovering potentials and novelties across the family. (ii) A directed acyclic graph algorithm representation to fit the proposed prototype. Its flexibility and evolvability enable discovering various algorithm structures in a single run of design, thus boosting the possibility of finding high-performance algorithms. (iii) A graph representation embedding method offering an alternative compact form of the graph to be manipulated, which ensures AutoOpt's generality. Experiments on numeral functions and real applications validate AutoOpt's efficiency and practicability.

Qi Zhao, Bai Yan, Taiwei Hu et al.

Metaheuristics are prominent gradient-free optimizers for solving hard problems that do not meet the rigorous mathematical assumptions of analytical solvers. The canonical manual optimizer design could be laborious, untraceable and error-prone, let alone human experts are not always available. This arises increasing interest and demand in automating the optimizer design process. In response, this paper proposes AutoOptLib, the first platform for accessible automated design of metaheuristic optimizers. AutoOptLib leverages computing resources to conceive, build up, and verify the design choices of the optimizers. It requires much less labor resources and expertise than manual design, democratizing satisfactory metaheuristic optimizers to a much broader range of researchers and practitioners. Furthermore, by fully exploring the design choices with computing resources, AutoOptLib has the potential to surpass human experience, subsequently gaining enhanced performance compared with human problem-solving. To realize the automated design, AutoOptLib provides 1) a rich library of metaheuristic components for continuous, discrete, and permutation problems; 2) a flexible algorithm representation for evolving diverse algorithm structures; 3) different design objectives and techniques for different optimization scenarios; and 4) a graphic user interface for accessibility and practicability. AutoOptLib is fully written in Matlab/Octave; its source code and documentation are available at https://github.com/qz89/AutoOpt and https://AutoOpt.readthedocs.io/, respectively.

Bai Yan, Qi Zhao, Jin Zhang et al.

Gridless methods show great superiority in line spectral estimation. These methods need to solve an atomic $l_0$ norm (i.e., the continuous analog of $l_0$ norm) minimization problem to estimate frequencies and model order. Since this problem is NP-hard to compute, relaxations of atomic $l_0$ norm, such as nuclear norm and reweighted atomic norm, have been employed for promoting sparsity. However, the relaxations give rise to a resolution limit, subsequently leading to biased model order and convergence error. To overcome the above shortcomings of relaxation, we propose a novel idea of simultaneously estimating the frequencies and model order by means of the atomic $l_0$ norm. To accomplish this idea, we build a multiobjective optimization model. The measurment error and the atomic $l_0$ norm are taken as the two optimization objectives. The proposed model directly exploits the model order via the atomic $l_0$ norm, thus breaking the resolution limit. We further design a variable-length evolutionary algorithm to solve the proposed model, which includes two innovations. One is a variable-length coding and search strategy. It flexibly codes and interactively searches diverse solutions with different model orders. These solutions act as steppingstones that help fully exploring the variable and open-ended frequency search space and provide extensive potentials towards the optima. Another innovation is a model order pruning mechanism, which heuristically prunes less contributive frequencies within the solutions, thus significantly enhancing convergence and diversity. Simulation results confirm the superiority of our approach in both frequency estimation and model order selection.