Fitness function circuit

Details Fitness function circuit Fitness function circuit

1997-08-12

2001-02-06

Hafiz, Tariq R. (Department: 2762)

Data processing: artificial intelligence

Machine learning

Genetic algorithm and genetic programming system

C707S793000, C707S793000, C707S793000, C706S045000

Reexamination Certificate

active

06185547

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a genetic algorithm machine for executing genetic algorithms and more particularly, to a circuit to compute a problem-specific fitness of a chromosome applied specifically to a set covering problem or optimization problem.
2. Description of the Related Art
FIG. 32
shows a conceptual diagram of a conventional genetic algorithm.
Generic algorithms (hereinafter referred to by the initials, GA) were introduced in 1975 by John Holland as a method for finding an optimum solution to complicated problems. (John H. Holland, “Adaptation in Natural and Artificial Systems,” University of Michigan Press, 1975; Second edition: MIT Press, 1992.) For example, the GA is a useful method for finding optimum solutions to the Traveling Salesman Problem described by Grefenstette. In the GA, an emulated chromosomal data structure is initially designed to represent a candidate or trial solution. A plurality of n-bit chromosomes of that data structure are then randomly generated. A plurality of generated chromosomes are registered in groups or populations. A plurality of parent chromosomes are selected from this population of generated chromosomes according to a given algorithm. Each generated chromosome is assigned a unique problem-specific fitness which differs from other chromosomes in the population identifying a solution quality of the chromosome. The problem-specific fitness is expressed by a fitness value. Chromosomes are selected from the population of chromosomes in proportion to their fitness values with more-fit chromosomes having higher probability of being selected. When a pair of parent chromosomes are selected from the population, the parent chromosomes are combined with a probabilistically generated cutpoint. In the case of having no cutpoint generated, either of the parent chromosomes is simply copied to provide a new chromosome as a child chromosome. Thus, a child chromosome is created and outputted. The child chromosome therefore contains portions of each parent or the whole portion of a parent. The child chromosome is then mutated. The mutation is performed with a low probability. The mutation is performed through inversion of a bit in the child chromosome. A mutated child chromosome is then evaluated to be assigned its fitness value. An evaluated child chromosome along with its fitness value is stored as a member of the next generation in the population.
After repeated iteration of this process, the general fitness of chromosomes in the population improves. Thus, a solution to the problem emerges In the population. A solution to the problem is acquired with highly fit chromosomes concentrated in the population.
A major disadvantage of the conventional GA is that the GA is extremely slow in its execution speed when emulated by software on a conventional general-purpose computer.
Some proposals have been addressed for accelerating the processing speed of a GA. Graham, et al. has proposed a hardware implementation of the GA using the Splash
2
machine (Paul Graham and Brent Nelson, “A Hardware Genetic Algorithm for the Traveling Salesman Problem on Splash
2
” Field-Programmable Logic and Applications, ed. W. More and W. Luk, pp. 352-361, Springer, Oxford, 1995). A similar attempt of hardware implementation of a GA to accelerate the execution speed of the GA has been proposed by Sitkoff et al. (Nathan Sitkoff, Mike Wazlowski, Aaron Smith, and Harvey Silverman, “Implementing a Genetic Algorithm on a Parallel Custom Computing Machine, ”Proceedings of IEEE Workshop on FPGAs for Custom Computing Machines, pp. 180-187, 1995).
These attempts of the hardware implementation of a GA, however, ended in limited success with the speedup factors of roughly 10 times. One reason for their limited gains is copying the original GA proposed by Holland to be implemented on hardware. The original GA into the hardware implementation has thus inefficiencies introduced therein.
Another reason that greater speed gains are not realized is the underlying hardware architecture being used to implement the GA. Graham, et al. employs the Splash
2
machine which is a reconfigurable computer designed to support linear systolic data such as SIMD (single instruction, multiple data) and MIMD (multiple instruction, multiple data).
Sitkoff, et al. employs the Armstrong
3
machine which is a loosely-coupled MIMD multicomputer with reconfigurable computing capabilities. They achieved only limited gains because they implemented GAs in machines whose hardware architectures are not designed originally or particularly to implement the GAs. This can prevent the execution speed of GAs from achieving satisfactory gains.
A set covering problem is a problem to be solved by an applied form of a GA. The set covering problem is a non-deterministic polynomial hard (NP-hard) problem to be solved through a resource selection from among many resources. The applied form of a GA to the set covering problem minimizes the hardware architecture of a logic circuit, for example, with a resultant optimum solution. The set covering problem may be defined as follows.
“Given a collection C of finite sets, each with non-negative cost, find a minimum-cost sub-collection C′ such that every elements are covered by the respective sets of collection C belongs to at least one set in sub-collection C′.”
A set covering problem is now described with reference to
FIGS. 33 through 35
.
FIG. 33
shows a simplified diagram of a manufacturing process of DRAM (Direct Random Access Memory) chips composed of DRAM manufacturing line and DRAM test line.
FIG. 34
shows a partial graph of a failure log illustrating a DRAM testing result of DRAM chips
1
through
5000
by test types
1
through
70
, with each one of 5000 DRAM chips tested through the respective 70 tests. Each test requires certain time for execution and cost including test devices, etc. A typical cost required for DRAM testing amounts as much as some 20 per-cent of the whole DRAM manufacturing cost. In the case of 70 test types for each of 5000 DRAM chips of
FIG. 34
, a 20 per-cent increase in the whole manufacturing cost of DRAM chips is large and therefore reduction in the number of execution of tests is a vital challenge for lowering of DRAM cost if removing one test can save some 150 hundred thousand dollars for example. The set covering problem is an effective tool for this challenge. In this case, the set covering problem is a problem of finding a minimum-sized test set through which provides the same failure log as that through the practical operation of the whole 70 tests on each chip. Thus, the set covering problem finds a minimum-sized combination of test set which can detect or cover all failed chips.
FIG. 35
shows a graph of a simplified failure log illustrating the set covering problem further in detail. The simplified failure log, having DRAM chips
1
through
8
detected all as failed through tests
1
through
7
, illustrates the minimum-sized combination of test set which can cover all failed chips. Four tests (tests
1
,
2
,
5
, and
6
) is enough for detecting all the failed DRAM chips
1
through
8
and thus three out of seven tests can be saved. The set covering problem can be explained as follows with reference to this example.
A collection C of finite sets indicates tests
1
through
7
, each with non-negative cost. It may be desirable to assign a test an actual cost required for the test in a practical sense, but it is assumed here that all tests have the same cost of +1 each. Now, find a minimum-cost sub-collection such that every one of the failed chips
1
through
8
detected or covered by the tests
1
through
7
belongs to at least one test in the sub-collection. In this case, the sub-collection includes tests
1
,
2
,
5
, and
6
with the minimum-cost
4
.
The set covering problem can be solved through a optimum solution finding approach using a GA. This approach aims at attaining an optimum solution through a screening process of candidate o

Affiliated with

Also associated with

Rating

Fitness function circuit does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Fitness function circuit, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fitness function circuit will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2583687