Chapter 4: Methodology

CHAPTER 4

METHODOLOGY

The proposed algorithm is explained in this section. The main idea of the algorithm is to allow learning from the below average solutions as well as the traditional learning from the good solutions. The coincidence found in a situation should be able to statistically describe the chance of the situation to be happening whether the situation is good or bad. Thus the learning of the coincidence found in the bad solutions should be used to avoid the bad situation as well.

Design

Coincidence algorithm (COIN) is designed to construct the solutions based on the mutual information in type I relative o-schema. We assume that there are linkages between each of the permuted items. In this algorithm, we focus on the pair of permuted objects called incidences rather than the absolute position of a single object. For example, two candidates with order 5, [ 1 2 3 4 5 ] and [ 4 5 3 2 1 ] share the common coincidence [ 4 5 ] which is considered to be a schema in the type I relative o-schema.

According to the building blocks hypothesis (BBH), the coincidences can be considered to be the building blocks. However, we would not rather call the coincidences as building blocks due to the coincidences can describe only some partial building blocks as they cover only some types of the o-schemas.

COIN adapts the first order matrix of MCMC[23] (Markov Chain Monte Carlo) as a data structure to maintain the joint probabilities, this matrix identifies both positive and negatives incidences found in the populations. Then it is used to generate the populations according to the conditional probability.

Even though the building blocks with gaps are not easy to be recognized, they are indirectly identified using the conditional probability property of Markov Chain. Therefore COIN can indirectly recognize the type II relative o-schema as well.

Design of COIN is similar to an algorithm called Mutual Information Maximizing Input Clustering (MIMIC), MIMIC[24] is one of the most famous algorithms in bivariate dependency class EDA. In 1997, De Bonet et al proposed a greedy algorithm that searches in each generation for the best permutation between the variables in order to find the probability distribution, p_l^π(x) that is closest to the empirical distribution of the set of selected points when using the Kullback-Leibler distance, where

p_l^π(x) = p_l(x_i1|x_i2) * p_l(x_i2|x_i3) * … * p_l(x_in − 1|x_in)p_l(x_in)
(1) ——————————————————————————————————————————————————————————————————————- ———

and π = (i₁,i₂,…,i_n) denotes a permutation of the indexes 1,2,….,n.

COIN uses the same distribution as MIMIC. However, COIN does not estimate the selected population the same way as MIMIC and MCMC. COIN rather uses the incremental model based on reward and punishment. When an incidence is found in the above average solutions, it is rewarded more probability to be selected. Otherwise, if an incidence is found in the under average solutions, it would be punished by deducting the probability to be selected. The reward probabilities are gathered from the other incidences equally, while the deducted probabilities are scattered to the other incidences the same way.

Components

Similar to most black box optimization algorithms, the components of the algorithms are composed of data structure and fitness function(s) evaluator. The data structure of this algorithm mimics from the first order matrix of Markov Chain in which we use to learn the positive and negative building blocks in a form of joint probabilities and then use the joint probability to generate the candidates. We simply call it a generator.

1. Generator

The COIN algorithm uses a generator to generate the population according to the coincidences found in the good and the bad candidates. The generator is a matrix of size n × n where n is the size of a permutable candidate. Each row denote a dependency tree, where each of the members in the row is the joint probability h(X_i|X_j). X_i indicates the row of the matrix, while X_j indicates the column. A coincidence is denoted by X_i,X_j of the event X_i followed by the event X_j. The coordinate X_i,_j indicates the joint probability h(X_i|X_j).

2. Fitness Function Evaluator

The fitness function evaluator is used to evaluate the fitness of the solution generated by the generator. To maximize the efficiency of the algorithm, the solutions are sorted on the fly as the selection mechanism of the algorithm needs to select the solutions from their ranks.

1. Initialize the generator.

2. Generate the population using the generator.

3. Evaluate and rank the population.

4. Select the candidates. There are two methods:

   1. Uniform selection: select the top and bottom c percent.

   2. Adaptive selection: select the above and below the average ±2σ

5. For each joint probability h(x_i|x_j), update the generator according to the reward and punishment :-

$$X_{i,j}\left( t + 1 \right) = X_{i,j}\left( t \right) + \frac{k}{\left( n - 1 \right)}\left( r_{i,j}\left( t + 1 \right) - p_{i,j}\left( t + 1 \right) \right) + \frac{k}{\left( n - 1 \right)^{2}}\left( \sum_{j = 1}^{n}{p_{i,j}(t + 1)} - \sum_{j = 1}^{n}{r_{i,j}(t + 1)} \right)$$

where X_i,j denotes the joint probability h(x_i|x_j), k is the learning coefficient, r_i,j denotes the number of coincidence X_i,X_j found in the good solutions, p_i,j denotes the number of coincidence X_i,X_j found in the not-good solutions, n is the size of the problem.

6. Repeat Step 2. Until the terminate condition is met.

Fig. 6. Pseudo code for COIN

Mechanics

The mechanism of the COIN algorithm is shown in Fig. 6. It begins by initializing the generator then the population is sampling from the generator. The generator is updated by each of the coincidences found in the selected good and bad candidates according to their evaluated ranks. The generating, evaluation and updating steps are repeated until terminate condition is met.

1. Initialization

The generator is initialized so that each of the joint probabilities h(X_i|X_j) except the X_i,_j equal to 1/((n-1)) . The summation of all joint probability h(X_i|X_j) where j range from 1 to n is equal to 1. This initialization represents the uniform distribution of each joint probability in the dependency tree.

2. Generating the Population

Each individual are sampling one position by one position from head to tail. The next position is generated depend on the current and all of the previously generated position. Therefore the permuted sequences are always feasible. The sampling procedure is as follows:

1. Begin at any node, Xi in the tree. This is the root node. Pick its value according to its empirical probability h(X_i).

2. Perform a depth-first traversal of the tree from the root. For each Xi, choose its value according to the empirical probability h(X_i|X_j).

3. Selection

Two selection methods are considered: a uniform method selects from the top and bottom c percent of the population and an adaptive method selects from the population above and below the average band of two standard deviations.

In the adaptive selection process, if the population contains more good candidates, the selector will select more of the bad solutions rather than the good solutions. Conversely the selector would select more of the good solution when the overall candidates in the population are not good. This mechanism maintains the fitness distribution among the candidates in the objective space which we hope that the diversity of the decision space is also maintained.

4. Updating the Generator

In the initialization phase, the joint probabilities h(X_i|X_j) are equally initiated so that the probabilities to be selected are equal. As the generation progresses, the candidates are ranked, good and bad populations are well separated. In this phase, the mutual information indicating the joint probabilities are used to bias the generator in order to generate the desired candidates being closed to the good concepts and avoid generating the undesired candidates being distant to the opposite concepts.

The reward and punishment reinforcement schemes are used to bias the generator. The coincidence found in the top ranks are considered as good building blocks and given more probabilities to be chosen as rewards. On the other hand, the coincidence found in the bottom ranks are considered as bad building blocks and punished by deducting the probabilities to be chosen.

The incremental and detrimental models used in the algorithm are different to the other evolutionary algorithms based on probabilistic models as most of them are represented in binary. The good substructures are usually rewarded by deducted from the bad. If the good is 1 the bad is simply 0 or opposite. In this algorithm, when good and bad coincidences are found, the other coincidences sharing joint probability are affected. The generator updates the good and bad joint probabilities using two different methods.

Reward

When each coincidence X_c,X_r is found in good candidates it is used to update the joint probability h(X_c|X_r) by rewarding the coordinate X_c,_r in the matrix. The coordinate X_c,_r is rewarded by gathering the probability $\frac{k}{{(n - 1)}^{2}}$ from the set X_c,j where j range from 1 to n and k is the coefficient denoting the learning step, and r_c,r is the total number of coincidence X_c,_r counted from the good solution. The reward equation of X_c,r is

Punishment

Contrary to the rewarding, when each coincidence X_c,X_p is found in a not-good candidate it is used to update the joint probability h(X_c|X_p) by punishing the X_c,p in the matrix. The X_c,p is punished by scattering its own probability $\frac{k}{{(n - 1)}^{2}}$ to every member in the set X_c,j where j range from 1 to n and k is the coefficient denoting the learning step, and p_c,p is the total number of coincidence X_c,p counted from the not-good solution. The punishment equation of X_c,p is

Combining together reward and punishment when a coincidence X_c1,c2 is found in both good and not-good solutions we will get:

There is some constraint in updating the generator. Since the joint probability is updated by increasing or decreasing by a constant rate, a joint probability must not become negative. Therefore we need to maintain the probability value by disallow the punishment if it would decrease the probability down below 0.

Fig. 7. the effect of the rewards and punishment to a dependency tree

The effects of reward and punishment are shown in Fig. 7. The Fig 7 (a) shows the dependency X₁|X_j after it has just been initialized. Each of the joint probabilities X₁|X₂, X₁|X₃, X₁|X₄, and X₁|X₅ is initialized as 0.25 uniformly. The Fig 7 (b) illustrates the punishment of X₁|X₅ when the coincidence X₁|X₅ is found in a not-good solution. If the learning step k is equal to 0.2, X₁|X₅ has to scatter its joint probabilities to every node under X₁. As in this case it has to donate 0.05 each to X₁|X₂, X₁|X₃, X₁|X₄, including itself. The Fig 7 (c) presents the way to reward X₁|X₄ by gathering joint probabilities of value 0.05 from each of the members. The Fig 7 (d) shows a result of reward X₁|X₄ and punishment X₁|X₅ at the same time.

Fig.8. Updating the generator k=0.1

Fig. 8 illustrates the process of initializing the generator, generating the first population, selection of good and not-good candidates and finally updating the generator using the selected candidates. The generator is initialized so that each node of the dependency is equally to 0.25. The population is generated from the initiated generator. The candidates are sorted and classified into three classes: high fitness, medium fitness, and low fitness. The high fitness candidates are considered to be the good solutions while the low fitness candidates are considered to be the bad solutions in the population.

As seen in the fig. 8, the candidate [X₂, X₃, X₄, X₁, X₅] is classified as a good solution. The incidences [X₂, X₃], [X₃, X₄], [X₄, X₁] and [X₁, X₅] are used to update the generator as rewards. The candidate [X₃, X₂, X₄, X₁, X₅] is classified as a bad solution thus the incidences [X₃, X₂], [X₂, X₄], [X₄, X₁] and [X₁, X₅] are used to punish the generator in the opposite way. Since the coincidences [X₄, X₁] and [X₁, X₅] are found in both good and not-good solutions, they are counted as a one-time reward and a one-time punishment so the row X_1j and row X_4j remain unchanged. While [X₂, X₃] and [X₃, X₄] are considered to be the coincidences found in the good solutions, hence these coincidences are used to update the row X₂ and X₃. The coincidences [X₃, X₂] and [X₂, X₄] are used to punish the generator as they are found in the not-good solutions.

Moreover, if the representation of the permutation strings can be circulated, the coincidence [X₅, X₂] in the good candidate and [X₅, X₃] in the bad candidate are also needed to update the generator as well.

Fig. 9. The probability dependency tree of a 3 dimensions combinatorial problem

Fig. 9 represents the search space of a 3 dimensional ordering problem. In the generation 0, all joint probabilities are equal. As the generation progresses, the joint probabilities are increased or decreased. It can be seen that some of the connections are weaken as they are statistical found in the bottom ranks. Whereas some of the connections are strengthen as they are found in the top ranks.

Computational Cost and Space Issues

If the problem size is n, and there are m candidates in each generation, the computational cost and space complexity are as follow:

1. Generating the population requires time O(mn²) and space O(mn)

2. Sorting the population requites time O(m log m)

3. The generator require space O(n²)

4. Updating the generator require time O(mn²)

Multi-Objective Coincidence Algorithm

The multi-objective version of coin is slightly different from the single-objective COIN in the selection method. We adopt the non-dominate sorting and clouding distance of NSGA-II[25] as the way to select the population used in updating the generator. Again, we use the not-good solutions to update the generator. The not-good solutions are defined different from the single-objective COIN. They are obtained from the non-dominated frontier of the opposite side of the objectives we are optimizing.

Fig. 10. The non-dominate ranking in Multi-objective Coincidence Algorithm

Fig. 10. shows the non-dominate ranking in Multi-objective COIN. The number of the selected candidates depends on the rank of the frontiers. In this case the first and the second ranks contain 10 candidates, while the last two ranks contain 11 candidates.

The first n^th ranks of the not-good non-dominated solutions are not the same as the last n^th ranks of the good non-dominated solutions. The candidates in the desired and undesired solutions might be overlapped at the extreme ends as can be seen in the Fig.11. The overlapped candidates are considered to be both good and bad, thus the coincidences in the candidates would be used for both reward and punishment.

Fig. 11. The overlapping candidates in between the non-dominate ranking and the inverse non-dominate ranking