A family of compact genetic algorithms for intrinsic evolvable hardware

For many evolvable hardware applications, small size and power efficiency are critical design considerations. One manner in which significant memory, and thus, power and space savings can be realized in a hardware-based evolutionary algorithm is to represent populations of candidate solutions as probability vectors rather than as sets of bit strings. The compact genetic algorithm (CGA) is a probability vector-based evolutionary algorithm that can be efficiently and elegantly implemented in digital hardware. Unfortunately, the CGA is a very weak, first order, evolutionary algorithm that is unlikely to possess sufficient search power to enable intrinsic evolvable hardware applications. In this paper, we further develop a number of modifications to the basic CGA that significantly improve its search efficacy without substantially increasing the size and complexity of its hardware implementation. The paper provides both benchmark results demonstrating increased efficacy and a conceptual data path/microcontroller design suitable for implementation in digital hardware. Following, it demonstrates efficient implementation by making a head-to-head comparison of field programmable gate array implementations of both the classic CGA and a member of our family of modifications. The paper concludes with a discussion of future research, including several additional extensions that we expect will further increase search efficacy without increasing implementation cost.     

基于免疫原理的逻辑电路设计算法

硬件进化是基于进化计算和可重构硬件的新兴研究领域。逻辑电路的进化设计是硬件进化的主要研究方向之一。文章将生物免疫系统的进化非选择机制引入到逻辑电路设计中,提出了相应的逻辑电路设计算法,并给出了该文算法和进化算法的对比实验结果,结果表明该文算法更加有效。     

基于演化算法的电路自动设计方法

在电路设计中引入演化计算,在可编程逻辑器件上通过对基本电路元器件进行演化而自动生成人工不可能设计出的电路结构,称为演化硬件设计。文中介绍了演化硬件实现的物质基础、演化计算在硬件自动设计方法的实现过程以及该方法要解决的问题,并对演化数字电路、模拟电路的设计进行了分析,说明演化算法在电路自动设计中是切实有效的。     

硬件进化中演化算法的研究及应用

详细介绍了硬件进化的概念,硬件进化的原理与实现思想,遗传算法与蚁群算法动态融合的基本原理,融合后算法中遗传算法及蚁群算法规则.融合过程中遗传算法与蚁群算法动态衔接问题以及融合后的算法在硬件进化中的应用过程.最后,分析了通过该算法进化后硬件的进化应用前景.     

基于EHW的可进化传感器的研究

为克服常规传感器对信号采集和处理的局限,探求了一种具有智能传感并自适应于外部环境的机理,将常规传感器和可进化硬件相结合,提出了一种可进化传感器的基本框架,介绍了基于遗传算法和可进化硬件原理的具有自适应能力和容错特性的可进化传感器的初步研究。     

Evolvable Hardware in Evolutionary Robotics

In recent decades the research on Evolutionary Robotics (ER) has developed rapidly. This direction is primarily concerned with the use of evolutionary computing techniques in the design of intelligent and adaptive controllers for robots. Meanwhile, much attention has been paid to a new set of integrated circuits named Evolvable Hardware (EHW), which is capable of reconfiguring its architectures unlimited time based on artificial evolution techniques. This paper surveys the application of evolvable hardware in evolutionary robotics. The evolvable hardware is an emerging research field concerning the development of evolvable robot controllers at the hardware level to adapt to dynamic changes in environments. The context of evolvable hardware and evolutionary robotics is reviewed, and a few representative experiments in the field of robotic hardware evolution are presented. As an alternative to conventional robotic controller designs, the potentialities and limitations of the EHW-based robotic system are discussed and summarized.     

演化硬件技术及其应用发展

在硬件电路设计中引入演化计算,在可编程逻辑器件上通过对基本电路元器件进行演化而自动生成人工不可能设计出的电路结构,称为演化硬件设计。本文就演化硬件的原理和其国内外的发展现状进行说明和阐述,并对此技术的具体实现过程做了一个简单的实验。通过实验,说明演化硬件技术确实在电路自动设计方面有着极大的前景。最后介绍了演化硬件技术发展,及其应用到深空探测领域的现实意义。     

Quantum-inspired design of resilient substitution boxes: From coding to hardware implementation

S-boxes constitute a cornerstone component in symmetric-key cryptographic algorithms, such as DES and AES encryption systems. In block ciphers, they are typically used to obscure the relationship between the plaintext and the ciphertext. Non-linear and non-correlated S-boxes are the most secure against linear and differential cryptanalysis. In this paper, we focus on a twofold objective: first, we evolve regular S-boxes with high non-linearity and low auto-correlation properties; then automatically generate evolvable hardware for the obtained S-box. Targeting the former, we use a quantum-inspired evolutionary algorithm to optimize regularity, non-linearity and auto-correlation, which constitute the three main desired properties in resilient S-boxes. Pursuing the latter, we exploit the same algorithm to automatically generate the evolvable hardware designs of substitution boxes that minimize hardware space and encryption/decryption time, which form the two main hardware characteristics. We compare our results against existing and well-known designs, which were produced by using conventional methods as well as through genetic algorithm. We will show that our approach provides higher quality S-boxes coding as well as circuits.     

REVISITING OVERLOOKED FOUNDATIONS OF EVOLUTIONARY COMPUTATION: PART I

Evolutionary computation is a rapidly expanding field of research with a long history. Much of that history remains unknown to most practitioners and researchers. This two-part article offers a review of selected foundational efforts in evolutionary computation, with focus on those that have not received commensurate attention. Part I presents a brief initial overview of the essential components of evolutionary algorithms followed by a review of early research in artificial life. Part II reviews seminal results in evolving programs and evolvable hardware. Comments on theoretical developments and future developments conclude Part II.     

演化硬件在图像边缘检测中的应用

设计基于演化硬件（Evolvable Hardware，EHW）的快速边缘检测进化系统，提出一种适于此系统的图像边缘提取操作结构，给出进化算法的编码方案，设计用于染色体评估的适应度函数，利用标准遗传算法来实现可变结构参数的图像边缘提取进化方法，并采用Roberts，Sobel，LOG，Robinson等传统边缘检测算法与进化方法进行对比试验。结果表明：进化方法边缘检测误差率最低，只有9．87％，其边缘提取的效果优于传统检测方法，     

REVISITING OVERLOOKED FOUNDATIONS OF EVOLUTIONARY COMPUTATION: PART II

Evolutionary computation is a rapidly expanding field of research with a long history. Much of that history remains unknown to most practitioners and researchers. This two-part article offers a review of selected foundational efforts in evolutionary computation, with a focus on those that have not received commensurate attention. Part I presented an initial overview of the essential components of evolutionary algorithms followed by a review of early research in artificial life and modeling genetic systems. Here, Part II reviews seminal results in evolving programs and evolvable hardware. Comments on theoretical developments and future developments conclude Part II.     

基于动态可重构FPGA的自演化硬件概述

演化硬件研究如何利用遗传算法进行硬件自动设计,或者设计随外界环境变化而自适应地改变自身结构的硬件,在电子设计自动化、自主移动机器人控制器、无线传感器网络节点等领域都有潜在的应用价值. 自演化硬件是在硬件内部完成遗传操作和适应度计算,利用支持动态部分可重构的FPGA芯片上的微处理器核实现遗传算法,模拟生物群体演化过程搜索可能的电路设计并配置片上的可重构逻辑,找到最优或较优的设计结果,从而实现自适应硬件. 当电路发生故障时,自演化硬件自动搜索新的配置,利用片上冗余资源取代故障区域,从而实现自修复硬件. 介绍了基于动态部分可重构FPGA的自演化硬件的基本思想、体系结构以及研究现状,总结并提出了亟待解决的关键技术,指出高效的电路染色体编码表示与可重构逻辑配置位串之间的映射方式是当前研究的重点之一.     

用遗传算法实现逻辑函数的化简

在硬件设计中引入演化计算，在可编程逻辑器件上通过对基本硬件元器件进行演化而自动生成人工难以设计出的硬件结构，称为演化硬件设计。代数法和卡诺图法用来化简给定的逻辑函数，但它们难以化简规模很大的逻辑函数。这里用演化硬件设计方法实现了区别于传统的代数化简法和卡诺图化简法的一种新的对给定的某一逻辑函数进行化简的方法。实验表明演化硬件设计方法能够化简规模很大的逻辑函数。     

Evolutionary design and adaptation of high performance digital filters within an embedded reconfigurable fault tolerant hardware platform

Finite impulse response filters (FIRs) are crucial devices for robust data communication and manipulation. Multiplierless filters have been shown to produce high performance systems with fast signal processing and reduced area. Furthermore, the distributed architecture inherent in multiplierless filters makes it a suitable candidate for fault tolerant design. Alternative approaches to the design of fault tolerant systems have been proposed using evolutionary algorithms (EAs) and the concept of evolvable hardware (EHW). This paper presents an evolvable hardware platform for the automated design and adaptation of multiplierless digital filters. Filters are realised within a dedicated programmable logic array (PLA) based on the Primitive Operator Filter design principle. The platform employs a genetic algorithm to autonomously configure the PLA for a given set of coefficients. The ability of the platform to adapt to increasing numbers of faults was investigated through the evolution of a 31-tap low-pass FIR filter. Results show that the functionality of filters evolved on the PLA was maintained despite an increasing number of faults covering up to 25% of the PLA area. Additionally, three PLA initialisation methods were investigated to ascertain which produced the fastest fault recovery times. It was shown that seeding a population of random configuration-strings with the best configuration currently obtained resulted in a 6 fold increase in fault recovery speed over other methods investigated.     

基于演化硬件的在线自适应系统

随着演化硬件的兴起,其在电子电路自动设计、客错以及自适应等方面的优越性,使它有望成为突破传统电子系统设计瓶颈的新技术.在已有研究的基础之上,进一步探讨利用演化硬件技术实现电子系统的自适应性,提出了一个基于演化硬件技术的自适应系统模型,并通过在Xilinx Virtex-Ⅱ Pro (XC2VP20)FPGA芯片上的实验,表明了演化硬件技术是解决电子系统自适应性问题的一种可行方案.     

Evolvable hardware techniques for on-chip automated reconfiguration of programmable devices

While complete automated design is a harder problem than computer-assisted design, automated hardware reconfiguration is an even more challenging problem, because it needs to adjust to limited resources and various factors, such as noise and parasitic capacitance, a resistance and inductance. This paper presents some experimental results of on-chip automated design and reconfiguration using evolvable hardware techniques. It describes a stand-alone board level evolvable system, and its use to demonstrate on-chip synthesis of new circuits in only a few seconds. The experiments presented here indicate a recovery capability in the case of extreme environmental conditions, such as extreme temperatures, that adversely affect electronics. Some of the difficulties of dealing with the real hardware are exposed, as well as challenges more generally related to automated evolution of complex electronic systems.The work described in this paper was performed at the Center for Integrated Space Microsystems, Jet Propulsion Laboratory, California Institute of Technology and was sponsored by the Defense Advanced Research Projects Agency and by the National Aeronautics and Space Administration.     

Learning hardware using multiple-valued logic - Part 1:introduction and approach

The authors propose a learning-hardware approach as a generalization of evolvable hardware. A massively parallel, reconfigurable processor speeds up logic operators performed in learning hardware. The approach uses combinatorial synthesis methods developed within the framework of the logic synthesis in digital-circuit-design automation     

Evolvable hardware: A robot navigation system testbed

Recently there has been great interest in the design and study of evolvable systems based on Artificial Life principles in order to monitor and control the behavior of physically embedded systems such as mobile robots, plants and intelligent home devices. At the same time new integrated circuits calledsoftware-reconfigurable devices have been introduced which are able to adapt their hardware almost continuously to changes in the input data or processing. When the configuration phase and the execution phase are concurrent, the software-reconfigurable device is calledevolvable hardware (EHW). This paper examines an evolutionary navigation system for a mobile robot using a Boolean function approach implemented on gate-level evolvable hardware (EHW). The task of the mobile robot is to reach a goal represented by a colored ball while avoiding obstacles during its motion. We show that the Boolean function approach using dedicated evolution rules is sufficient to build the desired behavior and its hardware implementation using EHW allows to decrease the learning time for on-line training. We demonstrate the effectiveness of the generalization ability of the Boolean function approach using EHW due to its representation and evolution mechanism. The results show that the evolvable hardware configuration learned off-line in a simple environment creates a robust robot behavior which is able to perform the desired behaviors in more complex environments and which is insensitive to the gap between the real and simulated world. Didier Keymeulen, Ph.D.: He currently works as a senior research engineer at the Computer Science Division of Electrotechnical Laboratory, AIST, MITI, Japan. His research interests are in the design of adaptive physically embedded systems using biologically inspired complex dynamical systems. He studied electrical and computer science engineering at the Universite Libre de Bruxelles in 1987. He obtained his M. Sc. and PH. D. in Computer Science from the Artificial Intelligence Laboratory of the Vrije Universiteit Brussel, directed by Dr. Luc Steels, respectively in 1991 and 1994. He was the Belgium laureate of the Japanese JSPS Postdoctoral Fellowship for Foreign Researchers in 1995. Masaya Iwata, Ph.D.: He currently works as a researcher at the Computer Science Division of Electrotechnical Laboratory, AIST, MITI, Japan. His research interests are in developing adaptive hardware devices using genetic algorithms, and in their applications to pattern recognition and image compression. He received his B. E. in 1988, his M. E. in 1990, and his Ph. D. in 1993 in applied physics from the Osaka University. He was a postdoctoral fellow in optical computing at ONERA-CERT, Toulouse, France in 1993. Kenji Konaka: He is currently working as a software research engineer at the Humanoid Interaction Laboratory of the Intelligent Systems Division of Electrotechnical Laboratory, AIST, MITI, Japan. His current research interest is on real-time vision-based mobile robots working in cooperative mode. He has developped a highly interactive distributed real-time software and hardware platform for controlling a group of robots. Yasuo Kuniyoshi, Ph.D.: He is currently a senior research scientist and head of the Humanoid Interaction Laboratory at the Intelligent Systems Division of Electrotechnical Laboratory, AIST, MITI, Japan. His current research interest is on emergence of stable structures out of complex sensory-motor interactions by a humanoid robot. He received IJCAI93 Outstanding Paper A ward and several other awards in the field of intelligent robotics. He received the B. Eng. in applied physics in 1985, M. Eng. and Ph. D. in information engineering in 1988 and 1991 respectively, all from the University of Tokyo. Tetsuya Higuchi, Ph.D.: He heads the Evolvable Systems Laboratory in Electrotechnical Laboratory, AIST, MITI, Japan. He received B. E., M. E., Ph. D. degrees all in electrical engineering from Keio University in 1978, 1980, and 1984, respectively. His current interests include envolvable hardware systems, parallel processing architecture in artificial intelligence, and adaptive systems. He is also in charge of the adaptive devices group in the MITI national project, Real World Computing Project.     

基于函数级FPGA原型的硬件内部进化

电路进化设计是现阶段可进化硬件（EHW）研究的重点内容，针对制约进化设计能力的主要“瓶颈”，该文提出并讨论了一种简洁高效的内部进化方法，包括基于函数变换的染色体高效编码方案，与之配套的函数级FPGA原型和进化实验平台以及在线评估与遗传数自适应方法等，交通灯控制器，4位可级联比较器等相对复杂且具应用价值的电路的成功进化，证明该方法适用于组合，时序电路的进化设计，并可显著地减少运算量，提高进化设计的速度和规模。