Time Complexity of Evolutionary Algorithms for Combinatorial Optimization:A Decade of Results

Computational time complexity analyzes of evolutionary algorithms （EAs） have been performed since the mid-nineties. The first results were related to very simple algorithms, such as the （1＋1）-EA, on toy problems. These efforts produced a deeper understanding of how EAs perform on different kinds of fitness landscapes and general mathematical tools that may be extended to the analysis of more complicated EAs on more realistic problems. In fact, in recent years, it has been possible to analyze the （1＋1）-EA on combinatorial optimization problems with practical applications and more realistic population-based EAs on structured toy problems. This paper presents a survey of the results obtained in the last decade along these two research lines. The most common mathematical techniques are introduced, the basic ideas behind them are discussed and their elective applications are highlighted. Solved problems that were still open are enumerated as are those still awaiting for a solution. New questions and problems arisen in the meantime are also considered.

A Theoretical Comparison among Recursive Algorithms for Fast Computation of Zernike Moments Using the Concept of Time Complexity

Zernike polynomials have been used in different fields such as optics, astronomy, and digital image analysis for many years. To form these polynomials, Zernike moments are essential to be determined. One of the main issues in realizing the moments is using factorial terms in their equation which causes higher time complexity. As a solution, several methods have been presented to reduce the time complexity of these polynomials in recent years. The purpose of this research is to study several methods among the most popular recursive methods for fast Zernike computation and compare them together by a global theoretical evaluation system called worst-case time complexity. In this study, we have analyzed the selected algorithms and calculated the worst-case time complexity for each one. After that, the results are represented and explained and finally, a conclusion has been made by comparing these criteria among the studied algorithms. According to time complexity, we have observed that although some algorithms such as Wee method and Modified Prata method were successful in having the smaller time complexities, some other approaches did not make any significant difference compared to the classical algorithm.

Improved reduced-complexity bit and power allocation algorithms for multicarrier systems

Based on the iterative bit-filling procedure, a computationally efficient bit and power allocation algorithm is presented. The algorithm improves the conventional bit-filling algorithms by maintaining only a subset of subcarriers for computation in each iteration, which reduces the complexity without any performance degradation. Moreover, a modified algorithm with even lower complexity is developed, and equal power allocation is introduced as an initial allocation to accelerate its convergence. Simulation results show that the modified algorithm achieves a considerable complexity reduction while causing only a minor drop in performance.

Highly Accurate Golden Section Search Algorithms and Fictitious Time Integration Method for Solving Nonlinear Eigenvalue Problems

This study sets up two new merit functions,which are minimized for the detection of real eigenvalue and complex eigenvalue to address nonlinear eigenvalue problems.For each eigen-parameter the vector variable is solved from a nonhomogeneous linear system obtained by reducing the number of eigen-equation one less,where one of the nonzero components of the eigenvector is normalized to the unit and moves the column containing that component to the right-hand side as a nonzero input vector.1D and 2D golden section search algorithms are employed to minimize the merit functions to locate real and complex eigenvalues.Simultaneously,the real and complex eigenvectors can be computed very accurately.A simpler approach to the nonlinear eigenvalue problems is proposed,which implements a normalization condition for the uniqueness of the eigenvector into the eigenequation directly.The real eigenvalues can be computed by the fictitious time integration method(FTIM),which saves computational costs compared to the one-dimensional golden section search algorithm(1D GSSA).The simpler method is also combined with the Newton iterationmethod,which is convergent very fast.All the proposed methods are easily programmed to compute the eigenvalue and eigenvector with high accuracy and efficiency.

Polynomial Complexity Bounds of Mehrotra-type Predictor-corrector Algorithms for Linear Programming over Symmetric Cones

We establish polynomial complexity corrector algorithms for linear programming over bounds of the Mehrotra-type predictor- symmetric cones. We first slightly modify the maximum step size in the predictor step of the safeguard based Mehrotra-type algorithm for linear programming, that was proposed by Salahi et al. Then, using the machinery of Euclidean Jordan algebras, we extend the modified algorithm to symmetric cones. Based on the Nesterov-Todd direction, we obtain O（r log ε1） iteration complexity bound of this algorithm, where r is the rank of the Jordan algebras and ε is the required precision. We also present a new variant of Mehrotra-type algorithm using a new adaptive updating scheme of centering parameter and show that this algorithm enjoys the same order of complexity bound as the safeguard algorithm. We illustrate the numerical behaviour of the methods on some small examples.

Complexity analysis of interior-point algorithm based on a new kernel function for semidefinite optimization

Interior-point methods （IPMs） for linear optimization （LO） and semidefinite optimization （SDO） have become a hot area in mathematical programming in the last decades. In this paper, a new kernel function with simple algebraic expression is proposed. Based on this kernel function, a primal-dual interior-point methods （IPMs） for semidefinite optimization （SDO） is designed. And the iteration complexity of the algorithm as O（n^3/4 log n/ε） with large-updates is established. The resulting bound is better than the classical kernel function, with its iteration complexity O（n log n/ε） in large-updates case.

Timing Advanced Estimation Algorithm of Low Complexity Based on DFT Spectrum Analysis for Satellite System

In satellite mobile communication system, relative movement of the satellite and the terminal will cause a large Doppler offset. Timing advanced estimation with Zadoff-Chu sequence is sensitive to the frequency offset. When the frequency offset is larger than one times subcarrier spacing, the value of peak cannot be detected at the receiving end. To suppress the larger Doppler frequency shift, this paper proposes a novel timing advanced estimation scheme(TAE-MCD) for satellite communication system. In this algorithm, t r a n s m i t t e d s i g n a l i s d i v i d e d i n t o Z C sequence and its conjugate sequence. Using multiplication and DFT operation to find the estimated peak at the receiving end, and make subtraction with the obtained sequences at last. The scheme can not only inhibit the adverse effects of large Doppler frequency shift in timing estimation effectively, but also reduce the computational complexity at the receiving end and improve the work efficiency of the hardware. Simulations results show that TAEMCD outperform the existing timing advanced estimation methods, on the condition of no additional time and frequency resource are needed.

Optimizing Connections:Applied Shortest Path Algorithms for MANETs

This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.

Concise review of relaxations and approximation algorithms for nonidentical parallel-machine scheduling to minimize total weighted completion times

A class of nonidentical parallel machine scheduling problems are considered in which the goal is to minimize the total weighted completion time. Models and relaxations are collected. Most of these problems are NP-hard, in the strong sense, or open problems, therefore approximation algorithms are studied. The review reveals that there exist some potential areas worthy of further research.

Correlation between detrended fluctuation analysis and the Lempel-Ziv complexity in nonlinear time series analysis

We study the correlation between detrended fluctuation analysis（DFA） and the Lempel-Ziv complexity（LZC） in nonlinear time series analysis in this paper.Typical dynamic systems including a logistic map and a Duffing model are investigated.Moreover,the influence of Gaussian random noise on both the DFA and LZC are analyzed.The results show a high correlation between the DFA and LZC,which can quantify the non-stationarity and the nonlinearity of the time series,respectively.With the enhancement of the random component,the exponent α and the normalized complexity index C show increasing trends.In addition,C is found to be more sensitive to the fluctuation in the nonlinear time series than α.Finally,the correlation between the DFA and LZC is applied to the extraction of vibration signals for a reciprocating compressor gas valve,and an effective fault diagnosis result is obtained.

Intelligent recognition and information extraction of radar complex jamming based on time-frequency features

In modern war,radar countermeasure is becoming increasingly fierce,and the enemy jamming time and pattern are changing more randomly.It is challenging for the radar to efficiently identify jamming and obtain precise parameter information,particularly in low signal-to-noise ratio(SNR)situations.In this paper,an approach to intelligent recognition and complex jamming parameter estimate based on joint time-frequency distribution features is proposed to address this challenging issue.Firstly,a joint algorithm based on YOLOv5 convolutional neural networks(CNNs)is proposed,which is used to achieve the jamming signal classification and preliminary parameter estimation.Furthermore,an accurate jamming key parameters estimation algorithm is constructed by comprehensively utilizing chi-square statistical test,feature region search,position regression,spectrum interpolation,etc.,which realizes the accurate estimation of jamming carrier frequency,relative delay,Doppler frequency shift,and other parameters.Finally,the approach has improved performance for complex jamming recognition and parameter estimation under low SNR,and the recognition rate can reach 98%under−15 dB SNR,according to simulation and real data verification results.

Vehicle routing optimization algorithm based on time windows and dynamic demand

To provide the supplier with the minimizum vehicle travel distance in the distribution process of goods in three situations of new customer demand,customer cancellation service,and change of customer delivery address,based on the ideas of pre-optimization and real-time optimization,a two-stage planning model of dynamic demand based vehicle routing problem with time windows was established.At the pre-optimization stage,an improved genetic algorithm was used to obtain the pre-optimized distribution route,a large-scale neighborhood search method was integrated into the mutation operation to improve the local optimization performance of the genetic algorithm,and a variety of operators were introduced to expand the search space of neighborhood solutions;At the real-time optimization stage,a periodic optimization strategy was adopted to transform a complex dynamic problem into several static problems,and four neighborhood search operators were used to quickly adjust the route.Two different scale examples were designed for experiments.It is proved that the algorithm can plan the better route,and adjust the distribution route in time under the real-time constraints.Therefore,the proposed algorithm can provide theoretical guidance for suppliers to solve the dynamic demand based vehicle routing problem.

Inversion of Seabed Geotechnical Properties in the Arctic Chukchi Deep Sea Basin Based on Time Domain Adaptive Search Matching Algorithm

The chirp sub-bottom profiler,for its high resolution,easy accessibility and cost-effectiveness,has been widely used in acoustic detection.In this paper,the acoustic impedance and grain size compositions were obtained based on the chirp sub-bottom profiler data collected in the Chukchi Plateau area during the 11th Arctic Expedition of China.The time-domain adaptive search matching algorithm was used and validated on our established theoretical model.The misfit between the inversion result and the theoretical model is less than 0.067%.The grain size was calculated according to the empirical relationship between the acoustic impedance and the grain size of the sediment.The average acoustic impedance of sub-seafloor strata is 2.5026×10^(6) kg(s m^(2))^(-1)and the average grain size(θvalue)of the seafloor surface sediment is 7.1498,indicating the predominant occurrence of very fine silt sediment in the study area.Comparison of the inversion results and the laboratory measurements of nearby borehole samples shows that they are in general agreement.

Arrhythmia Detection by Using Chaos Theory with Machine Learning Algorithms

Heart monitoring improves life quality.Electrocardiograms(ECGs or EKGs)detect heart irregularities.Machine learning algorithms can create a few ECG diagnosis processing methods.The first method uses raw ECG and time-series data.The second method classifies the ECG by patient experience.The third technique translates ECG impulses into Q waves,R waves and S waves(QRS)features using richer information.Because ECG signals vary naturally between humans and activities,we will combine the three feature selection methods to improve classification accuracy and diagnosis.Classifications using all three approaches have not been examined till now.Several researchers found that Machine Learning(ML)techniques can improve ECG classification.This study will compare popular machine learning techniques to evaluate ECG features.Four algorithms—Support Vector Machine(SVM),Decision Tree,Naive Bayes,and Neural Network—compare categorization results.SVM plus prior knowledge has the highest accuracy(99%)of the four ML methods.QRS characteristics failed to identify signals without chaos theory.With 99.8%classification accuracy,the Decision Tree technique outperformed all previous experiments.

A Class of Fast Algorithms in Real-Time Simulation

A class of hybrid algorithms of real-time simulation based on evaluation of non-integerstep right-hand side function are presented in this paper. And some results of the convergence and stability of the algorithms are given. Using the class of algorithms, evaluation for the right-hand side function is needed once in every integration-step. Moreover, comparing with the other methods with the same amount of work, their numerical stability regions are larger and the method errors are smaller, and the numerical experiments show that the algorithms are very effective.

A Class of Parallel Algorithms of Real-TimeNumerical Simulation for Stiff Dynamic System

In this paper a class of real-time parallel modified Rosenbrock methods of numerical simulation is constructed for stiff dynamic systems on a multiprocessor system, and convergence and numerical stability of these methods are discussed. A-stable real-time parallel formula of two-stage third-order and A(α)-stable real-time parallel formula with o ≈ 89.96° of three-stage fourth-order are particularly given. The numerical simulation experiments in parallel environment show that the class of algorithms is efficient and applicable, with greater speedup.

Drift Analysis in Studying the Convergence and Hitting Times of Evolutionary Algorithms: An Overview

This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with Markov chains or supermartingales. Then the drift conditions which guarantee the convergence of evolutionary algorithms are described. And next the drift conditions which are used to estimate the hitting times of evolutionary algorithms are presented. Finally an example is given to show how to analyse hitting times of EAs by drift analysis approach.

A CLASS OF EBE TIME INTEGRATION ALGORITHMS FOR TRANSIENT FINITE ELEMENT STRUCTURAL DYNAMICAL ANALYSIS

A new class of algorithms for trails lent finite element structural dynamical analysis which is amenable to all efficient implementation inl parallel computers (especially Massively Parallel Computers) is proposed. The suitability of the method for parallel computation stems from the fact that, gived an arbitrary partition of the finite element mesh, each element in the partition can be processed over a time step independently and simultaneously with the rest, and no global equation solving effort is involved. Although the Proposed EBE time integration algorithms are shown to have the structure of an explicit scheme, they are unconditionally stable over a certain range of the algorithmic parameter.

Cellular automation model of faults and algorithmic complexity

In this paper, we use the cellular automation model to imitate earthquake process and draw some conclusionsof general applicability. First, it is confirmed that earthquake process has some ordering characters, and it isshown that both the existence and their mutual arrangement of faults could obviously influence the overallcharacters of earthquake process. Then the characters of each stage of model evolution are explained withself-organized critical state theory. Finally, earthquake sequences produced by the models are analysed interms pf algorithmic complexity and the result shows that AC-values of algorithmic complexity could be usedto study earthquake process and evolution.

Space Complexity of Algorithm for Modular Multiplicative Inverse

In certain computational systems the amount of space required to execute an algorithm is even more restrictive than the corresponding time necessary for solution of a problem. In this paper an algorithm for modular multiplicative inverse is introduced and its computational space complexity is analyzed. A tight upper bound for bit storage required for execution of the algorithm is provided. It is demonstrated that for range of numbers used in public-key encryption systems, the size of bit storage does not exceed a 2K-bit threshold in the worst-case. This feature of the Enhanced-Euclid algorithm allows designing special-purpose hardware for its implementation as a subroutine in communication-secure wireless devices.