Use of a genetic algorithm to optimize memory space

• US 5,651,099 A
• Filed: 01/26/1995
• Issued: 07/22/1997
• Est. Priority Date: 01/26/1995
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Konsella, Shane
• Primary Examiner(s): Downs, Robert
• Assistant Examiner(s): SMITH, JEFFREY S
• Application Number:
  US08/378,329
• Time in Patent Office: 908 Days
• Field of Search: 395/13, 341/51, 341/79
• US Class Current: 706/13
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

The present invention is accomplished by first initializing a plurality of individuals. A trie is constructed for each individual, where the trie represents the original data. The trie comprises a root node, a plurality of sub-nodes and sub-arrays in a hierarchical arrangement. The individual indicates the number of the sub-nodes, sub-arrays and number of entries in each sub-array. Within a trie, delete any sub-array which contains redundant data and remove any of sub-node which contains redundant data. Apply an overlapping reduction function to the trie. With the trie constructed, determine the size for the trie and associate the size to the individual. Select a mating population based on trie size. Choose and perform at least one operation for the mating population, where the operation is the operations of crossover or mutation. For crossover, create at least one new individual by recombining the "genes" of at least two individual from the mating population. Then, add the new individual to the plurality of individuals. For mutation, mutate an individual by stochastically changing a property of the individual, then place the mutated individual in the plurality of individuals. Iterate for a predefined number of generations. Finally, keep in memory the trie with the smallest size.

Claims

1. A method for storing original data in a computer memory, said method comprising the steps of:

picking a number of generations;

initializing a plurality of individuals;

for each individual, determining a size for a trie symbolized by said each individual where said trie represents said original data;

selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual'"'"'s trie size;

choosing and performing at least one operation for said mating population, where said operation is the operation of crossover;

said operation of crossover comprising creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals;

iteratively doing said steps of determining, selecting, and choosing and performing for said number of generations times; and

keeping in memory the trie having minimum said size.

2. The method as described in claim 1 wherein said step of selecting comprising:

defining said mating population as having a plurality of individuals, said number of individuals in said mating population equals the number of individuals in said plurality of individuals;

copying individuals from said plurality of individuals to said mating population where probability of being copied is inversely related to said individual'"'"'s trie size; and

deleting all individuals in said plurality of individuals.

3. The method as described in claim 1 wherein said individual is a binary number with N number of bits set to a first value, said step of crossover occurs by exchanging first value bits between said at least two individuals.

4. The method as described in claim 1 wherein said step of initializing randomly generates said plurality of individuals.

5. The method as described in claim 2 wherein said step of choosing and performing further comprising an operation of mutation, if said chosen operation is mutation, mutating said individual by stochastically changing a property of said individual, placing said mutated individual in said plurality of individuals.

6. The method as described in claim 5 wherein said individual is a binary number with N number of bits set to a first value, said step of changing a property modifies said binary number.

7. The method as described in claim 1 wherein said step of determining comprising the steps of:

creating a root node, a plurality of sub-nodes, and a plurality of sub-arrays in a hierarchical arrangement, said individual indicates a number of said sub-nodes and said sub-arrays, and a number of entries in said sub-array;

deleting any of said plurality of sub-arrays which contain redundant data;

removing any of said plurality of sub-nodes which contain redundant data; and

applying overlapping reduction function.

8. The method as described in claim 7 wherein each of sub-array having a head and a tail, said step of applying overlapping reduction function comprising the steps of:

first finding overlappable entries in said tail for each of said entries in said sub-array;

second finding overlappable entries in said head for each of said entries in said sub-array; and

matching said overlappable entries in said tail with said overlappable entries in said head.

9. The method as described in claim 8 wherein said individual is a binary number with N number of bits set to a first value, said step of creating further comprising the step of linking said root with said plurality of sub-nodes and said sub-arrays to form a modified hybrid multiway radix search tree, said root and said plurality of sub-nodes arranged in N levels.

10. A method for storing original data in a minimum amount of computer memory, said method comprising the steps of:

picking a number of generations;

initializing a plurality of individuals;

for each individual;

constructing a trie, where said trie represents said original data, said trie comprising a root node, a plurality of sub-nodes, and a plurality of sub-arrays in a hierarchical arrangement, said individual indicates a number of said sub-nodes and said sub-arrays, and a number of entries in said sub-array;

deleting any of said plurality of sub-arrays which contain redundant data;

removing any of said plurality of sub-nodes which contain redundant data;

applying overlapping reduction function to said trie;

determining a size for said trie;

associating said size to said individual;

selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual'"'"'s trie size;

choosing and performing at least one operation for said mating population, where said operation is the operations of crossover or mutation;

if said chosen operation is crossover, creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals;

if said chosen operation is mutation, mutating an individual in said mating population by stochastically changing a property of said individual, placing said mutated individual into said plurality of individuals;

iteratively performing steps for said number of generations times; and

keeping in said memory the trie having minimum said size.

11. The method as described in claim 10 wherein said step of selecting comprising:

defining said mating population as having a plurality of individuals, said number of individuals in said mating population equals the number of individuals in said plurality of individuals;

copying individuals from said plurality of individuals to said mating population where probability of being copied is inversely related to said individual'"'"'s trie size; and

deleting all individuals in said plurality of individuals.

12. The method as described in claim 10 wherein each of sub-array having a head and a tail, said step of applying overlapping reduction function comprising the steps of:

first finding overlappable entries in said tail for each of said entries in said sub-array;

second finding overlappable entries in said head for each of said entries in said sub-array; and

matching said overlappable entries in said tail with said overlappable entries in said head.

13. The method as described in claim 10 wherein said individual is a binary number with N number of bits set to a first value, said step of crossover occurs by exchanging first value bits between said at least two individuals, said step of changing a property modifies said binary number, said step of constructing further comprising the step of linking said root with said plurality of sub-nodes and said sub-arrays to form a modified hybrid multiway radix search tree, said root and said plurality of sub-nodes arranged in N levels.

14. A computer system that stores an original data comprising:

a memory in which a plurality of individuals are stored;

a processor coupled to said memory, said processor executes a sequence of instruction;

means for determining a size of a trie symbolized by each individual where said trie represents said original data, said means for determining coupled to said processor;

means for selecting a mating population from said plurality of individuals where probability of selection for an individual is inversely proportionate to said individual'"'"'s trie size;

means for choosing and performing an operation for said mating population, where said operation is the operation of crossover, said means for choosing and performing coupled to said processor;

means for performing said operation of crossover comprising creating at least one new individual by crossover using at least two individuals from said mating population, adding said new individual to said plurality of individuals; and

means for keeping in memory the trie having minimum said size, said means for keeping coupled to said processor.

15. The computer system of claim 14 wherein said means for selecting further comprising:

means for defining said mating population as having a plurality of individuals, said number of individuals in said mating population equals the number of individuals in said plurality of individuals;

means for copying individuals from said plurality of individuals to said mating population where probability of being copied is inversely related to said individual'"'"'s trie size; and

means for deleting all individuals in said plurality of individuals.

16. The computer system of claim 14 wherein said means for choosing and performing an operation further comprising an operation of mutation, said computer system further comprising means for performing said operation of mutation comprising stochastically changing a property of said individual, placing said mutated individual back into said plurality of individuals.

17. The computer system of claim 16 wherein said individual is a binary number with N number of bits set to a first value, said changing a property modifies said binary number.

18. The computer system of claim 14, said trie comprising:

a root node having at least two pointers; and

at least two sub-arrays linked to said root node through said at least two pointers in a hierarchical arrangement, said at least two sub-arrays each having a plurality of entries in which said original data is stored.

19. The computer system of claim 18, said trie further comprising:

a plurality of sub-nodes located between said root node and said sub-arrays, said root linked with said plurality of sub-nodes and said sub-arrays to form a modified hybrid multiway radix search tree.

20. The computer system of claim 19 wherein said means for determining a size further comprising:

means for deleting any of said plurality of sub-arrays which contain redundant data;

means for removing any of said plurality of sub-nodes which contain redundant data;

means for applying overlapping reduction function; and

means for counting the amount of said memory necessary to store the trie.