Fitness function circuit

• US 6,185,547 B1
• Filed: 08/12/1997
• Issued: 02/06/2001
• Est. Priority Date: 11/19/1996
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Shackleford, J. Barry, Yasuda, Mitsuhiro, Okushi, Etsuko, Iwamoto, Takashi
• Primary Examiner(s): Hafiz, Tariq R.
• Assistant Examiner(s): PENDER JR, MICHAEL J
• Application Number:
  US08/909,830
• Time in Patent Office: 1,274 Days
• Field of Search: 706/13, 706/12, 706/14
• US Class Current: 706/13
• 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 fitness function circuit for computing a fitness value for a trial solution to a set covering problem accelerates the execution speed of a genetic algorithm provided with a matrix circuit for outputting a column signal covered by a row signal corresponding to a bit in a chromosome, a column signal counter for counting column signals, a subtractor for calculating a difference between a counted number of column signals and a number of all elements and outputting the difference as a number of uncovered elements, a carry-save-adder for outputting a number of valid row signals as a chromosome cost, an aggregate cost register for holding the number of uncovered elements as a more significant portion of a total cost and the chromosome cost as a less significant portion of the total cost and outputting the total cost, an inverter for inverting a value of the total cost and outputting an inverted value as a fitness value.

Claims

1. A fitness function circuit for an execution of a genetic algorithm (GA), said fitness function circuit inputting a chromosome having n bits and outputting a fitness value of the chromosome, said fitness function circuit comprising:

a hardware circuit for calculating a number of elements covered by the chromosome inputted, said chromosome selected from a population memory comprising a plurality of chromosomes, and calculating the fitness value of the chromosome based upon a calculated number of covered elements, such that all cromosomes in said population memory are evolved into legal solutions,

wherein said hardware circuit includes an aggregate cost calculator for calculating a total cost of the chromosome, said aggregate cost calculator including an aggregate cost register for concatenating and then retaining the number of uncovered elements as a more significant portion and the chromosome cost as a less significant portion and outputting a concatenated value as the total cost.

2. The fitness function circuit of claim 1, wherein said hardware circuit further includes

an inverter for inverting a value of the total cost and outputting an inverted value of the total cost as the fitness value of the chromosome.

3. The fitness function circuit of claim 2, wherein said aggregate cost calculator includes,

an uncovered element counter for counting a number of uncovered elements by the chromosome, and

a chromosome cost calculator for calculating a chromosome cost of the chromosome.

4. The fitness function circuit of claim 3, wherein the fitness value of the chromosome is calculated with the number of the uncovered elements prioritized over the chromosome cost.

5. The fitness finction circuit of claim 4, wherein said uncovered element counter includes a matrix circuit having a matrix of order n (rows) x e (columns), said matrix circuit inputting, to each of said rows, a row signal representing a bit in the n bits of the chromosome and outputting, from each of said columns, a column signal for distinguishing an element corresponding to the column between covered and uncovered by said row signals.

6. The fitness function circuit of claim 5, wherein said uncovered element counter further includes a column signal counter for inputting column signals outputted from said matrix circuit, counting a number of valid column signals, and outputting a counted number as the number of uncovered elements.

7. The fitness function circuit of claim 6, wherein said matrix circuit includes cross circuits for validating the column signal corresponding to an element covered by a bit in the chromosome corresponding to the row signal when the row signal is valid.

8. The fitness function circuit of claim 7, wherein said cross circuit validates the column signal by outputting a valid row signal as the column signal,

wherein the matrix circuit further includes OR gates coupled to the respective columns for inputting the column signals outputted by said cross circuits.

9. The fitness function circuit of claim 6, wherein said column signal counter includes a first carry-save-adder for inputting the column signals and counting a number of valid column signals.

10. The fitness function circuit of claim 9, wherein said column signal counter further includes a subtractor for calculating a difference between the number of valid column signals and a number of elements and outputting the number of uncovered elements.

11. The fitness function circuit of claim 10, wherein said chromosome cost calculator includes a second carry-save-adder for inputting the row signals and outputting a number of valid row signals.

12. The fitness finction circuit of claim 2, wherein said inverter outputs said fitness value by inverting each bit of said total cost.

13. The fitness function circuit of claim 1, wherein the fitness value is calculated as a solution to a set covering problem.

14. The fitness function circuit of claim 1, wherein said fitness function circuit is mounted on a GA machine for implementing a GA using the chromosome having n bits representing a potential problem solution,

wherein said GA machine includes,

said population memory for storing a population of chromosomes and respective fitness values,

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

a crossover module for performing a crossover operation on the parent chromosome and creating a child chromosome,

a mutation operator for mutating the child chromosome,

a mount wherein said fitness function circuit for evaluating a fitness of the mutated chromosome and outputting a fitness value, and

a survival comparator for determining a survival of the mutated chromosome based upon the fitness value,

wherein the population memory, selector, crossover module, mutation operator, and survival comparator are respectively implemented by general-purpose circuits which can be used for non-specific problems, and configures a framework of said GA machine through a hardware-based implementation,

wherein said GA machine becomes a problem-specific genetic algorithm machine when said fitness function circuit is mounted on said mount.

15. The fitness function circuit of claim 14, wherein said selector selects said parent chromosome at random from among all the chromosomes in the population memory.

16. The fitness function circuit of claim 14, wherein said crossover module comprises:

a crossover template generator for generating a base serial pattern of a crossover template;

a crossover template shift register for inputting the serial pattern, shifing the pattern bit by bit, and outputting an n-bit crossover template; and

at least one multiplexor for performing the crossover operation on the parent chromosome based upon the n-bit crossover template.

17. The fitness function circuit of claim 16, wherein said crossover module comprises a circuit for generating a cutpoint pattern in the crossover template in case of no cutpoints provided in the template.

18. The fitness function circuit of claim 14, wherein said mutation operator performs mutation on all bits in the child chromosome independently, probabilistically and in parallel with one another.

19. The fitness function circuit of claim 14, wherein said population memory stores parent chromosomes and surviving mutated chromosomes.

20. The fitness function circuit of claim 14, wherein said survivor comparator determines that a mutated chromosome will survive when it is more fit than a current least-fit chromosome, and wherein the surviving mutated chromosome is transferred into said population memory.

21. The fitness function circuit of claim 14, wherein said population memory, said selector, said crossover module, said mutation operator, said fitness function circuit, and said survival comparator are designed to operate in synchronization with a machine cycle to accelerate the execution speed of said GA machine.

22. A fitness function circuit for an execution of a genetic algorithm (GA), said fitness function circuit inputting a chromosome having n bits and outputting a fitness value of the chromosome, said fitness function circuit comprising:

a hardware circuit for calculating a number of elements covered by the chromosome inputted, and calculating the fitness value of the chromosome based upon a calculated number of covered elements, said hardware circuit including an aggregate cost calculator for calculating the fitness value of the chromosome and wherein said aggregate cost calculator includes

a chromosome cost calculator for calculating a chromosome cost of the chromosome;

an inverter for receiving an output from said chromosome cost calculator and outputting an inverted chromosome cost value; and

an aggregate cost register for concatenating and then retaining the number of covered elements as a more significant portion and the inverted chromosome cost value as a less significant portion and outputting a concatenated value as the fitness value.

23. The fitness function circuit of claim 22, wherein

said aggregate cost calculator further includes

a covered element counter for counting a number of covered elements by the chromosome.

24. The fitness function circuit of claim 23, wherein said covered element counter includes a matrix circuit having a matrix of order n (rows) x e (columns), said matrix circuit inputting, to each of said rows, a row signal representing a bit in the n bits of the chromosome and outputting, from each of said columns, a column signal for distinguishing an element corresponding to the column between covered and uncovered by said row signals.

25. The fitness function of claim 24, wherein said covered element counter further includes a column signal counter for inputting column signals outputted from said matrix circuit, counting a number of valid column signals, and outputting a counted number as the number of covered elements.

26. The fitness function of claim 25, wherein said column signal counter includes a first carry-save-adder for inputting the column signals and counting a number of valid column signals.

27. The fitness function of claim 26, wherein said chromosome cost calculator includes a second carry-save-adder for inputting the row signals and outputting a number of valid row signals.

28. The fitness function circuit of claim 22, wherein said fitness function circuit is mounted on a GA machine for implementing a GA using the chromosome having n bits representing a potential problem solution,

wherein said GA machine includes,

a population memory for storing a population of chromosomes and respective fitness values,

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

a crossover module for performing a crossover operation on the parent chromosome and creating a child chromosome,

a mutation operator for mutating the child chromosome,

a mount wherein said fitness finction circuit for evaluating a fitness of the mutated chromosome and outputting a fitness value, and

a survival comparator for determining a survival of the mutated chromosome based upon the fitness value,

wherein the population memory, selector, crossover module, mutation operator, and survival comparator are respectively implemented by general-purpose circuits which can be used for non-specific problems, and configures a framework of said GA machine through a hardware-based implementation,

wherein said GA machine becomes a problem-specific genetic algorithm machine when said fitness fuinction circuit is mounted on said mount.

29. A fitness function circuit for an execution of a genetic algorithm (GA), said fitness function circuit inputting a chromosome having n bits and outputting a fitness of the chromosome, said fitness function circuit comprising:

a hardware circuit, which assigns an even cost to each of the n bits, for counting a number of elements covered by the chromosome inputted, counting a number of valid bits of the n bits and deciding the fitness of the chromosome by inverting a counted number of covered elements and a counted number of valid bits,

wherein said hardware circuit includes an aggregate cost calculator for calculating a total cost of the chromosome, and said aggregate cost calculator includes

a chromosome cost calculator for calculating a chromosome cost of the chromosome;

an inverter for receiving an output from said chromosome cost calculator and outputting an inverted chromosome cost value; and

an aggregate cost register for concatenating and then retaining the number of covered elements as a more significant portion and the inverted chromosome cost value as a less significant portion and outputting a concatenated value as the fitness value.

30. A fitness function circuit for an execution of a genetic algorithm (GA), said fitness function circuit inputting a chromosome having n bits and outputting a fitness of the chromosome, said fitness function circuit comprising:

a hardware circuit for calculating a number of elements covered by the chromosome inputted, and calculating the fitness of the chromosome based upon a calculated number of covered elements,

wherein said hardware circuit includes an aggregate cost calculator for calculating a total cost of the chromosome, and said aggregate cost calculator includes

a chromosome cost calculator for calculating a chromosome cost of the chromosome;

an inverter for receiving an output from said chromosome cost calculator and outputting an inverted chromosome cost value; and

an aggregate cost register for concatenating and then retaining the number of covered elements as a more significant portion and the inverted chromosome cost value as a less significant portion and outputting a concatenated value as the fitness value and

wherein the hardware circuit is mounted on a mount to work with a non-problem-specific general purpose hardware circuit to form a problem-specific GA machine.

31. A fitness function circuit for an execution of a genetic algorithm (GA), said fitness function circuit inputting a chromosome having n bits and outputting a fitness value of the chromosome, said fitness function circuit comprising:

a hardware circuit for calculating a number of elements covered by the chromosome inputted, and calculating the fitness value of the chromosome based upon a calculated number of covered elements,

wherein said hardware circuit includes an aggregate cost calculator for calculating a total cost of the chromosome, and

wherein said aggregate cost calculator includes,

a covered element counter for counting a number of covered elements by the chromosome, and

a chromosome cost calculator for calculating a chromosome cost of the chromosome,

wherein said covered element counter includes a matrix circuit having a matrix of order n (rows) x e (columns), said matrix circuit inputting, to each of said rows, a row signal representing a bit in the n bits of the chromosome and outputting, from each of said columns, a column signal for distinguishing an element corresponding to the column between covered and uncovered by said row signals, and a column signal counter for inputting column signals outputted from said matrix circuit, counting a number of valid column signals, and outputting a counted number as the number of covered elements,

wherein said column signal counter includes a first carry-save-adder for inputting the column signals and counting a number of valid column signals,

wherein said chromosome cost calculator includes a second carry-save-adder for inputting the row signals and outputting a member of valid row signals, and

wherein said aggregate cost calculator includes

an inverter for receiving an output from said second carry-save-adder of said chromosome cost calculator and outputting an inverted chromosome cost value, and

an aggregate cost register for concatenating and then retaining the number of covered elements as a more significant portion and the inverted chromosome cost value as a less significant portion and outputting a concatenated value as the total cost.