· 6 years ago · May 31, 2019, 10:44 AM
1
2tspants, is a implementation in java of some ant colony optimization algorithms applied to tsp
3Copyright (C) 2014 Juan Luis Jiménez Laredo
4
5This file is part of tspants.
6
7tspants is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 3 of the License, or
10(at your option) any later version.
11
12tspants is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with tspants; if not, write to the Free Software
19Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20
21contact: juanlu.jimenez no@spam gmail.com https://code.google.com/p/tspants/
22Time of creation: 07/03/2014
23by: Juanlu J. Laredo
24
25This software package is loosely inspired by ACOTSP of Thomas Stuetzle. ACOTSP is available at
26http://www.aco-metaheuristic.org/aco-code, 2004.
27 */
28
29package tspants;
30import java.util.Iterator;
31
32import tspants.ants.Ant;
33import tspants.config.Config;
34import tspants.config.LoadProperties;
35import tspants.environment.Environment;
36
37/**
38 * @author Juanlu J. Laredo
39 *
40 * This class runs an Ant Colony Optimization (ACO) algorithm. It can be either an ant system (AS) or an ant colony system (ACS)
41 */
42public class ACO {
43
44 // Define next class variables if necessary
45
46 // Variable to control the number of iterations
47 private int _iteration = 0;
48
49 // Ants
50 private Ant[] _ant;
51
52 // Best tour
53 private Ant _best_ant=null;
54
55 /**
56 * Construct an ACO system. Ants are instances of the class defined at Config.path_to_your_ant_implementation
57 */
58 public ACO(){
59 _ant = new Ant[Config.m];
60
61 ClassLoader loader = ClassLoader.getSystemClassLoader();
62
63 for (int k = 0 ; k < Config.m ; k++) {
64 try {
65 _ant[k] = (Ant) loader.loadClass(Config.path_to_your_ant_implementation)
66 .getConstructor()
67 .newInstance();
68 } catch (Exception e) {
69 e.printStackTrace();
70 }
71 }
72
73 try {
74 _best_ant = (Ant) loader.loadClass(Config.path_to_your_ant_implementation)
75 .getConstructor()
76 .newInstance();
77 } catch (Exception e) {
78 e.printStackTrace();
79 }
80 }
81
82
83 //-------------------------------------------------
84 // Main function
85 //-------------------------------------------------
86 public static void main(String[] args) {
87
88 // Next line sets all the parameters as properties
89 // e.g. If you type in the command line: java AS xxx.properties
90 // and your property file (xxx.properties) contains the property: alpha=1
91 // after this line you are allowed to access the value of alpha by typing Config.alpha
92 Config.setConfiguration(new LoadProperties(args,null));
93
94 ACO aco = new ACO();
95 aco.printinfo();
96
97 // Main loop
98 while ( !aco.termination_condition() ) {
99
100 aco.construct_solutions();
101
102 aco.statistics();
103
104 aco.pheromone_trail_update();
105
106 aco._iteration++;
107 }
108
109 System.out.println(aco._iteration+"\t\t"+aco._best_ant.get_tourlength()+" FINAL RESULT");
110 }
111
112 //-------------------------------------------------
113 // Private functions
114 //-------------------------------------------------
115
116 /**
117 * Print information about the settings of the experiment
118 */
119 private void printinfo(){
120 System.out.println("#####################################################");
121 System.out.println("# TSP instance: "+Config.name);
122 System.out.println(" No. of cities: "+Config.n+" Optimal tour: "+Config.optimum);
123 System.out.println("# Algorithm: "+Config.algorithm);
124 System.out.println(" using the ant class: "+Config.path_to_your_ant_implementation);
125 System.out.println(" random seed: "+Config.seed);
126 System.out.println("# ACO settings ");
127 System.out.println(" No. of ants (m): "+Config.m);
128 System.out.println(" alpha: "+Config.alpha);
129 System.out.println(" beta: "+Config.beta);
130 System.out.println(" rho: "+Config.rho);
131 if(Config.algorithm.equals(Config.ACS))
132 System.out.println(" Q0: "+Config.q0);
133 System.out.println("#####################################################");
134 System.out.println("(New iterations appear if only there is an improvement in the tour)");
135 System.out.println("#Iteration\t#Best tour so far");
136 }
137
138 /**
139 *
140 * @return true if the maximum number of tours have been reached or if the optimal tour has been found
141 */
142 private boolean termination_condition(){
143 if ((_iteration * Config.m >= Config.max_number_of_tours) || _best_ant.get_tourlength() == Config.optimum)
144 return true;
145 else
146 return false;
147 }
148
149 /**
150 * Every ant construct a tour
151 */
152 private void construct_solutions() {
153
154 //Mark cities as unvisited
155 Environment.reset();
156
157 //Free previous tours
158 for (int k = 0 ; k < Config.m ; k++) {
159 _ant[k].free_ant();
160 }
161
162 //Place ants in some initial city
163 for (int k = 0 ; k < Config.m ; k++) {
164 int first_city = Environment.place_ant();
165 _ant[k].add_city_to_tour(first_city);
166 }
167
168 // Constructing a path step by step
169 while ( !_ant[0].is_tour_completed()) {
170
171 //Every step each ant adds a new city according to the state transition rule
172 for (int k = 0 ; k < Config.m ; k++) {
173 int to_city = _ant[k].next_transition_rule();
174 _ant[k].add_city_to_tour(to_city);
175 if(Config.algorithm.equals(Config.ACS)){ // Next function needs to be implemented for Ant Colony Systems
176 _ant[k].local_acs_pheromone_update();
177 }
178 }
179 }
180 }
181
182 /**
183 * Global update of pheromone after all ants have constructed a tour
184 */
185 private void pheromone_trail_update(){
186
187 //We only call the evaporation in an Ant System
188 if(Config.algorithm.equals(Config.AS))
189 Environment.evaporation();
190
191 if(Config.algorithm.equals(Config.AS)){ // In an ant system (AS) all ants update the pheromone trails
192 for ( int k = 0 ; k < Config.m ; k++ )
193 _ant[k].global_pheromone_update();
194 }else{// In an ant colony system (ACS) only the best ant so far update the pheromone trail
195 _best_ant.global_pheromone_update();
196 }
197
198 Environment.compute_total();
199 }
200
201 /**
202 * Print in the standard output the best so far tour
203 */
204 private void statistics(){
205
206 int best_tour_in_it = _ant[best_ant_in_iteration()].get_tourlength();
207 if (best_tour_in_it < _best_ant.get_tourlength()){
208 copy_to_best_ant(_ant[best_ant_in_iteration()]);
209 System.out.println(_iteration+"\t\t"+_best_ant.get_tourlength());
210 }
211 }
212
213 /**
214 *
215 * @return The index of the ant that has constructed the best tour of the iteration
216 */
217 private int best_ant_in_iteration(){
218 int best_ant = 0;
219 double shortest_path = Double.MAX_VALUE;
220 for(int k=0;k<Config.m;k++){
221 if(_ant[k].get_tourlength() < shortest_path){
222 shortest_path = _ant[k].get_tourlength();
223 best_ant = k;
224 }
225 }
226 return best_ant;
227 }
228
229 /**
230 * Save the best tour so far
231 * @param newbest
232 */
233 private void copy_to_best_ant(Ant newbest){
234 _best_ant.free_ant();
235 for (Iterator<Integer> cities = newbest.get_tour().iterator(); cities.hasNext();){
236 _best_ant.add_city_to_tour(cities.next().intValue());
237 }
238
239 }
240
241
242}