Drift analysis in studying the convergence and hitting times of evolutionary algorithms: An overview

This paper introduces drift analysis approach in studying the convergence and hitting times of evolutionary algorithms. First the methodology of drift analysis is introduced, which links evolutionary algorithms with Markov chains or supermartingales. Then the drift conditions which guarantee the convergence of evolutionary algorithms are described. And next the drift conditions which are used to estimate the hitting times of evolutionary algorithms are presented. Finally an example is given to show how to analyse hitting times of EAs by drift analysis approach. Foundation item: Supported by Engineering and Physical Science Research Courcil (GR R52541 01) and State Laboratory of Software Engineering Foundation item: Supported by Engineering and Physical Science Research Courcil (GR R52541 01) and State Laboratory of Software Engineering Biography: He Jun( 1967-), male, visiting fellow at State Key Lab of Software Engineering, Ph D. , research direction: computational intelligence     

A Multi-objective optimal evolutionary algorithm based on tree-ranking

Multi-objective optimal evolutionary algorithms (MOEAs) are a kind of new effective algorithms to solve Multi-objective optimal problem (MOP). Because ranking, a method which is used by most MOEAs to solve MOP, has some shortcomings, in this paper, we proposed a new method using tree structure to express the relationship of solutions. Experiments prove that the method can reach the Pare-to front, retain the diversity of the population, and use less time. Foundation item: Supported by the National Natural Science Foundation of China(60073043, 70071042, 60133010) Biography: Shi Chuan( 1978-), male, Master candidate, research direction; intellective computation, evolutionary computation.     

Evolutionary graph drawing algorithms

In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements. Foundation item: Supported by the National Natural Science Foundation of China(60133010,60073043,70071042) Biography: Huang Jing-wei ( 1956-), male, Professor, research direction: the design and analysis of algorithms and evolutionary computation.     

Some massively parallel algorithms from nature

We introduced the work on parallel problem solvers from physics and biology being developed by the research team at the State Key Laboratory of Software Engineering, Wuhan University. Results on parallel solvers include the following areas: Evolutionary algorithms based on imitating the evolution processes of nature for parallel problem solving, especially for parallel optimization and model-building; Asynchronous parallel algorithms based on domain decomposition which are inspired by physical analogies such as elastic relaxation process and annealing process, for scientific computations, especially for solving nonlinear mathematical physics problems. All these algorithms have the following common characteristics: inherent parallelism, self-adaptation and self-organization, because the basic ideas of these solvers are from imitating the natural evolutionary processes. Foundation item: Supported by the National Natural Science Foundation of China (No. 60133010, No. 70071042, No. 60073043) and National Laboratory for Parallel and Distributed Processing Biography: Li Yan (1974-), female, Ph. D candidate, research direction: evolutionary computation.     

The evolutionary computation techniques for protein structure prediction: A survey

In this paper, the applications of evolutionary al gorithm in prediction of protein secondary structure and tertiary structures are introduced, and recent studies on solving protein structure prediction problems using evolutionary algorithms are reviewed, and the challenges and prospects of EAs applied to protein structure modeling are analyzed and discussed. Foundation item: Supported by the National Natural Science Foundation of China( 60133010,70071042,60073043) Biography: Zou Xiu-fen ( 1966-), female, Associate professor, research direction:evolutionary computing, parallel computing, bioinformatics.     

关于多目标演化算法的策略分析

基于Pareto排序算法的多目标演化算法是多目标演化算法所采用的重要方法,本文叙述了多目标演化算法(MOEAs)的有关概念,在分析已有算法的一些性能和特征的基础上,结合演化算法的有关概念,重点基于Pareto排序算法分析了影响多目标演化算法性能的两大方面:求解过程中解集合的多样性、均匀性分布的保持与维护以及解的收敛性,分析了MOEAs设计中需要注意的策略问题以及今后研究的重点.     

A generic design model for evolutionary algorithms

A generic design model for evolutionary algorithms is proposed in this paper. The model, which was described by UML in details, focuses on the key concepts and mechanisms in evolutionary algorithms. The model not only achieves separation of concerns and encapsulation of implementations by classification and abstraction of those concepts, it also has a flexible architecture due to the application of design patterns. As a result, the model is reusable, extendible, easy to understand, easy to use, and easy to test. A large number of experiments applying the model to solve many different problems adequately illustrate the generality and effectivity of the model. Foundation item: Supported by the National Natural Science Foundatron of China (70071042, 60073043, 60133010) Biography: He Feng (1974-), male, Ph. D candidate, research direction evolutionary computation, software engineering.     

多目标进化算法研究综述

简要介绍了多目标进化算法(MOEAs)的基本框架、研究历史、总体分类和主要方法,同时讨论了进化算法(EAs)在多目标优化的应用中的几个关键性问题及今后需进一步研究的工作.     

一类自适应的差分演化算法

介绍了差分演化算法常用的五个版本和一种自适应技术,并给出了五个自适应的差分演化算法.并试验研究了各自适应差分演化算法在欺骗问题上的表现,还分析了自适应差分演化算法的性能.     

A niche-based evolutionary Tabu search algorithm for optimal coordination of protection relays in power networks

In this paper, refusal of operation and the degree of constraint violation are considered as one part of the objective function for optimizing the protection relay setting coordination of over current relays in power systems; a new expression of objective function in this optimization problem is proposed. To combine the advantages of both Tabu search (TS) and evolutionary algorithms (EAs), a new niche-based evolutionary Tabu search algorithm (named NETS) is presented to solve this optimization problem. Moreover, in two cases of power networks, comparisons between NETS and two published algorithms are given. Experimental results show the expression of the objective function for protection relay setting is feasible and reasonable, and the proposed algorithm NETS exhibits a good performance. Biography: YUAN Rongxiang (1965–), male, Professor, Ph. D., research direction: safety and stability in distributed power networks, relay protection, information and intelligent of power system.     

基于粒群行为与克隆的移动机器人进化路径规划

针对移动机器人路径规划, 将粒群行为和生命科学中的免疫克隆原理、进化算法相结合, 将过去进化过程中的经验通过粒群行为来体现, 提出了一种结合粒群行为和免疫克隆的移动机器人进化规划, 较快速地规划出性能是全局优化的可行路径. 分析了粒群行为的二种学习方式对路径规划的作用, 研究了通过调整粒群行为操作中的参数实现多路径规划. 通过仿真实验, 对上述算法进行了验证.     

A new structure of EHW

Evolvable hardware (EHW) realizes circuit function through evolution. It may be viewed as the combination of EAs (evolutionary algorithms) and PLDs (programmable logic devices). At present the main problem is that the speed of evolution is too slow. In order to tackle the problem, we must do work from two aspects: algorithm and device structure. This paper presents a function PLD as a new EHW's structure. So the efficiency of coding is improved, and evolution is sped up. A 4-bit comparator is successfully completed. Supported by the National Natural Science Foundation of China He Wei born in 1969, Ph.D.     

Design of evolvable hardware for robotic navigation

This paper presents an integrated on-line learning system to evolve programmable logic array (PLA) controllers for navigating an autonomous robot in a two-dimensional environment. The integrated online learning system consists of two learning modules: one is the module of reinforcement learning based on temporal-difference learning based on genetic algorithms, and the other is the module of evolutionary learning based on genetic algorithms. The control rules extracted from the module of reinforcement learning can be used as input to the module of evolutionary learning, and quickly implemented by the PLA through on-line evolution. The on-line evolution has shown promise as a method of learning systems in complex environment. The evolved PLA controllers can successfully navigate the robot to a target in the two-dimensional environment while avoiding collisions with randomly positioned obstacles.     

An improved group search optimizer for mechanical design optimization problems

This paper presents an improved group search optimizer (iGSO) for solving mechanical design optimization problems. In the proposed algorithm, subpopulations and a co-operation evolutionary strategy were adopted to improve the global search capability and convergence performance. The iGSO is evaluated on two optimization problems of classical mechanical design: spring and pressure vessel. The experimental results are analyzed in comparison with those reported in the literatures. The results show that iGSO has much better convergence performance and is easier to implement in comparison with other existing evolutionary algorithms.     

基于组织进化和信息熵的数据驱动分类算法

提出了一种分类算法---基于组织进化和信息熵的数据驱动分类算法(a data-driven classification algorithm based on organizational evolution and entropy,DDCAOEE),与已有进化算法的运行机制不同,它的进化操作直接作用于数据而不是规则,进化结束后再从各组织中提取规则,这样有利于避免在进化过程中产生无意义的规则。根据分类问题的特点,设计了信息系统的组织,提出了3种进化算子和一种组织选择机制,给出了基于信息熵的属性重要度的进化方式,并基于此定义了组织适应度函数,最后,将算法用于6个试验数据集,并与现有的2个分类方法(Ant-Miner和CN2)进行了比较,实验结果表明,该方法获得了更高的预测准确率,产生了更小的规则集。     

噪声环境下进化算法

以球型模型为例, 讨论了环境噪声对遗传算法(GAs)和进化策略(ESs) 及进化算法(EAs)的影响.并采用重新采样的方法来抑制噪声,提高进化算法在复杂环境下的鲁棒性.     

多群体并行遗传算法迁移策略的性能研究

研究了迁移策略对并行遗传算法性能的影响。研究了所有可能的4种组合：（1）选取最优个体进行迁移并在目的子群体中替换最差个体；（2）随机选取个体进行迁移并在目的子群体中替换最差个体；（3）选取最优个体进行迁移并在目的子群体中随机替换个体；（4）随机选取个体进行迁移并在目的子群体中随机替换个体。从累积量（Cumulants）的分析来看，似乎选取最优个体进行迁移并在目的子群体中随机替换个体的迁移策略能更好地兼顾局部搜索和全局搜索。通过对几个典型测试函数的测试，结果表明：选取最优个体进行迁移并在目的子群体中随机替换个体的迁移策略不比其他3种策略差，甚至在部分测试中要优于其他策略。这一结果可能有助于设计出性能更好的并行遗传算法。     

基于仿生进化的自动控制系统

介绍了基于仿生进化的优化理论与技术：遗传算法,进化规划和进化策略;概述了遗传算法中的编码机制,适应度函数的建立以及三种基因操作（选种,交配和突变）;叙述了遗传算法在模糊控制、自适应控制、神经网络控制、最优控制、多变量控制以及相关技术（系统辨识,故障诊断,机器人学习）中的应用;还简述了进化规划和进化策略的机理及其在自动控制中的应用。     

非支配解集的质量评价方法

多目标演化算法的目的是获得逼近Pareto最优前沿的分布均匀的非支配解集合,非支配解集的质量是多目标演化算法研究的重要领域.本文对目前提出的非支配解集的质量评价方法进行分类比较,为算法的整体性能评价和算法的性能比较提供了参考依据.     

基于DNA进化算法的车辆调度问题

在建立一种物流配送车辆调度模型的基础上,针对传统启发式算法对复杂问题搜索效率低、易陷入局部最优的缺点,构造了DNA进化算法求解该问题。将其在个体变异操作中进行了一些改进,避免陷入局部最优。车辆调度问题(V SP)属于组合优化NP难题。采用V SP问题进行测试,仿真结果表明:该算法简单可行,与其他算法相比较,不但有很好的求解性能,而且具有更快的收敛能力与搜索能力。