Adaptive computing system

• US 4,961,152 A
• Filed: 06/10/1988
• Issued: 10/02/1990
• Est. Priority Date: 06/10/1988
• Status: Expired due to Term

• Current Assignee: BBN Technologies Corporation (Rtx Corporation)
• Original Assignee: Bolt Beranek & Newman, Inc. (Verizon Communications Inc.)
• Inventors: Davis, Lawrence
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): GORDON, PAUL P
• Application Number:
  US07/205,154
• Time in Patent Office: 844 Days
• Field of Search: 364/513, 364/200 MS File, 364/274, 364/221.1, 364/900 MS File, 364/916, 364/972, 382/14, 382/15, 365/49
• US Class Current: 706/13
• CPC Class Codes: G06F 18/2111 by using evolutionary computational techniques, e.g. genetic algorithms
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming

Abstract

The adaptive computing system disclosed herein employs a data structure involving a multiplicity of classifiers, each of which includes a match string of characters which the system attempts to match up with messages generated either by the environment or by other classifiers. Associated with each match string is a response message definer or action part which defines the response to be given when a match is obtained. To facilitate matching in a noisy or changing environment, there is associated with each character in the match string a weighting value and the degree of match is judged by means of a score value which is a function of the weighting values of the characters which match between the match string and the message.

Claims

1. A method of generating responses to a source of an input signal comprising a succession of messages, said source providing a reinforcement signal for good responses, said method comprising:

initially generating a population of classifiers, each classifier comprising;

a match string;

for each character in the match string, a weighting value;

a response message definer; and

a strength value for the classifier;

for successive input signal messages performing the steps of;

comparing the match string of each classifier to each successive input signal message provided by the source and generating a corresponding score value which is a function of the weighting values of the matching characters;

comparing the score values generated by the different classifiers;

outputting respective response messages for classifiers selected stochastically on a basis favoring those classifiers having the better scores; and

modifying, as a function of a received reinforcement signal, the strength values for classifiers whose response messages were appropriate.

2. A method as set forth in claim 1 further comprising applying genetic operations to generate new classifiers based upon the modification of selectd ones of said match strings and selected sets of weighting values.

3. A method as set forth in claim 2 wherein said genetic operation comprises a crossover operation in which a new classifier has some weights taken from one pre-existing classifier and other weights taken from another pre-existing classifier.

4. A method as set forth in claim 2 wherein said genetic operation comprises a crossover operation in which a new classifier has some characters and associated weights taken from one pre-existing classifier and other characters and associated weights taken from another pre-existing classifier.

5. A method as set forth in claim 2 wherin a pair of classifiers are selected for combining, the selection being based on a distance between the classifiers which is calculated as a function of the weighting values associated with the matching and non-matching characters in each pair considered.

6. A method of generating responses to a source of a binary encoded input signal comprising a successive of messages, said source providing a reinforcement signal for good responses, said method comprising:

initially generating a population of classifiers, each classifier comprising;

a binary encoded match string of bits;

for each bit in the match string, a weighting value;

a binary encoded response message definer; and

a strength value for the classifier;

for successive input signal messages performing the steps of;

comparing the match string of each classifier to each successive input signal message provided by the source and generating a corresponding score value which is a function of the weighting values of the matching bits;

comparing the score values generated by the different classifiers;

outputting respective response messages for classifiers selected stochasically on a basis favoring those classifiers having the better scores;

modifying, as a function of a received reinforcement signal, the strength values for classifiers whose response messages were appropriate; and

periodically applying genetic operations to generate new classifiers based upon the modification of selected ones of said match strings and selected sets of weighting values, the selection process including a randomizing component and a component based on the respective strength values of the classifiers.

7. A method as set forth in claim 6 wherein the response messages are binary encoded strings equal in length to the match strings.

8. A method as set forth in claim 7 wherin, between successive input signal messages, a succession of cycles are performed in which the match strings of all classifiers are compared to the response messages which were output during previous cycles.

9. A method as set forth in claim 6 wherein said genetic operation comprises a crossover operation in which a new classifier has some bits and associated weights taken from one pre-existing classifier and other bits and associated weights taken from another pre-existing classifier.

10. A method as set forth in claim 9 wherein a pair of classifiers are selected for crossover, the selection being based on a distance between the classifiers which is calculated as a function of the weighting values associated with the matching and non-matching bits in each pair considered.