Germain Montazeaud
email: g.montazeaud@gmail.com

François Rousset

Florian Fort

Cyrille Violle

Hélène Fréville

Sylvain Gandon

Farming plant cooperation in crops

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Ever since the dawn of Agriculture, humans have imposed artificial selection on plants to increase the quality and the quantity of crop production [START_REF] Harlan | Comparative evolution of cereals[END_REF][START_REF] Meyer | Patterns and processes in crop domestication: an historical review and quantitative analysis of 203 global food crops[END_REF]. The domestication of wild species led to the selection of phenotypes that would never have been favoured by natural selection under unmanaged conditions, such as the loss of seed dispersal or the decrease in defence compounds production [START_REF]On the origin of species by means of natural selection[END_REF][START_REF] Donald | The convergent evolution of annual seed crops in agriculture[END_REF]. This was further amplified in the 20th century with the progressive mechanization of field work and the increasing use of herbicides and fertilizers. Agronomists indeed observed that varieties with weak competitive abilities performed better than competitive ones under such conditions [START_REF] Donald | The breeding of crop ideotypes[END_REF][START_REF] Jennings | Studies on competition in rice I. Competition in mixtures of varieties[END_REF][START_REF] Jennings | Studies on competition in rice II. Competition in segregating populations[END_REF]. This led Donald to define a cereal ideotype designed to perform "as a community" by having a set of phenotypic characteristics such as a short stem, few tillers and few erected leaves [START_REF] Donald | The breeding of crop ideotypes[END_REF]. As such, Donald disseminated the idea that phenotypes which maximize group productivity, or crop yield, also decrease individual competitiveness.

This idea was further generalized as the "Tragedy of the commons" (TOC): phenotypes that maximize group performance are necessarily sub-optimal for individual performance, making them susceptible to invasion by selfish phenotypes [START_REF] Hardin | The tragedy of the commons[END_REF]. TOCs were widely investigated in crops using Evolutionary Game Theory (EGT) approaches (reviewed in [START_REF] Anten | Tragedies and crops: understanding natural selection to improve cropping systems[END_REF]), most studies concluding that humans have to work against natural selection to prevent invasions of the best performing groups by competitive phenotypes. This was early observed by plant breeders in bulk breeding programs, where the most favourable phenotypes for yield, such as short plants, were lost over few generations due to intraspecific competition [START_REF] Jennings | Studies on competition in rice I. Competition in mixtures of varieties[END_REF][START_REF] Jennings | Studies on competition in rice II. Competition in segregating populations[END_REF][START_REF] Suneson | Survival of barley and wheat varities in mixtures[END_REF].

At the same time, the evolutionary biologist William Hamilton formalized the kin selection theory which aimed at understanding the evolution of social interactions, notably altruism where individuals act to increase the fitness of their social partners at the expense of their own reproduction [START_REF] Hamilton | The genetical evolution of social behaviour[END_REF][START_REF] Hamilton | The genetical evolution of social behaviour[END_REF]. Hamilton proposed a very simple rule which states that altruistic phenotypes can be selected if the fitness cost for the actor, c, is outweighed by the benefit received by the partners, b, weighted by the relatedness between the actor and the partners, R, i.e. when c < Rb. With this rule, Hamilton explicitly incorporated the contribution of relatives in transmitting genes that are shared with the actor to the next generations. Later works have emphasized that -c+Rb provides a representation of the average effect of an allelic substitution on individual fitness (e.g. [START_REF] Dawkins | The extended phenotype[END_REF]) rather than an alternative to individual fitness: -c+Rb gives the expected effects of copies of an allele in different individuals on the expected fitness of individuals who bear the allele. Kin selection has been extremely successful in explaining a wide range of altruistic phenotypes such as sterility in eusocial insects [START_REF] Hamilton | The genetical evolution of social behaviour[END_REF] or helping behaviours in birds [START_REF] Emlen | The role of kinship in helping decisions among white-fronted beeeaters[END_REF], and it has received increasing attention in plants in recent decades (reviewed in [START_REF] File | Fitness consequences of plants growing with siblings: reconciling kin selection, niche partitioning and competitive ability[END_REF]).

Since farmers are more interested in productivity per unit area than in individual plant productivity, it was early advanced that plant breeding should take advantage of the mechanisms that maximize group productivity to increase crop yield [START_REF] Harper | Population biology of plants[END_REF]. More recently, several authors argued that plant breeding had not fully explored the trade-off between group productivity and individual performance and that significant yield gain could be achieved by reversing past natural selection for competitiveness [START_REF] Weiner | Evolutionary Agroecology: the potential for cooperative, high density, weed-suppressing cereals[END_REF][START_REF] Denison | Darwinian Agriculture: when can humans find solutions beyond the reach of natural selection?[END_REF][START_REF] Denison | Darwinian Agriculture: how understanding evolution can improve agriculture[END_REF][START_REF] Weiner | Evolutionary agroecology: individual fitness and population yield in wheat (Triticum aestivum)[END_REF]. To do so, recommendations drawn from the general principles of kin selection or group selection have been proposed [START_REF] Weiner | Evolutionary Agroecology: the potential for cooperative, high density, weed-suppressing cereals[END_REF][START_REF] Denison | Darwinian Agriculture: when can humans find solutions beyond the reach of natural selection?[END_REF][START_REF] Weiner | Evolutionary agroecology: individual fitness and population yield in wheat (Triticum aestivum)[END_REF][START_REF] Murphy | Kin recognition, multilevel selection and altruism in crop sustainability[END_REF][START_REF] Kiers | Inclusive fitness in agriculture[END_REF]]. Yet, it remains difficult to assess the extent to which plant breeding could benefit from these principles as long as they are not formally applied to crops.

Current crop improvement programs do not explicitly take into account social interactions among plants [START_REF] Denison | Darwinian Agriculture: when can humans find solutions beyond the reach of natural selection?[END_REF][START_REF] Murphy | Kin recognition, multilevel selection and altruism in crop sustainability[END_REF]. Conversely, significant work has been achieved to integrate the effects of social interactions into farm animals breeding programs [START_REF] Wade | Group selection and social evolution in domesticated animals[END_REF]. Indeed, reducing competitiveness among group-housed animals is critical for both productivity and animal welfare [START_REF] Rodenburg | Breeding amiable animals? Improving farm animal welfare by including social effects in breeding programmes[END_REF]. Based on the early work of Griffing [START_REF] Griffing | Selection in reference to biological groups. I. Individual and group selection applied to populations of unordered groups[END_REF], quantitative genetic models have been developed to account for the effect of the genes of the focal individual on its own phenotypic traits, known as the direct genetic effect (DGE), and the effects of the genes of individuals interacting with the focal individual, known as the indirect genetic effect (IGE) [START_REF] Muir | Incorporation of competitive effects in forest tree or animal breeding programs[END_REF][START_REF] Bijma | Multilevel selection 1: Quantitative genetics of inheritance and response to selection[END_REF][START_REF] Bijma | Multilevel selection 2: Estimating the genetic parameters determining inheritance and response to selection[END_REF]. Experiments have shown that IGEs can represent a significant proportion of the heritable variation on traits such as growth rate in pigs [START_REF] Bergsma | The contribution of social effects to heritable variation in finishing traits of domestic pigs (Sus scrofa)[END_REF] or survival rate in laying hens [START_REF] Ellen | Survival of laying hens: Genetic parameters for direct and associative effects in three purebred layer lines[END_REF].

Therefore, the genetic response to selection can significantly be improved by accounting for IGEs [START_REF] Muir | Incorporation of competitive effects in forest tree or animal breeding programs[END_REF]. Theoretical studies have shown how the IGEs frameworks connects with kin selection theory and how relatedness affects the genetic response to selection in presence of IGEs [START_REF] Bijma | The joint effects of kin, multilevel selection and indirect genetic effects on response to genetic selection[END_REF][START_REF] Mcglothlin | Quantitative genetic versions of Hamilton's rule with empirical applications[END_REF]. To a lesser extent, this framework has also been applied in tree breeding [START_REF] Cappa | Direct and competition additive effects in tree breeding: Bayesian estimation from an individual tree mixed model[END_REF][START_REF] Costa E Silva | Accounting for competition in genetic analysis, with particular emphasis on forest genetic trials[END_REF]. Yet we still poorly understand how social interactions affect the evolution of plant phenotypes, and the extent to which crop breeding schemes can improve yield depending on the intensity of social interactions.

To fill these gaps, we develop a kin selection model to investigate the evolution of cooperation in crops. The model allows us to identify the most important parameters that promote cooperation and increase crop yield, and to revisit crop evolutionary history in light of the kin selection theory.

Methods

We define cooperation as the evolution of a phenotype that decreases the intensity of intraspecific competition. We focus on competition for light, using plant height as the competitive trait for three main reasons. Over the different axes of phenotypic variation in plants, height is classically reported as the main driver of competitive ability [START_REF] Gaudet | A comparative approach to predicting competitive ability from plant traits[END_REF][START_REF] Westoby | Plant ecological strategies: some leading dimensions of variation between species[END_REF]. Second, the impact of competition for light on plant fitness has been widely documented [START_REF] Gaudet | A comparative approach to predicting competitive ability from plant traits[END_REF][START_REF] Weiner | Asymmetric competition in plant populations[END_REF][START_REF] Violle | Competition, traits and resource depletion in plant communities[END_REF] including in crops [START_REF] Flintham | Optimizing wheat grain yield: effects of Rht (gibberellin-insensitive) dwarfing genes[END_REF][START_REF] Donald | Competition among crop and pasture plants[END_REF], enabling us to have a reasonably realistic mathematical formalism. Finally, plant height is one of the traits for which we have important historical data in crops [START_REF] Austin | Genetic improvements in winter wheat yields since 1900 and associated physiological changes[END_REF][START_REF] Roucou | Shifts in plant functional strategies over the course of wheat domestication[END_REF][START_REF] Milla | Shifts and disruptions in resource-use trait syndromes during the evolution of herbaceous crops[END_REF][START_REF] Milla | Phylogenetic patterns and phenotypic profiles of the species of plants and mammals farmed for food[END_REF], making it possible to interpret our results in light of human selection practices. It must be stressed that we deliberately kept the mechanistic and genetic aspects of the model simple to focus on processes of interest in this study, which are evolutionary dynamics and their interaction with human practices.

Crop populations are spatially structured, either in fields when grown by a farmer, or in experimental plots when evaluated by a plant breeder. In our model we assume that the crop population is made of n F fields, with n P plants per field. In agreement with experimental evidence on several crop species [START_REF] Flintham | Optimizing wheat grain yield: effects of Rht (gibberellin-insensitive) dwarfing genes[END_REF][START_REF] Austin | Genetic improvements in winter wheat yields since 1900 and associated physiological changes[END_REF], we assume that there is an optimal height x that maximizes plant fecundity, i.e. individual seed production, in the absence of competition for light (Fig. 1B). We model competition for light with the drop shadows of neighbouring plants (Fig. 1A). Plant fecundity is assumed to decrease proportionally to the size of the overlapping area between drop shadows and thus with the height of the neighbours, as observed in experimental studies [START_REF] Gaudet | A comparative approach to predicting competitive ability from plant traits[END_REF][START_REF] Violle | Competition, traits and resource depletion in plant communities[END_REF][START_REF] Donald | Competition among crop and pasture plants[END_REF] (Fig. 1C). One of the main parameters that drives intraspecific competition in crops is plant density [START_REF] Donald | The breeding of crop ideotypes[END_REF][START_REF] Donald | Competition among crop and pasture plants[END_REF]. In the model, plant density is governed by the parameter d, the distance between plants. The intensity of competition for light also depends on the angle a at the apex of the triangle used to represent drop shadows (Fig. 1A). We computed crop yield as the total number of seeds produced in a field divided by the field area (see Supplementary Information section 1.1). As expected, the plant height that maximises crop yield decreases with the distance between plants (Fig. 3 and Fig. S2), and crop yield is maximized by growing short plants at high density [START_REF] Donald | The breeding of crop ideotypes[END_REF][START_REF] Donald | Competition among crop and pasture plants[END_REF]. To fit as closely as possible to the specifics of real crops such as wheat, we set the optimal plant heightxto 100 cm and the angle a to π/50 rad. Such a small angle allowed us to generate a moderate and realistic intensity of competition at low plant-plant distances such as those classically encountered in cereals. Note that the choice of parameter values did not affect our results qualitatively.

We compared the efficiency of three selection strategies. In the Within-Field (WF) strategy, seeds sown in a given field are exclusively sampled in the harvest of this same field; in the Among-Field (AF) strategy, fields are sown with seeds sampled after pooling the harvest of all fields; in the Top-Field (TF) strategy, fields are sown with seeds exclusively sampled in the harvest of the most productive field. In the WF strategy, the best performing plants within their fields contribute more to the next generation, whereas in the AF strategy, the best performing fields within the crop population contribute more to the next generation, this phenomenon being magnified in the TF strategy.

Relatedness, a key parameter of kin selection theory, is modulated by the parameter n S , the number of founding seeds (Supplementary Information section 1.3 and Fig. S3). For cases where n S <n P , we multiply each founding seed in equal proportion, i.e. no selection during this step, until we obtain enough seeds to have n P plants in each field.

We developed an analytical model from which we derived approximations for the Evolutionary Stable Strategy (ESS) for plant height, that is the strategy that cannot be invaded by any alternative strategy [START_REF] Geritz | Evolutionarily singular strategies and the adaptive growth and branching of the evolutionary tree[END_REF] (Supplementary Information section 1.2). The ESS approach is widely used in evolutionary biology to predict the outcome of long-term evolutionary processes where fitness depends on the frequencies of the different phenotypes present in the population. In our study, we adopt the kin selection approach to account for the spatial structure of crops [START_REF] Taylor | How to make a kin selection model[END_REF]: as mentioned above, the crop population is distributed into different fields, or different groups, that can be connected by migration. These groups delineate social interactions: individuals only interact within groups. The evolution of social traits is driven by the genetic similarity between actors and recipients and thus by genetic similarity between group members at the loci involved in social traits [START_REF] Hamilton | The genetical evolution of social behaviour[END_REF]. Relatedness (R) quantifies this similarity and measures the extent to which an actor is more likely to share an allele (and thus share a common phenotype) with an individual sampled in its own group than with an individual sampled in another group [START_REF] Frank | Foundations of Social Evolution[END_REF][START_REF] Rousset | A theoretical basis for measures of kin selection in subdivided populations: finite populations and localized dispersal[END_REF] (Supplementary Information section 1.3). Compared to traditional definitions of relatedness from pedigrees, the definition of relatedness used here averages pedigree relatedness over the distribution of pedigrees of gene copies within groups [START_REF] Rousset | Inbreeding and relatedness coefficients: what do they measure?[END_REF]. As this distribution depends on other features of the life cycle such as migration rates, relatedness depends on the life cycle (Fig. S3).

In addition to the ESS approach, we ran individual-based simulations to track the evolution of plant height across generations (Supplementary Information section 1.4): we simulated the life cycle of all plants from sowing to harvest over thousands of generations until the selection-drift-mutation equilibrium was reached. Finally, we compared the mean plant height at equilibrium with ESS approximations. We hereafter present ESS and simulation results for the three selection strategies (WF, AF, and TF) with varying planting density and relatedness.

Results

Overall, ESS predictions agreed very well with simulation results and equilibriums were always monomorphic, meaning that a single phenotype was present in the population at the end of the simulations (Fig. 3, black dots). When plants were grown at low densities (d > 12), they did not compete for light and thus the mean phenotype at equilibrium was the optimal phenotype for individual fecundity, i.e. x (competition intensity 0 in Fig. 1A). At intermediate densities (7 < d < 12), plants evolved smaller than their optimal phenotype in all scenarios. Indeed, when competition is low (competition intensity 1 in Fig. 1A), shorter phenotypes result in greater plant fecundity because the fecundity loss incurred by moving away from the optimum is overcompensated by the fecundity gain obtained by avoiding the shadow of the neighbours. At high densities (d < 7), where competition is more intense (competition intensity 2 in Fig. 1A), evolutionary outcomes differed greatly among scenarios. With the WF strategy, the higher the density (the lower d), the taller the plant evolved. At equilibrium, plant were well above the optimal height x, leading to very low yields whatever the number of founding seeds (Fig. 3A, D, andG). In contrast, both AF and TF strategies resulted in the evolution of short high-yielding phenotypes when the number of founding seeds was low (Fig. 3B, C, andF). Increasing the number of founding seeds reduced relatedness (Fig. S3), drove the evolution of taller plants, and lowered crop yield (Fig. 3E, H, andI). Shorter phenotypes evolved under the TF strategy compared to the AF strategy, as a result of stronger selection among fields in the TF strategy (Fig. 3E andF). Interestingly, with both AF and TF strategies, two alternative evolutionary outcomes were possible for certain ranges of d (e.g. Fig. 3E when 2 < d < 3.5 cm). When such evolutionary bistability occurred, which evolutionary outcome was reached depended on the initial phenotypic value of the population (Fig. S4).

The ESS analysis captures the long-term evolutionary outcome of the model but does not predict the speed of phenotypic evolution towards the ESS. To explore the short-term evolutionary dynamics of plant height under realistic agricultural practices, we carried out individual-based simulations under the three selection strategies for 20 generations with a small number of fields ( n F =5 , Fig. 4). The WF strategy and the AF strategy generated slow evolution compared to the TF strategy (Fig. 4A). Consequently, the relative efficiency in increasing yield differed markedly among selection strategies: after 20 generations, yield had decreased by 5% with the WF strategy whereas it has increased by 15% with the AF strategy and by 110 % with the TF strategy (Fig. 4B).

Discussion

While most studies concluded that phenotypes which maximize group productivity are not evolutionary stable [START_REF] Anten | Tragedies and crops: understanding natural selection to improve cropping systems[END_REF][START_REF] Falster | Plant height and evolutionary games[END_REF], our model demonstrates that evolutionary principles can be used to select for cooperation and increase crop yield. Our results thus provide new insights into the relative importance of parameters that could be used to select for cooperation in breeding programs. First, as widely acknowledged in agronomy, plant density has a critical role in controlling the balance between individual competitiveness and group performance [START_REF] Weiner | Evolutionary Agroecology: the potential for cooperative, high density, weed-suppressing cereals[END_REF]. The closer the plants, the stronger the direct and indirect fitness effects, resulting in stronger selection for either selfish tall phenotype or altruistic short phenotype depending on relatedness. Yet, the effect of density is not monotonic. Therefore, the phenotypic value of the crop population at the beginning of the breeding program can constrain selection even if all conditions are met for cooperation to evolve. For example, starting with tall plants might hamper the evolution of short phenotypes. Second, although selection at the group level is indeed mandatory to select altruistic phenotypes [START_REF] Weiner | Evolutionary Agroecology: the potential for cooperative, high density, weed-suppressing cereals[END_REF][START_REF] Denison | Darwinian Agriculture: when can humans find solutions beyond the reach of natural selection?[END_REF][START_REF] Murphy | Kin recognition, multilevel selection and altruism in crop sustainability[END_REF], our results demonstrate that group-level selection is not sufficient: when relatedness becomes too low, the AF and TF strategies fail to select for short phenotypes. More precisely, as the number of founding seeds increases, the within-field variability increases and the between-field variability decreases. This reduces relatedness and limits the ability to discriminate the different fields based on their productivity, thus reducing the strength of among-field selection. Such an important role of relatedness in interaction with group level selection has been missed in the literature on cultivated plants.

The potential of group selection in agriculture was early demonstrated in poultry. In a seminal experiment, Muir demonstrated that selection at the family level (half sib families) was very efficient to increase egg production and to reduce mortality in laying hens [START_REF] Muir | Group selection for adaptation to multiple-hen cages: selection program and direct responses[END_REF]. Moreover, such practices have been shown experimentally to be more efficient when groups are composed of relatives [START_REF] Muir | Incorporation of competitive effects in forest tree or animal breeding programs[END_REF]. These results are in line with our study and previous theoretical works in quantitative genetics showing that relatedness and the degree of group selection jointly affect genetic response to selection [START_REF] Bijma | The joint effects of kin, multilevel selection and indirect genetic effects on response to genetic selection[END_REF][START_REF] Mcglothlin | Quantitative genetic versions of Hamilton's rule with empirical applications[END_REF]. More generally, the convergence between our results and the findings obtained in quantitative genetics and animal breeding literature suggest that the principles and the tools (e.g. mixed model [START_REF] Muir | Incorporation of competitive effects in forest tree or animal breeding programs[END_REF][START_REF] Costa E Silva | Accounting for competition in genetic analysis, with particular emphasis on forest genetic trials[END_REF]) developed in these areas could be applied in crops whenever breeding programs can rely on strong phenotyping efforts.

In crops, the very common pedigree selection is quite similar to the TF strategy, at least in the last generations of selection where plots are planted with single genotypes, and only the most productive plots are retained from one generation to another, which generates both among-field selection and high relatedness. Yet, as mentioned in previous studies, such programs could be even more efficient in improving yield by increasing plant density [START_REF] Weiner | Evolutionary Agroecology: the potential for cooperative, high density, weed-suppressing cereals[END_REF] and by selecting at the group level from the very beginning [START_REF] Murphy | Kin recognition, multilevel selection and altruism in crop sustainability[END_REF]. In practice, the TF strategy could be implemented with a number of experimental plots as limited as 5, with 200 or 300 plants per plot (Figure 4). Increasing the number of plots would increase the effective population size and thus increase the evolutionary speed. To take into account the effect of environmental variability on the evaluation of crop yield and on the selection procedure, it could be useful to replicate the plots or to sample founding seeds in a handful of the most productive fields (Figure S5). Then, founding seeds could be multiplied in a greenhouse between two growing seasons by growing plants at low densities to maximize the seed multiplication rate.

Controlled or uncontrolled crosses could be used to generate new allelic combinations and new phenotypes over generations.

Our results shed new light on the evolution of plant height during the evolutionary history of crops. For most cereals, plant height has increased between their wild ancestor and their earliest domesticated form [START_REF] Roucou | Shifts in plant functional strategies over the course of wheat domestication[END_REF][START_REF] Milla | Shifts and disruptions in resource-use trait syndromes during the evolution of herbaceous crops[END_REF]. Moreover, most of these primitive domesticated forms remained tall, or even evolved taller until the end of the 19th century [START_REF] Donald | The convergent evolution of annual seed crops in agriculture[END_REF]. The practices associated with the transition from gathering to cultivation [START_REF] Harlan | Comparative evolution of cereals[END_REF], as well as the most common selection method over this period, namely mass selection, could be regarded in light of the kin selection: grains were collected from isolated plants (or low-density grown plants), these plants being selected for their individual features, and grains (or spikes) from different plants being mixed before sowing [START_REF] Allard | Principles of plant breeding[END_REF]. Such practices leading to low among-field selection and low relatedness inevitably select for selfish phenotypes. Even if tallness might have deliberately been selected for other needs such as chaff production or weed control [START_REF] Donald | The convergent evolution of annual seed crops in agriculture[END_REF], our model suggests that mass selection might have reinforced selection for increased plant height.

Initiating breeding programs with plants that are too tall can hamper the evolution of short high-yielding phenotypes. This might have happened at least twice in the evolutionary history of crops. First, there is evidence that farmers chose relatively tall plants in the wild to start cultivation [START_REF] Cunniff | Functional traits differ between cereal crop progenitors and other wild grasses gathered in the Neolithic Fertile Crescent[END_REF]. Second, for most cereals the main reduction in plant height was achieved in the 1960's by introgressing dwarf genes from Asian varieties [START_REF] Peng | Green revolution' genes encode mutant gibberellin response modulators[END_REF]. At that time, most wheat varieties were very tall in U.S.A [START_REF] Cox | Genetic improvement in agronomic traits of hard red winter wheat cultivars 1919 to 1987[END_REF] and Europe [START_REF] Austin | Genetic improvements in winter wheat yields since 1900 and associated physiological changes[END_REF], and we could wonder whether plant breeding would have achieved such shortening by crossing and selecting among the local pool varieties.

Reducing plant height in crops was motivated by the need for varieties that better respond to intensive cultivation practices, notably through increased allocation to grains and decreased sensitivity to lodging [START_REF] Hedden | The genes of the Green Revolution[END_REF]. Although such varieties achieved significant yield gain, yield improvement was perceived more as an improvement in individual plant properties, i.e. grain allocation and lodging resistance, than as an improvement in community properties, i.e. lower intraspecific competition [START_REF] Austin | Genetic improvements in winter wheat yields since 1900 and associated physiological changes[END_REF].

As a consequence, plant height is still mainly selected at the single-plant level by eliminating tall plants in the early steps of breeding programs than through indirect selection for group performance, as described in this study. Such direct selection on a plant trait can indeed prove very efficient when the trait measurement is cheap and heritable, which might not be the case of all traits involved in plant-plant interactions.

We explored particular combinations of parameters that we thought relevant for a typical cereal crop. Yet, additional selection scenarios could be evaluated for applications in a broader set of crops including non-grain crops. Moreover, traits other than plant height can be important in driving competitive interactions. For example, root morphological traits can play a key role in the competition for soil resources in perennial species [START_REF] Casper | Plant competition underground[END_REF]. Flower size might also be important for cross-pollinated species [START_REF] Parachnowitsch | Pollinators exert natural selection on flower size and floral display in Penstemon digitalis[END_REF]. More generally, many traits have been reported to be involved in plant-plant interactions, which offer as many opportunities to increase cooperation in crops [START_REF] Anten | Tragedies and crops: understanding natural selection to improve cropping systems[END_REF]. Because of recurrent bottlenecks during the evolutionary history of crops [START_REF] Glémin | A comparative view of the evolution of grasses under domestication[END_REF] and historical practices of cultivation and breeding (see above for an illustration for plant height), altruistic phenotypes might have been lost in the pool of modern varieties. As illustrated with dwarf genes introduced from Japan, it might thus be useful to further enlarge phenotypic variation available at the start of breeding programs by exploring gene pools such as landraces or wild relatives. Moreover, studying the genetic determinism of these traits could help to select for optimized mixtures of genotypes instead of mono-genotypic varieties.

Indeed, not all genes need to be shared in the population for cooperation to evolve, only those involved in competitive interactions. In practice, the identification of specific genes (or linked molecular markers) encoding for competitive traits would allow to sample individuals which are highly related only at these specific loci instead of sampling individuals which are highly related on the whole genome, as illustrated in this study. These practices could select for mixtures of varieties that combine low variability on traits related to competitive ability and high variability on traits linked to other functions such as pathogen resistance, resource-use or stress tolerance. Such mixtures of varieties combining the positive effects of cooperation and biodiversity could help farmers facing the need for more sustainable agriculture [START_REF] Litrico | Diversity in plant breeding: a new conceptual framework[END_REF]. plant height, x. We assumed that, for an isolated plant, there is an optimal plant height x which maximizes individual fecundity. The relationship is shown for three optimal plant height values x = 80 cm (dotted line), x = 90 cm (dashed line), and x = 100 cm (solid line). (C) Relationship between focal plant fecundity and neighbours' plant height. We computed the cost of competition as the proportion of shaded area of the focal triangle. The relationship is shown for a focal plant height equal to the optimal plant height so that x = x = 100 cm, an angle a = π/50, and three plant-plant distances d = 10 cm (dotted line), d = 5 cm (dashed line), and d = 1 cm (solid line). Competition intensity increases from yellow to red. Symbol: "Wheat" by efi kaperoni from the Noun Project. with fields respectively coloured in blue, yellow and green. In the Within-Fields (WF) selection strategy, fields are sown with seeds exclusively sampled in their own harvest. Consequently, the crop evolves separately in the different fields. In the Among-field (AF) selection strategy, seeds from the different fields are pooled together at harvest. Then, each field is sown with seeds sampled in that pool. In the Top-Field (TF) selection strategy, only the most productive field is retained for the next generation. Then, each field is sown with seeds exclusively sampled in the harvest of that top field. For all strategies, a multiplication stage precedes sowing when there are not enough founding seeds to re-populate the n F fields. Symbols: "Wheat" by lastspark from the Noun Project, "seed" by corpus delicti from the Noun Project, and "sow" by Symbolon from the Noun Project. cm. Phenotypic variability was then generated by mutations. Mutation rate equalled 10% meaning that on average 1 individual out of 10 differed in height from its parent. Mutation effect was set to ± 5 cm. We varied the plant-plant physical distance from 1 cm to 15 cm with steps of 2 cm. After 5000 generations, the selection-mutation-drift equilibrium was reached in all simulations. Orange solid lines represent unstable equilibriums, i.e. equilibriums at which any mutation makes the mean phenotype deviate further from its original value, either in the upward or in the downward direction.

Figure 1 |

 1 Figure 1 | Geometrical representation of plant competition for light. (A) We used triangles to represent drop shadows around the plants (grey triangles). The focal individual is represented in black, neighbours are represented in green. Neighbours are positioned at equal distance, d, from the focal individual. For simplicity, we here represented the left and right neighbours with the same plant height, y. Competition for light happens when triangles overlap. Competition intensity increases with increasing overlap (from yellow to red), with no competition (competition intensity 0), low competition (competition intensity 1), intermediate competition (competition intensity 2) and intense competition (competition intensity 3). (B) Relationship between focal plant fecundity, f, and focal

Figure 2 |

 2 Figure 2 | Strategies of selection. The crop is grown in a farm composed of n F fields. Here, n F =3,

Figure 3 |

 3 Figure 3 | Relationship between the mean plant height in the meta-population at equilibrium, z, and the physical distance between plants, d. Evolutionary Stable Strategies (ESS) predicted from the analytical model are reported as a red solid line. Results from individual based simulation are reported in black, with dots (error bars) representing the mean (standard deviation) plant height in the meta-population after 5000 generations. Grain yield is represented in the background of the graphs and increases with lighter grey shade (see Fig. S2). We tested the three seed selection strategies (WF, AF and TF) with three numbers of founding seeds n S = 1 (A, B, C), n S = 2 (D, E, F), and n S = 100 (G, H, I). Simulations were performed with n F = 20 fields and n P = 200 plants per field. In the first generation, the population was monomorphic, i.e. all plants had the same height z, with z = x = 100

Figure 4 |

 4 Figure 4 | Selection efficiency.We modeled the evolution of plant height (A) and we measured the yield gains (B) realized after 20 generations with the three selection strategies (WF in red, AF in green and TF in blue). We performed simulations with n F = 5 fields, n P = 200 plants per field, and a 5 cm plant-plant distance. At generation 1 (G1), each field was initiated by sampling two founding seeds in a normally distributed plant population with mean and standard deviation on plant height respectively equal to 100 cm and 20 cm. For all subsequent generations, we draw two founding seeds in the harvest to repopulate each field. Funding seeds were multiplied in equal proportion (x 100 each) to obtain 200 seeds per field. Mutation rate was equal to 10% with a ± 5 cm mutation effect. Reported values are averaged over 20 simulation runs.

Acknowledgments

We thank R. F. Denison, S. A. West, J. Biernaskie, J. David and A. Rodrigues for helpful comments on earlier versions. We thank V. Ranwez for his assistance in the development of the simulation algorithm. This work was supported by a PhD grant from the Ministère de l'Enseignement Supérieur, de la Recherche et de l'Innovation to GM, the CIRAD -UMR AGAP HPC Data Center of the South Green Bioinformatics platform (htttp://www.southgreeen.fr/), and the European Research Council (ERC) Starting Grant Project "Ecophysiological and biophysical constraints on domestication in crop plants" (Grant ERC-StG-2014-639706-CONSTRAINTS).

No datasets were used during the current study. Scripts used for the analysis and simulations are available at https://github.com/germmtz/farming-plant-cooperation


Thu Huong Nguyen
email: thu-huong.nguyen@univ-cotedazur.fr

Andrea G B Tettamanzi
email: andrea.tettamanzi@univ-cotedazur.fr

A Multi-Objective Evolutionary Approach to Class Disjointness Axiom Discovery

Keywords: Ontology Learning, OWL Axiom, Disjointness Axiom, Genetic Programming, Grammatical Evolution, Multi-Objective Optimization

The huge wealth of linked data available on the Web (also known as the Web of data), organized according to the standards of the Semantic Web, can be exploited to automatically discover new knowledge, expressed in the form of axioms, one of the essential components of ontologies. In order to overcome the limitations of existing methods for axiom discovery, we propose a two-objective grammar-based genetic programming approach that casts axiom discovery as a genetic programming problem involving the two independent criteria of axiom credibility and generality. We demonstrate the power of the proposed approach by applying it to the task of discovering class disjointness axioms involving complex class expression, a type of axioms that plays an important role in improving the quality of ontologies. We carry out experiments to determine the most appropriate parameter settings and we perform an empirical comparison of the proposed method with state-of-the-art methods proposed in the literature.

I. INTRODUCTION

The growth of the Semantic Web also known as the Web of data, where the Linked Open Data (LOD) is a prominent representative opens up exciting opportunities for ontology learning. Due to heterogeneous semantic resources on the Web, ontological knowledge bases (KBs) may turn out to incomplete and noisy. Specifically, the incompleteness refers to the lack of information in ontology while the noise is relevant to the issues of invalid information. To enhance the quality of an ontology, the existence of axioms can be considered as the agents in pinpointing errors and inconsistencies in KBs. In ontology construction and knowledge base enrichment, the automatic asquistion of axiom is a central task which goes under the name of axiom learning. Like other types of axioms, class disjointness axioms are used to check the consistencies of the information contained in the ontologies or to deduce new information. For example, a reasoner will be able to deduce an error, i.e., a logical inconsistency of facts in the ontology, whenever the class Fish is associated to a resource related to the class Planet, if there is a constraint of disjointness between the two concepts Fish and Planet.

As a consequence of the essential role of class disjointness axioms in existing ontologies, learning hidden knowledge in terms of axioms from a LOD repository in the context of the Semantic Web has been the object of research using several different methods. Some prominent research towards the automatic creation of class disjointness axioms from RDF facts include supervised classification, like in the LeDA system [START_REF] Völker | Learning disjointness[END_REF], statistical schema induction via associative rule mining, like in the GoldMiner system [START_REF] Völker | Automatic acquisition of class disjointness[END_REF], and learning general class descriptions (including disjointness) from training data, like in the DL-Learner framework [START_REF] Lehmann | Dl-learner: Learning concepts in description logics[END_REF]. In adtition, recent contribution has proposed using unsupervised statistical approaches like Formal Concept Analysis (FCA) [START_REF] Reynaud | Redescription mining for learning definitions and disjointness axioms in linked open data[END_REF] or Terminological Cluster Trees (TCT) [START_REF] Rizzo | Terminological cluster trees for disjointness axiom discovery[END_REF], to discover disjointness axioms. Most approaches to learning axioms in the literature are based on deterministic level-wise generate-and-test methods, which essentially perform an exhaustive search, coupled with heuristic pruning, of the the space of hypotheses. Their main limitation is that they are incapable of scaling up when the space of the hypothesis, i.e. axioms, becomes too large. As a consequence, their applicability is restricted to the discovery of relatively simple axioms, i.e. atomic axioms.

Given the complexity of the problem, a heuristic approach, such as evolutionary algorithm, can handle with the search for more complex axioms whose space is incomparably larger. In fact, there are also some recent works [START_REF] Nguyen | Learning class disjointness axioms using grammatical evolution[END_REF]- [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] applying an evolutionary approach by using Grammatical Evolution (GE) to extracting class disjointness axioms from large RDF repository, i.e., DBpedia1 . The use of a grammar allows great flexibility: only the grammar needs to be changed to mine different data repositories for different types of axioms. Extracted axioms in [START_REF] Nguyen | Learning class disjointness axioms using grammatical evolution[END_REF], [START_REF]An evolutionary approach to class disjointness axiom discovery[END_REF] include both atomic and complex axioms, i.e., defined with the help of relational operators of intersection and union; in other words, axioms like Dis(C 1 , C 2 ), where C 1 and C 2 are complex class expressions including operators. However, the dependence on SPARQL endpoints (i.e., query engines) for testing mined axioms against facts, i.e. instances, in large RDF repositories limits the performance of the method. In addition, evaluating the effectiveness of the method requires the participation of experts in specific domains, i.e. the use of a Gold Standard, which is proportional to the number of concepts. Hence, the extracted axioms are limited to the classes relevant to a small scope of topics, namely the Work topic of DBpedia. Also, complex axioms are defined with the help of relational operators of intersection and union, which can also be mechanically derived from the known atomic axioms. To overcome that limitation, the type of mined class disjointness axioms in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] is extended to include the existence restriction (∃r.C) and value restriction (∀r.C) constructors, where r is a property and C a class, which cannot be mechanically derived from a given set of atomic axioms. Furthermore, a training-testing model is applied to objectively validate the method. Specifically, the whole DBpedia is used as the objective benchmark for evaluating the extracted axioms from a small training RDF dataset, i.e. sample of DBpedia, and eliminating the use of Gold Standard created by knowledge experts. The evaluation framework based on possibility theory [START_REF]An evolutionary approach to class disjointness axiom discovery[END_REF]- [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] to determine the fitness values of generated axioms in the evolutionary cycle, i.e. the credibility and generality of axioms. However, the selection pressure in each phases of the evolutionary process tends naturally to drive the diversity of the population down. In addition, the presence of highly fit but possibly invalid candidate axioms in the population reduces the number of valid axioms that can be discovered which can be derived from unsuited fitness function in evaluation framework which based on a single criterion.

Along the lines of the studies using GE to mine class disjointness axioms, we extend the approach as a multiobjective problem, i.e. multi-objective GE, in additition to the trade-off between a set of objectives. Specifically, we used an multi-objectives approach to refine the evaluation of candidate axioms that improves the adaptive fit of a population of candidate axioms constrained by two independent criteria, i.e. the credibility and generality. We also proposed a new measure called the similarity and a method to compute it. We aim to optimize the evaluation framework for the axioms which ensures the high accuracy, generality and the diversity of the obtained axioms. In the study, we reuse the grammar and the training-testing model to extract class disjointness axioms in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] and perform comparison with the relevant approaches.

The rest of the paper is organized as follows: some basics in GE and GE in axioms discovery are provided in Section II. Axiom discovery in multi-objective GE approach is presented in Section III. Section IV introduces the organization of dataset. The experimental settings and results are presented and discussed in Section V. Finally, conclusions and directions for future research are given in Section VI.

II. GRAMMATICAL EVOLUTION FOR AXIOM DISCOVERY

The foundation of our study is Grammatical Evolution (GE), a recent evolutionary model pioneered by Michael O'Neil and his collaborators [START_REF] O'neill | Grammatical evolution[END_REF]. In this section, we provide a summary of the GE in addition to theoretical and technical ingredients concerning axiom discovery.

A. Basics

Grammatical Evolution (GE) is an evolutionary approach that extends Genetic Programming (GP) [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF], [START_REF] Vanneschi | Genetic Programming -Introduction, Applications, Theory and Open Issues[END_REF] to allow the exploration of the space of computer programs through the use of a grammar-mediated representation. Programs, viewed According to it, the variable-length binary string genomes, or chromosomes, are split into consecutive groups of bits, called codons, representing an integer value, used to select, at each step, one of a set of production rules from a formal grammar, typically in Backus-Naur form (BNF), which specifies the syntax of the desired programs. Furthermore, inspired by biological evolution and its fundamental mechanisms, these programs are "bred" using iterative improvement of an initially random population of programs. That is an evolutionary process. At each iteration, known as a generation, improvements are made possible by stochastic variation, i.e., by a set of genetic operators, usually crossover and mutation, and probabilistic selection according to pre-specified criteria for judging the quality of an individual (solution). According to the levels of fitness, the process of selecting individuals, called fitness-based selection, is performed to create a list of better qualified individuals as input for generating a new set of candidate solutions in the next generation. The new solutions of each generation are bred by applying genetic operators on the selected old individuals. Then, replacement is the last step and decides which individuals stay in a population and which are replaced on a par, with selection influencing convergence. An illustration of the GE mechanism is presented in Fig 1.

B. BNF Grammar

In terms of axioms discovery, "programs" or "phenotypes" refer to axioms constrained by a given BNF grammar. A BNF grammar is a context-free grammar consisting of terminal and non-terminal symbols (also called just terminals and nonterminals) and being represented in the form of a four-tuple {N, T, P, S}, where N is the sets of non-terminals, which can be extended into one or more terminals; T is the set of terminals, which are tokens in the described language; P is the set of the production rules that map N to T ; S is the start symbol and a member of N . When there are a number of productions that can be used to rewrite one specific nonterminal, they are separated by the '|' symbol.

We comply with the BNF grammar given in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] to mine binary disjointness axioms only, of the form DisjointClasses(C 1 , C 2 ), where C 1 and C 2 may be atomic or complex classes involving relational operators, i.e. existential quantification and value restriction, and possibly including more than one single class identifier, like DisjointClasses(VideoGame, ObjectAllValuesFrom(hasStadium, Sport)). To make the paper self-contained, we recall here the most important aspects of this grammar. The grammar is split into a static and a dynamic part to ensure that changes in the contents of RDF repositories will not require the grammar to be rewritten. The static part defines the syntax of the types of axioms to be extracted. The content of this part is loaded from a hand-crafted text file. The structure of the BNF grammar here aims at mining well-formed axioms expressing the facts, i.e. instances, contained in a given RDF triple store. Hence, only resources that actually occur in the RDF dataset should be generated. The static part of the grammar is thus structured as follows:

The dynamic part contains production rules for the low-level non-terminals, called primitives in [START_REF] Nguyen | Learning class disjointness axioms using grammatical evolution[END_REF], [START_REF]An evolutionary approach to class disjointness axiom discovery[END_REF]. These production rules are automatically filled at run-time by querying the SPARQL endpoint of the RDF data source at hand. Let us consider an example representing a small sample of an RDF dataset: The productions for Class and ObjectPropertyOf would thus be:

PREFIX

C. Mapping Process

In the mapping process, codons are used consecutively to choose production rules in the BNF grammar according to the function: production = codon modulo Number of productions for the current non-terminal [START_REF] Völker | Learning disjointness[END_REF] We illustrate the decoding of an integer chromosome into an OWL class disjointness axiom through a specific example (see Fig 2). Let the chromosome be (352, 265, 529, 927, 419). There is only one production for the non-terminals Axiom, ClassAxiom, DisjointClasses, ObjectIntersectionOf, ObjectSomeValuesFrom and ObjectAllValuesFrom, as it can be seen from Rules 1-3 and 6-8. In these cases, we skip using any codons for mapping and concentrate on reading codons for nonterminals having more than one production, like in Rules 4, 5, 9, and 10.

III. MULTI-OBJECTIVE GE FOR AXIOM DISCOVERY

Within the evolutionary process, the evaluation framework quantifies the quality of axioms, which is the base for selecting individuals (solutions) for the recombination, mutation, and replacement phases. In previous work [START_REF]An evolutionary approach to class disjointness axiom discovery[END_REF]- [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF], the aim was to look for credible and general axioms, based on possibilistic axiom scoring for credibility and on a scoring of their generality. These two scores were then combined into a single fitness function, i.e., a single objective. The superiority of an axiom over other ones was simply determined by comparing their fitness scores. However, the fitness values can suffer from one of two objectives offsetting the other, for instance when a high generality score is assigned to axioms possessing a low possibility. In fact, the two criteria of generality and credibility are incommensurable and any way of combining them is therefore largely a matter of points of view, hard to justify on an objective basis. To overcome that limitation, we treat the problem as a multi-objective optimization problem, which allows for explicit trade-offs with respect to a set of objectives.

A. Multi-Objective Evolutionary Algorithms

A Multi-objective Optimization (MO) [START_REF] Deb | Multi-objective optimisation using evolutionary algorithms: An introduction[END_REF] problem involves a number of objective functions constituting a multidimensional objective space, in addition to the decision variable space. Specifically, a solution to a MO problem is a vector of decision variables x = (x 1 , x 2 , ...., x n ) T in the decision space X. For each x, there exists an objective vector y = (y 1 , y 2 , ...., y n ) T in the objective space Y mapped by a function f : X → Y .

The term domination is used for the situation of comparing two solutions x (1) and x (2) . A solution x (1) dominates the other solution x (2) (x (1) x (2) ) if x (1) is no worse than x (2) in all objectives (no component of y (1) is smaller than the component of y (2) , where y (1) = f (x (1) ) and y (2) = f (x (2) )), and x (1) is strictly better than x (2) in at least one objective (at least one component is greater). The set of optimal solutions in the decision space X is denoted as Pareto-optimal solutions or Pareto set. In addition, there are corresponding optimal objective vectors, i.e. points, in the objective space Y , denoted as Pareto-optimal front or non-domination front. In MO, all objectives are equally important, i.e., finding the optimum solution cannot be based on one objective alone while skipping other objectives. The goal of MO is to find multiple solutions Fig. 2. An illustration of mapping process representing the possible non-dominated trade-offs among the objective functions, i.e., a set of solutions lying on the Paretooptimal front. In addition, a set of obtained solutions is sought for that is also diverse enough to represent the entire range of the Pareto-optimal front. This results in a heuristic approach, the Multi-objective Evolutionary Algorithm (MOEA) [START_REF] Deb | Multi-objective optimisation using evolutionary algorithms: An introduction[END_REF], [START_REF] Zitzler | A tutorial on evolutionary multiobjective optimization[END_REF], which follows the goal of MO but refers to finding multiple non-dominated points as close to the Pareto-optimal front as possible, i.e., a Pareto-optimal front approximation, with respect to the trade-off among objectives. Also, it provides operators, i.e., recombination and mutation operators, to constantly improve the evolving non-dominated points.

NSGA-II [START_REF] Deb | A fast and elitist multiobjective genetic algorithm: NSGA-II[END_REF] is one of the well-known multi objective evolutionary algorithms, which simultaneously optimizes each objective without being dominated by any other solution. NSGA-II concentrates on finding non-dominated solutions in addition to elistist and diversity preserving mechanisms.

As a particular case of MOEA, the approach we propose comprises the integration of GE in MOEA i.e., using NSGA-II, for axiom discovery, which we call Multi-Objective GE (MOGE). Basically, the mechanism of MOGE is quite similar to the one of a MOEA, except that we define multi-objective problems using integer arrays called codons as decision variables. The codons do not define axioms, i.e., the programs, themselves, but provide instructions for deriving axioms using the BNF grammar through the mapping process explained above.

B. Multi-objective Evaluation Framework

The goodness of an axioms is determined by its dominance, whereby it obtains a score on each objective which is not dominated by the corresponding score of another axiom. To derive such axioms, we extend the classic GE approach presented in [START_REF] Nguyen | Learning class disjointness axioms using grammatical evolution[END_REF]- [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] to MOGE. We also develop separate objective functions to evaluate the fitness of each axiom. In order to ensure the diversity of the obtained axioms, a scoring of the similarity of each axiom to the other axioms in the population (essentially, a local phenotypic crowding measure) is also considered in the evaluation framework. In this section, we first recall axiom the scoring, regarding possibility and generality applied in [START_REF]An evolutionary approach to class disjointness axiom discovery[END_REF]- [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF]. In addition, we introduce a new scoring, called the similarity. Finally, the objective functions for the method are presented.

1) Possibility Measure: is based on possibility theory [START_REF] Zadeh | Fuzzy sets as a basis for a theory of possibility[END_REF], a mathematical theory of epistemic uncertainty. In the openworld, the knowledge base represented by RDF repository is incomplete. Additionally, as a results of the heterogeneous and collaborative character of the LOD, there exist some missing and erroneous facts (instances) in RDF datasets, i.e. noisy knowledge. Hence, adopting an axiom scoring heuristics based on possibility theory (see [START_REF] Tettamanzi | Possibilistic testing of OWL axioms against RDF data[END_REF] for the theoretical background) is well-suited. Accordingly, a candidate axiom φ is viewed as a hypothesis that has to be tested against the evidence contained in an RDF dataset. Its content is defined as a finite set of logical consequences

content(φ) = {ψ : φ |= ψ}, (2)
obtained through the instantiation of φ to the vocabulary of the RDF repository; every ψ ∈ content(φ) may be readily tested by means of a SPARQL ASK query. The support of axiom φ, u φ , is defined as the cardinality of content(φ). The support, together with the number of confirmations u + φ (i.e., the number of ψ for which the test is successful) and the number of counterexamples u - φ (i.e., the number of ψ for which the test is unsuccessful), are used to compute a degree of possibility Π(φ) for axiom φ, defined, for u(φ) > 0, as

Π(φ) = 1 -1 - u φ -u - φ u φ 2 .
Possibility alone is a reliable measure of the credibility of a class disjointness axiom, all the more so because (and this is a very important point), in view of the open world assumption, for two classes that do not share any instance, disjointness can only be hypothetical (i.e., fully possible, if not contradicted by facts, but never necessary). Possibility is measured by defining the numbers of counterexamples and the support. These values are counted by executing the corresponding SPARQL queries based on graph patterns, via an accessible SPARQL endpoint.

We refer the interested reader to [START_REF]An evolutionary approach to class disjointness axiom discovery[END_REF], [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF] for an in-depth description of the relevant SPARQL queries.

2) Generality measure: is determined by the quantities of the facts(instances), in the extension of its components. In [START_REF] Nguyen | Learning class disjointness axioms using grammatical evolution[END_REF], the generality of an axiom is defined as the cardinality of the set of the facts in the RDF repository reflecting the support of each axiom, i.e., u φ . However, in case one of the components of an axiom is not supported by any fact, its generality should be zero. Hence, the generality of an axiom should be measured by the minimum of the cardinalities of the extensions of the two class expressions involved, i.e. g φ = min{ [C] , [D] } where C, D are class expressions.

3) Similarity measure: quantifies the similarity of an axiom φ, s(φ), to the population of n axioms which is defined by the average of similarity metrics s(φ, a i ) between axiom φ and each axiom a i in the population:

s(φ) = 1 n -1 n i=1;ai =φ s(φ, a i ) (3)
In order to measure the similarity coefficient s(φ) as in the above formula, the similarities s(φ, a i ) need to be computed. Expressions in each axiom are represented in the form of binary trees where each node can be an atomic class or a relational operator, namely existential quantification (∃), value restriction (∀), or intersection ( ) operators. Determining each similarity between expressions, e.g., s(A, C), is performed on corresponding binary trees t 1 and t 2 . Binary trees are traversed simultaneously and each pair of corresponding nodes (p j , q j ) in both trees, i.e., p j in t 1 and q j in t 2 , is compared to each other and the value returned is the similarity between two nodes, i.e., s(p j , q j ), according to Table I. One notable point is that if both nodes represent atomic classes, the value returned is 1 if the two nodes represent the same class; otherwise the value returned is 0. Each similarity between expressions, e.g. s(A,C), is defined as

s(A, C) = 1 k k j=1 s(p j , q j ) (5)
where k is the number of pairs defined by the number of nodes in the smallest tree.

TABLE I MATRIX FOR THE COMPARISON BETWEEN NODES

Node

Atomic class

∃ ∀ Atomic class 0 or 1 0 0 0 0 1 0 0.5 ∃ 0 0 1 0 ∀ 0 0.5 0 1
4) Objective Functions: are used for the comparisons between axioms which reflect the correlation of measures to determine the quality of each axiom. We propose two objective functions, f 1 and f 2 , used in our approach, which aim at obtaining axioms that maximize the value of possibility and generality, while not being too similar among themselves:

       Maximize f 1 = Π(φ) • 1 -s(φ) 2 Maximize f 2 = g φ • 1 -s(φ) 2 Where 0 ≤ Π(φ) ≤ 1; g φ ≥ 0 ; 0 < s(φ) < 1 (6)

IV. DATASET ORGANIZATION

To investigate the effectiveness of our approach, we organize our dataset following the "training-testing" model. Specifically, the learning process is performed with the input data source derived from a training RDF dataset, a random sample of DBpedia, whereas the evaluation of discovered axioms is based on a testing dataset, which is the full DBpedia, which can be considered as an objective benchmark. The workflow of this model is shown in Fig 3. We use the same Training Dataset2 (TD) used in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF], with 6,739,240 connected RDF triples with a variety of topics from DBpedia, which randomly collect 1% of the triples from DBpedia 2015-04 (English version).The performance of the method is measured by using the entire DBpedia 2015-04 as a test set, measuring possibility, generality, and similarity scores for every distinct axiom discovered by our algorithm. To avoid overloading DBpedia's SPARQL endpoint, we set up a local mirror using the Virtuoso Universal Server. 3

V. EXPERIMENTS & RESULTS

A. Experimental Protocol

We use the BNF grammar introduced in Section II. In addition, to make fair comparisons possible with previous studies [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF], a set of milestones of total effort k (defined as the total number of fitness evaluations) corresponding to each population size are also recorded for each run, namely 100,000; 200,000; 300,000 and 400,000, respectively. The maximum numbers of generations, maxGenerations (used as the stopping criterion of the algorithm) are automatically determined based on the values of the total effort k, thus popSize • maxGenerations = k.

A prototype system of the proposed method was developed in Java, using Apache Jena to interface with SPARQL endpoints and GEVA v.2.04 , a reference Java implementation of GE. Also, we integrated the system with the MOEA framework API, 5 a Java framework for multi-objective optimization. The parameters are listed in Table II.

B. Results

We ran the MOGE method for 20 distinct runs for each of the different parameter settings summarized in Table II, using the BNF grammar defined in Section II-B. The full set of valid distinct axioms, i.e., axioms φ such that Π(φ) > 0 and g φ > 0 discovered are available online. 6 Statistics for automatically generated axioms are presented in Table III. In addition, we can see in Fig. 4 that the number of valid distinct axioms for most parameter settings, i.e., population size popSize and total effort k, mined by MOGE is significantly greater than those mined by the single-objective GE method in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF]. This means that the diversity of an extracted set of axioms is considerably enhanced when we use the MOGE method. Furthermore, we follow the use of the fuzzy extension of the usual definition of precision in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] to measure the accuracy of our results. Accordingly, Π(φ) is interpreted as the degree of membership of axiom φ in the (fuzzy) set of the "positive" axioms. The value of precision can thus be computed against the test dataset, i.e., DBpedia 2015-04, according to the formula precision = true positives discovered axioms

= φ Π DBpedia (φ) φ Π TD (φ) . (7)
where Π TD and Π DBpedia are the possibility measures computed on the training dataset and DBpedia, respectively. The results in Table IV confirm the high accuracy of the proposed MOGE method. The precision values are quite equivalent to the figures of GE method [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF] with the range from 0.984 to 0.996 for all the different considered population sizes and different numbers of generations (reflected through the values of total effort). in terms of the two objectives, i.e. possibility and generality, compared with the GE methods of [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF]. We perform the comparison based on the results of the best setting, i.e., those yielding the largest number of obtained distinct axioms and the highest accuracy, for either method, i.e., {popSize = 10, 000; k = 200, 000} and {popSize = 5, 000; k = 300, 000}, respectively. We can observe that the number of highly qualified axioms (Π(Φ) > 2 3 and g Φ > 100)) is maintained in MOGE system. More clearly, based on the specific resulting statistics, the number of obtained axioms from MOGE in the best setting is 38, 134 which is much greater than those extracted by the GE, i.e., 23, 767 axioms. In addition, with the smaller value of total effort k reflecting the cost of evaluations, i.e., k = 200, 0000 compared with k = 300, 000 in [START_REF]Using grammar-based genetic programming for mining disjointness axioms involving complex class expressions[END_REF], [START_REF]Grammatical evolution to mine OWL disjointness axioms involving complex concept expressions[END_REF], MOGE is clearly more effective in inducing highly qualified axioms. We also show the distribution of the discovered axioms in this best setting in terms of similarity coefficient in Fig. 6. The range of similarity scores recorded for these axioms lies below 0.35, which indicates a good diversity of the classes and properties in the components of axioms. Based on the given grammar, one part of the axioms is forced to contain a relational operator, i.e. ∃, ∀, or , hence, the overlap of the operators in axioms does not allow the similarity score to be zero.

According to the results, we consider in detail the axioms discovered by the algorithm with this best setting. First, we witness that the number of obtained axioms containing the ∃ operator is slightly larger than the one of those with the ∀ operator, namely 40,122 and 36,682 axioms, respectively. However, together with the mandatory class expression containing the ∀ or ∃ operator, most extracted class disjointness axioms contain an atomic class expression. This may be due to the fact that the support of atomic classes is usually larger than the support of a complex class expression. Specifically, we obtain 7 axioms containing complex expressions in both their members. These axioms are less general, even though they are completely possible. An example is the case with DisjointClasses(ObjectAllValuesFrom(dbprop:operation dbo:MilitaryConflict) ObjectAllValuesFrom(dbprop:order dbo:MIlitaryUnit))(Π(φ) = 1.0 ; g φ = 1). Also, we analyze an example of a completely possible and highly general axiom, DisjointClasses(dbo:District ObjectSomeValuesFrom(dbo:birthPlace dbo:Place)) (Π(φ) = 1.0 ; g φ = 8, 483), which we can paraphrase as "districts cannot have a place as their birthplace". Knowing that District and Place are not disjoint, this axiom states that District and ∃birthPlace.Place are in fact disjoint; in addition, ∃birthPlace.Place, i.e., "(people) whose birthplace is a place" is a class with many instances, hence the high generality of the axiom.

GE MOGE

VI. CONCLUSION

We have proposed a multi-objective extension to a grammarbased genetic programming approach to axiom discovery which consists of using two objectives plus a "similarity" score, which is in fact a sort of a local phenotypic crowding factor. The experimental results confirm that the proposed method is capable of discovering highly accurate and general axioms and is more effective compared with the singleobjective methods of previous studies. In the future, we will focus on mining disjointness axioms involving further types of complex classes, by bringing into the picture other relational operators such as owl:hasValue and owl:OneOf. We also plan on refining the evaluation of candidate axioms with the inclusion of some measurement of their complexity in the fitness function.

GE MOGE

Fig. 1 .

 1 Fig. 1. Grammatical Evolution mechanism

  As mentioned in II-B, axioms are structured in the form of binary axioms of the form φ ≡ DisjointClasses(A, B) and a i ≡ DisjointClasses(C, D) where A, B, C, D can be atomic expressions or complex expressions containing relational operators of restriction, i.e., existential quantification and value restriction. We define the similarity between two axioms based on the similarities between pairs of expressions as s(φ, a i ) = max{s(A, C), s(A, D), s(B, C), s(B, D)} (4)

Fig. 3 .

 3 Fig. 3. Workflow of class disjointness axioms discovery using GE in the training-testing model

Fig. 5

 5 illustrates the distribution of axioms having Π(φ) > 2 3

Fig. 4 .

 4 Fig. 4. Statistical comparison about the number of axioms discovered over 20 runs between MOGE and GE method.

Fig. 5 . 3 Fig. 6 .

 536 Fig. 5. Possibility and generality distribution of the discovered axioms with Π(φ) > 2 3

TABLE II PARAMETER

 II VALUES FOR MOGE.

	Parameter	Value
	Total effort k	100,000; 200,000; 300,000; 400,000
	initLenChrom	6
	pCross	80%
	popSize	1000; 2000; 5000; 10000

TABLE IV AVERAGE

 IV PRECISION PER RUN (±std)

			GE				MOGE
	X k X X 100,000 X X popSize X X	1,000 0.981 0.019	2,000 0.999 ±0.002	5,000 0.998 ±0.002	10,000 0.998 ±0.003	1,000 0.988 ±0.007	2,000 0.990 ±0.005	5,000 0.989 ±0.003	10,000 0.996 ±0.001
	200,000	0.973 ±0.024	0.979 ±0.011	0.998 ±0.001	0.998 ±0.002	0.989 ±0.007	0.990 ±0.004	0.987 ±0.004	0.988 ±0.004
	300,000	0.972 ±0.024	0.973 ±0.014	0.993 ±0.007	0.998 ±0.001	0.989 ±0.007	0.989 ±0.003	0.986 ±0.004	0.986 ±0.003
	400,000	0.972 ±0.024	0.969 ±0.018	0.980 ±0.008	0.998 ±0.001	0.989 ±0.008	0.990 ±0.003	0.985 ±0.004	0.984 ±0.004

https://wiki.dbpedia.org/

Available for download at http://bit.ly/2OtFqHp

https://virtuoso.openlinksw.com/

http://ncra.ucd.ie/Site/GEVA.html

http://moeaframework.org/javadoc/index.html

https://bit.ly/38crj4M

ACKNOWLEDGMENTS

This research was carried out in the Wimmics team, which is a joint research team of Université Côte d'Azur, Inria, and I3S. Our research motto: AI in bridging social semantics and formal semantics on the Web. This work has been partially supported by the French government, through the 3IA Côte d'Azur "Investments in the Future" project managed by the National Research Agency (ANR) with the reference number ANR-19-P3IA-0002.