Author Topic: Implementation of Generic Algorithm Using VHDL on FPGA  (Read 2177 times)

0 Members and 1 Guest are viewing this topic.

IJSER Content Writer

  • Sr. Member
  • ****
  • Posts: 327
  • Karma: +0/-1
    • View Profile
Implementation of Generic Algorithm Using VHDL on FPGA
« on: September 20, 2011, 07:40:52 am »
Author : Prashant Sen, Priyanka Pateriya
International Journal of Scientific & Engineering Research Volume 2, Issue 9, September-2011
ISSN 2229-5518
Download Full Paper : PDF

Abstract— Architecture. The development of a flexible very-large-scale integration (VLSI) for GA has been proposed in this paper. For the hardware architecture, we has develop on a random number generator (RNG), crossover, and mutation based on flexibility structure. This structure can dynamically perform to the 3 types chromosome encoding: binary encoding, real-value encoding, and integer encoding. The overall structures has been designed and synthesized by VHDL (VHSIC hardware description language), simulation by ModelSim program, and then implemented on FPGAs (Field programmable gate arrays). This hardware architecture that our design work very well flexible for the 3 groups problem examples: combinatorial optimization problems, function optimal problems.

1   INTRODUCTION                                                                      
Genetic algorithms (GA) are techniques used to find exact or approximate solutions to optimization and search problems its algorithmic structure is simple. In Figure 1 each of the block modules performs a simple operation: (i) the fitness module performs the evaluation of the chromosome, (ii) the sequencer module randomly selects the chromosomes, i.e. an aspect of the model under study, and passes them to the selection module, (iii) the selection module decides which of the sequenced module should advance, and (iv) the mutation and crossover modules mutate and mate the selected chromosomes. The need for hardware implementation of GAs arises from the vast computational complexity of problems that cause delays in the optimization process of software implementations. The speed advantage of hardware and its ability to parallelize, offer great advantages to genetic algorithms to overcome those problems. Speedups of 1 to 3 orders of magnitude were achieved when frequently used software routines were implemented in hardware with Field Programmable Gate Arrays (FPGAs). However, those implementations were focusing on solving one specific problem due to the hardware resources constraints This paper is organized as follows. Section II,describes basics of GA and classification of the chromosomes encoding. Section III, proposed GA hardware architectures. Section IV, discusses the simulation result. Section V, is conclusion

II Generic Algrithm
A. The Basics of GA
In general, the step of GA operations consists of 6 main steps: population initialization, fitness calculation, selection, crossover, mutation and termination judgment, is shown in Fig.2. In the beginning, the initial population of a GA is generated randomly. Then, the evaluation values of the fitness function for the individuals in the current population are calculated. And then, the 3 steps of GA operators: selection, crossover, and mutation are performed. Finally, the termination criterion is checked, and the whole GA procedure stops if the termination criterion is reached. Our design and develop hardware in the GA process conclude RNG operation, crossover operation, and mutation operation.
B. Classifications of the Chromosome Encodings
In this paper, we have classified the chromosome encoding according to the most prefer are 3 types compose of: binary encoding, real-value encoding, and integer encoding, that can describe are as follow:

1) Binary encoding: In binary encoding, every chromosome is a string of bits only ‘0’ and ‘1’. For example “[11001110], [11100101]”

Crossover operation: Used in selection of the genes from par-ent chromosomes and creates a new issue. The simplest way how to do this is to choose randomly some crossover point and everything before this point copy from a first parent and then everything after a crossover point copy from the second parent.

Mutation operation: After crossover performed, mutation take place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new issue. Which, can switch a few randomly chosen bits from ‘1’ to ‘0’ or from ‘0’ to ‘1’. For example “[ 1 1 0 1 0 1 1 ] => [ 1 1 1 1 0 1 0 ]”

2) Real-value encoding: Is the best used for function optimization problem. It has been widely confirmed that real value encoding performs better than binary encoding. In a real value encoding, every chromosome is a string of some value. The values can be anything connected to problem, from numbers, real numbers. For example “[1.23 2.47 3.21], [ABCDEF], [(right), (left)]”

Crossover operation: All crossovers from binary encoding can be used.

Mutation operation: Adding a small number to selected values is added (or subtracted). For example “(6 2.86 4.11 5.47) => (6 2.73 4.22 5.47)”

3) Integer encoding: In integer encoding, every chromosome is a string of numbers, which represents number in a sequence. For example “[1 5 8 3 2 4 6 3 10], [10 2 5 9 6 4 1 3 8]”
Crossover operation: One-point crossover is selected, till this point the integer is copied from the first parent, then the sec-ond parent is scanned and if the number is not yet in the offspring it is added. For example “(1 2 3 4 5 6 7 8 9), (4 5 3 6 8 9 7 2 1) => (1 2 3 4 5 6 8 9 7)”
Mutation operation: Order changing, two numbers are se-lected and exchanged. For example “(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)”
A basic idea in this work is to implement the hardware architectures of RNG ( random number generation), crossover, and mutation. Because the 3 architecture are depend on the encoding operation. Difference encoding operation requires difference crossover and mutation. So, this hardware architecture design based on flexibility to the 3 types encoding for working together at a time. However the main drawbacks of hardware design are difference operation of crossover and mutation in each encoding. The main process of 3 hardware architecture are the users can choose any one of 3 type encoding according to the requirement of various GA applications, is shown in Fig 3.

In this paper, we have design and develop the 3 hardware architecture of the GA process, that concluding: random number generator module, crossover module, and mutation module, are as follow:

A. Random Number Generator Module
We have to take advantage of linear feedback shift register (LFSR) for random number generated. The operation of LFSR are generated by D flip-flop, is show in Fig. 4. And a first bit (X0) to take XOR with a last-bit (Xn) represent feedback, that is repeat process many time. as following the equation (1).
X0(n +1) = Xn(n) + X0(n)…………………. (1)
When X0(n +1) represent as data bit 0 at clock time (n +1), X0(n) represent as data bit 0 at clock time (n), and Xn(n) represent as data bit n at clock time (n).

Read More: Click here...