Combinatorial Optimization with Coincidence (COIN)

¹

Abstract—Most optimization algorithms that use probabilistic models focus on extracting the information from good solutions found in the population. A selection method discards the below-average solutions assuming that they do not contribute any information to be used to update the models. This work proposes a new single and multi-objective algorithm, Combinatorial Optimization with Coincidence (COIN) that utilization the building blocks in both good and not-good solutions. A Generator represents a probabilistic model of the required solution. The Generator is used to sample candidate solutions. The good solutions give reward values and the not-good solution give punishment values. These values are used to update the Generator. It has been observed that the not-good solutions contribute to avoid producing the bad solutions. The proposed algorithm has been tested with combinatorial problems such as TSP and one application in industrial engineering problem is also demonstrated. The result shows that it is competitive with other probabilistic-model methods.

Index Terms—Multi-Objective Combinatorial Optimization, Permutation, Negative Knowledge, Ordering Schemas, Building Block

INTRODUCTION

"I have not failed, I’ve just found 10,000 ways that won’t work" – Thomas Alva Edison has inspired us all to learn from the failures and find out why we failed. This quote motivates us to invent an algorithm that learns from the mistakes.

Combinatorial optimization is a potential field for application in real world problems including scheduling, timetabling and vehicle route planning problems. A good survey of the state of the art is provided by [1] and [2]. But as far as real world decision making is concerned, it is also well known, that decision makers have to deal with more than one objective. The growth in the interest of theory and methodology of multi-criteria decision making (MCDM) over the last thirty years[3] [4] is well aware.

Surprisingly, multi-criteria or multi-objective combinatorial optimization (MOCO) has not been widely studied. Unfortunately, many methods use either problem-specific or ad-hoc representation codings and operators. Moreover, the performance has not been sufficiently tested on hard problems, leaving the question of how to scales up open.

Apart from the problem-specific solvers, most of the researches rely on either population-based methods (GAs and EAs) or methods of local search (SA, TS and GRASP) or hybridization methods. The population-based methods have an advantage over the local search methods as they usually produce more diversity of solutions whereas the local optimization methods have advantage on the quality of solutions.

The weakness of population-based methods is that the recombination operators are inefficient. Due to the decision space is discrete and the continuity of the permutation space is complex, simple operators are ineffective as they might produce the infeasible solutions. In order to recombine the potential solutions, we need to prevent or repair the infeasible solutions[5]. There are attempts to redesign the GAs specialized for the permutation problems including fmGA[6], and OmeGA[7] to be able to solve various types of the ordering problems. These algorithms are later extended to use in multi-objective ordering problems [8].

This paper develops a new evolutionary algorithm based on probabilistic model called Coincidence Algorithm (COIN). This algorithm is designed specialized for permutation problems based on Markov Chain. The proposed algorithm adopts the negative knowledge to enhance the search by bounding the undesired solutions.

The structure of the paper is as follows. The motivations of the work are discussed in Section II. The proposed algorithm, Combinatorial Optimization with Coincidence, is explained in Section III. Section IV introduces the multi-objective version of COIN. The experiments are reported in Section V. Section VI concludes the work. The potential future works are discussed in the final Section VII.

Motivation

This work extends the proximate optimality principle (POP)[9] and Building Block Hypothesis (BBH)[10][11]. They assume that good solutions share similar structures. The combination of the good building blocks lead to the better solutions. The bad solutions also contain the common substructures which lead to the undesired solutions as well. In most evolutionary algorithm, undesired solutions are usually ignored by the selection process. The knowledge why the non-selected solutions cannot survive is also ignored. This paper we focus on how the bad common substructures help the optimization process to avoid reproducing the bad solutions. Fig 1. illustrates the top rank of the Pareto frontier share the similar substructures in the decision space as well as the last rank of the Pareto frontier also share similar substructures in the decision space.

Fig 1. the similar substructures in the decision space lead to
the similar quality in the objective space.

Negative Knowledge

In 1994, Minsky[12] introduced explicitly the idea of knowing negatively in his literature “Negative Expertise”. He points out that competence often requires one to know what one must do, but it also requires one to know what not to do. Living things more often learn to avoid disaster rather than how to succeed in order to survive. In the process of learning, even experts seem to have negative rather than positive goals, namely that we seem to learn what should not be done. Minsky also states that the creativity of the machine does not only come from the randomization, but also come from the reduction of the search space. The performance of a smart or creative problem-solver is not how many trials precede a success, but how few. So the secret lies not in disorderly search, but in pre-shaping the search space so as reduce the numbers of useless attempts.

In 2006, Parviainen and Eriksson[21] extended Minsky’s idea. They further characterize the negative knowledge by identifying four features of negative knowing as follows:-

1. to know what one does not know: experts are usually aware of their own competence, but they must also know what they do not know and what they should know

2. to know what not to do: experts must know both how to achieve goals and how to avoid disasters, namely ‘learning what not to do’

3. unlearning and bracketing knowledge: experts may get into a situation when they have to give up some parts of their knowing and ‘unlearn’ or ‘bracket’ their skills and know-how

4. failures and mistakes: experts should also regard the value of failures and disappointments as emotions, as well as recognize the creativity that emerges from making mistakes

Apart from the negative knowing, they also argue that negative is not considered as the mere empty opposite to the positive. They purpose that positive and negative knowledge can be considered as independent areas, which overlap one another in the following way:

TABLE I

Linking Positive and Negative Knowledge[]

In 2005, the concept of opposition-based learning (OBL)[13] has emerged. Tizhoosh introduces the idea of learning toward the opposite states, opposite weights, opposite actions and many more opposition ways. The secret behind OBL is the simultaneous consideration of an estimate and its corresponding opposite estimate in order to achieve a better approximation of the current candidate solution. The opposition-based learning has been successfully applied to accelerate reinforcement learning[14], back propagation learning[13], and differential evolution[15].

OBL algorithms are considered to be utilizing of the negative knowledge to accelerate the optimization process. However the opposition-based extension idea of genetic algorithm is still too far from the negative knowledge. The anti -chromosome with inverted sub mutation can partially describe some of the negative information. The negative concept of a binary representation of a sub-chromosome [*101*] is not as simple as [*010*]. The complete negative concept should includes [*001*], [*011*], [*100*], [*110*] and [*000*] as well. This example indicates that the size of the negative concept in probabilistic-based learning is unimaginable large compared to the positive one.

Artificial immune systems (AIS) are computational systems inspired by the principles and processes of the vertebrate immune system. The algorithms typically exploit the immune system's characteristics of learning and memory to solve a problem. The negative selection techniques[16] in AIS try to output the complementary concept of the real target concept. Algorithms in this class are used in many areas including classification and optimizations.

There are some works that try to utilize the negative knowledge hidden in the below average solutions by applying classification techniques in optimization. In 2000, Michalski[17] proposed an algorithm called Learnable Execution Model (LEM) that applies classifiers to develop a population of solutions. The candidates of a population are divided as the fittest and the less fitted ones. Then the characteristics of the good ones are strengthened while bad ones are avoided. Later in 2003, Llorà and Goldberg[18] proposed an algorithm that combined the Induction of Decision Tree (ID3) and evolutionary algorithm using statistical approaches. In 2004, Miquelez, Bengoetxea, and Larrañaga[19] introduced a new estimation of distribution algorithm based on Bayesian classifiers called Evolutionary Bayesian Classifier-Based Optimization Algorithm (EBCOAs) and later extended in the continuous optimization domains[20].

Schema Theorem and Negative Schema

The Schema Theorem is defined by Holland[10] represented a mile stone in the development of Genetic Algorithms. In schema theorem, the search space is partitioned into subspaces of varying levels of generality, and mathematical models are constructed which estimate how the number of individuals in the population belonging to certain schema can be expected to grow in the next generation. From this model, Goldberg arose the building block hypothesis (BBH), which attempted to explain how a GA solves a problem by positing that near optimal solutions were forged from small, low-order, better-than-average schemata.

In 2006, Tae and Lee[22] prove that a negated concept is defined implicitly by a hidden feature abstracted from the property common to all the objects not belonging to the concept. This paper proposes based on Minsky that there is a logical schema that enables an agent to perceive a negated concept. However, the negative schema of Kang Soo and Samual is defined based on an assumption in which an agent can recognize only one concept at a time. They also state that the positive and negated concepts, exist together, and two concepts cannot be recognized at the same time.

Order Schema

In 1992, Kargupta[5] et al discussed about schemata in permutation problems, the so called order schema or o-schema is defined by assigning a sequence characteristic to a similarity subset. It has unique alleles at all of its fixed positions and contains all permutations of other alleles at don’t care positions. In general, an o-schema can be classified into two broad categories – absolute ordering schema and relative ordering schema.

The absolute o-schema defines a similarity subset having some common allelic position characteristics. For instance, the absolute o-schema [ ! ! ! 1 ! 8 ! ! ] defines the subset of all valid permutation string that have alleles 1 and 8 in fourth and sixth positions respectively. The string S₁ = [ 4 3 2 1 5 8 7 6 ] is contained in the schema, while S₂ = [ 1 5 8 2 4 3 5 6 7 ] is not contained in the schema. This schema representation is useful in the problems where the placement of certain position is important. In this type of schema, both ordering and position of the defined alleles are important.

TABLE II

A Comparison of Some Statistics for Binary,L-ary and size-L Permutation Problems[]

	Binary	l-ary	Size-l permutation
Solution Space	2l	ll	l!
String in an order o(H) schema	2l-o(H)	ll-o(H)	(l-o(H))!
Number of o(H) schemata	2o(H)	lo(H)	Pm(l,o(H))
Total schemata	3l	(l + 1)l

The relative o-schema defines a similarity subset having some common order allelic characteristics which in between the order there can be some gap containing any size of the permutation substring. For example, the relative o-schema [ ! ! ! 1 ! 4 ! ! ] represents the subset of all valid permutation string that have allele 1 happens before 4 in any configuration without having any restriction on the specific allelic position of genes. This coding is important for problems where ordering among alleles is the only matter.

There might be confusing between the definition of the relative o-schema defined in 1989[11] which allow only the fixed distance between the defined schemata. For example, the strings containing 4 placed after 1 with in a fixed size of gap. In this paper, we will call the relative o-schema proposed in 1989 as type I relative o-schema and the one proposed in 1992 as type II relative o-schema.

According to the Table II, The o-schemas reduce more space compared to the binary schemas. Let [ * * 1 * * ] be a binary schema, there would be only 16 strings in the order 1 schema which is 1/2 of the solution space. While an absolute o-schema [ ! ! 1 ! ! ] reduce the solution space down from 120 to only 24 strings. The larger the problem size, the greedier the o-schema reduces the search space.

The even greedier example can be illustrated in Fig 2. The Fig 2 shows scaled spaces bounded by the o-schema and the more specific o-schema compared to the whole search space. Let [ ! 3 5 ! ! ] be a type I relative o-schema which allow only the string containing 5 placed after 3 with no gap. The solution space would reduce from 5! down to 4!. Which is equal to 5!/5. As generation progressed, the even more specific o-schema [ ! 3 5 1 ! ] dominates the population. The solution space is reduced down to 3! or 5!/(3*4).

Fig 2. Solution space reduced by more specific relative o-schema.

Negative Order Schema

In this work, we purpose a way to recognize negative schema in the ordering problems and show the role of the negative schema in search and optimization.

In most evolutionary algorithms, the positive schemas usually dominate the population and assume that the solutions in the inverse set of the schema are negative due to the selection process filters the less fitted solutions. Thus the strings that are not contained in the schema are extinct especially in the ordering problems; the strings satisfied by the schema are not easy to regenerate by chance. The search and optimization procedure might be stuck in some local peaks. Moreover, some of the multimodal and multi-objective solutions might be missing. These problems are well aware therefore many researches try to preserve the diversity and elitist in order to explore more in the uncovered searching areas and prevent the extinction of solutions in the uncovered space.

Negative o-schemas play a different role compared to the positives. They are used to void the search space rather than to limit the search space. The more specific schemas void less space than the general ones as can be seen in Fig 3. The negative o-schemas are defined using a “~” in front of the positive o-schema. For example ~[ ! 3 4 ! ! ] is a type I negative o-schema that void the search space from the string containing in the negative schema. The search space after voiding is reduced down from 5! to 5!-4!. Therefore the remaining space is greater than the space bounded by the positive schema with the equally order. In addition, the more specific negative schemas reduce less space compare to the more general ones as the negative o-schema ~[ ! 3 4 2 ! ] reduce the space from 5! To 5!-3!.

The positive schemas dominated by the selected solution seen so far, thus the uncovered peaks that have not been found in the previous generation were not considered. Most algorithms assume that the unseen solutions are not desirable.

In contrast, if the negative schemas are identified by the solution seen so far in the very beginning generations, the remaining spaces apart from the set of the strings contained in the negative schemas are left to be explored. This mechanism enhances the preserving of solutions in the unseen space.

Fig.3 Solution space reduced by more specific
negative relative o-schema

Fig. 4 illustrates the behavior of the positive and the negative o-schemas. Let [ ! 3 5 ! ! ] be a positive o-schema which dominate the population by the good solutions seen so far. It might ignore the white circle peak solutions in the unseen space. On the other hand, the negative o-schema defined by ~[ ! 3 4 ! ! ] is identified by the undesired solutions, thus can be used to void only the undesired areas retaining all the peaks to be explored.

Fig 4. Behavior of positive and negative schemas in problems with multiple peaks or multiple objectives

Combining Positive and Negative Order Schema

In most evolutionary algorithms, the schemas are kept in a form of the selected population. Thus the knowledge of which schemas are likely to form the bad solutions, are thrown away with the non-selected population. The evolutionary process repeats searching for the more specific schema within the bounded area assuming that the solutions in the uncovered search space would not be able to survive. The solutions in the uncovered area are composed of the unknown to the positive area and known negative area.

Vice versa, the negative schemas void the search space and left behind the uncovered area that composed of unknown quality solutions and the positive known solutions.

In theory, the negative concepts should be the complement of the positive concepts. However, it is impossible to identify the positive and the negative concepts without verifying all of the solutions in the space. The learning process starts from the unknown space. As the learning progresses, the solutions are verified and classified.

Utilizing the positive and negative schemas together we need to distinguish between the good and the bad schemas. So that the solutions left behind the good and the bad are in the unknown state, therefore the selection methods also need to distinguish between the good solutions, the bad solutions and the solutions that might contain both positive and negative schemas.

Fig 5. The classification of the solution in the space

According to the negative knowledge defined by Parviainen and Eriksson, the negative cannot be considered to be the complement of the positive due to the space contain not only the known positive and known negative but also contain the unknown.

In order to utilize the negative knowledge in learning, we need to utilize four feature of the negative knowing. First of all we need to categorize the solutions in to two categories as known and unknown. Moreover, the known solutions are also divided in to positive and negative as can be seen in Fig 5. This enable the algorithm to distinguish between what is known and what is not known.

The algorithm should be able to identify the negative schemas in order to pre-shape the search space and try not to waste the function evaluation with the expected undesired solutions. Thus, we need a data structure to keep the state of schema.

Moreover, the solutions found in the good solutions might contain the same schemata found in the bad solutions or vice versa, which can be classified as false positive or false negative. Thus, the algorithm should be able to justify the gained knowledge and should be able to unlearn or bracket the knowledge back to unknown information or re-classify or re-justify the old beliefs.

Coincidence Algorithm

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, that is closest to the empirical distribution of the set of selected points when using the Kullback-Leibler distance, where

()

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.

{#section .list-paragraph}

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 :-

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 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

(2)

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 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

(3)

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

(4)

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

Experiment

Travelling Salesman Problems

To measure the performance of COIN, we perform several benchmarks on TSP problems and compare them to the experiment of Robles and Larrañaga [26]. We aim to measure the performance of the algorithm in two main aspects: quality of the results and the number of function evaluations. This paper we show the result of the well known Gröstel24, Gröstel48 and Gröstel120. These can be obtained from the TSPLIB [43].

The experiments of Robles and Larrañaga use both of the discrete and continuous EDAs in the following learning methods: UMDA [27], MIMIC, TREE [28], EBNA [29], UMDA_c, and MIMIC_c,, EGNA [30] and EMNA [31]. Moreover we compare the results with GA in the literature of Larrañaga [32] in 1999 which uses GENITOR [33] algorithm. For each of the combinations shown in the experiment, we perform 10 runs and average the results.

1. Gröstel24

TABLE III

Tour length for the Gröstel24 problem

* Size of population 200, mutation used SM

unif denotes uniform selection with learning step k = 0.1

adpt denotes adaptive selection with learning step k = 0.1

Optimum 1272

However the TSP coding for continuous EDAs in the original literature uses real numbers which later sorted into the ordering path based on these numbers, is known to be a poor alternative coding compared with path representations based on permutations. Thus the results from continuous EDAs are not compared in this paper due to the use of different representations. Moreover, the detail of local search in the literature is limited to us, thus the result of COIN incorporate with local search cannot be compared.

Table III shows the best results and average results obtained for each of population size, with and without local optimization and learning type of EDAs. The table also shows results obtained for the GA using the crossover operators ER and OX2. The results show that COIN with adaptive selection can find the optimum of Gröstel24 without the need of local optimizer and it is competitive with all the EDAs in the experiment.

TABLE IV

Number of Generations for the Gröstel24 problem

Table IV illustrates the number of the generation used to find the solutions. Again the result shows that COIN is competitive in the larger population size.

Fig 12 shows the convergence of the Gröstel24 problem using only good solutions, only not-good solutions and using both types. It shows that the use of both good and not-good solutions outperform the use of only good or bad solutions. Learning from not-good solutions creates more variety amongst the best results but retaining the average results.

Fig 12. the best candidates generated from the generator for Gröstel24

In this experiment, we rather use the adaptive selection as it is the parameter less approach. According to the Fig 13, in some generation there is no reward given to the good coincidence as overall fitness are high. In order to maintain the fitness distribution, the selector rather selects more of the bad individual than the good. When some generations contain more of the bad solution, the selector rather give more reward than punishment.

Fig 13. the number of good and bad selected solution for Gröstel24

2. Gröstel48

The results for the Gröstel48 are shown in Table V and VI. COIN sacrificing more generations for a better solution compared to the other discrete EDAs.

TABLE V

Tour length for the Gröstel48 problem

* Size of population 200, mutation used SM

** Learning step k = 0.12, Adaptive Selection

Optimum 5046

TABLE VI

Tour length for the Gröstel48 problem

3. Gröstel120

Table VII and VIII show the results of the Gröstel120 problem, Again the COIN algorithm perform better results compared to the rest discrete EDAs.

TABLE VII

Tour length for the Gröstel120 problem

* Learning step k = 0.14, Adaptive selection

Optimum 6942

TABLE VIII

Tour length for the Gröstel120 problem

4. KroAB100

To study the effect of reward and punishment of good and bad instances in multi-objective problems, the multi-objective COIN is tested in a multi-objective TSP problem. We setup an experiment using kroa100 and krob100 as a bi-objective 100 tours TSP problem obtained from the TSPLIB. The population size we used in the experiment is 250 and the learning step k is equal to 0.1. Then we took some snapshots at the number of generations equal to 100 and 500 respectively. The behavior of the algorithm can be seen in Fig. 14 and Fig 15.

Fig. 14. the population clouds in a bi-objective kroa/b100 TSP

Fig. 14 shows the population in the generation 1, 100 and 500 respectively. The population migrates towards the optimum fitness area as the generation progresses.

Fig. 15 the parato frontier obtained from different generation and updating method in a bi-objective kroa/b100 TSP

Fig. 15 shows the effect of COIN algorithm in using only rewarding and only punishment compared with using both. Two curves at the upper-right hand corner are the result from using only reward or punishment for 500 generations. Contrast this with the rest of the curves in the lower-left corner which use both reward and punishment together for 100 and 500 generations. The use of both reward and punishment for just 100 generations outperforms the result from using only either one for 500 generations.

However, the result of KroAB100 of COIN cannot be compared with the hybrid algorithms compared by Kumar and Singh[34] as the Pareto set obtained from COIN is worse in both quality and quantity.

Multi-objective Workers Allocation in U-shaped Assembly Lines in JIT Production Systems Problems

To measure more of the performance of multiple-objective COIN, we perform benchmarks on real world applications. COINs have been successfully apply to both U-shaped assembly line balancing and sequencing[35] as the result of balancing can be seen in the first international debut in CEC’09.[36] COINs outperform NSGA II in both class of problems.

The paper, the experiments are carried on the multi-objective workers allocation problems in U-shaped assembly lines in JIT production systems.

The workers allocations in U-shaped assembly line are considered to be NP-Hard constraint problems. This kind of assembly line has advantage in reduction of the waste walking time to switch from workstation to workstation, thus enhance reduction of employee and cost.

Fig. 16. The precedence diagram with assembly network (Jackson 1956).

Fig. 16 illustrates the Jackson’s problem[37] with 11 tasks. Given each workstation ws = 1 to m , number of tasks i = 1 to n , each task uses time t_i. The total time used in the fig. 16 is equal to 10 while it used up to 14 if the line is straight.

Fig. 17. Completed line assignment for straight assembly line.

Fig. 18. Completed line assignment for U-shaped assembly line.

After fitting the tasks and workstations in to the assembly line, we can see that the U-shaped assembly line in the Fig. 17 use one less workstation than the straight line in the Fig. 18. As the employee who processes the task number 1 can be shared with the task number 11.

We carry experiments based on ten well-known problem sets [38][39][40][41][42][43] as shown in Table IX. The first and second columns show the author of the problem and the number of tasks, respectively. The third, fourth and fifth columns display the fixed number of tasks at the front, back and side lines. The number of selected different cycle times (s), i.e. minimum, medium and maximum values, for each set is given in the sixth column. In the seventh column, a number of product models that produce one quantity for each model are shown. However, average time is represented in mixed models. Clearly, in this experiment, the sequencing problem is not taken into account.

Illustrative characteristics of a single U-line in this research that describe the worker allocation problem (workers are assigned to machines) are shown in Fig. 19. No automated processing machines identified with grouped tasks are located on a U-shaped assembly line.

In the algorithm the following notation is used:

Fig.19. Mapping a diagram of a single U-shaped assembly line for

j workers and k machines on grid arrangement.

Three performance criteria are taken into consideration. Hierarchically, the number of workers or workstations, deviation of operation times of workers and walking time are minimized simultaneously. In order to maximize line efficiency, it is essential to decrease the number of workers. By the minimization of DOW, it is necessary to reduce workload difference between workers and to distribute these workloads to workers as equally as possible. The minimization of WT is also considered to save the space needed for the possible size of a U-shaped line and shorten the distance for communication between workers. Consequently, the three criteria are:

1. minimize the number of workers (m);

f₁(X) = m (1)

2. minimize the Deviation of Operation times of Workers (DOW)

f₂(X) = DOW = (2)

Operation Time (C_jk) = Walking Time (WT_jk) + Manual Time (T_jk)

(U-Worker Balancing) (U-line Balancing)

3. minimize the Walking Time (WT)

f₃(X) = WT = (3)

These experiments under the problem sets from seven to two hundred and ninety-seven tasks are compared between NSGA-II and COIN in four aspects:

1. Convergence to the Pareto-optimal set

2. Spread of non-dominated solution

3. Ratio of non-dominated solution

4. Processing time

The exemplified results of Miltenburg’s 10-task problem from Table I are calculated and shown in Table X.

TABLE X

An example of worker allocation in Miltenburg’s 10-task
single U-line problem

The objective functions of m, DOW and WT are 5 workers, 3.58 and 15 time units by eq. 1-3, respectively.

In order to demonstrate the effectiveness of the proposed approach, computational results are obtained on a set of single U-shaped assembly line worker allocation problems with multiple objectives filled in the gaps missing from previous studies.

Finally, each of the worker allocation problems minimizing m, DOW and WT simultaneously is exemplified in the same way by the solution of Miltenburg’s 10 tasks at a local optimal string with orthogonal walking distance as shown in Fig. 20 and Table XI. However, the final Pareto-optimal frontier consists of many strings that minimize the number of workers and show several pairs of DOW and WT.

Fig.20. An example of worker allocation at Miltenburg’s 10 tasks layout

TABLE XII

NSGA-II with displacement for worker allocation
at the side ratio of 1:1 (1/3)

* Minimum cycle time (5,755) is less than the operation time of 6,615. Thus,

the feasible minimum cycle time from the data sets of UALBP-I is replaced.

** One local optimal solution (or one coordinate) on the DOW and WT

For given cycle times, this research aims to study at most three values of each problem with the minimum, middle and maximum values. Walking distance is calculated with displacement. It is assumed that one walking time unit is equivalent to one walking distance unit. To validate the feasibility of workers (workstations), experimental results are compared with ULINO data sets available from Homepage for Assembly Line Optimizing Research[44]. Both algorithms are programmed by using MATLAB R2008a, and the set of test problems are solved on an AMD Athlon^TM 64 Processor 3500+ 2.21 GHz PC with 960 MB DDR-SDRAM. All numbers of workers are feasible and most are the same as shown in Table XII and XIII. The italic number of workers display the building block of memorized adjacent tasks of COIN makes workers smaller than the randomized assignment tasks of NSGAII.

Since the solutions in the global Pareto set are not known, we cannot benchmark the algorithm using IGD. The better algorithm should provide the convergence and spread of the solution closer to zero and the ratio closer to one. COIN seems to perform better than NSGA-II for most problem sets between Columns in the Table XII-XIII. Furthermore, in terms of CPU time in the last column, the multi-objective COIN is much faster than NSGA-II. The comparison of them for Scholl and Klein’s 297 tasks at the cycle time of 2,787 time units is exemplified. Some of the final Pareto set are shown in Fig. 21 to Fig. 30 which is range from the smallest problem to the largest problem.

TABLE XIII

COIN with displacement for worker allocation
at the side ratio of 1:1 (1/3)

Conclusion

In this paper, we introduce a new optimization algorithm involving negative knowledge contained in the non-selected solution. Moreover, we developed a new algorithm named COIN which supports the four features of negative knowledge proposed be Paviainen and Eriksson. COIN identifies partial building blocks in type I relative order schema then composes them using condition probability. The single objective COIN has been benchmarked with several TSP problems and the results show that it is competitive with other discrete EDAs. The multi-objective COIN has been benchmarked against NSGA-II in the worker allocation problem in U-shaped Assembly Lines. The overall results state that COINs outperform NSGA-IIs in most problems.

Fig.21. Comparison of NSGA-II vs COIN for the Merten’s 7-task problem

Fig.22. Comparison of NSGA-II vs COIN for the Miltenburg’s 10-task problem

Fig.23. Comparison of NSGA-II vs COIN for the Jackson’s 11-task problem

Fig.24. Comparison of NSGA-II vs COIN for the Thomopoulos’s 19-task problem

Fig.25. Comparison of NSGA-II vs COIN for the Heskiaoff’s 28-task problem

Fig.26. Comparison of NSGA-II vs COIN for
the Kilbridge & Wester’s 45-task problem

Fig.27. Comparison of NSGA-II vs COIN for the Kim’s 61-task problem

Fig.28. Comparison of NSGA-II vs COIN for the Tongue’s 70-task problem

Fig.29. Comparison of NSGA-II vs COIN for the Arcus’s 111-task problem

Fig.30. Comparison of NSGA-II vs COIN for
the Scholl & Klein’s 297-task problem

Discussion

Fig.31. Population Cloud of NSGA-II vs COIN for
KroAB100 TSP bi-objective problem

COIN has been shown to be a competitive algorithm in many real world multi-objective ordering problems[35][36]. However, the result of COIN is still far from the optimal set compared to [34]. Fig 31. Show the population of COIN and NSGA-II in KroAB100 in the experiment A.4. From the figure, COIN tries to evolve toward the two objectives by composing the building blocks obtained from the positive samples and avoid producing the solutions containing bad building blocks. Somehow, COIN ignores the production of the solution in the extreme ends. The reason might be the building blocks at the extreme ends are in conflict to each other or the building blocks of the problem are in the absolute order or the linkage between building blocks are significantly far apart to be learned by the first order matrix. NSGA-II might not be as efficient as COIN in exploitation of the building blocks, but it maintains the diversity among the population in both two objectives as it utilizes the advantage of elitists. The future research might be extending the COIN algorithm to support more variety of the schema or a hybrid algorithm that combines the advantage of both COIN and NSGA-II.

ACKNOWLEDGMENT

The authors thank to P. Olanviwitchai, N. Kampirom, and P. Pinkoompee for their verification and validation of encoding and programming. We are also grateful to G. K. Rogers for partial proofreading.

REFERENCES

1. M. Ehrgott and X. Gandibleux, “A survey and annotated bibliography of multiobjective combinatorial optimization” in OR Spektrum, 2000 22:425-460.

2. J.A. Diaz (1978) “Solving multiobjective transportation problems”. Ekonomicko Mathematicky Obzor 14:267–274.

3. R.E. Steuer,Gardiner LR,Gray J (1996) “A bibliographic survey of the activities and international nature of multiple criteria decision making”. Journal of Multi-Criteria Decision Analysis 5:195–217.

4. D.J. White (1990) “A bibliography on the application of mathematical programming multiple-objective methods”. Journal of the Operational Research Society 41(8):669–691.

5. H. Kargupta, K. Deb, and D.E. Goldberg (1992) “Ordering genetic algorithms and deception”. Parallel Problem Solving form Nature, 2:47-56.

6. D.E. Goldberg, K. Deb, H. Kargupta, and G. Harik (1993) “Rapid, accurate optimization of difficult problems using fast messy genetic algorithms”. Procedding of the Fith International Conference on Genetic Algorithms, 56-64.

7. D. Knjazew and D.E. Goldberg (2000) “OmeGA – Ordering Messy GA : Solving Permutation Problems with the Fast Messy Genetic Algorithm and Random Keys” IlliGAL Report No. 2000004

8. D.A.V. Veldhuizen and G.B. Lamont (2000) “Multiobjective evolutionary algorithms: Analyzing the state-of-the-art” Evolutionary Computation . MIT Press

9. F. Glover and M. Laguna. “Tabu Search”. Kluwer Academic Publishers,

1998.

10. J. H. Holland (1975). “Adaptation in Natural and Artificial Systems”. Ann Arbor, MI: The University of Michigan Press.

11. D. E. Goldberg (1989). “Genetic Algorithms in Search, Optimization, and Machine Learning”. Reading, MA: Addison Wesley.

12. M. Minsky (1994). “Negative Expertise”, International Journal of Expert Systems 7

13. H.R.Tizhoosh, (2005) “Opposition-Based Learning: A New Scheme for Machine Intelligence”. Proceedings of International Conference on Computational Intelligence for Modelling Control and Automation - CIMCA'2005, Vienna, Austria, vol. I, pp. 695-701.

14. H.R.Tizhoosh, (2005) “Reinforcement Learning Based on Actions and Opposite Actions”. ICGST International Conference on Artificial Intelligence and Machine Learning (AIML-05).

15. S.Rahnamayan, H.R.Tizhoosh, M.M. Salama, (2006) “Opposition-Based Differential Evolution Algorithms”, IEEE Congress on Evolutionary Computation proceeding 2006 (WCCI 2006)

16. Z. Ji and D. Dasgupta (2007) “Revisiting Negative Selection Algorithms”. Evolutionary Computation. Vol. 15, No. 2, Pages 223-251 MIT Press

17. R.S. Michalski (2000): "Learnable execution model: Evolutionary

processes guided by machine learning". Mach.Learn., Vol. 38, pp. 9-40.

18. X. Llorà X. and D.E. Goldberg (2003): "Wise Breeding GA via Machine

Learning Techniques for Function Optimization". Proc. Genetic and Evolutionary Computation Conference GECCO-03

19. T. Miquélez, E. Bengoetxea, P. Larrañaga (2004) “Evolutionary computation based on Bayesian classifiers”. International. Journal of Applied Mathematics and Computer Science, 14(3), 101-115.

20. T. Miquelez, E. Bengoetxea, A. Mendiburu, P. Larrañaga (2007) “Combining Bayesian classifiers and estimation of distribution algorithms for optimization in continuous domains”. Connection Science, 19(4), 297-319.

21. J. Parviainen and M. Eriksson.(2006) “Negative knowledge, expertise and organizations”. Int. J. Management Concepts and Philosophy, Vol.2, No.2.

22. K.S. Tae and S.S. Lee (2006) “On cognitive role of negative schema”. Lecture Notes in Computer Science, 2006 Springer.

23. C. Andrieu et al. (2003)“An introduction to MCMC for machine learning”, Machine Learning, 50, 5-43.

24. De Bonet, J.S., Isbell, C.L., and Viola, P. (1997) “MIMIC: Finding Optima by Estimating Probability Densities”. Advance in Neural Information Processing Systems, volume 9.

25. K. Deb, A. Pratap, S. Agrawal, and T. Meyarivan.(2002) A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6, 2(April 2002) 182-197.

26. Robles V. and Larrañaga P.(2006) Solving the Traveling Salesman Problem with EDAs. In Estimation of Distribution Algorithm: A New Tool for Evolutionary Computation.

27. Mühlenbein, H. (1998) “The Equation for Response to Selection and Its Use for Prediction”. Evolutionary Computation, 5:303-346.

28. Chow, C. and Liu, C.(1967) “Approximating Discrete Probability Distributions with Dependency trees”. IEEE Transactions on Information Theory, 14:462-467. (1967)

29. Etxeberria, R. and Larranga, P.(1999) “Global Optimization with Bayesian Networks”. In II Symposium on Artificial Intelligence. CIMAF99. Special Session on Distributions and Evolutionary Optimization, pages 322-339. (1999)

30. Larrañaga, P., Etxeberria, R., Lozano, J. A., and Pena, J.M.(1999) “Optimization by Learning and Simulation of Bayesian and Gaussian Networks”. Technical Report. KZZA-IK-4-99, Department of Computer Science and Artificial Intelligence, University of the Basque Country.

31. Larrañaga, P., Lozano, J. A., and Bengoetxea, E.(2001) “Estimation of Distribution Algorithms Based on Multivariate Normal and Gaussian Networks”. Technical Report KZZA-IK-1-01, Department of Computer Science and Artificial Intelligence, University of the Basque Country.

32. Larrañaga, P., Kujipers, C.M. H., Murga, R.H., Inza, I., and Dizdarevic, S.(1999) “Genetic Algorithms for the Travelling Salesman Problem: A Review of Representations and Operators”. Artificial Intelligence Review, 13:129-170.

33. Whitley, D., Starkweather, D., and Fuquay, D.: Scheduling Problems and Travelling Salesman(1989) “The Genetic Edge Recombination Operator”. Proceedings of the International Joint Conference on Artificial Intelligence, pages 133-140. Morgan Kaufmann Publishers

34. R.Kumar and P.K. Singh (2007) “Pareto Evolutionary Algorithm Hybridized with Local Search for Biobjective TSP”. Studies in Computational Intelligence Vol 75.pp.361-389.

35. P. Chutima et al (2008)“Application of Combinatorial Optimization with Coincidence for multi-objective sequencing problems on mixed-model U-lines in JIT production systems” Proceeding Kasetsart Conference 2008 (Thai Version)

36. W. Wattanapornprom et al (2009) “Multi-objective Coincidence Algorithm”, IEEE Congress on Evolutionary Computation proceeding 2009

37. Jackson, J.R.(1956) A Computing Procedure for a Line Balancing Problem. Management Science. Vol. 2,No.3: pp.261-271.

38. J. Miltenburg, (2001) “One-piece flow manufacturing on U-shaped production lines: a tutorial”, IIE Transactions, vol. 33, pp. 303-321, 2001.

39. R. K. Hwang, H. Katayama, and M. Gen, (2008) “U-shaped assembly line balancing problem with genetic algorithm” International Journal of Production Research, vol. 46, no. 16, pp. 4637-4649.

40. G. R. Aase, J. R. Olson, and M. J. Chniederjans, "U-shaped assembly line layouts and their impact on labour productivity: An experimental study," European Journal of Operational Research, vol. 56, pp. 698-711, 2004.

41. J. Miltenburg, (2001) “U-shaped production lines: A review of theory and practice,” International Journal of Production Economics, vol. 70, pp. 201-214.

42. J. P. Shewchuk, (2008) “Worker allocation in lean U-shaped production lines” International Journal of Production Research, vol. 46, pp. 3485-3502.

43. TSPLIB,http://www.iwr.uni-heidelberg.de/groups/comopt/software/

TSPLIB95/ (retrieving on August 18^th, 2008)

44. Homepage for Assembly Line Optimizing Research, http://www.assembly-line-balancing.de/ (retrieving on July 15^th 2009)