Comparative Analysis Of Evolutionary Algorithms Performance Based On First Hitting Time

Evolutionary Algorithms(EAs)are types of stochastic heuristic search algorithm that simulates the process of biological evolution.It is widely used in some fields such as function optimization,combinatorial optimization,image processing,and machine learning.However,the inherent complexity of EAs,such as randomness and the difficulty in characterizing the search process,makes its performance difficult to analyze directly.This article takes(1+λ)EA and simulated annealing algorithm as examples,based on the first hitting time construction of the average gain model,equivalent relation model,and interval relation model,and proposes the idea and method of direct comparison analysis of EAs from the perspective of comparing computing time.The main research contents are discussed and verified from both theoretical and case study aspects.(1)To address the issue of difficulty in characterizing the computing time of EAs,this article takes the simulated annealing algorithm as an example and combines first hitting time to propose an average gain model for the simulated annealing algorithm,providing a theoretical basis for analyzing the computing time of the algorithm.Furthermore,the feasibility of the average gain model for the simulated annealing algorithm is verified by designing standard normal distribution mutation operators and uniform distribution mutation operators separately.Experiment results show that the computing time of the simulated annealing algorithm is related to the problem size,and the larger the problem size,the longer the average first hitting time.Additionally,the theoretical analysis and experimental demonstration confirm that the average gain model can be used to analyze the computing time of the simulated annealing algorithm.(2)To address the issue of the difficulty in directly comparing the performance of EAs,this article takes(1+λ)EA as an example and combines the absorbing Markov theory to propose an equivalent relation model based performance comparison model for EAs.Based on this model,the convergence of equivalent classes for EAs is established to provide a theoretical basis for directly comparing the computing time of different algorithms within the same set.Additionally,the computing time of(1+λ)EA is characterized by designing various selection and mutation operators.Experiment results demonstrate that this model can directly realize the comparative analysis of different EAs and through theoretical derivation and experimental verification confirmed the effectiveness of the proposed model,which is consistent with both the theoretical analysis and experimental results.(3)To address the issue of the difficulty in evaluating the interval problem of comparing the performance of different algorithms in the performance comparison model,this article proposes a lower bound expression of the computing time of EAs based on the theory of sub-martingale.Combined with the upper bound of computing time,a interval relation model based on first hitting time is given,which provides a theoretical basis for the comparative analysis of different EAs in linear functions.In addition,the feasibility of the interval relation model was verified by designing an EA with a standard normal distribution mutation operator and an EA with a uniform distribution mutation operator.Experiment results show that the proposed interval relation model can be used as a theoretical tool for the direct comparative analysis of the performance of EAs.