Муравьиный алгоритм (Задание 5), страница 3

Ahmadizar, H. Soltanpanah / Expert Systems with Applications 38 (2011) 3640–3646Table 1 (continued)SubsystemTech 1Tech 2Tech 3Tech 4Tech 5Tech 6Tech 7Tech 8380.75200.75150.99400.85400.9300.999700.95750.99400.99991000.9961000.999600.999991300.99961150.9995800.9999991600.99996140–0.999996155–0.9999996175–0.99999991850.999999982100.9999999952253940ReliabilityCost ($)ReliabilityCost($)ReliabilityCost ($)Tech = Technology.sij ¼ ð1 q0 Þsij þ q0 s0ð10Þwhere s0 is the initial value of the pheromone trails and q0 , a parameter between 0 and 1, is the local pheromone trail evaporation rate.The effect of this updating is to make the desirability of edgeschange dynamically in order to explore different paths by the nextants in the colony.

That is, the technologies in one ant’s solution willbe chosen with a lower probability in constructing other ants’solutions.3.6. Global updating of the pheromone trailsOnce all ants in the colony have constructed their solutions, theamount of pheromone on each edge (i, j) related to the global-bestsolution, that is, the best solution constructed so far, is modified byapplying the global updating rule as follows:sij ¼ ð1 qÞsij þ qz Rgb =TC gbð11Þwhere q, a parameter between 0 and 1, is the global pheromonetrail evaporation rate, z is a positive parameter and Rgb and TCgbare, respectively, the reliability and total cost of the global-bestsolution.

The global updating rule is intended to provide a greateramount of pheromone to better solutions in order to make thesearch more directed.4. Computational resultsIn order to evaluate the approach developed for the given reliability problem, five large examples are used. Examples 1, 2, 3and 4 presented in Nahas and Nourelfath (2005) are used for comparing ACS with the previous metaheuristic (i.e., AS) and example 5is considered for an additional evaluation. Example 1 has 15 subsystems and 60 decision variables, example 2 has 15 subsystemsand 80 decision variables, example 3 has 15 subsystems and 100decision variables and example 4 has 25 subsystems and 166 decision variables (for details see Nahas & Nourelfath, 2005). The datafor example 5 are shown in Table 1.

For this example, which has 40subsystems and 266 decision variables, the available budget is2700$ and the search space size is larger than 3.039 1032.The proposed algorithms have been coded in Visual C++6.0 andrun on a Pentium 4, 2 GHz PC with 256 MB memory under Windows XP. In order to test the effect of the local search technique,ACS is considered both without the local search and coupled withit. Furthermore, as the heuristic information can be calculatedbased on (7)–(9), eight cases are studied as follows:Case 1: Without the local search and without the heuristicinformation.Case 2: Without the local search and with the heuristic information based on (6) and (7).Case 3: Without the local search and with the heuristic information based on (6) and (8).Case 4: Without the local search and with the heuristic information based on (6) and (9).Case 5: With the local search and without the heuristicinformation.Case 6: With the local search and with the heuristic informationbased on (6) and (7).Case 7: With the local search and with the heuristic informationbased on (6) and (8).Case 8: With the local search and with the heuristic informationbased on (6) and (9).Note that in order to test the effect of the heuristic information,in Cases 1 and 5 the approach is considered without using the heuristic information, while in the other ones it is employed.

When theheuristic information is not used, (4) changes to j ¼ arg max½sij and (5) is also modified as follows:sijpkij ¼ PNið12Þsl¼1 ilIn the preliminary experiment, some values have been testedfor the numeric parameters. Four different values of Max_iter(1000, 1500, 2000 and 3000), five different values of Ant_size (5,10, 20, 30 and 50), various values of q0 (0.75, 0.8, 0.85, 0.9, 0.95and 0.97), different values of b (0.01, 0.1, 0.5, 1, 1.5 and 2), a rangeof values of q and q0 (0.01, 0.025, 0.05, 0.075, 0.1 and 0.15) andthree different values of z (1, S/2 and S) have been considered.We set s0 = 106. This value should always be chosen so little thats0 < zðRgb =TC gb Þ.

This issue imposes that (11) causes an increase inthe related sij (and then (10) causes a decrease in the related sij; ofcourse, s0 is a lower bound of the pheromone trails). With differentcombinations of the parameter values, each operator in (6) hasbeen evaluated and the aggregation operator O3, the Min operator,Table 2Results for example 1.Case12345678Time1.531.311.291.33.754.142.694.21ReliabilityMinimumAverageStd. dev.Maximum0.8500980.8570540.8500980.8561080.8561080.8570540.8561080.8570540.8558950.8570540.8559630.8566590.8569590.8570540.8567700.8570540.00207200.0021000.0004270.00029900.00045700.8570540.8570540.8570540.8570540.8570540.8570540.8570540.857054MinimumAverageStd. dev.Maximum0.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.9150420.915042000000000.9150420.9150420.9150420.9150420.9150420.9150420.9150420.915042Table 3Results for example 2.Case12345678Time2.011.711.71.72.332.442.722.01Reliability3645F.

Ahmadizar, H. Soltanpanah / Expert Systems with Applications 38 (2011) 3640–3646the cases have been the same in example 2. In view of the objectivefunction, Case 6 has been superior in all of the examples comparedto the other cases. Furthermore, when the local search has been applied, the ACS approach has been enhanced in case of the sameheuristic information (Case 5 in comparison with Case 1, Case 6in comparison with Case 2 and so on). Of curse, using the localsearch has often caused an increase in the time, but the CPU timesof the different cases for the same examples have been so closethat could be ignored. Because the sizes of the examples are largeenough to conclude, using the local search is suggested. Moreover,Case 5 in comparison with Cases 6, 7 and 8 has not been better.Consequently, the ACS approach coupled with the local searchand with the heuristic information based on (6) and (7) isrecommended.Finally, Table 7 gives a comparison between the results of ACS(Case 6) and AS for examples 1–4.

The proposed approach has beenthe same as AS in examples 1 and 2, but superior in examples 3 and4. In addition, it is worth to point out that the results of AS have notbeen generated using unique parameter values for all of the fourexamples (four set of numeric parameters have been used; for details see (Nahas & Nourelfath, 2005). This implies that what set ofparameter values should be used to solve another example is notspecified.

Therefore, the parameters of AS should be set againand again and this may be a weak point, whereas the numericparameters prepared for ACS are unique and because of the varietyof the five examples, it is assumed that they can be employed tosolve any other example. On the whole, ACS has outperformedAS and has been able to get very good solutions for large problemsat a reasonable CPU time.Table 4Results for example 3.CaseTime123456782.572.172.112.155.235.134.054.34ReliabilityMinimumAverageStd. dev.Maximum0.9581630.9640700.9640700.9640700.9640700.9651340.9651340.9640700.9639050.9650280.9647080.9644960.9650280.9651340.9651340.9648150.0020860.0003360.0005490.0005490.000336000.0005140.9651340.9651340.9651340.9651340.9651340.9651340.9651340.965134MinimumAverageStd. dev.Maximum0.8646600.8646600.8559260.8646600.8654390.8654390.8654390.8654390.8651270.8651270.8641760.8651270.8654390.8654390.8654390.8654390.0004020.0004020.0029250.00040200000.8654390.8654390.8654390.8654390.8654390.8654390.8654390.865439MinimumAverageStd.

dev.Maximum0.9107960.9123960.9107300.9107270.9115510.9140450.9124870.9116390.9131030.9139200.9137980.9140630.9134410.9147940.9145530.9142210.0016080.0011060.0017930.0013890.0013840.0002630.0007710.0012030.9148720.9148950.9148950.9148950.9148950.9148950.9148950.914895Table 5Results for example 4.Case12345678TimeReliability4.273.623.683.634.733.914.043.79Table 6Results for example 5.Case12345678Time6.695.835.825.917.126.155.965.83Reliability5. Conclusionshas been yielded the best results (while the Max operator has beenthe worst). Therefore, (6) is set according to O3.