Open access

Interactive Genetic Algorithms with Individual’s Uncertain Fitness

Written By

Dun-wei Gong, Xiao-yan Sun and Jie Yuan

Published: 01 October 2009

DOI: 10.5772/9605

From the Edited Volume

Evolutionary Computation

Edited by Wellington Pinheiro dos Santos

Chapter metrics overview

2,186 Chapter Downloads

View Full Metrics

1. Introduction

Interactive genetic algorithms (IGAs), proposed in mid 1980s, are effective methods to solve an optimization problem with implicit or fuzzy indices (Dawkins, 1986). These algorithms combine traditional evolution mechanism with a user’s intelligent evaluation, and the user assigns an individual’s fitness rather than a function that is difficult or even impossible to explicitly express. Up to now, they have been successfully applied in many fields, e.g. face identification (Caldwell & Johnston, 1991), fashion design (Kim & Cho, 2000), music composition (Tokui & Iba, 2000), hearing aid fitting (Takagi & Ohsaki, 2007).

The obvious character of IGAs, compared with traditional genetic algorithms (TGAs), is that the user assigns an individual’s fitness. The user compares different individuals in the same generation and assigns fitness based on their phenotypes through a human-computer interface. The frequent interaction results in user fatigue. Therefore, IGAs often have small population size and a small number of evolutionary generations (Takagi, 2001), which influences these algorithms’ performance to some degree and restricts their applications in complicated optimization problems. Accordingly, how to evaluate an individual and express its fitness becomes one of the key problems in IGAs.

Since user fatigue results from the user’s evaluation on an individual and expression of its fitness, in order to alleviate user fatigue, a possible alternative is to change the approach to express an individual’s fitness. The goal of this chapter is to alleviate user fatigue by adopting some appropriate approaches to express an individual’s fitness.

An accurate number is a commonly used approach to express an individual’s fitness. As is well known, the user’s cognitive is uncertain and gradual, therefore the evaluation of an individual by the user and the expression of its fitness should also be uncertain and gradual. It is difficult to reflect the above character if we adopt an accurate number to express an individual’s fitness.

We will present two kinds of uncertain numbers to express an individual’s fitness in this chapter, one is an interval described with the lower limit and the upper limit, the other is a fuzzy number described with a Gaussian membership function. These expressions of an individual’s uncertain fitness well accord with the user’s fuzzy cognitive on the evaluated object.

In addition, we will propose some effective strategies to compare different individuals in the same generation on condition of an individual’s uncertain fitness. We will obtain the probability of an individual dominance by use of the probability of interval dominance, and translate a fuzzy number into an interval based on α -cut set. We will determine the dominant individual in tournament selection with size being two based on the probability of an individual dominance.

We will apply these proposed algorithms to a fashion evolutionary design system, a typical optimization problem with an implicit index, and compare them with a traditional interactive genetic algorithm (TIGA), i.e. an interactive genetic algorithm with an individual’s accurate fitness (Gong et al., 2007), to show their advantages in alleviating user fatigue and looking for user’s satisfactory individuals.

In the next section, we will review some related work on methods to alleviate user fatigue, and some basic knowledge on interval analysis as well as fuzzy numbers. The emphasis of this chapter is section 3 and 4 where we will present an IGA with an individual’s interval fitness and an IGA with an individual’s fuzzy fitness. Their applications in a fashion evolutionary design system and some experimental results are given in section 5. Finally, we will draw some conclusions and provide possible opportunities for future researches in section 6.

Advertisement

2. Related work

2.1. Approaches to evaluate individuals

Generally speaking, there are two approaches to evaluate an individual. One is that the user directly evaluates an individual based on his/her preference, e.g. Takagi proposed a fitness assignment method which combines a continuous fitness with a discrete one (Takagi & Ohya, 1996). The other is that surrogate-assisted models evaluate a part of or even all individuals in some generations, e.g. Sugimoto et al. presented a method to estimate an individual’s fitness using fuzzy logic based on the distance and the angle between the evaluated individual and the optima being found (Sugimoto & Yoneyama, 2001). Biles and Zhou et al. adopted neural networks (NNs) to learn the user’s intelligent evaluation, and the number of individuals being evaluated by the user decreases by use of NNs evaluating an individual in an appropriate time (Biles et al., 1996)( Zhou et al., 2005). In order to improve learning precision and reduce network complexity, we ever adopted multiple surrogate-assisted models (Gong et al., 2008), in which a single surrogate-assisted model only learns the user’s evaluation in a part of the search space. Wang et al. transformed the user’s evaluation into an absolute rating fitness and adopted it to train a support vector machine (SVM) to evaluate an individual (Wang et al., 2006). Hao et al. did it based on “the fitness” of a gene sense unit (Hao et al., 2006). The common character of the above methods is that an accurate number expresses an individual’s fitness.

In order to conveniently understand the proposed algorithms, we will introduce some basic knowledge on interval analysis and fuzzy numbers.

2.2. Interval analysis

Interval analysis is the mathematic foundation of this chapter. Therefore, we introduce some definitions of interval analysis in this subsection.

Interval (Liu, 2005) For any x _ x ¯ R and x _ x ¯ , a set X satisfying X [ x _ x ¯ ] = { x | x _ x x ¯ x R } is called a limited and closed interval, where x _ and x ¯ are called the lower limit and the upper limit of the interval, respectively. In case that x _ = x ¯ X is called a point interval. The midpoint and the width of X are defined as follows.

w ( X ) = x ¯ x _ m ( X ) = x _ + x ¯ 2 E1

Interval dominance (Limbourg & Aponte, 2005) For any two intervals X i = [ x _ i x ¯ i ] and X j = [ x _ j x ¯ j ] , there are 2 cases of their dominance relations,shown as follows.

If x ¯ i x ¯ j and x _ i x _ j , then we call that X i dominates over X j in interval, and denote X i i n X j , which is shown as Fig. 1.

Figure 1.

Formula: Eqn019.wmf>dominates over X i in interval

If X j , then we call that x " X j : x " X i   and   x ' X i : x ' X j and X i is incomparable in interval, and denote X j , which is shown as Fig. 2.

Figure 2.

Formula: Eqn025.wmf>and X i | | X j is incomparable in interval

2.3. Fuzzy numbers

A fuzzy number is a number with fuzzy meaning. There are many fuzzy numbers in real world, e.g. “about 10“, “close to 48“, “around 95“. It is easy to observe that a fuzzy number is usually composed of a fuzzy operator and an accurate (or a precise) number. The fuzzy operator is to “fuzzify“ a word with crisp meaning or to make a word with fuzzy meaning fuzzier. Some commonly used fuzzy operators are “about“, “near“, “close to“, “around“, etc. Some modal operators, e.g. “very“, “quite“, “greatly“ can also match with these fuzzy operators. In fuzzy mathematics, we often define a fuzzy number with a fuzzy set as follows.

Fuzzy number (Wei, 2004) A fuzzy number X i is a normalized, convex fuzzy set in domain U.

We call a fuzzy set X j normalized if there exists at least an element f ˜ belonging to U whose membership degree f ˜ is equal to 1, i.e. u

We call a fuzzy set μ f ˜ ( u ) convex if its membership function satisfies that max u U μ f ˜ ( u ) = 1

Therefore, we can also define a fuzzy set f ˜ as follows:

u [ u i u j ] U : μ f ˜ ( u ) min { μ f ˜ ( u i ) μ f ˜ ( u j ) } E2

There are many kinds of membership functions, and some typical ones are Gaussian, triangular, and trapezoidal. If describing f ˜ with a Gaussian membership function, we have:

μ f ˜ : U [ 0 1 ] max u U μ f ˜ ( u ) = 1 u [ u i u j ] U μ f ˜ ( u ) min { μ f ˜ ( u i ) μ f ˜ ( u j ) } E3

where c and σ are the center and the width of f ˜ , respectively.

A single-point fuzzy number μ f ˜ ( u ) = e 1 2 ( u c σ ) 2 is special in that except one element f ˜ belonging to U with f ˜ , the membership degree of other elements is 0, i.e.

u 0 E4
μ f ˜ ( u 0 ) = 1 -cut set For μ f ˜ ( u ) = { 1 u = u 0 0 u u 0 , the α -cut set of α ( 0,1 ) , denoted as α , is a subset of U satisfying that the membership degree of its element f ˜ is larger than or equal to f ˜ α , i.e.
u E5

It is easy to observe from the definition of α -cut set that f ˜ α = { u | μ f ˜ ( u ) α u U } , obtained from a line α intercepting f ˜ α , is a crisp set, and the degree of its element belonging to μ f ˜ ( u ) = α is not less than f ˜

It is easy to understand that if the membership function of f ˜ is Gaussian, α is a closed interval, i.e.

f ˜ E6

where f ˜ α and f ˜ α = { u | μ f ˜ ( u ) α u U } = [ f ˜ α _ f ˜ α ¯ ] are the lower limit and the upper limit of f ˜ α _ , respectively. In particular, if f ˜ α ¯ is a single-point fuzzy number, we have f ˜ α , and therefore f ˜ is a point interval, a special interval.

We consider the following general optimization problem in this chapter:

f ˜ α _ = f ˜ α ¯ E7

where f ˜ α is a performance index to be optimized, and cannot be expressed with an explicit function, max f ( x ) s . t . x S R D is a decision variable belonging to a domain S. On condition of not causing confusion, we also denote f ( x ) and S as corresponding individual and the search space, respectively.

Advertisement

3. IGA with individual’s interval fitness

3.1. Methodology of algorithms

By applying interval analysis to evaluate an individual in IGAs, an interactive genetic algorithm with an individual’s interval fitness (IGA-IIF) is presented in this section. An individual’s fitness is an interval in this algorithm, and the width of the interval decreases gradually along with the evolution which embodies that the user’s cognitive on the evaluated object is fuzzy and gradual. In addition, the dominance among different individuals is based on interval dominance and probability dominance, which makes the comparison among different individuals more objective.

3.2. Individual’s interval fitness

Let the i-th individual of a population in some generation be x , x , and the population size be N. Because of the user’s fuzzy cognitive on x i , he/she hardly assigns i = 1,2, N ’s exact fitness, but easily assigns its range which is expressed with an interval. Therefore x i ’s fitness can be described as x i , where x i and f ( x i ) = [ f _ ( x i ) f ¯ ( x i ) ] are the lower limit and the upper limit of the user’s evaluation on f _ ( x i ) , respectively.

It is easy to observe that the larger the lower limit of f ¯ ( x i ) together with the smaller of its width is, the higher and the more exact the evaluation on x i assigned by the user is; otherwise, the smaller the upper limit of f ( x i ) together with the larger its width is, the lower and the rougher the evaluation on x i assigned by the user is. In general, the user’s cognitive on f ( x i ) is fuzzy at early stage of the evolution, therefore x i is large. This cognitive will become clearer and clearer along with the evolution, and hence x i will become narrower and narrower. Therefore, compared with the accurate fitness, it more approximates the mode of the user’s thought that an interval is adopted to express an individual’s fitness, which embodies the user’s fuzzy and gradual cognitive on the evaluated object validly.

3.3. Comparison between two Individuals with interval fitness

Generally speaking, the user has different preferences to different individuals, hence assigning them different interval fitness. As we all know, the quality of an individual is much crucial information in TGAs, which has close relation with genetic operation, hence determining that of offspring. Then how to compare the priority of different individuals in case of interval fitness? In this subsection, we will present the strategy of comparing two individuals with interval fitness.

Considering two individuals w ( f ( x i ) ) and w ( f ( x i ) ) x i , their interval fitness are x j and i j = 1,2, N , respectively. To determine which one is dominant, the following 2 cases are considered.

Case 1 f ( x i ) = [ f _ ( x i ) f ¯ ( x i ) ] , in which case there are 2 possibilities.

(I) f ( x j ) = [ f _ ( x j ) f ¯ ( x j ) ] , which indicates that the lower limit of evaluation on f ( x i ) i n f ( x j ) assigned by the user is not less than the upper limit of evaluation on f _ ( x i ) f ¯ ( x j ) . Therefore, it is reasonable that x i dominates over x j with the probability of 1, and it is impossible for x i to dominate over x j . In this case x j is the dominant individual in tournament selection.

(II) x i , which indicates that x i dominates over f _ ( x i ) f ¯ ( x j ) , but the lower limit of evaluation on f ( x i ) assigned by the user is less than the upper limit of evaluation on f ( x j ) , i.e. their interval fitness have superposition, and the superposition interval denotes the commonness of evaluation on these two individuals. It is easy to understand that the larger the superposition interval is, the smaller the difference of the user’s preference to individuals is, and vice versa. First, we consider an interval x i , the probability of x j ’s fitness falling into this interval is [ f ¯ ( x j ) f ¯ ( x i ) ] , where x i dominates over f ¯ ( x i ) f ¯ ( x j ) w ( f ( x i ) ) with the probability of 1. And then we consider an interval x i , the probability of x j ’s fitness falling into this interval is [ f _ ( x i ) f ¯ ( x j ) ] , where x i dominates over f ¯ ( x j ) f _ ( x i ) w ( f ( x i ) ) with the probability of x i . Therefore x j dominates over 0.5 f ¯ ( x j ) f _ ( x i ) w ( f ( x j ) ) + f _ ( x i ) f _ ( x j ) w ( f ( x j ) ) with the probability of

x i E8

Then the probability that x j becomes the dominant individual in tournament selection is p ( x i x j ) = f ¯ ( x i ) f ¯ ( x j ) w ( f ( x i ) ) + f ¯ ( x j ) f _ ( x i ) w ( f ( x i ) ) ( 0.5 f ¯ ( x j ) f _ ( x i ) w ( f ( x j ) ) + f _ ( x i ) f _ ( x j ) w ( f ( x j ) ) )

Similarly, we can obtain the following probability with which x i dominates over p ( x i x j )

x j E9

That is to say, the probability that x i becomes the dominant individual in tournament selection is p ( x j x i ) = 0.5 f ¯ ( x j ) f _ ( x i ) w ( f ( x j ) ) f ¯ ( x j ) f _ ( x i ) w ( f ( x i ) )

At early stage of the evolution, the difference of different individuals’ interval fitness is much obvious, which is common as case (I). Along with the evolution, the difference of different individuals decreases gradually, and so does their interval fitness. In addition, the width of these intervals decreases gradually too, resulting in the superposition intervals of different individuals increasing gradually, which is common as case (II). In this case, the probabilities that different individuals are dominant ones in tournament selection are nearer and nearer.

Case 2 x j , i.e. p ( x j x i ) or f ( x i ) | | f ( x j ) . Because of f ¯ ( x i ) f ¯ ( x j ) f _ ( x i ) f _ ( x j ) ’s randomicity, only the former is considered in this subsection, i.e. f ¯ ( x j ) f ¯ ( x i ) f _ ( x j ) f _ ( x i ) . In the case above, it is shown that the evaluation on x i assigned by the user is incomparable with that on f ¯ ( x i ) f ¯ ( x j ) f _ ( x i ) f _ ( x j ) , but the former is more exact. First, an interval x i is considered. The probability of x j ’s fitness falling into this interval is [ f ¯ ( x i ) f ¯ ( x j ) ] , where x j dominates over f ¯ ( x j ) f ¯ ( x i ) w ( f ( x j ) ) with the probability of 1. Then we consider an interval x j , the probability of x i ’s fitness falling into this interval is [ f _ ( x i ) f ¯ ( x i ) ] , where x j dominates over f ¯ ( x i ) f _ ( x i ) w ( f ( x j ) ) with the probability of 0.5. Therefore, x j dominates over x i with the following probability

x j E10

Hence the probability that x i becomes the dominant individual in tournament selection is p ( x j x i ) = f ¯ ( x j ) f ¯ ( x i ) w ( f ( x j ) ) + 0.5 w ( f ( x i ) ) w ( f ( x j ) )

Similarly, we can obtain the following probability with which x j dominates over p ( x j x i )

x i E11

That is to say, the probability that x j becomes the dominant individual in tournament selection is p ( x i x j ) = 0.5 w ( f ( x i ) ) w ( f ( x j ) ) + f _ ( x i ) f _ ( x j ) w ( f ( x j ) )

It is easy to obtain through simple deduction that x i in the 2 cases above.

The results above are obtained on condition that the fitness of these 2 individuals are both ordinary intervals. If their fitness are both point intervals, then the method to compare their quality degenerates as the traditional one. If only p ( x i x j ) is a point interval and dominates over p ( x i x j ) + p ( x j x i ) = 1 , we have f ( x i ) . If only f ( x j ) is a point interval and incomparable with p ( x i x j ) = 1, p ( x j x i ) = 0 , we have f ( x i ) and f ( x j ) . Similarly, if only p ( x j x i ) = f ¯ ( x j ) f ( x i ) w ( f ( x j ) ) is a point interval and dominated by p ( x i x j ) = f ( x i ) f _ ( x j ) w ( f ( x j ) ) , we have f ( x j ) . If only f ( x i ) is a point interval and incomparable with p ( x i x j ) = 1 p ( x j x i ) = 0 , we have f ( x j ) and

f ( x i ) E12

Here p ( x i x j ) = f ¯ ( x i ) f ( x j ) w ( f ( x i ) ) and p ( x j x i ) = f ( x j ) f _ ( x i ) w ( f ( x i ) ) are dominant individuals in tournament selection with the probability of x i and x j , respectively. The method to perform tournament selection above is as follows. First, calculate the accumulative probabilities of p ( x i x j ) and p ( x j x i ) , i.e. x i . And then generate a random number r in [0, 1]. At last, compare r with x j . If c i = p ( x i x j ) c j = c i + p ( x j x i ) = 1 , then c i is the dominant individual in tournament selection; otherwise, r c i is the dominant one.

3.4. Steps of algorithm

The steps of the proposed algorithms in this section can be described as follows.

  1. Set the values of control parameters in the algorithms. Let x i , and initialize a population.

  2. Decode and assign an individual’s interval fitness based on the user’s evaluation.

  3. Determine whether the algorithm stops or not, if yes, go to Step 6.

  4. Select two candidates x j and t = 0 x i ( t ) for tournament selection, calculate x j ( t ) and i j = 1,2, N according to formula (2) to (5), and generate the dominant individual in tournament selection.

  5. Perform genetic operation and generate offspring. Let p ( x i ( t ) x j ( t ) ) , go to Step 2.

  6. Output the optima and stop the algorithm.

3.5. Further explanations

Compared with TIGAs, an obvious character of the proposed algorithm in this section is that an individual’s fitness is an interval not an accurate value, resulting in the comparison of different individuals not being based on their fitness. What to be obtained is a probability with which an individual is the dominant one in tournament selection based on interval dominance. It is remarkable that an individual is the dominant one in tournament selection with some probability, but not the absolutely dominant one.

An individual’s interval fitness proposed in this section reflects the user’s cognitive law on the evaluated object. On the one hand, it embodies that the user’s cognitive on the evaluated object is fuzzy. The user’s fuzzy cognitive process makes the evaluation on an individual is also fuzzy, which cannot be appropriately described by an accurate value, but by an interval. An individual’s interval fitness expresses that an individual’s fitness falls into an interval, not exact evaluation on the individual by the user, which reflects that the user’s cognitive is fuzzy. On the other hand, it embodies that the user’s cognitive on the evaluated object is gradual. It is a gradual process from fuzzy to clear to evaluate an object by the user. Along with deep cognitive on the evaluated object during the evolution, the user evaluates individuals clearer and clearer, and the width of an individual’s interval fitness is narrower and narrower, which is a gradual process, reflecting the development of the user’s cognitive.

Advertisement

4. IGA with individual’s fuzzy fitness

An IGA with an individual’s fuzzy fitness (IGA-IFF) is an IGA which expresses the result of the user’s evaluation on an individual with a fuzzy number, and adopts traditional genetic operation. Some new problems will result from the fuzzy expression of an individual’s fitness, in which the primary one is how to compare different individuals in the same generation. It will directly influence selection operation adopted in the algorithm. In addition, it will also influence the human-computer interface.

4.1. Methodology of algorithms

The methodology of the proposed algorithm is as follows. First, we adopt a fuzzy number to express the result of the user’s evaluation on an individual, which is different from all existing IGAs. Then, in order to compare two individuals in the same generation, we generate two crisp sets of individuals’ fitness based on p ( x j ( t ) x i ( t ) ) -cut sets, and obtain the dominance probability of an individual on the basis of the composition of these crisp sets. Finally, considering tournament selection with size being two, we generate the superior individual based on these dominance probabilities, and then perform the subsequent genetic operation after generating all parents.

Our contributions in this section mainly embody the following two aspects. First, we adopt a novel expression of an individual’s fitness, which much accords with the user’s fuzzy cognitive on the evaluated object. Second, we present an effective method to compare different individuals when an individual’s fitness is expressed with a fuzzy number, which is necessary for a population to evolve. These contributions can improve the performance of existing IGAs in alleviating user fatigue and looking for the optimal solutions of an optimization problem, therefore it is beneficial to solve complicated problems with implicit or fuzzy indices.

4.2. Individual's fuzzy fitness

In the initial phase of the evolution, the user’s preference is fuzzy and his/her cognitive degree to the evaluated object is low. Along with the evolution, the number of individuals being evaluated by the user increases, hence he/she is gradually familiar with the evaluated object. Therefore, the user’s cognitive on the evaluated object is fuzzy and gradual. In addition, the evaluation process is influenced by an individual’s phenotype and user fatigue. So it is difficult for an individual’s accurate fitness to accurately reflect the process and the user’s cognitive result, while an individual’s fuzzy fitness can.

We consider an individual t = t + 1 , and express its fitness as α . We define a function in x as follows

f ˜ ( x ) E13

to express the degree of a [ f min f max ] belonging to μ f ˜ ( x ) [ f min f max ] [ 0 1 ] , where f [ f min f max ] and f ˜ ( x ) are the smallest and the largest fitness of an individual. It is easy to observe that an individual’s fitness should lie in the range of f min , i.e. there exists at least one number in f max which is [ f min f max ] ’s real fitness, i.e. its membership degree w.r.t. [ f min f max ] is 1. Therefore, x is normalized. In addition, the further a number in f ˜ ( x ) from f ˜ ( x ) ’s real fitness is, the smaller its membership degree w.r.t. [ f min f max ] should be. Therefore, x is convex. According to the definition of fuzzy number, f ˜ ( x ) is a fuzzy number.

For not losing generality, we adopt a Gaussian membership function to express an individual’s fuzzy fitness, and define the membership function of f ˜ ( x ) as follows:

f ˜ ( x ) E14

where f ˜ ( x ) is μ f ˜ ( x ) ( f ) = e 1 2 ( f c ( x ) σ ( x ) ) 2 ’s center, it is the fitness whose membership degree w.r.t. c ( x ) is 1. f ˜ ( x ) is f ˜ ( x ) ’s width satisfying that the membership degree of fitness within σ ( x ) w.r.t. f ˜ ( x ) is not less than [ c ( x ) σ ( x ) c ( x ) + σ ( x ) ]

We now further explain the above f ˜ ( x ) ’s fuzzy fitness as follows.

In general, for different individuals, the membership functions of their fitness have different centers and width, i.e. for 1 / e 0.6 , we have x

The user’s cognitive on the evaluated object is influenced by an individual’s phenotype and user fatigue, therefore for the same individual in different generations, the center and the width of its membership function may be different, i.e. the center and the width of a membership function are also relative to generation x i x j S x i x j , i.e. for c ( x i ) c ( x j ) σ ( x i ) σ ( x j ) , we may have t 0 t i t j T t i t j , where T is the maximum generation. Whereas in TGAs, an individual’s fitness is uniquely determined by its phenotype, and does not change along with the evolution. Therefore, we think it an essential difference between IGAs and TGAs.

Generally speaking, along with the evolution, the user is gradually familiar with the evaluated object, and assigns an individual’s fitness with high confidence. Therefore, the sum of all width of the membership functions of these individuals’ fitness in the same generation will be narrower and narrower, at the same time, the sum of all their centers will be larger and larger as a result of more superior individuals being reserved as well as more inferior ones being eliminated, i.e. for c ( x t i ) c ( x t j ) , we have σ ( x t i ) σ ( x t j )

0 t i t j T E15

If x σ ( x t i ) x σ ( x t j ) , we have x c ( x t i ) x c ( x t j ) , whereas if f = c ( x ) and μ f ˜ ( x ) ( f ) = e 1 2 ( f c ( x ) σ ( x ) ) 2 = 1 , we have f c ( x ) , which indicates that the fuzzy number degenerates as an accurate one. Therefore, it is rational to regard an individual’s fuzzy fitness as the extension of an accurate one, whereas an individual’s accurate fitness as a special case of a fuzzy one.

When we adopt an accurate number to express an individual’s fitness, it often takes the user very much time to assign an individual’s appropriate fitness, and the user bears considerable mental pressure during evaluation. Whereas when we adopt a fuzzy number, described with a Gaussian membership function, to express an individual’s fitness, it seems that we require two parameters, i.e. σ ( x ) 0 and μ f ˜ ( x ) ( f ) = e 1 2 ( f c ( x ) σ ( x ) ) 2 = 0 , but c ( x ) need not be very precise, and we can determine σ ( x ) beforehand or change it with selected fuzzy modal words. Therefore, the user only assigns an individual’s approximate fitness, which greatly decreases his/her pressure during evaluation.

It is easy to understand that the proposed algorithm requires a new human-computer interface when adopting a fuzzy number to express an individual’s fitness. In comparison with TIGAs whose individual’s fitness is expressed with an accurate number, the obvious difference lies in the approach to input an individual’s fitness. In addition to input c ( x ) ’s value through a text box or a scroll bar, the user also selects a fuzzy modal word, e.g. “about“, “close to“, “very close to“, etc., in order to determine σ ( x ) . Besides, the proposed algorithm calculates c ( x ) , and displays their change curves through the interface to reflect the progress of the evolution.

4.3. Comparison between two Individuals with fuzzy fitness

It is very easy to compare individuals when we adopt an accurate number to express an individual’s fitness. We only determine the relationship of their fitness, therefore, it is a case of comparing some accurate numbers. When we adopt a fuzzy number to express an individual’s fitness, the comparison of individuals will become a case of comparing some fuzzy sets. It will be a case of comparing some sets. Therefore, it is very difficult to compare individuals in this case.

In this subsection, we consider the comparison of two individuals based on σ ( x ) -cut set whose idea is as follows. First, we choose a fuzzy level x σ ( x t ) x c ( x t ) , and obtain two α -cut sets of these individuals’ fuzzy fitness. They are crisp sets and often intervals. Then, we determine two dominance probabilities by use of the relationship of two intervals. Finally, considering tournament selection with size being two, we determine the dominant individual by use of the roulette wheel method based on these dominance probabilities.

We will expound the proposed strategy in detail as follows.

Let two fuzzy fitness of individuals α and α be x i and x j , and their membership functions be f ˜ ( x i ) and f ˜ ( x j ) , respectively. The μ f ˜ ( x i ) ( f ) = e 1 2 ( f c ( x i ) σ ( x i ) ) 2 -cut sets of μ f ˜ ( x j ) ( f ) = e 1 2 ( f c ( x j ) σ ( x j ) ) 2 and

α E16
are

f ˜ ( x i ) E17

respectively, where both f ˜ ( x j ) and f ˜ α ( x i ) = { f | μ f ˜ ( x i ) ( f ) α f [ f min f max ] } [ f ˜ α ( x i ) _ f ˜ α ( x i ) ¯ ] f ˜ α ( x j ) = { f | μ f ˜ ( x j ) ( f ) α f [ f min f max ] } [ f ˜ α ( x j ) _ f ˜ α ( x j ) ¯ ] are crisp sets, and reflect that the fitness lying in which belongs to f ˜ α ( x i ) and f ˜ α ( x j ) respectively with the membership degree being not less than f ˜ ( x i ) , or the value lying in f ˜ ( x j ) and α is the fitness of f ˜ α ( x i ) and f ˜ α ( x j ) respectively with the confidence degree being not less than x i

According to the positions of x j and α , there are two cases when μ f ˜ ( x i ) compares with μ f ˜ ( x j )

Case 1 x i , in which case there are two possibilities.

The first one is x j and c ( x i ) = c ( x j ) , which indicates that c ( x i ) = c ( x j ) , i.e. the fitness of σ ( x i ) = σ ( x j ) is the same as that of f ˜ ( x i ) = f ˜ ( x j ) . Therefore, x i dominates x j with the probability of 0.5, and so does x i

Figure 3.

Two individuals’ fitness on condition of x j but x j

The second one is c ( x i ) = c ( x j ) but σ ( x i ) σ ( x j ) . For not losing generality, we only consider the case that c ( x i ) = c ( x j ) but σ ( x i ) σ ( x j ) , shown as Fig. 3. The comparison between c ( x i ) = c ( x j ) and σ ( x i ) σ ( x j ) at x i level is equal to the comparison between x j and

α E19

Similar to the deduction in subsection 3.3, we can easily obtain that f ˜ α ( x i ) dominates over f ˜ α ( x j ) with the probability of

x j E20
And x i dominates over p ( x j x i ) = f ˜ α ( x j ) ¯ f ˜ α ( x i ) ¯ + 0.5 w ( f ˜ α ( x i ) ) w ( f ˜ α ( x j ) ) = 0.5 with the following probability
x i E21

Case 2 x j . For not losing generality, we only consider the case that p ( x i x j ) = 0.5 w ( f ˜ α ( x i ) ) + f ˜ α ( x i ) _ f ˜ α ( x j ) _ w ( f ˜ α ( x j ) ) = 0.5 . Let c ( x i ) c ( x j ) . We will discuss the following two cases based on the relationship between c ( x i ) c ( x j ) and

α 0 = max f [ f min f max ] μ f ˜ ( x i ) f ˜ ( x j ) ( f ) E22

If α , shown as Fig. 4, we have α 0 , which indicates that at α α 0 level the lower limit of evaluation on f ˜ α ( x j ) _ f ˜ α ( x i ) ¯ is larger than the upper limit of evaluation on α . Therefore it is reasonable that x j dominates over x i with the probability of 1, and it is impossible that x j dominates over x i

Figure 4.

Two individuals’ fitness on condition of xi and xj

If c ( x i ) c ( x j ) , shown as Fig. 5, we have α α 0 , which indicates that though α α 0 dominates over f ˜ α ( x j ) _ f ˜ α ( x i ) ¯ , at f ˜ α ( x j ) level the lower limit of evaluation on f ˜ α ( x i ) is less than or equal to the upper limit of evaluation on α . Adopting the same method as that in subsection 3.3, we can easily obtain that x j dominates over x i with the probability of
x j E24
And x i dominates over p ( x j x i ) = f ˜ α ( x j ) ¯ f ˜ α ( x i ) ¯ w ( f ˜ α ( x j ) ) + f ˜ α ( x i ) ¯ f ˜ α ( x j ) _ w ( f ˜ α ( x j ) ) ( 1 0.5 f ˜ α ( x i ) ¯ f ˜ α ( x j ) _ w ( f ˜ α ( x i ) ) ) with the following probability
x i E25

The above results are obtained based on both individuals’ fitness being ordinary fuzzy numbers. If their fitness are both single-point fuzzy numbers, the approach to compare these two individuals degenerates to the traditional one. If only one individual’s fitness is a single-point fuzzy number, for not losing generality, we assume that x j is a single-point fuzzy number, i.e. p ( x i x j ) = 0.5 ( f ˜ α ( x i ) ¯ f ˜ α ( x j ) _ ) 2 w ( f ˜ α ( x i ) ) w ( f ˜ α ( x j ) ) . If f ˜ ( x i ) , we have f ˜ α ( x i ) ¯ = f ˜ α ( x i ) _ ; If f ˜ α ( x i ) ¯ = f ˜ α ( x i ) _ f ˜ α ( x j ) ¯ , we have p ( x i x j ) = 1, p ( x j x i ) = 0 ; If f ˜ α ( x j ) _ f ˜ α ( x i ) ¯ = f ˜ α ( x i ) _ f ˜ α ( x j ) ¯ , we have p ( x j x i ) = f ˜ α ( x j ) ¯ f ˜ α ( x i ) ¯ w ( f ˜ α ( x j ) ) p ( x i x j ) = f ˜ α ( x i ) _ f ˜ α ( x j ) _ w ( f ˜ α ( x j ) )

Figure 5.

Two individuals’ fitness on condition of f ˜ α ( x i ) ¯ = f ˜ α ( x i ) _ f ˜ α ( x j ) _ and p ( x i x j ) = 0, p ( x j x i ) = 1

Also, we adopt the same method as that in subsection 3.3 to select the dominant individual in tournament selection.

It is easy to observe from the process of comparison between c ( x i ) c ( x j ) and α α 0 that what determines an individual to be the dominant one in tournament selection is x i and x j . For case 2 both dominance probabilities have close relation with p ( x i x j ) -cut set. Even if we have the same fuzzy set, different p ( x i x j ) will lead to different α -cut sets. That is, α directly influences the comparison result.

Generally speaking, at the initial phase of the evolution, we expect a population with good diversity so as to search in exploration. It requires an inferior individual having some opportunities as the parent one. We can achieve it by choosing a small value of α ; on the contrary, at the later phase of the evolution, we expect a population with good convergence in order to converge in a timely manner. It requires a superior individual having more opportunities as the parent one. We can do it by choosing a large value of α .

In addition, it can be seen from the user’s fuzzy and gradual cognitive that at the initial phase of the evolution, we usually require a small value of α so as to make up the deviation of the user’s evaluation by reserving some potential individuals. Whereas at the later phase of the evolution, the user has been familiar with the evaluated object, we often require a large value of α to select the superior individual with large confidence.

Based on these, an approach to change α is as follows:

α E27

where α is the minimum of α ( t ) = min { α min + t T ,1 } t T set by the user in prior.

4.4. Steps of algorithms

Similar to that of IGA with an individual’s interval fitness, the steps of the proposed algorithm in this section can be described as follows.

  1. Set the values of control parameters in the algorithm. Let α min , and initialize a population.

  2. Decode and assign an individual’s fuzzy fitness based on the user’s evaluation.

  3. Determine whether the algorithm stops or not, if yes, go to Step 6.

  4. Select two candidates α ( t ) and t = 0 x i ( t ) for tournament selection, calculate x j ( t ) and i j = 1,2, N according to formula (7) to (10), and generate the dominant individual in tournament selection.

  5. Perform genetic operation and generate offspring. Let p ( x i ( t ) x j ( t ) ) , go to Step 2.

  6. Output the optima and stop the algorithm.

It can be observed from the above steps that except for Step 2 and Step 4, the rest have no difference with those of TIGAs. For Step 2, different from TIGAs in which we adopt an accurate number to express an individual’s fitness, in IGA-IFF we adopt a fuzzy number, described with a center and width, to express an individual’s fitness. In Step 4, the core of IGA-IFF, we give the process of generating the dominant individual in tournament selection based on an individual’s fuzzy fitness. Comparing with TIGAs, the above process is obviously complicated as a result of the fuzzy fitness, but can be automatically achieved through the computer. Therefore in contrast with time taken to evaluate an individual, we can ignore time taken during the above process, which implies that it does not take the proposed algorithm much additional time to select the dominant individual; on the contrary, as a result of alleviating the user’s pressure in evaluating an individual, time to evaluate an individual will sharply decrease, and so will the whole running time.

4.5. Fuzzy fitness and interval fitness

Both Fuzzy fitness (FF) and interval fitness (IF) are uncertain fitness, and reflect the user’s fuzzy and gradual cognitive on the evaluated object, which are their common character.

But there are some differences between them. The first one is that they emphasize different aspects. IF emphasizes the range that an individual’s fitness lies in, reflecting the uncertainty of an individual’s fitness; while FF emphasizes the fuzziness degree, reflecting the diversity of the fuzziness degree of an individual’s fitness. The second one is that different kinds of uncertain fitness require different parameters. IF requires the lower limit and the upper limit; while FF described with a Gaussian membership function requires the center and the width.

Besides, the comparison of two FF is based on the comparison of two IF. Therefore, we say from this point that IF is the base and a special case of FF; while FF is the extension and a generalization of IF.

Which kind of uncertain fitness should be adopted in an IGA is determined by the acquired knowledge in prior. When having acquired the fuzzy knowledge on an individual’s fitness, we should choose FF; otherwise, when having acquired the range in which an individual’s fitness lies, it would be better to choose IF.

Advertisement

5. Applications in fashion evolutionary design system

5.1. Backgrounds

Fashion design is a very popular vocation, for everyone likes to wear satisfactory fashions but few can design a satisfactory one. In fact, fashion design is a very complicated process and often completed by designers who have been systematically trained. Although there is some software available for fashion design, they are often too professional for an ordinary person to use. With the development of society pursuing personality becomes a fad. That is to say, people often like to wear fashions with some personalities. It is much necessary for a fashion design system available for an ordinary person to design his/her satisfactory fashions.

We aim to establish a fashion design system for an ordinary person to generate a suit by combining all parts from different databases. That is to say, all parts of a suit are stored in databases in advance. What a person does is to combine different parts into his/her most satisfactory suit by using the system. In fact, the above is a typical combinational optimization problem and solved by evolutionary optimization methods.

But what is “the most satisfactory suit“? Different persons may have different opinions on it because of different personalities, and these opinions are often fuzzy and implicit. Therefore it is impossible to get a uniform and explicit index to be optimized. It is infeasible for TGAs to deal with it, whereas suitable for IGAs to do.

We develop two fashion evolutionary design systems based on IGA-IIF and IGA-IFF, respectively by using Visual Basic 6.0. We also develop a fashion evolutionary design systems based on TIGA by using the same development tool, and conduct some experiments to compare their performances.

5.2. Individual codes

The same individual code is adopted in these systems. For simplification, the phenotype of an individual is a suit composed of coat and skirt, and its genotype is a binary string of 18 bits, where the first 5 bits expresses the style of coat, the 6th to 10th bits expresses the style of skirt, the 11th to 14th bits expresses the color of coat, and the last 4 bits expresses the color of skirt. There are 32 styles of coats and skirts respectively, and their names correspond to the integers from 0 to 31, which are also their decimals of these binary codes. The colors and their codes are listed as Table 1. They are all stored in different databases. According to the user’s preference, these systems look for “the most satisfactory suit“ in the design space with p ( x j ( t ) x i ( t ) ) suits during evolutionary optimization.

color code color code
black 0000 gray 1000
blue 0001 bright blue 1001
green 0010 bright green 1010
cyan 0011 bright cyan 1011
red 0100 bright red 1100
carmine 0101 bright carmine 1101
yellow 0110 bright yellow 1110
white 0111 bright white 1111

Table 1.

Colors and their codes

5.3. Parameter settings

In order to compare the performances of these three algorithms, the same genetic operation and parameters but different approaches to evaluate an individual during running are adopted. The population size t = t + 1 is equal to 8. In order to express an individual’s fuzzy fitness, a scroll bar is adopted to set 2 5 × 2 5 × 2 4 × 2 4 = 262144 , and its range is restricted between 0 and 1000, i.e. N and c ( x ) are 0 and 1000, respectively. Besides, tournament selection with size being two, one-point crossover and one-point mutation operators are adopted, and their probabilities f min and f max are 0.6 and 0.02, respectively. In addition, p c and T are 0.5 and 20, respectively. That is to say, if the evolution does not converge after 20 generations, the system will automatically stop it. When the evolution converges, i.e. there are at least 6 individuals with the same phenotype in some generation, the system will also automatically stop it. Also, when the user is satisfied with the optimal results, he/she can manually stop the evolution.

5.4. Human-computer interface and individual evaluation

The human-computer interface of IGA-IIF, shown as Fig. 6, includes 3 parts. The first one is individuals’ phenotypes and their evaluations. In order to assign a suit’s fitness, the user drags two scroll bars under it. Of the two scroll bars, the upper one stands for the lower limit of the fitness, and the lower one stands for its upper limit. The values of the lower limit and the upper limit are also displayed under these scroll bars. The second one is some command buttons for a population evolving, e.g. “Initialize“, “Next Generation“, “End“ and “Exit“. And the third one is some statistic information of the evolution, including the number of individuals being evaluated (distinct ones), the current generation and time-consuming. Having evaluated all suits, if the user clicks “Next Generation“, the system will perform genetic operation described as subsection 5.3 to generate offspring, and then display them to the user. The system will cycle the above procedure until automatically or manually stops the evolution.

The human-computer interface of IGA-IFF, shown as Fig. 7, includes 3 parts. The first one is individuals’ phenotypes and their fitness. The user evaluates a suit through selecting one of these modal words in the list box, i.e. “about“, “close to“ or “very close to“ with their corresponding values of p m being 60, 40 and 20, respectively, and dragging the scroll bar. The second one is the same as that of IGA-IIF. And the third one is also some statistic information of the evolution, including α min , the number of individuals being evaluated, the current generation and time-consuming.

Figure 6.

Human-computer interface of IGA-IIF.

Figure 7.

Human-computer interface of IGA-IFF.

During the evolution, the user evaluates a suit through dragging the scroll bar under it to provide the membership function’s center of its fitness, and clicking the corresponding modal word in the list box to provide the membership function’s width. For example, the user drags the scroll bar to “938“ and clicks “very close to“ to obtain the fuzzy fitness “very close to 938“ of the first individual, shown as Fig. 7. Having evaluated all individuals, if the user clicks “Next Generation“, the system will look for the dominant individual in tournament selection based on the proposed method in subsection 4.3. After that, the system will perform genetic operation described as subsection 5.3 to generate offspring, and then display them to the user. The system will cycle the above procedure until automatically or manually stops the evolution.

Similarly, the human-computer interface of TIGA, shown as Fig. 8, also includes 3 parts. The first one is individuals’ phenotypes and their evaluations. In order to assign a suit’s fitness, the user drags the scroll bar under it only once. The second and the third parts are the same as those of IGA-IIF. Having evaluated all suits, if the user clicks “Next Generation“, the system will perform genetic operators described as subsection 5.3 to generate offspring, and then display them to the user. The system will cycle the above procedure until automatically or manually stops the evolution. The interested reader can refer to our newly published book for detail (Gong et al., 2007).

Figure 8.

Human-computer interface of TIGA.

5.5. Results and analysis

First, we run the system based on IGA-IIF 20 times independently, calculate the sum of the width of interval fitness and that of the midpoints of interval fitness in each generation. Their averages of the 20 runs in 15 generations are listed as Table 2.

It can be observed from Table 2 that the sum of the width of individuals’ interval fitness gradually decreases along with the evolution, which reflects that the user’s cognitive on the evaluated object is from fuzzy to clear, i.e. the user’s cognitive is gradual. In addition, the sum of the midpoints of individuals’ interval fitness increases along with the evolution, which indicates that the quality of optimal solutions gradually improves.

We then run the system based on IGA-IFF 8 times independently, and calculate σ ( x ) and x σ ( x t ) x c ( x t ) in each generation. Their averages of the 8 runs are shown as Fig. 9.

generations sum of width of interval fitness sum of midpoints of interval fitness
1 5012 4100
2 4970 4404
3 4075 4437
4 3791 4265
5 3854 4870
6 3067 5167
7 2997 5411
8 2373 5268
9 2647 5031
10 2707 5923
11 2071 5966
12 1925 6148
13 1797 6264
14 1577 6629
15 1173 6611

Table 2.

Sum of width and midpoints of interval fitness

Figure 9.

Trends of x σ ( x t ) and x c ( x t )

It is obvious from Fig. 9 that the trends of x σ ( x t ) and x c ( x t ) change with t. x σ ( x t ) changes from 390 in the 1st generation to 210 in the 9th generation. In general, it gradually decreases along with the evolution, reflecting that the user’s cognitive is from fuzzy to clear, i.e. the user’s cognitive is gradual. On the other hand, x c ( x t ) changes from 2603.25 in the 1st generation to 6434.5 in the 9th generation, and increases along with the evolution, indicating that individuals’ quality gradually improves, which is the result of more and more superior individuals being reserved and inferior individuals being eliminated. Therefore, an individual’s fuzzy fitness described with a Gaussian membership function can correctly and clearly reflect the user’s cognitive.

Now we compare the performance of three systems based on IGA-IIF, IGA-IFF and TIGA respectively. To achieve this, we run three systems 8 times independently, record time-consuming for evaluating individuals, the number of distinct individuals being evaluated in each run, and calculate their sums. The results are listed as Table 3 and Table 4.

It can be observed from Table 3 that for IGA-IIF, IGA-IFF and TIGA, the longest time-consuming for evaluating individuals in each run is 5’11“, 8’33“ and 7’44“,respectively. They are all less than 10 minutes, which is acceptable because the user often does not feel fatigue within 10 minutes. This means that it often takes the user less time to design a satisfactory suit by using these systems.

It is easy to observe from Table 4 that for IGA-IFF, the largest number of individuals being evaluated is 93, which is equivalent to the population evolving about 12 generations. That is to say, the user finds “the most satisfactory suit“ in small generations by using IGA-IFF. For IGA-IIF, all runs find “the most satisfactory suit“ in also about 12 generations. For TIGA, all runs find “the most satisfactory suit“ in about 11 generations. In the three algorithms, the number of generations required by the user is less than the given maximum generations, i.e. 20, which indicates the three algorithms are feasible to deal with fashion design.

No. of run IGA-IIF IGA-IFF TIGA
1 7’48“ 3’42“ 5’40“
2 3’00“ 4’15“ 4’02“
3 6’10“ 3’34“ 6’58“
4 8’33“ 5’11“ 7’44“
5 3’44“ 3’53“ 3’10“
6 3’41“ 4’50“ 5’02“
7 3’53“ 3’02“ 5’49“
8 5’17“ 3’47“ 6’15“
sum 42’06“ 32’14“ 44’40“

Table 3.

Time-consuming for evaluating individuals

No. of run IGA-IIF IGA-IFF TIGA
1 81 45 59
2 28 59 42
3 65 46 63
4 96 93 86
5 35 65 39
6 38 68 45
7 39 41 56
8 62 62 69
sum 444 479 459

Table 4.

Number of individuals being evaluated

It is obvious from Table 4 that the number of individuals being evaluated in IGA-IFF is the largest, i.e. 479, whereas combined with the Table 3, its time-consuming for evaluating individuals is the shortest, which implies that its number of generations may not be the largest. This is because the fuzzy fitness and the approach to compare different individuals increase the diversity of a population, therefore IGA-IFF can prevent the evolution from premature convergence to some extent, and increase the opportunities to find satisfactory solutions.

In order to compare the performance of different algorithms in alleviating user fatigue, we calculate the average time-consuming for evaluating individuals in each run and the average time-consuming for evaluating an individual, listed as Table 5. The items in Table 5 are calculated from the data in Table 3 and Table 4. We obtained the 2nd column of Table 5 through dividing the last row of Table 3 by 8, and the 3rd column of Table 5 through dividing the last row of Table 3 by that of Table 4.

algorithm for evaluating individuals in each run for evaluating an individual
IGA-IIF 5’16“ 5.7“
IGA-IFF 4’02“ 4.0“
TIGA 5’35“ 5.8“

Table 5.

Average time-consuming for evaluating individuals

It is obvious from Table 5 that the average time-consuming for evaluating individuals in each run of IGA-IFF is 4’02“, which is less than that of IGA-IIF (5’16“) and TIGA (5’35“). In addition, the average time-consuming for evaluating an individual of IGA-IFF is 4.0“, which is also less than that of IGA-IIF (5.7“) and TIGA (5.8“). Different time-consuming for evaluating an individual is due to different approaches of evaluation. For TIGA, the user needs to assign an accurate fitness to an individual, therefore it takes him/her much time to consider what the fitness should be. For IGA-IIF, the user does not need to assign an accurate fitness to an individual. In order to obtain an individual’s fitness, the user needs to assign its upper limit and lower limit. Different from TIGA, in IGA-IFF, the user evaluates an individual without spending much time in providing an accurate fitness, leading to small time-consuming. Comparing IGA-IFF with IGA-IIF, the user spends shorter time in IGA-IFF as the result of convenient assignment through human-computer interface. In IGA-IFF, the user evaluates a suit through dragging the scroll bar once, and clicking the corresponding modal word in the list box. While in IGA-IIF, the user evaluates a suit through dragging the scroll bar twice. Therefore an individual’s fuzzy fitness can alleviate user fatigue to some degree.

The success rate to find “the most satisfactory suit“ within limited time is another index to compare the performance of these algorithms. We calculated the success rate to find “the most satisfactory suit“ within 5 minutes, 7 minutes and 9 minutes respectively. Considering the 8 independent runs, we recorded the times to find “the most satisfactory suit“ within 5 minutes, 7 minutes and 9 minutes respectively, and then divided these numbers by 8. For example, there are 4 times for IGA-IIF to find “the most satisfactory suit“ within 5 minutes, therefore the success rate of IGA-IIF within 5 minutes is x σ ( x t ) . The success rate of different algorithms within different time is listed as Table 6.

algorithm within 5’ within 7’ within 9’
IGA-IIF 50 75 100
IGA-IFF 87.5 100 100
TIGA 25 87.5 100

Table 6.

Success rate(%)

It is easy to observe from Table 6 that when the user spends 5 minutes in evaluating individuals, 7 runs of IGA-IFF find “the most satisfactory suit“, only 4 runs of IGA-IIF find it, and 2 runs of TIGA find it. When time increases to 9 minutes, they all find “the most satisfactory suit“. This indicates that IGA-IFF has more opportunities to find “the most satisfactory suit“ in short time than the other two algorithms.

To sum up, compared with TIGA, the proposed algorithms in this chapter have good performances in alleviating user fatigue and looking for “the most satisfactory suit”.

Advertisement

6. Conclusion

User fatigue problem, resulted from evaluation on an individual and expression of its fitness by the user, is very important and hard to solve in IGAs. It is key for IGAs to improve performance in case of successfully solving user fatigue problem.

It is easy to understand that user fatigue can alleviate to some degree if we adopt some appropriate approaches to express an individual’s fitness. Based on this, we propose two novel interactive genetic algorithms, i.e. IGA-IIF and IGA-IFF in this chapter. We adopt an interval described with the lower limit and the upper limit as well as a fuzzy number described with a Gaussian membership function to express an individual’s fitness. These expressions well accord with the user’s fuzzy and gradual cognitive on the evaluated object. In order to compare different individuals in the same generation, we obtain the probability of an individual dominance by use of the probability of interval dominance, translate a fuzzy number into an interval based on x c ( x t ) -cut set, and determine the dominant individual in tournament selection with size being two based on the probability of an individual dominance. We develop fashion evolutionary design systems based on these proposed algorithms, and compare them with TIGA. The experimental results show their advantages in alleviating user fatigue and looking for user’s satisfactory individuals.

An individual’s uncertain fitness is a novel research direction. How to extract some information on a population evolving on condition of an individual’s uncertain fitness to guide the subsequent evolution so as to improve the performance of IGAs is a significant research topic. In addition, another way to alleviate user fatigue is to adopt surrogate-assisted models. How to build and apply surrogate-assisted models on condition of an individual’s uncertain fitness is also a very meaningful research issue.

Advertisement

7. Acknowledgements

This work was completed when Dun-wei Gong was visiting CERCIA, School of Computer Science, the University of Birmingham. It was jointly supported by NSFC with granted No. 60775044 and Program for New Century Excellent Talents in University with granted No. NCET-07-0802.

References

  1. 1. Biles J. A. Anderson P. G. Loggi L. W. 1996 Neural network fitness functions for a musical IGA, Proceedings of International Symposium on Intelligent Industrial Automation and Soft Computing, 39 44
  2. 2. Caldwell C. Johnston V. S. 1991 Tracking a criminal suspect through’face-space’ with a genetic algorithm, Proceedings of 4th International Conference on Genetic Algorithms, 416 421 , Morgan Kaufmann
  3. 3. Dawkins R. 1986 The Blind Watchmaker, Longman, Essex, U.K.
  4. 4. Gong D. W. Hao G. S. Zhou Y. et al. 2007 Theory and Applications of Interactive Genetic Algorithms, Defense Industry Press, Beijing, China
  5. 5. Gong D. W. Zhou Y. Guo Y. N. 2008 Interactive genetic algorithms with multiple approximate models. Control Theory and Applications, 25 434 438
  6. 6. Hao G. S. Gong D. W. Shi Y. Q. et al. 2006 Method of replacing the user with machine in interactive genetic algorithm. Pattern Recognition and Artificial Intelligence, 19 111 115
  7. 7. Kim H. S. Cho S. B. 2000 Application of interactive genetic algorithm to fashion design. Engineering Applications of Artificial Intelligence, 13 635 644
  8. 8. Limbourg P. Aponte D. E. 2005 An optimization algorithm for imprecise multi-objective problem functions, Proceedings of IEEE Congress on Evolutionary Computation, 459 466 , IEEE Press
  9. 9. Liu B. K. 2005 NN global optimization based on interval optimization. Computer Engineering and Applications, 23 90 92
  10. 10. Sugimoto F. Yoneyama M. 2001 An evaluation of hybrid fitness assignment strategy in interactive genetic algorithm, Proceedings of 5th Australasia-Japan Joint Workshop on Intelligent and Evolutionary Systems, 62 69
  11. 11. Takagi H. Ohya K. 1996 Discrete fitness values for improving the human interface in an interactive GA, Proceedings of IEEE Conference on Evolutionary Computation, 109 112 , IEEE Press
  12. 12. Takagi H. 2001 Interactive evolutionary computation: fusion of the capabilities of EC optimization and human evaluation. Proceedings of the IEEE, 89 1275 1296
  13. 13. Takagi H. Ohsaki M. 2007 Interactive evolutionary computation-based hearing aid fitting. IEEE Transactions on Evolutionary Computation, 11 414 427
  14. 14. Tokui N. Iba H. 2000 Music composition with interactive evolutionary computation, Proceedings of 3rd International Conference on Generative Art, 215 226
  15. 15. Wang S. F. Wang X. F. Takagi H. 2006 User fatigue reduction by an absolute rating data-trained predictor in IEC, Proceedings of IEEE Congress on Evolutionary Computation, 2195 2200 , IEEE Press
  16. 16. Wei W. 2004 Intelligent Control Technology, Machine industrial Press, Beijing,China
  17. 17. Zhou Y. Gong D. W. Hao G. S. et al. 2005 Phase estimations of individual’s fitness based on NN in interactive genetic algorithms. Control and Decision, 20 234 236

Written By

Dun-wei Gong, Xiao-yan Sun and Jie Yuan

Published: 01 October 2009