A Memetic Algorithm for Multi Level Redundancy Allocation

 

Abstract

Reliability Redundancy allocation problem determines the component reliability and redundancy level for each subsystem in order to improve the system reliability. Redundancy allocation problem is NP-hard problem and hence various Heuristic and meta-heuristic approaches are being applied.[1] This paper proposes a memetic algorithm to solve the RAP problem. Although the real engineering experience deals with multi-level systems, in this paper prior assumptions are made such that the algorithm has been applied to single level systems. This proposed MA is then compared against the HGA of a two multi-level systems and the proposed MA has outperformed the HGA of two multi-level system.

1. INTRODUCTION of Articles

In this article, a new Memetic algorithm has been proposed to solve the Redundancy Allocation Problem which has attained great attention in recent years.

Prior assumptions has been made in order to investigate the Multi-Level Redundancy Allocation problem and the three important assumptions are: If a unit is not at its lowest level then its child units are assumed to be serial and they are fixed. The second assumption is that the redundancy can be allocated to the units at any level and the final assumption is that the quality of each component is predefined and the cost and the reliability are calculated based on child units if and only if the unit is not a component. From the various literature review which has been carried out, it is found that there are few approaches to MLRAP and these are rarely being investigated. Genetic Algorithm and the modified Genetic Algorithm which is the Hierarchical Genetic Algorithm is although considered to be the significant approach for MLRAP, the effectiveness of these approaches can be improved.

Thus for the improvement in these approaches, the new Memetic Algorithm has been proposed in this article. Memetic algorithm is a population based eta-heuristic search method which uses the combination of global search engines along with the local search heuristics. According to the article MA is more successful than the GA because of two key issues. One is the appropriate balance between the global and local search engines and the other is the cost effectiveness. In this article two new genetic operators and a new problem specific local search operator are incorporated in the MA framework and a new MA has been proposed for approaching the MLRAP.

In this article, the parts of a multi-level serial system has been defined hierarchically at the topmost level and the sub system has been defined at the lower level and the components in the lowest level. As per the assumption made previously, there is fixed number of child units for each unit except a component. The redundancy allocation procedure always starts from the system level and moves to the component level for a multi-level serial system. The reliability of the multi-level serial system can be calculated using,

While the reliability of the units at the lower level can be calculated on the basis of the components using,

Also the cost for the multi-level serial system is calculated using,

When applying the Conventional GA for solving MLRAP, the decision variables becomes in fixed number during problem solving. Whereas in MLRAP problem solving the decision variable changes due to the change in redundancy allocation to a unit. Hence to overcome this problem, a hierarchical structure has been proposed in the article which is capable of changing the decision variables.

Nomenclature

2. Explanation of the work presented in journal articles

The proposed MA in the article has two types of operators which consists of the genetic operator for global explorations and the local search operator for exploitation. This section explains the articles you reviewed.

In the proposed model, the quality of the solutions should be evaluated and from the literature the author of the article has pointed out many techniques to measure the quality of the solution out of which a penalty function which has been proposed by Gen and Cheng has been used to derive the fitness function to evaluate the quality of the solution during the search process. This fitness function is given by,

Ψ(x) is the penalty function which measures the extent of the solution violating the constraints.

The initialization of the MA is generally done at the system level and it starts from generating the random population of solutions. For a system of multi-level series, K integer is generated randomly for n child unit n X k redundancy units have to be generated at the second level and goes on until an individual is obtained.

Of the two proposed genetic operators, before being applied the hierarchical representation need to be selected. And hence the solution highly depends on type of the hierarchical representation being selected. Then the two genetic operators will be applied to the iteration and both the operator treat the unit or the system at the same level.

Of the two genetic operators, the crossover between two individuals occurs in three steps. Initially an intermediate is selected from the system and component level and the higher level is being assigned higher probability. Finally the selected levels exchange their lower structures to give two new individuals. Whereas the mutation also occurs in three steps but is applied to individual level. The first two steps remains the same as the crossover and the third step is replacing the redundancy of the selected unit by a randomly generated integer. Also when changing the redundancy corresponding decision variable o the parent unit should also be updated.

The other operator of the proposed MA is the local search operator. In the new MA proposed in the article, local search operator is implemented in three steps. The population solution are evaluated through the metric which is given by,

Then a single individual is chosen from the population solution. The local search is carried out based on it. Then the individual with the higher metric is selected for local search. For an MLRAP, it is desired to have an optimal system for a higher reliability and the reliability to cost ratio serves as a measure to determine the potential of the individual solution. The local search operator randomly selects ten pairs of components and for each pair the redundancy of the components are modified and during this search newly generated individual will be stored in the archive if and only if it donot violate the cost constraint. Finally, the preserved inividual will be mixed with the population solution and arranged descendingly and the top most individuals will be used discarding others.

3. Discussion of Contributions

Two systems has been taken into consideration. One system with three levels and the other system with four levels. With this systems into consideration, the performance of the proposed MA is to be evaluated and compared with the performance of conventional HGA.

Since there are a number of control parameters in both HGA and the proposed MA, there are some values which are to be preset before beginning the experiment. For fair process, the values which has been set for HGA is used as same for the proposed MA for problem A. In this experiment the aim is to study the convergence behavior of the proposed MA in order to compare it with HGA. The best solution obtained in each generation is recorded and the corresponding system reliability is calculated. It is seen that both the methods converged fast whereas the convergence of the proposed MA is significantly better than the convergence of the HGA which is shown in Fig 1.

Fig:1 Comparison of convergence between HGA and MA for Problem A.[1]

Furthermore the comparisons has been carried by varying the numerous cost constraints. 20 cost constraint values are varied between the intervals 150 to 340 leaving the system parameters unchanged. For every constraint values, MA and HGA were applied 10 times to each cost constraint. The observations are made for each and every run and the reliability and the cost constraints are calculated and compared between MA and HGA. From the calculative comparison, it is evident that the proposed new MA has outperformed the conventional HGA for problem A that is the system with three levels.

The same kind of experiment is carried out for problem B to examine whether the advantage of MA holds a variety of system parameters. Similar to the problem A, ten test instances are obtained and the MA and HGA are applied to each instances for ten times. The convergence of MA is significantly better than the convergence of HGA which is shown below.

Fig:2 Convergence of MA and HGA for problem 2[1]

Since the same kind of experiment was done on problem B, the results were also quite the same. The proposed MA has outperformed the conventional HGA.

4. Discussion of Dificiency and Potential Improvements

The article being reviewed here discusses only about the multi-level serial system and the experimentation has been done considering this system alone. Changing the condition and the structure of the system changes the reliability and the cost function of the corresponding solution changes. Also the proposed MA gives significant reliability for the multi-level serial system, the proposed MA should also be extended to multi-level serial systems of complex structures. Also the problems which is being formulated in the article are single objective or are of only one goal of increasing the reliability of the system by having the cost reduction as only one constraint. Instead, in the future research, the problems can be formulated with multiple objective and multiple constraint along with the cost constraint. This type of approach with multiple objective problems will yield multiple solutions which has trade-off between the system reliability and cost constraint.

5. Summary

The RAP which has attained a global attention among the researchers motivating them to find the solution for the RAP. Though many algorithms, techniques and approaches have been proposed by many researchers around the world, there is something which can be improved in each and every approach proposed by researchers to solve the MLRAP. In this article, the author has given a detailed approach on how does a reliability problem works and formulated in a way that the problem deals with the multi-level serial system of simple structure. Upon formulating a problem, the author tries to make proper assumptions to advocate the formulated problem. Then the author just solves it with the conventional GA approach which yields a good system reliability. Then the problem is again solved with the new method. This new method is being proposed by the author is the novel Memetic Algorithm where some preconditioning is being done to the solution that is being selected form the population solution. The solution is checked for the quality by using a fitness function. Now the population solution will be initialized and the two search operators of the MA is applied to the selected and preserved solution from the population samples of solution. The solutions which are being obtained from the search operators are then being combined with the population and the best among them is selected. The process is repeated for various generations and the best individual will be selected as the solution for the MLRAP. Then the approaches are compared and it is found that the proposed MA has outperformed the conventional HGA irrespective of the type of multi-level serial system of same structure.

Acknowledgments

I would like to thank Dr. Wang,  fellow, IEEE, and Dr. Tang, fellow, IEEE and Dr. Yao, fellow, IEEE for their research study that was done by them to prepare the article, which helped me to understand the concept behind the RAP and MLRAP and the techniques used to solve or approach MLRAP. I would also like to express my Thanks to Dr. Pingfeng Wang, Graduate Coordinator in Wichita State University for his valuable advice which guided me through this project and helped me to complete this review successfully.

References

[1] Wang, Z., Tang, K., & Yao, X. (2010). A memetic algorithm for multi-level redundancy allocation. IEEE Transactions on reliability, 59(4), 754-765.

[2]    Sharifi, M., Cheragh, G., Maljaii, K. D., Zaretalab, A., Daei, A. V. F., & Vahid, A. (2015). RELIABILITY OPTIMIZATION OF A SERIES-PARALLEL K-OUT-OF-N SYSTEM WITH FAILURE RATE DEPENDS ON WORKING COMPONENTS OF SYSTEM. International Journal of Industrial Engineering, 22(4), 438-453.