How Does an LCS work?

An LCS is a variable architecture learning system, which uses a genetic algorithm (GA) to occasionally change its operating principles (rules) to improve its performance. The LCS obtains information about its environment from the detectors, and maps those inputs onto the rule conditions. The rules whose conditions match the detector’s state are then considered for action.

Traditional LCSs use discrete actions, that is to say, actions are selected from the set of all available actions to the LCS. Actions are selected relative to a rule’s merit. Rules use their merit to bid for the right to take action. The final action is selected based on merit, originally termed strength. Modern LCSs, like Wilson’s XCS (1995), use metrics based on rule accuracy, rule confidence, or consensus (Wilson, 1994; Wilson, 1995; Smith & Cribbs, 1994).

The final action is determined via competition of all matching rules. The subset of rules advocating the same action with the highest combined merit is generally selected. Many action selection schemes have been developed, but most use a form of noisy auction. Noise is added to the bids (cumulative merit) to allow for exploration of the action space by stochastically selecting rules early on and slowly degrading the noise level. One method of doing this is to key the noise level to a Boltzmann distribution,

that decays as time progresses. Equation 16.1 represents the probability of action, a_i being selected based on its merit, m_i, in light of all the possible actions available for this time step.

The Predominant Components of an LCS

No matter what “flavor” of LCS, there are similarities. For instance, rules are necessary, and some form of rule discovery mechanism is required. In addition to these two items, facilities for credit assignment and conflict resolution are needed. A simple glossary of LCS terms and components follows.

LCS Terms and Components:

•  Conditions - The circumstances under which a rule becomes active. Rules whose conditions match the state of the environment provided by the detectors are said to have fired.

•  Actions - The method the LCS uses to affect its environmental state.

•  Detector - The sensor interpreter that determines the environmental state to match against the rule’s conditions.

•  Effectors - Effectors interact with the environment according to the selected action.

•  Rule Set - The set of all rules within the LCS, it can be thought of as the sum total of all knowledge the LCS has learned through interacting with its environment.

•  Match Set - The set of all rules whose conditions match the current values of the detectors.

•  Action Set - The subset of rules from the match set that is selected for action.

•  Action Selection Mechanism - The method used to select the action out of the rules in the match set.

•  Credit Assignment Mechanism - The facility that updates the rules’ merit ratings based on feedback from the environment.

•  Conflict Resolution Mechanism - When conflicting actions of equal merit are presented, this mechanism breaks the tie.

•  Rule Discovery Mechanism - Method for discovering new (better) rules for the LCS.

A GA is used due to its global search properties and theoretically backed efficiency for processing (schema) information. Other methods, such as genetic programming (GP) have been used (Koza, 1992; Tufts, 1995). The possibility exists for other evolutionary methods to be used, although no other evolutionary methods have appeared in the LCS literature. The evolutionary approach to rule discovery is considered by some researchers to be the defining element of the LCS.

LCS Operational Cycle

The LCS starts by encoding its perceived state in the environment via its detectors. The detectors encode the state of the environment for the rules to be matched against. The matching rules form the match-set. Action selection takes the match-set and determines the winning action. Basing selection on a proportion of an action’s cumulative merit, a stochastic action selection method may be used. Such a method was presented in Equation 16.1. The effectors perform the selected action. Credit assignment takes any available feedback from the environment and updates the merit ratings of the participating rules. The GA takes the rule-set(s) and modifies the rules by deleting inferior rules (or rule-sets). The GA also spawns new rules from highly fit rules, or rule-sets. GA activation may be periodic or triggered.¹ This process of natural selection is based on accumulated knowledge (fitness information) about the overall performance (accuracy) of the rules or rule-set. The process then repeats.

---

¹Periodic GA operation is the simplest form. If the system has a way to signal the GA to search for new rules then the GA may be triggered anytime the system generates the signal.

---