New Heuristic Function in Ant Colony System Algorithm for Optimization Ku Ruhana Ku-Mahamud 1 ,Mustafa Muwafak Alobaedy 2 1 Universiti Utara Malaysia, Malaysia, ruhana@uum.edu.my 2 Universiti Utara Malaysia, Malaysia,new.technology@hotmail.com Abstract: -NP-hard problem can be solved by Ant Colony System (ACS) algorithm. However, ACS suffers from pheromone stagnation problem, a situation when all ants converge quickly to one sub-optimal solution. ACS algorithm utilizes the value between nodes as heuristic value to calculate the probability of choosing the next node. However, the heuristic value is not updated throughout the process to reflect new information discovered by the ants. This paper proposes a new heuristic function for the Ant Colony System algorithmthat can reflect new information discovered by ants. The credibility of the new function was tested on travelling salesman and grid computing problems. Promising results were obtained when compared to classical ACS algorithm in terms of best tour length for the travelling salesmanproblem. Better results were also obtained for the grid scheduling problem in terms of makespan and utilization. Key-Words: -Ant colony system, heuristic function, traveling salesman problem, grid scheduling. 1 Introduction Marco Dorigo presented the first ACO algorithm in 1992, to solve optimization problems such as travelling salesman problem, job scheduling and network routing[1]. Other variants of ACO are (i) Ant System (AS) [2]. (ii) Elitist Ant System (EAS) [3], the first improvement on ant system in providing strong additional reinforcement to arcs belonging to the best tour found since the start of the algorithm. (iii) Rank-Based Ant System (ASrank) [4], another improvement over AS whereeach ant deposits an amount of pheromone that decreases with its rank. This is similar to EAS, where the best-so-far ant always deposits the largest amount of pheromone. (iv) Max-Min Ant System (MMAS) [5] [6] that has four direct improvements over AS. MMAS strongly exploits the best tours found, limits the possible range of pheromone trail values to the interval [tmin, tmax], the pheromone trails are initialized to the upper pheromone trail limit, and pheromone value is reinitialized each time the system approaches stagnation or when no improved tour has been generated for specific number of iterations. (v) Ant Colony System (ACS) [7] [8]. This variant allows the ants to apply exploitation and exploration mechanisms when they select the next node to move. In addition, ACS applies local pheromone update and global pheromone update to direct the search for next iteration. Global update is calculated based on the quality of the best solution so far while the local update apply evaporation concept. Ant colony system algorithm is one of the meta-heuristic algorithms which have been used to solve NP-Hard problems. This study focuses on two domains namely, Travelling Salesman Problem (TSP), and job scheduling problem in grid computing. In travelling salesman problem there are a set of cit ies {C1, C2, C3..., CN} and for each pair of cities, the distance is d (Ci, Cj). The solution for this problem is to find the shortest tour, which is to find a permutation π of the cities that minimizes the quantity . Such a problem is an optimization problem. Therefore, an approximation algorithm is required to find near optimal solutions rather than optimal solutions[7] [8]. In grid environment, the scheduler is responsible to find suitable resource to process specific job. Jobs are submitted to the grid system by users. The scheduler will assign jobs to resources according to the scheduling algorithm adopted by the grid system. Job scheduling problem can be presented as a directed graph (digraph) with nodes and directed edges. Resources and jobs are represented as nodes and the directed edges represent the processing cost and pheromone as shown in Fig.1. Recent Advances in Mathematical Methods, Intelligent Systems and Materials ISBN: 978-1-61804-168-513 Figure 1: Directed graph representation of jobs and resources. Job scheduling problem is different from traveling salesman problem where in traveling salesman problem, the graph is complete and undirected because every pair of distinct vertices is connected by a unique edge. In job scheduling, graph the connections (edges) are only between resources and jobs and directed from resources to jobs. There is no connection (edge) between resources and resources or jobs and jobs. 2 Research Framework The research framework starts with formulating a heuristic update function to reflect the change in the heuristic information of ACS algorithm. The second stage is the development of the enhanced ACS algorithm followed by the testing of the performance of the enhanced algorithm in solving the travelling salesman problem. This is followed by the development of the simulator and finally, testing the performance of the enhanced ACS algorithm in solving grid job scheduling problem. Fig.2 depicts the framework for this research. Formulate heuristic update function Integrate heuristic update function in ACS Develop enhanced ACS and evaluate its performance in solving TSP Develop enhanced ACS for solving job scheduling problem Develop grid simulator and evaluate the performance of enhanced ACS Figure 2: Research framework 3 New Heuristic Function ACS algorithms utilize the values between the edges to use it as heuristic value for the calculation of probability to choose the next node. However, heuristic value is not updated at any time during execution. Such situation contradicts the concept of heuristic. A new a function for heuristic value is needed to reflect the new information discovered by the ants. The pseudo-code for the function is as shown in Fig.3. Step 0: for each path in the best tour do step 1 to 2 Step 1: if path i (i = 1, 2, n) is not updated before do step 2 Step 2: ηi = ηi + (δ/ best-so-far tour) // δ is parameter from (0-10) End Figure 3: Pseudo-code for the new heuristic function. After ant constructed its solution, a global update process will be applied to update the best-so-far solution. This event will change the environment for the next iteration. The new function will be triggered to reflect this change and thus a new heuristic value will be obtained. The new information will be applied to the best-so-far edge every time the ants find a better solution in the iteration. The parameter δ will determine how much the influence of the updating value should be applied to the heuristic value. If δ = 0 then no update will occur which reflects the heuristic value in the classical ACS. The heuristic value on each edge will be updated only one time during the whole process if it belongs to the best-so-far edge. This condition will eliminate the issue of stagnation that may occur if the heuristic value is updated more than one time. After conducting many experiments, it is found that δ = 0.5 will produce good results. However, this depends on the problem domain and dimensions. The new heuristic function has been integrated in the classical ACS algorithm thus enhancing it. The enhanced ACS algorithm is known as EHF_ACS. In EHF_ACS, ants will be randomly distributed to nodes (cities or resources) after the initialization process. All ants will move concurrently and each ant will start building a solution which is a function of the distance between the cities in the case of TSP or the processing all jobs using all resources for the grid scheduling case. Each time an ant moves from a node to the next node, the pheromone on that connection (edge) will be evaporated based on local update mechanism. The benefit of local update function is to reduce the probability of Recent Advances in Mathematical Methods, Intelligent Systems and Materials ISBN: 978-1-61804-168-514 s electing the same resource (node) by the following ant. Local update also helps to reduce stagnation problem and increase exploration mechanism when sometime ACS algorithm does not show a convergence behavior (i.e., ants do not converge to the generation of a common path) [7] [8].After all ants have constructed their solutions, the best solution will be selected based on the shortest tour or makespan and utilization criteria. The best solution will be stored as global best solution if it is better than the current global best solution. A global update will be applied at this step using the global best solution. The benefit from global update is to increase the probability of selecting the same node (or the edge) for the next iteration. The heuristic function will start immediately after the global update in order to update the heuristic value. The proposed Ant Colony System (EHF_ACS) algorithm flowchart is depicted in Fig.4. Figure 4: EHF_ACS algorithm flowchart The difference between EHF_ACS algorithm and the classical ACS is the application of the enhanced heuristic function after global pheromone update activity is performed. Fig.5 presents EHF_ACS pseudo-code. Procedure EHF_ACS Initialize parameters While (termination condition not met) do Construct Ants Solutions Apply Local Pheromone Update If (New AntSolution better than Global Best Solution) Global Best Solution = New Ant Solution Apply Global Pheromone Update Apply New Heuristic Function End - While End - Procedure Figure : The EHF_ACS algorithm 4 Experimental Result Experiments were conducted to evaluate the performance of the enhanced ACS algorithm on two problem domain. The domains are the TSP and grid computing. Several initializations will have to be performed before EHF_ACS algorithm can be applied to TSP. The initializations are: (i) calculate distance between cities using Euclidean distance method. (ii) calculate heuristic values using heuristic function (1/distance). (iii) Initialize pheromone on all paths with values equal to 1 / (No of cities * nearest neighbor solution. (iv) set alpha (α), beta (β), delta (δ), q, p, number of ants (m), and number of iteration.The tour length is used to measure the quality of each ant where the shorter tour length the better is the solution quality. After completing all iterations, the heuristic value is updated for each edge that has not been updated before. In the experiment for TSP, eight data sets from TSPLIP with different sizes were used. Results were compared to classical ACS algorithm[7] [8]. Parameters initializations are as follows: α = 1, β = 2, δ = 0.5, q = 0.9, m = 10, p = 0.1, Initial pheromone (τ0) = 1/ (N*nn), where N = number of cities and nn = nearest neighbour, and number of iteration = 10000. Comparisons of results between the proposed algorithm and best known solution and ASC results from previous studies [9] [10] [11] [12] are depicted in Table 1. It can be seen that the proposed algorithm produces better solutions quality in terms of best and mean tours, and smaller standard deviation (SD). Seven (7) mean tour results obtained by the proposed algorithm are better than ACS and for the best tour results the proposed algorithm is at par with ACS. The mean Recent Advances in Mathematical Methods, Intelligent Systems and Materials ISBN: 978-1-61804-168-515 a nd SD shows the robustness of the proposed algorithm and its ability to guide the ants to quickly converge to the best solution. Each data set was run for five times to calculate the mean and SD. All the experiments using EHF_ACS produced good solution with minor differences between the runs.Fig. 6 represents the mean tour length of all instance using ACS and EHF_ACS. The enhanced algorithm was able to find shorter mean tour than the classical ACS in seven instances. Table1. Performances of ACS and EHF_ACS Algorithm on TSP a. SD is not calculated in the original study. Figure 6: Mean tour length of all instances using ACS and EHF_ACS In order to apply EHF_ACS to job scheduling problem, several initializations will have to be performed on i) list of jobs and resources, ii) array for the pheromone and iii) the variables alpha (α), beta (β), delta (δ), p, q, number of ants and number of iteration.A simulator was developed to test the performance of the proposed algorithm for the grid computing domain. Jobs were created with size varies from 500 – 1000 Million Instruction (MI) and the number of jobs is set between 10 and 100. The number of resources created for these experiments are seven resources with capacity varying from 50 – 250 Million Instruction per Second (MIPS) with load from 0 – 9.In total, the number of experiments conducted is 100 for ACS and 100 for EHF_ACS. 10 instances created based on incremental number of jobs from 10-100 with interval of 10 jobs. Each 10 experiments conducted using the same instances to get the average and SD of each 10 experiments’ results. Other parameters settings are as follows: number of ants = 7, α = 1, β = 2, initial pheromone (t0) = 0.0001, p = 0.5, q = TSP instance Optimum Source ACS EHF_ACS |Mean ACS – Mean EHF_ACS|% Mean SD Best Mean SD Best att48 33522 [12] 35595 a--- 33780 33614.4 43.135 33587 5.56 % eil51 426 [9] 428.21 2.05 426 428 1.095 426 0.05 % st70 675 [11] 682.50 2.82 677 677.2 0.748 676 0.78 % eil76 538 [9] 541.55 2.97 538 545.2 1.469 543 0.67 % rat99 1211 [11] 1219.60 6.45 1211 1212.6 0.8 1211 0.57 % kroA100 21282 [10] 21441.30 112.13 21315 21297.2 11.51 21282 0.67 % eil101 629 [9] 640.67 5.86 630 633 2.449 631 1.20 % rat195 2323 [11] 2352.76 15.79 2334 2347 4.147 2342 0.24 % Recent Advances in Mathematical Methods, Intelligent Systems and Materials ISBN: 978-1-61804-168-516 0.9, number of iteration = 1000 and δ = 0.5.The performance metrics used to evaluate the proposed algorithm were makespan and utilization. Shorter makespan indicates faster performance in term of processing time while utilization criteria indicate the quality of jobs scheduling and load balancing policy. Contradiction between makespan and utilization may occur if there is limited resource. Therefore, load balancing provide fair distribution rather than equal distribution in order to get good performance. Table 2 presents the comparison between ACS and EHF_ACS in terms on makespan and utilization where better results are highlighted. It can be seen that for makespan, the proposed algorithm performed better than ACS algorithm in 8 out of 10 cases. As for utilization, the proposed algorithm performed better than ACS algorithm in 7 out of 10 cases. Table 2. ACS and EHF_ACS performances on Grid Computing ACS EHF_ACS Task Makespan Utilization Avg UT SD Makespan Utilization Avg UT SD 10 12.52 64.56 62.48 1.04 15.929 77.715 74.82 3.82 20 22.638 74.716 71.59 3.3 20.541 90.14 85.74 5.63 30 33.364 92.396 83.94 5.24 29.395 88.246 82.94 3.86 40 35.566 88.658 81.57 5.46 43.547 85.604 81.41 2.81 50 51.913 88.984 77.1 5.7 42.575 92.96 87.85 3.14 60 65.359 88.896 82.81 5.1 50.327 94.369 87.5 4.62 70 64.82 77.747 74.02 7.26 59.836 89.643 84.14 3.61 80 71.647 96.154 79.75 8.79 65.747 96.14 87.39 5.32 90 101.043 80.417 73.95 3.8 73.134 94.106 87.56 4.48 100 110.039 82.26 74.68 3.75 80.284 95.472 86.62 4.99 The results are again presented in Fig 7 and Fig 8 which display the makespan, utilization, average utilization (AvgUT) and standard deviation (sd) of 7 resources with various tasks for ACS and EHF_ACS. Figure 7: Utilization of 7 resources Figure 8: Makespan of 7 resources The stability of resource utilization with various numbers of jobs is also tested. The unstable utilization pattern using classical ACS is depicted in Fig 9 whereas EHF_ACS algorithm produces a more stable utilization pattern as shown in Fig 10. Figure 9: Utilization and makespan using ACS Figure 10: Utilization and makespan using EHF_ACS 0 20 40 60 80 100 120 102030405060708090100 Utilization No of Jobs EHF_ACS ACS 0 50 100 150 102030405060708090100 Makespan No of Jobs EHF_ACS ACS 0 20 40 60 80 100 120 102030405060708090 100 No of Jobs Makespan Utilization 0 50 100 150 102030405060708090 100 No of Jobs Makespan Utilization Recent Advances in Mathematical Methods, Intelligent Systems and Materials ISBN: 978-1-61804-168-517 T he above results show that the proposed new heuristic function that has been integrated in ACS produces better results as indicated by smaller values for standard deviation in most cases. 5 Conclusion The new heuristic function can produce a heuristic value that reflects the quality of the best-so-far solution. This is important because ants can be guided to choose a path that will prevent stagnation. The new heuristic function is integrated into the classical ACS algorithm thus enhancing it. The enhanced ant colony systems algorithm can be considered as a new member to the family of ant colony optimization algorithms. Results show that the proposed algorithm outperforms the classical ant colony system algorithm. Future work will focus on enhancing the exploration mechanism in ant colony system algorithm. Better exploration mechanism will increase the ants’ ability to explore more search space in order to reach the nearest optimal solution for NP-hard problem. Acknowledgments The authors wish to thank the Ministry of Higher Education Malaysia for funding this study under Fundamental Research Grant Scheme, S/O code 11980 and RIMC, Universiti Utara Malaysia, Kedah for the administration of this study. References: [1] M. Dorigo and T. Stutzle.Ant colony optimization. Cambridge, Massachusetts, London, England: MIT Press, 2004. [2] A. Colorni, M. Dorigo, and V. Maniezzo.Distributed “Optimization by Ant Colonies”.Proceedings of the first European Conference on Artificial Life, Cambridge, 1991, pp. 134 – 142. [3] M. Dorigo. “Optimization, learning and natural algorithms” (Unpublished doctoral dissertation), Politecnico di Milano, Italy. 1992. [4] B. Bullnheimer, R. F. Hartl, and C. Strauss. “A New Rank-Based Version of the Ant System: A Computational Study”. Central European for Operations Research and Economics, Vol. 7(1), pp. 25 – 38, 1999. [5] T. Stutzle. “MAX-MIN ant system for quadratic assignment problems”. Germany: Intellektik Group, Department of Computer Science, Darmstadt University of Technology (Report No. AIDA-97-04), 1997. [6] T. Stutzle, and H. Hoos. “MAX-MIN ant system and local search for the traveling salesman problem,” Proceedings of IEEE International Conference on Evolutionary Computation. Indianapolis, 1997, pp. 309 – 314. [7] M. Dorigo, and L.M. Gambardella. “Ant Colonies for the Travelling Salesman Problem”. BioSystems Journal, Vol. 43(2), pp. 73–81, 1997. [8] M. Dorigo, and L. M. Gambardella. “Ant colony system: a cooperative learning approach to the traveling salesman problem”. IEEE Transactions on Evolutionary Computation, Vol. 1(1), pp. 53 – 66, 1997. [9] Y. Wei-Jie, H. Xiao-min, Z. Jun, and H. Rui- Zhang. “Self-Adaptive ant colony system for the traveling salesman problem,” Proceedings of the IEEE International Conference on Systems, Man and Cybernetics, San Antonio, Texas, USA, 2009, pp. 1399–1404. [10] A. Aljanaby, K. R. Ku-Mahamud, and N. M.Norwawi.“Optimizing Large Scale Combinatorial Problems Using multiple Ant Colonies Algorithm Based on Pheromone Evaluation Technique.”International Journal of Computer Science and Network Security, vol. 8(10), pp. 54 – 58, 2008. [11] L. Kangshun, K. lanlan, Z. Wensheng, and L. Bing.“Comparative analysis of genetic algorithm and ant colony algorithm on solving traveling salesman problem.” Proceedings of the First IEEE International Workshop on Semantic Computing and Systems, Huangshan, China, 2008, pp. 72 – 75. [12] Y. Wei-Jie, and Z. Jun. “Pheromonedistribution-based adaptive ant colony system.” Proceedings of the 12th Annual Conference on Genetic and Evolutionary Computation, New York, USA, 2010, pp. 31-38. Recent Advances in Mathematical Methods, Intelligent Systems and Materials ISBN: 978-1-61804-168-518