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

A solution is constructed by repeatedly applying thetransition rule.B. If the solution is infeasible, it is replaced by a feasibleone using Algorithm 2.C. If it is possible, the solution is improved by Algorithm 3,i.e., the local search procedure.D. The pheromone trails related to the chosentechnologies are finally modified according to the localupdating rule.Step 2.2. The pheromone trails are modified according tothe global updating rule.Step 3. The best solution found is printed.if subsystem i uses technology j0; otherwiseThen, the problem is formulated as the following binary integerprogramming problem with one nonlinear objective function:Max Rsys ¼NiSYXi¼1s:t:3641NiS XXi¼1NiX!xij Rijj¼1xij C ij 6 Bð1Þj¼1xij ¼ 1;8 i ¼ 1; 2; .

. . ; Sð2ÞArtificial ants probabilistically build solutions by iterativelychoosing technologies by taking into account both the heuristicinformation on the problem and the (artificial) pheromone trailswhich change dynamically at run-time. An ant chooses one ofthe available technologies to assign to the current subsystem asfollows: with probability q0 an ant k for subsystem i selects thetechnology j for which the product between the pheromone trailand the heuristic information is maximum, that is,j ¼ arg max½sij ðgij Þb j¼1xij ¼ f0; 1g;3.2.

Pseudo-random transition rule8 i ¼ 1; 2; . . . ; S; j ¼ 1; 2; . . . ; Nið3ÞConstraint (1) represents the budget constraint, constraint (2)represents the multiple-choice constraint and constraint (3) defines the decision variables.ð4Þwhere sij and gij are, respectively, the pheromone trail and heuristicinformation between subsystem i and technology j – denoted byedge (i, j).

Also, b is a positive parameter denoting the relativeimportance of the heuristic information versus the pheromone trail.3642F. Ahmadizar, H. Soltanpanah / Expert Systems with Applications 38 (2011) 3640–3646While with probability 1 q0, the ant selects a technology j according to the probability distribution given in the following equation:sij ðgij Þbbl¼1 sil ðgil Þpkij ¼ PNið5ÞAs seen, gij shows the desirability of selecting technology j forsubsystem i. Therefore, the heuristic information related to onesubsystem can be considered as a fuzzy set.

We present two priority rules in order to calculate the heuristic information as follows.Rule 1: (based on the objective function) If a technology is reliable, it must be chosen with a high desirability.Rule 2: (based on the budget constraint) If a technology ischeap, it must be chosen with a high desirability.ð1ÞF ijð2ÞF ijLetandbe, respectively, the priority grade, i.e., the gradeof membership, of technology j for choosing in subsystem i relatedto the sets of reliable (say fuzzy set 1) and cheap (say fuzzy set 2)technologies for this subsystem. According to Rules 1 and 2 andð1Þð2Þbased on both F ij and F ij , the heuristic information can be calculated in several ways.

In this research, four operators are considered as the aggregation operator:ð1Þ ð2ÞO1Þgij ¼ F ij F ijð1Þð2ÞO2Þgij ¼ Average F ij ; F ijð1Þð2ÞO3Þgij ¼ Min F ij ; F ijð1Þð2ÞO4Þgij ¼ Max F ij ; F ijð1Þð6Þð2ÞMoreover, F ij and F ij can be calculated in several manners. Inthis research, three methods are defined as follows.In method 1, the relative values of the reliability and the cost ofa technology are considered according to the given fuzzy sets asfollows:Rijð1ÞF ij ¼ PNl¼1 Rili;1=C ijð2ÞF ij ¼ PNil¼1 1=C ilð7ÞWhile in methods 2 and 3, the reliability and the cost of a technology are indirectly considered.

Assume that, based on fuzzy set1, the available technologies for subsystem i are sequenced in1decreasing order of reliability. Let rankij be the rank of technologyj which can be between 1 (related to the most reliable technology)and Ni (related to the most unreliable technology). Also, supposethat, based on fuzzy set 2, these technologies are rearranged in2increasing order of cost. Let rankij be the rank of technology j whichcan be between 1 (related to the cheapest technology) and Ni (related to the most expensive technology).

Then, according to methð1Þð2Þods 2 and 3, F ij and F ij are, respectively, formulated as (8) and (9).1ð1ÞF ij ¼ð1ÞF ij ¼Ni þ 1 rankij;Ni11rankij;ð2ÞF ij ¼2ð2ÞF ij ¼12rankijNi þ 1 rankijNið8Þð9ÞNote that all of the three methods guarantee that the higherð1Þð2Þreliability, the greater F ij and the smallest cost, the greater F ijwhich, respectively, agree with fuzzy sets 1 and 2. In addition,ð1Þð2ÞF ij and F ij in (7) are greater than 0 and smaller than 1, while inboth (8) and (9) are limited to the interval ½1=N i ; 1.a convenient procedure where an infeasible solution is replacedby a feasible one. This mechanism is based on a neighborhoodsearch as follows. (Let TC be the total cost of the current solution.)Algorithm 2Step 1.

One of the subsystems is chosen; if it is possible, the current technology of this subsystem is replaced as follows: amongthe available technologies which have smaller cost than thecurrent one, (if the given set is not empty) the most reliabletechnology is selected.Step 2. TC is calculated. If TC is not greater than B, the procedureis terminated, and otherwise, it is repeated from Step 1.In Step 1, a subsystem can be chosen in a random way or in apurposeful manner based on cost (that is, the subsystem withthe greatest cost).3.4. Local searchWhen an ant colony algorithm is coupled with a local searchprocedure, the performance could be greatly improved (Dorigo &Stutzle, 2003). A local search is performed based on a neighborhood search in order to find a better solution.

Therefore, if the entire available budget is used by a solution, it may not be improvedby a local search which is not very deep. It is noteworthy that if atechnology is more reliable than another, it also has greater cost,and otherwise, the last one will not be chosen in the optimal solution of the problem and hence, it should be eliminated from the listof available technologies in the beginning – this proposition hasbeen proved in Sung and Cho (2000).

In order to achieve the bestperformance, the following local search procedure is developedto improve each solution which has not used the entire availablebudget.Algorithm 3Step 1. One of the subsystems is chosen (say i); if it is possible,the current technology of subsystem i (let us say technology j) isreplaced as follows: among the available technologies whichhave higher reliability than technology j and whichCi. Cij 6 B TC, (if the given set is not empty) the most reliabletechnology is selected.Step 2. TC is calculated. If TC is smaller than B, the procedure iscontinued from the next step, and otherwise, i.e., if TC = B, it isterminated.Step 3. One of the subsystems is chosen (say i).

The availabletechnologies which have higher reliability than the currentone (say technology j) and which Ci Cij 6 B TC are specified.If this set is empty, the procedure is terminated, and otherwise,technology j is replaced by the most reliable one among thespecified technologies.Step 4. TC is calculated. If TC is smaller than B, the procedure iscontinued from Step 1, and otherwise, i.e., if TC = B, it isterminated.In Steps 1 and 3, a subsystem can be selected in a random wayor in a purposeful manner based on reliability (that is, the subsystem with the lowest reliability).3.3. Dealing with infeasibility3.5. Local updating of the pheromone trailsAs mentioned before, a constructed solution may be infeasiblebecause the total cost of the chosen technologies may be greaterthan B (that is, the violation of constraint (1)).

Thus, we developWhile constructing a solution, an ant changes the pheromoneintensity on each edge (i, j) related to its chosen technologies byapplying the local updating rule as follows:3643F. Ahmadizar, H. Soltanpanah / Expert Systems with Applications 38 (2011) 3640–3646Table 1Data for example 5.SubsystemTech 1Tech 2Tech 3Tech 4Tech 5Tech 6Tech 7Tech 810.9200.85300.8200.75300.85200.9250.95400.85100.9300.99150.95200.8400.75300.8100.99500.9200.85300.8200.75300.85200.9250.95400.85100.9300.99150.95250.85400.85250.8300.8200.85200.9300.85150.9250.95200.99300.8300.99400.9775600.96400.938400.99400.95300.99600.995300.95500.999400.999400.9600.85500.95300.999800.99400.9775600.96400.938400.99400.95300.99600.995300.95500.999400.99350.97600.96450.9450.98400.9300.97500.95300.95450.999450.998400.9500.999600.9966900.99600.98500.999650.999500.997800.999600.995700.9999700.9998600.99850.99800.99400.99991100.999600.9966900.99600.98500.999650.999500.997800.999600.995700.9999700.999550.997900.99600.98600.995600.99500.997700.995600.995650.9995700.9998600.99800.9999800.99951200.998800.999600.9999800.9999700.99971000.9999800.9995900.999991000.99999800.9991100.9991000.999600.999991400.9999800.99951200.998800.999600.9999800.9999700.99971000.9999800.9995900.999991000.9995700.99951200.998850.998700.9995800.999700.9997900.9995850.9995850.999991000.99998800.9991150.999991000.99991500.99971000.9999700.999981000.99999900.999971200.999991200.999951100.9999991300.9999981000.99991300.99961200.9999800.9999991600.999991000.99991500.99971000.9999700.999981000.99999900.999971200.999991200.999951100.9999991300.99999950.99991450.99981000.9995850.999951000.9999900.999971100.999951100.999951050.9999951400.9999981000.99991300.999999120–0.9999999140–0.99999999180–0.9999120–0.99999140–0.999999160–0.999998120–0.9999998140–0.99999998155–0.999997140–0.9999997160–0.99999997180–0.9999951300.99999991600.9999999120–0.9999995150–0.99999995170–0.99999997140–0.999999999160–0.99996140–0.999996160–0.9999996180–0.99999991800.999999120–0.999999982000.9999999140–0.9999999952200.99999999180–0.9999120–0.99999140–0.999999160–0.999998120–0.9999998140–0.99999998155–0.999997140–0.9999997160–0.99999997180–0.9999951300.99999991600.999995115–0.9999995150–0.99999995170–0.9999999140–0.99999998160–0.99995125–0.99999150–0.999999170–0.999995120–0.9999995140–0.99999995160–0.999997130–0.9999997150–0.99999997170–0.9999951250.99999991700.9999998120–0.9999995145–0.99999995165–0.99999998140–0.999999998160–2345678910111213141516171819202122232425262728293031323334353637ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)ReliabilityCost ($)(continued on next page)3644F.