05-Chena TC_ You PS - Immune algorithms-based approach for redundant reliability problems with multiple component choices (Задание 5), страница 2

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.

Above all, the genetic algorithms become verypopular tools for solving the problem successfully[18,5,6,10]. Although genetic algorithms can be easilydesigned and implemented without the requirement ofsophisticated mathematical treatment, the difficultiesare in the determining appropriate values for theparameters.

If the parameters are not assignedproperly, the genetic algorithms will more likelyconverge to a local optimum and hard to reach theglobal optimum. One of the characteristics of immunealgorithms-based approach mentioned in previoussection, the global optimum could be more easilyachieved than genetic algorithms since the diversitiesof the feasible spaces can be better ensured. For theabove reason, the immune algorithms-based approachis applied for solving the series–parallel redundantreliability problems in this research.3. Immune algorithms implementationThe natural immune system of all animals is a verycomplex system for defense against pathogenicorganisms.

A two-tier line of defense is in the systemincluding the innate immune system and the adaptiveimmune system. The basic components are lymphocytes and antibodies [21]. The cells of the innateimmune system are immediately available to combatagainst a wide variety of antigen without previousexposure to them. The antibody production inresponse to a determined infectious agent (antigen)is the adaptive immune response mediated bylymphocytes which are responsible for recognitionand elimination of the pathogenic agents [22].

Thecells in the adaptive system are able to develop animmune memory so that they can recognize the sameantigenic stimulus when it is presented to the organismagain. Also, all the antibodies are produced only in198T.-C. Chen, P.-S. You / Computers in Industry 56 (2005) 195–205Fig. 1. A redundant reliability problem with multiple component choices.response to specific infections. There are two maintypes of lymphocytes: B-lymphocytes (B-cells) and Tlymphocytes (T-cells). B-cells and T-cells carrysurface receptor molecules capable of recognizingantigens. The B-cells produced by the bone marrowshow a distinct chemical structure and can beprogrammed to make only one antibody that is placedon the outer surface of the lymphocyte to act as areceptor. The antigens will only bind to these receptorswith which it makes a good fit [23].To distinguish and eliminate the intruders of theorganism is the main task of the immune system sothat it must has the capability of self/non-selfdiscrimination.

As mentioned previously, variousantibodies can be produced and then can recognizethe specific antigens. The portion of antigen recognized by antibody is called epitope which acts as anantigen determinant. Every type of antibody has itsown specific antigen determinant which is calledidiotope. Moreover, in order to produce enoughspecific effector cells to against an infection, andactivated lymphocyte has to proliferate and thendifferentiate into these effector cells. This process iscalled clonal selection [24] and followed by thegenetic operations such that a large clone of plasmacell is formed. Therefore, the antibodies can besecreted and ready to bind antigens.

According toabove facts, Jerne [19] proposed an idiotype networkhypothesis which is based on the clonal selectiontheory. In his hypothesis, some types of recognizingsets are activated by some antigens and produce anantibody which will then activate other types ofrecognizing sets. By this way, the activation ispropagated through entire network of recognizingTable 1Component data for the example [15]Subsystem No.Component choicesChoice 11234567891011121314Choice 2Choice 3Choice 4PCWPCWPCWPCW0.900.950.850.830.940.990.910.810.970.830.940.790.980.9012232343243224387545748654560.930.940.900.870.930.980.920.900.990.850.950.820.990.92113423453443344105634879565570.910.930.870.850.950.970.940.910.960.900.960.850.970.9521153256455425296455967666660.95*0.92**0.96**0.91**0.90*0.992*4**2**3**5*65*4**4**8**7*9T.-C.

Chen, P.-S. You / Computers in Industry 56 (2005) 195–205sets via antigen–antibody reactions. It is noted that theantigen identification is not done by a single ormultiple recognizing sets but by antigen–antibodyinteractions. The more details are referred to Huang[23,25]. From this point of view, for solving thecombinatory optimization problems, the antibody andantigen can be looked as the solution and objectionfunction, respectively.3.1.

Computation proceduresThecomputationproceduresoftheproposedimmunealgorithms-based approach illustrated in Fig. 2 workas follows and the discussion comes in sequence:Step 1: Generate an initial population of strings(antibodies) randomly.Step 2: Evaluate each individual in current populationand calculate the corresponding fitness value for eachindividual.Step 3: Select the best n individual with highest fitnessvalues.Step 4: Clone the best n individuals (antibodies)selected in Step 3.

Note that the clone size for eachselect individual is an increasing function of the199affinity with the antigen. In other words, the number ofposterity of each antibody is proportional to theirfitness values, i.e., the higher the fitness, the larger theclone size [26].Step 5: The set of the clones in Step 4 will suffer thegenetic operation process, i.e., crossover and mutation[27].Step 6: Calculate the new fitness values of these newindividuals (antibodies) from Step 5.

Select thoseindividuals who are superior to the individuals in thememory set, and then the superior individuals replacethe inferior individuals in the memory set. While thememory set is updated, the individuals will beeliminated while their structures are too similar. Sothe individuals in the memory set can keep thediversity.Step 7: Check the stopping criterion, if not stop thengo to Step 2. Otherwise go to next step.Step 8: Stop.

The optimal or near-optimal solution(s)can be obtained from the memory set.In our implementation, the integer solutions arerepresented by strings of binary digits. Each stringconsisting of substring includes the type of componentand redundant levels for each subsystem. The detailsFig. 2. The immune-based approach.200T.-C. Chen, P.-S. You / Computers in Industry 56 (2005) 195–205have been described in next section. In the aboveprocedures, the clonal selection and affinity maturation processes are described in details by De Castroand Von Zuben [26].

The stopping criterion is themaximum iterations in this paper.3.2. The representation mechanism andembodiment of diversityThe solution representation for IAs can be used inthe same manner to that of genetic algorithms. In ourimplementation, the antibody will be represented by abinary string, each string consisting of a substring foreach subsystem. Each subsystem in turn consists of abinary substring representing the type of componentand the level of redundancy. A real number can berepresented by a binary string and rounded to thenearest integer [28]. It is illustrated in Fig.

3.Because of the soul of diversity in the IAs, thequality of solutions in the feasible space can be betterguaranteed and obtained. So, a suppression process(diversity embodiment) is needed and shown in Step 6in the proposed IAs procedure. In this study, for eachantibody represented by a binary string can betranslated into a integer string which illustrates thetype of component and the corresponding redundantlevels as described above. The diversity in each pair ofantibody i (Abi) and antibody j (Abj) can be evaluatedby calculating their affinity (fij) by following way:fij ¼ kAbi Abj kfor all i and jWhile the affinity between each pair of antibodies inmemory is obtained, the antibodies will be eliminatedif the affinity is less than the predefined threshold.So, the diversity of the antibodies in memory isembodied.

It is noted that the way of evaluatingaffinities of Ab–Ab and Ab–Ag are distinct. Theprocedure of evaluating the antibodies is to calculatethe Ab–Ag affinity for each antibody that will beillustrated in the following section.3.3. Constrained optimizationFor breeding the superior antibodies for the nextgeneration (iteration), to evaluate the antibody isnecessary step for the immune algorithms.