2014_421_Vasilenko_ImmuneAlgorithm_based approach for redundant reliability problems with multiple component choices (1158515), страница 2
Текст из файла (страница 2)
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. The goal ofthe algorithm is to adapt the unfeasible antibodies tothe feasible antigen(s), so as to reduce the constraintviolations of the search for obtaining the optimal ornear-optimal solutions. Like the majority of geneticalgorithms applications, for handling these constraintviolations the penalty function has been defined. Thepenalty function increases the penalty for infeasiblesolutions based on the distance away from the feasibleregion. According to Eq. (2) in the problem formulation, the function has been defined and described asfollows.Assume the individual j within the memory ofN.
For each individual antibody, the constraint (2)violation value for the jth individual is defined as8kin kin XX>< XXai;j;k xi;k bj ; ifai;j;k xi;k > bjVj ¼i¼1 k¼1i¼1 k¼1>:0;otherwiseNote the objective and solution are deemed as theantigen and antibody, respectively. After defining thepenalty function, the fitness of each antibody to theantigen (objective) can be obtained. In other words,the affinity between each antibody and antigen is ableto be determined.
The affinity function (fitness function) of any Ab to Ag is described below:Affinity ¼RðxjqÞP1þ mj¼1 VjThe above affinity value is to be maximized when thepenalty is minimized.3.4. Genetic operation processFig. 3. Binary string represents a solution of a series–parallelreliability problem.The implementation of genetic operations is thesame as in genetic algorithms. It including thecrossover operator and mutation operator requiresthe selection of the crossover point(s) and mutationpoint(s) for each antibody (string) under a predetermined crossover probability and mutation probability.T.-C.
Chen, P.-S. You / Computers in Industry 56 (2005) 195–205The crossover operator provides a thorough search ofthe sample space to produce good solutions. Themutation operator performs random perturbations toselected solutions to avoid the local optimum. Note themutation rate must be small enough to avoid degradingthe performance.4. Numerical results and discussionTo evaluate the performance of our artificialimmune algorithms for the integer nonlinear redundant reliability problems, 33 test problems are solved.The input data for a reliability system are described in201Table 1, which includes the component choices, andthe corresponding reliability of each component.
Theinput parameters have the same values as those ofNakagawa and Miyazaki [4], Coit and Smith [5] andHsieh [7]. These test problems based on theparameters in Table 1 are resolved with varying theavailable weight varied incrementally from 159 to 191while fixing the available cost = 130. Numericalresults obtained by using artificial immune algorithmare shown in Table 2, and compared with those foundby Nakagawa and Miyazaki [4], Coit and Smith [5]and Hsieh [7] in Table 3.
Recall that, for each problem,both the component choices and the number of thechosen component are to be decided simultaneously.Table 2Numerical results by artificial immune algorithmNo.WeightReliabilitySolution1234567891011121314151617181920212223242526272829303132331911901891881871861851841831821811801791781771761751741731721711701691681671661651641631621611601590.98681100.98641610.98592170.98532970.98444950.98417550.98343630.98269800.98220620.98151830.98102710.98029020.97950470.97820850.97724290.97669050.97570790.97469010.97375800.97302660.97192950.97076040.96929100.96812510.96633510.96504160.96371180.96242190.96064240.95918840.95803460.95571440.9545648333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,333,Note: The cost limitation is 130 for all 33 cases.11,11,11,11,22,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,444, 3333, 222, 22, 111, 1111, 12, 233, 33, 1111, 11, 34444, 3333, 222, 22, 111, 1111, 11, 233, 33, 1111, 12, 34444, 3333, 222, 22, 111, 1111, 23, 233, 13, 1111, 22, 34444, 3333, 222, 22, 111, 1111, 13, 233, 13, 1111, 12, 34444, 333, 222, 22, 111, 1111, 23, 233, 33, 1112, 22, 344444, 333, 222, 22, 111, 1111, 23, 233, 33, 1111, 22, 34444, 333, 222, 22, 111, 1111, 23, 223, 33, 1111, 22, 344444, 333, 222, 22, 111, 1111, 23, 333, 33, 1111, 22, 33444, 333, 222, 22, 111, 1111, 23, 233, 33, 1111, 22, 3334444, 333, 222, 22, 111, 1111, 33, 333, 33, 1111, 22, 33444, 333, 222, 22, 111, 1111, 33, 233, 33, 1111, 22, 334444, 333, 222, 22, 111, 1111, 33, 223, 33, 1111, 22, 334444, 333, 222, 22, 111, 1111, 33, 223, 13, 1111, 22, 33444, 333, 222, 22, 33, 1111, 33, 233, 33, 1111, 22, 33444, 333, 222, 22, 33, 133, 33, 223, 33, 1111, 22, 33444, 333, 222, 22, 33, 1111, 33, 223, 13, 1111, 22, 33444, 333, 222, 22, 13, 1111, 33, 223, 33, 1111, 22, 33444, 333, 222, 22, 33, 113, 33, 223, 13, 1111, 12, 33444, 333, 222, 22, 13, 113, 33, 233, 13, 1111, 22, 33444, 333, 222, 22, 13, 113, 33, 223, 13, 1111, 22, 33444, 333, 222, 22, 13, 113, 33, 222, 13, 1111, 22, 33444, 333, 222, 22, 13, 113, 33, 222, 11, 1111, 22, 33444, 333, 222, 22, 11, 113, 33, 222, 13, 1111, 22, 33444, 333, 222, 22, 11, 113, 33, 222, 11, 1111, 22, 33444, 333, 22, 22, 13, 113, 33, 222, 11, 1111, 22, 3344, 333, 222, 22, 13, 113, 33, 222, 11, 1111, 22, 33444, 333, 22, 22, 11, 113, 33, 222, 11, 1111, 22, 3344, 333, 222, 22, 11, 113, 33, 222, 11, 1111, 22, 3344, 333, 22, 22, 11, 113, 33, 222, 13, 1111, 22, 3344, 333, 22, 22, 11, 113, 33, 222, 13, 1111, 22, 3344, 333, 22, 22, 11, 113, 33, 222, 11, 1111, 22, 3344, 333, 22, 22, 11, 111, 33, 222, 13, 1111, 22, 3344, 333, 22, 22, 11, 111, 33, 222, 11, 1111, 22, 33CostWeight130130130130130129128129128130129128126127129124125123124123122120121119118116117115114115113112110191190189188187186185184183182181180179178177176175174173172171170169168167166165164163162161160159202T.-C.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
