Multiobjective Genetic Algorithm

To deal with the multi-objective association rule problem, we develop a specific GA [22], as GAs have been widely used to solve multi-objective optimization problems and have been applied with success to mono-objective rule mining problems [23]. We adopt a "A posteriori" approach while looking for all the solutions of best compromise between criteria. We expose the main features of the proposed GA scheme for association rules problem (encoding, mutation, and crossover operators) and its multi-objective aspects (archive of Pareto solutions, ranking, and management of the population).

13.4.1 General Scheme

GAs are inspired from Darwin's theory of evolution. By simulating nature evolution and emulating biological selection and reproduction techniques, a GA can solve complex problems in a strong search domain.

The algorithm starts with a set of randomly generated solutions (population). The population size remains constant throughout the GA. At each iteration, solutions are selected, according to their fitness quality to form new solutions (offspring). Offspring are generated through a reproduction process (crossover and mutation).

As in a multi-objective optimization, we are looking for all the solutions of best compromise, best solutions encountered over generations are filed into a secondary population called the "Pareto archive." In the production process, solutions can be selected also from "Pareto archive," this mechanism is called "elitism." A part of the offspring solutions replace their parents according to the replacement strategy.

Figure 13.2 presents the multi-objective GA scheme.

13.4.2 Operators for Association Rules

Crossover and mutation operators are two basic operators of GAs.

Crossover: The crossover mixes the features of two rules by the combination of their attributes. The proposed crossover operator has two versions:

• Crossover by Value Exchange. If two rules X and Y have one or several common attribute(s) in their C parts, one common attribute is randomly selected. The value of the selected attribute in X is exchanged with its counterpart in Y (Fig. 13.3).

• Crossover by Insertion. Conversely, if X and Y have no common attribute, one term is randomly selected in the C part of X and inserted in Y with a probability inversely proportional to the length of Y. The similar operation is performed to insert one term of Y in X(Fig. 13.4).

Figure 13.2 A multi-objective GA.