Mobile Edition
Print
Get the Mag
Weekly Updates1. Introduction
Reliability optimization is very important in system design. Usually, a single-objective optimization model is formulated. For example, system reliability may be maximized subject to resource constraints, or cost may be minimized subject to reliability requirements. To achieve the best system design, it is often desirable to simultaneously maximize system reliability and minimize resource consumption. In this case, it is better to adopt a multi-objective approach to system design (Kuo and Prasad, 2000). In solving multi-objective optimization problems, the decision maker must have a sufficient number of desirable optimal solutions to choose from. However, multiple objectives and various constraints make it difficult to simultaneously solve this type of problem.
Currently available approaches may combine multiple objectives into a single objective, treat the objectives as penalties, or apply interactive techniques to reduce the size of the optimization problem. Dhingra (1992) and Rao and Dhingra (1992) studied a reliability and redundancy allocation problem for a four-stage and a five-stage over-speed protection system, using crisp and fuzzy multi-objective optimization approaches, respectively. Li (1996) proposed a Genetic Algorithm (GA) approach for multi-objective reliability design problems maximizing the reliability and minimizing the total cost of the system. Gen and Kim (1998, 1999a, 1999b) proposed a hybrid GA approach to handle multi-objective reliability-redundancy allocation problems and compared it with the GA approach reported by Li (1996). Huang et al. (2004) and Huang, Tian and Zuo (2005) developed an interactive physical programming approach and applied it to a reliability and redundancy allocation problem. Huang (1997) also reported a fuzzy multi-objective optimization decision-making method for a series system. Salazar et al. (2006) solved constrained multiple-objective reliability optimization problems by using a second-generation multiple-objective evolutionary algorithm. Coit and Konak (2006) proposed a multiple weighted objectives heuristic for a redundancy allocation problem based on the transformation of a multiple objective problem into a single-objective problem. For other related papers see Huang, Wu and Liu (2005), Ha and Kuo (2006), Huang et al. (2006), Liang and Chen (2007), Onishi et al. (2007) and Yun et al. (2007). In this paper we introduce a direct approach that uses GAs to solve multi-objective optimization problems.
GAs can be viewed as a probabilistic approach based on the principle of natural evolution. Their advantage over other methods, such as exact algorithms and heuristic algorithms, is that they can simultaneously manipulate the entire population of solutions to the optimization problem. This property makes it possible to approximate the whole Pareto frontier in a single optimization run for a multi-objective optimization problem.
Fonseca and Fleming (1995) provided an overview of GAs for multi-objective optimization. Deb et al. (2002) proposed a fast and elitist multi-objective GA. Horn and Nafpliotis (1993) and Horn et al. (1994) proposed the niched Pareto GA for multi-objective problems that is now used in many areas. Erickson and Horn (2002) applied a niched Pareto GA to simultaneously minimize remedial design cost and contaminant mass. Zheng et al. (2005) applied the Pareto ranking and niche formation to GA-based multi-objective time-cost optimization.
Since GAs are appropriate for high-dimension stochastic problems with many non-linearities or discontinuities, they are suited to solving reliability-based design problems. In this paper, we propose an algorithm that combines a population-based constraint handling method and a niched Pareto GA based on Pareto tournament and equivalence sharing to solve optimal reliability-redundancy allocation problems.
2. Problem statement
The reliability optimization model considered in this paper is obtained by transforming the single-objective optimization model of an over-speed protection system reported by Dhingra (1992) into a multi-objective optimization model. Its objective functions are maximizing system reliability and minimizing system cost, subject to limits on weight and volume.
Notation
[R.sub.i] = reliability of a component at stage i;
[n.sub.i] = number of redundant components at stage i;
[R.sub.s] = system reliability;
[C.sub.s] = total system cost;
[W.sub.s] = total system weight;
[V.sub.s] = total system volume;
N = number of stages;
[W.sub.lim] = upper limit on weight;
[V.sub.lim] = upper limit on volume;
[w.sub.i] = the weight of each component in stage i;
[v.sub.i] = the volume of each component in stage i;
[[alpha].sub.i], [[beta].sub.i] = constants representing the physical characteristics of each component at stage i;
T = operating time.
The model takes the following form:
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)
[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)
subject to
[W.sub.s] = [N.summation over i][w.sub.i] X [n.sub.i] X exp([n.sub.i]/4)[less than or equal to] [W.sub.lim], (3)
[V.sub.s] = [N.summation over i][[upsilon].sub.i] X [([n.sub.i]).sup.2] [less than or equal to] [V.sub.lim], (4)
1 [less than or equal to] [n.sub.i] [less than or equal to] [n.sub.max], [R.sub.min] [less than or equal to] [R.sub.i] [less than or equal to] [R.sub.max], i = 1,2, ..., N, (5)
where exp([n.sub.i]/4) accounts for the interconnecting hardware, [n.sub.max] represents the maximum number of components allowed at each stage and [R.sub.max] and [R.sub.max] the minimum and maximum reliability limits of each component. The parameters [[alpha].sub.i] and [[beta].sub.i] provide flexibility in expressing the cost of the system as a function of the number of components [n.sub.i] at each stage i, the mission time T and the component reliability level [R.sub.i] at stage i. The adopted cost function form is as proposed by Dhingra (1992). It is adopted here for ease of comparison of the proposed algorithm with those used in Dhingra (1992). Our approach, however, is more general. When applying our approach, one should use a cost function appropriate to the specific application.
3. Multi-objective GA
GAs have been widely used to solve multi-objective optimization problems. Two factors that must be considered in such cases are fitness assignment and fitness sharing.
Fitness assignment provides a criterion for assessing the fitness of an individual solution. The Pareto ranking method, which is usually applied for this purpose, relies on the notion of dominance, that is, a better solution must have better objective function values. The concept of Pareto optimality can be used here for ranking individual solutions. A solution to a multi-objective optimization problem is called Pareto optimal if no objective can be improved without sacrificing another objective. A more formal definition of Pareto optimality is as follows (Fonseca and Fleming, 1995).
Definition 1. Without loss of generality, consider the maximization of n elements [f.sub.k], k = 1, ..., n, of vector function (f) with vector variable (x) in a universe (u), where:
f(x) = ([f.sub.1](x), ..., [f.sub.n](x)). (6)
Then, a decision vector, s [member of] u, for which g = f(s) = ([g.sub.1], . ..., [g.sub.n]), dominates another decision vector, t [member of] u, for which h = f(t) = ([h.sub.1], ..., [h.sub.n]), if
[for all] i [member of] {1, ..., n}, [h.sub.i] [less than or equal to] [g.sub.i] [conjunction] [there exists] i [member of] {1, ..., n}|[h.sub.i]< [g.sub.i]. (7)
A decision vector is said to be Pareto optimal if it is not dominated by any other decision vectors. The set of all Pareto optimal decision vectors is called the admissible set of the problem. The corresponding set of objective vectors is called the non-dominated set.
By definition, the Pareto ranking method ranks all the individuals and then assigns a fitness value to each of them. The individuals that are non-dominated are assigned larger fitness values, so they will be copied more than the others in GA procedures.
The Pareto tournament method also uses the dominance notion. It chooses two individuals from the population at random, and then selects the better one to be included in the next generation. It is different from the Pareto ranking method in that it does not actually assign fitness values to individuals, so it is less complicated. As the commonly used pair-wise tournament method may generate more dominated solutions in the final population, an improved Pareto tournament method is used in this paper.
Other methods of fitness assignment include the weight-based method, the compromise-based method and the goal programming method (Gen and Cheng, 2000).
Fitness sharing refers to maintaining the diversity of the Pareto optimal solutions. Fitness sharing aims to provide Pareto optimal solutions over the entire non-dominated frontier. It ensures a set of diversified Pareto solutions.
The sharing scheme is designed to spread the population of individuals along the Pareto frontier by penalizing individuals that are already strongly represented in the population. There are two types of sharing: sharing in the objective space and sharing in the variable space. These approaches provide diversity of Pareto solutions in the objective space and the variable space, respectively. We calculate the following indicator for individual i (Horn and Nafpliotis, 1993):
[m.sub.i] = [pop-size.summation over(j=1)] sh([d.sub.ij]), (8)
where [m.sub.i] is the niche count of individual i, which is an estimate of how crowded the neighborhood (niche) of individual i is; [d.sub.ij], usually calculated by the pth. order norm (for example, p = 2), is the distance between individuals i and j; and sh(*) represents the following sharing function:
FEED