A learning automata-based memetic algorithm

Abstract

Combing a genetic algorithm (GA) with a local search method produces a type of evolutionary algorithm known as a memetic algorithm (MA). Combining a GA with a learning automaton (LA) produces an MA named GALA, where the LA provides the local search function. GALA represents chromosomes as object migration automata (OMAs), whose states represent the history of the local search process. Each state in an OMA has two attributes: the value of the gene (allele), and the degree of association with those values. The local search changes the degree of association between genes and their values. In GALA a chromosome’s fitness is computed using only the value of the genes. GALA is a Lamarckian learning model as it passes on the learned traits acquired by its local search method to offspring by a modification of the genotype. Herein we introduce a modified GALA (MGALA) that behaves according to a Baldwinian learning model. In MGALA the fitness function is computed using a chromosome’s fitness and the history of the local search recorded by the OMA states. In addition, in MGALA the learned traits are not passed to the offspring. Unlike GALA, MGALA uses all the information recorded in an OMA representation of the chromosome, i.e., the degree of association between genes and their alleles, and the value of a gene, to compute the fitness of genes. We used MGALA to solve two problems: object partitioning and graph isomorphism. MGALA outperformed GALA, a canonical MA, and an OMA-based method using computer simulations, in terms of solution quality and rate of convergence.

1 Introduction

Exploration and exploitation are two main search goals. Exploration is important for ensuring global reliability: the whole of search space needs to be searched to provide a trustworthy estimate of the global optimum. Exploitation is important, because it focuses the search effort around the best solutions by searching their neighborhoods to find more accurate solutions [1]. Many search algorithms use a combination of a global search method and a local search method to achieve their goal. These algorithms are known as hybrid methods. The combination of a traditional genetic algorithm (GA) with local search methods that incorporate local improvement procedures can improve the performance of GAs. These hybrid methods are commonly known as memetic algorithms (MAs), or Baldwinian [2] or Lamarckian [3] evolutionary algorithms (EA). The particular local search method employed is the important aspect of these algorithms. In the Lamarckian approach the local search method is used as a refinement genetic operator that modifies the genetic structure of an individual and places it back in the genetic population [4]. Lamarckian evolution can increase the speed of search processes in genetic algorithms. However, it can damage schema processing by changing the genetic structure of individuals, which may lead to premature convergence [5, 6].

The Baldwinian learning approach improves the fitness of an individual by applying a local search, however, individual genotypes remain unchanged. Thus, it increases the individual’s chances of remaining in subsequent generations. Similar to natural evolution, Baldwinian learning does not modify the genetic structure of an individual; but it does increase its chances of survival. Unlike the Lamarckian learning model, the Baldwinian approach does not allow parents to transfer what they have learned to their children [6]. The local search method is used as a part of the individual’s evaluation process in the Baldwinian approach. The local search method uses local knowledge to create a new fitness that can be used by the global genetic operators to improve an individual’s capability. In this method one or more individuals of a population that are similar in genotype gain similar fitness. These individuals, are probably near to each other in search space, and are equal in fitness after applying the local search. Therefore, the new search space will be a smooth surface, and will cover many of the local minima of the new search space. This fitness modification is known as the smoothing effect. The Baldwinian learning approach can be more effective, albeit slower, than Lamarckian approaches, since it does not alter the global search process of GAs [5].

Learning automata (LAs) are based on the general schemes of reinforcement learning algorithms. LAs enable agents to learn their interaction with an environment. They select actions via a stochastic process and apply them on a random, unknown environment. They can learn the best action by iteratively performing and receiving stochastic reinforcement signals from the unknown environment. These stochastic responses from the environment show the favorability of the selected actions, and the LAs change their action selecting mechanism in favor of the most promising actions according to responses from the environment [7, 8].

GALA is a type of MA first reported by Rezapoor and Meybodi [9]. GALA combines a GA, used for its global search function (Exploration), with an LA, used for its local search function (Exploitation). Object migration automata (OMAs) represent chromosomes in GALA. Each state in an OMA has two attributes: the value of the gene, and the degree of association with its value. Information about the past history of the local search process shows the degree of association between genes and their values. GALA performs according to a Lamarckian learning model, because it modifies the genotype and only uses a chromosome’s fitness to fitness function computation.

We present a new version of GALA, called modified GALA (MGALA), in the first part of this paper. MGALA behaves according to a Baldwinian learning model. Unlike GALA, which only uses the value of genes for fitness computation, MGALA uses all the information in the OMA representation of the chromosome (i.e., the degree of association between genes and their alleles, and the value of genes) to compute the fitness function. In the second part of the paper MGALA is used to solve two optimization problems: object partitioning and graph isomorphism. Computer simulations show that MGALA outperforms GALA, a canonical MA, and an OMA-based method, in terms of solution quality and in the rate of convergence.

Overall our paper is organized as follows: after this introduction Sect. 2 briefly describes learning automata and object migrating automata. GALA and its applications are described in Sect. 3. MGALA is introduced in Sect. 4. Two MGALA applications, those of solving the object partitioning problem and the graph isomorphism problem (GIP), are explained in Sects. 5 and 6, respectively. These two sections include implementation considerations, simulation results, and comparisons with other algorithms, which highlights MGALA’s contributions to the field. Section 7 is the conclusion.

2 Learning automata and object migrating automata

2.1 Learning automata

A learning automaton (LA) [5] is an adaptive decision‐making unit. It can be described as determination of an optimal action from a set of actions through repeated interactions with an unknown random environment. It selects an action based on a probability distribution at each instant and applies it on a random environment. The environment sends a reinforcement signal to automata after evaluating the input action. The learning automata process the response of environment and update its action probability vector. By repeating this process, the automaton learns to choose the optimal action so that the average penalty obtained from the environment is minimized. The environment is represented by a triple $< \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} >$. $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } = \{ \alpha_{1} , \ldots ,\alpha_{r} \}$ is the finite set of the inputs, $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } = \{ 0, 1\}$ is the set of outputs that can be taken by the reinforcement signal, and $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c} = \{ c_{1} , \ldots , c_{r} \}$ is the set of the penalty probabilities, where each element c _i of $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c}$ is corresponds to one input action α _i . The input α(n) to the environment belongs to $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha }$ and may be considered to be applied to the environment at discrete time $t = n\,(n = 0,1,2, \ldots )$. The output β(n) of the environment belongs to $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta }$ and can take on one of two values 0 and 1. An β(n) = 1 is identified with a failure or an unfavorable response and β(n) = 0 with a success or favorable response of the environment. The element c_i of $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{c}$ which characterizes the environment may then be defined by $pr\left( {\beta (n) = 1|\alpha (n) = \alpha_{i} } \right) = c_{i} \quad (i = 1,2, \ldots ,r)$. When the penalty probabilities are constant, the random environment is said a stationary random environment. It is called a non stationary environment, if they vary with time. Figure 1 shows the relationship between the LA and the random environment.

Fig. 1

The relationship between the LA and random environment

There are two main families of learning automata [6]: fixed structure learning automata and variable structure learning automata. First, we formally define fixed structure learning automata and then some of the fixed structures learning automata such as Tsetline, Krinsky, and Krylov automata are described.

A fixed structure LA is represented by a quintuple $< \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } ,F,G >$. where:

• $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } = \{ \alpha_{1} , \ldots ,\alpha_{r} \}$ is the set of actions that it must choose from.

• $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } = \{ \varphi_{1} , \ldots ,\varphi_{s} \}$ is the set of internal states.

• $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } = \{ 0,1\}$ is the set of inputs where 1 represents a penalty and 0 represents a reward.

• $F:\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } *\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \to \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi }$ is a function that maps the current state and current input into the next state.

• $G:\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } \to \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha }$ is a function that maps the current state into the current output. In other words, G determines the action taken by the automaton.

The operation of fixed learning automata could be described as follows: At the first step, the selected action $\alpha (n) = G[\varPhi (n)]$ serves as the input to the environment, which in turn emits a stochastic response β(n) at the time n. β(n) is an element of $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } = \{ 0,1\}$ and is the feedback response of the environment to the automaton. In the second step, the environment penalize (i.e., β(n) = 1) the automaton with the penalty probability c _i , which is the action dependent. On the basis of the response β(n), the state of automaton is updated by $\varPhi (n + 1) = F[\varPhi (n),\beta (n)]$. This process continues until the desired result is obtained.

In the following paragraphs, we describe some of the fixed structure learning automata such as Tsetline, Krinsky, and Krylov automata.

2.1.1 The two-state automata (L _2,2)

This automaton has two states, $\varphi_{1}$ and $\varphi_{2}$ and two actions α ₁ and α ₂. The automaton accepts input from a set of {0,1} and switches its states upon encountering an input 1 (unfavorable response) and remains in the same state on receiving an input 0 (favorable response). An automaton that uses this strategy is refereed as L _2,2 where the first subscript refers to the number of states and second subscript to the number of actions.

2.1.2 The Tsetline automata (the two-action automata with memory L _2N,2)

Tsetline suggested a modification of L _2,2 denoted by L _2N,2. This automaton has 2 N states and two actions and attempts to incorporate the past behavior of the system in its decision rule for choosing the sequence of actions. While the automaton L _2,2 switches from one action to another on receiving a failure response from environment, L _2N,2 keeps an account of the number of success and failures received for each action. It is only when the number of failures exceeds the number of successes, or some maximum value N; the automaton switches from one action to another. The procedure described above is one convenient method of keeping track of performance of the actions α₁ and α₂. As such, N is called depth of memory associated with each action, and automaton is said to have a total memory of 2N. For every favorable response, the state of automaton moves deeper into the memory of corresponding action, and for an unfavorable response, moves out of it. This automaton can be extended to multiple action automata. The state transition graph of L _2N,2 automaton is shown in Fig. 2.

Fig. 2

The state transition graph for L _2N,2 (Tsetline automaton)

2.1.3 The Krinsky automata

This automaton behaves exactly like L _2N,2 automaton when the response of the environment is unfavorable, but for favorable response, any state $\varphi_{i}$ (for i = 1,…,N) passes to the state $\varphi_{1}$ and any state $\varphi_{i}$ (i = N + 1, 2N) passes to the state $\varphi_{N + 1}$. This implies that a string of N consecutive unfavorable responses are needed to change from one action to another. The state transition graph of Krinsky automaton is shown in Fig. 3.

Fig. 3

The state transition graph for Krinsky automaton

2.1.4 The Krylov automata

This automaton has state transitions that are identical to the L _2N,2 automaton when the output of the environment is favorable. However when the response of the environment is unfavorable, a state $\varphi_{i} \,(i \ne 1,N,N + 1,2N)$ passes to a state $\varphi_{i + 1}$ with probability 1/2 and to state $\varphi_{i - 1}$ with probability 1/2, as shown in Fig. 4. When i = 1 or N + 1, $\varphi_{i}$ stays in the same state with probability 1/2 and moves to $\varphi_{i + 1}$ with the same probability. When i = N, $\varphi_{N}$ moves to $\varphi_{N - 1}$ and $\varphi_{2N}$ each with probability 1/2 and similarly, When i = 2 N, $\varphi_{2N}$ moves to $\varphi_{2N - 1}$ and $\varphi_{N}$ each with probability 1/2. The state transition graph of Krylov automaton is shown in Fig. 4.

Fig. 4

The state transition graph for Krylov automaton

Object migration automaton (OMA) that is an example of fixed structure learning automata is described in the next section. Learning automata have a vast variety of applications in combinatorial optimization problems [8–10], computer networks [10–13], queuing theory [14, 15], signal processing [16, 17], information retrieval [18, 19], adaptive control [20–22], neural networks engineering [23, 24] and pattern recognition [25–27].

2.2 Object migration automata

Object migration automata were first proposed by Oommen and Ma [10]. OMAs are a type of fixed structure learning automata, and are defined by a quintuple $< \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } ,\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } ,F,G >$.$\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } = \{ \alpha_{1} , \ldots , \alpha_{r} \}$. is the set of allowed actions for the automaton. For each action α _k , there is a set of states $\{ \varphi_{{\left( {k - 1} \right)N + 1}} , \ldots ,\varphi_{kN} \}$, where N is the depth of memory. The states $\varphi_{{\left( {k - 1} \right)N + 1}}$ and $\varphi_{kN}$ are the most internal state and the boundary state of action α _k , respectively. The set of all states is represented by $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } = \{ \varphi_{1} , \ldots ,\varphi_{s} \}$, where $s = N*r$. $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } = \{ 0,1\}$ is the set of inputs, where 1 represents an unfavorable response, and 0 represents a favorable response. $F: \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } *\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \to \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi }$ is a function that maps the current state and current input into the next state, and $G:\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\varPhi } \to \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha }$ is a function that maps the current state into the current output. In other words, G determines the action taken by the automaton. W objects are assigned to actions in an OMA and moved around the states of the automaton, as opposed to general learning automata, in which the automaton can move from one action to another by environmental response. The state of objects is changed on the basis of the feedback response from the environment. If the object w _i is assigned to action α _k (i.e., w _i is in state ξ _i , where $\xi_{i} \in \left\{ {\varphi_{{\left( {k - 1} \right)N + 1}} , \ldots ,\varphi_{kN} } \right\}$), and the feedback response from the environment is 0, α_k is rewarded, and w_i is moved toward the most internal state $(\varphi_{{\left( {k - 1} \right)N + 1}} )$ of that action. If the feedback from the environment is 1, then α _k is penalized, and w _i is moved toward the boundary state ($\varphi_{kN}$) of action α _k . The variable γ _k denotes the reverse of the state number of the object assigned to action α _k (i.e., degree of association between action α _k and its assigned object). By rewarding an action, the degree of association between that action and its assigned object will be increased. Conversely, penalizing an action causes the degree of association between that action and its assigned object to be decreased. An object associated with state $\varphi_{{\left( {k - 1} \right)N + 1}}$ has the most degree of association with action α _k , and an object associated with state $\varphi_{kN}$ has the least degree of association with action α _k .

3 GALA

GALA, which is a hybrid model based on a GA and an LA, was introduced for the first time by Rezapoor and Meybodi [9]. Chromosomes are represented by OMAs in this model. In the OMA-based representation, there are n actions in each automaton corresponding to n genes in each chromosome. Furthermore, for each action, there are a fixed number of states N. The value of each gene, as a migratory object in the automata, is selected from the set W = {w ₁,…,w _m } and assigned to states of corresponding action. After applying a local search, if the assignment of an object to the states of an action is promising, then the automaton is rewarded and the assigned object moves toward the most internal state of that action; otherwise, the automaton is penalized and the assigned object moves toward the boundary state of that action. The rewarding and penalizing of an action changes the degree of association between an object and its action. Figure 5 shows a representation of chromosome “dfabec” using the Tsetline automaton-based OMA with six actions and a depth of memory of five.

Fig. 5

The state transition graph of a Tsetline-based OMA

In Fig. 5 there are six actions (genes), denoted by α ₁, α ₂, α ₃, α ₄, α ₅, and α ₆. Genes 1, 2, and 6 possess values ‘d,’ ‘f,’ and ‘c,’ located at internal states 2, 3, and 4 of their actions, respectively. The value of genes 3 and 5 are ‘a’ and ‘e’ respectively, and both of them are located at the boundary states of their actions. Consequently, there is a minimum degree of association between these actions and their corresponding object. The remaining action, gene 4, has a value of ‘b’ and is located at the most internal state of its action. That is, it has the maximum degree of association with action 4. Representation of chromosomes based on other fixed structure learning automata is also possible. In a Krinsky-based OMA representation, as shown in Fig. 3, the object will be associated with the most internal state (i.e., it gets the highest degree of association with the corresponding action) when it is rewarded, and moves according to the Tsetline automaton-based OMA when it is penalized. In the representation of a Krylov OMA shown in Fig. 4, the object moves either toward the most internal state, or toward the boundary state, with a probability 0.5 toward penalty, and moves according to the Tsetline automaton-based OMA upon reward.

3.1 Global search in GALA

The global search in GALA is based on a traditional genetic algorithm. A population of chromosomes is represented by an OMA. Chromosome i is denoted by CR _i  = [(CR _i .Action(1), CR _i .Object(1), CR _i .State(1)),…,(CR _i .Action(n), CR _i .Object(n), CR _i .State(n))], where CR _i .Action(k) is the kth action of CR _i , CR _i .Object(k) is the object assigned to the k _th action (the value of the kth gene), and CR _i .State(k) is the state of the object assigned to the k _th action (the degree of association between gene k and its value), specifying 1 ≤ k≤n, 1 ≤ CR _i .Object(k) ≤ m, and (k − 1)N + 1≤CR _i .State(k) ≤ kN. The initial population is created randomly and objects are located at the boundary state of their actions. At the beginning of each generation the best chromosome from the previous generation is moved to the population of the current generation. Next, the crossover operator is applied to the parent chromosomes at rate r _c (parents are selected according to the chromosome’s fitness using a tournament mechanism), and then the mutation operator is applied at rate r _m .

3.2 Crossover operator

The crossover operator in GALA is applied as follows: Two chromosomes, CR ₁ and CR ₂, are selected by the selection mechanism as parent chromosomes. Two actions, r₁ and r₂, are also randomly selected from CR ₁ and CR ₂, respectively. Then for each action in the range of [r₁,r₂] of CR ₁, the assigned object is exchanged with an assigned object of the same action in chromosome CR ₂. In the crossover operator, the previous states of the selected actions in CR ₁ and CR ₂ are transferred to the child chromosomes. The pseudo code for the crossover operator is shown in Fig. 6.

Fig. 6

Pseudo code for a crossover operator

Figure 7 illustrates an example of a crossover operator. First, two actions are randomly selected in the parent chromosomes (e.g. actions 2 and 4 here), and then objects are assigned to all actions in the range of [2,4] in CR ₁, and are exchanged with the objects of the corresponding actions in CR ₂.

Fig. 7

An example of crossover operator

3.3 Mutation operator

The mutation operator is the same as in a traditional genetic algorithm. Two actions are selected randomly in the parent chromosome, and then their assigned objects are exchanged. The previous states of selected actions in the parent chromosome are transferred to the child chromosomes in this operator. Pseudo code for the mutation operator is shown in Fig. 8.

Fig. 8

Pseudo code for a mutation operator

Figure 9 illustrates an example of a mutation operator. First two actions in the parent chromosome are randomly selected (e.g. actions 1 and 2 here). The mutation operator exchanges both the state and the object assigned to action 1 with the state and the object assigned to action 2.

Fig. 9

A sample of mutation operator

3.4 Local learning in GALA

Local learning in GALA is done using OMA representations of chromosomes. If the objects assigned to an action are the same before and after applying a given local search, then that action will be rewarded; otherwise, it will be penalized. It is worth noting that a local search only changes the state of the actions (according to the OMA connections), not the objects assigned to the actions (i.e., the action associated with an object will not change). By rewarding an action, the state of that action will move toward the most internal state according to the OMA connection. This causes the degree of association between an object, and its corresponding action, to be increased. The state of an action remains unchanged, if the object is located at its most internal state, such as the state of object D in action 4, shown in Fig. 11.

Figure 10 provides pseudo code for rewarding an action. Figure 11 illustrates an example of rewarding an action.

Fig. 10

Pseudo code for a reward function

Fig. 11

An example of a reward function

Penalizing an action causes the degree of association between an object and its corresponding action to be decreased. If an object is not in the boundary state of its action, then penalizing causes the object assigned to the action to move toward the boundary state. This means that the degree of association between the action and the corresponding object will be decreased (Fig. 12). If an object is in the boundary state of its action, then penalizing the action causes the object assigned to that action to change, and results in the creation of a new chromosome. How a new chromosome is created depends on the application. A new chromosome is always created in such a way that its fitness becomes greater than the fitness of the old chromosome. Figure 13 shows the effect of the penalty function on action 3 of a sample chromosome (assuming that chromosome “cbadfe” has better fitness than chromosome “cbedfa”). Pseudo code for the penalty function is shown in Fig. 14. The pseudo code for GALA is shown in Fig. 15.

Fig. 12

An example of a penalty function

Fig. 13

Another example of a penalty function

Fig. 14

Pseudo code for the penalty function

Fig. 15

Pseudo code for GALA

3.5 Applications of GALA

GALA has been used in a variety of applications, including the GIP [11], join ordering problems in database queries [12–15], the traveling salesman problem [16–18], the Hamiltonian cycles problem [19], sorting problems in graphs [20], the graph bandwidth minimization problem [21–23], software clustering problems [24, 25], the single machine total weighted tardiness scheduling problem [26], data allocation problems in distributed database systems [27, 28], and the task graph scheduling problem [29, 30].

4 Modified GALA (MGALA)

Modified GALA (MGALA) is a new version of GALA. Like GALA each chromosome is represented by an object migration automaton (OMA) whose states keep information about the past history of the local search process. Each state in the OMA has two attributes: the value of the corresponding gene, and the degree of association of the gene with its value. In MGALA the fitness function is computed using the past history of the local search kept in the OMA states, as well as the chromosome’s fitness. Unlike GALA, which only uses the value of the genes for fitness computation, MGALA uses all the information in the OMA representation of the chromosome (i.e., the degree of association between genes and their values) to compute the fitness function. Hence, unlike GALA, which behaves according to a Lamarckian learning model it behaves according to a Baldwinian learning model. MGALA’s various components will be described in the remainder of this section.

4.1 Fitness function

The fitness function in MGALA is not only dependent on genotype information, but also on phenotype information. We use the fitness function $f^{'} (CR) = \sum\nolimits_{i = 1}^{n} {f_{i} (1 + \gamma_{i} )}$ for maximization problems, and $f^{'} (CR) = \sum\nolimits_{i = 1}^{n} {f_{i} (1 - \gamma_{i} )}$ for minimization problems in the selection of chromosomes. In these functions f _i is the fitness of the ith gene, and γ _i is the degree of association between action α _i and its assigned object. The depth of memory is N, so we have $\frac{1}{N} \le \gamma_{i} \le 1$. The parent chromosomes and the chromosomes of the next generation are selected based on the defined fitness function using a tournament mechanism.

4.2 Mutation operator

Depending on whether the state of the selected actions changes or not, we define two types of mutation operators in MGALA. In the first type the states of the selected actions remain unchanged (i.e., the degree of association between actions and their assigned objects are saved). In second class the states of the selected actions are changed (i.e., the degree of association between actions and their assigned objects are lost).

MGALA has three mutation operators defined in this paper: SS-Mutation, XS-Mutation, and LS-Mutation. Specifically:

• The mutation operator in which the previous state of selected actions can be saved is referred to as the SS-Mutation.

• The mutation operator in which the previous state of selected actions can be exchanged is referred to as the XS-Mutation.

• The mutation operator in which the previous state of selected actions can be lost is referred to as the LS-Mutation.

The SS-Mutation and XS-Mutation are examples of the first type of mutation operator described above, and the LS-Mutation is an example of the second type. These mutation operators are described in more detail below.

4.2.1 SS-Mutation

Assuming actions 1 and 2 are the selected actions, the SS-Mutation exchanges the objects assigned to the states of actions 1 and 2. Figure 16 shows an example of an SS-Mutation. Pseudo code for our SS-Mutation is shown in Fig. 17.

Fig. 16

An example of an SS-Mutation

Fig. 17

Pseudo code for the SS-Mutation

4.2.2 XS-Mutation

The XS-Mutation is the same as the mutation that GALA uses. The states of the actions, along with their assigned objects, are exchanged. Figure 18 shows an example of an XS-Mutation. Assuming actions 1 and 2 are the selected actions, the XS-Mutation exchanges the object and the state of action 1 with those of action 2. Pseudo code for our XS-Mutation is shown in Fig. 19.

Fig. 18

An example of an XS-Mutation

Fig. 19

Pseudo code for the XS-Mutation

4.2.3 LS-Mutation

The LS-Mutation is the same as that used in GALA, except that the state of each action is changed to become its corresponding boundary state. Figure 20 shows an example of an LS-Mutation operator. Assuming that actions 1 and 2 are the selected actions, the LS-Mutation operator causes: 1) The object assigned to the state of action 1 is exchanged with the assigned object of the action; and 2) The state of each action changes to become its corresponding boundary state. Pseudo code for our LS-Mutation operator is given in Fig. 21.

Fig. 20

An example of an LS-Mutation

Fig. 21

Pseudo code for the LS-Mutation

4.3 Crossover operator

Similar to the mutation operators, we define two different types of crossover operators for MGALA. In the first type, the states of selected actions remain unchanged, and in the second type the states of the actions change to the boundary states.

Three crossover operators, SS-Crossover, XS-Crossover, and LS-Crossover, are defined in MGALA:

• The crossover operator in which the previous state of selected actions can be saved is referred to as the SS-Crossover.

• The crossover operator in which the previous state of selected actions can be exchanged is referred to as the XS-Crossover.

• The crossover operator in which the previous state of selected actions can be lost is referred to as the LS-Crossover.

The SS-Crossover and XS-Crossover are examples of crossover operators of the first type, and the LS-Crossover is an example of the second type. These crossover operators are described in further detail below.

4.3.1 SS-Crossover

Figure 22 shows an example of an SS-Crossover. Assuming actions 2 and 4 are selected randomly from the parent chromosomes, the SS-Crossover exchanges the assigned object of each action in the range of [2,4] of CR ₁, with the assigned object of the same action in the range of [2,4] of CR ₂. Note that in the SS-Crossover the states of the actions remain unchanged. Pseudo code for the SS-Crossover is shown in Fig. 23.

Fig. 22

An example of an SS-Crossover

Fig. 23

Pseudo code for the SS-Crossover

4.3.2 XS-Crossover

The XS-Crossover is the same as the crossover used in GALA. Figure 24 shows an example of an XS-Crossover. Assuming actions 2 and 4 are selected randomly from the parent chromosomes, the XS-Crossover exchanges both the assigned object and the state of each action in the range of [2,4] of CR ₁, with the assigned object and the state of the same action in the range of [2,4] of CR ₂. Figure 25 shows the pseudo code for the XS-Crossover.

Fig. 24

An example of an XS-Crossover

Fig. 25

Pseudo code for the XS-Crossover

4.3.3 LS-Crossover

The LS-Crossover is the same as the crossover used in GALA, except that the state of each action is changed to become its corresponding boundary state. Figure 26 shows an example of an LS-Crossover. Assume that actions 2 and 4 are randomly selected in the parent chromosomes, then the LS-Crossover causes: (1) Each object assigned to the actions in the range of [2,4] of CR ₁ is exchanged with the assigned object of the same action in the range of [2,4] of CR ₂; and (2) The state of each action changes to become its boundary state. Figure 27 shows the pseudo code of the LS-Crossover.

Fig. 26

An example of an LS-Crossover

Fig. 27

Pseudo code for the LS-Crossover

5 The equipartitioning problem

Let $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{A} = \{ A_{1} , \ldots ,A_{W} \}$ be a set of W objects. We want to partition $\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{A}$ into R classes {P ₁,…,P _R } such that the objects used more frequently are located together in the same class. We assume that the joint access probabilities of the objects are unknown. This problem is called the object partitioning problem. A special case of the object partitioning problem, referred to as the equal partitioning problem (EPP), is where the objects are equipartitioned. In an EPP each class has exactly M = W/R objects. For solving the EPP with MGALA we define a chromosome to have W genes (actions) and the value of the genes are selected from a set of classes {P ₁,…,P _R } (as migratory objects in the OMA) such that each class is assigned to W/R of genes (actions). Objects are initially assigned to the boundary state of actions. Figure 28 shows a chromosome based on a Tsetline OMA representation for 6 objects and 2 classes (called class α and class β) with N = 5. In this figure objects 1, 3, and 4 are assigned to class α, and objects 2, 5, and 6 are assigned to class β.

Fig. 28

A chromosome representation of the EPP with W = 6, R = 2, and N = 5

5.1 Local search for EPP

Suppose a query [which is a pair of objects (A _i , A _j )] has been accessed. If the assigned objects of actions α _i and α _j are the same, then both actions α _i and α _j are rewarded and their states change according to OMA connections. If the assigned objects of actions α _i and α _j are different, then they are penalized and their states change according to OMA connections. Pseudo code for our local search of the EPP is shown in Fig. 29.

Fig. 29

Pseudo code for our local search of the EPP

5.2 Experimental results

We studied the efficiency of our MGALA algorithm in solving the EPP by comparing its results to those obtained for an OMA method reported in [10] and to the GALA algorithm. Queries were chosen randomly from a pool of queries for all experiments. The pool of queries was generated in such a way that the sum of probabilities that object A _i in partition π _i is jointly accessed with other objects in partition π _i is p, and with objects in partition π _j (j ≠ i) is 1 − p, that is:

$$ \mathop \sum \limits_{{A_{j} \in \pi_{i} }} \Pr \left[ {A_{i} ,A_{j} \,accessed\,together} \right] = p $$

(1)

Therefore, if p = 1, then queries will only involve objects in the same partition. As the value of p decreases, the queries will become decreasingly informative about the solution of the EPP [10]. For all experiments an initial population of chromosomes of size 1 was randomly created, the size of each chromosome was set equal to the number of objects, the mutation rate was 0.05, the selection mechanism was (1,1), p was 0.9, and the depth of memory was 2. The algorithm terminates when all the objects in only chromosome are located in the most internal state of their actions. For all experiments a Tsetline-based OMA was used for chromosome representation. Each reported result was averaged over 30 runs. We performed a parametric test (T test) and two non-parametric tests (wilcoxon rank sum test and permutation test) at the 95 % significance level to provide statistical confidence. The T tests were performed after ensuring that the data followed a normal distribution (by using the Kolmogorov–Smirnov test).

5.2.1 Experiment 1

In this experiment we compared the results obtained from MGALA with the results of two other algorithms, an OMA-based algorithm reported in [10] and the GALA version of the algorithm, for the EPP, in terms of the number of iterations (number of accessed queries) required by the algorithm. MGALA was tested with three different mutation operators: SS-Mutation, XS-Mutation, and LS-Mutation.

Table 1 presents the results of the different algorithms for 14 different cases with respect to the average number of iterations and their standard deviation. From the results reported in Table 1 we report the following:

Table 1 Comparison of the number of iterations required by different algorithms

• The MGALA algorithm outperforms both the OMA and GALA algorithms.

• For cases (W = 9 and R = 3), (W = 12 and R = 2) and (W = 8 and R = 2), MGALA using the LS-Mutation performs the best, and for the other cases MGALA with the SS-Mutation displays the best performance.

• The OMA algorithm displays the worst performance compared with the GALA and MGALA algorithms.

• As the number of classes (R) decreases, the number of iterations required by all algorithms increase. This is because a low value for R means a higher number of objects will be placed in each class, leading to a situation where more actions have the same class number (migratory objects). This causes the probability that a mutation operator swaps two objects between two actions to decrease.

• MGALA with the XS-Mutation displays the same performance as GALA. This is because: (1) In the MGALA and GALA algorithms, the selection mechanism is considered to be (1,1), that is, MGALA, like GALA, has no selection mechanism in this mode; and (2) the XS-Mutation operator used by MGALA is the same as the mutation operator used by GALA.

Table 2 shows the p values of the two-tailed T test, the p values of the two-tailed wilcoxon rank sum test and the p values of the two-tailed permutation test. From the results reported in Table 2 we report the following:

Table 2 The results of statistical tests for OMA algorithm and other algorithms

• For all three kinds of statistical tests (wilcoxon, permutation and T test), the difference between the performance of the OMA and the performance of the other algorithms is statistically significant (p value <0.05) in most cases.

5.2.2 Experiment 2

This experiment’s goal was to evaluate the accuracy of the solution produced by MGALA. Before we introduce the concept of accuracy for MGALA, we will provide some preliminaries. For this purpose we use an example of equipartitioning with the 4 objects A ₁, A ₂, A ₃, and A ₄, and two classes, α and β. A Tsetline based on an OMA with a depth of memory 2 will be used for the chromosome representation shown in Fig. 30. We also assume that the initial population is of size one, and that the only chromosome in the initial population is created randomly, and has its migratory objects in the boundary state of the actions.

Fig. 30

A representation of the EPP with W = 4, R = 2, and N = 2

For this example there are the three possible object equipartitioning schemes specified below:

• ααββ: Objects A ₁, A ₂ are in class α and objects A ₃, A ₄ are in class β.

• αβαβ: Objects A ₁, A ₃ are in class α and objects A ₂, A ₄ are in class β.

• αββα: Objects A ₁, A ₄ are in class α and objects A ₂, A ₃ are in class β.

The chromosome in Fig. 30 can be also represented by $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$ which corresponds to the following situation:

• Object A ₁ is in partition α and the migratory object is located in the boundary state of action 1.

• Object A ₂ is in partition α and the migratory object is located in the internal state of action 2.

• Object A ₃ is in partition β and the migratory object is located in the internal state of action 3.

• Object A ₄ is in partition β and the migratory object is located in the boundary state of action 4.

Each possible equipartitioning scheme may correspond to any of the 16 possible chromosomes out of all 48 possible chromosomes. For example chromosomes $(\bar{\alpha }\bar{\alpha }\bar{\beta }\bar{\beta })$, $(\bar{\alpha }\bar{\alpha }\bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, $(\bar{\alpha }\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta }\bar{\beta })$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\bar{\beta }\bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$,$(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, and $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$ show the equipartitioning ααββ.

We group chromosomes corresponding to a given equipartitioning into two different sets: a converged chromosomes set (CCS), and a non-converged chromosomes set (NCCS). The CCS includes all the chromosomes for which all objects of class α or class β are in the internal states. All other chromosomes are in the NCCS. For example, chromosomes $(\bar{\alpha }\bar{\alpha }\bar{\beta }\bar{\beta })$, $(\bar{\alpha }\bar{\alpha }\bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\bar{\beta })$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\bar{\beta }\bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, and $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, of equipartitioning ααββ, are in the NCCS of equipartitioning ααββ, and $(\bar{\alpha }\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, and $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$ are in the CCS of equipartitioning ααββ. MGALA converges to one of the following six sets: either the NCCS of equipartitioning ααββ, or the CCS of equipartitioning ααββ, or the NCCS of equipartitioning αβαβ, or the CCS of equipartitioning αβαβ, or the NCCS of equipartitioning αββα, or the CCS of equipartitioning αββα. Let p1, p2, p3, p4, p5, and p6 be the probabilities of the current chromosome to be in one of the above-mentioned sets, respectively. Furthermore, assume that eighty percent of the queries accessed from the pool of queries are (A ₁, A ₂) or (A ₃, A ₄). For MGALA to produce the correct solution it must generate a population containing one of following chromosomes: $(\bar{\alpha }\bar{\alpha }\bar{\beta }\bar{\beta })$, $(\bar{\alpha }\bar{\alpha }\bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, $(\bar{\alpha }\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\bar{\beta })$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, $(\bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\bar{\beta }\bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$,$(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\alpha }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\bar{\beta })$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \bar{\beta }\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$, $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \bar{\beta })$, and $(\underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\alpha } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } \underset{\raise0.3em\hbox{$\smash{\scriptscriptstyle-}$}}{\beta } )$. So, MGALA must converge to one of the sets of NCCS of equipartitioning, or to one of the sets of CCS of equipartitioning ααββ. The algorithm is more accurate if the probability of converging to a set of NCCS of equipartitioning, or to a set of CCS of equipartitioning ααββ (that is p ₁  + p ₂ ) are higher than 0.8.

Next we undertook the experimentation phase of the study. Input queries were generated in such a way that eighty percent of the queries accessed from the pool of queries were (A ₁, A ₂) or (A ₃, A ₄). Note that the initial population is considered to be of size one, that the only chromosome in the initial population is created randomly, and that it has its migratory objects at the boundary state of the actions. That is chromosome $(\bar{\alpha }\bar{\alpha }\bar{\beta }\bar{\beta })$, which belongs to the NCCS of equipartitioning $\alpha \alpha \beta \beta$, or $(\bar{\alpha }\bar{\beta }\bar{\alpha }\bar{\beta })$, which belongs to the NCCS of equipartitioning αβαβ, or $(\bar{\alpha }\bar{\beta }\bar{\beta }\bar{\alpha })$, which belongs to the NCCS of equipartitioning αββα are the only options. Therefore, initial values for p ₁ , p ₃ , and p ₅ are considered to be zero, and initial values for p ₂ , p ₄ , and p ₆ are considered to be 1/3. Figure 31a–c show the evolution of p ₁ , p ₂ , p ₃ , p ₄ , p ₅ , and p ₆ for the three different mutation operators SS-Mutation, XS-Mutation, and LS-Mutation.

Fig. 31

The evolution of p ₁ , p ₂ , p ₃ , p ₄ , p ₅ , and p ₆ in MGALA with W = 4, R = 2, and N = 2, for the SS-Mutation (a), XS-Mutation (b), and LS-Mutation (c) operator for the EPP

These figures show that p ₁  + p ₂ approaches a value close to 0.9 for all mutation operators. That is, when eighty percent of the queries accessed from the pool of queries are A ₁, A ₂ or A ₃, A ₄, MGALA converges to the correct equipartitioning (ααββ) with a probability close to 0.9. The mutation rate was set to 0.05 for this experiment.

Table 3 presents the MGALA algorithm results for different mutation operators and different query percentages (accessed from the pool of queries) being (A ₁, A ₂) or (A ₃, A ₄), with respect to the accuracy of the solution and its standard deviation. The percentage varies from 40 to 100 by increments of 10 in Table 3. From these results we conclude the following:

Table 3 Accuracy of MGALA with respect to percentage of queries (A ₁, A ₂) or (A ₃, A ₄) and mutation operators

• For all mutation operators the accuracy of the solution generated by MGALA increases as the percentage of queries (A ₁, A ₂) or (A ₃, A ₄) in the input increases.

• MGALA has the highest accuracy when the LS-Mutation operator is used.

Table 4 shows the results of statistical tests. From the results reported in Table 4 we report the following:

Table 4 The results of statistical tests for MGALA algorithm with LS-Mutation operator vs. MGALA algorithm with SS-Mutation and XS-Mutation operators with respect to percentage of queries (A ₁, A ₂) or (A ₃, A ₄)

• For all three kinds of statistical tests (wilcoxon, permutation and T test), the difference between the performance of the MGALA algorithm when it uses the LS-Mutation operator and the performance of the MGALA algorithm when it uses other mutation operators is not statistically significant (p value >0.05).

5.2.3 Experiment 3

The goal of this experiment was to study the impact of the parameter N (depth of memory) on the number of iterations required by the MGALA algorithm to find optimal equipartitioning. The depth of memory was varied from 2 to 10 by increments of 2. MGALA was tested with three different mutation operators. Tables 5, 6 and 7 show the results obtained for the MGALA algorithm with the SS-Mutation, XS-Mutation, and LS-Mutation for 14 different cases, with respect to the average number of iterations required and their standard deviation.

Table 5 Number of iterations required by MGALA with SS-Mutation operator for different cases and different depths of memory

Table 6 Number of iterations required by MGALA with XS-Mutation operator for different cases and different depths of memory

Table 7 Number of iterations required by MGALA with LS-Mutation operator for different cases and different depths of memory

• For lower values of R MGALA requires a higher number of iterations to converge to optimal equipartitioning.

• For higher values of W/R MGALA requires a higher number of iterations to converge to optimal equipartitioning.

• For higher values of W/R MGALA requires a higher depth of memory to converge to optimal equipartitioning.

• The MGALA algorithm with a depth of memory N = 2 performs better than MGALA with a depth of memory of N ≠ 2.

These conclusions are because higher values of W/R mean a higher number of objects are placed in each class. This leads to a situation where more actions have the same class number (migratory objects), and also decreases the probability that a mutation operator swaps two objects between two actions.

Tables 8, 9 and 10 show the p values of the two-tailed T test, the p values of the two-tailed wilcoxon rank sum test and the p values of the two-tailed permutation test for MGALA algorithm with SS-Mutation, XS-Mutation and LS-Mutation respectively. From the results reported in these tables we report the following:

Table 8 The results of statistical tests for MGALA with SS-Mutation and depth of memory 2 vs. MGALA algorithm with SS-Mutation and other depths of memory

Table 9 The results of statistical tests for MGALA with XS-Mutation and depth of memory 2 vs. MGALA algorithm with XS-Mutation and other depths of memory

Table 10 The results of statistical test for MGALA algorithm with LS-Mutation and depth of memory 2 versus MGALA algorithm with LS-Mutation and other depths of memory

• For all three kinds of statistical tests (wilcoxon, permutation and T test), the difference between the performance of the MGALA algorithm with depth of memory N = 2 and the performance of the MGALA algorithm with a depth of memory of N ≠ 2 is statistically significant (p value <0.05) in most cases for all three types of operators.

6 The graph isomorphism problem

A graph is described by G = (E, V) where V is the set of vertices and $E \subset V*V$ is the set of edges. Two graphs G = (E ₁, V ₁) and H = (E ₂, V ₂) are isomorphic if, and only if, their adjacency matrices M(G) and M(H) differ only by permutations of rows and columns, i.e., M(G) and M(H) are related with a permutation σ, according to Eq. (2).

$$ M(H) = P*M(G)*P^{T} \to \left[ {P*M(G)*P^{T} } \right]_{i,j} = [M(H)]_{\sigma \left( i \right),\sigma (j)} , $$

(2)

where P is the permutation matrix of σ. If we define the difference between two graph as

$$ J(\sigma ) = \left| {\left| {M(H) - P*M(G)*P^{T} } \right|} \right|, $$

(3)

where $|| \cdot ||$ is the matrix norm, defined as $\left| {\left| M \right|} \right| = \sum_{i} \sum_{j} |m_{ij} |$, the GIP can then be formulated as a search optimization problem in searching for a permutation σ that minimizes J(σ).

The mapping error of vertex k in graph G to vertex σ(k) in graph H is defined as

$$ J_{k} (\sigma ) = \mathop \sum \limits_{m = 1}^{n} \left| {[M(H)]_{k,m} - \left[ {M(G)} \right]_{\sigma (k),\sigma (m)} } \right| + \mathop \sum \limits_{m = 1}^{n} \left| {[M(H)]_{m,k} - [M(H)]_{\sigma (m),\sigma (k) } } \right|, $$

(4)

where n is the number of vertices of G and H. For undirected graphs the mapping error can be computed according to Eq. (5), as given below:

$$ J_{k} \left( \sigma \right) = 2*\mathop \sum \limits_{m = 1}^{n} \left| {[M\left( H \right)]_{k,m} - [M\left( H \right)]_{\sigma \left( k \right),\sigma \left( m \right)} } \right| $$

(5)

Consequently, the mapping error of graphs G and H can be computed using Eq. (6).

$$ J\left( \sigma \right) = \mathop \sum \limits_{k = 1}^{n} J_{k} \left( \sigma \right) $$

(6)

In this paper we use $f_{g} = C_{max} - J\left( \sigma \right)$ as genetic fitness, where C _max is the maximum of J(σ) [31].

6.1 The local search in the graph isomorphism problem

If two graphs are isomorphic to each other, then the weight and the number of input and output edges of isomorphic vertices must be equal. This is taken into consideration in the design of the local search procedure [31]. Pseudo code for our local search method is given in Fig. 32. This local search method consists of the following steps:

Fig. 32

Pseudo code for the local search in the GIP

• 1. The vertices are partitioned into a number of subsets of equal weight.

• 2. The worst gene of the current chromosome is selected (line 2 of Fig. 32).

• 3. The value of the selected gene is swapped with the value of a random gene selected from the same subset (lines 3 and 4 of Fig. 32).

6.2 Experimental results

In this section, several experiments are described that studied the effect of different MGALA parameters on the performance of the GIP. For this purpose we used a database with 10,000 coupled pairs of isomorphic graphs with different sizes [32]. We classified these graphs into three groups: small graphs (n < 50), medium graphs (50 ≤ n < 100), and large graphs (100 ≤ n < 200). MGALA results are compared with the results obtained from an algorithm based on a GA [31], an algorithm reported by Ullmann [33], and the VF and VF2 algorithms [34]. The source codes for these algorithms are available at http://amalfi.dis.unina.it/graph. Every result reported is the average of 30 runs. For all experiments an initial population of size 100 was created randomly, the chromosome size was set equal to the size of the graph, the mutation rate and crossover rate were both set to 0.05, and the selection mechanism was (µ + λ). Each algorithm terminates when either solution has been found or the number of generations exceeds 10,000. A Tsetline-based OMA is used for all experiments to represent chromosomes. We use RT to refer to running time, FE to refer to the number of fitness evaluations for the runs converged to the solution, and NR to refer to the number of runs not converged to the solution. All experiments were performed on three classes of graphs: small graphs (SG), medium graphs (MG) and large graphs (LG). We performed a parametric test (T test) and two non-parametric tests (wilcoxon rank sum test and permutation test) at the 95 % significance level to provide statistical confidence. The T tests were performed after ensuring that the data followed a normal distribution (by using the Kolmogorov–Smirnov test).

6.2.1 Experiment 1

Experiment 1 aimed to find the optimal memory depth for different classes of graphs for the MGALA algorithm. For this purpose we studied the effect of parameter N (depth of memory) on the FE, RT, and NR. The MGALA results were then compared with the results obtained for the Canonical Memetic Algorithm (CMA). Note that MGALA is equivalent to the CMA when N = 0. For this experiment the graph density was set to 0.5, and weights for vertices and edges were chosen from [0,100]. Table 11 lists the RT, FE, NR, and the standard deviation for the different depths of memory employed. From the results we conclude the following:

Table 11 performance of MGALA with respect to depth of memory

• For all classes of graphs the minimum value for RT and FE are obtained when N = 0,

• For all classes of graphs the maximum value for NR is obtained when N = 0, and

• For all classes of graphs the NR is inversely proportional to depth of memory.

Table 12 shows that, according to results of wilcoxon test, permutation test and T test, the MGALA algorithm with a memory depth of N = 2 performs better than the MGALA algorithm for N ≠ 2 for large graphs (LG).

Table 12 The results of statistical test for MGALA algorithm with depth of memory N = 2 versus MGALA algorithm with other depths of memory

Figure 33 shows the impact of the depth of memory on the FE and NR for different classes of graphs. Changes in the FE are minor for a depth of memory greater than 4 in all classes of graphs. Also, this figure shows that for all classes of graphs, a depth of memory greater than 10 causes convergence (NR = 0) in all runs.

Fig. 33

Number of fitness evaluations (FE) and number of non-converged runs (NR) vs. depth of memory for different classes of graphs

6.2.2 Experiment 2

This experiment investigated the effect of graph edge and vertex weights on MGALA performance. We studied the effect of weights on the FE, RT, and NR for different classes of graphs using MGALA and CMA (MGALA when N = 0). For this experiment the density of all graphs was set to 0.5 and N was set to 10. The experiment was repeated for five different weight ranges: [0,20], [0,40], [0,60], [0,80], and [0,100]. The experiment was also repeated with unweighted graphs (graphs whose edge weights are chosen from {0,1}, and whose nodes have no weights). Table 13 gives the RT, FE, NR, and standard deviation for the different weight parameters.

Table 13 Performance of MGALA with respect to the weight parameter

From these experimental results we conclude the following for MGALA:

• For all classes of graphs RT and FE are minimized when the weights for vertices and edges are chosen from [0,100] and are maximized for the unweighted graph. This is because GIP only uses the properties of local search method. If the weights of the graph have higher values, then the vertices of the graph are partitioned into a higher number of subsets with a lesser number of members. The effect of this is to cause just the vertices of the subset, which have same weight as the worst gene, to have a chance for exchanging with the worst gene in the local search method. Consequently, the local search selects an alternative vertex accurately in weighted graphs.

• For all classes of graphs the NR is inversely proportional to the weights of the vertices and edges.

• For all classes of graphs the maximum value of NR is obtained when CMA is used.

Table 14 shows that, for all three kinds of statistical tests (wilcoxon, permutation and T test), the difference between the performance of the MGALA algorithm when weights for vertices and edges are chosen from [0,100], and the performance of the MGALA algorithm when it uses other weight parameter values that are statistically significant (p value <0.05) for most graphs.

Table 14 The results of statistical tests for MGALA algorithm with weight parameter [0,100] vs. MGALA algorithm with other values of weight parameter

Figure 34 shows the FE for different graph classes and weights. The FE for all classes of graphs when the weights are chosen from ranges greater than [0,20] are almost the same. Figure 34 also shows that with all graph classes the NR is equal to zero when the weights are chosen from ranges greater than [0,60]. Consequently, the FE and NR are both minimized when the weights are chosen from ranges greater than [0,60] (ranges [0,80] or [0,100]).

Fig. 34

Number of fitness evaluations (FE) and number of non-converged runs (NR) vs. the weight parameter for different classes of graphs

6.2.3 Experiment 3

Experiment 3 studied the effect of graph density (D) on MGALA performance. The density of a graph is defined as $= \frac{2|E|}{\left| V \right|(\left| V \right| - 1)}$, which is the probability of the existence of an edge between any two vertices. For this experiment the weights of vertices and edges were chosen from [0,100], and N was set to 10. The impact of graph density on the FE, RT, NR, and the standard deviation for different classes of graphs using both MGALA and CMA are reported in Table 15. From these results we conclude the following:

Table 15 performance of MGALA with respect to graph density

• For all classes of graph RT and FE are minimized when the graph density is 1.

• For all classes of graphs NR decreases as the graph density increases.

• For all classes of graphs a maximum value for NR is obtained when CMA is used.

Table 16 shows that, for all three kinds of statistical tests (wilcoxon, permutation and T test), the difference between the performance of the MGALA algorithm when the density is 1, and the performance of the MGALA algorithm when it uses other density parameter values, is statistically significant (p value <0.05) for most graphs.

Table 16 The results of statistical tests for MGALA algorithm with density 1 versus MGALA algorithm with other values of density parameter

Figure 35 shows the impact of graph density on the FE for different classes of graphs. The FE remains almost fixed for graph densities >0.5 for all classes of graphs. Figure 35 also shows that for all classes of graphs, all runs converge (NR) to zero when the graph density is >0.6.

Fig. 35

Number of fitness evaluations (FE) and number of non-converged runs (NR) vs. density of graph for different classes of graphs

6.2.4 Experiment 4

The experimental goal here was to study the impact of different mutation and crossover operators on MGALA performance. For this experiment the density of all graphs was set to 0.5, and the depth of memory was set to 10. Weights for vertices and edges were selected from [0,100]. Table 17 lists the RT, FE, NR, and the standard deviations from different mutation and crossover operators. These results lead us to conclude the following:

Table 17 Performance of MGALA for different mutation and crossover operators

• For all classes of graphs a minimum NR value is obtained when the LS-Mutation and LS-Crossover operators are used.

• For large size graphs (LG), with respect to the FE and RT, MGALA with the SS-Mutation and SS-Crossover operators outperforms both MGALA with the XS-Mutation and XS-Crossover operators, as well as MGALA with the LS-Mutation and LS-Crossover operators.

• For medium size graphs (MG), with respect to FE and RT, MGALA with the LS-Mutation and LS-Crossover operators outperforms both MGALA with the SS-Mutation and SS-Crossover operators, as well as MGALA with the XS-Mutation and XS-Crossover operators.

• For small size graphs (SG), with respect to FE and RT, MGALA with the XS-Mutation and XS-Crossover operators outperforms both MGALA with the SS-Mutation and SS-Crossover operators, as well as MGALA with the LS-Mutation and LS-Crossover operators.

• For all classes of graphs the maximum value for NR is obtained when CMA is used.

According to Table 18, the MGALA algorithm with the SS-Mutation and SS-Crossover operators performs better than the MGALA algorithm with other mutation operators for large graphs.

Table 18 The results of statistical tests for MGALA algorithm with SS-Mutation, SS-Crossover vs. MGALA algorithm with other operators

6.2.5 Experiment 5

MGALA was compared with five other algorithms in this experiment (GA [31], Ullmann [33], VF and VF2 [34], and GALA [11] ) for the GIP, in terms of the number of fitness evaluations required. The result of this experiment is shown in Fig. 36. Each result was the average of 30 runs. The graph size was varied from 10 to 200 by an increment of 10. The results clearly show the superiority of MGALA.

Fig. 36

Number of fitness evaluations vs. graph size for different algorithms

7 Conclusions

A new memetic algorithm called MGALA is proposed for optimization purposes in this paper. MGALA, which is a newly revised version of GALA, is obtained from a combination of a GA and an LA, in which the LA plays the role of providing the local search. Unlike GALA, which uses Lamarckian learning, MGALA uses a Baldwinian learning model to improve its convergence rate and the quality of its solution. In this model, chromosomes are represented by OMAs, and the OMA states keep information about the history of the local search process. Each state in the OMA has two attributes: the value of the gene (allele), and the degree of association with the value of the gene. The local search changes the degree of association between genes and their values. Unlike GALA, which only uses the value of the genes for its fitness computation, MGALA uses all the information recorded in the OMA representation of the chromosome (i.e., the degree of association between genes and their allele, and the values of the genes) to compute the fitness of genes. In other words, MGALA’s fitness function is computed using a chromosome’s fitness (as genotype information) and the history of the local search kept in the states of the OMA (as phenotype information). The EPP and GIP applications were used to investigate the performance of MGALA. MGALA was also compared with some other well-known algorithms for the EPP and GIP application. Our experimental results showed the superiority of the proposed algorithm in terms of quality of solution and in the rate of convergence. This line of research could be extended in several directions, such as in applying GALA and/or MGALA in solving optimization problems where the environment is dynamic. Extension examples include the dynamic shortest path problem and the dynamic traveling salesman problem, improving the proposed algorithms by designing new mutation or crossover operators, and designing new object migrating automata to be used for chromosome representation. Another direction that may be pursued is the development of a mathematical framework for analyzing the proposed algorithm.