W. Kuo, R. Wan - Recent Advances in Optimal Reliability Allocation, страница 6
Описание файла
PDF-файл из архива "W. Kuo, R. Wan - Recent Advances in Optimal Reliability Allocation", который расположен в категории "". Всё это находится в предмете "надёжность программного обеспечения" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 6 страницы из PDF
It also showsthat the search process described in [95] does not necessarily give an exactoptimal solution due to its logical flows.Ref [83] develops a strong Lin & Kuo heuristic to search for an ideal allocation through the application of the reliability importance. It concludes that,if there exists an invariant optimal allocation for a system, the optimalallocation is to assign component reliabilities according to B-importanceordering. This Lin & Kuo heuristic can provide an exact optimal allocation.Assuming the existence of a convex and differential reliability costfunction C i ( y ij ) , y ij = log(1 − rij ) for all component j in any subsystem i,Ref [27] proves that the components in each subsystem of a series-parallelsystem must have identical reliability for the purpose of cost minimization.The solution of the corresponding unconstrained problem provides the upper bound of the cost, while a doubly minimization problem gives its lowerbound.
With these results, the algorithm ECAY, which can provide eitherexact or approximate solutions depending on different stop criteria, is proposed for series-parallel systems.1.4.3 Other Optimization TechniquesFor series-parallel systems, Ref [104] formulates the reliabilityredundancy optimization problem with the objective of maximizing theminimal subsystem reliability.Problem 5 (P5):max (min (1 − ∏ (1 − rij ) ij ))xx1 , x 2 ,...ijs.t.g i (x) ≤ bi ,x∈Xfor i = 1,...m24Way Kuo and Rui WanAssuming linear constraints, an equivalent linear formulation of P5 [36]can be obtained through an easy logarithm transformation, and, thus, theproblem can be solved by readily available commercial software.
It canalso serve as a surrogate for traditional reliability optimization problemsaccomplished by sequentially solving a series of max-min subproblems.Ref [51] presents a comparison between the Nakagawa and Nakashimamethod [43] and the max-min approach used by Ramirez-Marquez fromthe standpoint of solution quality and computational complexity. Theexperimental results show that the max-min approach is superior to theNakagawa and Nakashima method in terms of solution quality in smallscale problems, but the analysis of its computational complexity demonstrates that the max-min approach is inferior to other greedy heuristics.Ref [129] develops a heuristic approach inspired by the greedy methodand a GA. The structure of this algorithm includes:1.
randomly generating a specified population size number of minimumworkable solutions;2. assigning components either according to the greedy method or to therandom selection method;3. improving solutions through an inner-system and inter-system solutionrevision process.Ref [97] applies a hybrid dynamic programming/ depth-first search algorithm to redundancy allocation problems with more than one constraint.Given the tightest upper bound, the knapsack relaxation problem is formulated with only one constraint, and its solution f1(b) is obtained by a dynamic programming method.
After choosing a small specified parameter e,the depth-first search technique is used to find all near-optimal solutionswith objectives between f1(b) and f1(b) - e. The optimal solution is given bythe best feasible solution among all of the near-optimal solutions.Ref [127] also presents a new dynamic programming method for a reliability-redundancy allocation problem in series-parallel systems wherecomponents must be chosen among a finite set. This pseudo-polynomialYCC algorithm is composed of two steps: the solution of the subproblems, one for each subsystem, and the global resolution using previousresults. It shows that the solutions converge quickly toward the optimumas a function of the required precision.Recent Advances in Optimal Reliability Allocation251.5 Comparisons and Discussions of AlgorithmsReported in LiteratureIn this section, we provide a comparison of several heuristic or metaheuristic algorithms reported in the literature.
The compared numerical results are from the GA in Coit and Smith [10], the ACO in Liang and Smith[81], TS in Kulturel-Konak et al. [41], linear approximation in Hsieh [36],the IA in Chen and You [9] and the heuristic method in You and Chen[129]. The 33 variations of the Fyffe et al. problem, as devised by Nakagawaand Miyazaki [96], are used to test their performance, where different typesare allowed to reside in parallel. In this problem set, the cost constraint ismaintained at 130 and the weight constraint varies from 191 to 159.As shown in Table 4, ACO [81], TS [41], IA [36] and heuristic methods[129] generally yield solutions with a higher reliability. When compared toGA [10],• ACO [81] is reported to consistently perform well over different problem sizes and parameters and improve on GA’s random behavior;• TS [41] results in a superior performance in terms of best solutionsfound and reduced variability and greater efficiency based on the number of objective function evaluations required;• IA [9] finds better or equally good solutions for all 33 test problems, butthe performance of this IA-based approach is sensitive to valuecombinations of the parameters, whose best values are case-dependentand only based upon the experience from preliminary runs.
And moreCPU time is taken by IAs;• The best solutions found by heuristic methods [129] are all better than,or as good as, the well-known best solutions from other approaches.With this method, the average CPU time for each problem is within 8seconds;• In terms of solution quality, the proposed linear approximation approach[36] is inferior. But it is very efficient and the CPU time for all of thetest problems is within one second;• If a decision-maker is considering the max-min approach as a surrogatefor system reliability maximization, the max-min approach [104] isshown to be capable of obtaining a close solution (within 0.22%), but itis unknown whether this performance will continue as problem sizes become larger.For all the optimization techniques mentioned above, it might be hard todiscuss about which tool is superior because in different design problems26Way Kuo and Rui Wanor even in a same problem with different parameters, these tools will perform variously.Table 4.
Comparison of several algorithms in the literature. Each for the testproblems form [96]W191190189188187186185184183182181180179178177176175174173172171170169168167166165164163162161160159System Reliability[10]GA0.986700.985700.985600.985000.984400.983600.983100.982300.981900.981100.980200.979700.979100.978300.977200.976400.975300.974350.973620.972660.971860.970760.969220.968130.966340.965040.963710.962420.960640.959120.958030.955670.95432[81]ACO0.98680.98590.98580.98530.98470.98380.98350.98300.98220.98150.98070.98030.97950.97840.97760.97650.97570.97490.97380.97300.97190.97080.96930.96810.96630.96500.96370.96240.96060.95920.95800.95570.9546[41]TS0.986810.986420.985920.985380.984690.984180.983510.983000.982260.981520.981030.980290.979510.978400.977470.976690.975710.974790.973830.973030.971930.970760.969290.968130.966340.965040.963710.962420.959980.958210.956920.95560.95433[36]Hsieh0.986710.986320.985720.985030.984150.983880.983390.98220.981470.979690.979280.978330.978060.976880.97540.974980.97350.972330.970530.969230.96790.966780.965610.964150.962990.961210.959920.95860.957320.955550.95410.952950.9508[9]IA0.986810.986420.985920.985330.984450.984180.983440.98270.982210.981520.981030.980290.979510.978210.977240.976690.975710.974690.973760.973030.971930.970760.969290.968130.966340.965040.963710.962420.960640.959190.958040.955710.95457[129]Y&C0.986810.986420.985920.985380.984690.984180.983500.982990.982260.981520.981030.980290.979500.978400.977600.976690.975710.974930.973830.973030.971930.970760.969290.968130.966340.965040.963710.962420.960640.959190.958030.955710.95456Recent Advances in Optimal Reliability Allocation27Generally, if computational efficiency is of most concern to designer,linear approximation or heuristic methods can obtain competitive feasiblesolutions within a very short time (few seconds), as reported in [36, 129].The proposed linear approximation [36] is also easy to implement with anyLP software.
But the main limitation of those reported approaches is thatthe constraints must be linear and separable.Due to their robustness and feasibility, meta-heuristic methods such asGA and recently developed TS and ACO could be successfully applied toalmost all NP-hard reliability optimization problems. However, they cannot guarantee the optimality and sometimes can suffer from the prematureconvergence situation of their solutions because they have many unknownparameters and they neither use a prior knowledge nor exploit local searchinformation. Compared to traditional meta-heuristic methods, a set of promising algorithms, hybrid GAs [33-34, 48-50, 132-133], are attractivesince they retain the advantages of GAs in robustness and feasibility butsignificantly improve their computational efficiency and searching abilityin finding global optimum with combining heuristic algorithms, neuralnetwork techniques, steepest decent methods or other local search methods.For reliability optimization problems, exact solutions are not necessarilydesirable because it is generally difficult to develop exact methods for reliability optimization problems which are equivalent to methods used fornonlinear integer programming problems [45].
However, exact methodsmay be particularly advantageous when the problem is not large. Andmore importantly, such methods can be used to measure the performanceof heuristic or meta-heuristic methods.1.6 Conclusions and DiscussionsWe have reviewed the recent research on optimal reliability design. Manypublications have addressed this problem using different system structures,performance measures, problem formulations and optimization techniques.The systems considered here mainly include series-parallel systems,k-out-of-n: G systems, bridge networks, n-version programming architecture, recovery block architecture and other unspecified coherent systems.The recently introduced NVP and RB belong to the category of fault tolerant architecture, which usually considers both software and hardware.Reliability is still employed as a system performance measure in a majority of cases, but percentile life does provide a new perspective on optimaldesign without the requirement of a specified mission time.