Toward a systematic conflict resolution framework for ontologies

Background The ontology authoring step in ontology development involves having to make choices about what subject domain knowledge to include. This may concern sorting out ontological differences and making choices between conflicting axioms due to limitations in the logic or the subject domain semantics. Examples are dealing with different foundational ontologies in ontology alignment and OWL 2 DL’s transitive object property versus a qualified cardinality constraint. Such conflicts have to be resolved somehow. However, only isolated and fragmented guidance for doing so is available, which therefore results in ad hoc decision-making that may not be the best choice or forgotten about later. Results This work aims to address this by taking steps towards a framework to deal with the various types of modeling conflicts through meaning negotiation and conflict resolution in a systematic way. It proposes an initial library of common conflicts, a conflict set, typical steps toward resolution, and the software availability and requirements needed for it. The approach was evaluated with an actual case of domain knowledge usage in the context of epizootic disease outbreak, being avian influenza, and running examples with COVID-19 ontologies. Conclusions The evaluation demonstrated the potential and feasibility of a conflict resolution framework for ontologies.

Background
Use of ontologies keeps gaining traction, which motivates more ontology development and therewith the prospects and task of reusing existing ontologies in whole or in part. Reuse is not only less demanding on the resources than starting with a clean slate and re-inventing the wheel, but it also may foster interoperability across information systems. It is already a key component of the OBO Foundry approach for bio-ontologies [1] and it is incorporated in ontology development methodologies such as NeON [2]. The concrete steps for reuse could involve redesign of a single ontology or the importing or merging of one ontology with another ontology or it may be added to a *Correspondence: rolf.gruetter@wsl.ch 2 Swiss Federal Research Institute WSL, Zürcherstrasse 111, CH-8903 Birmensdorf, Switzerland Full list of author information is available at the end of the article complex network of integrated ontologies. Some of the myriad examples of different strategies are the top-down approach with the Infectious Diseases Ontology (IDO) within the OBO Foundry [3] and the re-configurable BioTop where modules can be exchanged thanks to multiple alignments [4]. Assessing the potential for (re)use can be difficult, where even one choice can lead to further research, such as which parthood [5,6], or avail of software-based assistance to choose quickly [7].
A candidate ontology for reuse may not have all the desired axioms or have much more than needed, and, once imported and aligned, may result in an inconsistent or incoherent ontology or be beyond the desired OWL species, or otherwise incompatible. Reuse experiences vary widely also in the biology domain; recent examples include reuse of the IDO with a simulation modeling ontology together with schistosomiasis knowledge [8], the modular design and many reuses of the Gene Ontology [9], and examining subtle differences across disease ontologies even before reuse [10]. For instance, two domain ontologies each may be aligned to a different foundational ontology, which may have representational differences where one ontology has a property vaccinates but the other uses a class Vaccination where they intended to mean the same general notion but one chose the process and the other its reified variant, or there are subject domain disagreements, like one having asserted that Virus is an organisms and the other does not.
Although it can seem overwhelming to assess extant ontologies and to just discard them to start from scratch again, we assume that a modeler would not wish to duplicate work and rather attempt to resolve any issues that may arise. How should one do this? Currently, this proceeds on an ad hoc basis, where one may not even be aware of what one should be looking for until the problem manifests itself. There are a few tools that assist with detecting conflicts, such as the explanations generated in Protégé [11], checking the differences in inferences obtained [12], the OWL Species Classifier 1 that pinpoints which axiom(s) violate which OWL species, and one can test if adding a particular axiom is going to cause problems before actually adding it [13]. Such tools, however, do not detect all sources of conflicts, such as between fundamental assumptions about a domain or preferred theories; e.g., the choice between either parthood or connection or both as primitive for a mereotopological theory [14] and whether it is "better" for one's domain to declare parthood transitive or use it in qualified number restrictions since one cannot have both in OWL 2 DL [15]. It then requires an overview of the options and consequences, as illustrated next.
Example 1 An OWL ontology O 1 about anatomy has declared that a biped is an animal that has_part exactly two legs (biped animal = 2 has_part.leg). When this o1 : has_part is aligned to the DOLCE ontology in OWL, a tool such as Protégé will report a clash, due to that dolce : haspart is declared as transitive, and therefore the default installed automated reasoner will not work. What can the modeler do? Their main options are: i. do not align to DOLCE; ii. give up on the qualified cardinality constraint and modify the definition of biped; iii. import DOLCE and remove transitivity, rendering it de facto incompatible with DOLCE; iv. accept to go beyond OWL 2 DL and use a different logic with little to no tool support; or, v. forsake automated reasoning over one's ontology. 1 https://github.com/muhummadPatel/OWL_Classifier/ The options have consequences that are all less optimal compared to the (impossible) intention.
The consequences of each choice still have to be assessed in some way, which may leave the ontologist to resort to trial and error attempts, which hampers redeployment of ontologies, also because the consequences of possible solutions may not be clear.
We aim to ameliorate these issues by devising an approach for meaning negotiation and conflict resolution in the ontology development and (re)use processes. The possible principal sources of conflict for both individual ontology development and networked multiple ontologies are examined. For each underlying source and type of conflict, there is a fixed set of feasible solution strategies, which will enable automatic generation of explanatory implications. Some of the components of the conflict resolution process can be computed automatically, but it is unavoidable to keep a human-in-the-loop who makes the final, but now well-informed, decision. The approach is illustrated and evaluated with a case study of ontology reuse to manage an epizootic disease outbreak (avian influenza) in Switzerland, involving negotiation and resolving conflicts concerning the suitable mereotopological theory and trade-offs with OWL species. Smaller examples throughout the paper are drawn from COVID-19 ontologies. This paper extends the authors' ICBO2020 paper [16] in a number of ways. It contains a larger preliminary library of conflicts, an extended case study, more examples with existing ontologies, and a conflict resolution walkthrough with a corresponding specification of software requirements.
The remainder of the paper is structured as follows. In the "Methods" section, an approach to meaning negotiation and conflict resolution is introduced. The use case is presented in the "Results" section. The "Discussion" section zooms in on system requirements for software support for conflict negotiation. "Conclusions" are drawn in the last section.

Methods
We first distinguish between meaning negotiation and conflict resolution. Subsequently, we introduce a preliminary 'library' of conflicts and the conflict set data structure that stores the minimum necessary data about such conflicts to be used for resolution, and then proceed to resolution strategies.

Characterizing meaning negotiation and conflict resolution
Negotiating the meaning of the knowledge-classes, properties, and axioms-to be represented in an ontology involves reaching an agreement on: 1) the exact elements required, 2) the domain theory that will provide these elements, and 3) the required ontology language to represent the former. Each item may involve meaning negotiation and conflict resolution. This will be disambiguated and illustrated first, after which potential sources of conflict are identified and the conflict set is introduced.

Types and sources of conflicts
We define informally the concepts of meaning negotiation and conflict resolution, which will be illustrated afterward.
Meaning negotiation concerns deliberations to figure out the precise semantics one wants to represent in the ontology. They are all positive choices in the sense of "which of the options is applicable? Then we take that one". Conflict resolution concerns choosing one option among a set of two or more options, where that choice is deemed the 'lesser among evils' for that scenario. It necessarily involves a compromise and making it work requires reengineering something in at least one of the ontologies or as a whole. Subtypes include: Language conflict resolution A conflict arises within the same family of languages or with a m ore distant one. This is either a zero-sum game (i.e., with a winner and a loser) or there may be a joint outside option. Ontological conflict resolution The ontologies adhere to different theories, which may be foundational philosophical decisions that affect the overall structure of the ontology or subject domain arguments with competing theories. This is likely a zero-sum game of either-or (no joint outside option).
They are illustrated in the following example.
Example 2 Meaning negotiation may involve assistance with explanations for the modeler, such as when they do not know whether to give up reflexivity for scalability, to offer them a dialogue alike "if you don't have reflexivity, you'll miss these sort of inferences: [example goes here]", or one can frame negotiation of alternatives as an imperative, e.g., "take either parthood or proper parthood as primitive for your mereological theory, but not both.".
Conflict resolution applies in many cases; e.g., there are several common types of language conflicts, such as: •  [17], which is a meta-language that provides the 'glue' between ontologies represented in different languages, including more expressive ones. This strategy was illustrated in [5] for mereotopological theories.
The language's semantics can be an example of a zerosum game, such as to either embed the UNA in the semantics or not, but it cannot be both, and it affects the reasoner's deductions. For instance, consider some ontology O1 that contains C = 1 R.D together with the assertions {R(a1, b1), R(a1, b2), C(a1), D(b1), D(b2)}. Under no-UNA such as with OWL, it will deduce b1 = b2, because it is the only way to satisfy the = 1 constraint; under UNA, it will deduce the ontology is inconsistent because is violating the = 1 constraint in the TBox.
An example of an ontological conflict is a clash in the top-level organization of the ontology, such as between BFO and GFO, and related philosophical differences, such as qualities with qualia vs trope theory to represent attributes [18]. At the subject domain level, this may be, e.g., whether a virus is a living thing or not and competing scientific theories more generally. They do not have a joint outside option because the theories conflict, except returning it to the domain experts to resolve (e.g., to conduct experiments).
What are the sources of such conflicts? The sources can be manifold and six principal cases were discerned, which are non-exclusive and possibly also not an exhaustive list: 1 Ontological differences between established theories; e.g., extensional mereology vs. minimal mereology and DOLCE vs. BFO as top-level ontology. 2 Ontological differences at the axiom-level; e.g., not all philosophers agree on whether the parthood relation is antisymmetric [19]. 3 Different modeling styles; e.g., foundational ontologyinspired or conceptual model-influenced, resulting in, e.g., reifying verbs into classes or adding them as object properties, respectively, [20], like the Vaccination/vaccinates mentioned in Fig. 1. 4 Logic limitations causing conflicts for an ontology, affecting the software ecosystem; e.g., the biped's haspart being either transitive or have it participate in axioms with qualified cardinality constraints in OWL 2 DL, or facing this clash when trying to merge or integrate two ontologies. 5 Logic limitations by design, for the purpose of scalability; e.g., there are axioms in one's ontology that are beyond the desired OWL species, so that one has to choose either to abandon the preferred species or to remove the axioms. 6 Certain deductions made by the reasoner (excluding modeling mistakes); e.g., an unsatisfiable class resulting from disjoint ancestors that were aligned. While this may also have as source an ontological difference at the axiom-level, it would manifest either after adding the axioms, during test-driven development (TDD) [13], or upon ontology matching attempts.
The first three are, in principle, a priori negotiations by an ontologist, but may manifest only upon ontology matching. Cases 4 and 5 emerge during ontology authoring. The last one may or may not be a priori. They will be elaborated on in the "Resolving conflicts" section further below.

The conflict set
Conflict detection offers opportunities for automation and, even though there is no single way of how conflicts can be detected, some tasks can be carried out with the aid of state-of-the-art ontology development environments (ODEs), which we elaborate on afterward and its requirements emanating from that in the "Discussion" section further below. The data structure in which the detected conflicts are stored and upon which the resolution of conflicts operates, is called the conflict set, which is generated in all cases where a conflict is detected. Without loss of generality, it is assumed that, when matching more than two ontologies, a conflict set is generated for every pair of ontologies.
The conflict set is described in a context-free grammar in Backus-Naur Form, as shown in Fig. 2, for purposes of genericity, as such a grammar can be implemented easily in most programming and rule languages and enforce verification of correctness of any implementation of the conflict sets. Accordingly, there are two ontologies or two fragments of the same ontology, each identified by an IRI or another identifier and composed of a (possibly singleton) set of axioms. An axiom may adhere to an ontologically well-founded theory, such as ground mereology, or some domain theory. It is briefly illustrated in the following example with the Virus Infectious Diseases Ontology (VIDO) and the COVoc vocabulary, whereas a more comprehensive case is deferred to the case study in the "Results" section. Fig. 2 is illustrated in 'pretty printing' notation with VIDO and COVoc, noting that we assume that acellular structure organism ⊥ is present in the ontology, following VIDO's accompanying documentation [21]  The explanation thereof, which assists toward resolution of this conflict at the subject domain level, will be elaborated on in the next section, and its Fig. 5 in particular.

Resolving conflicts
In practice, conflict resolution often starts with some issue raised by the ODE, and specifically when an axiom is added or an ontology is merged or integrated into the active ontology. Examples of such issues are undecidability, language profile violation, and incoherence. They can be seen as cues indicating that something is wrong with the active ontology. The author then has to find out what raised the issue. Thereby, they may be supported by the ODE. Proceeding that way is not as straightforward as one might expect, because there is no one-to-one correspondence between conflict and issue. Examples of such 'causal investigations' will be given in the following subsections. For the rest of this section, the following principal choices are presupposed: (i) The ontology author adheres to Occam's razor when developing an ontology for the case at hand: the least expressive language in which the required axioms can be represented fully is preferred over all more expressive ones. (ii) The ontology author wants to capture as much of the semantics of the domain theory as possible. (ii) The ontology author prefers a decidable language over first or higher order logic for representing a domain theory and a coherent ontology over an incoherent one (that suffers from at least one unsatisfiable class). The first choice is a general principle in many situations in life. The second choice assumes that the author prefers representing a full axiomatization over a partial axiomatization and, by extension, a partial one is better than mere primitives without any axioms. While the third choice may not hold in all situations, we deemed it realistic to include, since most software infrastructure caters for decidable ontology languages and coherent ontologies, and Semantic Web and Knowledge Graph languages in particular.
We now proceed to discuss the conflicts listed in Table 1 in their order of presentation.

Conflicting top-level and domain theories
If an ontologically well-founded theory underlying some axioms to add or an ontology to integrate is in conflict with the ontology representing the desired theory (nos. 1-3 and 5 in Table 1), then the respective IRIs must be added to the conflict set. This presupposes that the conflict is known and the pair of IRIs is already listed somewhere, for instance, in a library of common conflicts.
To give an example, if one wants to add the part-whole relations taxonomy [22] that is aligned with DOLCE to a BFO-aligned IDO [3], then the theory conflict 'BFO vs. DOLCE' will be detected through looking up the library of common conflicts. Conflict resolution, in this case, aims cultural-linguistic and labeling differences, such as preferred/alt labels, orthography, language variants population immunity vs herd immunity, eraser vs rubber, color vs colour, and non-1:1 mappings where a concept is named in one language but not in another (e.g., 'river' vs fleuve and rivière) at preserving a consistent theory. Since for conflicting theories there is no joint outside option, the ontology author has to decide in favor of one theory and discard the other. Their decision may be informed by the deliberations of what should be represented in the ontology made during meaning negotiating.
ODEs support the import of ontologies and after import, their IRIs can be read from the metadata of the active ontology and looked up manually for common conflicts in a library. Accordingly, this conflict detection approach is straightforward to implement. Uncommon conflicts are harder to detect and therefore harder to resolve. The use of ontology design patterns [23] for a theory would be helpful in automating detection, as would annotations that describe which theory is being represented. In addition, the library of common conflicts may grow upon finding more conflicts, be this automatically or manually curated or both, so that it can prevent the same or a similar conflict from emerging later on in the project.
Taking a step back from practicalities like checking the IRIs, there may be ontological commitments at stake underlying differences in IRIs. A straightforward example of commitments and a foundational ontology that satisfies them would be "Universals, Realist, Concrete entities only", which BFO meets [24]. One may have other preferences for commitments that do not agree fully. For instance, one may want an ontology for representing particulars, take a realist stance, yet also admit to a multiplicative approach where one admits to a difference between, e.g., the vase and the clay that it is made of. DOLCE and GFO, and SUMO each can only meet two of the three requirements, as illustrated in Fig. 3, and one then either has to change the requirements or accept that not all of them will be met and, in case of the latter option, which one is going to be traded in to compromise.
The top-level theory conflict listed in line No. 4 in Table 1 concerns ontologically irreconcilable differences that are embedded in the language that is used to represent the ontology in. This issue is described at length in [25] and its Table 2 lists the assessment of ontological features by ontology language, which can be applied for detecting conflicts. For instance, if one is convinced of the separation between natural language with labeling things one the one hand and the things themselves with their representation in logic on the other, then OBO is a good choice. Contrast this to OWL, which assumes the two are intertwined in that the classes and properties are expected to have human readable names. It is possible to convert one into the other, but it remains a brittle workaround due to the fundamental difference: practically, it acts out in 'OBO style' identifiers as names for classes and object properties in an OWL file with a hopeful wish that their labels are rendered in the tools. However, OWL assumes the elements are named and therefore labels are not mandatory, resulting in situations where the 'OBO style forced into OWL' occasionally breaks and one is left with only meaningless identifiers.
Conflicting theories at the subject domain level (nos. 5-6 in Table 1) may act out, and be detected and resolved, in two different ways. First, if each domain theory was represented in an ontology and had its own IRI, then one could use the same resolution approach as for the toplevel theory issues of nos. 1-3 described above. Second, particularly in the case of fine-grained aspects like the status of an element, then they can be processed and resolved as for axiom-level conflicts, which will be described below and illustrated with a follow-up of Example 3.

Fig. 3
Explanation generated by ONSET [7] after having selected a combination of requirements for ontological commitments "Particulars, Realist, yet Multiplicative" that no foundational ontology can fully meet and whose conflict needs to be resolved at this requirements analysis stage

Conflicts manifesting themselves in an undecidable language
With conflicts nos 7-8 in Table 1, conflict resolution aims at preserving a decidable ontology language or raising awareness of undecidability when opting for a joint outside option. In the first case, this most often is a zero-sum game: the ontology author has to chose which one(s) of the conflicting axioms in the conflict set to keep and which one(s) to delete. For mereotopological theories, these types of conflicts have been investigated [5]: in most instances, incorporating a full axiomatization renders the active ontology at least undecidable, and possibly also incoherent. To support the author's decision, some criteria can be established for how to compute the possible resolution choices, such as the following: • The least number of axioms are affected; • The preferred axiom type is identified by assigning weights to classes, properties, or types of constraints; • The least number of inferences are lost.
The least number of axioms affected can be read from the conflict set that was computed in detecting the conflict. Assigning weights to axiom types implies that certain types are a priori considered more valuable than others; e.g., one may weigh existentially quantified properties in axioms more than universally quantified properties and unqualified cardinality more than qualified cardinality. The least number of inferences lost requires an additional step where the inferences of the ontologies are computed and recorded in the conflict set. If undecidability is caused by an ontological conflict at the axiom-level that was not resolved along with conflicting theories (e.g., weak vs. strong supplementation in Example 4), then also the decisions taken when negotiating meaning upfront may serve as a criterion. The authors' decision and the criteria upon which it is based ideally should be recorded so as to keep track of the decision made and in case the same or a similar conflict emerges later on in the project.
The second case, i.e., opting for a joint outside option, requires that principal choice (iii) (preferring a decidable language) is relaxed. Theories that are represented in different logics can be dealt with by the DOL framework [17]. This includes cases where the resulting logic is undecidable.
State-of-the-art ODEs provide some support for detecting and resolving these kinds of conflicts. To give an example, the OWL API [26] of Protégé 5 [27] issues an error message reporting the conflict arising from a violation of the expressive OWL 2 DL specification, which may render the language undecidable, when it is caused by a non-admissible axiom combination such as those listed in Example 4. In addition, Protégé 5 is equipped with an OWL reasoner, and a diff tool for computing the differences between OWL ontologies is available as a plug-in [28]. In order to compute the number of inferences lost, the axioms inferred from the merged ontology are first computed using the OWL reasoner. This requires that the merged ontology is saved as two decidable versions by removing one conflicting axiom set in exchange for the other. The difference between the sets of inferred axioms is then computed and returned to the modeler to inform them about the consequence of that particular choice.

Conflicts manifesting themselves in a language profile violation
This may occur in particular with conflict no 8 of Table 1, but may also appear as a confounding issue in conflict 7. The case where resolution aims at preserving the language to the extent that it is decidable again, while accepting that the original profile is violated, has to be distinguished from the case where the original language profile should be preserved. Presupposing aforementioned principal choices, conflict resolution in the first case aims at capturing as much of the semantics of the domain theory as possible. Since the language profile that was violated may not be the most expressive one, there may be room for a (decidable) joint outside option. To give an example, the 'overlap' axiom O(x, y) = def ∃z(P(z, x) ∧ P(z, y)) cannot be expressed in any decidable OWL species, because it does not admit property definitions in the language. That is, the syntax does not permit usage of equivalence for object properties and, in fact, even puts limitations on property subsumption so as to prevent cycles in the hierarchy (called a "regular" role hierarchy [29]). While preserving decidability, the author may still want to state that P(z, x) ∧ P(z, y) is a sufficient condition for O(x, y) or they may want to state that O(x, y) is a reflexive and symmetric property. Yet, doing so may violate the original language profile. Whether the ontology language still is undecidable with the modified axioms and conditions can be figured out in the same way as described in the previous section, about Conflicts Manifesting Themselves in an Undecidable Language. Weakening the theory step by step this way will end up in a representation such that the language features used remain within a decidable language, since the representation of properties as mere primitives is always possible in OWL and other ontology languages.
In the second case, conflict resolution aims at preserving the original language profile at the expense of relaxing principal choice (ii), i.e., accepting that 'as much semantics as possible' is less than anticipated. This applies to conflicts emerging from what is called design for scalability in the "Types and sources of conflicts" section, above. Here, conflict resolution is likely to be a zero-sum game similar to that described in the section about undecidability. For instance, the OWL 2 QL profile is aimed at applications that use very large amounts of data, such as conventional relational database systems, and where query answering is the most important reasoning task. Violating this profile then means accepting that query answering may no longer be implementable by rewriting queries into a standard relational query language [30].
Concerning tool support for these two cases, in the first case, it is the same as that described in the preceding section about undecidability. For the second case, the OWL Species Classifier supports authors of OWL ontologies by listing which axioms violate which OWL species (see footnote 1). An illustration of the benefits of this sort of automation is described in the following example, where the classifier was used to search through the 417 axioms of the CIDO ontology for COVID-19 [31] to check for profile violations, compared to manually searching for a possible needle in a haystack.

Example 5
Practically, medical ontologies for information systems typically do not exceed the OWL 2 EL profile, because of scalability and compatibility with typical OBO Foundry ontologies and SNOMED CT, so let us assume this as a requirement. CIDO [31] is not within OWL 2 EL, however, which is due to a class expression with a universal quantifier on the right-hand side; more specifically, as easily pinpointed by the OWL Species Classifier (see Fig. 4

Conflicts manifesting themselves in an incoherent ontology
Conflicts nos. 7-8 in Table 1 may also manifest themselves as an incoherent ontology, with one or more unsatisfiable classes or properties (observe that conflict no. 7 includes any remaining unresolved theory-level conflicts of nos. 1-3, 5, and 6). Conflict resolution in this case aims at preserving or obtaining a coherent ontology. Examples include ontological misspecifications at the axiom-level, such as disjoint ancestors, resulting in unsatisfiable classes (no. 7 in Table 1). Such conflicts manifest only when the automated reasoner reports the deductions; an example is shown in Fig. 5. In the simplest case, they are resolved by keeping some of the conflicting axioms and removing others in a way similar to that described in the section about undecidability, above. Typically, either the disjointness axiom on the ancestors or the subclass axioms on the class may be kept, but not both. State-of-theart ODEs allow for making deductions. After running the OWL reasoner in Protégé 5.x, for instance, unsatisfiable classes and properties are displayed in red color.
In order to find out what made them unsatisfiable, justifications can be computed using the respective plug-in, where a justification is a set of axioms from an ontology that is sufficient for an entailment to hold [11]. In the case of unsatisfiable classes and properties, justifications are computed for entailments with owl:Nothing and owl:bottomObjectProperty on the right-hand side of the inclusion axiom, enabling identification of the source(s) of incoherence.

Conflicting modeling styles and language issues
These conflicts arise from source 3 listed at the start of the "Methods" section and concern the 'other conflicts' , being nos. 9-10 listed in Table 1. Resolving them aims Fig. 4 Section of the OWL classifier, having detected that CIDO_0000020, i.e., Yale New Haven Hospital SARS-CoV-2 assay, is one of the class expressions violating the OWL 2 EL profile at restructuring (parts of ) an ontology such that correspondences with entities of a different ontology can be established. For instance, if the same notion is modeled in one ontology as a class and in another as an object property (see Fig. 1), or even in both ways in the same ontology, and the ontology language does not permit heterogenous alignments, then either the object property has to be reified or the class has to be recast as an object property (see no. 9 in Table 1). Typical examples are object properties such as o1:married-to and o1:has-member and corresponding reifications as o2:Marriage and o2:Member, respectively. A concrete difference in modeling choice in two ontologies in the same domain is illustrated in Example 6. CIDO (v1.0.181), there is also the CODO [32] (v1.3 of 25-9-2020), which focuses predominantly on patient data and therewith alike a practice-oriented application ontology. CODO's COVID-19 test results are represented as codo:'laboratory test finding' ≡ {positive, pending, negative}, i.e., the outcomes are instances and, within the context of the other content in the ontology, practically conflated with the diagnosis of the disease. In contrast, CIDO is informed by the BFO top-level ontology with its modeling guidelines and has a cido:'COVID-19 diagnosis' class with three subclasses: negative COVID-19 diagnosis conclusion, and one for positive and one for presumptive positive. Aside from disagreeing on names and possibly also the meaning of possible test statuses, the modeling style issue here is that it is an example of class vs. instance modeling conflict of the same notion. Ontologically, the same notion cannot be both a class and an instance and should thus not co-exist in one ontology, hence, one of the two options will have to be chosen if they were to be integrated.

Example 6 Let us continue with COVID-19 ontologies. Besides the
What is recorded in the conflict set depends on the case at hand; for the class vs. property example, these would be the respective axioms to match and the axioms they are used in, which may be found by using a natural language processing-based algorithm with part-of-speech tagging and stemming. Generally speaking, there are two different options of dealing with conflicting modeling styles. The first is to choose one style and then convert instances of the 'losing' modeling pattern into the style of the 'winning' pattern, where each consists of one or more axioms, and the second option is to keep both styles and match patterns by a set of axioms, rather than by a single bridging axiom, which is referred to as a heterogeneous TBox mapping [20].
The way how ODEs deal with conflicting styles depends on the kind of conflict and the ODE. For instance, Protégé 5 restricts alignments to equivalence and simple subsumption between classes and between object properties. Simply put, it does not provide the necessary means to assert an alignment between a class and an object property. An algorithm for detecting conflicting modeling styles and additional axioms for heterogeneous alignment has been proposed [20], but this is yet to be integrated in an ODE. A joint outside option may be the DOL framework that already does have a logic-based mechanism for heterogeneous alignments [17].
Language conflicts (no. 10 in Table 1) may vary in severity. There are straight-forward differences in naming patterns, such as camel case naming versus using underscores between words in a term, which are detected by the OOPS! tool [33], and one can use a spelling checker to detect US English versus British English orthography and more advanced resources to assist with synonym detection and resolution. It will not yet resolve which English variant to use in an ontology. More detailed labeling of language aspects and a stricter separation of the language layer on top of the ontology layer may assist in resolving this. Promising proposals for such additional modeling are the Ontolex-lemon community standard [34] and the MoLA [35] language annotation model. Then, instead of an either-or choice for one way of labeling, it can be both-and with an arbitrary number of alternative labels.

Results
The framework proposed here is tested against a realistic case of epizootic disease outbreak in the Lemanic Arc (France, Switzerland) in 2006 [36]. To this end, case records of three occurrences of human-pathogenic avian influenza (H5N1) in wild birds were examined. The measures taken by the Swiss authorities to prevent the virus from infecting domestic poultry consisted of establishing protection zones within a radius of at least 3 kilometers and surveillance zones within a radius of at least 10 kilometers. In these zones regulations, such as poultry must be kept in the henhouse, were introduced. The Swiss authorities had to decide which municipalities to include in the protection zones and which in the surveillance zones. Figure 6 shows the second last stage of the avian influenza outbreak. Since the regulations brought into operation after the first two occurrences are no longer in effect, the affected municipalities are not highlighted, but those in the protection and surveillance zones of Divonne-les-Bains (Ain, France).
Assume the administrative division of Switzerland is represented in administrative ontology O 1 and the finds of infected birds as well as protection and surveillance zones are represented in epidemiology ontology O 2 (only the RBoxes are displayed; the ontologies can be downloaded from https://www.envidat.ch/dataset/icbo2020). In order to construct a query against a geodatabase to figure out which municipalities to include in which zones, the two ontologies need to be merged. Both are OWL 2 DL ontologies with an expressivity of ALCRIF and SRIF, respectively. They have been implemented using Protégé 5.2 [27].
District, Municipality, Find, Zone (not shown) describe classes of objects that are related to each other by roles located_in, located_in_inv, proximal. Their spatial extensions are instances of the class Region (not shown) which are interrelated by roles partOf, overlaps. Roles has_2D, has_2D_inv relate objects to their spatial extensions and vice versa.
In order to represent the administrative division properly, every region occupied by a municipality is assigned to exactly one region occupied by a district (line 1.22). Accordingly, the role partOf is functional in ontology O 1 . For the finds of infected birds in ontology O 2 , on the other hand, the same role needs to be transitive (line 2.32): The (small) regions occupied by the finds are contained in the regions occupied by the protection zones. These are contained in the regions occupied by the surveillance zones. Merging the two ontologies, thus, results in a conflict which is reported by the following conflict set: Fig. 6 Avian influenza in the Lemanic Arc (adapted from [37] The conflict is resolved by trading transitivity of appl:epidemiology#partOf for functionality of appl:admin#partOf and disjointness of roles in the administrative ontology. Doing so affects less, but equally preferred, axioms than the other way round, namely, one axiom vs. seven axioms (please note: 'axiom' 1.17 is a shorthand notation for six individual axioms omitted due to space limitations). It loses exactly the same inferences (diff is empty) as trading in the opposite direction.

Discussion
A first step for a conflict resolution framework has been made, comprising the basic specification what it is, a specification of a conflict set, a first library of conflicts, and indications of paths toward resolution. Examples and the case study suggest that conflicts are abound already, and this is likely set to increase with the increasing number of ontologies that are being developed. This, in turn, brings afore an imperative for software-supported conflict detection and resolution to further systematize and facilitate the process. Broadly, for each type of conflicts one needs (1) mechanisms-software tools, where possibleto be able to detect them; (2) to store the information collected upon detection for further processing; (3) a set of resolution strategies associated with each type of conflict that then can be used in some form by the user, for instance, in a Query & Answer dialogue, alike demonstrated in Fig. 7; and (4) a means to automate the implementation of the choice made. We discuss the requirements for such software support in the remainder of this section, first specifically for the walk-throughs of the case study, and then more generally.

Tool requirements for the walk-throughs
A system encompassing the whole walk-through of the case study, alike in Fig. 7, requires, as a minimum, a Question Answering system that avails of a controlled natural language or a natural language generation system to generate the text and to process the user's input.
For step 1/i, the "beyond OWL 2 DL" is a slot filled with that value in a template sentence "O' is [species]. ", where the value for the species variable is fetched from the conflict set, and likewise for the "partOf" etc that are values from the <axiom> variables of the grammar (recall Fig. 2). This entails the software requirement to be able to find such conflicts, which, in this case, can be achieved with the OWL Species Classifier and processing of its output into the conflict set data structure, and additional template design for a 'pretty printing' wrapper. This is likewise for generating the explanation in step ii.
Steps 2 & 3 and ii & iii require a mechanism to propose alternatives, which has to consist of at least two components: a data structure storing the typical resolutions that may be feasible for each conflict and a decision tree covering each option. For instance, there are 6 possible choices for the case study (yes + a, yes + b, etc.): for the "yes" choice in walk-through A, the options are always to roll-back the integration, delete one or delete the other axiom, whereas the "keep" answer in step ii, i.e., to keep the axioms (in walk-through B), has three choices that can be presented as canned text.
Once at the end of the decision tree, step 4/iv and 5 require an algorithm to gather all consequences of each leaf in the decision tree. Consequences may be only a list of axioms deleted or also inferences lost, which have to be collected on-the-fly. Such algorithms will have to be developed. For step 4's roll-back, it simply means using the OWL API [26] or Owlready [38] to query the ontology for alignment axioms between the two ontologies (that are identifiable with their different IRIs) and displaying the query answer by slotting in those axioms into a variable length template. If the resolution choice would also show the deductions lost or options b) or c), then it will take some more effort, in that the ontology then has to be copied, the relevant axiom removed, inferences computed and the differences in entailments determined (e.g., with the OWL Diff tool [28]), which then would be rendered. No tool exists that does this whole process, but the key components exist. Canned explanations, as in step v, obviously can be prepared easily.
The last step, 6/vi, sounds deceptively simple, but the ease or difficulty to implement it depends on the type of conflict and the choice. For option a) in walk-through A, as well as for the earlier example about viruses in Fig. 5: if one has chosen to remove the ontology or the offending axiom, then it is a simple deletion of the axioms identified for step 5. Ignoring the reasoner (step vi) is even easier to do.

Further tool requirements
The implementation of the choices in Fig. 7 are straightforward. It rapidly can become more challenging for other chosen resolutions, however. For instance, a modeller may have chosen the DOLCE ontology from the choices shown in Fig. 3, then the implementation of that choice depends on the starting position: perhaps it is simply an import of DOLCE-lite.owl, but if another foundational ontology was used before, it would entail swapping out the old foundational ontology for DOLCE and aligning one's domain entities to that, either manually or automatically with SUGOI [39]. The remodeling of all vaccinates object property usages in axioms into its reified Vaccination, as suggested in Fig. 1, requires a substantial modification of the ontology between two modeling patterns for which no algorithm exists yet.
Alternative routes may be possible for other conflicts and walk-throughs, such as assisting with testing the effect of axioms oneself with TDDonto2 [13], and migration paths to the 'beyond OWL' infrastructures, such as Onto-Hub [40] with the Hets toolset reasoner for ontologies in the DOL framework [41]. The requirements for advanced handing of language conflicts require software support for, e.g., the Ontolex-lemon [34] and MoLA [35] models, which presuppose that such issues can be detected, which is also a requirement to be fulfilled. Similarly, there are theoretical advances on modeling styles [20] for detecting and resolving conflict 9 of Table 1 and for ontological conflicts between modeling languages [25] to resolve conflict 4 of Table 1: also here the main requirement is to repurpose the theory for software-supported conflict resolution.
To sum up, the minimal system requirements are: • A conflict resolution workflow management system, be it a Question Answering system or another strategy that avails of a knowledge-to-text controlled language, canned text, a decision tree, and two data structures (the conflict set and the resolution options); • Algorithms to populate the conflict set, which may avail of new wrappers for existing OWL tools to recast their computation and outputs as detection and conflict resolution functionalities; • End-user usable DOL and CL tools; • Software support for the language annotation models and extant assessments on modeling style and language conflicts. From a different viewpoint: these requirement are future work. The first steps on the conflict resolution path that we presented here, together with the case study, has enabled a formulation of tool requirements, paving a path forward.

Conclusions
Foundational steps towards a framework that can deal in a systematic way with the various types of modeling conflicts through meaning negotiation and conflict resolution have been proposed. The article introduced and specified the notions of meaning negotiation and conflict resolution, outlined what their components are, and presented a first step towards a library of conflicts. There is no single way of detecting and resolving conflicts, where four common categories were described, with conflicts at the top-level theory level, at the subject domain level, and axiom-level conflicts, which intersect with language expressiveness conflicts. The notion of the conflict set was also introduced, which is a minimal data structure in which the detected conflicts can be stored and upon which a software-mediated conflict resolution will be able to operate. This approach was evaluated with an actual case of domain knowledge usage in the context of epizootic disease outbreak. The theory and use case combined assisted in elucidating software requirements for conflict resolution workflows.
While there are some tools and plugins that can assist with meaning negotiation and conflict resolution, no integrated support is currently provided. Future work includes refining the framework and proceed to components of automating conflict detection and resolution, as well as establishing the conflict library in more concrete terms.


s2fieldsofstudy:
Computer Science
Business

text:
An Improved Adaptive Genetic Algorithm for Two-Dimensional Rectangular Packing Problem

: This paper proposes the hybrid adaptive genetic algorithm (HAGA) as an improved method for solving the NP-hard two-dimensional rectangular packing problem to maximize the filling rate of a rectangular sheet. The packing sequence and rotation state are encoded in a two-stage approach, and the initial population is constructed from random generation by a combination of sorting rules. After using the sort-based method as an improved selection operator for the hybrid adaptive genetic algorithm, the crossover probability and mutation probability are adjusted adaptively according to the joint action of individual fitness from the local perspective and the global perspective of population evolution. The approach not only can obtain differential performance for individuals but also deals with the impact of dynamic changes on population evolution to quickly find a further improved solution. The heuristic placement algorithm decodes the rectangular packing sequence and addresses the two-dimensional rectangular packing problem through continuous iterative optimization. The computational results of a wide range of benchmark instances from zero-waste to non-zero-waste problems show that the HAGA outperforms those of two adaptive genetic algorithms from the related literature. Compared with some recent algorithms, this algorithm, which can be increased by up to 1.6604% for the average filling rate, has great significance for improving the quality of work in fields such as packing and cutting.

Introduction
The two-dimensional rectangular packing (2DRP) problem is often involved in the manufacturing process of furniture, glass, metal, paper products, VLSI chip design, newspapers paging, and so on [1,2]. Consequently, optimized algorithms designed to improve the quality and efficiency of packing (therefore reducing the cost of the enterprises) are the subject of many researchers' explorations in recent years. The 2DRP problem can be described simply as this: rectangles of different sizes are put into a large two-dimensional rectangular container (which we call the sheet) in a certain way to maximize the filling rate of the sheet. The 2DRP is a representative NP-hard problem [3] with complex constraints, which means that there is no exact method to solve the problem in polynomial time. Thus, most researchers have devoted their efforts to fast approximate heuristics and meta-heuristics to obtain practical solutions with higher qualities.
In recent decades, in order to solve the optimal or nearly optimal packing scheme of the 2DRP problem in a compromise time and space, scholars have explored and studied many methods for solving the problem. Two types of representative approaches have been used to address the 2DRP problem: the first solves the problem directly by using different heuristics; the second uses meta-heuristic algorithms, such as Simulated Anneal-ing (SA) [4], Genetic Algorithm (GA) [5], Particle Swarm Optimization (PSO) [6], Ant Colony Optimization (ACO) [7], etc., combined with heuristic placement strategy. Recently, other introduced algorithms include whale optimization algorithm [8], dragonfly algorithm [9], naked mole-rat algorithm [10], moth flame optimization [11], etc.
The component in the first approach is the layout representation for packing sequence. The bottom-left (BL) algorithm [12] proposed by Baker et al. is the earliest heuristic. The main idea is to start from the top right corner of the container, making each item continuously slide as far as possible downwards and then as far as possible to the left until the item is placed in a stable position. Some BL algorithms have improved heuristic variants such as bottom-left-fill (BLF) [13], deepest bottom-left-fill (DBLF) [14], improved bottom-left (IBL) [15], and bottom-left decreasing (BLD) [16]. The lowest horizontal line algorithm (LHLA) [17] proposed by Jia et al. queries the horizontal line with the lowest height when laying out the rectangle and places the rectangle on it. However, taking account of the lack of iterative optimization, in general, the packing quality of the heuristic approach is poor.
In order to improve the packing quality, the key part of the second method is how to use meta-heuristics combined with a layout representation approach to optimize the packing sequence. Hopper et al. conducted empirical research, combining SA and GA with BL and BLF approaches [18]. The best fit algorithm (BF) [19] proposed by Burke et al. describes the sheet as a set of dynamic slots, places items on the lowest available slot at each iteration step, and then combines them together. Later, Burke's team also proposed a simulated annealing enhancement to the BF algorithm [20]. He et al. suggested an efficient deterministic heuristic [21] using the action space. Wei et al. investigated an adaptive selection approach [22] without any control parameter to address the 2D rectangle packing area minimization problem. Recently, Xia et al. proposed an adaptive genetic simulated annealing algorithm [23] applied to the problem of packing optimization of rectangles.
In view of the premature problem of Simple Genetic Algorithm (SGA) in practical applications, it is easy to fall into local optimal solution prematurely as well as poor local search ability [24]. Srinivas et al. [25] proposed an Adaptive Genetic Algorithm (AGA) that dynamically adjusts the crossover probability and mutation probability according to the fitness of the individual. However, if the fitness of the individual is close to or equal to the maximum fitness of the population, the crossover probability and mutation probability will be close or equal to zero, making the evolution of genetic algorithm stagnant. Ren proposed an improved AGA [26] for this problem. However, when the average fitness is close to the maximum fitness of the contemporary population, it is easy to cause a large number of individuals to have a lower crossover probability and mutation probability, which will stagnate the evolution. This improved AGA has also been applied to many fields such as the three-dimensional container loading problem [27] and the laminate stacking sequence optimization [28]. In addition, the algorithm proposed by Ren is only in view of individual fitness. This algorithm adaptively changes the crossover probability and mutation probability from the local perspective, but the dynamic adjustment of crossover and mutation are not considered whether they have a positive impact on the population evolution process from the overall perspective of population evolution. According to the evolution of later generations, the AGA [29] proposed by Jiang recorded the number of algebras in which the fitness of the optimal individual of the population did not change and dynamically adjusted the crossover and mutation probabilities. However, the algorithm has two shortcomings: (1) the incremental value and decrement value of crossover probability and mutation probability are greatly affected by fitness, and if the value range of the fitness function is not between 0 and 1, the adaptive algorithm will no longer be applicable; (2) although the crossover probability and mutation probability of each generation are dynamically adjusted, the crossover probability and mutation probability of all individuals in a certain generation are the same, and the performance is consistent for individuals with different fitness. In this paper, in order to overcome the shortcomings of the two kinds of adaptive genetic algorithms, an improved method called hybrid adaptive genetic algorithm (HAGA) is proposed to supplement Ren and Jiang's algorithms. It is the key for HAGA to work through the joint action of individual fitness from local perspective and the global perspective of population evolution. The presented algorithm not only can obtain differential performance for individuals but also deals with the impact of dynamic changes on population evolution to quickly find a further improved solution. First of all, through the research and analysis of the 2DRP, a two-dimensional packing model is established to maximize the filling rate with relevant constraints. Then, the initial population is constructed by two-stage encoding, and the heuristic lowest horizontal line algorithm is used in the process of placement to decode the packing solution and calculate the individual fitness. After the termination rules of the design are satisfied in the iterative optimization process of HAGA, the packing scheme with the largest filling rate is selected in the feasible solutions. To verify the performance of the proposed algorithm, zero-waste and non-zerowaste instances are tested. The computational results show that the proposed HAGA is more efficient than the compared algorithms.
The rest of this paper is organized as follows. In Section 2, the mathematical model of 2DRP is built. The improved method, HAGA, for the 2DRP problem is introduced in detail in Section 3. Then, Section 4 provides the computational results and comparisons. Finally, the conclusion of this paper is given in Section 5 with some closing remarks.

Problem Statement
Assume that there is a set of n rectangle ( { } 1 2 , ,..., n R r r r = The task is to orthogonally place the items without overlapping in the sheet with W H × to maximize the filling rate of the sheet, i.e., to maximize the total area of the placed items divided by the area of the sheet. The paper addresses the 2DRP with the following assumptions [30,31]: (1) For any two rectangular items put in, they cannot overlap each other.
(2) When the rectangle is put into the sheet, it cannot exceed the boundary of the sheet.
(3) The side of the rectangular items must be parallel to the side of the sheet.   Let i θ be a decision variable, taking the value 1 or 0 accordingly as rectangle i r is or is not placed. The filling rate F of the sheet is defined as the ratio of the total area of the rectangles placed in it to the area of the sheet. The mathematical model of the 2DRP is as follows: (1) In constraints (1)-(4), i , j applies to 1, 2,..., n and i j ≠ . Constraint (1) implies that the boundaries of the placed rectangles do not exceed the width and height boundaries of the sheet. Constraint (2) means that the placed rectangles cannot overlap each other.  (3) implies that the placed rectangle is parallel to the side of the sheet and can be rotated by 9 0  . To sum up, the 2DRP problem can be described as figuring out the best packing solution that satisfies the constraints and maximizes the filling rate of the sheet.

Improved Adaptive Genetic Algorithm
It is representative for 2DRP to combine heuristic placement strategies and metaheuristic algorithms such as GA. The GA usually includes SGA and various improved genetic algorithms such as AGA. The SGA is prone to premature problems that cannot escape the local optimal solution. Then, some adaptive genetic algorithms such as AGA [25], AGA [26], and AGA [29] were proposed to solve this problem. However, these also have some problems. Since the AGA [26] is an improvement to the AGA [25], this section mainly focuses on some problems in AGA [26] and AGA [29], presenting further improved AGA for 2DRP by combining heuristic placement strategy.
The packing sequence of rectangles and whether they are rotated are the most important factors that affect the results of the final packing solution. This paper proposes an improved adaptive genetic algorithm as a rectangle sequencing algorithm to determine the packing sequence and rotation state of the rectangles, with the heuristic lowest horizontal line algorithm used as the placement algorithm to determine the position coordinates of the rectangle. First of all, in terms of the genetic algorithm, two-stage encoding is constructed, i.e., the packing sequence is coded by continuous integers from 1 to n , and the rotation state is coded with 0 and 1. The initial population is constructed through a combination of sorting rules and random generation. The heuristic lowest horizontal line algorithm is applied to decode, so as to provide the packing solution and calculate the individual fitness. Then, it uses a sort-based method for selection and improved adaptive crossover and mutation operations for evolution. The process of iterative optimization continues until the designed termination rule is reached, and finally, the result decoded by the optimal individual is taken as the final packing solution.

Encoding and Population Initialization
Assuming there are n rectangles 1 2 { , ,..., } n r r r to be packed, the chromosome adopts a two-stage encoding method consisting of the packing sequence and placement state of the rectangles, and the encoding length is 2n . The former n uses an integer permutation code, and the packing sequence adopts integer numbers, which is the order of the rectangles to be packed. The latter n uses integer coding, and the rectangle placement status is numbered with 0 and 1, in which 1 means the placement rectangle rotates, and 0 represents that it does not rotate. So,  Figure 2. The order of rectangular packing is 4, 2, 5, 1, 8, 6, 3, and 7, and the rectangles numbered 2, 5, 6, and 7 need to be rotated during the packing process. The above encoding approach accurately describes the factors that affect the packing solution. Considering that the packing sequence sorted by certain attributes tends to be the optimal solution, the following sorting rules [32] are fully utilized to generate the initial population in combination with random generation to speed up the algorithm when initializing the population.       E − are generated randomly. The packing sequence of the remaining six individuals is generated by the six sorting rules, and the corresponding rotation state of the rectangles is generated randomly. The PS is set to 100 in this paper.
Once the chromosome encoding sequence of the individuals in the population is determined, the heuristic placement algorithm can be used to decode and place, and then the individuals can be evaluated through the fitness function.

Heuristic Placement Algorithm
When using the fitness function to evaluate individuals in the population, it is necessary to arrange the rectangles into the sheet according to a certain heuristic algorithm for the packing sequence, rotation state, the width and height of rectangles, and the width and height of the sheet to calculate the sheet filling rate and figure out the fitness.
Liu proposed the IBL algorithm [15] to solve the problem that the left side of the BL algorithm [12] is too high and the unfilled cavity area can not be effectively used. Although it can overcome the disadvantage of the BL algorithm, which is prone to the waste area of the sheet, it will lead to the problem of a high right side. In contrast, the lowest horizontal line algorithm proposed in this paper can effectively solve the shortcomings of the BL and IBL algorithms and improve the filling rate [33]. Therefore, the placement algorithm in this paper adopts the heuristic lowest horizontal line algorithm of Ref. [23], and the procedure is as follows in Algorithm 1.
Algorithm 1 Heuristic packing procedure HeuristicPacking(R, sheet): 1 Initialize the lowest level line l is 0 2 while R is not empty or l is beyond the sheet H: 3 Get filling area on l and hollow area under l , the area size store 2-tuple set (AW, AH) 4 Priority to sorting hollow area in increasing order of AW for (AW, AH) If exist the next area: 14 Move the next area to continue placing 15 else: 16 Sort these placed i r in increasing order of i y 17 Update l and the area size (AL, AH) 18 return the placed information for R

Fitness Function and Selection Operator
Generally, the fitness function of the genetic algorithm is often determined by the objective function. In this paper, the fitness function refers to the sheet filling rate of the objective function, and its definition can be seen in the 2DRP mathematical model in Section 2.
Selection operation is the process of the genetic algorithm to evaluate the survival of the fittest. Its purpose is to keep the individuals with better fitness in the parent population as much as possible to keep good genes. The traditional roulette [34] selection method gives every individual the opportunity to make a copy, which does not reflect the competitiveness of excellent individuals and cannot realize the principle of survival of the fittest by the genetic algorithm. This paper uses an improved selection method sorted by individual fitness [35] to replace the roulette selection method. The sort-based selection method is described as follows: Step1. Calculate the fitness of each individual in the population.
Step2. Sort the individuals in the population in descending order of fitness.
Step3. Divide the sorted individuals into three parts, and the first one was duplicated into two copies.
Step4. Make a copy of the individuals in the middle.
Step5. The remaining individuals ranked behind are not copied.

Adaptive Crossover Operator and Mutation Operator
This subsection gives an improved genetic algorithm, in which the crossover probability and mutation probability can be adjusted adaptively. The crossover operation is to randomly exchange some genes between two individuals in the population based on the crossover probability so as to combine excellent genes to produce new and better individuals, which is the main part of the genetic algorithm. The mutation operation is to replace genes of an individual with other alleles under a certain mutation probability, thereby forming a new individual, ensuring the diversity of the population and preventing the phenomenon of premature.
Crossover probability and mutation probability are the most important parameters for crossover and mutation operations. Their selection is the key to influencing the behavior and performance of the algorithm and directly affecting the convergence of the algorithm. Regarding the crossover probability, if the crossover probability is too small, the search process will be slow and will easily cause stagnation. However, if the crossover probability is too large, the chromosomal structure of an individual with high fitness will be quickly destroyed and replaced. For the mutation probability, if it is too small, a new individual chromosome structure is not easy to be generated, and the search space will become narrower. Otherwise, if the mutation probability is too large, the genetic algorithm becomes a purely random search algorithm, which makes it easy to fall into a local optimal solution.
The AGA [26] proposed by Ren is to adaptively change the crossover probability and mutation probability from the local point according to individual fitness without considering whether the dynamic adjustment of crossover and mutation has a positive impact on population evolution from the whole point of population evolution. The AGA [29] proposed by Jiang dynamically adjusts the crossover probability and mutation probability according to the fitness changes of the optimal individual from the whole point of the evolution of the population offspring. However, the crossover probability and mutation probability of all individuals of a certain generation of population are still the same, and the performance of individuals with different fitness of the generation is consistent, so there is no difference. Moreover, the AGA [29] is greatly affected by the contemporary optimal fitness and the range of fitness function, which will limit the wide application of the algorithm.
Inspired by Ren and Jiang, this paper proposes an improved method called hybrid adaptive genetic algorithm (HAGA) to solve the 2DRP problem. The adaptive description of the crossover probability is as follows: where 1 c P and 2 c P are the upper bound and lower bound of c P . In general, the recommended parameters for these two crossover probabilities are 0.9 and 0.6 respectively [36]; i.e., 1 0.9 c P = and 2 0.6 c P = . The parameter t is the cumulative number of generations in which the optimal fitness value of the population has not changed. When the optimal fitness value of a certain generation changes, it will be set to 0 for re-accumulation. For example, in the process of iterative optimization, if the best fitness value lasts for ten times without changing, the t is set to 10. The parameter c is a constant to determine the slope  It also helps to solve the problem for AGA [29] that is greatly affected by the contemporary optimal fitness, representing the fitness function range with appropriately adjusting 1 c P and 2 c P . It is beneficial to combine with AGA [26]. The t is recorded after each iteration to determine the change of ( ) c P t . If t becomes larger, it shows that the optimal fitness of the population evolution has not changed, and the crossover probability needs to be increased to promote the change of the optimal fitness. If 0 t = , it reveals that the optimal fitness of the population evolution has increased, and the crossover probability ( ) c P t will drop to 2 c P for increasing more possible solutions. Then, combining Formula (3) to increase the difference of crossover operation for different individuals. Combining Formula (2) and Formula (3), it works together to find a better solution from the global perspective of population evolution and the local perspective of individual fitness. In addition, because it can increase the crossover probability from the perspective of the population evolution process, it is also helpful to overcome the problem that evolution is likely to stagnate when avg f is close to max f . The effect of the adaptive mutation probability change in the latter part is similar to this.
When carrying out crossover, the packing sequence gene string adopts the partial matching crossover (PMX), and the rotating state gene string adopts the two-point crossover method. An example of the crossover process is shown in Figure 4. The procedure of the hybrid adaptive crossover algorithm is described in Algorithm 2.

12
Get two crossed children using the same method of Figure   a v g Similarly, we can be aware that Formula (5) is the adaptive mutation probability from the whole point of population offspring evolution, and Formula (6) is the adaptive mutation probability for individual fitness from a local perspective. The hybrid adaptive mutation probability is used to work together to dynamically adjust the mutation probability. When mutating, the packing sequence gene string adopts the exchange mutation method, and the rotating state gene string takes the two-point basic position mutation method. An example of the mutation process is shown in Figure 5. The procedure of the hybrid adaptive mutation algorithm is described in Algorithm 3. In Algorithms 2 and 3, P represents the population in the genetic algorithm; PS means the size of the population, i.e., the number of individuals in the population; The parameter t is obtained by comparing the fitness of the best individual in the previous and next generations in the population evolution process. If the optimal individual fitness of the previous generation and the next generation are equal, 1 t t = + ; otherwise, t is reset to 0.

11
Get mutated child using the same method of Figure 5  12 Put mutated child with Heuristic Packing Procedure 13 Update ' [ ] P i using mutated child 14 Add ' P to P , Sort them in decreasing order of fitness In summary, Algorithm 2 plays a role of constructing the hybrid adaptive crossover algorithm (HACA) and Algorithm 3 structures the hybrid adaptive mutation algorithm (HAMA), which are two main parts of HAGA. From the local aspect of individual fitness and the whole evolution of later generations' population, the crossover probability and mutation probability can be adjusted adaptively to quickly find a further improved solution.

Termination Rules
The improved adaptive genetic algorithm we proposed shows a convergence trend in the process of searching and optimizing the solution space. For the iterative optimization calculation of 2DRP problem, there are the following termination rules: (1) After the iterative calculation reaches a certain level, the optimal fitness value has no obvious change in the continuous T iterations, and the calculation can be stopped in advance. For example, the T is set to 150 in this paper, which means the calculation is terminated if the optimal fitness value does not change through 150 continuous iterations; (2) Set the desired packing rate in advance. In the process of calculating, the pre-set filling rate is reached, and the calculation can be terminated early. For the expected filling rate, if the theoretical filling rate is known before the experiment, e.g., the theoretical filling rate of the C benchmark instances proposed by Hopper is 100% [18], it can be set to the theoretical value; otherwise, the user's expected value can be set according to actual needs; (3) Set the maximum number of iterations in advance. If the algorithm does not terminate prematurely, when the genetic algebra reaches the maximum number of iterations, the calculation is terminated, and the packing solution and filling rate are obtained.
The combination of the above three termination rules can not only fully optimize within the maximum number of iterations but also terminate the iterative optimization of the algorithm early when the expected value or fitness value is reached and there is no obvious change, which is beneficial to reduce the calculation time of the algorithm. When the iterative optimization of the algorithm is terminated, the packing solution corresponding to the chromosome with the largest fitness value is the optimal packing solution, and the corresponding filling rate is calculated.

Related Discussion
The proposed algorithm firstly overcomes the problem that is greatly affected by the contemporary optimal fitness and fitness function range for AGA [29] to expand its application; especially, the fitness function range is not between 0 and 1. Moreover, this algorithm not only obtains the differential performance of a certain generation of individuals by combining AGA [26] but also handles the impact of dynamic changes on population evolution to find adaptively an improved solution. However, the presented algorithm is not perfect in this paper; it has the following drawbacks: (1) There are some parameters that need to be controlled, including  P . In the early stage of evolution, the optimal individual is easy to change frequently; that is, there are more times where 0 t = , which leads to lower crossover probability and mutation probability that are not beneficial to rapid population evolution.
We can set up a series λ and c to determine the appropriate parameters through many experiments. In addition, it is possible for 0 t = to make continuous descent changes for different evolutionary periods.

Computational Experiments
In this section, to evaluate the effectiveness of the proposed improved method, HAGA, four computational experiments are designed and implemented. The rectangle packing instances, which include zero-waste and non-zero-waste datasets, are used for testing. The first three benchmark instances as zero-waste are the J instances ( 1 2 J J − ) proposed by Jakobs [37], the C instances ( 11 73 C C − ) proposed by Hopper et al. [18], and the N instances ( 1 13 N N − ) proposed by Burke et al. [19]. The scale and optimization difficulty of these three benchmark instances increase sequentially. The optimal solution for each instance is known beforehand, in which the total area of the given items is equivalent to the area of the sheet, resulting in a 100% filling rate. So, they all theoretically have a 100% filling rate but are not balanced dimensionally. However, considering that non-zero-waste problems often occur in real application, the non-zero-waste datasets, including 4 instances (cgcut1-cgcut3) given in Ref. [38], 13 instances (gcut1-gcut13) in Ref. [39], 12 instances (ngcut1-ngcut12) in Ref. [40], and 10 instances (beng1-beng10) in Ref. [41], are used for further testing.
The SGA, AGA [26], AGA [29], and HAGA involved in the experiment are implemented in Python language programming and calculated on an Intel Core i5 CPU at 2.5 GHz with 8 GB memory. We tested the effects of SGA and AGA [26] for each individual fitness proposed by Ren, AGA [29] for the evolutionary process proposed by Jiang, and the HAGA proposed in this paper. Then, a comparison of HAGA with some recent algorithms is provided. In order to balance the calculation accuracy and efficiency of the test algorithm, the number of iterations NIND is set to 2000, and the calculation result is the average of twenty operations.

Computational Experiment for J Instances
We know that Ref. [42] divides the J benchmark instances into two groups of problem instances, which are called 1 J and 2 J . The size of the large rectangular sheet is 40 15 × . The number of items in the first group is 25, and the number of items in the second group is 50. For more detailed information on the instances, refer to the original paper published by Jakobs [37].
In this subsection, we compare the performance of the proposed HAGA with SGA, AGA [26], and AGA [29] on the J instances. The AGA [26] is an adaptive genetic algorithm that dynamically adjusts the crossover probability and mutation probability for each individual. The AGA [29] is an adaptive genetic algorithm that dynamically adjusts the crossover probability and mutation probability for the evolution process. In the comparative experiment, the crossover probability and mutation probability in SGA are 0.9 and 0.1, respectively. The parameters 1 c P , 2 c P , 1 m P and 2 m P of the AGA [26] remain consistent with that in this paper, and the parameter c in AGA [29] also remains consistent with this paper. The computational results are shown in Table 1, where F represents the filling rate of the sheet. Figures 6 and 7 show the rectangular packing layouts corresponding to the optimal solution obtained by the HAGA. From the results shown in Table 1, it can be seen that the average calculation time of the three adaptive genetic algorithms of AGA [26], AGA [29], and HAGA are 16.45 s, 16.4 s, and 14.45 s respectively, which is less than that of the SGA. It shows that the adaptive genetic algorithm can accelerate the convergence speed of the algorithm by dynamically adjusting the crossover probability and mutation probability. The average filling rate of the adaptive genetic algorithm is higher than that of SGA, which shows that the adaptive genetic algorithm can address the problem that SGA may fall into a local optimal solution. Next, by comparing three adaptive genetic algorithms, we can realize that they have almost the same average filling rate on the J instances, but the average time consumed for HAGA is 2 s, which is less than AGA [26] and 1.95 s less than AGA [29]. The results show that the HAGA can overcome the shortcomings of the two types of adaptive genetic algorithms including AGA [26] and AGA [29] through the joint effect of the local aspects of individual and the overall aspects of evolution, and the convergence speed of the algorithm is accelerated to show the effectiveness of the proposed algorithm.

Computational Experiment for C Instances
The number of items per instance for C benchmark instances ranges from 16 to 197. According to the area of the sheet, these instances can be classified into seven groups with three instances each. For detailed information on the C instances, refer to Hopper et al. [18]. The experimental comparison results are shown in Table 2. It can be inferred from the results in Table 2 that as the scale n of the problem instances becomes larger and larger, the difficulty of the algorithm convergence increases, and some instances cannot achieve a 100% filling rate. The HAGA can obtain a 100% filling rate for all instances except for C71, but AGA [26] fails to obtain a 100% filling rate for C13, C71, C72, and C73. The scale of the C13 instance is not large, but the 100% filling rate is not obtained because the algorithm fell into a possible local optimal solution during a certain test. In addition, the AGA [29] fails to obtain a 100% filling rate for C71, C72, and C73. It is obvious that the HAGA is better than AGA [26] and AGA [29].
Then, by comparing SGA and the adaptive genetic algorithm, it can be realized that AGA [26], AGA [29], and HAGA save 74.59, 71.9, and 108.91 s respectively in comparison to SGA. The average filling rate of the adaptive genetic algorithm is generally higher than that of SGA, which shows that the adaptive genetic algorithm can overcome the "premature" phenomenon to which SGA is prone. Through the analysis of the results of the three adaptive genetic algorithms, it can be found that the HAGA uses 34.32 s and 37.01 s less than AGA [26] and AGA [29] in the average calculation time, and it increases the average filling rate by 0.15% and 0.11%, respectively. This shows that the improved method, HAGA, can speed up the convergence of the algorithm and relatively increase the filling rate of the sheet.

Computational Experiment for N Instances
The N benchmark instances were generated by Burke et al., and optimal solutions were also known beforehand. It includes 13 groups of test instances, and the number of items to be packed increases from 10 in the first group to 3152 in the thirteenth group. For detailed information on N instances, refer to Burke et al. [19]. The comparison results of our experiments are shown in Table 3. It should be noted that the '-' in N13 means that no experimental calculation has been performed. We can recognize from the results shown in Table 3 that SGA can only obtain a 100% filling rate for N1-N3 instances with a small scale. Both AGA [26] and AGA [29] fail to obtain a 100% filling rate in five instances, and HAGA fails to obtain a 100% filling rate in three instances N10~N12. Comparing the N5 and C41-C43 instances of almost the same scale, you will find that the N5 instance consumes a lot more time than the C41-C43 instances. For example, the calculation time of AGA [26] is 22.37 s on the C43 instance, but it takes 33.98 s on the N5 instance. These indicate that solving N instances is more difficult than solving the C instances, but the HAGA is still better than the two types of adaptive methods AGA [26] and AGA [29] to solve the 2DRP problem.
Then, by comparing SGA and the adaptive genetic algorithm, we figure out that AGA [26], AGA [29], and HAGA reduce the time by 90.46, 114.08, and 154.49 s, respectively compared with SGA, and the average filling rate of the adaptive genetic algorithm is generally higher than that of SGA. We compare the computational results of the three adaptive genetic algorithms again, and it can be seen that the HAGA saves 64.03 s and 40.41 s in the average calculation time than AGA [26] and AGA [29], and it increases the average filling rate by 0.1% and 0.05%, respectively. Therefore, it further shows that the HAGA can better improve the convergence speed and filling rate for 2DRP, thereby improving the packing efficiency and quality.

Computational Experiment for Non-Zero-Waste Instances
The 38 non-zero-waste instances including cgcut1-cgcut3, gcut1-gcut13, ngcut1-ngcut12, and beng1-beng10 are evaluated to further verify the effectiveness of the HAGA. These datasets have been used by other authors to verify the performance of the algorithm. Although some of the area of the stock sheet is wasted in these instances, the optimal solution of problem can be known from Ref. [43]. It should be noted that the filling rate needs to be obtained through the (1 ) 100 trim loss − × formula conversion for the trim loss indicator in Ref. [43]. The data can be downloaded from http://people.brunel.ac.uk/~mastjjb/jeb/info.html. Table 4 reports the comparison results of AGA [26], AGA [29], and HAGA for nonzero-waste instances. From Table 4, we can observe that the number of instances in which HAGA, AGA [26], and AGA [29] obtained the optimal filling rate is 22, 20, and 21, respectively. The HAGA obtains the optimal filling rate except for cgcut3 on the cgcut1-cgcut3 instances, ngcut6, ngcut9, and ngcut11 on the ngcut1-gcut12 instances, and beng10 on the beng1-beng10 instances. The worst performance of HAGA is that it only obtains the optimal filling rate on gcut1 and gcut3 for the gcut1-gcut13 instances. The filling rate of HAGA is not lower than that of AGA [26] except for five instances (gcut5, gcut9, gcut11, gcut12, ngcut11). Similarly, the filling rate of HAGA is not lower than that of AGA [29] except for six instances (gcut2, gcut7, gcut9, gcut10, ngcut12, beng10). By comparing the computational results of the three adaptive genetic algorithms, it can be observed that the HAGA saves 19.5 s and 15.8 s in average calculation time compared with AGA [26] and AGA [29], and it improves the average filling rate by 0.2% and 0.06%, respectively. The computational results show that the HAGA is still effective for non-zero-waste instances.

Compare the Results with Other Algorithms
We compare the proposed algorithm with the algorithms in Ref. [43][44][45]. A hybrid simulated annealing algorithm (HSA) proposed by Leung et al. [43] uses a greedy strategy and simulated annealing to obtain an improved solution. A least-waste-first heuristic algorithm (LWF) proposed by Wei et al. [44] presents a least wasted first heuristic algorithm to find the desirable solution. An iterative bidirectional heuristic placement (IBHP) proposed by Shiangjen et al. [45] combines the constructive heuristic algorithms of bidirectional heuristic placement (BHP) and iterated local search (ILS) with a shift strategy to improve the solution. Considering that Ref. [44] lacks some test instances, the results of LWF and HSA are taken directly from Ref. [43]. The HSA and LWF in C++ programming language were run on a Dell GX270 with 2.60 GHz CPU and 512 MB memory. The IBHP in C programming language was performed on an Intel Core i5 CPU at 2.90 GHz with 4 GB of RAM running on the Ubuntu 12.04 operating system. The comparisons of the average filling rate and the average calculation time between LWF, HSA, IBHP, and HAGA are shown in Table 5. The '-' in Table 5 means that the results are not reported by the corresponding algorithm. From Table 5, it can be observed that the average filling rate of HAGA on the C11-C73, cgcut1-cgcut3, and ngcut1-ngcut12 instances is 99.8%, 97.5755%, and 86.5549%, respectively, which outperforms LWF, HSA, and IBHP. Compared with LWF for these instances, the average filling rate of HAGA can be increased by 0.5356%, 1.6604%, and 0.999%, respectively. The maximum average filling rate can be improved by 1.6604% on cgcut1-cgcut3 for LWF. The average filling rate of HAGA is better than HSA except for N1-N12. Compared with IBHP for C11-C73, cgcut1-cgcut3, and ngcut1-ngcut12 instances, the average filling rate of HAGA can be increased by 0.0527%, 0.486%, and 1.1835%, respectively. Therefore, the HAGA achieved better quality for C11-C73, cgcut1-cgcut3, and ngcut1-ngcut12 instances within reasonable time, with the elimination of equipment and language differences. However, the average filling rate of HAGA on the N1-N12, gcut1-gcut13, and beng1-beng10 instances is worse than LWF and IBHP. For example, the average filling rate of HAGA is only 0.23%, 0.0252%, and 0.0897% lower on these instances for IBHP, respectively. Overall, the HAGA is relatively superior to these three algorithms within a reasonable duration of computational time, especially on the C11-C73, cgcut1-cgcut3, and ngcut1-ngcut12 instances.
In order to observe the performance of different changes of the proposed algorithm, we just run the proposed algorithm on the N1-N12 instances. We first set 0. . Similarly, Figure 9 shows the computational results of different c . From Figure 9, we can observe that 0.2 c = is better. Furthermore, from Figures 8 and 9, it can be seen that the change of parameters has a greater impact on the performance of HAGA as the scale of the instance increases. However, the parameter changes for different problems may achieve better results. In addition, if =0 λ , the algorithm just changes to AGA [26] from the local perspective of the individual fitness; if =1 λ , the algorithm happens to be an adaptive genetic algorithm that changes from the overall perspective of the population evolution. We can see that the proposed algorithm, HAGA, has better performance. According to the results of parameter changes, we can establish a consistent parameter setting for HAGA to obtain good benefits.

Conclusions
In this paper, in order to better solve the 2DRP problem, we analyzed the respective shortcomings of the current two types of adaptive genetic algorithms in detail and proposed an improved method named hybrid adaptive genetic algorithm (HAGA). In the process of providing the solution, the crossover probability and mutation probability of chromosomes are adaptively adjusted according to the collective effect of individual fitness and population evolution process. When using HAGA, the initial population is constructed through a combination of sorting rules and random generation, and operators with better performance are fully used for selection, crossover, and mutation. The heuristic lowest horizontal line algorithm is used as the positioning algorithm to place rectangles. Through continuous iterative optimization of the algorithm, the final packing layout and sheet filling rate are obtained.
The proposed improved method is compared with other representative algorithms. The computational experiments on a wide range of benchmark instances from zero-waste to non-zero-waste problems are implemented. The computational results show that HAGA outperforms the comparison of two adaptive genetic algorithms. Compared with some recent algorithms, the results reveal that HAGA is relatively better than HSA, LWF, and IBHP, especially on the C11-C73, cgcut1-cgcut3, and ngcut1-ngcut12 instances. Moreover, in view of observing the performance of different changes, the experiments were designed a series of λ and c parameters to determine the consistent parameter settings for HAGA. The presented algorithm, which works adaptively through the two perspectives of individual and population evolution, can also be applied to cutting, the Travelling Salesman Problem (TSP), Vehicle Routing Problem (VRP), etc. In the future, the focus of research is to further improve the calculation speed and filling rate of the algorithm for 2DRP problem and strive to find a satisfactory solution for larger scale and difficult benchmark instances.

Institutional Review Board Statement: Not applicable.
Informed Consent Statement: Not applicable.

Data Availability Statement:
The test source data comes from an existing data set. The test source data can be downloaded from http://people.brnel.ac.uk/~mastjjb/jeb/info.html or related literature. The test source data does not belong to us. The experimental result data is calculated by applying the algorithm of this paper to the test source data.

Conflicts of Interest:
The authors declare no conflict of interest.