Open access peer-reviewed chapter

Interactive Genetic Algorithms with Individual’s Uncertain Fitness

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

Published: October 1st 2009

DOI: 10.5772/9605

Downloaded: 1077

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.

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 anyx_x¯Randx_x¯, a setXsatisfyingX[x_x¯]={x|x_xx¯xR}is called a limited and closed interval, wherex_andx¯are called the lower limit and the upper limit of the interval, respectively. In case thatx_=x¯Xis called a point interval. The midpoint and the width ofXare defined as follows.

w(X)=x¯x_m(X)=x_+x¯2E1

Interval dominance (Limbourg & Aponte, 2005) For any two intervalsXi=[x_ix¯i]andXj=[x_jx¯j], there are 2 cases of their dominance relations,shown as follows.

Ifx¯ix¯jandx_ix_j, then we call thatXidominates overXjin interval, and denoteXiinXj, which is shown as Fig. 1.

Figure 1.

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

IfXj, then we call thatx"Xj:x"Xi and x'Xi:x'XjandXiis incomparable in interval, and denoteXj, 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 numberXiis a normalized, convex fuzzy set in domain U.

We call a fuzzy setXjnormalized if there exists at least an elementf˜belonging to U whose membership degreef˜is equal to 1, i.e.u

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

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

u[uiuj]U:μf˜(u)min{μf˜(ui)μf˜(uj)}E2

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

μf˜:U[01]maxuUμf˜(u)=1u[uiuj]Uμf˜(u)min{μf˜(ui)μf˜(uj)}E3

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

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

u0E4
μf˜(u0)=1-cut set Forμf˜(u)={1u=u00uu0, theα-cut set ofα(0,1), denoted asα, is a subset of U satisfying that the membership degree of its elementf˜is larger than or equal tof˜α, i.e.
uE5

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

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

f˜E6

wheref˜αandf˜α={u|μf˜(u)αuU}=[f˜α_f˜α¯]are the lower limit and the upper limit off˜α_, respectively. In particular, iff˜α¯is a single-point fuzzy number, we havef˜α, and thereforef˜is a point interval, a special interval.

We consider the following general optimization problem in this chapter:

f˜α_=f˜α¯E7

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

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 bex,x, and the population size be N. Because of the user’s fuzzy cognitive onxi, he/she hardly assignsi=1,2,N’s exact fitness, but easily assigns its range which is expressed with an interval. Thereforexi’s fitness can be described asxi, wherexiandf(xi)=[f_(xi)f¯(xi)]are the lower limit and the upper limit of the user’s evaluation onf_(xi), respectively.

It is easy to observe that the larger the lower limit off¯(xi)together with the smaller of its width is, the higher and the more exact the evaluation onxiassigned by the user is; otherwise, the smaller the upper limit off(xi)together with the larger its width is, the lower and the rougher the evaluation onxiassigned by the user is. In general, the user’s cognitive onf(xi)is fuzzy at early stage of the evolution, thereforexiis large. This cognitive will become clearer and clearer along with the evolution, and hencexiwill 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 individualsw(f(xi))andw(f(xi))xi, their interval fitness arexjandij=1,2,N, respectively. To determine which one is dominant, the following 2 cases are considered.

Case 1f(xi)=[f_(xi)f¯(xi)], in which case there are 2 possibilities.

(I)f(xj)=[f_(xj)f¯(xj)], which indicates that the lower limit of evaluation onf(xi)inf(xj)assigned by the user is not less than the upper limit of evaluation onf_(xi)f¯(xj). Therefore, it is reasonable thatxidominates overxjwith the probability of 1, and it is impossible forxito dominate overxj. In this casexjis the dominant individual in tournament selection.

(II)xi, which indicates thatxidominates overf_(xi)f¯(xj), but the lower limit of evaluation onf(xi)assigned by the user is less than the upper limit of evaluation onf(xj), 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 intervalxi, the probability ofxj’s fitness falling into this interval is[f¯(xj)f¯(xi)], wherexidominates overf¯(xi)f¯(xj)w(f(xi))with the probability of 1. And then we consider an intervalxi, the probability ofxj’s fitness falling into this interval is[f_(xi)f¯(xj)], wherexidominates overf¯(xj)f_(xi)w(f(xi))with the probability ofxi. Thereforexjdominates over0.5f¯(xj)f_(xi)w(f(xj))+f_(xi)f_(xj)w(f(xj))with the probability of

xiE8

Then the probability thatxjbecomes the dominant individual in tournament selection isp(xixj)=f¯(xi)f¯(xj)w(f(xi))+f¯(xj)f_(xi)w(f(xi))(0.5f¯(xj)f_(xi)w(f(xj))+f_(xi)f_(xj)w(f(xj)))

Similarly, we can obtain the following probability with whichxidominates overp(xixj)

xjE9

That is to say, the probability thatxibecomes the dominant individual in tournament selection isp(xjxi)=0.5f¯(xj)f_(xi)w(f(xj))f¯(xj)f_(xi)w(f(xi))

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 2xj, i.e.p(xjxi)orf(xi)||f(xj). Because off¯(xi)f¯(xj)f_(xi)f_(xj)’s randomicity, only the former is considered in this subsection, i.e.f¯(xj)f¯(xi)f_(xj)f_(xi). In the case above, it is shown that the evaluation onxiassigned by the user is incomparable with that onf¯(xi)f¯(xj)f_(xi)f_(xj), but the former is more exact. First, an intervalxiis considered. The probability ofxj’s fitness falling into this interval is[f¯(xi)f¯(xj)], wherexjdominates overf¯(xj)f¯(xi)w(f(xj))with the probability of 1. Then we consider an intervalxj, the probability ofxi’s fitness falling into this interval is[f_(xi)f¯(xi)], wherexjdominates overf¯(xi)f_(xi)w(f(xj))with the probability of 0.5. Therefore,xjdominates overxiwith the following probability

xjE10

Hence the probability thatxibecomes the dominant individual in tournament selection isp(xjxi)=f¯(xj)f¯(xi)w(f(xj))+0.5w(f(xi))w(f(xj))

Similarly, we can obtain the following probability with whichxjdominates overp(xjxi)

xiE11

That is to say, the probability thatxjbecomes the dominant individual in tournament selection isp(xixj)=0.5w(f(xi))w(f(xj))+f_(xi)f_(xj)w(f(xj))

It is easy to obtain through simple deduction thatxiin 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 onlyp(xixj)is a point interval and dominates overp(xixj)+p(xjxi)=1, we havef(xi). If onlyf(xj)is a point interval and incomparable withp(xixj)=1,p(xjxi)=0, we havef(xi)andf(xj). Similarly, if onlyp(xjxi)=f¯(xj)f(xi)w(f(xj))is a point interval and dominated byp(xixj)=f(xi)f_(xj)w(f(xj)), we havef(xj). If onlyf(xi)is a point interval and incomparable withp(xixj)=1p(xjxi)=0, we havef(xj)and

f(xi)E12

Herep(xixj)=f¯(xi)f(xj)w(f(xi))andp(xjxi)=f(xj)f_(xi)w(f(xi))are dominant individuals in tournament selection with the probability ofxiandxj, respectively. The method to perform tournament selection above is as follows. First, calculate the accumulative probabilities ofp(xixj)andp(xjxi), i.e.xi. And then generate a random number r in [0, 1]. At last, compare r withxj. Ifci=p(xixj)cj=ci+p(xjxi)=1, thenciis the dominant individual in tournament selection; otherwise,rciis 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. Letxi, 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 candidatesxjandt=0xi(t)for tournament selection, calculatexj(t)andij=1,2,Naccording to formula (2) to (5), and generate the dominant individual in tournament selection.

  5. Perform genetic operation and generate offspring. Letp(xi(t)xj(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.

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 onp(xj(t)xi(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 individualt=t+1, and express its fitness asα. We define a function inxas follows

f˜(x)E13

to express the degree of a[fminfmax]belonging toμf˜(x)[fminfmax][01], wheref[fminfmax]andf˜(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 offmin, i.e. there exists at least one number infmaxwhich is[fminfmax]’s real fitness, i.e. its membership degree w.r.t.[fminfmax]is 1. Therefore,xis normalized. In addition, the further a number inf˜(x)fromf˜(x)’s real fitness is, the smaller its membership degree w.r.t.[fminfmax]should be. Therefore,xis 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 off˜(x)as follows:

f˜(x)E14

wheref˜(x)isμf˜(x)(f)=e12(fc(x)σ(x))2’s center, it is the fitness whose membership degree w.r.t.c(x)is 1.f˜(x)isf˜(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 abovef˜(x)’s fuzzy fitness as follows.

In general, for different individuals, the membership functions of their fitness have different centers and width, i.e. for1/e0.6, we havex

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 generationxixjSxixj, i.e. forc(xi)c(xj)σ(xi)σ(xj), we may havet0titjTtitj, 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. forc(xti)c(xtj), we haveσ(xti)σ(xtj)

0titjTE15

Ifxσ(xti)xσ(xtj), we havexc(xti)xc(xtj), whereas iff=c(x)andμf˜(x)(f)=e12(fc(x)σ(x))2=1, we havefc(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)0andμf˜(x)(f)=e12(fc(x)σ(x))2=0, butc(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 inputc(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 calculatesc(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 levelxσ(xt)xc(xt), 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αbexiandxj, and their membership functions bef˜(xi)andf˜(xj), respectively. Theμf˜(xi)(f)=e12(fc(xi)σ(xi))2-cut sets ofμf˜(xj)(f)=e12(fc(xj)σ(xj))2and

αE16
are

f˜(xi)E17

respectively, where bothf˜(xj)andf˜α(xi)={f|μf˜(xi)(f)αf[fminfmax]}[f˜α(xi)_f˜α(xi)¯]f˜α(xj)={f|μf˜(xj)(f)αf[fminfmax]}[f˜α(xj)_f˜α(xj)¯]are crisp sets, and reflect that the fitness lying in which belongs tof˜α(xi)andf˜α(xj)respectively with the membership degree being not less thanf˜(xi), or the value lying inf˜(xj)andαis the fitness off˜α(xi)andf˜α(xj)respectively with the confidence degree being not less thanxi

According to the positions ofxjandα, there are two cases whenμf˜(xi)compares withμf˜(xj)

Case 1xi, in which case there are two possibilities.

The first one isxjandc(xi)=c(xj), which indicates thatc(xi)=c(xj), i.e. the fitness ofσ(xi)=σ(xj)is the same as that off˜(xi)=f˜(xj). Therefore,xidominatesxjwith the probability of 0.5, and so doesxi

Figure 3.

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

The second one isc(xi)=c(xj)butσ(xi)σ(xj). For not losing generality, we only consider the case thatc(xi)=c(xj)butσ(xi)σ(xj), shown as Fig. 3. The comparison betweenc(xi)=c(xj)andσ(xi)σ(xj)atxilevel is equal to the comparison betweenxjand

αE19

Similar to the deduction in subsection 3.3, we can easily obtain thatf˜α(xi)dominates overf˜α(xj)with the probability of

xjE20
Andxidominates overp(xjxi)=f˜α(xj)¯f˜α(xi)¯+0.5w(f˜α(xi))w(f˜α(xj))=0.5with the following probability
xiE21

Case 2xj. For not losing generality, we only consider the case thatp(xixj)=0.5w(f˜α(xi))+f˜α(xi)_f˜α(xj)_w(f˜α(xj))=0.5. Letc(xi)c(xj). We will discuss the following two cases based on the relationship betweenc(xi)c(xj)and

α0=maxf[fminfmax]μf˜(xi)f˜(xj)(f)E22

Ifα, shown as Fig. 4, we haveα0, which indicates that atαα0level the lower limit of evaluation onf˜α(xj)_f˜α(xi)¯is larger than the upper limit of evaluation onα. Therefore it is reasonable thatxjdominates overxiwith the probability of 1, and it is impossible thatxjdominates overxi

Figure 4.

Two individuals’ fitness on condition of xi and xj

Ifc(xi)c(xj), shown as Fig. 5, we haveαα0, which indicates that thoughαα0dominates overf˜α(xj)_f˜α(xi)¯, atf˜α(xj)level the lower limit of evaluation onf˜α(xi)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 thatxjdominates overxiwith the probability of
xjE24
Andxidominates overp(xjxi)=f˜α(xj)¯f˜α(xi)¯w(f˜α(xj))+f˜α(xi)¯f˜α(xj)_w(f˜α(xj))(10.5f˜α(xi)¯f˜α(xj)_w(f˜α(xi)))with the following probability
xiE25

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 thatxjis a single-point fuzzy number, i.e.p(xixj)=0.5(f˜α(xi)¯f˜α(xj)_)2w(f˜α(xi))w(f˜α(xj)). Iff˜(xi), we havef˜α(xi)¯=f˜α(xi)_; Iff˜α(xi)¯=f˜α(xi)_f˜α(xj)¯, we havep(xixj)=1,p(xjxi)=0; Iff˜α(xj)_f˜α(xi)¯=f˜α(xi)_f˜α(xj)¯, we havep(xjxi)=f˜α(xj)¯f˜α(xi)¯w(f˜α(xj))p(xixj)=f˜α(xi)_f˜α(xj)_w(f˜α(xj))

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 betweenc(xi)c(xj)andαα0that what determines an individual to be the dominant one in tournament selection isxiandxj. For case 2 both dominance probabilities have close relation withp(xixj)-cut set. Even if we have the same fuzzy set, differentp(xixj)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+tT,1}tTset 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)andt=0xi(t)for tournament selection, calculatexj(t)andij=1,2,Naccording to formula (7) to (10), and generate the dominant individual in tournament selection.

  5. Perform genetic operation and generate offspring. Letp(xi(t)xj(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.

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 withp(xj(t)xi(t))suits during evolutionary optimization.

colorcodecolorcode
black0000gray1000
blue0001bright blue1001
green0010bright green1010
cyan0011bright cyan1011
red0100bright red1100
carmine0101bright carmine1101
yellow0110bright yellow1110
white0111bright white1111

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 sizet=t+1is equal to 8. In order to express an individual’s fuzzy fitness, a scroll bar is adopted to set25×25×24×24=262144, and its range is restricted between 0 and 1000, i.e.Nandc(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 probabilitiesfminandfmaxare 0.6 and 0.02, respectively. In addition,pcand 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 ofpmbeing 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)andxσ(xt)xc(xt)in each generation. Their averages of the 8 runs are shown as Fig. 9.

generationssum of width of interval fitnesssum of midpoints of interval fitness
150124100
249704404
340754437
437914265
538544870
630675167
729975411
823735268
926475031
1027075923
1120715966
1219256148
1317976264
1415776629
1511736611

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 ofxσ(xt)andxc(xt)change with t.xσ(xt)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,xc(xt)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 runIGA-IIFIGA-IFFTIGA
17’48“3’42“5’40“
23’00“4’15“4’02“
36’10“3’34“6’58“
48’33“5’11“7’44“
53’44“3’53“3’10“
63’41“4’50“5’02“
73’53“3’02“5’49“
85’17“3’47“6’15“
sum42’06“32’14“44’40“

Table 3.

Time-consuming for evaluating individuals

No. of runIGA-IIFIGA-IFFTIGA
1814559
2285942
3654663
4969386
5356539
6386845
7394156
8626269
sum444479459

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.

algorithmfor evaluating individuals in each runfor evaluating an individual
IGA-IIF5’16“5.7“
IGA-IFF4’02“4.0“
TIGA5’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 isxσ(xt). The success rate of different algorithms within different time is listed as Table 6.

algorithmwithin 5’within 7’within 9’
IGA-IIF5075100
IGA-IFF87.5100100
TIGA2587.5100

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

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 onxc(xt)-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.

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.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Dun-wei Gong, Xiao-yan Sun and Jie Yuan (October 1st 2009). Interactive Genetic Algorithms with Individual’s Uncertain Fitness, Evolutionary Computation, Wellington Pinheiro dos Santos, IntechOpen, DOI: 10.5772/9605. Available from:

Embed this chapter on your site Copy to clipboard

<iframe src="http://www.intechopen.com/embed/evolutionary-computation/interactive-genetic-algorithms-with-individual-s-uncertain-fitness" />

Embed this code snippet in the HTML of your website to show this chapter

chapter statistics

1077total chapter downloads

2Crossref citations

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

A Genetic Algorithm for Optimizing Hierarchical Menus

By Shouichi Matsui and Seiji Yamada

Related Book

First chapter

Novel Binary Particle Swarm Optimization

By Mojtaba Ahmadieh Khanesar, Hassan Tavakoli, Mohammad Teshnehlab and Mahdi Aliyari Shoorehdeli

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More about us