Evolvable Hardware is a technique derived from evolutionary computation applied to a hardware design. The term evolutionary computation involves similar steps as involved in the human evolution. It has been given names in accordance with the electronic technology like, Genetic Algorithm (GA), Evolutionary Strategy (ES) and Genetic Programming (GP). In evolutionary computing, a configured bit is considered as a human chromosome for a genetic algorithm, which has to be downloaded into hardware. Early evolvable hardware experiments were conducted in simulation and the only elite chromosome was downloaded to the hardware, which was labelled as Extrinsic Hardware. With the invent of Field Programmable Gate Arrays (FPGAs) and Reconfigurable Processing Units (RPUs), it is now possible for the implementation solutions to be fast enough to evaluate a real hardware circuit within an evolutionary computation framework; this is called an Intrinsic Evolvable Hardware. This research has been taken in continuation with project 'Evolvable Hardware' done at Manukau Institute of Technology (MIT). The project was able to manually evolve two simple electronic circuits of NAND and NOR gates in simulation. In relation to the project done at MIT this research focuses on the following: To automate the simulation by using In Circuit Debugging Emulators (IDEs), and to develop a strategy of configuring hardware like an FPGA without the use of their company supplied in circuit debugging emulators, so that the evolution of an intrinsic evolvable hardware could be controlled, and is hardware independent. As mentioned, the research conducted here was able to develop an evolvable hardware friendly Generic Structure which could be used for the development of evolvable hardware. The structure developed was hardware independent and was able to run on various FPGA hardware’s for the purpose of intrinsic evolution. The structure developed used few configuration bits as compared to current evolvable hardware designs.

<p>FIR filters are widely used nowadays, with applications from MP3 players, Hi-Fi systems, digital TVs, etc. to communication systems like wireless communication. They are implemented in DSPs and there are several trade-offs that make important to have an exact as possible estimation of the required filter order. </p><p>In order to find a better estimation of the filter order than the existing ones, genetic expression programming (GEP) is used. GEP is a Genetic Algorithm that can be used in function finding. It is implemented in a commercial application which, after the appropriate input file and settings have been provided, performs the evolution of the individuals in the input file so that a good solution is found. The thesis is the first one in this new research line. </p><p>The aim has been not only reaching the desired estimation but also pave the way for further investigations.</p>

FIR filters are widely used nowadays, with applications from MP3 players, Hi-Fi systems, digital TVs, etc. to communication systems like wireless communication. They are implemented in DSPs and there are several trade-offs that make important to have an exact as possible estimation of the required filter order. In order to find a better estimation of the filter order than the existing ones, genetic expression programming (GEP) is used. GEP is a Genetic Algorithm that can be used in function finding. It is implemented in a commercial application which, after the appropriate input file and settings have been provided, performs the evolution of the individuals in the input file so that a good solution is found. The thesis is the first one in this new research line. The aim has been not only reaching the desired estimation but also pave the way for further investigations.

This thesis studies the application of a multi-objective niched Pareto genetic algorithm on the design optimization of an electric field mill sensor. The original sensor requires resonant operation. The objective of the algorithm presented is to optimize the geometry eliminating the need for resonant operation which can be difficult to maintain in the presence of an unpredictable changing environment. The algorithm evaluates each design using finite element simulations. A population of sensor designs is evolved towards an optimal Pareto frontier of solutions. Several candidate solutions are selected that offer superior displacement, frequency, and stress concentrations. These designs were modified for fabrication using the PolyMUMPs abrication process but failed to operate due to the process. In order to fabricate the sensors in-house with a silicon-on-glass process, an anodic bonding apparatus has been designed, built, and tested.

Non-rigid shapes are generally known as objects whose three dimensional geometry may deform by internal and/or external forces. Deformable shapes are all around us, ranging from protein molecules, to natural objects such as the trees in the forest or the fruits in our gardens, and even human bodies. Two deformable shapes may be related by isometry, which means their intrinsic geometries are preserved, even though their extrinsic geometries are dissimilar. An important problem in the analysis of the deformable shapes is to identify the three-dimensional correspondence between two isometric shapes, given that the two shapes may be deviated from isometry by intrinsic distortions. A major challenge is that non-rigid shapes have large degrees of freedom on how to deform. Nevertheless, irrespective of how they are deformed, they may be aligned such that the geodesic distance between two arbitrary points on two shapes are nearly equal. Such alignment may be expressed by a permutation matrix (a matrix with binary entries) that corresponds to every paired geodesic distance in between the two shapes. The alignment involves searching the space over all possible mappings (that is all the permutations) to locate the one that minimizes the amount of deviation from isometry. A brute-force search to locate the correspondence is not computationally feasible. This thesis introduces a novel approach created to locate such correspondences, in spite of the large solution space that encompasses all possible mappings and the presence of intrinsic distortion. In order to find correspondences between two shapes, the first step is to create a suitable descriptor to accurately describe the deformable shapes. To this end, we developed deformation-invariant metric descriptors. A descriptor constitutes pair-wise geodesic distances among arbitrary number of discrete points that represent the topology of the non-rigid shape. Our descriptor provides isometric-invariant representation of the shape irrespective of its circumstantial deformation. Two isometric-invariant descriptors, representing two candidate deformable shapes, are the input parameters to our optimization algorithm. We then proceed to locate the permutation matrix that aligns the two descriptors, that minimizes the deviation from isometry. Once we have developed such a descriptor, we turn our attention to finding correspondences between non deformable shapes. In this study, we investigate the use of both classical and quantum particle swarm optimization (PSO) algorithms for this task. To explore the merits of variants of PSO, integer optimization involving test functions with large dimensions were performed, and the results and the analysis suggest that quantum PSO is more effective optimization method than its classical PSO counterpart. Further, a scheme is proposed to structure the solution space, composed of permutation matrices, in lexicographic ordering. The search in the solution space is accordingly simplified to integer optimization to find the integer rank of the targeted permutation matrix. Empirical results suggest that this scheme improves the scalability of quantum PSO across large solution spaces. Yet, quantum PSO's global search capability requires assistance in order to more effectively manoeuvre through the local extrema prevalent in the large solution spaces. A mutation based genetic algorithm (GA) is employed to augment the search diversity of quantum PSO when/if the swarm stagnates among the local extrema. The mutation based GA instantly disengages the optimization engine from the local extrema in order to reorient the optimization energy to the trajectories that steer to the global extrema, or the targeted permutation matrix. Our resultant optimization algorithm combines quantum Particle Swarm Optimization (PSO) and mutation based Genetic Algorithm (GA). Empirical results show that the optimization method presented is scalable and efficient on standard hardware across different solution space sizes. The performance of the optimization method, in simulations and on various near-isometric shapes, is discussed. In all cases investigated, the method could successfully identify the correspondence among the non-rigid deformable shapes that were related by isometry.

This thesis studies the application of a multi-objective niched Pareto genetic algorithm on the design optimization of an electric field mill sensor. The original sensor requires resonant operation. The objective of the algorithm presented is to optimize the geometry eliminating the need for resonant operation which can be difficult to maintain in the presence of an unpredictable changing environment. The algorithm evaluates each design using finite element simulations. A population of sensor designs is evolved towards an optimal Pareto frontier of solutions. Several candidate solutions are selected that offer superior displacement, frequency, and stress concentrations. These designs were modified for fabrication using the PolyMUMPs abrication process but failed to operate due to the process. In order to fabricate the sensors in-house with a silicon-on-glass process, an anodic bonding apparatus has been designed, built, and tested.

The aim of this study is to introduce a real-world timetabling problem that exists in some private schools in Turkey and to solve such problem instances utilizing memetic algorithms. Being a new type of problem and for privacy reasons, there is no real data available. Hence for benchmarking purposes, a random data generator has been implemented. Memetic algorithms (MAs) combining genetic algorithms and hill-climbing are applied to solve synthetic problem instances produced by this generator. Different types of recombination and mutation operators based on the hierarchical structure of the timetabling problem are proposed. A modified version of the violation directed hierarchical hill-climbing method (VDHC), introduced by A. Alkan and E. Ozcan, coordinates the process of 12 different low-level hill-climbing operators grouped in two distinct arrangements that attempt to resolve corresponding constraint violations. VDHC is an adaptive method advocating cooperation of hill-climbing operators. In addition, MAs with VDHC are compared with different versions of multimeme algorithms and pure genetic algorithms. Experimental results on synthetic benchmark data set indicate the success of the proposed MA.

Evolvable Hardware is a technique derived from evolutionary computation applied to a hardware design. The term evolutionary computation involves similar steps as involved in the human evolution. It has been given names in accordance with the electronic technology like, Genetic Algorithm (GA), Evolutionary Strategy (ES) and Genetic Programming (GP). In evolutionary computing, a configured bit is considered as a human chromosome for a genetic algorithm, which has to be downloaded into hardware. Early evolvable hardware experiments were conducted in simulation and the only elite chromosome was downloaded to the hardware, which was labelled as Extrinsic Hardware. With the invent of Field Programmable Gate Arrays (FPGAs) and Reconfigurable Processing Units (RPUs), it is now possible for the implementation solutions to be fast enough to evaluate a real hardware circuit within an evolutionary computation framework; this is called an Intrinsic Evolvable Hardware. This research has been taken in continuation with project 'Evolvable Hardware' done at Manukau Institute of Technology (MIT). The project was able to manually evolve two simple electronic circuits of NAND and NOR gates in simulation. In relation to the project done at MIT this research focuses on the following: To automate the simulation by using In Circuit Debugging Emulators (IDEs), and to develop a strategy of configuring hardware like an FPGA without the use of their company supplied in circuit debugging emulators, so that the evolution of an intrinsic evolvable hardware could be controlled, and is hardware independent. As mentioned, the research conducted here was able to develop an evolvable hardware friendly Generic Structure which could be used for the development of evolvable hardware. The structure developed was hardware independent and was able to run on various FPGA hardware’s for the purpose of intrinsic evolution. The structure developed used few configuration bits as compared to current evolvable hardware designs.

This research presents various intelligent optimisation methods which are: genetic algorithm (GA), particle swarm optimisation (PSO), artificial bee colony algorithm (ABCA), firefly algorithm (FA) and bacterial foraging optimisation (BFO). It attempts to minimise analogue electronic filter and amplifier circuits, taking a cascode amplifier design as a case study, and utilising the above-mentioned intelligent optimisation algorithms with the aim of determining the best among them to be used. Small signal analysis (SSA) conversion of the cascode circuit is performed while mesh analysis is applied to transform the circuit to matrices form. Computer programmes are developed in Matlab using the above mentioned intelligent optimisation algorithms to minimise the cascode amplifier circuit. The objective function is based on input resistance, output resistance, power consumption, gain, upperfrequency band and lower frequency band. The cascode circuit result presented, applied the above-mentioned existing intelligent optimisation algorithms to optimise the same circuit and compared the techniques with the one using Nelder-Mead and the original circuit simulated in PSpice. Four circuit element types (resistors, capacitors, transistors and operational amplifier (op-amp)) are targeted using the optimisation techniques and subsequently compared to the initial circuit. The PSO based optimised result has proven to be best followed by that of GA optimised technique regarding power consumption reduction and frequency response. This work modifies symbolic circuit analysis in Matlab (MSCAM) tool which utilises Netlist from PSpice or from simulation to generate matrices. These matrices are used for optimisation or to compute circuit parameters. The tool is modified to handle both active and passive elements such as inductors, resistors, capacitors, transistors and op-amps. The transistors are transformed into SSA and op-amp use the SSA that is easy to implement in programming. Results are presented to illustrate the potential of the algorithm. Results are compared to PSpice simulation and the approach handled larger matrices dimensions compared to that of existing symbolic circuit analysis in Matlab tool (SCAM). The SCAM formed matrices by adding additional rows and columns due to how the algorithm was developed which takes more computer resources and limit its performance. Next to this, this work attempts to reduce component count in high-pass, low-pass, and all- pass active filters. Also, it uses a lower order filter to realise same results as higher order filter regarding frequency response curve. The optimisers applied are GA, PSO (the best two methods among them) and Nelder-Mead (the worst method) are used subsequently for the filters optimisation. The filters are converted into their SSA while nodal analysis is applied to transform the circuit to matrices form. High-pass, low-pass, and all- pass active filters results are presented to demonstrate the effectiveness of the technique. Results presented have shown that with a computer code, a lower order op-amp filter can be applied to realise the same results as that of a higher order one. Furthermore, PSO can realise the best results regarding frequency response for the three results, followed by GA whereas Nelder- Mead has the worst results. Furthermore, this research introduced genetic folding (GF), MSCAM, and automatically simulated Netlist into existing genetic programming (GP), which is a new contribution in this work, which enhances the development of independent Matlab toolbox for the evolution of passive and active filter circuits. The active filter circuit evolution especially when operational amplifier is involved as a component is of it first kind in circuit evolution. In the work, only one software package is used instead of combining PSpice and Matlab in electronic circuit simulation. This saves the elapsed time for moving the simulation between the two platforms and reduces the cost of subscription. The evolving circuit from GP using Matlab simulation is automatically transformed into a symbolic Netlist also by Matlab simulation. The Netlist is fed into MSCAM; where MSCAM uses it to generate matrices for the simulation. The matrices enhance frequency response analysis of low-pass, high-pass, band-pass, band-stop of active and passive filter circuits. After the circuit evolution using the developed GP, PSO is then applied to optimise some of the circuits. The algorithm is tested with twelve different circuits (five examples of the active filter, four examples of passive filter circuits and three examples of transistor amplifier circuits) and the results presented have shown that the algorithm is efficient regarding design.

The motif discovery problem is becoming increasingly important for molecular biologists as new sequencing technologies are producing large amounts of data, at rates which are unprecedented. The solution space for DNA motifs is too large to search with naive methods, meaning there is a need for fast and accurate motif detection tools. We propose MotifGP, a multiobjective motif discovery tool evolving regular expressions that characterize overrepresented motifs in a given input dataset. This thesis describes and evaluates a multiobjective strongly typed genetic programming algorithm for the discovery of network expressions in DNA sequences. Using 13 realistic data sets, we compare the results of our tool, MotifGP, to that of DREME, a state-of-art program. MotifGP outperforms DREME when the motifs to be sought are long, and the specificity is distributed over the length of the motif. For shorter motifs, the performance of MotifGP compares favourably with the state-of-the-art method. Finally, we discuss the advantages of multi-objective optimization in the context of this specific motif discovery problem.