تخصیص افزونگی چند سطحی با استفاده از پشتیبانی آرایه های دو بعدی و الگوریتم ژنتیک ترکیبی
کد مقاله | سال انتشار | تعداد صفحات مقاله انگلیسی |
---|---|---|
8090 | 2013 | 15 صفحه PDF |

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)
Journal : Computers & Industrial Engineering, Volume 64, Issue 1, January 2013, Pages 69–83
چکیده انگلیسی
With the popularity of multilevel design in large scale systems, reliability redundancy allocation on multilevel systems is becoming attractive to researchers. Multilevel redundancy allocation problem (MLRAP) is not only NP-hard, but also qualifies as hierarchy optimization problem. Exact method could not tackle MLRAP very well, so heuristic and meta-heuristic methods are often used to solve it. To improve the effectiveness of current algorithms on MLRAP, this paper proposes a hybrid genetic algorithm (HGA) based on the two dimensional redundancy encoding mechanism. Instead of hierarchical genotype representation, a two dimensional array is used to represent the solutions to MLRAP. Each row of the array contains the redundancy information of a certain unit in the system and each element in one row stands for the redundancy value of one element of that unit. The number of rows of this array is fixed and equals to the number of distinct units in the system. Each row of the array is an unfixed-length vector whose length depends on the redundancy of all elements of its parent unit. On top of this two dimensional arrays, a local search operator employing simulated annealing strategy is used to generate new population for the next generation instead of the traditional genetic operators. Experimental results have shown that our two dimensional arrays based HGA outperforms the state-of-the-art approaches using two kinds of multilevel system structure.
مقدمه انگلیسی
The demand for complex processing tends to make the scale of real world systems increasingly large. Multilevel design is often used for large-scale systems and reliability has also become a great concern for them. The reliability of multilevel systems could be calculated from lower-level modules or components and also could be improved through provision of redundant components (Kuo & Wan, 2007). The difference between redundancy configuration in multilevel systems and that in single-level systems is that redundancy could be allocated to sub-systems or components at any level. Similar to small systems, the reliability of a multilevel system could also be optimized by allocating appropriate redundancy to less reliable subsystems or components at different levels, subject to certain constraints (Kumar, Izui, & Masataka, 2008). To decrease the additional cost brought by redundant components, the tradeoff of redundancy on different level should be considered. Thus, multilevel redundancy allocation problem (MLRAP) is becoming increasingly attractive mainly for the following reasons. Firstly, multilevel redundant designs are prevalent in many practical systems, such as communication systems, computing systems, control systems, and critical power systems (Wang, Loman, & Vassiliou, 2004). The popularity of service-oriented technology and web service composition has also provided the possibility of multilevel software system design. Secondly, comparing with traditional redundancy allocation problem, which is nonlinear integer programming problem and NP-hard (Chern, 1992), multilevel redundancy allocation problem qualify as hierarchical optimization problems (Anandlingam & Friesz, 1992). The complexity of such problems is much larger than the traditional ones. In spite of its importance in the real world, MLRAP has rarely been investigated, and few approaches have been proposed. To provide a general representation of MLARAP, a hierarchy solution encoding mechanism is proposed by Kumar et al. (2008) and the following researches (He et al., 2012 and Wang et al., 2010) employ the same mechanism to implement their genetic algorithm (GA) or memetic algorithm (MA). The hierarchy redundancy encoding mechanism could present the redundancy of multilevel system in a good manner, however, there are two shortcomings with this kind of mechanism and corresponding algorithms: (1) The result of hierarchy encoding is an un-fixed length array and it is difficult to implement genetic algorithm, which often works on fixed length of vector. (2) To implement algorithms on un-fixed length array, the crossover or mutation operation is often taken by level. For example, the memetic algorithm proposed by Wang et al. (2010) first selects a level in the system and then selected units from the certain level to do the following operation. This kind of operation heavily depends on the level division of a system and lost the generality of considering the units in a unified manner. To tackle the above two problems, this paper first proposes a two dimensional genotype encoding strategy and converts the solution into a two dimensional arrays. For each system, there are fixed number of rows in this array and the number of rows equals to the number of units without redundancy in the system. A row of the array is a one dimensional array (a vector) with unfixed number of nodes representing the redundancy of all elements of that unit belonging to different parent units. The number of the columns in one row depends on the overall redundancy of its parent units, so the length of each vector is unfixed. Using this kind of encoding mechanism, each unit in the system could be treated in a unified manner. And since the number of rows is fixed, it is easier to conduct genetic algorithm operators. According to researches of Krasnogor and Smith (2005), MAs (Moscato, 1989) have been reported to search more efficiently than conventional GAs due to the local search procedure. So, this paper then conducts a further improvement on the genetic algorithm and proposes a two dimensional array based hybrid genetic algorithm (TDA-HGA) to solve MLRAP. An iterative local search method based on two dimensional solution arrays and simulation annealing algorithm is employed in TDA-HGA. Detailed experiments are conduct to compare our algorithm with MA provided by Wang et al. (2010) and improved memetic algorithm (IMA) by He et al. (2012) using the same system structures. The whole paper is organized as follows: Section 2 provides related work on the redundancy allocation problem and MLRAP. Section 3 summarized the description of MLRAP and the corresponding problem formulation. Two dimensional array genotype encoding mechanism for solution of MLRAP is presented in Section 4 and the corresponding hybrid genetic algorithm is given in Section 5. Section 6 listed experiments and comparison results on the TDA-HGA and MA followed the conclusion of the whole paper in Section 7.
نتیجه گیری انگلیسی
In this literature, the MLRAP has been intensively investigated. To improve the efficiency of existing algorithms in MLRAP, this paper proposed a two dimensional solution mechanism and improved the genetic algorithm based on two dimensional array solutions. The number of rows in this two dimensional arrays equals to the number of units the system and each element in a row represents the redundancy of one element of that unit. A new local search operator is proposed with sensitivity-based random selection strategy to choose one element from each row. A simulation annealing strategy has been used in the local search operator to keep the feasible solutions. For the genetic algorithm, fitness value is used to sort individuals and to select population for the next generation. Experimental studies on two multilevel system examples demonstrated that our TDA-HGA consistently outperformed state-of-the-art algorithms named MA (Wang et al., 2010) and IMA (He et al., 2012). This paper presents a further investigation on MLRAP comparing with existing researches and there are more issues need to be studied in the future. Current MLRAP only focus on serial or serial-parallel systems and the levels of component units are the same. The structure of current systems is much complex than serial systems. For example, the service composition, which is used to construct service oriented applications, often has more complex structure than traditional software systems. Changing the structure of a system will lead to different reliability and cost functions of the corresponding optimization problem, so current algorithms may need to be extended to adjust to new problems. Furthermore, current MLRAP mainly considers single-objective optimization. Even the few researches on multi-objective redundancy optimization in multilevel systems (Kumar, Izui, & Masataka, 2009a) also only takes reliability and cost into consideration. The redundancy configuration in service-oriented environment also causes response time increase and we need to take that into consideration in the future.