Genetic algorithm machine and its production method, and method for executing a genetic algorithm

• US 5,970,487 A
• Filed: 08/13/1997
• Issued: 10/19/1999
• Est. Priority Date: 11/19/1996
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Corporation
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Iwamoto, Takashi, Shackleford, J. Barry, Yasuda, Mitsuhiro, Okushi, Etsuko
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/910,103
• Time in Patent Office: 797 Days
• Field of Search: 707/1-206, 706/1-62, 706/900-934
• US Class Current: 1/1
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

A multi-purpose non-problem-specific hardware-based framework for the execution of a genetic algorithm (GA) accelerates the execution speed of a GA through the implementation of hardware-based non-problem-specific functions of population memory, first and second chromosome registers, crossover module, mutation operator, and survival comparator. The non-problem-specific aspect of the hardware-based framework turns problem-specific without changing the contents of the framework once a problem-specific fitness function circuit is included for evaluating chromosomal data representing a potential problem solution. The hardware-based framework is thus applicable to a variety of problem-specific aspects of the problem-specific fitness function circuit.

Claims

1. A genetic algorithm (GA) machine for executing a GA using a chromosome representing a potential problem solution, said GA machine comprising:

a population memory for storing a population of chromosomes;

a selector for selecting a chromosome from among the chromosomes in the population as a parent chromosome;

a crossover module for inputting a plurality of parent chromosomes and performing a crossover operation on the plurality of parent chromosomes for creating a new chromosome and outputting the new chromosome as a child chromosome;

a mutation operator for inputting the child chromosome and mutating the child chromosome and generating a mutated chromosome;

a mount for mounting a fitness function circuit for evaluating a fitness of the mutated chromosome and outputting an evaluated value of the fitness of the mutated chromosome; and

a survival comparator for determining a survival of the mutated chromosome based upon the evaluated value.

2. The GA machine of claim 1, wherein said population memory, selector, crossover module, mutation operator, and survival comparator are non-problem-specific general-purpose hardware circuits to form a framework of a multi-purpose non-problem-specific GA machine.

3. The GA machine of claim 2, wherein the multi-purpose non-problem-specific GA machine turns into a problem-specific GA machine when a problem-specific fitness function circuit is mounted on said mount.

4. The GA machine of claim 3, wherein the fitness function circuit is implemented in a reconfigurable hardware circuit.

5. The GA machine of claim 4, wherein the reconfigurable hardware circuit includes a field-programmable gate array (FPGA).

6. The GA machine of claim 3, wherein said population memory, selector, crossover module, mutation operator, survival comparator and the fitness function circuit operate in synchronization with a common machine cycle.

7. The GA machine of claim 3, further comprising an initialization circuit for initializing said population memory by using at least a part of said mutation operator and a part of the evaluator circuit.

8. The GA machine of claim 7, wherein said initialization circuit generates a random bit pattern sequentially based upon an externally supplied parameter, evaluates the fitness of a random bit pattern, and then stores the bit pattern and the evaluated value of the fitness sequentially in said population memory.

9. The GA machine of claim 1, wherein said population memory stores both the parent and child chromosomes in an area of a single memory space.

10. The GA machine of claim 9, wherein said population memory replaces a less-fit chromosome in the population by a more-fit chromosome so that the more-fit chromosome has a longer lifetime in said population memory.

11. The GA machine of claim 10, further comprising:

an address pointer register for storing an address of a least-fit chromosome among parent chromosomes selected from among the chromosomes in said population memory after a replacement of one of the chromosomes of the population;

wherein said population memory replaces a chromosome located at the address stored in said address pointer register by the mutated chromosome.

12. The GA machine of claim 10, wherein said selector selects a chromosome at random without regard to the fitness.

13. The GA machine of claim 12, wherein said selector selects a plurality of chromosomes from among the chromosomes in the population memory as the parent chromosomes.

14. The GA machine of claim 9, wherein said selector includes a plurality of chromosome registers cascaded in series for passing a selected parent chromosome from one chromosome register to another, wherein each of said chromosome register having a storage capacity of one chromosome, wherein each of said chromosome register outputs a received parent chromosome in parallel to another chromosome register concurrently to said crossover module.

15. The GA machine of claim 10, further comprising:

an evaluated chromosome register for storing the evaluated value of the fitness and a corresponding chromosome, and

a least-fit value register for storing the evaluated value of the fitness of a least-fit parent chromosome among parent chromosomes selected by said selector,

wherein said survival comparator compares the evaluated values of the fitness in said evaluated chromosome register and least-fit value register and transfers the evaluated value of the fitness and the corresponding chromosome evaluated to said population memory for the replacement of the less-fit chromosome in the population based upon a compared result.

16. The GA machine of claim 1, wherein the chromosome includes n bits,

wherein said crossover module includes,

a template generator for generating a template including a pattern indicating a cutpoint,

a template shift register having a storage capacity of n bits, for inputting and then shifting the template and outputting bit values corresponding to the respective n bits in the chromosome, and

a multiplex operator for performing the crossover operation on the respective n bits in the chromosome, wherein each of the n bits processed in parallel to another bit, based upon the bit values at corresponding bit positions in the template shift register.

17. The GA machine of claim 16, wherein said multiplex operator includes a plurality of multiplexers, each multiplexer for inputting i-th (1≦

i≦

n) bits of a plurality of n-bit chromosomes, selecting one of the i-th bits based upon a bit value at an i-th bit position in said template shift register and outputting a selected i-th bit as an i-th bit of the child chromosome.

18. The GA machine of claim 17, wherein said crossover module requires log₂ q (decimals raised to the next whole number) number of template shift registers when performing the crossover operation on q (q≧

2) number of the parent chromosomes,

wherein said multiplexer inputs the i-th bits of the log₂ q (decimals raised to the next whole number) number of said template shift registers, and selects one of the i-th bits of the q(q≧

2) number of the parent chromosomes.

19. The GA machine of claim 16, wherein said template generator self-regulates probabilistically a cutpoint-indicating pattern generation based upon an externally supplied number of cutpoints.

20. The multi-purpose non-problem-specific GA machine of claim 19, wherein said template generator includes,

a counter for counting a number of patterns indicating a cutpoint in said template shift register and outputting a counted number,

a cutpoint-number comparator for comparing the counted number with the externally supplied number of cutpoints and outputting a cutpoint-number compared result,

a threshold-value counter for setting a threshold value for generating the pattern indicating a cutpoint based upon the cutpoint-number compared result,

a threshold-value comparator for comparing the threshold value with a random number and outputting a threshold-value compared result, and

a toggle flip-flop for generating the cutpoint-indicating pattern based upon the threshold-value compared result.

21. The GA machine of claim 20, wherein said template generator includes a pattern generator for generating the pattern indicating a cutpoint based upon the counted number of the patterns indicating a cutpoint.

22. The GA machine of claim 1, wherein the chromosome includes n bits,

wherein said mutation operator includes,

a mutation module for mutating each bit in an n-bit chromosome singly in parallel to another bit and outputting the mutated chromosome, and

a mutated chromosome register for loading each bit in the mutated chromosome in parallel to another bit.

23. The GA machine of claim 22, wherein said mutation operator further includes,

first and second random pulse stream generators for generating first and second pulse streams, respectively, each stream having a predetermined pulse density p based upon a random number,

an AND gate for ANDing the first and second pulse streams and generating a third pulse stream having a pulse density p², and

an XOR gate for XORing each bit of the third pulse stream with a corresponding bit in a n-bit chromosome.

24. The GA machine of claim 1, wherein said mount comprises a device for removably mounting a different fitness function circuit depending upon a problem to be solved.

25. The GA machine of claim 1, wherein said survival comparator compares the evaluated value with a fitness value of a least-fit parent chromosome in said population memory, and replaces a chromosome in the population memory corresponding to the least-fit parent chromosome with the mutated chromosome.

26. The GA machine of claim 1, wherein said selector selects the chromosome from among the chromosomes in the population as a parent chromosome based on a random selection, without regard to the evaluated value.

27. A method for manufacturing a genetic algorithm (GA) machine for executing a GA using a chromosome representing a potential problem solution, said method comprising the step of producing hardware-based population memory, selector, crossover module, mutation operator, and survival comparator which are designed to implement a GA.

28. A method for producing a genetic algorithm (GA) machine for executing a GA using a chromosome representing a potential problem solution, said method comprising the steps of:

producing at least one of population memory, selector, crossover module, mutation operator, and survival comparator formed as a multi-purpose non-problem-specific framework, and

producing a fitness function circuit for evaluating a problem-specific fitness of the chromosome, and mounting the fitness function circuit on the multi-purpose non-problem-specific framework so that the GA machine turns problem-specific.

29. A method for executing a genetic algorithm (GA) using a chromosome representing a potential problem solution in a GA machine provided with a population memory for storing a population of chromosomes along with corresponding values of a fitness, said method comprising the step of replacing a less-fit chromosome among the chromosomes stored in the population with a more-fit child chromosome created through an execution of the GA so that a more-fit chromosome has a longer lifetime in the population memory.

30. The method for executing a GA of claim 29, further comprising the steps of:

storing an address in the population memory of a least-fit chromosome among chromosomes selected after a replacement of the less-fit chromosome in the population, and

replacing a chromosome at the address in the population memory with a child chromosome.

31. The method for executing a GA of claim 29, further comprising the step of selecting a chromosome from among chromosomes in the population at random without regard to the fitness and outputting a parent chromosome.

32. A method for executing a genetic algorithm (GA) in a GA machine provided with a crossover module for creating a child chromosome through a crossover operation on a chromosome, said method comprising the step of probabilistically controlling a number of cutpoints on a chromosome used in the crossover operation based upon an externally supplied number of cutpoints.

33. The method for executing a GA of claim 32 further comprising the step of generating a cutpoint based upon a cutpoint number probabilistically generated in said probabilistically controlling step to guarantee that there is always at least one cutpoint.

34. A method for executing a genetic algorithm (GA) using a simulated chromosomal data representing a potential problem solution in a GA machine provided with a population memory for storing a population of chromosomes and corresponding values of a fitness and a fitness function circuit for evaluating the fitness of a chromosome, said method comprising the step of initializing the population memory,

wherein said initializing step including,

generating a random bit pattern sequentially based upon an externally supplied parameter,

evaluating the fitness of the random bit pattern and outputting an evaluated value, and

storing the evaluated value and the random bit pattern to the population memory.