Memetic Algorithms: The Polynomial Local Search Complexity Theory Perspective

In previous work (Krasnogor, . In: Studies on the Theory and Design Space of Memetic Algorithms. Ph.D. thesis, University of the West of England, Bristol, UK, 2002; Krasnogor and Smith, IEEE Trans Evol Algorithms 9(6):474–488, 2005) we develop a syntax-only classification of evolutionary algorithms, in particular so-called memetic algorithms (MAs). When “syntactic sugar” is added to our model, we are able to investigate the polynomial local search (PLS) complexity of memetic algorithms. In this paper we show the PLS-completeness of whole classes of problems that occur when memetic algorithms are applied to the travelling salesman problem using a range of mutation, crossover and local search operators. Our PLS-completeness results shed light on the worst case behaviour that can be expected of a memetic algorithm under these circumstances. Moreover, we point out in this paper that memetic algorithms for graph partitioning and maximum network flow (both with important practical applications) also give rise to PLS-complete problems.

---

Electronic Supplementary Material The online version of this article (doi:) contains supplementary material, which is available to authorized users.      

Computational experiments with a lazy version of a <Emphasis Type="Italic">K</Emphasis> quickest simple path ranking algorithm

The quickest path problem is related to the classical shortest path problem, but its objective function concerns the transmission time of a given amount of data throughout a path, which involves both cost and capacity. The K-quickest simple paths problem generalises the latter, by looking for a given number K of simple paths in non-decreasing order of transmission time. Two categories of algorithms are known for ranking simple paths according to the transmission time. One is the adaptation of deviation algorithms for ranking shortest simple paths (Pascoal et al. in Comput. Oper. Res. 32(3):509–520, 2005; Rosen et al. in Comput. Oper. Res. 18(6):571–584, 1991), and another is based on ranking shortest simple paths in a sequence of networks with fixed capacity lower bounds (Chen in Inf. Process. Lett. 50:89–92, 1994), and afterwards selecting the K quickest ones. After reviewing the quickest path and the K-quickest simple paths problems we describe a recent algorithm for ranking quickest simple paths (Pascoal et al. in Ann. Oper. Res. 147(1):5–21, 2006). This is a lazy version of Chen’s algorithm, able to interchange the calculation of new simple paths and the output of each k-quickest simple path. Finally, the described algorithm is computationally compared to its former version, as well as to deviation algorithms.      

Perturbation bounds for Monte Carlo within Metropolis via restricted approximations

The Monte Carlo within Metropolis (MCwM) algorithm, interpreted as a perturbed Metropolis–Hastings (MH) algorithm, provides an approach for approximate sampling when the target distribution is intractable. Assuming the unperturbed Markov chain is geometrically ergodic, we show explicit estimates of the difference between the $n$th step distributions of the perturbed MCwM and the unperturbed MH chains. These bounds are based on novel perturbation results for Markov chains which are of interest beyond the MCwM setting. To apply the bounds, we need to control the difference between the transition probabilities of the two chains and to verify stability of the perturbed chain.     

Improved Noniterative Algorithm for Solving the Traffic Equilibrium Problem

We provide an equivalent formulation of a previously proposed noniterative algorithm (see A. Maugeri, Appl. Math. Optim. 16, 169–185, 1987) for the traffic equilibrium problem. Moreover, under the strict monotonicity assumption, we provide an improved algorithm which enlarges the range of applicability of the previous algorithm and decreases considerably its computational effort. Our algorithm is based on a general algorithm for variational inequalities (see O. Mancino, G. Stampacchia, J. Optim. Theory Appl. 9, 3–23, 1972), which we further develop and adapt to the traffic equilibrium problem. Both our proofs and the algorithm exploit directly the equilibrium conditions which characterize our problem.     

Adaptive Isotopic Approximation of Nonsingular Curves: the Parameterizability and Nonlocal Isotopy Approach

We consider domain subdivision algorithms for computing isotopic approximations of a nonsingular algebraic curve. The curve is given by a polynomial equation f(X,Y)=0. Two algorithms in this area are from Snyder (1992) SIGGRAPH Comput. Graphics, 26(2), 121 and Plantinga and Vegter (2004) In Proc. Eurographics Symposium on Geometry Processing, pp. 245–254. We introduce a new algorithm that combines the advantages of these two algorithms: like Snyder, we use the parameterizability criterion for subdivision, and like Plantinga and Vegter, we exploit nonlocal isotopy. We further extend our algorithm in two important and practical directions: first, we allow subdivision cells to be rectangles with arbitrary but bounded aspect ratios. Second, we extend the input domains to be regions R ₀ with arbitrary geometry and which might not be simply connected. Our algorithm halts as long as the curve has no singularities in the region, and intersects the boundary of R ₀ transversally. Our algorithm is practical and easy to implement exactly. We report some very encouraging experimental results, showing that our algorithms can be much more efficient than the algorithms of Plantinga–Vegter and Snyder.     

Packing r-Cliques in Weighted Chordal Graphs

In 1, we have previously observed that, in a chordal graph G, the maximum number of independent r-cliques (i.e., of vertex disjoint subgraphs of G, each isomorphic to K_r, with no edges joining any two of the subgraphs) equals the minimum number of cliques of G that meet all the r-cliques of G. When r = 1, this says that chordal graphs have independence number equal to the clique covering number. When r = 2, this is equivalent to a result of Cameron (1989), and it implies a well known forbidden subgraph characterization of split graphs. In this paper we consider a weighted version of the above min-max optimization problem. Given a chordal graph G, with a nonnegative weight for each r-clique in G, we seek a set of independent r-cliques with maximum total weight. We present two algorithms to solve this problem, based on the principle of complementary slackness. The first one operates on a graph derived from G, and is an adaptation of an algorithm of Farber (1982). The second one improves the performance by reducing the number of constraints of the linear programs. Both results produce a min-max relation. When the algorithms are specialized to the situation in which all the r-cliques have the same weight, we simplify the algorithms reported in 1, although these simpler algorithms are not as efficient. As a byproduct, we also obtain new elementary proofs of the above min-max result.     

Adaptive,Delayed-Acceptance MCMC for Targets With Expensive Likelihoods

When conducting Bayesian inference, delayed-acceptance (DA) Metropolis–Hastings (MH) algorithms and DA pseudo-marginal MH algorithms can be applied when it is computationally expensive to calculate the true posterior or an unbiased estimate thereof, but a computationally cheap approximation is available. A first accept-reject stage is applied, with the cheap approximation substituted for the true posterior in the MH acceptance ratio. Only for those proposals that pass through the first stage is the computationally expensive true posterior (or unbiased estimate thereof) evaluated, with a second accept-reject stage ensuring that detailed balance is satisfied with respect to the intended true posterior. In some scenarios, there is no obvious computationally cheap approximation. A weighted average of previous evaluations of the computationally expensive posterior provides a generic approximation to the posterior. If only the k-nearest neighbors have nonzero weights then evaluation of the approximate posterior can be made computationally cheap provided that the points at which the posterior has been evaluated are stored in a multi-dimensional binary tree, known as a KD-tree. The contents of the KD-tree are potentially updated after every computationally intensive evaluation. The resulting adaptive, delayed-acceptance [pseudo-marginal] Metropolis–Hastings algorithm is justified both theoretically and empirically. Guidance on tuning parameters is provided and the methodology is applied to a discretely observed Markov jump process characterizing predator–prey interactions and an ODE system describing the dynamics of an autoregulatory gene network. Supplementary material for this article is available online.     

A numerical algorithm for singular optimal LQ control systems

A numerical algorithm to obtain the consistent conditions satisfied by singular arcs for singular linear–quadratic optimal control problems is presented. The algorithm is based on the Presymplectic Constraint Algorithm (PCA) by Gotay-Nester (Gotay et al., J Math Phys 19:2388–2399, 1978; Volckaert and Aeyels 1999) that allows to solve presymplectic Hamiltonian systems and that provides a geometrical framework to the Dirac-Bergmann theory of constraints for singular Lagrangian systems (Dirac, Can J Math 2:129–148, 1950). The numerical implementation of the algorithm is based on the singular value decomposition that, on each step, allows to construct a semi-explicit system. Several examples and experiments are discussed, among them a family of arbitrary large singular LQ systems with index 2 and a family of examples of arbitrary large index, all of them exhibiting stable behaviour. Research partially supported by MEC grant MTM2004-07090-C03-03. SIMUMAT-CM, UC3M-MTM-05-028 and CCG06-UC3M/ESP-0850.     

An Inexact Proximal-Type Algorithm in Banach Spaces

In this paper, we investigate the strong convergence of an inexact proximal-point algorithm. It is known that the proximal-point algorithm converges weakly to a solution of a maximal monotone operator, but fails to converge strongly. Solodov and Svaiter (Math. Program. 87:189–202, 2000) introduced a new proximal-type algorithm to generate a strongly convergent sequence and established a convergence result in Hilbert space. Subsequently, Kamimura and Takahashi (SIAM J. Optim. 13:938–945, 2003) extended the Solodov and Svaiter result to the setting of uniformly convex and uniformly smooth Banach space. On the other hand, Rockafellar (SIAM J. Control Optim. 14:877–898, 1976) gave an inexact proximal-point algorithm which is more practical than the exact one. Our purpose is to extend the Kamimura and Takahashi result to a new inexact proximal-type algorithm. Moreover, this result is applied to the problem of finding the minimizer of a convex function on a uniformly convex and uniformly smooth Banach space. L.C. Zeng’s research was partially supported by the Teaching and Research Award Fund for Outstanding Young Teachers in Higher Education Institutions of MOE, China and by the Dawn Program Foundation in Shanghai. J.C. Yao’s research was partially supported by the National Science Council of the Republic of China.     

Structured Markov Chain Monte Carlo

Abstract

This article introduces a general method for Bayesian computing in richly parameterized models, structured Markov chain Monte Carlo (SMCMC), that is based on a blocked hybrid of the Gibbs sampling and Metropolis—Hastings algorithms. SMCMC speeds algorithm convergence by using the structure that is present in the problem to suggest an appropriate Metropolis—Hastings candidate distribution. Although the approach is easiest to describe for hierarchical normal linear models, we show that its extension to both nonnormal and nonlinear cases is straightforward. After describing the method in detail we compare its performance (in terms of run time and autocorrelation in the samples) to other existing methods, including the single-site updating Gibbs sampler available in the popular BUGS software package. Our results suggest significant improvements in convergence for many problems using SMCMC, as well as broad applicability of the method, including previously intractable hierarchical nonlinear model settings.     

On the Convergence of the Pshenichnyi-Pironneau-Polak Minimax Algorithm with an Active Set Strategy

The purpose of this technical note is to present a proof of convergence of the Pshenichnyi-Pironneau-Polak (PPP) minimax algorithm (see Algorithm 2.4.1 in Polak, Optimization: Algorithms and Consistent Approximations, Springer, [1997]), modified to use an active set strategy. This active set strategy was formally derived in Polak (Optimization: Algorithms and Consistent Approximations, Springer, [1997]) from those used in the methods of feasible directions developed by Zoutendijk (Methods of Feasible Directions, Elsevier, [1960]) and Polak (Computational Methods in Optimization: A Unified Approach, Academic, [1971]). The resulting ε-Active PPP algorithm was presented as Algorithm 2.4.34, in Polak (Optimization: Algorithms and Consistent Approximations, Springer, [1997]), without any proofs.     

Speeding up MCMC by Delayed Acceptance and Data Subsampling

The complexity of the Metropolis–Hastings (MH) algorithm arises from the requirement of a likelihood evaluation for the full dataset in each iteration. One solution has been proposed to speed up the algorithm by a delayed acceptance approach where the acceptance decision proceeds in two stages. In the first stage, an estimate of the likelihood based on a random subsample determines if it is likely that the draw will be accepted and, if so, the second stage uses the full data likelihood to decide upon final acceptance. Evaluating the full data likelihood is thus avoided for draws that are unlikely to be accepted. We propose a more precise likelihood estimator that incorporates auxiliary information about the full data likelihood while only operating on a sparse set of the data. We prove that the resulting delayed acceptance MH is more efficient. The caveat of this approach is that the full dataset needs to be evaluated in the second stage. We therefore propose to substitute this evaluation by an estimate and construct a state-dependent approximation thereof to use in the first stage. This results in an algorithm that (i) can use a smaller subsample m by leveraging on recent advances in Pseudo-Marginal MH (PMMH) and (ii) is provably within O(m^{? 2}) of the true posterior.     

Modified Proximal-Point Algorithm for Maximal Monotone Operators in Banach Spaces

We introduce an iterative sequence for finding the solution to 0∈T(v), where T : E⇉E ^* is a maximal monotone operator in a smooth and uniformly convex Banach space E. This iterative procedure is a combination of iterative algorithms proposed by Kohsaka and Takahashi (Abstr. Appl. Anal. 3:239–249, 2004) and Kamamura, Kohsaka and Takahashi (Set-Valued Anal. 12:417–429, 2004). We prove a strong convergence theorem and a weak convergence theorem under different conditions respectively and give an estimate of the convergence rate of the algorithm. An application to minimization problems is given. This work was partially supported by the National Natural Sciences Grant 10671050 and the Heilongjiang Province Natural Sciences Grant A200607. The authors thank the referees for useful comments improving the presentation and Professor K. Kohsaka for pointing out Ref. 7.     

Approximating Huffman codes in parallel

In this paper we present new results on the approximate parallel construction of Huffman codes. Our algorithm achieves linear work and logarithmic time, provided that the initial set of elements is sorted. This is the first parallel algorithm for that problem with the optimal time and work. Combining our approach with the best known parallel sorting algorithms we can construct an almost optimal Huffman tree with optimal time and work. This also leads to the first parallel algorithm that constructs exact Huffman codes with maximum codeword length H in time O(H) with n/logn processors, if the elements are sorted.     

Interpolation algorithm of Leverrier–Faddev type for polynomial matrices

We investigated an interpolation algorithm for computing outer inverses of a given polynomial matrix, based on the Leverrier–Faddeev method. This algorithm is a continuation of the finite algorithm for computing generalized inverses of a given polynomial matrix, introduced in [11]. Also, a method for estimating the degrees of polynomial matrices arising from the Leverrier–Faddeev algorithm is given as the improvement of the interpolation algorithm. Based on similar idea, we introduced methods for computing rank and index of polynomial matrix. All algorithms are implemented in the symbolic programming language MATHEMATICA , and tested on several different classes of test examples.     

Jacobi spectral Galerkin method for elliptic Neumann problems

This paper is concerned with fast spectral-Galerkin Jacobi algorithms for solving one- and two-dimensional elliptic equations with homogeneous and nonhomogeneous Neumann boundary conditions. The paper extends the algorithms proposed by Shen (SIAM J Sci Comput 15:1489–1505, 1994) and Auteri et al. (J Comput Phys 185:427–444, 2003), based on Legendre polynomials, to Jacobi polynomials with arbitrary α and β. The key to the efficiency of our algorithms is to construct appropriate basis functions with zero slope at the endpoints, which lead to systems with sparse matrices for the discrete variational formulations. The direct solution algorithm developed for the homogeneous Neumann problem in two-dimensions relies upon a tensor product process. Nonhomogeneous Neumann data are accounted for by means of a lifting. Numerical results indicating the high accuracy and effectiveness of these algorithms are presented.     

On the local convergence of a derivative-free algorithm for least-squares minimization

In Zhang et al. (accepted by SIAM J. Optim., 2010), we developed a class of derivative-free algorithms, called DFLS, for least-squares minimization. Global convergence of the algorithm as well as its excellent numerical performance within a limited computational budget was established and discussed in the same paper. Here we would like to establish the local quadratic convergence of the algorithm for zero residual problems. Asymptotic convergence performance of the algorithm for both zero and nonzero problems is tested. Our numerical experiments indicate that the algorithm is also very promising for achieving high accuracy solutions compared with software packages that do not exploit the special structure of the least-squares problem or that use finite differences to approximate the gradients.     

A hybrid method for quantum global optimization

This paper gives a quantum algorithm for global optimization. The heart of such approaches employ Grover’s database search (1996; Phys Rev Lett 79(23):4709–4712, 1997a; 79(2):325–328, 1997b). Chi and Kim (1998) show that when the phases of the generalized Grover database search operator are optimally chosen, it is capable of finding a solution by a single query. To apply this method to global optimization requires knowledge of the number of marked points m to calculate the optimal phases, but this value is seldom known. This paper focuses on overcoming this hurdle by showing that an estimate of the optimal phases can be found and used to replace the optimal phases while maintaining a high probability of finding a solution. Merging this finding with a recently discovered dynamic quantum global optimization algorithm (BBW2D) that reduces the problem to finding successively improving regions using Grover’s search, we present a hybrid method that improves the efficiency and reduces the variance of the search algorithm when empirically compared to other existing quantum search algorithms.     

Newton-KKT interior-point methods for indefinite quadratic programming

Two interior-point algorithms are proposed and analyzed, for the (local) solution of (possibly) indefinite quadratic programming problems. They are of the Newton-KKT variety in that (much like in the case of primal-dual algorithms for linear programming) search directions for the “primal” variables and the Karush-Kuhn-Tucker (KKT) multiplier estimates are components of the Newton (or quasi-Newton) direction for the solution of the equalities in the first-order KKT conditions of optimality or a perturbed version of these conditions. Our algorithms are adapted from previously proposed algorithms for convex quadratic programming and general nonlinear programming. First, inspired by recent work by P. Tseng based on a “primal” affine-scaling algorithm (à la Dikin) [J. of Global Optimization, 30 (2004), no. 2, 285–300], we consider a simple Newton-KKT affine-scaling algorithm. Then, a “barrier” version of the same algorithm is considered, which reduces to the affine-scaling version when the barrier parameter is set to zero at every iteration, rather than to the prescribed value. Global and local quadratic convergence are proved under nondegeneracy assumptions for both algorithms. Numerical results on randomly generated problems suggest that the proposed algorithms may be of great practical interest. The work of the first author was supported in part by the School of Computational Science of Florida State University through a postdoctoral fellowship. Part of this work was done while this author was a Research Fellow with the Belgian National Fund for Scientific Research (Aspirant du F.N.R.S.) at the University of Liège. The work of the second author was supported in part by the National Science Foundation under Grants DMI9813057 and DMI-0422931 and by the US Department of Energy under Grant DEFG0204ER25655. Any opinions, findings, and conclusions or recommendations expressed in this paper are those of the authors and do not necessarily reflect the views of the National Science Foundation or those of the US Department of Energy.     

On the parallel computation of the biconnected and strongly connected co-components of graphs

In this paper, we consider the problems of co-biconnectivity and strong co-connectivity, i.e., computing the biconnected components and the strongly connected components of the complement of a given graph. We describe simple sequential algorithms for these problems, which work on the input graph and not on its complement, and which for a graph on n vertices and m edges both run in optimal O(n+m) time. Our algorithms are not data structure-based and they employ neither breadth-first-search nor depth-first-search.Unlike previous linear co-biconnectivity and strong co-connectivity sequential algorithms, both algorithms admit efficient parallelization. The co-biconnectivity algorithm can be parallelized resulting in an optimal parallel algorithm that runs in time using processors. The strong co-connectivity algorithm can also be parallelized to yield an -time and O(m^1.188/logn)-processor solution. As a byproduct, we obtain a simple optimal O(logn)-time parallel co-connectivity algorithm.Our results show that, in a parallel process environment, the problems of computing the biconnected components and the strongly connected components can be solved with better time-processor complexity on the complement of a graph rather than on the graph itself.