Parameterized Computation and Complexity： A New Approach Dealing with NP-Hardness

The theory of parameterized computation and complexity is a recently developed subarea in theoretical computer science. The theory is aimed at practically solving a large number of computational problems that are theoretically intractable.The theory is based on the observation that many intractable computational problems in practice are associated with a parameter that varies within a small or moderate range. Therefore, by taking the advantages of the small parameters, many theoretically intractable problems can be solved effectively and practically. On the other hand, the theory of parameterized computation and complexity has also offered powerful techniques that enable us to derive strong computational lower bounds for many computational problems, thus explaining why certain theoretically tractable problems cannot be solved effectively and practically. The theory of parameterized computation and complexity has found wide applications in areas such as database systems, programming languages, networks, VLSI design, parallel and distributed computing, computational biology, and robotics. This survey gives an overview on the fundamentals, algorithms, techniques, and applications developed in the research of parameterized computation and complexity. We will also report the most recent advances and excitements, and discuss further research directions in the area.     

On Unknown Small Subsets and Implicit Measures: New Techniques for Parameterized Algorithms

Parameterized computation is a recently proposed alternative approach to dealing with NP-hard problems.Developing efficient parameterized algorithms has become a very active research area in the current research in theoretical computer science. In this paper, we investigate a number of new algorithmic techniques that were proposed and initiated by ourselves in our research in parameterized computation. The techniques have proved to be very useful and promising,and have led to improved parameterized algorithms for many well-known NP-hard problems.     

A new dynamical evolutionary algorithm based on statistical mechanics

In this paper,a new dynamical evolutionary algorithm(DEA) is presented based on the theory of statistical mechanics.The novelty of this kind of dynamical evolutionary algorithm is that all individuals in a population(called particles in a dynamical system)are running and searching with their population evolving driven by a new selecting mechanism.This mechanism simulates the principle of molecular dynamics,which is easy to design and implement.A basic theoretical analysis for the dynamical evolutionary algorithm is given and as a consequence two stopping criteria of the algorithm are derived from the principle of energy minimization and the law of entropy increasing.In order to verify the effectiveness of the scheme,DEA is applied to sloving some typical numerical function minimization problems which are poorly solved by traditional evolutionary algorithms.The experimental results show that EAT is fast and reliable.     

A Differential Evolution Approach for Protein Folding Using a Lattice Model

Protein folding is a relevant computational problem in Bioinformatics, for which many heuristic algorithms have been proposed. This work presents a methodology for the application of differential evolution （DE） to the problem of protein folding, using the bi-dimensional hydrophobic-polar model. DE is a relatively recent evolutionary algorithm, and has been used successfully in several engineering optimization problems, usually with continuous variables. We introduce the concept of genotype-phenotype mapping in DE in order to provide a mapping between the real-valued vector and an actual folding. The methodology is detailed and several experiments with benchmarks are done. We compared the results with other similar implementations. The proposed DE has shown to be competitive, statistically consistent and very promising.     

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.     

Univied Parallel Lattice Structures for Block Time—Recursive Real—Valued Duiscrete Gabor Transforms

In this paper,the 1-D real-valued discrete Gabor transform(RDGT)proposed in the previous work and its relationship with the complex-valued discrete Gabor transform(CDGT)are briefly reviewed.Block time-recursive RDGT algorithms for the efficient and fast computation of the 1-D RDGT coefficients and for the fast reconstruction of the original signal from the coefficients are developed in both critical sampling and oversampling cases.Unified parallel lattice structuires for the implementation of the algorithms are studied.And the computational complexity analysis and comparison show that the proposed algorithms provide a more efficient and faster approach to the computation of the discrete Gabor transforms.     

Unified Parallel Lattice Structures for Block Time-Recursive Real-Valued Discrete Gabor Transforms

In this paper, the 1-D real-valued discrete Gabor transform (RDGT) proposed in the previous work and its relationship with the complex-valued discrete Gabor transform (CDGT) are briefly reviewed. Block time-recursive RDGT algorithms for the efficient and fast computation of the 1-D RDGT coefficients and for the fast reconstruction of the original signal from the coefficients are developed in both critical sampling and oversampling cases. Unified parallel lattice structures for the implementation of the algorithms axe studied. And the computational complexity analysis and comparison show that the proposed algorithms provide a more efficient and faster approach to the computation of the discrete Gabor transforms.     

Combinations of Estimation of Distribution Algorithms and Other Techniques

This paper summaries our recent work on combining estimation of distribution algorithms (EDA) and other techniques for solving hard search and optimization problems:a) guided mutation,an offspring generator in which the ideas from EDAs and genetic algorithms are combined together,we have shown that an evolutionary algorithm with guided mutation outperforms the best GA for the maximum clique problem,b)evolutionary algorithms refining a heuristic,we advocate a strategy for solving a hard optimization problem with complicated data structure,and c) combination of two different local search techniques and EDA for numerical global optimization problems,its basic idea is that not all the new generated points are needed to be improved by an expensive local search.     

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.     

Fast parallel algorithms for discrete Gabor expansion and transform based on multirate filtering

The Gabor transform has long been recognized as a very useful tool for the joint time and frequency analysis in signal processing.Its real time applications,however,were limited due to the high computational complexity of the Gabor transform algorithms.In this paper,some novel and fast parallel algorithms for the finite discrete Gabor expansion and transform are presented based on multirate filtering.An analysis filter bank is designed for the finite discrete Gabor transform(DGT)and a synthesis filter bank is designed for the finite discrete Gabor expansion(DGE).Each of the parallel channels in the two filter banks has a unified structure and can apply the FFT and the IFFT to reduce its computational load.The computational complexity of each parallel channel does not change as the oversampling rate increases.In fact,it is very low and depends only on the length of the input discrete signal and the number of the Gabor frequency sampling points.The computational complexity of the proposed parallel algorithms is analyzed and compared with that of the major existing parallel algorithms for the finite DGT and DGE.The results indicate that the proposed parallel algorithms for the finite DGT and DGE based on multirate filtering are very attractive for real time signal processing.     

Solving equations by hybrid evolutionary computation techniques

Evolutionary computation techniques have mostly been used to solve various optimization and learning problems. This paper describes a novel application of evolutionary computation techniques to equation solving. Several combinations of evolutionary computation techniques and classical numerical methods are proposed to solve linear and partial differential equations. The hybrid algorithms have been compared with the well-known classical numerical methods. The experimental results show that the proposed hybrid algorithms outperform the classical numerical methods significantly in terms of effectiveness and efficiency     

Evolutionary algorithms and de novo peptide design

One of the goals of computational chemistry is the automated de novo design of bioactive molecules. Despite significant progress in computational approaches to ligand design and efficient evaluation of binding energy, novel procedures for ligand design are required. Evolutionary computation provides a new approach to this design issue. This paper presents an automated methodology for computer-aided peptide design based on evolutionary algorithms. It provides an automatic tool for peptide de novo design, based on protein surface patches defined by user. Regarding the restrictive constrains of this problem a special emphasis has been made on the design of the evolutionary algorithms implemented.     

Enhancing rule-based scheduling in wafer fabrication facilities by evolutionary algorithms: Review and opportunity

Scheduling is a critical and challenging task in manufacturing systems, especially in large-scale complex systems like wafer fabrication facilities. Although evolutionary algorithms (EAs) have demonstrated many successful applications in the field of manufacturing scheduling, there are very few studies on scheduling of wafer fabs using EAs. Dispatching rules are one of the most common techniques for fab scheduling. In this paper, we present six ways of applying EAs for enhancing the rule-based scheduling system. We provide potential EA-based solutions and review relevant literature. Many of the mentioned viewpoints can serve as new research topics for both researchers in the fields of scheduling and evolutionary computation (EC). Several general EC techniques including multiobjective optimization, expensive optimization, and parallelization are also introduced and shown to be helpful to fab scheduling.     

The impact of parametrization in memetic evolutionary algorithms

Memetic (evolutionary) algorithms integrate local search into the search process of evolutionary algorithms. As computational resources have to be spread adequately among local and evolutionary search, one has to care about when to apply local search and how much computational effort to devote to local search. Often local search is called with a fixed frequency and run for a fixed number of iterations, the local search depth. There is empirical evidence that these parameters have a significant impact on performance, but a theoretical understanding as well as concrete design guidelines are missing.     

Evolutionary optimization in uncertain environments-a survey

Evolutionary algorithms often have to solve optimization problems in the presence of a wide range of uncertainties. Generally, uncertainties in evolutionary computation can be divided into the following four categories. First, the fitness function is noisy. Second, the design variables and/or the environmental parameters may change after optimization, and the quality of the obtained optimal solution should be robust against environmental changes or deviations from the optimal point. Third, the fitness function is approximated, which means that the fitness function suffers from approximation errors. Fourth, the optimum of the problem to be solved changes over time and, thus, the optimizer should be able to track the optimum continuously. In all these cases, additional measures must be taken so that evolutionary algorithms are still able to work satisfactorily. This paper attempts to provide a comprehensive overview of the related work within a unified framework, which has been scattered in a variety of research areas. Existing approaches to addressing different uncertainties are presented and discussed, and the relationship between the different categories of uncertainties are investigated. Finally, topics for future research are suggested.     

演化算法时间复杂性的趋势条件

计算时间复杂性是演化理论中的一个重大课题.将趋势分析引入演化算法的平均时间复杂性分析,可用于很广一类演化算法及许多问题.基于趋势分析,研究了确定演化算法时间复杂性的一些有用的趋势条件.这些条件应用于完全欺骗问题以验证其有效性.     

进化计算在复杂机电系统设计自动化中的应用综述

复杂机电系统设计自动化是知识自动化的一个重要分支, 在机器人系统设计、高档数控机床设计、智能装备系统设计等方面具有重要的研究意义和应用价值. 本文对进化计算在复杂机电系统设计自动化中的应用进行了综述. 首先, 介绍了几种常用进化计算方法及其优点; 其次, 对进化计算在电子系统、微机电系统和复杂机电系统三个领域的设计自动化进行了较为系统且全面的总结. 然后, 以一类典型的复杂机电系统—机器人系统的设计自动化为代表, 对进化计算在机器人系统设计自动化的研究发展进行了讨论. 最后, 针对进化计算在复杂机电系统设计自动化中存在的共性关键问题进行了讨论与展望.     

A research-led and industry-oriented MSc program in natural computation

Natural computation is the study of computational systems that use ideas and get inspirations from natural systems, including biological, physical, chemical, economical and social systems. It covers many active research fields, such as evolutionary computation, neural computation, molecular computation, quantum computation, ecological computation, etc. It has made tremendous progress in academic research and real-world applications. Many university departments have been offering individual modules/courses in one form or another on related topics. However, few universities have been offering an entire postgraduate program in natural computation. This article summarises one such MSc program in natural computation at the University of Birmingham, UK.     

Evolutionary algorithms and dynamic programming

Recently, it has been proven that evolutionary algorithms produce good results for a wide range of combinatorial optimization problems. Some of the considered problems are tackled by evolutionary algorithms that use a representation which enables them to construct solutions in a dynamic programming fashion. We take a general approach and relate the construction of such algorithms to the development of algorithms using dynamic programming techniques. Thereby, we give general guidelines on how to develop evolutionary algorithms that have the additional ability of carrying out dynamic programming steps. Finally, we show that for a wide class of the so-called DP-benevolent problems (which are known to admit FPTAS) there exists a fully polynomial-time randomized approximation scheme based on an evolutionary algorithm.