![]() |
Fusion of Neural Networks, Fuzzy Systems and Genetic Algorithms: Industrial Applications
by Lakhmi C. Jain; N.M. Martin CRC Press, CRC Press LLC ISBN: 0849398045 Pub Date: 11/01/98 |
Previous | Table of Contents | Next |
In the absence of any information regarding the relative importance of design objectives, Pareto-dominance is the only method of determining the relative performance of solution estimates. Nondominated individuals are all therefore considered to be best performers and are thus assigned the same fitness [9], e.g., zero. However, determining a fitness value for dominated individuals is a more subjective matter. The approach adopted here is to assign a cost proportional to how may individuals in a population dominate a given individual, Figure 3. In this case, nondominated individuals are all treated as desirable.
If goal and/or priority information is available for the design objectives, then it may be possible to differentiate between some nondominated solutions. For example, if degradations in individual objectives still allow those goals to be satisfied while also allowing improvements in other objectives that do not already satisfy their design goals, then these degradations should be accepted. In cases where different levels of priority may be assigned to the objectives then, in general, it is important to improve only the high priority objectives, such as hard constraints, until the corresponding design goals are met, after which improvements may be sought in the lower priority objectives.
Figure 3 Pareto ranking.
These considerations have been formalized in terms of a transitive relational operator, preferability, based on Pareto-dominance, which selectively excludes objectives according to their priority and whether or not the corresponding goals are met [15]. For simplicity only one level of priority is considered here. Consider two objective vectors u and v and the corresponding set of design goals, g. Let the smile denote the components of u that meet their goals and the frown
those that do not. Assuming minimization, one may then write
where the inequalities apply component wise. This is equivalent to,
where ui and gi represent the components of u and g, respectively. Then, u is said to be preferable to v given g if and only if
where a b is used to denote that a dominates b. Hence u will be preferable to v if and only if one of the following is true:
After a cost has been assigned to each individual, selection can take place in the usual way. Suitable schemes include rank-based cost-to-fitness mapping [16] followed by stochastic universal sampling [17] or tournament selection, also based on cost, as described by Ritzel et al. [18].
Exponential rank-based fitness assignment is illustrated in Figure 4. Here, individuals are sorted by their cost in this case the values from Figure 3 and assigned fitness values according to an exponential rule in the first instance, shown by the narrow bars in Figure 4. A single fitness value is then derived for each group of individuals sharing the same cost, through averaging, and is shown in the figure by the wider bars.
Figure 4 Rank-based fitness assignment.
Even though all preferred individuals in the population are assigned the same level fitness, the number of offspring that they will produce, which must obviously be integer, may differ due to stochastic nature of EAs. Over generations, these imbalances may accumulate resulting in the population focusing on an arbitrary area of the trade-off surface, known as genetic drift [19]. Additionally, recombination and mutation may be less likely to produce individuals at certain areas of the trade-off surface, e.g., the extremes, giving only a partial coverage of the trade-off surface.
Originally introduced as an approach to sampling multiple fitness peaks, fitness sharing [20] helps counteract the effects of genetic drift by penalizing individuals according to the number of other individuals in their neighborhood. Each individual is assigned a niche count, initially set to zero, which is incremented by a certain amount for every individual in the population, including itself. A sharing function determines the contribution of other individuals to the niche count as a function of their mutual distance in genotypic, phenotypic, or objective space. Raw fitness values are then weighted by the inverse of the niche count and normalized by the sum of the weights prior to selection. The total fitness in the population is redistributed, and thus shared, by the population. However, a problem with the use of fitness sharing is the difficulty in determining the niche size, σshare, i.e., how close together individuals may be before degradation occurs.
An alternative, but analogous, approach to niche count computations are kernel density estimation methods [21] as used by statisticians. Instead of a niche size, a smoothing parameter, h, whose value is also ultimately subjective, is used. However, guidelines for the selection of suitable values for h have been developed for certain kernels, such as the standard normal probability density function and Epanechnikov kernels. The Epanechnikov kernel may be written as [21]
where n is the number of decision variables, cn is the volume of the unit n-dimensional sphere, and d/h is the normalized Euclidean distance between individuals. Apart from the constant factor, , this kernel is a particular case of the family of power law sharing functions proposed by Goldberg and Richardson [20].
Silverman [21] gives a smoothing factor that is approximately optimal in the least mean integrated squared error sense when the population follows a multivariate normal distribution for the Epanechnikov kernel Ke(d) as
for a population with N individuals and identity covariance matrix. Where populations have an arbitrary sample covariance matrix, S, this may simply be sphered, or normalized, by multiplying each individual by a matrix R such that RRT = S-1. This means that the niche size, which depends on S and h, may be automatically and constantly updated, regardless of the cost function, to suit the population at each generation.
Previous | Table of Contents | Next |