2014_421_Vasilenko_ImmuneAlgorithm_based approach for redundant reliability problems with multiple component choices (Задание 5)

Computers in Industry 56 (2005) 195–205www.elsevier.com/locate/compindImmune algorithms-based approach for redundant reliabilityproblems with multiple component choicesTa-Cheng Chena,*, Peng-Sheng YoubabDepartment of Information Management, National Formosa University, Huwei, Yulin 632, TaiwanGraduate Institute of Transportation and Logistics, National Chia-Yi University, Chia-Yi 600, TaiwanReceived 3 March 2003; received in revised form 3 November 2003; accepted 28 June 2004Available online 16 December 2004AbstractThis paper considers the series–parallel redundant reliability problems in which both the multiple component choices of eachsubsystem and the redundancy levels of every selected component are to be decided simultaneously so as to maximize the systemreliability.

The reliability design optimization problem has been studied in the literature for decades, usually using mathematicalprogramming or heuristic optimization approaches. The difficulties encountered for both methodologies are the number ofconstraints and the difficulty of satisfying the constraints. A penalty-guided immune algorithms-based approach is presented forsolving such integer nonlinear redundant reliability design problem.

The results obtained by using immune algorithms-basedapproach are compared with the results obtained from 33 test problems from the literature that dominate the previouslymentioned solution techniques. As reported, solutions obtained by the proposed method are better than or as well as thepreviously best-known solutions.# 2004 Elsevier B.V.

All rights reserved.Keywords: Redundant reliability problem; Immune algorithms; Optimization1. IntroductionThe system reliability optimization is very important in the real-world applications and the variouskinds of systems have been studied in the literature fordecades. Generally, as Misra and Sharma [1] mentioned, two main approaches are used to enhance thesystem reliability. One of the approaches is to increase* Corresponding author. Tel.: +886 5 6315740;fax: +886 5 6364127.E-mail address: tchen@nfu.edu.tw (T.-C. Chen).the reliability of the elements constituted in thesystem, and the other is the use of redundant elementsin various subsystems in the system. In the formerapproach, the system reliability can be enhanced tosome degree, but the required enhancement of thereliability may be never attainable even though themost currently reliable elements are used.

Use of thelater approach is to select the optimal combination ofelements and redundancy levels; the system can alsobe enhanced, but the cost, weight, volume, etc. will beincreased as well. In addition to the above twoapproaches, the combination of the two approaches0166-3615/$ – see front matter # 2004 Elsevier B.V. All rights reserved.doi:10.1016/j.compind.2004.06.002196T.-C.

Chen, P.-S. You / Computers in Industry 56 (2005) 195–205Nomenclatureai,j,kbjkinqi,kxi,kthe jth resource requirement associated withtype k component of subsystem i, whereai,j,k > 0the limitation on the jth resourcethe number of component choices for subsystem i, 1 i nthe number of subsystem in the systemthe failure probability of type k componentin subsystem ithe number of type k components in subsystem iand reassignment of interchangeable elements arealso feasible ways for increasing the system reliability[2].Based on the above two main approaches, two maincategories of reliability design problems, the integerand mixed integer problems, are investigated. Theseries–parallel system problem with known component reliabilities for determining the redundancyallocation belongs to integer reliability problems, inwhich the decision variables are constrained to integervalue [3–7].

For the mixed-integer reliability problems, component reliabilities and redundancy allocation are to be decided simultaneously [1,4,8–10]. Inthe formulation of the series–parallel system problemconsidered in this paper, for each subsystem, multipleelements choices are used in parallel. The problem isthen to choose the optimal combination of elementsand redundancy levels to meet two constraints withcost and weight, respectively. With the known cost,reliability and weight for each element, the systemdesign and elements selection of problem becomes acombinatorial optimization problem.

Moreover, suchredundancy allocation problem for series–parallelsystems considered in this paper has been showed thatthis is an NP hard problem [11]. For solving thisdifficult problem, the most used integer programmingtechniques in literatures are generally classified intothree categories that are approximate techniques,exact techniques and heuristic/meta-heuristic techniques [2,12]. The approximate techniques are such asthe uses of Lagrangian multiplier and geometricprogramming. Kuo et al. [13] used the branch-andbound strategy and Lagrangian multipliers, and Misraand Sharma [1] used the geometric programming forfinding the nearest integers.

To a problem, the exacttechniques are the methods which can provide anexact optimal solution. For example, the use ofdynamic programming for maximizing the systemreliability with a single cost-constraint [14]. Fyffeet al. [15] used the same method to solve more difficultdesign problem where a system with 14 subsystemsand the cost and weight constraints are considered.Furthermore, improved dynamic programming algorithm was presented by Nakagawa and Miyazaki [4]with the use of surrogate constraints for the problemwith above two constraints. The heuristic techniquesare the intuitive procedure for obtaining the nearoptimal solutions in a reasonably short time.

Amajority of the recent work in the problem is devotedto developing heuristic and meta-heuristic algorithmsfor solving the optimal redundancy allocation problems [2]. Several heuristic methods have beensuggested in literatures for the redundant allocationproblems [16,17]. The meta-heuristics methods, basedmore on artificial intelligence than traditionalmathematic programming methods, include geneticalgorithms (GAs), simulated annealing, Tabu search,fuzzy optimization approach, etc. Recently, thegenetic algorithm has been widely and successfullyapplied for solving the system reliability problem[18,5,6,10].A new meta-heuristic optimization approachemploying immune algorithms (IAs) to solve theredundant allocation problem is proposed in thispaper. The merits of immune algorithms lie in patternrecognition, memorization capabilities [19] and thetheory was originally proposed by Jerne [20].Compared with other meta-heuristic approaches suchas genetic algorithms and evolution strategies, theimmune algorithms-based approach has very distinctcharacteristics: (1) the diversity is embedded bycalculating the affinity and (2) the self-adjustment ofthe immune response is accomplished by the boost orrestriction of antibody generations.

These characteristics are also the advantages for solving thecombinatory problems because: (1) the diversitiesof the feasible spaces can be better ensured, i.e., theglobal optimum can be more likely achieved and (2) apopulation of antibodies in IAs can operate simultaneously so that the possibility of paralysis in the wholeprocess can be reduced.T.-C. Chen, P.-S. You / Computers in Industry 56 (2005) 195–205This paper is arranged as follows: in the nextsection the series–parallel redundant reliability problem is briefly described; in Section 3, the generalconcept of an immune algorithms-based approach isdescribed and numerical examples of 33 variousproblems are solved and discussed in Section 4.Finally, the conclusion of the paper is summarized.2.

Model description and assumptionsFor integer reliability problems, both the type ofcomponent and number of the selected type ofcomponent, i.e., the redundancy allocations for eachsubsystem are to be decided simultaneously. Themodel of the series–parallel redundant reliabilitysystem with n subsystems and m separable linearconstraints is considered and stated as the followinginteger nonlinear programming problem:max RðxjqÞ ¼nYxi;kxxð1 qi;1i;1 qi;2i;2 ; .

. . ; qi;kii Þ(1)i¼1s:t:kin XXai;j;k xi;k bj ;j ¼ 1; 2; . . . ; m(2)i¼1 k¼1xi;k 2 non-negative integer(3)It is noted that the problem generalizes the generalseries–parallel reliability problems when ki = 1 fori = 1, 2, . . ., n [7].In the above model of a series–parallel systemproblem considered in this paper, for each of nsubsystems, k component choices are used in parallel.Then, the overall system is connected in series bythese n subsystems with the limited resources tomaximize whole system reliability. An example isshown in Fig.

1. The overall system includes 14subsystems (n = 14) with weight and cost limitationare 186 and 130, respectively. The correspondinginput data are described in Table 1. In Fig. 1, it showsthat the first subsystem contains three components ofchoice 3, the second subsystem contains two components of choice 1, and so on.

The reliability of theoverall system is 0.9841755.As previous investigations, the approximate techniques such as Lagrangian multiplier and geometricprogramming used for solving the global optimumallocation are generally time-consuming due to the197complex transformation and the integer solutions arenot necessarily optimal any longer. Moreover, theexact solutions for the reliability optimizationproblems are not necessarily desirable because it isvery hard to obtain the exact solutions, and even whenthey are available, their utility may become marginal[2]. Because of difficulties of applying the approximate and exact techniques, a major part of thework on solving the reliability optimizations isdevoted to developing heuristic/meta-heuristic algorithms.