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.     

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.     

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.     

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

Accelerating floating-point fitness functions in evolutionary algorithms: a FPGA-CPU-GPU performance comparison

Many large combinatorial optimization problems tackled with evolutionary algorithms often require very high computational times, usually due to the fitness evaluation. This fact forces programmers to use clusters of computers, a computational solution very useful for running applications of intensive calculus but having a high acquisition price and operation cost, mainly due to the Central Processing Unit (CPU) power consumption and refrigeration devices. A low-cost and high-performance alternative comes from reconfigurable computing, a hardware technology based on Field Programmable Gate Array devices (FPGAs). The main objective of the work presented in this paper is to compare implementations on FPGAs and CPUs of different fitness functions in evolutionary algorithms in order to study the performance of the floating-point arithmetic in FPGAs and CPUs that is often present in the optimization problems tackled by these algorithms. We have taken advantage of the parallelism at chip-level of FPGAs pursuing the acceleration of the fitness functions (and consequently, of the evolutionary algorithms) and showing the parallel scalability to reach low cost, low power and high performance computational solutions based on FPGA. Finally, the recent popularity of GPUs as computational units has moved us to introduce these devices in our performance comparisons. We analyze performance in terms of computation times and economic cost.     

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.     

Integrating instance selection, instance weighting, and feature weighting for nearest neighbor classifiers by coevolutionary algorithms

Cooperative coevolution is a successful trend of evolutionary computation which allows us to define partitions of the domain of a given problem, or to integrate several related techniques into one, by the use of evolutionary algorithms. It is possible to apply it to the development of advanced classification methods, which integrate several machine learning techniques into a single proposal. A novel approach integrating instance selection, instance weighting, and feature weighting into the framework of a coevolutionary model is presented in this paper. We compare it with a wide range of evolutionary and nonevolutionary related methods, in order to show the benefits of the employment of coevolution to apply the techniques considered simultaneously. The results obtained, contrasted through nonparametric statistical tests, show that our proposal outperforms other methods in the comparison, thus becoming a suitable tool in the task of enhancing the nearest neighbor classifier.     

Large scale structural optimization: Computational methods and optimization algorithms

Summary The objective of this paper is to investigate the efficiency of various optimization methods based on mathematical programming and evolutionary algorithms for solving structural optimization problems under static and seismic loading conditions. Particular emphasis is given on modified versions of the basic evolutionary algorithms aiming at improving the performance of the optimization procedure. Modified versions of both genetic algorithms and evolution strategies combined with mathematical programming methods to form hybrid methodologies are also tested and compared and proved particularly promising. Furthermore, the structural analysis phase is replaced by a neural network prediction for the computation of the necessary data required by the evolutionary algorithms. Advanced domain decomposition techniques particularly tailored for parallel solution of large-scale sensitivity analysis problems are also implemented. The efficiency of a rigorous approach for treating seismic loading is investigated and compared with a simplified dynamic analysis adopted by seismic codes in the framework of finding the optimum design of structures with minimum weight. In this context a number of accelerograms are produced from the elastic design response spectrum of the region. These accelerograms constitute the multiple loading conditions under which the structures are optimally designed. The numerical tests presented demonstrate the computational advantages of the discussed methods, which become more pronounced in large-scale optimization problems.     

约束优化进化算法

约束优化问题是科学和工程应用领域经常会遇到的一类数学规划问题.近年来,约束优化问题求解已成为进化计算研究的一个重要方向.从约束优化进化算法=约束处理技术+进化算法的研究框架出发,从约束处理技术和进化算法两个基本方面对约束优化进化算法的研究及进展进行了综述.此外,对约束优化进化算法中的一些重要问题进行了探讨.最后进行了各种算法的比较性总结,深入分析了目前约束优化进化算法中亟待解决的问题,并指出了值得进一步研究的方向.     

Balance between genetic search and local search in memetic algorithms for multiobjective permutation flowshop scheduling

This paper shows how the performance of evolutionary multiobjective optimization (EMO) algorithms can be improved by hybridization with local search. The main positive effect of the hybridization is the improvement in the convergence speed to the Pareto front. On the other hand, the main negative effect is the increase in the computation time per generation. Thus, the number of generations is decreased when the available computation time is limited. As a result, the global search ability of EMO algorithms is not fully utilized. These positive and negative effects are examined by computational experiments on multiobjective permutation flowshop scheduling problems. Results of our computational experiments clearly show the importance of striking a balance between genetic search and local search. In this paper, we first modify our former multiobjective genetic local search (MOGLS) algorithm by choosing only good individuals as initial solutions for local search and assigning an appropriate local search direction to each initial solution. Next, we demonstrate the importance of striking a balance between genetic search and local search through computational experiments. Then we compare the modified MOGLS with recently developed EMO algorithms: the strength Pareto evolutionary algorithm and revised nondominated sorting genetic algorithm. Finally, we demonstrate that a local search can be easily combined with those EMO algorithms for designing multiobjective memetic algorithms.     

A survey: hybrid evolutionary algorithms for cluster analysis

Clustering is a popular data analysis and data mining technique. It is the unsupervised classification of patterns into groups. Many algorithms for large data sets have been proposed in the literature using different techniques. However, conventional algorithms have some shortcomings such as slowness of the convergence, sensitive to initial value and preset classed in large scale data set etc. and they still require much investigation to improve performance and efficiency. Over the last decade, clustering with ant-based and swarm-based algorithms are emerging as an alternative to more traditional clustering techniques. Many complex optimization problems still exist, and it is often very difficult to obtain the desired result with one of these algorithms alone. Thus, robust and flexible techniques of optimization are needed to generate good results for clustering data. Some algorithms that imitate certain natural principles, known as evolutionary algorithms have been used in a wide variety of real-world applications. Recently, much research has been proposed using hybrid evolutionary algorithms to solve the clustering problem. This paper provides a survey of hybrid evolutionary algorithms for cluster analysis.     

Genetic Programming and Autoconstructive Evolution with the Push Programming Language

Push is a programming language designed for the expression of evolving programs within an evolutionary computation system. This article describes Push and illustrates some of the opportunities that it presents for evolutionary computation. Two evolutionary computation systems, PushGP and Pushpop, are described in detail. PushGP is a genetic programming system that evolves Push programs to solve computational problems. Pushpop, an autoconstructive evolution system, also evolves Push programs but does so while simultaneously evolving its own evolutionary mechanisms.     

Cryptographic Boolean functions: One output,many design criteria

Boolean functions represent an important primitive in the design of various cryptographic algorithms. There exist several well-known schemes where a Boolean function is used to add nonlinearity to the cipher. Thus, methods to generate Boolean functions that possess good cryptographic properties present an important research goal. Among other techniques, evolutionary computation has proved to be a well-suited approach for this problem. In this paper, we present three different objective functions, where each inspects important cryptographic properties of Boolean functions, and examine four evolutionary algorithms. Our research confirms previous results, but also sheds new insights on the effectiveness and comparison of different evolutionary algorithms for this problem.     

分布式优化: 算法设计和收敛性分析

近年来,随着高科技的蓬勃发展,特别是云计算和大数据等新兴领域的出现,分布式优化理论和应用得到了越来越多的重视,并逐渐渗透到科学研究、工程应用和社会生活的各个方面,分布式优化是通过多智能体之间的合作协调有效地实现优化的任务,可用来解决许多集中式算法难以胜任的大规模复杂的优化问题.如今如何设计出有效的分布式优化算法并对其进行收敛性和复杂性的分析成了优化研究的主要任务之一.与集中式算法的主要区别在于分布式算法还不得不考虑通讯和协调在优化中起到的重要作用.本文集中讨论了近年来分布式优化研究中的一些典型热门的研究问题,从一个侧面介绍了包括无约束优化、带约束优化、以及分布式博弈等方向的部分最新成果.同时也比较详尽地论述了笔者最近的相关研究成果.最后,本文简要地对分布式优化的研究和应用前景进行了展望.