Keywords: Learning Automata, "Adaptive" Data Structures, Hierarchical Singly-linked Lists, Object Migration Automaton

Optimizing Self-Organizing Lists-on-Lists using Enhanced Object Partitioning O. Ekaba Bisong 1 ⋆ and B. John Oommen 2 ⋆⋆ School of Computer Science, Carleton University, Ottawa, Canada : K1S 5B6. 1 ekaba.bisong@carleton.ca, 2 oommen@scs.carleton.ca

Abstract. The question of how to store, manage and access data has been central to the field of Computer Science, and is even more pertinent in these days when megabytes of data are being generated every second. This paper considers the problem of minimizing the cost of data retrieval from the most fundamental data structure, i.e., a Singly-Linked List (SLL). We consider a SLL in which the elements are accessed by a Non-stationary Environment (NSE) exhibiting so-called "Locality of Reference". We propose a solution to the problem by designing an "Adaptive" Data Structure (ADS) which is created by means of a composite of hierarchical data "sub"-structures to constitute the overall data structure. In this paper, we design an hierarchical Lists-on-Lists (LOLs) by assembling a SLL into an hierarchical scheme that results in a Singly-Linked List on Singly-Linked Lists (SLLs-on-SLLs) comprising of an outer-list and sublist context. The goal is that elements that are more likely to be accessed together are grouped within the same sub-context, while the sublists themselves are moved "en masse" towards the head of the list-context so as to minimize the overall access cost. This move is carried-out by employing the "de-facto" list re-organization schemes, i.e., the Move-To-Front (MTF) and Transposition (TR) rules. To achieve the clustering of elements within the sublists, we invoke the Object Migration Automaton (OMA) family of reinforcement schemes from the theory of Learning Automata (LA). They are introduced so as to capture the probabilistic dependence of the elements in the data structure as it receives query accesses from the Environment. In this paper, we show that SLLs-on-SLLs augmented with the Enhanced Object Migration Automaton (EOMA) minimizes the retrieval cost for elements in NSEs and are superior to the stand-alone MTF and TR schemes, and also superior to the OMA-augmented SLLs-on-SLLs operating in such Environments.

Introduction

The goal of this research endeavor is to further push the frontier of computational efficiency with regards to optimizing the speed of retrieving data from its datastructure. By considering the state-of-the-art, we address this issue by designing an Adaptive Data-Structure (ADS) that uses reinforcement learning schemes and their associated re-organization rules to update itself as it encounters query accesses from the Environment of interaction. The result of such a process is the subsequent minimization of the cost associated with query accesses.

To render the problem realistic, the Environments under consideration in this work are time-varying, i.e., they are Non-stationary Environments (NSEs), where the elements' access probabilities change with time. These Environments exhibit a particular dependency property called "Locality of Reference" where the events are probabilistically dependent on one another. In this work, we consider two such Environments, namely, the Periodic Switching Environment (PSE) and the Markovian Switching Environment (MSE).

The approach we adopt in designing these "Adaptive" Data Structures (ADSs) is to set up a hierarchy of data "sub"-structures. In this research, we employ hierarchical Lists-on-Lists (LOL) data-structures pioneered by Amer and Oommen in [START_REF] Amer | Adaptive list organizing strategies for non-stationary distributions[END_REF] for Singly-Linked Lists (SLLs) on Singly-Linked Lists. The LOL concept consists of an outer-list and many sublists, whose elements are called the outer and sublist contexts respectively. In this framework, elements that are more likely to be accessed together are grouped within the same sub-context, while the sublists are moved "en masse" towards the head of the list-context by following a re-organization rule.

In order to capture the probabilistic dependence of the elements in the data structure, based on the query accesses from the Environment, we employ a set of reinforcement learning schemes derived from the theory of Learning Automata (LA). These reinforcement schemes are variants of the so-called "Object Migration Automaton" (OMA).

The pioneering work of Amer and Oommen in [START_REF] Amer | Adaptive list organizing strategies for non-stationary distributions[END_REF] utilized the OMA algorithm to capture the probabilistic dependence of the queries coming from the Environment. The introduction of the OMA mitigated the static ordering of the sublists so that the elements can move freely from one sublist partition to another as the OMA learns the optimal sublist grouping. The addition of the OMA to the primitive hierarchical schemes, resulted in the MTF-MTF-OMA, and TR-MTF-OMA, where the third component in the triple is LA used.

Unfortunately, the OMA algorithm used in the literature [START_REF] Amer | Adaptive list organizing strategies for non-stationary distributions[END_REF] suffers from a deadlock1 impediment that prevents it from converging to its optimal grouping. This is because the accessed element can be swapped from one sublist to another and then back to the original sublist. This deadlock phenomenon was mitigated by the Enhanced Object Migration Automaton (EOMA) in [START_REF] Gale | Improvements to an algorithm for equipartitioning[END_REF]. The EOMA forbids such "false alarm" swaps of elements between sublists, and also avoids pointless swaps between the various sublists themselves. Moreover, the EOMA acknowledges that the sublist has converged when the elements are within a few of the most internal states. By this, it is certain about the identity of the elements that should constitute a sublist. This work augments the hierarchical SLLs-on-SLLs schemes with the EOMA. The design in this work yielded the MTF-MTF-EOMA, MTF-TR-EOMA, TR-MTF-EOMA and the TR-TR-EOMA schemes.

Contributions of this Paper

In summary, the novel contributions of this paper include:

-The design and implementation of the EOMA-enhanced SLLs-on-SLLs; -The inclusion of the MTF-TR, and TR-TR enhanced hierarchical schemes as part of the SLLs-on-SLLs class of ADS design; -Demonstrating the superiority of the EOMA-augmented hierarchical schemes to the MTF and TR rules when the outer-list context is the MTF; -Demonstrating superiority of the EOMA-augmented hierarchical schemes to the original OMA-augmented schemes that pioneered the idea of a hierarchical LOL approach, with the "Periodic" and "UnPeriodic" versions; -Showing that as the periodicity T increased in the PSE, the asymptotic cost is further minimized.

Outline of this Paper

Section 1 makes the case for minimizing retrieval costs in NSEs. Section 2 surveys2 the theory of LA, which forms the framework for the EOMA used in learning the true partition of objects into groups. The section addresses the concept of "Locality of Reference" in NSEs and outlays the models of dependence used in this work to simulate state probabilities. Section 4 discusses the "de-facto" MTF and TR adaptive list organizing schemes for NSEs and why they constitute the primitive rules for the hierarchical LOL data-structures. Section 5 explains the rationale for using data "sub"-structures in designing the SLLs-on-SLLs giving rise to the MTF-MTF, MTF-TR, TR-MTF and TR-TR hierarchical schemes with static dependence capturing, making the case for an adaptive capturing mechanism. Section 6 explains the EOMA reinforcement algorithm and how it augments the Hierarchical SLLs. Section 7 presents the Results and Discussions, and Section 8 concludes the paper.

2 Theoretical Background

The Field of Learning Automata

An Automaton, by definition, models an autonomous agent, whose behavior manifests as a consequence of the interplay between a sequence of stimuli from the Environment. The Automaton responds adaptively to the Environment and enforces the actions which fit the highest perceivable rewards from among a predetermined set of actions. Such an automaton is referred to as a Learning Automaton (LA) [START_REF] Bisong | On Designing Adaptive Data Structures with Adaptive Data[END_REF][START_REF] Narendra | Learning Automata: An Introduction[END_REF]. Oommen and Ma proposed the Object Migrating Automata (OMA) [START_REF] Oommen | Deterministic learning automata solutions to the equipartitioning problem[END_REF][START_REF] Oommen | Stochastic automata solutions to the object partioning problem[END_REF] to solve a special case of the OPP, namely the Equi-Partitioning Problem (EPP). The introduction of the OMA solution made reallife applications possible, because the prior art [START_REF] Yu | Adaptive clustering schemes: General framework[END_REF] was an order of magnitude slower. The OMA resolved the EPP both efficiently and accurately, and it could thus be easily incorporated into many real-life application domains [START_REF] Bisong | On Designing Adaptive Data Structures with Adaptive Data[END_REF][START_REF] Fayyoumi | A fixed structure learning automaton microaggregation technique for secure statistical databases[END_REF][START_REF] Fayyoumi | Achieving microaggregation for secure statistical databases using fixed-structure partitioning-based learning automata[END_REF].

The OMA

In the partitioning problem, the underlying distribution of the objects among the classes is unknown to the OMA, and its goal is to migrate the objects between its classes, using the incoming queries specified by an Environment, denoted as E. This should be done in such a way that the partitioning error is minimized as the queries are encountered. Such an Environment and its associated query generating system can be characterized by three main parameters, namely, the number of objects, specified by W , the number of groups or partitions, specified by R, and a quantity 'p' , which is the probability specifying the certainty by which E pairs the elements in the query.

In our model, every query presented to the OMA by E consists of two objects, and this can be easily generalized for queries of larger sizes. Consider the case in which we have 3 classes with 3 objects, i.e., a system which has a total of 9 objects. This is depicted in Figure 1. E randomly selects an initial class with probability 1 R , and it then chooses the first object in the query from it, say, q 1 . The second element of the pair, q 2 , is then chosen with the probability p from the same class, and with the probability (1p) from one of the other classes uniformly, each of them being chosen with the probability of 1 R-1 . In Figure 1, the three classes are named G 1 , G 2 and G 3 , and the objects inside them are represented by integers in {1, • • • , 9}. The original distribution of the objects between the classes is shown in Figure 1, at the extreme left. This is the true unknown state of nature, i.e., Ω * . The OMA is initialized in a purely random manner by the numbers within the range. This step is depicted at the right of Figure 1, and Ω 0 indicates the initial state of the OMA. At every iteration, a pair given by E is processed by the OMA, and it performs a learning step towards its convergence. The goal of the algorithm is for it to converge to a state, say Ω + . In an optimal setting, we would hope that Ω + is identical to Ω * .

The OMA is a Fixed Structure Stochastic Automata (FSSA) designed to solve the EPP. It is defined as a quintuple with R actions, each of which represents a specific class, and for every action there exists a fixed number of states, N . Every abstract object from the set O resides in a state identified by a state number, and it can move from one state to another, or migrate from one group3 to another. Thus, if the abstract object O i is located in state ξ i belonging to a specific group (an action or class) α k , we say that O i is assigned to class k. If two objects O i and O j happen to be in the same class and the OMA receives a query A i , A j , they will be jointly rewarded by the Environment. Otherwise, they will be penalized. Our task is to formalize the movements of the {O i } on reward and penalty.

For every action α k , there is a set of states {φ k1 , • • • , φ kN }, where N is the fixed depth of the memory, and where 1 ≤ k ≤ R represents the number of desired classes. We also assume that φ k1 is the most internal state and that φ kN is the boundary state for the corresponding action. The reward and penalty responses are defined as follows: Reward: Given a pair of physical objects presented as a query A i , A j , if both O i ,and O j happen to be in the same class α k , the reward scenario is enforced, and they are both moved one step toward the actions's most internal state4 , φ k1 . Penalty: If, however, they are in different classes, α k and α m , (i.e., O i , is in state

ξ i where ξ i ∈ {φ k1 , • • • , φ kN } and O j , is in state ξ j where ξ j ∈ {φ m1 , • • • , φ mN })
they are moved away from φ k1 and φ m1 as follows:

1. If ξ i = φ kN and ξ j = φ mN , then we move O i and O j one state toward φ kN and φ mN , respectively. 2. If ξ i = φ kN or ξ j = φ mN but not both (i.e., only one of these abstract objects is in the boundry state), the object which is not in the boundary state, say O i , is moved towards its boundary state. Simultaneously, the object that is in the boundary state, O j , is moved to the boundary state of O j . Since this reallocation will result in an excess of objects in α k , we choose one of the objects in α k (which is not accessed) and move it to the boundary state of α m . In this case, we choose the object nearest to the boundary state of ξ i . 3. If ξ i = φ kN and ξ j = φ mN (both objects are in the boundary states), one object, say O i , will be moved to the boundary state of α m . Since this reallocation, will again, result in an excess of objects in α m , we choose one of the objects in α m (which is not accessed) and move it to the boundary state of α k . In this case, we choose the object nearest to the boundary state of ξ j .

The above rules are figuratively shown in [START_REF] Bisong | On Designing Adaptive Data Structures with Adaptive Data[END_REF]. The algorithm invokes the procedures "ProcessReward" and "ProcessPenalty" given algorithmically in [START_REF] Bisong | On Designing Adaptive Data Structures with Adaptive Data[END_REF].

Environments with Locality of Reference

Non-Stationary Environments (NSEs) deal primarily with learning in settings that change with time. Thus, in a NSE, c i (n) changes with time.

In the context of an ADS, this variation affects the expected query cost because the Environment exhibits so-called "Locality of Reference", or is characterized by dependent accesses. Locality of Reference occurs when there exists a probabilistic dependence between the consecutive queries [START_REF] Bachrach | On the competitive theory and practice of online list accessing algorithms[END_REF]. Thus, there is a considerably small number of unrelated queries within a segment of the accesses.

Given a set of n distinct elements, if we split it into k disjoint and equal partitions with m elements where n = k.m, the k subsets can be considered to be local or "sub"-contexts. If the elements within a sub-context k i exhibit Locality of Reference, it implies that if an element from set k i is queried at time t, there exists a high likelihood that the next queried element will also arrive from the same set k i . Thus, the Environment itself can be modeled to have a finite set of states {Q i |1 ≤ i ≤ k}, and the dependent model defines the transition from one Environmental state to another.

Learning schemes with fixed policies may become non-expedient over time, rendering them inadequate for such Environments. The goal is to have schemes which possess enough flexibility to choose actions that minimize the expected penalty. Two models of NSEs critical to this research are the Markovian Switching Environments (MSEs), and the Periodic Switching Environments (PSEs). Markovian Switching Environments (MSEs): Consider an Environment with 128 distinct records, that are divided into k = 4 subsets, with 32 contiguous elements in each subset. In such a case, the set of states

{Q 1 , Q 2 , Q 3 , Q 4 }, could be Q 1 = {1 . . . 32}, Q 2 = {33 . . . 64}, Q 3 = {65 . . . 96}, and Q 4 = {97 . . . 128}.
The Markovian Switching Environment (MSE) models each subset as the states of the Environment as the states of a Markov chain. If the probability of the Environment choosing a record from the current subset is 0.9, the probability of switching to another subset is equally divided among the other three subsets. After a query is generated from Q 1 , the Environment remains in that state with probability α and moves to a different state with probability 1-α k-1 . Periodic Switching Environments (PSEs): The Periodic Switching Environment (PSE) on the other hand changes the state of the Environment in a round-robin fashion, i.e., after every T queries, the Environment changes state from Q i to Q i+1 mod k . This implies that each set of T consecutive queries belong to the same sub-context. Further, there are two variations that define the PSE model; the first is when the data structure is aware of the change of state in the query generator ("Periodic"), and the other is when the data structure is unaware of the state change ("UnPeriodic"). Understandably, the performance of the scheme is better when the ADS is aware of the Environment's state change.

Models of Dependence

The Environment generates queries according to a probability distribution. This work considered five different types of query distributions, namely, the Zipf, Eighty-Twenty, Lokta, Exponential and Linear distributions. For a given list of size J, divided into k sublists, with each sublist containing J k elements, the probability distribution {s i } where 1 ≤ i ≤ m describes the query accesses for the elements in the subset k. Thus, the total probability mass for the accesses in each group is the same, and the distribution within each group has the specified distribution. The distributions for these generators are described below.

1. The Zipf distribution: The access probabilities for the Zipf query generator is given as:

s i = 1 iHm , for 1 ≤ i ≤ m
, where H m is the m th Harmonic number and defined as H m = m j=1 ( 1 j ). The Zipf distribution is the most commonly-used one for modelling real-life access probabilities. 2. The 80-20 distribution: The access probabilities for the 80-20 query generator is given as:

s i = 1 i (1-θ) H (1-θ) m
, for 1 ≤ i ≤ m and θ = log 0.80 log 0.20 ≈ 0.1386, where H

(1-θ) m
is the m th Harmonic number of order (1θ), and is given by m j=1 ( 1 j (1-θ) ). 3. The Lotka distribution: The access probabilities for the Lotka query generator is given as:

s i = 1 i 2 H 2 m
, for 1 ≤ i ≤ m, where H 2 m is the m th harmonic number of order 2, and is given by m j=1 ( 1 j 2 ). 4. The Exponential distribution: The access probabilities for the Exponential query generator is given as:

s i = 1 2 i K , for 1 ≤ i ≤ m, where K = m j=1 ( 1 2 j ).

The Linear distribution:

The access probabilities for the Linear query generator is given as:

s i = K(m -i + 1), for 1 ≤ i ≤ m
, where K is determined as the constant which normalizes the {s i } to be a distribution.

A rationale for conducting the simulations with these query distributions is that, for the most part, they result in "L-shaped" graphs which assign high probabilities to a small number of the sublist elements. This is true for the Exponential and Lotka distribution, and to an extent, for the Zipf distribution.

Adaptive Lists-on-Lists (LOL)

Self-organization is the ability for a list to re-order its constituent elements in response to queries from the underlying query system, that serves as an Environment. The probability distribution of the query accesses is unknown to the list re-organization algorithm. The goal of this re-organization, among others, is to minimize the asymptotic cost or access-time of record retrieval.

The cost models employed in evaluating list access costs are the asymptotic cost, which is the ensemble mean of the final time-average cost after a convergence threshold, and the amortized cost, which is the mean overall query costs [START_REF] Bentley | Amortized analyses of self-organizing sequential search heuristics[END_REF][START_REF] Hester | Self-organizing linear search[END_REF][START_REF] Sleator | Amortized efficiency of list update and paging rules[END_REF]. In studying ADSs, one assumes that the Environment will not request a record absent from the list, and that each record is retrieved at least once [START_REF] Hester | Self-organizing linear search[END_REF].

The simplest and yet most prominent Adaptive Lists are the Move-to-Front (MTF) and the Transposition rule (TR) adaptive schemes. The MTF update heuristic moves the queried element to the front of the list. In the TR, a queried record (if not at the front) is moved one position towards the front of the list.

For Environments with Locality of Reference, the MTF and TR have been shown to be superior to other deterministic schemes such as FC, MRI(0) and TS(0) [START_REF] Bachrach | On the competitive theory and practice of online list accessing algorithms[END_REF]. Further, the time and space complexities involved in implementing other composite MTF and TR schemes (the details of which are omitted here) such as the MHD(k) [START_REF] Rivest | On self-organizing sequential search heuristics[END_REF], the POS(k) and the SWITCH(k) [START_REF] Tenenbaum | Two spectra of self-organizing sequential search algorithms[END_REF] and other probabilistic approaches such as the SP LIT algorithm [START_REF] Irani | Two results on the list update problem[END_REF], the JUMP [START_REF] Hester | Self-organizing search lists using probabilistic back-pointers[END_REF], MTF2, Randomized MTF (RMTF), and the Randomized move ahead (RMHD) schemes [START_REF] Bachrach | On the competitive theory and practice of online list accessing algorithms[END_REF] render most of them impractical for real-world settings.

Hierarchical Data "Sub"-structures

The novel idea that we propose is to combine the MTF and TR rules to take advantage of the quick updates of the MTF rule, and the asymptotically stable convergence of the TR rule, in designing the improved hierarchical strategies. The concept of a hierarchical data "sub"-structure involves dividing a list of size J into k sublists. A re-organization strategy is then hierarchically applied to the list by first considering the elements within the sublist (also called the sub-context) and then operating over the sublists (or sub-contexts) themselves.

As mentioned earlier, the primitive re-organization strategies involved are the MTF and TR rules. When used in a hierarchical scheme, this yields the MTFpreceding-MTF, (MTF-MTF), MTF-preceding-TR, (MTF-TR), TR-preceding-MTF, (TR-MTF), and TR-preceding-TR, (TR-TR) schemes. For example, in the case of MTF-TR, the element within a sub-context is first moved to the front of the list, and then the sub-context is moved to the front of the list context. The hierarchical schemes on their own, however, perform worse than standalone schemes such as the MTF and TF in NSEs. The drawback is due to the fact that the hierarchical schemes make an assumption that the elements within a specific a priori sub-context have a probabilistic dependence. But this is often not the case as the elements in the list initially are ordered in an arbitrary manner. To mitigate this shortcoming, we will later argue that we must design a mechanism to adaptively group the elements that have a probabilistic dependence within the same sub-context.

EOMA-Augmented Hierarchical SLLs-on-SLLs

The "Enhanced" OMA (EOMA) is an upgraded embodiment of the OMA algorithm proposed by the authors of [START_REF] Gale | Improvements to an algorithm for equipartitioning[END_REF] to mitigate the susceptibility of the OMA algorithm to a "deadlock situation" which prevents the algorithm from converging to the objects' optimal partitioning. The deadlock condition is actually exacerbated when the algorithm is interacting with a near-optimal Environment (e.g., when p = 0.9) by considerably slowing down the convergence rate even if the problem complexity is small.

The deadlock phenomenon occurs when there is a query pair O i , O j in a stream of query pairs belonging to different actions, α m and α k . If one object is in the boundary state of its action, and the other is not, the query pairs are prevented from converging to their optimal ordering, and this can lead to an "infinite" loop scenario. To mitigate this, if there exists an object in the boundary state of the group containing O j , the EOMA swaps O i with the object in this boundary state (Figure 3). Otherwise, the update is identical to the OMA.

φhM Oi φhM-1 φhM-2 • • • φh1 αh Ol φgM φgM-1 • • • φg3 Oj φg2 φg1
αg Fig. 3: Resolving the deadlock scenario with EOMA for the case when only one object is in the boundary state.

The EOMA also redefines the concept of the convergence condition so as to reduce the algorithms vulnerability to divergent queries. This modification designates the two-innermost states as the "final" states, as opposed to just the innermost state in the vanilla OMA. A marginally superior solution specifies a parameter m, to designate the m innermost states of each action to be the convergence condition. More details on the EOMA are found in [START_REF] Gale | Improvements to an algorithm for equipartitioning[END_REF][START_REF] Shirvani | Novel Solutions and Applications of the Object Partitioning Problem[END_REF].

The augmentation of the hierarchical SLLs based on the EOMA reinforcement scheme results in a new set of hierarchical strategies, namely, the MTF-MTF-EOMA, MTF-TR-EOMA, TR-MTF-EOMA and the TR-TR-EOMA.

Results and Discussions

The experimental setup involved a list of size 128, split into k sublists, where k ∈ {2, 4, 8, 16, 32, 64}. In the MSE, the probability of subsequent query accesses coming from the same sublist, α, was set to 0.9, while the PSE had the hyper-parameter for the number of queries to arrive from the query space before switching to another pattern, T = 30. For all the results reported in this section, the simulation setup involved an ensemble of 10 experiments, each constituting 300,000 query accesses. In the interest of brevity, we report the results for k = 8. From the simulation results in Table 1, with k = 8, we observed that for the MSE, the hierarchical schemes with EOMA generally outperformed their standalone counterparts in both the asymptotic (top of the table) and amortized (bottom of the table) costs for all instances except the Exponential distribution. In the Exponential distribution, the stand-alone MTF and TR schemes had a slightly superior performance to the EOMA-augmented hierarchical schemes. This is because the MTF and TR rules are competitive in Environments with an L-shaped curve such as the Exponential distribution, because they assign higher probabilities to a small subset of the elements in the query system. Table 2 compared the performance of the EOMA-augmented hierarchical schemes with the stand-alone MTF and TR schemes in PSEs when the number of sublists k = 8. Here we saw that the hierarchical schemes with the EOMA performed better than their stand-alone counterparts, except for the Exponential distribution with the same reason as in the MSE. However, when the concept of "periodicity" was introduced into the EOMA-augmented hierarchical schemes, the search cost is an order of magnitude superior to other schemes. From Figure 4, it is easy to observe that from the first few queries, all the EOMA-augmented hierarchical schemes perform better than the TR rule in minimizing the amortized cost. Right about the 10, 000 th query, the EOMAaugmented hierarchical schemes catches-up with the MTF rule in terms of performance and from thereon boasts a far superior performance compared to the MTF. A key observation is that the EOMA-augmented hierarchical schemes appeared to converge after about 30,000 queries. As opposed to this, the MTF and TR schemes quickly plateaued with no additional gains in performance with extended interactions with the Environment. Although Figure 4 shows the rate of convergence for the Zipf distribution, the observed phenomena were similar for the 80-20, Lotka, Exponential and Linear distributions.

In Periodic Environments, the hierarchical schemes that incorporated the EOMA were able to boost their performance if they possessed an insight into the period, T , of the Environment (see Figure 5). This implied that the schemes could preempt the EOMA's ordering by moving the first sublist to the end of the list after T queries. This move was predicated on the observation that the elements from the completed query space would not be requested again until after (k -1)T queries. Schemes with such a prior awareness of period T are referred to by including the prefix "Periodic", leading to the MTF-MTF-EOMA-Periodic, MTF-TR-EOMA-Periodic, TR-MTF-EOMA-Periodic and TR-TR-EOMA-Periodic respectively. Also, without explicitly knowing the value of T , the hierarchical schemes were able to infer the period, T , of the Environment by moving the first sublist to the end of the list if two successive queries to the EOMA were not in the same group. These periodic variations were suffixed by "UnknownPeriod", yielding the MTF-MTF-EOMA-UnknownPeriod, MTF-TR-EOMA-UnknownPeriod, TR-MTF-EOMA-UnknownPeriod and TR-TR-EOMA-UnknownPeriod schemes.

Conclusion

In this research we studied the area of Adaptive Data Structures (ADSs) and considered the relatively novel concept of having lists whose basic primitive elements were themselves sub-lists, with ADS operations being done on the elements and on the sublists. In order to break the static arrangement of their sublists, we incorporated the EOMA (from the field of Learning Automata (LA)) into the hierarchical schemes. The EOMA enabled the hierarchical schemes to capture the probabilistic dependence ordering of the query accesses from the Environment. Further, the paper discussed the performance of the MTF-MTF-EOMA, MTF-TR-EOMA, TR-MTF-EOMA and the TR-TR-EOMA for various sublist values of k, various distributions, and various types of non-stationarity.

The overall observation that we could make is that the MTF-MTF-EOMA and the TR-MTF-EOMA perform better than the MTF-TR-EOMA and the TR-TR-EOMA. One can almost categorically state that, the schemes having the TR as its outer-list re-organization strategy were inferior to the MTF, when we compared their asymptotic and amortized costs. However, the observed poor performance of the MTF-TR-EOMA and the TR-TR-EOMA schemes as k increases, were mitigated in the PSEs when a knowledge of the period, T , was incorporated into the hierarchical scheme.

Fig. 1 :

 1 Fig. 1: A figure describing the partitioning of the objects.

Fig. 2 :

 2 Fig. 2: A diagrammatic description of the MTF-MTF Hierarchical scheme

Fig. 4 :

 4 Fig.4: Rate of convergence of the first 100,000 queries for the stand-alone and the EOMA-augmented hierarchical schemes in a MSE.

Fig. 5 :

 5 Fig. 5: Asymptotic cost of Periodic variations of MTF-MTF-EOMA in the Zipf distribution. PSE with period T = 30 and k = {k : 2, 4, 8, 10, 16, 32, 64}.

Although this is referred to as a "deadlock" in the literature, it could probably, be better termed as a "livelock".

Due to space limitations, it is obvious that the background material will be surveyed very briefly. More details of the various concepts concerning LA can be found in[START_REF] Narendra | Learning Automata: An Introduction[END_REF], and the details of the applications of the OMA, the EOMA and the state-of-the-art regarding ADSs etc. is found in the MCS thesis of the first author[START_REF] Bisong | On Designing Adaptive Data Structures with Adaptive Data[END_REF]. This thesis can be made available to the reader.

As in the field of LA, we use the terms "action", "class" and "group" synonymously.

The actual figure describing the schematic of transitions of the LA is given in[START_REF] Bisong | On Designing Adaptive Data Structures with Adaptive Data[END_REF], and is omitted here in the interest of space.

A study of the various graphs that we have obtained seems to imply that there is a way by which we can group the various schemes themselves using a higher level statistical analysis. Such a study remains open.


Will Serrano
email: g.serrano11@imperial.ac.uk

The Blockchain Random Neural Network in Cybersecurity and the Internet of Things

Keywords: Neural Network, Internet of Things, Blockchain, Cybersecurity, User Management, Access Credentials Key Neuron y

The Internet of Things (IoT) enables increased connectivity between devices; however, this benefit also intrinsically increases cybersecurity risks as cyber attackers are provided with expanded network access and additional digital targets. To address this issue, this paper presents a holistic digital and physical cybersecurity user authentication method based on the Blockchain Random Neural Network. The Blockchain Neural Network connects increasing neurons in a chain configuration providing an additional layer of resilience against Cybersecurity attacks in the IoT. The proposed user access authentication covers holistically its digital access through the seven OSI layers and its physical user identity such as passport before the user is accepted in the IoT network. The user's identity is kept secret codified in the neural weights, although in case of cybersecurity breach, its physical identity can be mined, and the attacker identified, therefore enabling a safe decentralized confidentiality. The validation results show that the addition of the Blockchain Neural Network provides a user access control algorithm with increased cybersecurity resilience and decentralized user access and connectivity.

Introduction

In the Internet of Things (IoT), things are objects of the physical world (physical things) that can be sensed, or objects of the information world (virtual things) that can be digitalized; both are capable of being identified and integrated into information and transmitted via sensor and wired or wireless communication networks [1]. The IoT enables comprehensive connectivity between devices; however, this benefit also intrinsically increases cybersecurity risks as cyber attackers are provided with expanded network access and additional digital targets [START_REF] Andrea | Internet of Things: Security Vulnerabilities and Challenges[END_REF][START_REF] Deogirikar | Security attacks in IoT: A survey[END_REF][START_REF] Granjal | Security for the Internet of Things: A Survey of Existing Protocols and Open Research Issues[END_REF].

Blockchain enables the digitalization of contracts as it provides authentication between parties and information encryption of data that gradually increments while it is processed in a decentralized network such as the IoT [START_REF] Huh | Managing IoT devices using Blockchain platform[END_REF]. Due to these features, Blockchain has been already applied in Cryptocurrency [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System -Bitcoin[END_REF], Smart Contracts [START_REF] Watanabe | Blockchain contract: Securing a blockchain applied to smart contracts[END_REF], Intelligent Transport Systems [START_REF] Yuan | Towards blockchain-based intelligent transportation systems[END_REF] and Smart Cities [START_REF] Biswas | Securing Smart Cities Using Blockchain Technology[END_REF].

Research Motivation

To address the increased cybersecurity risk of the IoT, this paper proposes a holistic digital and physical cybersecurity user authentication method based on the Blockchain Random Neural Network [START_REF] Serrano | The Random Neural Network with a Blockchain Configuration in Digital Documentation[END_REF]. The Blockchain Neural Network connects neurons in a chain configuration providing an additional layer of resilience against Cybersecurity attacks in the IoT. The Cybersecurity and IoT application presented on this paper can be generalized to emulate an Authentication, Authorization and Accounting (AAA) server where user access information is encrypted in the neural weights and stored decentralized servers.

The Blockchain Neural Network solution is equivalent to the Blockchain with the same properties: user authentication, data encryption and decentralization where user access credentials are gradually incremented and learned while travelling or roaming. The Neural Network configuration have analogue biological properties as the Blockchain where neurons are gradually incremented and chained through synapses as variable user access credentials increase; information is stored and codified in decentralized neural networks weights. The main advantage of this research proposal is the biological simplicity of the solution however it suffers high computational cost when the neurons increase.

Research Proposal

Internet of Things and the Blockchain related work is described in Section 2. The proposed user access authentication described in Section 3 covers holistically its digital access through the seven OSI layers and its physical user identity such as passport ID before the user is allowed to use IoT network resources. The method forces the user to be physically authenticated before establishing the connection that allows access to the IoT network, therefore cybersecurity is increased by reducing the likelihood of criminal network access. The user's digital OSI layer identification such as MAC and IP address and physical identification such as biometrics generates the Private Key whereas there is no need for a Public Key, therefore this paper defines a truly decentralized solution with the same Blockchain validation process: mining the input neurons until the neural network solution is found as presented in Section 4.

Experimental results in Section 5 show that the additional Blockchain neural network provides increased cybersecurity resilience and decentralized confidentiality to user access and connectivity. The main conclusion presented in Section 6 proves that the user physical identity is kept secret codified in the neural weights although in case of cybersecurity breach the identity can be mined and the attacker identified by its passport ID or biometrics.

Related work

Internet of Things

The IoT has provided new services and applications with additional Cybersecurity issues. G. Lee et al [START_REF] Lee | Internet of Things[END_REF] present the evolution of the IoT technology started from Machine to Machine to connect machines and devices, Interconnections of Things that connect any physical or virtual object and finally Web of Things that enables the collaboration between people and objects. The IoT is formed of three layers, as proposed by Q. Jing et al [START_REF] Jing | Security of the Internet of Things: perspectives and challenges[END_REF]: sensor, transportation and application that similar as traditional networks, also have security issues and integration challenges. R. Roman et al [START_REF] Roman | Securing the Internet of Things[END_REF] state that because physical, virtual and user private information is captured, transmitted and shared by the IoT sensors, Cybersecurity aspects on data confidentiality and authentication, access control within the IoT network, identity management, privacy and trust among users and things; the enforcement of security and privacy policies shall be also considered and implemented. S. Sicari et al [START_REF] Sicari | Security, privacy and trust in Internet of Things: The road ahead[END_REF] declare that the dynamic IoT is formed by heterogeneous technologies to provide innovative services in various application domains which shall meet flexible security and privacy requirements where traditional security countermeasures cannot be directly applied due the different standards, communication protocols and scalability issues because of the high number of interconnected devices. An important challenge for supporting diverse multimedia applications in the IoT is the security heterogeneity of wired and wireless sensor and transmission networks that requires a balance between flexibility and efficiency, as presented by L. Zhou et al [START_REF] Zhou | Multimedia Traffic Security Architecture for the Internet of Things[END_REF]. Secure and Safe Internet of Things (SerI-oT) was proposed by E. Gelenbe et al [START_REF] Gelenbe | Security for Internet of Things: The SerIoT Project[END_REF] to improve the information and physical security of different operational IoT applications platforms in a holistic and crosslayered manner. SerIoT covers areas such as mobile telephony, networked health systems, the Internet of Things, Smart Cities, Smart Transportation Systems, Supply Chains and Industrial Informatics [17]

Neural Networks in Cryptography

Neural Networks have been already applied to Cryptography; D. Pointcheval [START_REF]Neural Networks and their Cryptographic Applications[END_REF] presents a linear scheme based on the Perceptron problem or N-P problem suited for smart cards applications. W. Kinzel et al [START_REF] Kinzel | Interacting Neural Networks and Cryptography Secure exchange of information by synchronization of neural networks[END_REF] train two multilayer neural networks on their mutual output bits with discrete weights to achieve a synchronization that can be applied to secret key exchange over a public channel. A. Klimov et al [START_REF] Klimov | Analysis of Neural Cryptography[END_REF] propose three cryptanalytic attacks (genetic, geometric and probabilistic) to the above neural network. E. Volna et al [START_REF] Volna | Cryptography based on the Neural Network[END_REF] apply feed forward neural networks as an encryption and decryption algorithm with a permanently changing key. A. Yayık et al [START_REF] Yayık | Neural Network based cryptography[END_REF] present a two-stage cryptography multilayered neural network where the first stage generates neural network-based pseudo random numbers and the second stage, a neural network encrypts information based on the non-linearity of the model. T. Schmidt [START_REF] Schmidt | A review of applications of artificial neural networks in cryptosystems[END_REF] et al present a review of the use of artificial neural networks in cryptography.

2.3

Blockchain in Security

Currently; there is a great research effort in Blockchain Algorithms applied to security applications. D. Xu et al [START_REF] Xu | Game theoretic study on blockchain based secure edge networks[END_REF] propose a punishment scheme based on the action record on the blockchain to suppress the attack motivation of the edge servers and the mobile devices in the edge network. S.-C. Cha et al [START_REF] Cha | An ISO/IEC 15408-2 Compliant Security Auditing System with Blockchain Technology[END_REF] utilize a blockchain network as the underlying communication architecture to construct an ISO/IEC 15408-2 compliant security auditing system. K. Gai et al [START_REF] Gai | Blockchain-Enabled Reengineering of Cloud Datacenters[END_REF] propose a conceptual model for fusing blockchains and cloud computing over three deployment modes: Cloud over Blockchain, Blockchain over Cloud and Mixed Blockchain-Cloud. Y. Gupta et al [START_REF] Gupta | The applicability of blockchain in the Internet of Things[END_REF] propose a Blockchain consensus model for implementing IoT security. R. Agrawal et al [START_REF] Agrawal | Continuous Security in IoT Using Blockchain[END_REF] present a Blockchain mechanism that evaluates legitimate presence of user in valid IoT-Zone continuously without user intervention.

Blockchain Neural Network in the Internet of Things

Blockchain [START_REF] Nakamoto | Bitcoin: A Peer-to-Peer Electronic Cash System -Bitcoin[END_REF] is based on cryptographic concepts which can be applied similarly by the use of Neural Networks. Information in the Blockchain is contained in blocks that also include a timestamp, the number of attempts to mine the block and the previous block hash. Decentralized miners then calculate the hash of the current block to validate it. Information contained in the Blockchain consists of transactions which are authenticated by a signature that uses the user private key, transaction origin, destination and value (Figure 1).

The Random Neural Network

The proposed Blockchain configuration is based on the Random Neural Network (RNN) [START_REF] Gelenbe | Random Neural Networks with Negative and Positive Signals and Product Form Solution[END_REF][START_REF] Gelenbe | Learning in the Recurrent Random Neural Network[END_REF][START_REF] Gelenbe | G-Networks with Triggered Customer Movement[END_REF] which is a spiking neuronal model that represents the signals transmitted in biological neural networks, where they travel as spikes or impulses, rather than as analogue signal levels. The RNN is a spiking recurrent stochastic model for neural networks where its main analytical properties are the "product form" and the existence of the unique network steady state solution.

3.2

The Random Neural Network with Blockchain configuration

The Random Neural Network with Blockchain configuration consists of L Input Neurons, M hidden neurons and N output neurons Network (Figure 2). Information in this model is contained networks weights w + (j,i) and w -(j,i) rather than neurons xL, zM, yN.

x 1 w + (j,i): excitatory network weights The main concept of the Random Neural Network Blockchain configuration is that the neuron vector sizes, L, M and N are variable instead of fixed. Neurons or blocks are iteratively added where the value of the additional neurons consists on both the value of the additional information and the value of previous neurons therefore forming a neural chain. Information in this model is transmitted in the matrixes of network weighs, w + (j,i) and w -(j,i) rather than in the neurons. The input layer X represents the user's incremental verification data; the hidden layer Z represents the values of the chain and the output layer Y represents the user Private Key.

x 2 x L z 1 z 2 z M

Cybersecurity and the Internet of Things Blockchain Model

Cybersecurity and the Internet of Things in the Neural Network Blockchain model described in this section is based on the main concepts shown on Figure 3: • Private key, yN;

• Roaming, R(t) and Verification, V;

• Neural Chain network and Mining; • Decentralized information, w + (j,i) and w -(j,i).

Private key

The private key Y = (y1, y2, … , yN) consists on the user digital AAA authentication credentials that covers the seven layers of the OSI model and physical information such as a passport, biometrics or both. The private key is presented by the user every time its credentials require verification from the accepting roaming node (Table 1).

4.2

Roaming and Verification

Let's define Roaming and Verification as:

• Roaming, R(t) = {R(1), R(2), … R(t)} as a variable vector where t is the roaming number; • Verification, V = {v1, v2, … vt} as a set of t I-vectors where vo = (eo1, eo2, … eoI) and eo are the I different dimensions for o=1,2, ... t.

The first Roaming R(1) has associated an input state X = xI which corresponds to v1 and represents the user verification data. The output state Y = yN corresponds to the user Private Key and the hidden layer Z = zM corresponds to the value of the neural chain that will be inserted in the input layer for the next roaming.

The second Roaming R(2) has associated an input state X = xI which corresponds to the user verification data v1 for the first Roaming R(1), the chain (or the value of the hidden layer zM) and the additional user data v2. The output state Y = yN still corresponds the user Private Key and the hidden layer Z = zM corresponds to the value of the neural chain for the next transaction. This process iterates as more user verification data is inserted. The neural chain can be formed of the values of the entire hidden layer neurons, a selection of neurons, or any other combination to avoid the reverse engineering of the user identity from the stored neural weights.

Neural Chain Network and Mining

The first Roaming R(1) calculates the Random Neural Network neural weights with an Ek < Y for the input data I = (ΛL, λL) and the user private key Y = yN. The calculated network weights w + (j,i) and w -(j,i) are stored in the decentralized network and are retrieved in the mining process. After the first Roaming; the user requires to be validated at each additional Roaming with its private key where its verification data is validated and verification data vt from Roaming R(t) are added to the user. Verification data is validated or mined by calculating the outputs of the Random Neural Network using the transmitted network weighs, w + (j,i) and w -(j,i) at variable random inputs i, or following any other method. The solution is found or mined when quadratic error function Ek is lesser than determined minimum error or threshold T:

E k = 1 2 ∑(y' n -y n ) 2 N n=1 <T ( 1
)
where Ek is the minimum error or threshold, y'n is the output of the Random Neural Network with mining or random input I and yn is the user Private Key. The mining complexity can be tuned by adjusting Ek. The Random Neural Network with Blockchain configuration is mined when an Input I is found that delivers an output Y with an error Ek lesser than a threshold T for the retrieved user network weights w + (j,i) and w -(j,i).

When the solution is found, or mined, the user data can be processed; the potential value of the neural hidden layer Z = zM is added to form the Neural Chain as the input of the next transaction where more user data is added. Then, the system calculates the Random Neural Network with gradient descent learning algorithm for the new pair (I, Y) where the new generated network weights w + (j,i) and w -(j,i) are stored in the decentralized network. The more roaming and verification data; the validation or mining process increases on complexity.

Decentralized Information

The user network weights w + (j,i) and w -(j,i) are stored in the decentralized network rather than its data I directly where I is calculated with the mining process. The network weights expand as more verification data is inserted creating an adaptable method. In addition; only the user Data can be extracted when the user presents its biometric key therefore making secure to store information in a decentralized system.

Neural Blockchain in Cybersecurity and IoT Validation

This section proposes a practical validation of the Neural Blockchain model in the Internet of Things and Cybersecurity using the network simulator Omnet ++ with Java for a network of ten nodes. The three independent experiments will emulate a Bluetooth network with roaming validation of MAC addresses, WLAN network with roaming validation of MAC and IP addresses and LTE Mobile network with a roaming validation of MAC and IP and user Passport (Table 2). The user is assigned a private key yN that requires validation before is allowed to transmit. When the user travels through the space, the credential private key is validated by the roaming node; the decentralized system retrieves the neural weights associated to the private key; mines the block, adds the node code and stores back the network weights in the decentralized system. This validation considers mining as the selection of random neuron values until Ek < T. When the user roams, the private key is presented and the information of the node (MAC and IP address) vt is added to the neural chain once it is mined. Each bit is codified as a neuron however rather than the binary 0-1, neuron potential is codified as 0.25 -0.75 (Figure 4); this approach removes overfitting in the learning algorithm as neurons only represent binary values. 9) R( 8) R( 7) R( 6 The simulations are run 100 times for a Bluetooth MAC Network (Table 3). The information shown is the number of iterations the Random Neuron Network with Blockchain configuration requires to achieve an Ek < 1.0E-10; the error Ek, the number of iterations to mine the Blockchain and the number of neurons for each layer; input xL, hidden zM and output yN. With four neurons in the hidden layer, the number of learning iterations gradually decreases while the number of input neurons increases due the additional information added when roaming between nodes. The results for the mining iteration are not as linear as expected because mining is performed using random values (Figure 5). Surprisingly; mining is easier in some Roaming stages when it would have been expected harder as the number of neurons increases.

Fig. 5. Bluetooth MAC Simulation -Learning and Mining

The Blockchain Random Neural Network algorithm shall detect tampering to be effective (Table 4) where Δ represents the number of tampered bits. The effects of tampering the Neural Block Chain (Figure 6) is detected by the learning algorithm even when the tampered values only differ in a bit, Δ=1.0, although this error reduces with an incrementing roaming as the number of neurons increases. Both Bluetooth and WLAN Networks perform similarly.

Conclusions

This paper has presented the application of the Blockchain Random Neural Network in Cybersecurity and the IoT where neurons are gradually incremented as user validation data increases through travelling and roaming, although this research can be generalized to any AAA server or Access Control solution. This configuration provides the proposed algorithm the same properties as the Blockchain: security and decentralization with the same validation process: mining the input neurons until the neural network solution is found. The Random Neural Network in Blockchain configuration has been applied to an IoT AAA server that covers the digital seven layers of the OSI Model and the physical user credentials such as Passport or biometrics. Experimental results show that Blockchain applications can be successfully implemented using neural networks with a gradually increased mining effort, user authentication and data encryption in a decentralized network therefore removing centralized validation mechanisms.

This paper has provided a holistic physical and digital Cybersecurity application in the IoT where access to the network in an area requires prior user physical verification between decentralized parties. User data is encrypted, information is decentralized where attackers can be identified if a criminal attack is delivered.

Appendix

Fig. 1 .

 1 Fig. 1. Blockchain Model

Fig. 2 .

 2 Fig. 2. The Random Neural Network structure • I = (ΛL, λL), a variable L-dimensional input vector I Є [-1,1] L represents the pair of excitatory and inhibitory signals entering each input neuron respectively; where scalar L values range 1<L< ∞; • X = (x1, x2, … , xL), a variable L-dimensional vector X Є [0,1] L represents the input state qL for the neuron L; where scalar L values range 1<L< ∞; • Z = (z1, z2, … , zM), a M-dimensional vector Z Є [0,1] M that represents the hidden neuron state qM for the neuron M; where scalar M values range 1<M< ∞; • Y = (y1, y2, … , yN), a N-dimensional vector Y Є [0,1] N that represents the neuron output state qN for the neuron N; where scalar N values range 1<N< ∞; • w + (j,i) is the (L+M+N) x (L+M+N) matrix of weights that represents from the excitatory spike emission from neuron i to neuron j; where i Є [xL, zM, yN] and j Є [xL, zM, yN]; • w -(j,i) is the (L+M+N) x (L+M+N) matrix of weights that represents from the inhibitory spike emission from neuron i to neuron j; where i Є [xL, zM, yN] and j Є [xL, zM, yN].

Fig. 3 .

 3 Fig. 3. Cybersecurity and the Internet of Things in the neural Blockchain Model

Fig. 4 .

 4 Fig. 4. Neural Blockchain in Cybersecurity validation

Fig. 6 .

 6 Fig. 6. Bluetooth and WLAN Simulation -Tampering Error

Table 1 .

 1 Private Key

	Private Key	Bits	Reference	Type	Interface
	y8	72	User	Physical	Passport -Biometrics
	y7	16	Web		OSI Layer 7
	y6	16	Middleware		OSI Layer 6
	y5	16	Socket		OSI Layer 5
	y4	16	Port	Digital	OSI Layer 4
	y3	32	IP		OSI Layer 3
	y2	48	MAC		OSI Layer 2
	y1	16	Bit		OSI Layer 1

Table 2 .

 2 Neural Blockchain in IoT and Cybersecurity Validation -Node values

	Type	Use	Coverage	Layer	Node Vt	User yN
	Bluetooth Master	Room Floor	10m 3140m 2	MAC	48 bits 01-23-45-67-89-XX	48 bits 01-23-45-67-89-AB
	Wireless LAN Access Point	Building Campus	100m 0.314km 2	MAC-IP	48+32 bits 192.168.11.XX	48+32 bits 192.168.11.11
	Mobile LTE	City	1km	MAC-IP	48+32 bits	48+32+72 bits
	Base Station	Country	31.4km 2	PASSPORT	N/A	VGD12345F

Table 3 .

 3 Bluetooth MAC Simulation -Learning and Mining

	Roaming	Learning Iteration	Learning Error	Mining Iteration	Mining Threshold	Mining Error Ek	Number of Neurons (xL, zM, yN)
	1	233.00	9.96E-11	36.22	1.00E-05	2.48E-06	48-4-48
	2	190.52	9.46E-11	24.88	1.00E-05	3.30E-06	100-4-48
	3	171.42	9.40E-11	56.32	1.00E-05	3.01E-06	152-4-48
	4	160.90	9.18E-11	758.37	1.00E-05	3.97E-06	204-4-48
	5	150.67	9.12E-11	109.10	1.00E-05	3.64E-06	256-4-48
	6	144.31	9.43E-11	116.59	1.00E-05	3.13E-06	308-4-48
	7	140.00	9.47E-11	354.38	1.00E-05	3.09E-06	360-4-48
	8	137.00	9.06E-11	2134.31	1.00E-05	3.70E-06	412-4-48
	9	132.99	8.75E-11	12.13	1.00E-05	3.56E-06	464-4-48
	10	131.00	9.30E-11	141.99	1.00E-05	3.26E-06	516-4-48

Table 4 .

 4 Bluetooth and WLAN Simulation -Tampering Error

			Bluetooth -MAC			WLAN -IP
	Roaming	Error	Error	Neurons	Error	Error	Neurons
		Δ=0.0	Δ=1.0	(xL, zM, yN)	Δ=0.0	Δ=1.0	(xL, zM, yN)
	1	9.96E-11	1.31E-03	48-4-48	9.28E-11	1.18E-03	80-4-80
	2	9.49E-11	1.50E-04	100-4-48	9.57E-11	1.63E-04	164-4-80
	3	9.18E-11	4.32E-05	152-4-48	9.36E-11	5.21E-05	248-4-80
	4	9.38E-11	1.95E-05	204-4-48	9.50E-11	2.23E-05	332-4-80
	5	9.01E-11	8.54E-06	256-4-48	9.21E-11	1.02E-05	416-4-80
	6	9.07E-11	4.28E-06	308-4-48	9.36E-11	5.22E-06	500-4-80
	7	9.49E-11	2.56E-06	360-4-48	9.12E-11	3.07E-06	584-4-80
	8	9.33E-11	1.71E-06	412-4-48	9.28E-11	2.10E-06	668-4-80
	9	8.93E-11	9.00E-07	464-4-48	9.25E-11	1.15E-06	752-4-80
	10	9.59E-11	7.22E-07	516-4-48	9.55E-11	7.81E-07	836-4-80


Ladislav Lenc
email: llenc@kiv.zcu.cz

Jiří Martínek

Pavel Král

Tools for Semi-automatic Preparation of Training Data for OCR

Keywords: CNN, Historical Documents, LSTM, Neural Networks, OCR

This work aims at data preparation for OCR systems based on recurrent neural networks. Precisely annotated data are necessary for training a network as well as for evaluation of OCR methods. It is possible to synthesize the data, however such data are not that realistic as the real ones. Manual annotation is thus still needed in many cases, especially in the case of historical documents we are focusing on. Although there are several complex systems for historical document processing, to the best of our knowledge, a simple annotation tool for OCR data is completely missing. Therefore, we propose and implement a set of tools utilizing artificial intelligence that simplify the annotation process. These tools create ground truths for line images that are used for training of nowadays OCR systems. Another contribution of this paper is making these tools freely available for research purposes.

Introduction

Digitization of historical documents is a very important task for preserving our cultural heritage. Nowadays, a significant number of such documents is already scanned and saved into archival databases and portals. The next step is making such documents accessible to researchers and to the public. The accessibility is very important and it requires further processing of the scanned documents. A crucial task is converting document images to plain text by the means of optical character recognition (OCR) or handwritten text recognition (HTR). This paper is focused on OCR of printed documents.

We concentrate on historical German newspapers from the end of the nineteenth century. The documents are printed in the obsolete Fraktur script. The scans have several quality issues such as noise, skew, warping and even missing parts of some characters. The documents also have quite a variable page layout. All above mentioned aspects make the OCR of such documents challenging.

Current trend in the OCR field is utilizing neural networks that process whole text lines. Recurrent neural networks (RNN) are usually utilized for this task [START_REF] Breuel | High-performance ocr for printed english and fraktur using lstm networks[END_REF]. A great benefit of RNN based approaches is that the segmentation to characters is not necessary. Some approaches also combine RNN and convolutional neural networks (CNN) [START_REF] Shi | An end-to-end trainable neural network for image-based sequence recognition and its application to scene text recognition[END_REF][START_REF] Rawls | Combining convolutional neural networks and lstms for segmentation-free ocr[END_REF]. In such approaches CNN serves as a feature extractor for the recurrent layers. It helps mainly in cases when the data are not well aligned and contain noise.

The segmentation free approaches need a significant amount of annotated line images to be able to train the models. The images can be synthesized using available fonts. However, for capturing all aspects of the real data synthetic data are not sufficient. Therefore, some amount of manually annotated data is still necessary. Moreover, the real data must be also used for system evaluation.

Although there are several complex systems for historical document processing, to the best of our knowledge, a simple single-purpose system to facilitate data annotation is completely missing. Therefore, the main goal of this paper consists in developing a set of simple tools dedicated to OCR data annotation. We would like to save human resources as much as possible. Therefore, we integrate several components of artificial intelligence into these tools to minimize manual annotation work. Their main purpose is to create annotation for line based OCR systems, however one of the tools allows also creating character based annotation. Another contribution of this paper consists in public availability of these tools for research purposes 3 . The implemented tools will be used for training and evaluation of an OCR system developed mainly for historical German newspapers. However, they can be utilized for arbitrary data.

Related Work

This section first describes the methods currently used in the OCR field. Then, we summarize available tools and methods for image ground truth creation.

Labeling unsegmented sequences was made possible by using connectionist temporal classification (CTC) loss [START_REF] Graves | Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks[END_REF]. CTC loss allowed using a single network for the whole labeling process. It gives the probability distribution over all possible label sequences conditioned on the input sequence. The network uses an objective function that maximizes the probabilities of correct labelings. It is differentiable and therefore a standard backpropagation can be used. This approach was first used for speech recognition. It's utilization directly for text recognition was proposed in [START_REF] Graves | Offline handwriting recognition with multidimensional recurrent neural networks[END_REF]. It was aimed mainly at handwritten data. However, it is also suitable for printed OCR.

Breuel et. al [START_REF] Breuel | High-performance ocr for printed english and fraktur using lstm networks[END_REF] proposed an efficient OCR system based on LSTM. It is part of the open-source OCR system OCRopus [START_REF] Breuel | The ocropus open source ocr system[END_REF]. The method utilizes a 1D bidirectional LSTM network and uses a text line normalization. The normalization step is built upon a dictionary of connected component shapes associated with baseline and x-height information. The dictionary is pre-computed on external annotated data. The baseline and x-height lines are mapped to two straight lines using spline interpolation. The system is applied on printed English and Fraktur texts. It reaches 0.6% CER on English and values from 0.16% to 0.82% on Fraktur depending on the quality of scans.

An approach combining CNN and RNN is proposed in [START_REF] Rawls | Combining convolutional neural networks and lstms for segmentation-free ocr[END_REF]. The system utilizes CNN for feature extraction. LSTM is then used for sequence modeling. The model is evaluated on handwritten as well as printed data. It is shown that such a model using 1D LSTM performs well for both data types. This work also presents weighted finite state transducer (WFST) that supplies a language model to the decoding procedure.

A recursive-recurrent network combined with an attention mechanism was proposed in [START_REF] Lee | Recursive recurrent nets with attention modeling for ocr in the wild[END_REF]. This work aims at a photo OCR that reads scene texts in natural images. It is focused on the unconstrained scene text recognition. The system performs directly an image to sequence learning. The network contains 8 convolutional layers with varying number of kernels. RNN with 1024 units serves as the underlying character language model. The attention mechanism is used for better image feature usage. The reported accuracy improvement on the Street view text (SVT) database is 9%.

Van Beusekom et al. [START_REF] Van Beusekom | Automated ocr ground truth generation[END_REF] proposed an approach for automated ground truth generation. The method finds a robust and accurate alignment of a scanned image and corresponding electronic document. It involves printing of the electronic document and scanning it again. Ground truths on pixel level are prepared. It is tested on the UW3 dataset. The estimated ground truths are compared with the real ones and the resulting accuracy is less than one pixel difference.

A simple approach for ground truth creation is proposed in [START_REF] Clausner | Efficient ocr training data generation with aletheia[END_REF]. Aletheia [START_REF] Clausner | Aletheia-an advanced document layout and text ground-truthing system for production environments[END_REF], which is a powerful image ground-truthing tool is used for this task. Aletheia automatically detects objects on four levels: regions, text lines, words and glyphs. The outlines of the objects can be adjusted by users. The user also specifies the segmentation of words to single glyphs.

Another tool is DivaDia [START_REF] Chen | Ground truth model, tool, and dataset for layout analysis of historical documents[END_REF]. It is used for semi-automatic document image analysis. The system proposes page segmentations and the user then must approve it. The ground truths are stored in xml compatible with the PAGE format.

TrueViz [START_REF] Kanungo | Trueviz: a groundtruth/metadata editing and visualizing toolkit for ocr[END_REF] is a tool which allows ground truth creating and visualizing. It is written in Java. The data is saved in xml format. It allows multi-lingual text editing. It is available free of charge for research purposes.

Tools for Semi-automatic Annotation

This section describes the proposed set of tools as well as the whole data annotation process. The processing pipeline is depicted in Figure 1. Text regions are first extracted from the input images. The regions are then further segmented into single text lines. A character segmenter estimates segmentation to individual characters, which is then corrected by a human annotator. The extracted character images are then used for synthetic data preparation. These synthetic lines are then utilized as training data for the CRNN classifier. Line annotator tool used the trained model and its output are the annotated lines.

Line Image Extraction

This task is solved by automatic tools provided by open-source libraries. The input images are first binarized and deskewed using OCRopus [START_REF] Breuel | The ocropus open source ocr system[END_REF]. The next step is extraction of text blocks. Leptonica library [START_REF] Bloomberg | Leptonica[END_REF] is used for this task. Based on the positions of the blocks we determine the reading order. Then we apply a simple algorithm based on projection profiles which finds the text lines. The last step is extracting and post-processing the line images.

Character Segmentation

The first proposed tool is used for segmenting the text lines into individual characters. It additionally saves the annotated line images as well as the character separator positions. The input of this tool is a set of line images extracted in the previous step. The proposed character segmenter takes a line image and proposes a segmentation to characters. The algorithm is based on projection profiles.

The input image is first inverted and thresholded. Then we calculate the vertical projection profile of the image. This process is illustrated in Figure 2. The white peaks indicate presence of characters. The values lower than a specified threshold are considered to be gaps separating the characters. The proposed segmentation of the example image above is shown in Figure 3. This figure shows that several ending character borders are similar to the starting ones, which is depicted with one single separator. The example shows several segmentation errors that occur typically in letters m, n or u. Another issue are some pairs of characters that are impossible to split using projection profile method. Examples are ch, tz and ck. The user interface allows manual correction of incorrectly segmented characters. The tool has options for merging or splitting incorrect segmentations. It is also possible to shift character borders.

Annotation is done by typing the appropriate letter on the keyboard. After pressing a key a next character candidate is selected and it is thus possible to write fluently. Some special characters has dedicated buttons that simplify the typing. There are buttons for the above mentioned hard to segment pairs such as ch. An extra button is available also for character short s. The user interface is shown in Figure 4 The output of this tool is a set of annotated line images. We also extract individual character images that are saved to directories. We thus can obtain several examples of each character by processing a relatively small amount of data. We also save the positions of character separators that may be useful for successive tasks.

CRNN Classifier

We utilize a CNN-LSTM line image classifier. It is capable of classifying unsegmented line images and retrieving character sequences. The architecture we use is a simplified version of a network proposed in [START_REF] Shi | An end-to-end trainable neural network for image-based sequence recognition and its application to scene text recognition[END_REF]. Following Graves et al. [START_REF] Graves | A novel connectionist system for unconstrained handwriting recognition[END_REF] we use a bidirectional LSTM architecture with CTC loss function [START_REF] Graves | Connectionist temporal classification: labelling unsegmented sequence data with recurrent neural networks[END_REF].

The input of our network is binarized line images. We resize the images so that its height is 40 pixels. The width is set to the maximum image width occurring in the training set. We keep the aspect ratio of the images and pad the rest of the image with white space.

CNN is utilized for extraction of features, which are fed to the LSTM network [START_REF] Hochreiter | Long short-term memory[END_REF].

The output of the bidirectional LSTM layer is given to a set of dense layers with a softmax activation function. Its output represents a probability distribution of characters per each time frame. Let A be a set of symbols, which classifier recognizes (|A| = 83). Then the p ai t is the probability of observing character a i at given time t. In the each time t the sum of the probabilities of all symbols is equal to 1.

|A| i=1 p ai t = 1 (1)
The most probable symbol ât of each time frame t is determined as:

ât = argmax ai∈A p ai t (2)
The last part of the classifier is a transcription layer, which decodes the predictions for each frame into the output sequence. To be able to distinguish each individual character the blank-symbol (-) is present. It is also necessary to deduplicate the sequences of the same symbols. The architecture of the classifier is depicted in Figure 5.

Our network has two convolutional layers with 40 kernels of size 3 × 3. Each of them is followed by Max-pooling layer. The output of the convolutional layers is reshaped and connected to a fully-connected layer with 128 neurons. It is an input of recurrent layers. We utilize two bidirectional LSTM layers with 256 units.

Classifier Training

The model is trained on data prepared from the character images. We denote such data as synthetic. The character images extracted from the initial set of lines are used for composition of line images. The texts are taken from old German archives to ensure that the language corresponds with the processed documents. Line images are then composed from the images. We use a simple approach that adds a gap of a fixed size between the characters. A wider gap is used between words. We used 25,000 line images for the initial training.

An example of such synthetic data is shown in Figure 6. The model is trained using stochastic gradient descent (SGD) algorithm. The initial learning rate is set to 0.005 and learning rate decay is applied. We also clip the gradients to 5. We applied early stopping based on the behavior of character error rate (CER) and validation loss. Figure 7 shows the progress of training on synthetic data for 25 epochs. One page of real data is used for validation. The performance is measured in terms of CER on the validation data. We also show training and validation loss. The curves indicate that training the model longer than for 5 epochs is not beneficial. To fine-tune the model we use the real annotated line images. The set comprises of 137 line images. Figure 8 depicts training loss, validation loss and CER for additional training. Based on the previous experiment we chose a model pre-trained on synthetic data for 5 epochs.

Line Annotator

This tool utilizes the trained model to predict the transcription of a line image. It is then checked by a human annotator and corrected if needed. It uses a simple GUI as shown in Figure 9.

To be able to evaluate the performance of the underlying model we measure how many corrections must be done by the user. We report Levenshtein edit distance, which indicates the number of insertions, deletions and replacements. As additional information we report also CER, word error rate (WER) and normalized edit distance. The normalization is based on the ground truth sentence length. Table 1 summarizes the results of the classifier on nine additional pages that were annotated using this tool. We can state that the tool has acceptable performance. The average number of corrections is 4 per line image.

Conclusion and Future Work

This work has presented a set of tools for OCR data annotation at a low cost. They will be used for preparation of training data for OCR systems. It is focused mainly on historical German newspapers. The data are processed in the frame of a project that makes archival documents more accessible.

The tools are semi-automatic and require only small amount of human supervision. The main part of the whole process is the recurrent neural network model that recognizes text lines. The model is trained on data obtained from the character segmenter tool. It is utilized in the line annotator tool where it serves as recognizer of presented line images. The results obtained using model trained on a minimal set of data are satisfactory and allow very fast processing with minimal human labor.

A possibility for further improvement is a pre-processing of the images that ensures better quality of the extracted line images. It should help mainly on warped and noisy lines. A way to improve the line annotator is incremental training of the underlying model. Supplying more lines would help to create a more robust model.

Fig. 1 .

 1 Fig. 1. Processing pipeline of the proposed data preparation procedure.

Fig. 2 .

 2 Fig. 2. Original text line and its vertical projection profile.

Fig. 3 .

 3 Fig. 3. Proposed segmentation of an example line image.

Fig. 4 .

 4 Fig. 4. Line segmenter GUI.

Fig. 5 .

 5 Fig. 5. Architecture of the CRNN classifier.

Fig. 6 .

 6 Fig. 6. Two examples of the synthetic line images.

Fig. 7 .

 7 Fig. 7. Training progress on synthetic data.

Fig. 8 .

 8 Fig. 8. Progress of the additional training on real data.

Fig. 9 .

 9 Fig. 9. Line annotation tool.

Table 1 .

 1 Evaluation of the CRNN classifier.

	Metric	Value
	Average edit distance	4.1
	Normalized edit distance 0.088
	Average WER	0.386
	Average CER	0.087

http://home.zcu.cz/ ~pkral/sw/

Acknowledgement

This work has been partly supported from ERDF "Research and Development of Intelligent Components of Advanced Technologies for the Pilsen Metropolitan Area (InteCom)" (no.: CZ.02.1.01/0.0/0.0/17 048/0007267) and by Grant No. SGS-2019-018 Processing of heterogeneous data and its specialized applications.


Parthiv B Rana
email: ranaparthiv@gmail.com

Jigar L Patel

D I Lalwani

Design-parameters optimization of a deep-groove ball bearing for different boundary dimensions, employing Amended Differential Evolution Algorithm

Keywords: design-parameter optimization, constraint optimization, a ball bearing, Amended Differential Evolution Algorithm (ADEA)

Rolling-element bearing that is mostly used wherever rotary motion is provided to a shaft in rotating machineries. A deep-groove ball bearing is one type of rolling-element bearing which is used to support radial load, axial load or combination of both. After proper installation and condition, ball bearings usually fail because of fatigue under normal operating conditions. Therefore, the fatigue-life optimization is a prime objective in designing a ball bearing. In the present work, eleven different problems of a deep-groove ball bearing by changing boundary dimensions are optimize to obtain maximum fatigue life. Amended Differential Evolution Algorithm (ADEA), which is modified version of Differential Evolution (DE) algorithm along with constraint handling technique, is applied to these eleven problems and optimum results in the form of optimal designparameters and fatigue life is reported. The design parameters are bearing pitch diameter, ball diameter, number of balls and curvature coefficient of the outer and inner raceway groove are considered. Further, optimal results are compared with the other researcher's work and standard catalogue for the same problems. Better results for fatigue life are obtained using ADEA.

Introduction

Rolling element bearings are critical element of any rotating machinery and it is used in variety of applications such as machine tools, electrical equipments, automobile, household appliances, medical equipments and aeroplanes. Rolling element bearings are also called as antifriction bearings. Different types of rolling element bearings are used depending upon the loading condition, i.e., radial load, axial load and combination of both. Radial bearings are used to support the load which is perpendicular to the shaft whereas thrust bearings are used to support the load which acts along axis of the shaft. Among the various types of rolling element bearing, a single-raw, deep-groove ball bearing is most frequently used bearing because it can take radial as well as some thrust load and withstand a small amount of shaft misalignment or deflection [START_REF] Shigley | Mechanical Engineering Design[END_REF]. A singleraw, deep-groove ball bearings rely on balls to support loads between rotating and stationary machine elements. Ball bearings have high load carrying capacity, generates less noise and low resultant temperature because of point contact. Deep-groove ball bearings are available in variety of bore dimensions up to 400 mm [START_REF] Bhandari | Design of Machine Elements[END_REF]. The internal structural-parameters (design parameters) affect the bearing characteristics such as bearing life, lubrication, load distribution, stresses and deflection. Generally, ball bearings are designed to determine the geometric structure and their relative design parameters for smooth operation and bearing life.

Researchers have worked to optimize design parameters of various rolling-element bearing but some important and relevant literatures on optimization of a ball bearing are discussed here. Changsen [START_REF] Changsen | Analysis of Rolling Element Bearings[END_REF] discussed a design method for rolling element bearing using a gradient based numerical optimization technique; he defined five different non-linear objectives for rolling element bearing design, i.e., maximum frictional moment, maximum wear life, maximum static load rating, maximum spin to roll ratio and maximum fatigue life. Further, he proposed concept of multi-objective optimization of above objectives and also introduced basic concepts and optimization techniques to solve problems. Chakraborty et al. [START_REF] Chakraborty | Rolling element bearing design through genetic algorithms[END_REF] optimized the design parameters of deepgroove ball bearings using Genetic Algorithm (GA), where five design parameters were considered to maximize fatigue life of a bearing. Rao and Tiwari [5] refined the problem proposed by Chakraborty et al. [START_REF] Chakraborty | Rolling element bearing design through genetic algorithms[END_REF] to obtain more realistic optimum design parameters, where five design variables, five various constants of constraints and eight constraints, were used to maximize dynamic load rating of a deep-groove ball bearing using GA.

In the present work, eleven different problems of a deep-groove ball bearing by changing boundary dimensions are considered. These problems are modified by Rao and Tiwari [5] and used to optimize the design parameters using Amended Differential Evolution Algorithm (ADEA) [START_REF] Rana | Optimization of turning process using Amended Differential Evolution Algorithm[END_REF]. The optimized results are compared with the results of Genetic Algorithm (GA) [5] and standard catalogue [START_REF] Shigley | Mechanical Engineering Design[END_REF]. The rest of the paper is organized as follow: Section 2 describes mathematical model of ball bearing design problem; section 3 presents flow chart of Amended Differential Evolution Algorithm (ADEA); section 4 presents results and discussion and section 5 concludes the work.

Mathematical modelling of ball bearing design problem

On the basis of operating requirements, one of the most important objectives is the requirement of the longest bearing life (fatigue life). In normal operating conditions of ball bearings, fatigue failure is the main mode of failure at the surfaces of balls and races. The fatigue life of an individual ball bearing is defined as the number of revolutions, which the bearing runs before the first evidence of fatigue crack in balls or races. The Anti-Friction Bearing Manufacturing Association (AFBMA) standard states that the failure criterion is the first evidence of fatigue. AFBMA sanctioned a term 'rating life' of a bearing that is used by most of the bearing manufacturers and it is defined as 'the number of revolutions or hours at some given constant speed that 90 per cent of group of a bearings will complete or exceed before the failure criterion develops'. The fatigue life (or rating life) of bearing is based on the dynamic load capacity (dynamic load rating or basic dynamic capacity or specific dynamic capacity [START_REF] Shigley | Mechanical Engineering Design[END_REF]). The dynamic load capacity (C) is defined as the dynamic equivalent radial load in deep-groove ball bearings that can be carried for a minimum life of one million revolutions. The fatigue life of bearing can be improved by maximizing dynamic load capacity for a given size of bearing boundary dimensions (i.e., bearing bore, d, and outside diameter, D and bearing width, w). The fatigue life of a bearing (in millions of revolutions) that is subjected to applied dynamic equivalent radial load F is given as:

𝐿 10 = ( 𝐶 𝐹 ) 𝑎 and 𝐿 10ℎ = 10 6 60𝑛 𝐿 10 (1)
where 𝐿 10 is rated bearing life (in millions of revolutions), C is dynamic load capacity (N), F is applied dynamic equivalent radial load (N) and a is 3 for ball bearings, 𝐿 10ℎ is rated bearing life (in operating hours) and n is rotational speed in rpm. The bounds of design parameters, objective function and constraints are taken from Rao and Tiwari [5] and briefly discussed below.

Design parameters

The design parameters are basically internal structural dimensions of a ball bearing as shown in Fig. 1. The five design parameters of ball bearing are: diameter of ball (Db), number of balls (Z), pitch diameter (Dm) and curvature coefficient of the outer raceway groove (fo = ro/Db) and inner raceway groove (fi = ri/Db). ro and ri are the curvature radius of outer and the inner raceway groove, respectively [5]. Table 1 shows the design parameters and their ranges. when Db > 25.4 mm. [START_REF] Bhandari | Design of Machine Elements[END_REF] where 𝑓 𝑐 for deep-groove ball bearings is given as 1.39 (1 + 𝛾)

𝑓 𝑐 = 37.91 [1 + {1.04 ( 1 -𝛾 1 + 𝛾 ) 1.72 ( 𝑓 𝑖 (2𝑓 𝑜 -1) 𝑓 𝑜 (2𝑓 𝑖 -1) ) 0.41 } 10 3 ⁄ ] -0.3 [ 𝛾 0.3 (1 -𝛾)
1 3 ⁄ ] [ 2𝑓 𝑖 2𝑓 𝑖 -1 ] 0.41 (3)
where 𝛾 is 𝐷 𝑏 𝑐𝑜𝑠𝛼 𝐷 𝑚 ⁄ and α is free contact angle that is zero for deep-groove ball bearings.

Constraints

Ten constraints that are proposed by Rao and Tiwari [5] are considered in the present work. Out of ten constraints, five constraints are refined by Rao and Tiwari [5] that were proposed by Chakraborty et al [START_REF] Chakraborty | Rolling element bearing design through genetic algorithms[END_REF]. In the present work, constraints for curvature coefficient of inner and outer raceway groove (constraints 9 and 10 of Rao and Tiwari [5]) are in the form of range (bounds) that are already considered as design parameters and given in Table 2. Therefore, constraints for 𝑓 𝑖 and 𝑓 𝑜 are not discussed. The remaining eight constraints are discussed below [5].

Constraint 1: For a number of balls

For the convenience of the bearing assembly, the number of balls should satisfy the following equation, 𝑔 1 (𝑥):

𝑔 1 (𝑥) = 𝑍 ≤ 1 + ∅ 0 2𝑆𝑖𝑛 -1 (𝐷 𝑏 / 𝐷 𝑚 ) (4)
can be written as, 𝑔 1 (𝑥) = 𝑍 -1 -

∅ 0 2𝑆𝑖𝑛 -1 (𝐷 𝑏 / 𝐷 𝑚 ) ≤ 0 (5)
where ∅ 0 is the maximum assembly angle and it is given as

∅ 0 = 2𝜋 -2 𝑐𝑜𝑠 -1 [ 𝑈 2 +( 𝐷 2 -𝑇-𝐷 𝑏 ) 2 -( 𝑑 2 +𝑇) 2 2𝑈( 𝐷 2 -𝑇-𝐷 𝑏 ) ], (6)
and T and U are defined as

𝑇 = (𝐷-𝑑-2𝐷 𝑏 ) 4 and 𝑈 = (𝐷-𝑑) 2 - 3(𝐷-𝑑-2𝐷 𝑏 ) 4 (7)
In the constraints 2 to 8, some constraint constants are used and their range (bounds) are shown in Table 2 except constraint 6.

Constraints 2 and 3: For diameter of balls

For the convenience of the bearing assembly, the diameter of balls should be within a following range:

𝑔 2 (𝑥) = 2𝐷 𝑏 ≥ 𝐾 𝐷 𝑚𝑖𝑛 (𝐷 -𝑑), (8)
can be written as, 𝑔 2 (𝑥) = 𝐾 𝐷 𝑚𝑖𝑛 (𝐷 -𝑑) -2𝐷 𝑏 ≤ 0,

𝑔 3 (𝑥) = 2𝐷 𝑏 ≤ 𝐾 𝐷 𝑚𝑎𝑥 (𝐷 -𝑑), (10) can be written as, 𝑔 3 (𝑥) = 2𝐷 𝑏 -𝐾 𝐷 𝑚𝑎𝑥 (𝐷 -𝑑) ≤ 0, (11) where 𝐾 𝐷 𝑚𝑖𝑛 and 𝐾 𝐷 𝑚𝑎𝑥 are the minimum and the maximum values of the ball diameter constants, respectively. The range of 𝐾 𝐷 𝑚𝑖𝑛 is 0.4 to 0.5 and range 𝐾 𝐷 𝑚𝑎𝑥 is 0.6 to 0.7.

Constraints 4 and 5: For running mobility of a bearing

For the running mobility of bearings, the difference between the pitch diameter and the average diameter in a bearing should satisfy below constraints.

where e is a constant and its value depends on mobility condition of the balls. The range of e is taken here 0.03 to 0.08.

Constraint 6: For relationship between inner and outer ring thickness

In normal operating conditions, the stress on the inner ring is always more than the outer ring of a ball bearing. Therefore, outer ring thickness should be less than or equal to the inner ring thickness.

where 𝑑 𝑖 and 𝑑 𝑜 are the inner and outer raceway diameters at the grooves.

Constraint 7: For thickness of bearing ring at outer raceway bottom

The average diameter of bearing is usually less than the pitch diameter. Therefore, thickness of bearing ring at outer raceway bottom should not be less than 𝜀𝐷 𝑏 and the following equation, 𝑔 7 (𝑥) should satisfy:

𝑔 7 (𝑥) = 𝜀𝐷 𝑏 ≤ 0.5(𝐷 -𝐷 𝑚 -𝐷 𝑏 ) (18)
can be written as, 𝑔 7 (𝑥) = 𝜀𝐷 𝑏 -0.5(𝐷 -𝐷 𝑚 -𝐷 𝑏 ) ≤ 0 (19

)
where ε is a constant that is obtained using simple strength consideration of outer ring and the range of ε is 0.

)
where 𝛽 is a constant and the range of 𝛽 is 0.7 to 0.85. The ranges of various constants used in constraints are given in Table 2.

Amended Differential Evolution Algorithm (ADEA)

Amended Differential Evolution Algorithm is the modified version of Differential Evolution (DE) algorithm and it uses 'Σ 𝑐𝑜𝑛𝑠𝑡 -constraint handling method' to solve constrained optimization problems [START_REF] Rana | Optimization of turning process using Amended Differential Evolution Algorithm[END_REF]. Fig. 2 shows the flow chart of ADEA that is adapted from reference [START_REF] Rana | Optimization of turning process using Amended Differential Evolution Algorithm[END_REF].

In the present work, maximization problems of deep-groove ball bearing are converted into minimization problems and all the constraints are converted into ≤ 0 type. The design parameters of deep-groove ball bearing problems are optimized using ADEA. Following parameters are used in ADEA: Population Size (PS) = 50, number of generations (G) = 500, number of runs = 30, scale factor: Fmin = 0.5, Fmax = 0.8, crossover rate: CRmin = 0.85, CRmax = 0.95. The program is written in MATLAB ® for ADEA and results are reported.

4

Results and Discussion

ADEA is successfully applied to optimize design-parameters of single raw, deepgroove ball bearing problems for maximizing dynamic load capacity (𝐶). Results obtained using ADEA are reported in Tables 345.

Table 3 shows the optimum design-parameters and value of constants (used in constraints) that are obtained using ADEA. When optimal value of any parameter is exactly either the start value (lower bound) or the end value (upper bound) of range, algorithm requires greater number of generations (iterations) to converge. However, ADEA algorithm converges to lower bound value for two design parameters, namely, fo and fi, within 500 generations (Table 3). Further, ADEA attains lower bound value for 𝜺 (constant-constraint). Thus, ADEA is capable to converge the bound value within reasonable generations.

Table 4 presents the values of optimum design parameters, constraints (𝑔 1 (𝑥) to 𝑔 8 (𝑥)) and dynamic load capacity (𝐶). The value of design parameters, i.e., Db and Dm, are reported up to 3 decimal accuracy and accordingly other results are reported. It is clear from Table 4 that 𝑔 6 (𝑥) and 𝑔 7 (𝑥) constraints are active constraints (i.e., 𝑔 6 (𝑥) = 0 and 𝑔 7 (𝑥) = 0) for some boundary dimensions. Two constraints, 𝑔 1 (𝑥) and 𝑔 7 (𝑥), are difficult constraints for some boundary dimensions because value of constraint is neither zero nor negative value but very nearer to zero value, i.e., 0.0001.

Table 5 shows the comparison of the results with the results of Genetic Algorithm (GA) [5] and standard catalogue [START_REF] Shigley | Mechanical Engineering Design[END_REF] for dynamic load capacity (C). The comparison shows that ADEA provides better results for all boundary dimensions. Further, per cent improvement in dynamic load capacity with respect to GA and standard catalogue is presented in Table 5. The maximum and minimum per cent improvement over standard catalogue are 68.50 % and 8.24 %, respectively. Similarly, the maximum and minimum per cent improvement over GA are 11.11 % and 1.35 %, respectively.

Fig. 1 .

 1 Fig. 1. Internal diagram of ball bearing [4].

𝑔 4 ( 2 +

 42 𝑥) = 𝐷 𝑚 -𝐷 + 𝑑 2 ≤ -𝑒(𝐷 + 𝑑),(12)can be written as, 𝑔 4 (𝑥) = 𝐷 𝑚 -𝐷+𝑑 𝑒(𝐷 + 𝑑) ≤ 0, 𝑎𝑛𝑑(13)𝑔 5 (𝑥) = 𝐷 𝑚 -𝐷 + 𝑑 2 ≥ 𝑒(𝐷 + 𝑑),(14)can be written as, 𝑔 5 (𝑥) = 𝑒(𝐷 + 𝑑) -𝐷 𝑚 +

Fig. 2 .

 2 Fig. 2. Flow chart of ADEA (adopted from [6])

Table 1 .

 1 Design parameters and their ranges[5]

	Design parameters	Ranges
	Diameter of ball (Db)	0.15(D-d) to 0.45(D-d)
	Pitch diameter (Dm)	0.5(D+d) to 0.6(D+d)
	Number of balls (Z)	4 to 50
	Curvature coefficient of the inner raceway groove (fi)	0.515 to 0.52
	Curvature coefficient of the outer raceway groove (fo)	0.515 to 0.53

Table 2 .

 2 Range of various constants[5]

	Constants	Range [Lower Bound (LB), Upper Bound (UB)]
	𝐾 𝐷 𝑚𝑖𝑛	0.4 to 0.5 [0.4,0.5]
	𝐾 𝐷 𝑚𝑎𝑥	0.6 to 0.7 [0.6,0.7]
	e	0.03 to 0.08 [0.03,0.08]
	𝜀	0.3 to 0.35 [0.3,0.35]
	𝛽	0.7 to 0.85 [0.7,0.85]

Table 3 .

 3 Results obtained using ADEA in terms of optimized design-parameters and value of constants (used in constraints) for eleven boundary dimensions.

	Boundary Dimension (mm)		Design Parameters		Values of constants obtained in constraints
	D	d	w	Db (mm)	Dm (mm)	Z	fi	fo	KD min KD max	e	𝜺	𝜷
	30 10	9	6.213	20.059	7 0.515 0.515 0.442	0.649 0.072	0.3 0.793
	35 15	11	6.25	25	8 0.515 0.515 0.428	0.681 0.055	0.3 0.708
	47 20	14	8.438	33.5	8 0.515 0.515 0.435	0.664 0.065	0.3 0.762
	62 30	16	10	46	9 0.515 0.515 0.403	0.653 0.069	0.3 0.810
	80 40	18	12.5	60	9 0.515 0.515 0.412	0.667 0.048	0.3 0.812
	90 50	20	12.5	70 10 0.515 0.515 0.455	0.678	0.08	0.3 0.758
	110 60	22 15.625	85 10 0.515 0.515 0.456	0.656 0.044	0.3 0.750
	125 70	24 16.732	98.228 11 0.515 0.515 0.420	0.609 0.069	0.3 0.741
	140 80	26	18.75	110 11 0.515 0.515 0.402	0.648	0.05	0.3 0.768
	160 90	30 21.426 125.719 11 0.515 0.515 0.417	0.674 0.055	0.3 0.787
	170 95	32 22.752 133.597 11 0.515 0.515 0.435	0.682 0.051	0.3 0.786

Table 4 .

 4 Results obtained using ADEA in terms of optimized design-parameters, value of constraints and dynamic load capacity (C) for eleven boundary dimensions. 𝒙) 𝒈 𝟐 (𝒙) 𝒈 𝟑 (𝒙) 𝒈 𝟒 (𝒙) 𝒈 𝟓 (𝒙) 𝒈 𝟔 (𝒙) 𝒈 𝟕 (𝒙) 𝒈 𝟖 (𝒙) indicates constraint value less than or equal to 1×10 -4 (1E-4) and considered as zero (0).

	Boundary Dimension (mm) D d w 𝒈 𝟏 (30 10 Design Parameters Db (mm) Dm (mm) Z fi fo 9 6.213 20.059 7 0.515 0.515	Value of Constraints 0 * -3.59 -0.55 -2.94 -2.82 -0.06	0 * -0.92	Dynamic load capacity, 𝑪 (N) 6032.33
	35 15 11	6.25	25 8 0.515 0.515 -0.15 -3.94 -1.12 -2.65 -2.75	0	0 -1.54	7059.09
	47 20 14 8.438	33.5 8 0.515 0.515 -0.10 -5.13 -1.05 -4.36 -4.36	0	0 * -2.23	12100.67
	62 30 16	10	46 9 0.515 0.515 -0.06 -7.10 -0.90 -6.35 -6.35	0	0 -2.96	18113.18
	80 40 18	12.5	60 9 0.515 0.515 -0.37 -8.52 -1.68 -5.76 -5.76	0	0 -2.12	27144.31
	90 50 20	12.5	70 10 0.515 0.515 -0.60 -6.80 -2.12 -11.2 -11.2	0	0 -2.66	29174.48
	110 60 22 15.625	85 10 0.515 0.515 -0.35 -8.45 -1.55 -7.48 -7.48	0	0 -0.88	43620.92
	125 70 24 16.732 98.228 11 0.515 0.515	0 * -10.36 -0.03 -14.18 -12.77 -0.73	0 * -1.05	52452.58
	140 80 26 18.75	110 11 0.515 0.515 -0.01 -13.38 -1.38	-11	-11	0	0 -1.22	64386.86
	160 90 30 21.426 125.719 11 0.515 0.515	0 * -13.66 -4.33 -14.47 -13.03 -0.72	0 * -2.18	81862.64
	170 95 32 22.752 133.597 11 0.515 0.515	0 * -12.88 -5.65 -14.61 -12.42 -1.10	0 *	-2.4	91203.51

*

Table 5 .

 5 Comparison of results of ADEA with GA and catalogue for dynamic load capacity (𝐶)

	Boundary Dimension (mm)	Dynamic load capacity, 𝑪 (N)		% improvement
	D	d	w	ADEA	GA [5]	Catalogue [1]	𝐀𝐃𝐄𝐀 -𝐆𝐀 𝐆𝐀	× 𝟏𝟎𝟎	𝐀𝐃𝐄𝐀 -𝐂𝐚𝐭𝐚𝐥𝐨𝐠𝐮𝐞 𝐂𝐚𝐭𝐚𝐥𝐨𝐠𝐮𝐞	× 𝟏𝟎𝟎

Conclusions

ADEA is used to optimize the design-parameters of single raw, deep-groove ball bearing for maximizing dynamic load capacity (fatigue life) for eleven boundary dimensions. From the optimization results, following conclusions are drawn:

 Comparison of the results shows that ADEA provides better results than GA and catalogue for all boundary dimensions of deep-groove ball bearing.  The maximum per cent improvement in dynamic load capacity is 68.50 % over catalogue and 11.11 % over GA.  ADEA is capable to obtain optimum design-parameters or constants that are extreme value of the range within reasonable generations.  ADEA can be used to solve other design problems such as angular contact bearing, journal bearing problem, heat exchanger problems and truss problem.