International Journal of Electrical and Computer Engineering (IJECE) Vol.
No.
August 2017, pp.
ISSN: 2088-8708.
DOI: 10.
11591/ijece.
The Effect of Updating the Local Pheromone on ACS Performance using Fuzzy Logic Abdellatif El Afia.
Safae Bouzbita.
Rdouan Faizi National School of Computer Science and Systems Analysis (ENSIAS).
Mohammed V Universityin Rabat.
Morocco
Article Info
ABSTRACT
Article history:
Fuzzy Logic Controller (FLC) has become one of the most frequently utilised algorithms to adapt the metaheuristics parameters as an artificial intelligence In this paper, the yuO parameter of Ant Colony System (ACS) algorithm is adapted by the use of FLC, and its behaviour is studied during this adaptation.
The proposed approach is compared with the standard ACS Computational results are done based on a library of sample instances for the Traveling Salesman Problem (TSPLIB).
Received Feb 21, 2017 Revised May 13, 2017 Accepted May 27, 2017 Keyword:
Ant colony algorithm Fuzzy logic controller Parameter adaptation Copyright A 2017 Institute of Advanced Engineering and Science.
All rights reserved.
Corresponding Author:
Abdellatif El Afia.
National School of Computer Science and Systems Analysis (ENSIAS).
Mohammed Ben Abdallah Regragui Avenue.
Madinat Al Irfane.
BP 713.
Agdal Rabat.
Morocco.
Email: a.
elafia@um5s.
NOMENCLATURES
Random proportional rule Random variable uniformly distributed between .
, .
Parameter to control exploration and exploitation Set of cities not yet visited by ant k positioned on city r length of a nearest neighbour tour and n is the number of cities length of the globally best tour found from the beginning of the algorithm length standard deviation Greek Symbols yu yuO yuU yuN pheromone amount between city r and city s Heuristic information between city r and city s Parameter that determines the relative importance of pheromone versus heuristic value Local pheromone evaporation parameter Initial value of the pheromones Global pheromone evaporation parameter Mean of lengths INTRODUCTION The Ant Colony System (ACS) is one of the most effective extensions of the basic Ant System (AS) algorithm (Dorigo and Gambardella, 1.
The ACS algorithm is described in pseudo-code (Figure .
The procedure of ACS technique consists of three steps: Pheromone initialization.
Construct Ants Solutions, and Global pheromone updating.
Journal homepage: http://iaesjournal.
com/online/index.
php/IJECE A ISSN: 2088-8708 Procedure-ACS Set parameters, initialize pheromone trails While .
ermination condition not me.
do Place each ant in a randomly chosen node Construct Ants Solutions Update global pheromones End Figure 1.
The Ant Colon System procedure.
The Ant Colony System applied to Transport Salesman Problem can be formulated as follow: m ants are initially placed on n cities randomly, each ant builds a complete solution in the Construct Ants Solution using the so called pseudo-random proportional rule Equation .
and AuEquation .
Where:
: the set of cities not yet visited by ant k positioned on city r.
: the pheromone amount between city r and city s.
: the heuristic information between city r and city s.
: the parameter that determines the relative importance of pheromone versus heuristic value.
yu That is, the best edge is chosen with a probability .
Otherwise, with probability .
selected by biased exploration according to the following Equation:
{ Oc ), an edge is .
During the construction of solutions, each ant modifies the amount of pheromone on the visited edges by applying the local updating rule:
Where:
yuO : the local pheromone evaporation parameter.
: the initial value of the pheromones.
In the global pheromone step, once all ants have built a solution, the amount of pheromone on edges is modified again by the best ants, using the global updating rule:
yuU ( .
Where:
yuU : the length of the globally best tour found from the beginning of the algorithm.
: the global pheromone evaporation parameter.
Several approaches have been proposed to adapt the parameters on Ant Colony algorithms .
Espacially the adaptation using Fuzzy Logic, in this part the most important are presented.
In the first approach.
Amir et al.
, developed in their work, a Fuzzy Logic Controller (FLC) to adapt the parameters and automatically throughout the run according to definite performance measures which are the error of the best-so-far tour compared to the best-known tour to the TSP problem and the variance among the solutions found by the population of ants.
Also, in .
FLC was used to improve ACO.
In their work, a solution is constructed by an ant based on pheromone trails and heuristic information for solving the reliability problem for a series system, in order IJECE Vol.
No.
August 2017 : 2161 Ae 2168
IJECE
ISSN: 2088-8708
to find one technology for each subsystem.
The Fuzzy set of this approach is the heuristic information related to the subsystem in consideration.
In .
Olivas et al.
, suggested an improved ACO by dynamically adapting the responsible parameter for the evaporation of the pheromone with the use of fuzzy logic.
In this paper, authors tried to control the abilities for diversification and intensification of the search space.
To do so, they used two metrics that measure the algorithm performance, which are diversity and iteration as inputs of the Fuzzy system and the parameter as output.
On the other hand.
Fuzzy Logic was used to vary other metaheuristic parameters.
Valdez et al .
described a hybridization of PSO and GA using Fuzzy Logic for decision making and parameters adaptation.
Thus, three Fuzzy system were proposed.
the first one is responsible for deciding which are the best results of the FPSO FGA, and the two second ones are in charge of changing the values of the crossover the mutation , the social acceleration , and the cognitive acceleration .
In .
a Fuzzy Logic approach was proposed to dynamically adapt the cognitive and the social factors and to improve the convergence and diversity of the population in PSO algorithm.
Three Fuzzy Systems were modelled for adapting the and parameters, with respect to three performance measures, which are the diversity of the swarm, the average error, and the iterations of the algorithm.
The performance of ACS depends strongly on the values set to parameters.
Thus, varying parameters while solving a problem can enhance the performance of the algorithm.
In this paper, the Fuzzy Logic was used to dynamically adapt the pheromone parameters of ACS based on the approach proposed by Olivas et al .
To do this, first we applied the Fuzzy Logic to the yuO parameter, then we compared the obtained results with the standard ACS algorithm.
This paper is constructed as follows: in Section 2 we outline the proposed method.
The experimental part is discussed in the third section.
From our experimental results, we give some conclusions and suggestions for future work in Section fourth.
RESEARCH METHOD
To dynamically adapt the local pheromone parameter in ACS, we have used a Fuzzy Logic System .
that is characterized by two inputs and one output.
In fact, as inputs in each case we used a proportion of elapsed iterations and a measure of the diversity of the colony compared to the best ant, while the output is the parameter to be adapted, in our case the parameter.
Where, .
Current iteration is the number of past iterations, and total of iteration is the entire number of iterations needed for testing the algorithm, m is the population size, i is the number of the ant, n is the entire number of dimensions, j is the number of the dimension, is the j dimension of the ant i.
I is the j dimension of the current best ant of the colony.
Procedure CAS-FLC Calculate Iteration from AuEq.
Ay and Diversity from AuEq.
Ay Fuzzify the Iteration and Diversity using the membership functions described in figures 3 and 4.
Evaluate the fuzzy rules using AuEq.
Ay.
Defuzzify the results of evaluation phase and output the crisp value for yuO using AuEq.
Ay For each ant in the population do If q < then with probability choose the node to move to using AuEq.
Ay Else with Probability .
choose the node to step to using AuEq.
Ay Update pheromone amount using AuEq.
Ay Until all ants build a solution Figure 2.
Adaptive local parameter using FLC.
In Figure 2, we described the adaptation of yuO parameter using the FLC after one established In facts, in each iteration ants build solutions incrementally to the problem, by moving through neighbour components solution of the problem, using the transition rule described by Equations .
While moving, an ant modifies the amount of pheromone using the local pheromone updating procedure described by Equation .
Once all ants have terminated a solution the amount of pheromone is modified The Effect of Updating the Local Pheromone on ACS Performance using Fuzzy Logic (Abdellatif El Afi.
A ISSN: 2088-8708 again using the global pheromone updating procedure.
The obtained information from the first iteration are used to calculate the first inputs of the FLC algorithm, and so on.
Fuzzification The Fuzzification process is the first step in the FLC system, which corresponds to transforming the crisp values into fuzzy grades using the membership functions.
This process facilitates the application of the rule set.
For each input variable, we define three membership functions (MF), to define a qualitative category for each one: {Low.
Medium.
Hig.
In practice, there are various shapes of membership functions that can be used in the fuzzification process, for example: Triangular MFs.
Trapezoidal MFs.
Gaussian MFs.
Generalized bell MFs, yuU-Shaped Membership Function.
S-Shaped Membership Function .
In this work, we used the triangular membership functions that are very popular, easy to implement, and respond to our The input variables with their membership functions are illustrated in Figure 3 and Figure 4.
Figure 3.
Iteration as input variable.
Figure 4.
Diversity as input variable Figure 3 illustrates the three triangular membership functions of the iteration input variable with a range from 0 to 1.
In Figure 4 the three triangular membership functions of the Diversity input variable are shown with a range from 0 to 1.
Let x the crisp value of Iteration and y the crisp value of Diversity.
For each input we calculate the degree of membership: yuN , yuN , and yuN Where.
Low=.
, 0.
Medium=.
, .
, and High=.
5, .
Rule Evaluation In fuzzy logic, there are various ways to define a fuzzy rule.
Indeed, they can be divided into three main classes: the fuzzy conjunction, the fuzzy disjunction, and the fuzzy implication .
In this work, we used a MamdaniAos fuzzy conjunction fuzzy rule.
Once the variables and membership functions are designed, we define the rule base which is composed by IF- Then rules.
In fact, the rule base is developed according to some knowledge about the ACS algorithm and the chosen metrics.
The rules (Figure .
of the proposed fuzzy system with Iteration and Diversity as input and yuO as output are as follows:
If (Iteration is Lo.
and (Diversity is Lo.
uO is Lo.
If (Iteration is Lo.
and (Diversity is Mediu.
uO is MediumLo.
If (Iteration is Lo.
and (Diversity is Hig.
uO is Mediu.
If (Iteration is Mediu.
and (Diversity is Lo.
uO is MediumLo.
If (Iteration is Mediu.
and (Diversity is Mediu.
uO is Mediu.
If (Iteration is Mediu.
and (Diversity is Hig.
uO is MediumHig.
If (Iteration is Hig.
and (Diversity is Lo.
uO is Mediu.
If (Iteration is Hig.
and (Diversity is Mediu.
uO is MediumHig.
If (Iteration is Hig.
and (Diversity is Hig.
uO is Hig.
Figure 5.
IF-THEN rules of our fuzzy system To evaluate the fuzzy rules we used the Min fuzzy set operation, assuming that we are using the MamdaniAos conjunction operator (AND).
For each rule we return the lowest value from the calculated degrees of membership of the two inputs.
IJECE Vol.
No.
August 2017 : 2161 Ae 2168
IJECE
ISSN: 2088-8708
uN yuN Where, i is the index of the rule, j and k are indexes for the fuzzy sets {Low.
Medium.
Hig.
for x and y.
Then, the results of all rules are summed together to produce a set of fuzzy outputs.
Defuzzification After the evaluation of the rules, we obtain a fuzzy output thatAos need to be transformed to a crisp value using one of the defuzzification methods.
In fact, the commonly used techniques for defuzzification are: Mean of Maximum (MOM) method.
Center of Gravity method, and the height method .
, .
Figure 6 shows the yuO parameter as output variable, with a range from 0 to 1, and granulated into five triangular membership functions.
Where, output set is: S= { Figure 6.
yuO as output variable In order to obtain the output variable in crisp value, we defuzzify the obtained results from the inference process using the Center of Gravity (COG) algorithm described by Equation 8:
Where, p=9 is the number of output membership function, function, and yuN the result of all rule evaluation as shown in Table 1.
is the singleton of output membership Table 1.
The singleton of the output membership function
Low
Low
= 1/6
Medium
= 2/6
High
=3/6
Medium
=2/6
=3/6
=4/6
High
=3/6
=4/6
=5/6
Where, corresponds to Low membership function of the output, corresponds to Medium Low membership function of the output, corresponds to Medium membership function of the output and so on.
RESULTS AND DISCUSSION
To test the effectiveness of the proposed algorithm, we compared it to the standard ACS with a set of benchmark TSP instances from the TSPLIB .
Table 2 tabulates the size and the o.
timal tour length of each instance.
We run the ACS algorithm with the following parameters: yu = 2, = 0.
9, yuU = 0.
1 and m=10, which were proven to be the best setting parameters for ACS performance .
Programming by Matlab R2013a, the instances will be run 30 times separately, 1000 iterations each time.
The stop condition is: 100 as the maximum number of ACS iterations without improving.
The initial position of ants is set randomly on all The best comparison results are shown in Table 2.
The Effect of Updating the Local Pheromone on ACS Performance using Fuzzy Logic (Abdellatif El Afi.
A ISSN: 2088-8708 Table 2.
Chararteristics of TSP benchmark instances.
TSP
Number of cities est known solutions kroA100 Pr226 Comparison on the Solution Accuracy Comparing the running of ACS with a fixed set of parameters against the proposed method shows better results for both minimum and average length in most of the instances, especially when dynamically adapting the parameter.
In Table 3, it can also be observed that in instances of small sizes the best found solutions for the two algorithms are almost the same with a privilege in the average solutions for the proposed algorithm.
But in large size instances there is a big difference between the best solutions that are found for each of the two algorithms.
Thus, it can be concluded that as the size of problem becomes larger as the proposed algorithm can offer better results.
The experimental results reflect the role of learning to provide the best solutions.
Table 3.
Summary of results using ACSFL algorithm for TSP instances ACSFL
TSP
kroA100
Pr226
Min Avg
ACS
CPUtime Min Avg CPUtime Comparison on the Convergence Speed It can be noted from the Table 3, that the time of finding the best length for the proposed algorithm when adapting the parameter outperforms both the conventional ACS and the proposed algorithm when varying the parameter.
However, it can be seen that the time of finding the same best length is less in the proposed algorithm when adapting the parameter than the two others.
The Figures 7.
, 7.
, 7.
below show the result of running both algorithms on four chosen instances of TSP benchmarks which are:
eil51, kroA100, eil101, and lin105.
The Figures actually go in line with these observations, since a very big difference is noticed between the solutions found by the three algorithms, the proposed algorithm when varying parameter converges to a better solution than the conventional one and the proposed algorithm when adapting the parameter in all the figures.
In addition to the quality of solution, there is a faster convergence in the proposed algorithm when dynamically adapting the parameter.
IJECE Vol.
No.
August 2017 : 2161 Ae 2168
IJECE
ISSN: 2088-8708
Figure 7.
Sample run on eil51 instance, .
Sample run on kroA100 instance, .
Sample run on eil101 instance, .
Sample run on lin105 instance Statistical Test To compare the proposed method with the standard one, we have used the T-Test as a statistical test that compares the means of lengths returned by the proposed method and the standards ACS according to the following Equation:
Oo Where, n is the lengths size.
The results obtained from applying this test are illustrated in "Table 4".
The 30 experiments for each instance are the used parameters for the tests, the null hypothesis yuN yuN ) says that the proposed method returns greater lengths of averages when compared with the other method, while the alternative yuN yuN ) says that the proposed algorithm returns better average when compared with the other method, the level of significance is 5 percent, and the critical value = 1.
699, so the rejection region is for all values of T-Test lowers than .
From the results in table 4, the proposed method fail to reject the null hypothesis only in 2 instances, and this is for the smallest problems which are the easiest ones, however the proposed method can achieve better results with level of significance of 5 percent in all other results.
The Effect of Updating the Local Pheromone on ACS Performance using Fuzzy Logic (Abdellatif El Afi.
A ISSN: 2088-8708 Table 4.
Results of comparison using T-Test
TSP
ACS
Fuzzyglobal kroA100
Pr226
CONCLUSIONS
This paper proposed a new evolved Ant Colony System Algorithm based on a fuzzy system so as to dynamically adapt the local pheromone parameter that has a crucial impact in avoiding falling in the local best optimum during the construction solution phase.
The simulation result on TSP showed that the proposed method that dynamically adapt the local pheromone parameter has higher convergence speed and better quality of optimal solution.
In other words, the effect of local updating is to make a better use of pheromone information to explore new best solutions.
The proposed method when adapting parameter gives a flexible control of pheromone information which balances between the exploration search and exploitation then finding better solutions.
REFERENCES