This paper proposes a novel solution for the Traveling Salesman Problem, a NP (non-deterministic polynomial-time) hardness problem. The algorithm presented in this paper offers an innovative solution by combining the qualities of a Nearest Neighbor (NN) greedy algorithm and the Genetic Algorithm (GA), by overcoming their weaknesses. The paper analyses the algorithm features/improvements and presents this implementation on a FPGA based target board. The experimental results of the algorithm, tested in software (Matlab) and implemented on a portable hardware (FPGA for GA, Raspberry Pi 3 for NN) shows a significant improvement: a shorter route, compared to NN , a shorter running time (less generations) compared to traditional GA , and reaching the optimal minimum (validated by Matlab). In real time, the algorithm runs on a handheld console, which can also act as a server, through a custom Android client application.
To solve problems when an analytical solution is not available, more and more bio-inspired
computation techniques have been applied in the last years.
Thus, an efficient algorithm is the Genetic Algorithm (GA), which imitates the biological evolution
process, finding the solution by the mechanism of “natural selection”, where the strong has higher
chances to survive. A genetic algorithm is an iterative procedure which operates on a population of
individuals called "chromosomes" or "possible solutions" (usually represented by a binary code). GA
performs several processes with the population individuals to produce a new population, like in the
To provide a high speed solution, pipelined based FPGA hardware implementations are used, with a nstages
pipeline for a n-phases genetic algorithm.
The FPGA pipeline implementations are constraints by the different execution time of each stage and
by the FPGA chip resources.
To minimize these difficulties, we propose a bio-inspired technique to modify the crossover step by
using non identical twins. Thus two of the chosen chromosomes (parents) will build up two new
chromosomes (children) not only one as in classical GA.
We analyze the contribution of this method to reduce the execution time in the asynchronous and
synchronous pipelines and also the possibility to a cheaper FPGA implementation, by using smaller
populations. The full hardware architecture for a FPGA implementation to our target ALTERA
development card is presented and analyzed.
With the evolution of digital data storage and exchange, it is essential to protect the confidential information from every
unauthorized access. High performance encryption algorithms were developed and implemented by software and
hardware. Also many methods to attack the cipher text were developed. In the last years, the genetic algorithm has
gained much interest in cryptanalysis of cipher texts and also in encryption ciphers. This paper analyses the possibility to
use the genetic algorithm as a multiple key sequence generator for an AES (Advanced Encryption Standard)
cryptographic system, and also to use a three stages pipeline (with four main blocks: Input data, AES Core, Key
generator, Output data) to provide a fast encryption and storage/transmission of a large amount of data.
We propose an Eye Tracker/Display system, based on a novel, dual function device termed ETD, which allows sharing
the optical paths of the Eye tracker and the display and on-chip processing. The proposed ETD design is based on a
CMOS chip combining a Liquid-Crystal-on-Silicon (LCoS) micro-display technology with near infrared (NIR) Active
Pixel Sensor imager. The ET operation allows capturing the Near IR (NIR) light, back-reflected from the eye's retina.
The retinal image is then used for the detection of the current direction of eye's gaze.
The design of the eye tracking imager is based on the "deep p-well" pixel technology, providing low crosstalk while
shielding the active pixel circuitry, which serves the imaging and the display drivers, from the photo charges generated
in the substrate. The use of the ETD in the HMD Design enables a very compact design suitable for Smart Goggle
applications. A preliminary optical, electronic and digital design of the goggle and its associated ETD chip and digital
control, are presented.
In this presentation, several options for implementing an Image Transceiver System operating in real time are analyzed.
These include: the implementation of a multi chip system (including Display, Imager and Controller/Processor chips)
versus a single chip embedded system. The logical and physical aspects of a single chip, two chip- and three chip-implementation
are analyzed. The parallel and serial data transfer methods are analyzed for each case.
System architecture has a significant impact on software performance. In this manuscript, a method to increase the performance of the microprocessors and FPGA based systems using pipeline processing, is presented. An improved implementation using this concept, for image and display processing, providing real time vision applications, is described.