On the analysis of a simple evolutionary algorithm on quadratic pseudo-boolean functions

Evolutionary algorithms are randomized search heuristics, which are often used as function optimizers. In this paper the well-known (1+1) Evolutionary Algorithm ((1+1) EA) and its multistart variants are studied. Several results on the expected runtime of the (1+1) EA on linear or unimodal functions have already been presented by other authors. This paper is focused on quadratic pseudo-boolean functions, i.e., polynomials of degree 2, a class of functions containing NP-hard optimization problems. Subclasses of the class of all quadratic functions are identified where the (1+1) EA is efficient, for other subclasses the (1+1) EA has exponential expected runtime, but a large enough success probability within polynomial time such that a multistart variant of the (1+1) EA is efficient. Finally, a particular quadratic function is identified where the EA and its multistart variants fail in polynomial time with overwhelming probability.     

The analysis of evolutionary algorithms on sorting and shortest paths problems

The analysis of evolutionary algorithms is up to now limited to special classes of functions and fitness landscapes. E.g., it is not possible to characterize the set of TSP instances (or another NP-hard combinatorial optimization problem) which are solved by a generic evolutionary algorithm (EA) in an expected time bounded by some given polynomial. As a first step from artificial functions to typical problems from combinatorial optimization, we analyze simple EAs on well-known problems, namely sorting and shortest paths. Although it cannot be expected that EAs outperform the well-known problem specific algorithms on these simple problems, it is interesting to analyze how EAs work on these problems. The following results are obtained:– Sorting is the maximization of sortedness which is measured by one of several well-known measures of presortedness. The different measures of presortedness lead to fitness functions of quite different difficulty for EAs.– Shortest paths problems are hard for all types of EA, if they are considered as single-objective optimization problems, whereas they are easy as multi-objective optimization problems.     

A path-oriented encoding evolutionary algorithm for network coding resource minimization

Network coding is an emerging telecommunication technique, where any intermediate node is allowed to recombine incoming data if necessary. This technique helps to increase the throughput, however, very likely at the cost of huge amount of computational overhead, due to the packet recombination performed (ie coding operations). Hence, it is of practical importance to reduce coding operations while retaining the benefits that network coding brings to us. In this paper, we propose a novel evolutionary algorithm (EA) to minimize the amount of coding operations involved. Different from the state-of-the-art EAs which all use binary encodings for the problem, our EA is based on path-oriented encoding. In this new encoding scheme, each chromosome is represented by a union of paths originating from the source and terminating at one of the receivers. Employing path-oriented encoding leads to a search space where all solutions are feasible, which fundamentally facilitates more efficient search of EAs. Based on the new encoding, we develop three basic operators, that is, initialization, crossover and mutation. In addition, we design a local search operator to improve the solution quality and hence the performance of our EA. The simulation results demonstrate that our EA significantly outperforms the state-of-the-art algorithms in terms of global exploration and computational time.     

An evolutionary algorithm with the partial sequential forward floating search mutation for large-scale feature selection problems

Several meta-heuristic algorithms, such as evolutionary algorithms (EAs) and genetic algorithms (GAs), have been developed for solving feature selection problems due to their efficiency for searching feature subset spaces in feature selection problems. Recently, hybrid GAs have been proposed to improve the performance of conventional GAs by embedding a local search operation, or sequential forward floating search mutation, into the GA. Existing hybrid algorithms may damage individuals’ genetic information obtained from genetic operations during the local improvement procedure because of a sequential process of the mutation operation and the local improvement operation. Another issue with a local search operation used in the existing hybrid algorithms is its inappropriateness for large-scale problems. Therefore, we propose a novel approach for solving large-sized feature selection problems, namely, an EA with a partial sequential forward floating search mutation (EAwPS). The proposed approach integrates a local search technique, that is, the partial sequential forward floating search mutation into an EA method. Two algorithms, EAwPS-binary representation (EAwPS-BR) for medium-sized problems and EAwPS-integer representation (EAwPS-IR) for large-sized problems, have been developed. The adaptation of a local improvement method into the EA speeds up the search and directs the search into promising solution areas. We compare the performance of the proposed algorithms with other popular meta-heuristic algorithms using the medium- and large-sized data sets. Experimental results demonstrate that the proposed EAwPS extracts better features within reasonable computational times.     

Empirical analysis of evolutionary algorithms with immigrants schemes for dynamic optimization

In recent years, there has been a growing interest in studying evolutionary algorithms (EAs) for dynamic optimization problems (DOPs). Among approaches developed for EAs to deal with DOPs, immigrants schemes have been proven to be beneficial. Immigrants schemes for EAs on DOPs aim at maintaining the diversity of the population throughout the run via introducing new individuals into the current population. In this paper, we carefully examine the mechanism of generating immigrants, which is the most important issue among immigrants schemes for EAs in dynamic environments. We divide existing immigrants schemes into two types, namely the direct immigrants scheme and the indirect immigrants scheme, according to the way in which immigrants are generated. Then experiments are conducted to understand the difference in the behaviors of different types of immigrants schemes and to compare their performance in dynamic environments. Furthermore, a new immigrants scheme is proposed to combine the merits of two types of immigrants schemes. The experimental results show that the interactions between the two types of schemes reveal positive effect in improving the performance of EAs in dynamic environments.     

Applying self-adaptive evolutionary algorithms to two-dimensional packing problems using a four corners’ heuristic

This paper proposes a four corners’ heuristic for application in evolutionary algorithms (EAs) applied to two-dimensional packing problems. The four corners’ (FC) heuristic is specifically designed to increase the search efficiency of EAs. Experiments with the FC heuristic are conducted on 31 problems from the literature both with rotations permitted and without rotations permitted, using two different EA algorithms: a self-adaptive parallel recombinative simulated annealing (PRSA) algorithm, and a self-adaptive genetic algorithm (GA). Results on bin packing problems yield the smallest trim losses we have seen in the published literature; with the FC heuristic, zero trim loss was achieved on problems of up to 97 rectangles. A comparison of the self-adaptive GA to fixed-parameter GAs is presented and the benefits of self-adaption are highlighted.     

A general cost-benefit-based adaptation framework for multimeme algorithms

As memetic algorithms (MA) are a crossbreed between local searchers and evolutionary algorithms (EA) spreading of computational resources between evolutionary and local search is a key issue for a good performance, if not for success at all. This paper summarises and continues previous work on a general cost-benefit-based adaptation scheme for the choice of local searchers (memes), the frequency of their usage, and their search depth. This scheme eliminates the MA strategy parameters controlling meme usage, but raises new ones for steering the adaptation itself. Their impact is analysed and it will be shown that in the end the number of strategy parameters is decreased significantly as well as their range of meaningful values. In addition to this the number of fitness evaluations is reduced drastically. Both are necessary prerequisites for many practical applications as well as for the acceptance of the method by practitioners. Although the introduced framework is tailored to EAs producing more than one offspring per mating, it is also suited for those with only one child per pairing. So there are no preconditions to the EA for the described adaptation scheme to be applied.     

The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSAT problems

Heuristic algorithms, especially hill-climbing algorithms, are prone to being trapped by local optimization. Many researchers have focused on analyzing convergence and runtime of some heuristic algorithms on SAT-solving problems. However, there is rare work on analyzing success ratio (the ratio of the number of runs that find the global maxima of optimization versus the total runs) and expected fitness at each generation. Expected fitness at each generation could lead us to better understand the expected fitness of a heuristic algorithm could find on the problem to be solve at a certain generation. Success ratio help us understand with what a probability a heuristic algorithm could find the global optimization of the problem to be solved. So, this paper analyzed expected fitness and success ratio of two hill-climbing algorithms on two bimodal MaxSAT problems by using Markov chain. The theoretical and experimental results showed that though hill-climbing algorithms (both hill-climbing RandomWalk and Local (1+1)EA) converged faster, they could not always find global maxima of bimodal SAT-solving problems. The success ratios of hill-climbing algorithms usually have their own limits. The limit of success ratio is dependent on the SAT-solving problem itself and the expected distribution of initial bit string, and independent on whether hill-climbing RandomWalk or Local (1+1)EA is used.     

基于非均匀变异的进化算法对高维多峰函数的收敛性分析

对基于非均匀变异算子的进化算法的实验和机理分析已经证明了该算法模型的良好特性,最近基于非均匀变异算子的进化算法模型求解一维多峰函数问题的收敛性已经得到证明.基于马尔科夫过程理论,对基于非均匀变异算子的一般性进化算法模型和一般性高维多峰函数的收敛性给出证明,并基于典型算例与同类典型算法进行性能比较,数值试验表明算法模型具有很好的性能表现和应用前景.     

Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem

Evolutionary algorithms are applied to problems that are not well understood as well as to problems in combinatorial optimization. The analysis of these search heuristics has been started for some well-known polynomial solvable problems. Such analyses are starting points for the analysis of evolutionary algorithms on difficult problems. We present the first runtime analysis of a multi-objective evolutionary algorithm on a NP-hard problem. The subject of our analysis is the multi-objective minimum spanning tree problem for which we give upper bounds on the expected time until a simple evolutionary algorithm has produced a population including for each extremal point of the Pareto front a corresponding spanning tree. These points are of particular interest as they give a 2-approximation of the Pareto front. We show that in expected pseudopolynomial time a population is produced that includes for each extremal point a corresponding spanning tree.     

Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem

We look at the instance distributions used by Goldberg [3] for showing that the Davis Putnam Procedure has polynomial average complexity and show that, in a sense, all these distributions are unreasonable. We then present a ‘reasonable’ family of instance distributions F and show that for each distribution in F a variant of the Davis Putnam Procedure without the pure literal rule requires exponential time with probability 1. In addition, we show that adding subsumption still results in exponential complexity with probability 1.     

Bird mating optimizer: An optimization algorithm inspired by bird mating strategies

Thanks to their simplicity and flexibility, evolutionary algorithms (EAs) have attracted significant attention to tackle complex optimization problems. The underlying idea behind all EAs is the same and they differ only in technical details. In this paper, we propose a novel version of EAs, bird mating optimizer (BMO), for continuous optimization problems which is inspired by mating strategies of bird species during mating season. BMO imitates the behavior of bird species metaphorically to breed broods with superior genes for designing optimum searching techniques. On a large set of unimodal and multimodal benchmark functions, BMO represents a competitive performance to other EAs.     

Performance evaluation of evolutionary class of algorithms—An application to 0–1 knapsack problem

The 0–1 knapsack [1] problem is a well-known NP-complete problem. There are different algorithms in the literature to attack this problem, two of them being of specific interest. One is a pseudo polynomial algorithm of order O(nK), K being the target of the problem. This algorithm works unsatisfactorily, as the given target becomes high. In fact, the complexity might become exponential in that case. The other scheme is a fully polynomial time approximation scheme (FPTAS) whose complexity is also polynomial time. The present paper suggests a probabilistic heuristic which is an evolutionary scheme accompanied by the necessary statistical formulation and its theoretical justification. We have identified parameters responsible for the performance of our evolutionary scheme which in turn would keep the option open for improving the scheme.     

Greedy Dynamic Routing on Arrays

We study the problem of dynamic routing on arrays. We prove that a large class of greedy algorithms perform very well on average. In the dynamic case, when the arrival rate of packets in anN × Narray is at most 99% of network capacity, we establish an exponential bound on the tail of the delay distribution. Moreover, we show that in any window ofTsteps, the maximum queue-size isO(1 + log T/log N) with high probability. We extend these results to the case of bit-serial routing, and to the static case. We also calculate the exact value of the ergodic expected delay and queue-sizes under the farthest first protocol for the one-dimensional array, and for the ring when the arrivals are Poisson.     

On the utility of randomly generated functions for performance evaluation of evolutionary algorithms

Previous researches have disclosed that the excellent performance of some evolutionary algorithms (EAs) highly depends on existence of some properties in the structure of the objective function. Unlike classical benchmark functions, randomly generated multimodal functions do not have any of these properties. Having been improved, a function generator is utilized to generate a number of six benchmarks with random structure. Performance of some EAs is evaluated on these functions and compared to that evaluated on results from classical benchmarks, which are available in literature. The comparison reveals a considerable drop in the performance, even though some of these methods have all possible invariances. This demonstrates that in addition to properties, classical benchmarks have special patterns which may be exploited by EAs. Unlike properties, these patterns are not eliminated under linear transformation of the coordinates or the objective function; hence, limitations should be considered while generalizing performance of EAs on classical benchmarks to practical problems, where these properties or patterns do not necessarily exist.     

CONVERGENCE RATES FOR A CLASS OF EVOLUTIONARY ALGORITHMS WITH ELITIST STRATEGY

1 IntroductionOne of tlle fundamental issues about the theory of evolutionary algorithIns is their conver-gence. At present, the theoretical basis about evolutionary computation is still yery wcak['--'],especial1y for the researches into the convergeIlce rates of evolutionary a1gorithm8. Accord-illg to the literature, tllere are few results about the convergence rates[4--9], but this research..area i8 very importallt in both theory and practice. Xu and Li[l0] pointed out that the studyof the…     

Cover time and mixing time of random walks on dynamic graphs

The application of simple random walks on graphs is a powerful tool that is useful in many algorithmic settings such as network exploration, sampling, information spreading, and distributed computing. This is due to the reliance of a simple random walk on only local data, its negligible memory requirements, and its distributed nature. It is well known that for static graphs the cover time, that is, the expected time to visit every node of the graph, and the mixing time, that is, the time to sample a node according to the stationary distribution, are at most polynomial relative to the size of the graph. Motivated by real world networks, such as peer‐to‐peer and wireless networks, the conference version of this paper was the first to study random walks on arbitrary dynamic networks. We study the most general model in which an oblivious adversary is permitted to change the graph after every step of the random walk. In contrast to static graphs, and somewhat counter‐intuitively, we show that there are adversary strategies that force the expected cover time and the mixing time of the simple random walk on dynamic graphs to be exponentially long, even when at each time step the network is well connected and rapidly mixing. To resolve this, we propose a simple strategy, the lazy random walk, which guarantees, under minor conditions, polynomial cover time and polynomial mixing time regardless of the changes made by the adversary.     

A chaos-based evolutionary algorithm for general nonlinear programming problems

In this paper we present a chaos-based evolutionary algorithm (EA) for solving nonlinear programming problems named chaotic genetic algorithm (CGA). CGA integrates genetic algorithm (GA) and chaotic local search (CLS) strategy to accelerate the optimum seeking operation and to speed the convergence to the global solution. The integration of global search represented in genetic algorithm and CLS procedures should offer the advantages of both optimization methods while offsetting their disadvantages. By this way, it is intended to enhance the global convergence and to prevent to stick on a local solution. The inherent characteristics of chaos can enhance optimization algorithms by enabling it to escape from local solutions and increase the convergence to reach to the global solution. Twelve chaotic maps have been analyzed in the proposed approach. The simulation results using the set of CEC’2005 show that the application of chaotic mapping may be an effective strategy to improve the performances of EAs.     

Semidefinite programming for min–max problems and games

We consider two min–max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796–817, 2001; Math Program B 112:65–92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min–max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization.     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000