A New Approach for Analyzing Average Time Complexity of Population-Based Evolutionary Algorithms on Unimodal Problems

In the past decades, many theoretical results related to the time complexity of evolutionary algorithms (EAs) on different problems are obtained. However, there is not any general and easy-to-apply approach designed particularly for population-based EAs on unimodal problems. In this paper, we first generalize the concept of the takeover time to EAs with mutation, then we utilize the generalized takeover time to obtain the mean first hitting time of EAs and, thus, propose a general approach for analyzing EAs on unimodal problems. As examples, we consider the so-called $(N + N)$ EAs and we show that, on two well-known unimodal problems, leadingones and onemax , the EAs with the bitwise mutation and two commonly used selection schemes both need $O(nln n + n^{2}/N)$ and $O(n lnln n + nln n/N)$ generations to find the global optimum, respectively. Except for the new results above, our approach can also be applied directly for obtaining results for some population-based EAs on some other unimodal problems. Moreover, we also discuss when the general approach is valid to provide us tight bounds of the mean first hitting times and when our approach should be combined with problem-specific knowledge to get the tight bounds. It is the first time a general idea for analyzing population-based EAs on unimodal problems is discussed theoretically.      

A new approach to estimating the expected first hitting time of evolutionary algorithms

Evolutionary algorithms (EA) have been shown to be very effective in solving practical problems, yet many important theoretical issues of them are not clear. The expected first hitting time is one of the most important theoretical issues of evolutionary algorithms, since it implies the average computational time complexity. In this paper, we establish a bridge between the expected first hitting time and another important theoretical issue, i.e., convergence rate. Through this bridge, we propose a new general approach to estimating the expected first hitting time. Using this approach, we analyze EAs with different configurations, including three mutation operators, with/without population, a recombination operator and a time variant mutation operator, on a hard problem. The results show that the proposed approach is helpful for analyzing a broad range of evolutionary algorithms. Moreover, we give an explanation of what makes a problem hard to EAs, and based on the recognition, we prove the hardness of a general problem.     

A Runtime Analysis of Evolutionary Algorithms for Constrained Optimization Problems

Although there are many evolutionary algorithms (EAs) for solving constrained optimization problems, there are few rigorous theoretical analyses. This paper presents a time complexity analysis of EAs for solving constrained optimization. It is shown when the penalty coefficient is chosen properly, direct comparison between pairs of solutions using penalty fitness function is equivalent to that using the criteria ldquosuperiority of feasible pointrdquo or ldquosuperiority of objective function value.rdquo This paper analyzes the role of penalty coefficients in EAs in terms of time complexity. The results show that in some examples, EAs benefit greatly from higher penalty coefficients, while in other examples, EAs benefit from lower penalty coefficients. This paper also investigates the runtime of EAs for solving the 0-1 knapsack problem and the results indicate that the mean first hitting times ranges from a polynomial-time to an exponential time when different penalty coefficients are used.     

Drift conditions for estimating the first hitting times of evolutionary algorithms

For the global optimization problems with continuous variables, evolutionary algorithms (EAs) are often used to find the approximate solutions. The number of generations for an EA to find the approximate solutions, called the first hitting time, is an important index to measure the performance of the EA. However, calculating the first hitting time is still difficult in theory. This paper proposes some new drift conditions that are used to estimate the upper bound of the first hitting times of EAs for finding the approximate solutions. Two case studies are given to show how to apply these conditions to estimate the first hitting times.     

Population size versus runtime of a simple evolutionary algorithm

Evolutionary algorithms (EAs) find numerous applications, and practical knowledge on EAs is immense. In practice, sophisticated population-based EAs employing selection, mutation and crossover are applied. In contrast, theoretical analysis of EAs often concentrates on very simple algorithms such as the (1+1) EA, where the population size equals 1. In this paper, the question is addressed whether the use of a population by itself can be advantageous. A population-based EA that neither makes use of crossover nor any diversity-maintaining operator is investigated on an example function. It is shown that an increase of the population size by a constant factor decreases the expected runtime from exponential to polynomial. Thereby, the best gap known so far is improved from superpolynomial vs. polynomial to exponential vs. polynomial. Moreover, it is proved that the exponential and polynomial runtime bounds occur with a probability exponentially close to one if the population size is a constant (resp., a small polynomial). Finally, a second example function, where only a small population leads to a polynomial runtime, and a hierarchy result on the appropriate population size are presented. The analyses show formally how the population size can lead to different attractors in the search space.     

Reducing the run-time complexity of multiobjective EAs: The NSGA-II and other algorithms

The last decade has seen a surge of research activity on multiobjective optimization using evolutionary computation and a number of well performing algorithms have been published. The majority of these algorithms use fitness assignment based on Pareto-domination: Nondominated sorting, dominance counting, or identification of the nondominated solutions. The success of these algorithms indicates that this type of fitness is suitable for multiobjective problems, but so far the use of Pareto-based fitness has lead to program run times in O(GMN/sup 2/), where G is the number of generations, M is the number of objectives, and N is the population size. The N/sup 2/ factor should be reduced if possible, since it leads to long processing times for large population sizes. This paper presents a new and efficient algorithm for nondominated sorting, which can speed up the processing time of some multiobjective evolutionary algorithms (MOEAs) substantially. The new algorithm is incorporated into the nondominated sorting genetic algorithm II (NSGA-II) and reduces the overall run-time complexity of this algorithm to O(GN log/sup M-1/N), much faster than the O(GMN/sup 2/) complexity published by Deb et al. (2002). Experiments demonstrate that the improved version of the algorithm is indeed much faster than the previous one. The paper also points out that multiobjective EAs using fitness based on dominance counting and identification of nondominated solutions can be improved significantly in terms of running time by using efficient algorithms known from computer science instead of inefficient O(MN/sup 2/) algorithms.     

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-baeed 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.     

Set Cover和Hitting Set问题的研究进展

Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。     

Runtime analysis of the (mu+1) EA on simple Pseudo-Boolean functions

Although Evolutionary Algorithms (EAs) have been successfully applied to optimization in discrete search spaces, theoretical developments remain weak, in particular for population-based EAs. This paper presents a first rigorous analysis of the (mu+1) EA on pseudo-Boolean functions. Using three well-known example functions from the analysis of the (1+1) EA, we derive bounds on the expected runtime and success probability. For two of these functions, upper and lower bounds on the expected runtime are tight, and on all three functions, the (mu+1) EA is never more efficient than the (1+1) EA. Moreover, all lower bounds grow with mu. On a more complicated function, however, a small increase of mu probably decreases the expected runtime drastically.This paper develops a new proof technique that bounds the runtime of the (mu+1) EA. It investigates the stochastic process for creating family trees of individuals; the depth of these trees is bounded. Thereby, the progress of the population towards the optimum is captured. This new technique is general enough to be applied to other population-based EAs.     

A study of drift analysis for estimating computation time of evolutionary algorithms

This paper introduces drift analysis and its applications in estimating average computation time of evolutionary algorithms. Firstly, drift conditions for estimating upper and lower bounds of the mean first hitting times of evolutionary algorithms are presented. Then drift analysis is applied to two specific evolutionary algorithms and problems. Finally, a general classification of easy and hard problems for evolutionary algorithmsis given based on the analysis.     

A rigorous complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs

Evolutionary algorithms (EAs) are heuristic randomized algorithms which, by many impressive experiments, have been proven to behave quite well for optimization problems of various kinds. In this paper a rigorous theoretical complexity analysis of the (1 + 1) evolutionary algorithm for separable functions with Boolean inputs is given. Different mutation rates are compared, and the use of the crossover operator is investigated. The main contribution is not the result that the expected run time of the (1 + 1) evolutionary algorithm is theta (n ln n) for separable functions with n variables but the methods by which this result can be proven rigorously.     

Evolutionary algorithms based design of multivariable PID controller

In this paper, performance comparison of evolutionary algorithms (EAs) such as real coded genetic algorithm (RGA), modified particle swarm optimization (MPSO), covariance matrix adaptation evolution strategy (CMAES) and differential evolution (DE) on optimal design of multivariable PID controller design is considered. Decoupled multivariable PI and PID controller structure for Binary distillation column plant described by Wood and Berry, having 2 inputs and 2 outputs is taken. EAs simulations are carried with minimization of IAE as objective using two types of stopping criteria, namely, maximum number of functional evaluations (Fevalmax) and Fevalmax along with tolerance of PID parameters and IAE. To compare the performances of various EAs, statistical measures like best, mean, standard deviation of results and average computation time, over 20 independent trials are considered. Results obtained by various EAs are compared with previously reported results using BLT and GA with multi-crossover approach. Results clearly indicate the better performance of CMAES and MPSO designed PI/PID controller on multivariable system. Simulations also reveal that all the four algorithms considered are suitable for off-line tuning of PID controller. However, only CMAES and MPSO algorithms are suitable for on-line tuning of PID due to their better consistency and minimum computation time.     

关于漂移分析的注记

进化算法成功应用于求解各种复杂优化问题,其理论研究尚处于初级阶段。时间复杂性分析可以估计算法的平均运行时间,是进化算法理论研究中的重要方向和有力工具。讨论了漂移分析和进化算法时间复杂性的关系,利用吸收马尔科夫链给出漂移定理的一个新的证明;用一步平均漂移估计算法计算时间,得到了线性函数进化算法时间复杂度的一个一般性的结果。这些结果有助于更好地理解进化算法的工作原理和性能。     

The evolutionary cost of Baldwin effect in the routing and spectrum allocation problem in elastic optical networks

Evolutionary Algorithms (EAs) are frequently used to solve various practical problems. It is common to adjust an EA to the solved problem by adding a different kind of problem-dependent mechanisms. One of the possible improvements is an evolutionary method hybridization with local search algorithms. Such hybridization may lead to phenomena called the Baldwin effect. It was shown that the occurrence of Baldwin effect helps to preserve population diversity and therefore may be beneficial for the method effectiveness. However, it also has its drawbacks. The use of local search causes the significant increase of computation load necessary for a single individual’s fitness computation. Therefore, the hybridization of an evolutionary method does not have to be beneficial. Moreover, the benefits (or drawbacks) of hybridization may be different depending on the method type and the features of the solved problem. Therefore, the main objective of this paper is to investigate the pros and cons of hybridization on the base of a hard practical and up-to-date problem, namely the Routing and Spectrum Allocation of Multicast Flows (RSA/M) in Elastic Optical Networks (EONs). The second objective of this paper is to propose an effective optimization method for solving the RSA/M problem in EONs.     

Time complexity analysis of an evolutionary algorithm for finding nearly maximum cardinality matching

Most of works on the time complexity analysis of evolutionary algorithms have always focused on some artificial binary problems. The time complexity of the algorithms for combinatorial optimisation has not been well understood. This paper considers the time complexity of an evolutionary algorithm for a classical combinatorial optimisation problem, to find the maximum cardinality matching in a graph. It is shown that the evolutionary algorithm can produce a matching with nearly maximum cardinality in average polynomial time.     

Solving Computation Slicing Using Predicate Detection

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest subcomputation (with the least number of consistent cuts) that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are actually equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time complexity of the (derived) slicing algorithm is O(n|E|T), where n is the number of processes, E is the set of events, and O(T) is the time complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the general predicate detection problem in many cases. Slicing algorithms described in our earlier papers are all offline in nature. In this paper, we also present two online algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time complexity is O(n(c + n)T) per event, where c is the average concurrency in the computation and O(T) is the time complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time complexity is only O(n²) per event.     

Self-adaptive population sizing for a tune-free differential evolution

The study and research of evolutionary algorithms (EAs) is getting great attention in recent years. Although EAs have earned extensive acceptance through numerous successful applications in many fields, the problem of finding the best combination of evolutionary parameters especially for population size that need the manual settings by the user is still unresolved. In this paper, our system is focusing on differential evolution (DE) and its control parameters. To overcome the problem, two new systems were carried out for the self-adaptive population size to test two different methodologies (absolute encoding and relative encoding) in DE and compared their performances against the original DE. Fifty runs are conducted for every 20 well-known benchmark problems to test on every proposed algorithm in this paper to achieve the function optimization without explicit parameter tuning in DE. The empirical testing results showed that DE with self-adaptive population size using relative encoding performed well in terms of the average performance as well as stability compared to absolute encoding version as well as the original DE.     

Solving an algebraic path problem and some related graph problemson a hyper-bus broadcast network

The parallel computation model upon which the proposed algorithms are based is the hyper-bus broadcast network. The hyper-bus broadcast network consists of processors which are connected by global buses only. Based on such an improved architecture, we first design two O(1) time basic operations for finding the maximum and minimum of N numbers each of size O(log N)-bit and computing the matrix multiplication operation of two N×N matrices, respectively. Then, based on these two basic operations, three of the most important instances in the algebraic path problem, the connectivity problem, and several related problems are all solved in O(log N) time. These include the all-pair shortest paths, the minimum-weight spanning tree, the transitive closure, the connected component, the biconnected component, the articulation point, and the bridge problems, either in an undirected or a directed graph, respectively     

Computing all minimal hitting sets by subset recombination

In model-based diagnosis from first principles, the efficient computation of all minimal hitting sets (MHS) as candidates for the conflict component sets of a device is a vital task. However, deriving all MHS is NP-hard. In this paper, the principle of “Divide and Conquer” is used to decompose a large family of conflict sets into many smaller sub-families. To efficiently merge the sub-MHS to give sub-families of conflict sets, the relations between the sub-MHS and sub-families of conflict sets are exploited. Based on this, a new method called Subset-Rec-MHS is proposed. In theory, our method based on sub-MHS recombination generally has lower complexity than that based on whole MHS families, as it avoids a large number of set unions and comparisons (to minimize the family of hitting sets). Compared with the direct merge of whole MHS families, the proposed approach reduces the computation time by a factor of approximately \(\frac {7}{16}\). Experimental results on both synthetic examples and ISCAS-85 benchmark circuit conflict sets show that, in many cases, our approach offers better performance than previous algorithms.     

Evolutionary algorithms - how to cope with plateaus of constantfitness and when to reject strings of the same fitness

The most simple evolutionary algorithm (EA), the so-called (1 + 1) EA, accepts an offspring if its fitness is at least as large (in the case of maximization) as the fitness of its parent. The variant (1 + 1)* EA only accepts an offspring if its fitness is strictly larger than the fitness of its parent. Here, two functions related to the class of long-path functions are presented such that the (1 + 1) EA maximizes one in polynomial time and needs exponential time for the other while the (1 + 1)* EA has the opposite behavior. These results demonstrate that small changes of an EA may change its behavior significantly. Since the (1 + 1) EA and the (1 + 1)* EA differ only on plateaus of constant fitness, the results also show how EAs behave on such plateaus. The (1 + 1) EA can pass a path of constant fitness and polynomial length in polynomial time. Finally, for these functions, it is shown that local performance measures like the quality gain and the progress rate do not describe the global behavior of EAs