Reliability Optimization of a Series-Parallel System

Share Embed


Descrição do Produto

心智与计算

403

心智与计算, Vol.1,No.4 (2007), 403-412 文章编号:MC - 2007-040 收稿日期:2007-08-10 出版日期:2007-12-30 © 2007 MC– 厦门大学信息与技术学院

Reliability Optimization of Series-Parallel Systems Using Asynchronous Heterogeneous Hierarchical Parallel Genetic Algorithm ZENG Wen-hua1, Yiannis Papadopoulos 2, David Parker 2 (1.School of Software, Xiamen University, Xiamen 361005, China; 2.Department of Computer Science, University of Hull, UK) [email protected] Abstract: Redundancy allocation of series-parallel systems is a multiobjective optimization problem. In this paper, a new parallel genetic algorithm, named asynchronous heterogeneous hierarchical parallel genetic algorithm(AHHPGA), is proposed to solve reliability optimization of series-parallel systems. The AHHPGA is a hierarchical model, which uses coarse-grained model as upper layer, and fine-grained model as lower layer. The new parallel genetic algorithm is a heterogeneous model, different exploration/exploitation degree and different topology are assigned to each subpopulation. The migration model of AHHPGA is asynchronous, which includes asynchronous reception and asynchronous emigration. A new model-based reliability evaluation technique, which is called HiP-HOPS, is used to overcome the limitations imposed by reliability block diagrams. The simulation result of well known Fyffe’s problem is better than traditional genetic algorithms. Key words: redundancy allocation problem; series-parallel systems; multiobjective optimization; parallel genetic algorithm

异步异构分层并行演化算法及其在串并系统 可靠性优化中的应用 曾文华 1, Yiannis Papadopoulos 2, David Parker 2 (1.厦门大学软件学院, 福建 厦门 361005;2.英国 Hull 大学计算机系) [email protected] 摘要:本文提出了一种新的并行演化算法――异步异构分层并行演化算法(AHHPGA),用于求解串 并系统可靠性分配的多目标优化问题(RAP)。AHHPGA 采用分层结构,上层由粗粒度模型构成,下层由 细粒度模型构成。在 AHHPGA 的每个子种群中,采用不同的全局/局部搜索度和拓扑结构,构成异构模 型。AHHPGA 的迁移方式包括异步接收和异步迁出。采用基于模型的复杂系统可靠性评价工具 (HiP-HOPS),以克服可靠性框图方法(RBD)的缺点。仿真结果表明,基于异步异构分层并行演化算法和 HiP-HOPS 工具的串并系统可靠性分配的多目标优化方法,优于传统的基于遗传算法的优化方法。

Reliability Optimization of Series-Parallel Systems Using Asynchronous Heterogeneous Hierarchical Parallel Genetic Algorithm

404

关键词:可靠性最优分配问题;串并系统;多目标优化;并行遗传算法 中图分类号: TP301.6 文献标识码:A

1

Introduction A well-known and complex reliability design problem is the redundancy allocation problem(RAP). In the

formulation of RAP of series-parallel systems, for each subsystem, multiple component choices are used in parallel. The RAP is a multiobjective optimization problem, which goal is to select the optimal combination of parts and redundancy-levels to minimize cost and weight while maximizing system reliability. Chern[1] showed that the RAP is NP-hard. Many researchers have studied redundancy allocation problem. Frank[2] provided a thorough review related to optimal system reliability with redundancy. Fyffe[3] used a dynamic programming algorithm to solve the RAP with 14 k-out-of-n fault tolerant subsystems in series. The same problem was optimized using integer programming by Ghare[4]. Nakagawa[5] use a surrogate constraints approach to solve 33 variations of Fyffe’s problem, these variations of the original Fyffe’s system have become a benchmark for optimization methods seeking to solve the RAP. Heuristic approaches have been applied to optimize system reliability with redundancy. Coit[6] used genetic algorithm(GA) to obtain a competitive and robust results than exact mathematical methods. Tabu search is used to solve the RAP by Kulturel[7]. Liang[8] used ant system approach to optimize the redundancy allocation problem. In this paper, we propose a new parallel genetic algorithm to solve the Fyffe’s problem. In section 2, an asynchronous heterogeneous hierarchical parallel genetic algorithm for multiobjective optimization is presented. In section 3, we use AHHPGA to solve the reliability optimization of series-parallel systems. Section 4 gives the simulation result for solving 33 variations of Fyffe’s problem by new parallel genetic algorithm. Conclusion and future work are discussed in Section 5.

2

Asynchronous Heterogeneous Hierarchical Parallel Genetic Algorithm for Multiobjective Optimization Parallel genetic algorithms have been widely used in solving complicated optimization problems, such as

NP-hard, neural network optimization, multiobjective optimization, etc. There are three ways for implementing the parallelization of genetic algorithms(Herrera[9]): (1) Global parallelization. The evaluation of chromosome fitness and sometimes the genetic operator application are carried out in a parallel form. (2) Coarse-grained parallelization. The population is divided into small subpopulations that are assigned to different processors. These parallel genetic algorithms are known as distributed GAs, since they are usually implemented in distributed memory MIMD computers. (3) Fine-grained parallelization. The population is divided into a great number of small subpopulations, in which a unique individual is assigned to each processor. These parallel genetic algorithms, known as cellular

Reliability Optimization of Series-Parallel Systems Using Asynchronous Heterogeneous Hierarchical Parallel Genetic Algorithm

405

GAs, are usually implemented on massively parallel computers. On the other hand, hierarchical model is used to implement parallel genetic algorithms. Herrera[9] give a hierarchical distributed GAs model, which uses coarse-grained model with three-dimensional cyclic connective topology as upper layer, and coarse-grained model with three or six subpopulations as lower layer. Our new parallel genetic algorithm, which is called asynchronous heterogeneous hierarchical parallel genetic algorithm(AHHPGA), also uses coarse-grained model with three-dimensional cyclic connective topology as upper layer, but it will use fine-grained model as lower layer.

2.1

The Topology of AHHPGA

图1

Fig. 1

AHHPGA 算法的拓扑结构

Integral structure of AHHPGA

AHHPGA is a hierarchical model based on three-dimension hypercube topology. There are eight subpopulations categorized into explorative subpopulations(E1~E4) and exploitative subpopulations(e1~e4) in terms of search property. In explorative subpopulations, the exploration degree increases clockwise, starting at the lowest E1, and ending at the highest E4. In exploitative subpopulations, the exploitation degree increases clockwise, too, starting at the lowest e1, and ending at the highest e4. Furthermore, subpopulations are adequately connected for migrating between subpopulations belonging to different categories and induce the refinement or the expansion of the best zones emerging. Each subpopulation is constructed by a cellular GA, which size is different. Fig.1 outlines the topology of AHHPGA.

2.2

Heterogeneous Model The AHHPGA is a heterogeneous model, which includes: (1) Different exploration/exploitation degree is assigned to the recombination operator of each

subpopulation. (2) The corresponding topology is assigned to each subpopulation according to its exploration/exploitation degree. Yan & Zeng[10] proposes a new fuzzy recombination operator, called SF-FRO, which involves fitness information of parents in traditional fuzzy recombination operator(FRO). SF-FRO can adapt the searching intensity according to the fitness information of recombined parents, which will efficiently guide the algorithm to converge to global optima. When applying the SF-FRO to AHHPGA for multiobjective optimization

Reliability Optimization of Series-Parallel Systems Using Asynchronous Heterogeneous Hierarchical Parallel Genetic Algorithm

406

problem, the fitness of individual will be replaced by domination of individual. For example, two recombined parents x and y, if parent x dominates parent y, let Fx=1, Fy=0; if parent y dominates parent x, let Fx=0, Fy=1; if parent x and parent y are un-dominated, let Fx=1, Fy=1; where Fx and Fy are normalized fitness of parents x and y in SF-FRO. The research on ratio between neighborhood and population radii has been limited to fine-grained model with single population so far. We extend the ratio research to AHHPGA by assigning heterogeneous topology to each subpopulation. The higher exploration degree a subpopulation has, the more square topology will be assigned to it, and therefore, the selection pressure will be greater. Oppositely, the higher exploitation degree a subpopulation has, the more narrow topology will be assigned to it, and therefore, the selection pressure will be smaller. This heterogeneous topology will iron out the conquest and noneffect problems in migration between subpopulations, thus, improve the quality of solutions and algorithm efficiency.

2.3

Asynchronous Migration Model There are three migration modes

in

the

migration

model,

including

refinement

mode,

refinement/expansion mode, and expansion mode, as shown in Fig.2. Migrants are sent only toward immediate neighbors along a dimension of the hypercube, and each subsequent migration takes place along a different dimension of the hypercube. Particularly, the best element of each subpopulation is sent toward the corresponding subpopulation every fixed generations, and the place of an emigrant is taken by an immigrant. The sequence of migration is defined as follow: first, the refinement migration, second, the refinement/expansion migration, third, the expansion migration, and then, the sequence starts again. The migration model of AHHPGA is asynchronous, which includes asynchronous reception and asynchronous emigration: (1) Asynchronous reception. Reception won’t be considered unless the local subpopulation has empty cells. Otherwise, some local individuals have to be abandoned. Especially in asynchronous migration, if evolution levels of subpopulations are so different that some slow subpopulation haven’t got any empty cells since they haven’t arrived the emigration generation yet, while other subpopulations have sent their best individuals to them time after time, as the number of external individuals grows, the slow subpopulations will probably be occupied by other subpopulations and result in extinction since the loss of their own characters. Besides, the asynchronous test has been used to check whether the expectant individuals have been arrived. If the answer is yes, then the reception starts, otherwise, evolve the local subpopulation to the next generation. With the asynchronous reception, the evolutions of subpopulations don’t have to wait for others. The efficiency of algorithm is improved. (2) Asynchronous emigration. Once the local subpopulation reaches the emigration, the emigration mode and target subpopulation will be determined by the evolution generation, and the local best individual is allowed to emigrate immediately, without waiting for the other subpopulations to arrive the same evolution generation. Thus, with asynchronous emigration, AHHPGA is able to avoid the unnecessary cost of time result from unbalanced load, and therefore improve efficiency.

Reliability Optimization of Series-Parallel Systems Using Asynchronous Heterogeneous Hierarchical Parallel Genetic Algorithm

(a) 细化模式

(b) 细化/扩充模式

(a) Refinement mode

(b) Refinement/expansion mode

407

(c)扩充模式 (c) Expansion mode

图 2 三种迁移模式

Fig.2 Three migration mode 2.4

Algorithm (1) Initialize parameter; (2) Generate initial active subpopulation randomly; (3)Create an empty Pareto front (archive subpopulation); (4) while not TerminationCondition() do (5) Asynchronous receive the emigrant individual from other subpopulation; (6) for x
Lihat lebih banyak...

Comentários

Copyright © 2017 DADOSPDF Inc.