Evolutionary Design of Generic Structures Using Instruction-Based Development

Evolutionary algorithm, instruction, program, continual development, parametric development, environment, combinational logic circuit, general solution, generic structure.

Computational development rerpesents an extensive subset of the evolutionary design area. In general, the development is intended as an additional mechanism of evolutionary algorithm attempting to overcome the problem of scale that represent a crucial issue during the evolutionary design. Many models and techniques have been introduced so far, including their applications in various fields. This PhD thesis introduces a new class of developmental methods called an instruction-based development. The key feature is the evolution of application-specific programs, consisting of simple instructions, which is similar to the linear genetic programming approach. The concept of programs, in fact, enables to establish an universal computational model depending on the instruction set involved, interpretation and way of execution of the instructions. The program, represented as a sequence of instructions, can thus specify an arbitrary algorithm which is understood as a prescription for the development construction) of a target object. The objective of this work is to apply the instruction-based development to design generic structures. Combinational circuits have been chosen as suitable domain to demonstrate the capabilities of this approach. Experiments have been conducted, Two different approaches to the instruction-based development have been introduced. The first approach has been called a continual development. The target circuit can grow from an initial solution theoretically infinitely, preserving a desired function all the time during the development. A case study of the continual development is presented in the domain of the evolutionary design of generic sorting networks. It has been shown that the evolution is able to discover innovative solutions which exhibit better parameters in comparison with a conventional principle. The general properties of the best result have been demonstrated formally. Moreover, evolution of generic polymorphic circuits has been presented using the continual development approach. The second approach represents a parametric development. In this case the target circuit is developed every time from the start, while the size of its target instance is specified by a parameter. An external information, that we called an environment, has been introduced into the developmental system in order to develop generic structures containing irregular parts. The experiments have been conducted in the area of the evolutionary design of generic combinational multipliers. Two variants of a parametric developmental system have been presented. The first one represents an initial experiment of the evolution of common generic multipliers using the development, whilst the second one is intended to design effective generic carry-save multipliers. In general, ve have introduced an extensive set of experiments demonstrating the capability of the proposed concepts of instruction-based development to design various generic structures, including a discovery of some new general innovative solutions.