Chapter 2: Motivation

Chapter 2: Motivation

Schema Theorem

POP and BBs

Negative Knowledge

Negative Schema

Opposition based learning

CHAPTER 2

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.

Schema Theorem POP and BBH

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.

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

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

Negative Schema

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.

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

Opposition Based Learning

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.

Etc

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

Combining Positive and Negative Order Schema

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.

Summary