{'fraction_non_alphanumeric': 0.04429720381714381, 'fraction_numerical': 0.013043297078801516, 'mean_word_length': 4.282412502751486, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Genetic Algorithms for Extension Search in Default Logic

A default theory can be characterized by its sets of plausible conclusions, called its extensions. But, due to the theoretical complexity of Default Logic (Sigma_2p-complete), the problem of finding such an extension is very difficult if one wants to deal with non trivial knowledge bases. Based on the principle of natural selection, Genetic Algorithms have been quite successfully applied to combinatorial problems and seem useful for problems with huge search spaces and when no tractable algorithm is available. The purpose of this paper is to show that techniques issued from Genetic Algorithms can be used in order to build an efficient default reasoning system. After providing a formal description of the components required for an extension search based on Genetic Algorithms principles, we exhibit some experimental results.


Introduction
Default Logic has been introduced by Reiter (Reiter 1980) in order to formalize common sense reasoning from incomplete information, and is now recognized as one of the most appropriate framework for non monotonic reasoning. In this formalism, knowledge is represented by a default theory from which one tries to build some extensions, that is a set of plausible conclusions. But, due to the level of theoretical complexity of Default Logic, the computation of these extensions becomes a great challenge.
Previous works (Cholewiński et al. 1999;Schaub 1998;Niemelä 1995;Schwind & Risch 1994) have already investigated this computational aspect of Default Logic. Even if the system DeRes (Cholewiński et al. 1999) has very good performance on certain classes of default theories, there is no efficient system for general extension calculus. The aim of the present work is not to exhibit a system able to compute extensions of every default theory in a minimal time, but to show that techniques issued from Genetic Algorithms can be very useful in order to build an efficient default reasoning system.
Based on the principle of natural selection, Genetic Algorithms have been quite successfully applied to com-binatorial problems such as scheduling or transportation problems. The key principle of this approach states that, species evolve through adaptations to a changing environment and that the gained knowledge is embedded in the structure of the population and its members, encoded in their chromosomes. If individuals are considered as potential solutions to a given problem, applying a genetic algorithm consists in generating better and better individuals w.r.t. the problem by selecting, crossing and mutating them. This approach seems very useful for problems with huge search spaces and for which no tractable algorithm is available, such as our problem of default theory's extension search.
Here, the main difference with common uses of Genetic Algorithms is the domain of computation. One has to point out the symbolic aspect of the search space, since the extensions we want to compute are sets of propositional formulas.
The paper is organized as follows : first we recall basic definitions and concepts related to Default Logic and Genetic Algorithms. Then, we provide the formal description of an extension search system based on Genetic Agolrithms principles and, at last, we describe our experiments w.r.t. other existing systems.

Technical Background
Default Logic is a non monotonic logic since the sets of conclusions (theorems) does not necessary grow when the set of premises (axioms) does, as it is always the case in classical logic. In Default Logic, such a maximal set of conclusions is called an extension of the given default theory (W, D) where W is a set of first order formulas representing the sure knowledge, and D a set of default rules (or defaults). A default δ = α : β1,...,βn γ is an inference rule providing conclusions relying upon given, as well as absent information meaning "if the prerequisite α is proved, and if for all i = 1, . . . , n each justification β i is individually consistent (in other words if nothing proves its negation) then one concludes the consequent γ". For a default rule δ, Prereq(δ), Justif (δ) and Conseq(δ) respectively denotes the prerequisite, the set of justifications and the consequent of δ. These definitions will be also extended to sets of defaults. The reader who is not familiar with Default Logic will find in (Besnard 1989;Antoniou 1997;Schaub 1998) many other complements about this formalism. Therefore, we recall here the essential formal definitions in the context of propositional default theories since our work is concerned by these ones.
Definition 1 (Reiter 1980) Let (W, D) be a default theory. For any set of formulas S let Γ(S) the smallest set satisfying the following properties.
Based on this fixed-point definition, Reiter has given the following pseudo iterative characterization of an extension.
Definition 2 (Reiter 1980) Let (W, D) be a default theory and E a formula set. We define Then, E is an extension of (W, Example 1 To illustrate these definitions we give three examples, in order to describe three particular points about default theories. ¬b }) has no extension. As mentioned in introduction, the computation of an extension is known to be Σ p 2 − complete (Gottlob 1992). Intuitively, these two levels of complexity are due to the fact that for each default in D we have to prove its prerequisite and to check that we have no proof of the negation of one of its justification. But, in fact, building an extension consists in finding its Generating Default Set because this particular set contains all defaults whose consequents are used to build the extension. Defaults that occur in the generating default set are said to be applied and every generating default set is grounded.
Definition 4 (Schwind 1990) Given a default theory (W, D), a set of default ∆ ⊆ D is grounded if ∆ can be ordered as the following sequence < δ 1 , . . . , δ n > satisfying the property: Now, we briefly recall the Genetic Algorithms concepts we use. We have to adapt some basic techniques and modify some definitions to fit our context but we refer the reader to (Michalewicz 1996) for a survey.
Since Genetic Algorithms are based on the principle of natural selection, vocabulary issued from natural genetics will be used in the Genetic Algorithms framework. We first consider a population of individuals which are represented by their chromosome. Each chromosome represents a potential solution to the given problem. The semantics of a chromosome (called its phenotype) has to be defined externally by the user. Then, an evaluation process and genetic operators determine the evolution of the population in order to get better and better individuals.
A genetic algorithm consists of the following components : • a representation of the potential solutions : in most cases, chromosomes will be strings of bits representing its genes, • a way to create an initial population, • an evaluation function eval : the evaluation function rates each potential solution w.r.t. the given problem, • genetic operators that define the composition of the children : two different operators will be considered: Crossover allows to generate two new chromosomes (the offsprings) by crossing two chromosomes of the current population (the parents), Mutation arbitrarily alters one or more genes of a selected chromosome, • parameters : population size p size and probabilities of crossover p c and mutation p m .
We now present the general mechanism. Chromosomes, denoted G i , are strings of bits of length n. The initial population is created by generating p size chromosomes randomly. Starting from this initial population, we have to define a selection process for the next population and how to apply genetic operators.
The selection process presented here is based on an ordering of the individuals w.r.t. their evaluation. This process slightly differs from the initial definition of selection in (Michalewicz 1996) which is based on the construction of a roulette wheel by scaling.
• order 1 the population according to evaluation rates; note that identical individuals occur only once in this classification.
Then, an intermediate population is constructed by selecting chromosomes according to the following method : • consider the ordered list of the different chromosomes, • a decreasing number of occurrences of each chromosome is put in the selected population w.r.t. the place of the chromosome in this ordered list. For instance the best rated chromosome will be represented N times in this selected population, while next chromosome will occur N-1 times and so on...
• this repartition in this population is user-defined but should satisfy that its size is equal to p size .
This principle is illustrated on the example of Figure 1 where the evaluation corresponds to the number of 1 in the chromosome. Furthermore, the best chromosome is duplicated 4 times in the selected population , the second 3 times, the third 2 times and the fourth only once. Due to the extension of the order, one can remark that, even if their rating is the same, the chromosome (10010) is selected once while (01001) is selected twice. This is due to the fact that (01001) is greater than (10010) in the ordering. This example only shows how individuals are selected from a population to be involved in reproduction and mutation Therefore genetic operators will be now apply on this selected population. Crossover is performed in the following way : • select randomly two chromosomes in the selected population • generate randomly a number r ∈ [0, 1] • if r > p c then the crossover is possible; select a random position p ∈ {1, . . . , n − 1} -the two chromosomes (a 1 , ..., a p , a p+1 , ..., a n ) and (b 1 , ..., b p , b p+1 , ..., b n ) are replaced by the two new chromosomes (a 1 , ..., a p , b p+1 , ..., b n ) and (b 1 , ..., b p , a p+1 , ..., a n ) as shown in Figure 2.
• if the crossover does not occur then the two chromosomes are put back in the selected population.
The mutation is defined as : • if r > p m then mutate the bit b j (i.e. flip the bit).
This full process is repeated to generate successive populations and one has to define the number of populations to be explored. The best chromosome of each Clearly, the main difficulty of defining a Genetic Algorithms based search lies in the choice of the population's representation and in the definition of the evaluation process. A lot of work has also to be done in order to get a fine tuning of the different parameters p size , p c , p m . Concerning our particular problem, these steps will be fully detailed in the next section.

Formal Description of the System
Our purpose is to construct an extension of a given default theory (W, D) w.r.t. Definition 1. We call candidate extensions the possible solutions to our problem. According to the principles of Genetic Algorithms, we now consider a population of individuals representing candidate extensions.
A naive approach could consist in considering the underlying set of atomic propositions induced by the signature of the default theory. Thus, the chromosomes would represent a kind of truth table : It has only one extension T h({a, c, d}) which does not contain b neither ¬b. This representation will produce a lot of inconsistent candidate extensions because both b and ¬b can be marked as potentially valid as it is specified in G.
Therefore, it seems impossible to insure the efficiency and the convergence of the mechanism. One solution could be to introduce a three-valued logic representation but, in this case chromosomes cannot be strings of bits and require a more complicated encoding.
To avoid these drawbacks, another approach consists in focusing on the defaults more than on their consequences (according to Definition 2). Moreover, this approach seems to be natural since an extension is completely determined by its generating default set. The following definitions set out a common formal framework which consists of a representation scheme and of an evaluation process.

Representation
A representation consists of the following elements : • a chromosome language G defined by a chosen size n, • an interpretation mapping to translate chromosomes in term of possibly applied defaults, which provides the semantics of the chromosomes.
In this context, the chromosome language G is the regular language (0 + 1) n (i.e. strings of n bits). Given a chromosome G ∈ G, G| i denotes the value of G at occurrence i.
The mapping can be formally defined as : Definition 5 Given a default theory (W, D) and chromosome language G, an interpretation mapping is defined as : φ: G × D → {true, f alse} A candidate extension CE(W, D, G) is associated to each chromosome and can also be characterized by its candidate generating default set CGD(W, D, G)(see Definition 3). These two sets are easily defined w.r.t. the interpretation mapping. Definition 6 Given a default theory (W, D), a chromosome G ∈ G, the candidate generating default set associated to G is : Definition 7 Given a default theory (W, D), a chromosome G ∈ G, the candidate extension associated to G is : CE(W, D, G) and CGD(W, D, G) will be simply denoted CE(G) and CGD(G) when it is clear from the context. Remark that since we have to compute the set of logical consequences, a theorem prover will be needed in our system. We now comment two different possible representations according to the previous definitions.
• Given a set of defaults D = {δ 1 , · · · , δ n } we can choose to encode in the chromosome the fact that the default is applicable. In this case the size of the chromosome corresponds to the cardinality of D (i.e. n) and the interpretation function is defined as : The main problem with this representation is its sensitiveness to mutation and crossover since a bit flipping in the chromosome induces a great change in the candidate extension. To refine this, we suggest another solution. • For each default α : β1,...,βn γ we encode in the chromosome the prerequisite α and all justifications β 1 , ..., β n conjointly. Given a set of defaults D = {δ 1 , · · · , δ n } the size of the chromosome will be 2n and its semantics is given by the interpretation mapping : true if G| 2i−1 = 1 and G| 2i = 0 f alse in other cases Intuitively, for a default δ i , if G| 2i−1 = 1 then its prerequisite is considered to be in the candidate extension and if G| 2i = 0 no negation of its justifications is assumed to belong to the candidate extension.This representation is chosen for the remaining of this paper. Once the representation has been settled, one has to describe the evaluation process and then to run the genetic algorithm principles over the population of chromosomes.

Evaluation
An evaluation can be defined as : Definition 8 Given a chromosome language G, an evaluation function is a mapping eval: G → A, where A is any set such that there exists a total ordering < on it (to achieve the selection process).
Here, the evaluation function is mainly based on the definition of the extension. Different problems can be identified providing different evaluation criteria.  Table 1. Given the two positions G| 2i−1 and G| 2i in the chromosome associated to the default δ i , the first point is to determine w.r.t. these values if this default is supposed to be involved in the construction of the candidate extension (i.e. its conclusion has to be added to the candidate extension or not). Then, we check if this application is relevant.  A y in the penality column Π means that a positive value is assigned to f (G| 2i−1 , G| 2i ). Note that only cases 1 to 4 correspond to default considered to be applied (i.e. such that φ(δ) = true).

Comments on penalities
• Cases 2,3,4 : The consequence γ i is in the candidate extension (because G| 2i−1 = 1 and G| 2i = 0) while the default should not have been applied (because either CE(G) ⊢ α i or ∃j, CE(G) ⊢ ¬β j i ). • Cases 5,9,13: The consequence of the default is not in CE(G) while it should since the prerequisite of the default is in the extension and no negation of justifications is deducible from it. • Other cases : Even if the chromosome value does not agree with the generated candidate extension, these cases can be ignored since they do not affect the extension.
At last, due to the minimality condition in the extension Definition 1 we have also to take into account the cardinality of CGD(G) (noted card(CGD(G)). Thus, we can define the evaluation function as : where n=card(D) The ordering for the selection process is the lexicographic extension (<, <) of the natural ordering < on IN.

Correctness of the Evaluation
We examine now what we have to do when the evaluation function attributes a value (0, ) to a chromosome G. First, let us remark that every candidate extension E = CE(W, D, G) is based on the generating default set CGD(W, D, G). Since eval(G) = (0, ), we can easily conclude that for every default α : β1,...,βn γ ∈ CGD(W, D, G) we have α ∈ E and ¬β i ∈ E, ∀i = 1, . . . , n. But it is not sufficient to prove that E is truly an extension of the default theory (W, D) as shown in the following counter-example.
Example 4 Let (W, D) = (∅, { a : c b , b : c a }) be a default theory and G = (1010). Then, the candidate extension is E = CE(W, D, G) = Th({a, b}) and eval(G) = (0, ). But, it is obvious that E is not an extension of (W, D) that has only one extension : Th(∅).
In fact, the counter-example 4 illustrates that our evaluation function does not capture the groundedness (see Definition 4) of the generating default set of a candidate extension. So, when the evaluation function gives a chromosome with a null value, we have to check if the corresponding generating default set is grounded. If it is the case our following formal result ensures that we have found an extension. If not, the algorithm continues to search a new candidate.
Theorem 1 Let (W, D) be a default theory, G a chromosome and a candidate generating default set ∆ = CGD(W, D, G). eval(G) = (0, ) and ∆ is grounded iff (W, D) has an extension E = Th(W ∪ Conseq(∆)) of which ∆ is the generating default set.

Technical Improvements
Some particular types of defaults can be treated apart to improve the system.
• A default α : β ¬β has not to be specifically encoded in the chromosome language and can be removed from the initial set of default. Since as soon as this default can be applied it blocks itself . One has only to check that for each candidate extension CE(G) either α ∈ CE(G) or ¬β ∈ CE(G). Moreover, we focus on this kind of defaults because they are very interesting in certain cases. For instance, a default : β ¬β "keeps" only extensions that contain ¬β. This property is often used in the graph problem encoding described in (Cholewiński et al. 1999).
with W ⊢ α i : then for every chromosome G we impose G| 2i−1 = 1.
with W ⊢ ¬β j i : for some j then for every chromosome G we impose G| 2i = 1.

Experimental Results :
the GADEL System Basically, DeRes (Cholewiński et al. 1999) and our system GADEL use a common approach in their search for an extension of a default theory (W, D) : they both use a generate and test procedure. They explore the search space 2 D and check if a subset DG ⊂ D can be the generating default set of an extension of (W, D). But, DeRes explores the search space with an ad-hoc backtracking procedure while GADEL uses the Genetic Algorithms principles in order to reach as quickly as possible some "good" candidates. (Cholewiński et al. 1999) describes the very good performances of DeRes on some kind of default theories : the stratified ones. But it is also noticed that for a non stratified default theory, as for the Hamiltonian cycle problem, the performance of DeRes are not enough to deal with a non very few number of defaults. 3.0 14.6 ¿3600 man ∧ student 186.7 467.5 ¿3600 woman ∧ student 271.6 704.4 ¿3600 ham.b 3, 2, 0, 0, 1, 0, 0 1.8 5.6 0.5 ham.b 4, 2, 0, 0, 1, 0, 0 -¿3600 19.4 ham.b 5, 2, 0, 0, 1, 0, 0 -¿3600 566.4 ham.b 6, 2, 0, 0, 1, 0, 0 -¿3600 ¿3600 In Table the first column gives the used default theories. For the first lines it shows the formula f added to the theory people (the whole description of this example is given in appendix) and for the last ones it shows which Hamiltonian cycle problem we have used (the encoding of the problem is furnished by Theory-Base (Cholewiński et al. 1999)). The second and third columns respectively give average number of generations N G, and average time T G in seconds to obtain one extension of (W ∪ {f }, D) by GADEL (the parameters of the genetic algorithm are p c = 0.8, p m = 0.1, p size = 325 for people problems, and p size = 465 for the Hamiltonian problems, the number of tests is 100). The fourth column gives the time T D spent by DeRes to solve the problem with the full prover option. Note that all these problems are not stratified.
We give in (Stephan, Saubion, & Nicolas 2000) a finer analysis of our experiments but results given in this table shows that DeRes has a lot of difficulties with our taxonomic example People (even if we use the local prover). Conversely the number of generations are quite small for GADEL (even if the time is not so good: all the implementation is written in Prolog). But, on its turn, GADEL has poor performances on Hamiltonian problems. We think that it is because we do not take into account the groundedness into our evaluation func-tion. As a matter of fact, in the Hamiltonian problem, a solution is exactly one "chain" 2 of defaults, but, there is a lot of potential solutions (whose evaluation is null) based on two, or more, chains of defaults. The only criterion to discard these candidate generating default sets is the groundedness property that they do not satisfy. Conversely, in people example, a solution is a set of non conflicting defaults, but at most four defaults are chained together, and so the groundedness property is less important to reach a solution.

Conclusion
The general method described in this paper provides a new framework in order to search for extensions of a Default Logic theory, by using Genetic Algorithms techniques. This new approach allows us to quickly generate good candidate extensions and experimental results are promising w.r.t. other systems. Moreover, the validity of our method is ensured by a theoretical correctness result. Now, a first point to examine is to integrate the groundedness property in the evaluation function, but we have to take care to not much increase the computation time. The efficiency could be improved by combining other search techniques like local search heuristics. An another important feature of our approach is its ability to be parallelized. In fact, the evaluation of the whole population and its genetic manipulations can be distributed on several processors without fundamental difficulties. These points will be explored in a future work.

Appendices
Proof of the theorem Theorem 1 Let (W, D) be a default theory, G a chromosome and a candidate generating default set ∆ = CGD(W, D, G). eval(G) = (0, ) and ∆ is grounded iff (W, D) has an extension E = Th(W ∪ Conseq(∆)) of which ∆ is the generating default set.
Proof ←−: Let E = Th(W ∪ Conseq(∆)) be an extension of (W, D). Since ∆ is the generating default set of E, it is obviously grounded. Let us suppose that eval(G) > (0, ). Then, according to the definition of our evaluation function (see Table 1), it means that there exists a default δ = α : β1,...,βn γ ∈ D for which a penalty has been assigned. Let us examine the two possible cases: • δ ∈ ∆: penalties can arise from cases 2, 3 or 4, but no one of them is possible since E ⊢ α and E ⊢ β i , ∀i = 1, . . . , n by definition of a generating default set 2 We say that δ is chained to δ ′ if Conseq (δ) ⊢ Prereq (δ ′ ).
• δ ∈ ∆: penalties can arise from cases 5, 9, or 13, but no one of them is possible since it would indicate that δ should be a generating default of E.