1 |
dl |
1.1 |
/* |
2 |
dl |
1.2 |
* Written by Doug Lea and Bill Scherer with assistance from members |
3 |
|
|
* of JCP JSR-166 Expert Group and released to the public domain, as |
4 |
|
|
* explained at http://creativecommons.org/licenses/publicdomain |
5 |
dl |
1.1 |
*/ |
6 |
|
|
|
7 |
dl |
1.2 |
import java.util.*; |
8 |
dl |
1.1 |
import java.util.concurrent.*; |
9 |
|
|
import java.util.concurrent.atomic.*; |
10 |
|
|
import java.util.concurrent.locks.*; |
11 |
|
|
|
12 |
dl |
1.2 |
/** |
13 |
|
|
* A parallel Traveling Salesperson Problem (TSP) program based on a |
14 |
dl |
1.4 |
* genetic algorithm using an Exchanger. A population of chromosomes is |
15 |
|
|
* distributed among "subpops". Each chromosomes represents a tour, |
16 |
|
|
* and its fitness is the total tour length. |
17 |
jsr166 |
1.6 |
* |
18 |
dl |
1.4 |
* A set of worker threads perform updates on subpops. The basic |
19 |
|
|
* update step is: |
20 |
dl |
1.2 |
* <ol> |
21 |
dl |
1.4 |
* <li> Select a breeder b from the subpop |
22 |
dl |
1.2 |
* <li> Create a strand of its tour with a random starting point and length |
23 |
jsr166 |
1.6 |
* <li> Offer the strand to the exchanger, receiving a strand from |
24 |
dl |
1.4 |
* another subpop |
25 |
jsr166 |
1.6 |
* <li> Combine b and the received strand using crossing function to |
26 |
dl |
1.2 |
* create new chromosome c. |
27 |
dl |
1.4 |
* <li> Replace a chromosome in the subpop with c. |
28 |
dl |
1.2 |
* </ol> |
29 |
|
|
* |
30 |
dl |
1.4 |
* This continues for a given number of generations per subpop. |
31 |
|
|
* Because there are normally more subpops than threads, each worker |
32 |
|
|
* thread performs small (randomly sized) run of updates for one |
33 |
|
|
* subpop and then selects another. A run continues until there is at |
34 |
|
|
* most one remaining thread performing updates. |
35 |
|
|
* |
36 |
dl |
1.2 |
* See below for more details. |
37 |
|
|
*/ |
38 |
dl |
1.1 |
public class TSPExchangerTest { |
39 |
dl |
1.3 |
static final int NCPUS = Runtime.getRuntime().availableProcessors(); |
40 |
|
|
|
41 |
dl |
1.4 |
/** Runs start with two threads, increasing by two through max */ |
42 |
|
|
static final int DEFAULT_MAX_THREADS = Math.max(4, NCPUS + NCPUS/2); |
43 |
|
|
|
44 |
|
|
/** The number of replication runs per thread value */ |
45 |
|
|
static final int DEFAULT_REPLICATIONS = 3; |
46 |
|
|
|
47 |
|
|
/** If true, print statistics in SNAPSHOT_RATE intervals */ |
48 |
|
|
static boolean verbose = true; |
49 |
|
|
static final long SNAPSHOT_RATE = 10000; // in milliseconds |
50 |
dl |
1.2 |
|
51 |
|
|
/** |
52 |
|
|
* The problem size. Each city is a random point. The goal is to |
53 |
|
|
* find a tour among them with smallest total Euclidean distance. |
54 |
|
|
*/ |
55 |
|
|
static final int DEFAULT_CITIES = 144; |
56 |
|
|
|
57 |
jsr166 |
1.6 |
// Tuning parameters. |
58 |
dl |
1.2 |
|
59 |
|
|
/** |
60 |
dl |
1.4 |
* The number of chromosomes per subpop. Must be a power of two. |
61 |
dl |
1.2 |
* |
62 |
|
|
* Smaller values lead to faster iterations but poorer quality |
63 |
|
|
* results |
64 |
|
|
*/ |
65 |
jsr166 |
1.6 |
static final int DEFAULT_SUBPOP_SIZE = 32; |
66 |
dl |
1.1 |
|
67 |
dl |
1.2 |
/** |
68 |
dl |
1.4 |
* The number of iterations per subpop. Convergence appears |
69 |
dl |
1.2 |
* to be roughly proportional to #cities-squared |
70 |
|
|
*/ |
71 |
|
|
static final int DEFAULT_GENERATIONS = DEFAULT_CITIES * DEFAULT_CITIES; |
72 |
|
|
|
73 |
|
|
/** |
74 |
dl |
1.4 |
* The number of subpops. The total population is #subpops * subpopSize, |
75 |
dl |
1.2 |
* which should be roughly on the order of #cities-squared |
76 |
|
|
* |
77 |
|
|
* Smaller values lead to faster total runs but poorer quality |
78 |
|
|
* results |
79 |
|
|
*/ |
80 |
dl |
1.4 |
static final int DEFAULT_NSUBPOPS = DEFAULT_GENERATIONS / DEFAULT_SUBPOP_SIZE; |
81 |
dl |
1.2 |
|
82 |
|
|
/** |
83 |
|
|
* The minimum length for a random chromosome strand. |
84 |
|
|
* Must be at least 1. |
85 |
|
|
*/ |
86 |
|
|
static final int MIN_STRAND_LENGTH = 3; |
87 |
|
|
|
88 |
|
|
/** |
89 |
jsr166 |
1.5 |
* The probability mask value for creating random strands, |
90 |
dl |
1.2 |
* that have lengths at least MIN_STRAND_LENGTH, and grow |
91 |
|
|
* with exposnential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) |
92 |
|
|
* Must be 1 less than a power of two. |
93 |
|
|
*/ |
94 |
|
|
static final int RANDOM_STRAND_MASK = 7; |
95 |
|
|
|
96 |
|
|
/** |
97 |
jsr166 |
1.5 |
* Probability control for selecting breeders. |
98 |
dl |
1.2 |
* Breeders are selected starting at the best-fitness chromosome, |
99 |
jsr166 |
1.5 |
* with exponentially decaying probability |
100 |
jsr166 |
1.6 |
* 1 / (subpopSize >>> BREEDER_DECAY). |
101 |
dl |
1.2 |
* |
102 |
|
|
* Larger values usually cause faster convergence but poorer |
103 |
|
|
* quality results |
104 |
|
|
*/ |
105 |
|
|
static final int BREEDER_DECAY = 1; |
106 |
|
|
|
107 |
|
|
/** |
108 |
jsr166 |
1.5 |
* Probability control for selecting dyers. |
109 |
dl |
1.2 |
* Dyers are selected starting at the worst-fitness chromosome, |
110 |
jsr166 |
1.5 |
* with exponentially decaying probability |
111 |
dl |
1.4 |
* 1 / (subpopSize >>> DYER_DECAY) |
112 |
dl |
1.2 |
* |
113 |
|
|
* Larger values usually cause faster convergence but poorer |
114 |
|
|
* quality results |
115 |
|
|
*/ |
116 |
|
|
static final int DYER_DECAY = 1; |
117 |
|
|
|
118 |
|
|
/** |
119 |
|
|
* The set of cities. Created once per program run, to |
120 |
|
|
* make it easier to compare solutions across different runs. |
121 |
|
|
*/ |
122 |
jsr166 |
1.6 |
static CitySet cities; |
123 |
dl |
1.1 |
|
124 |
|
|
public static void main(String[] args) throws Exception { |
125 |
dl |
1.2 |
int maxThreads = DEFAULT_MAX_THREADS; |
126 |
dl |
1.1 |
int nCities = DEFAULT_CITIES; |
127 |
dl |
1.4 |
int subpopSize = DEFAULT_SUBPOP_SIZE; |
128 |
dl |
1.2 |
int nGen = nCities * nCities; |
129 |
dl |
1.4 |
int nSubpops = nCities * nCities / subpopSize; |
130 |
|
|
int nReps = DEFAULT_REPLICATIONS; |
131 |
dl |
1.1 |
|
132 |
|
|
try { |
133 |
dl |
1.2 |
int argc = 0; |
134 |
dl |
1.1 |
while (argc < args.length) { |
135 |
|
|
String option = args[argc++]; |
136 |
dl |
1.2 |
if (option.equals("-c")) { |
137 |
dl |
1.1 |
nCities = Integer.parseInt(args[argc]); |
138 |
dl |
1.2 |
nGen = nCities * nCities; |
139 |
dl |
1.4 |
nSubpops = nCities * nCities / subpopSize; |
140 |
dl |
1.2 |
} |
141 |
|
|
else if (option.equals("-p")) |
142 |
dl |
1.4 |
subpopSize = Integer.parseInt(args[argc]); |
143 |
dl |
1.1 |
else if (option.equals("-g")) |
144 |
dl |
1.2 |
nGen = Integer.parseInt(args[argc]); |
145 |
|
|
else if (option.equals("-n")) |
146 |
dl |
1.4 |
nSubpops = Integer.parseInt(args[argc]); |
147 |
|
|
else if (option.equals("-q")) { |
148 |
|
|
verbose = false; |
149 |
|
|
argc--; |
150 |
|
|
} |
151 |
|
|
else if (option.equals("-r")) |
152 |
|
|
nReps = Integer.parseInt(args[argc]); |
153 |
dl |
1.2 |
else |
154 |
dl |
1.1 |
maxThreads = Integer.parseInt(option); |
155 |
|
|
argc++; |
156 |
|
|
} |
157 |
|
|
} |
158 |
|
|
catch (Exception e) { |
159 |
|
|
reportUsageErrorAndDie(); |
160 |
|
|
} |
161 |
|
|
|
162 |
dl |
1.2 |
System.out.print("TSPExchangerTest"); |
163 |
|
|
System.out.print(" -c " + nCities); |
164 |
|
|
System.out.print(" -g " + nGen); |
165 |
dl |
1.4 |
System.out.print(" -p " + subpopSize); |
166 |
|
|
System.out.print(" -n " + nSubpops); |
167 |
|
|
System.out.print(" -r " + nReps); |
168 |
dl |
1.2 |
System.out.print(" max threads " + maxThreads); |
169 |
|
|
System.out.println(); |
170 |
|
|
|
171 |
|
|
cities = new CitySet(nCities); |
172 |
dl |
1.1 |
|
173 |
dl |
1.4 |
if (false && NCPUS > 4) { |
174 |
|
|
int h = NCPUS/2; |
175 |
|
|
System.out.printf("Threads: %4d Warmup\n", h); |
176 |
|
|
oneRun(h, nSubpops, subpopSize, nGen); |
177 |
|
|
Thread.sleep(500); |
178 |
|
|
} |
179 |
|
|
|
180 |
|
|
int maxt = (maxThreads < nSubpops) ? maxThreads : nSubpops; |
181 |
|
|
for (int j = 0; j < nReps; ++j) { |
182 |
|
|
for (int i = 2; i <= maxt; i += 2) { |
183 |
|
|
System.out.printf("Threads: %4d Replication: %2d\n", i, j); |
184 |
|
|
oneRun(i, nSubpops, subpopSize, nGen); |
185 |
|
|
Thread.sleep(500); |
186 |
|
|
} |
187 |
|
|
} |
188 |
dl |
1.1 |
} |
189 |
|
|
|
190 |
dl |
1.2 |
static void reportUsageErrorAndDie() { |
191 |
|
|
System.out.print("usage: TSPExchangerTest"); |
192 |
|
|
System.out.print(" [-c #cities]"); |
193 |
dl |
1.4 |
System.out.print(" [-p #subpopSize]"); |
194 |
dl |
1.2 |
System.out.print(" [-g #generations]"); |
195 |
dl |
1.4 |
System.out.print(" [-n #subpops]"); |
196 |
|
|
System.out.print(" [-r #replications]"); |
197 |
|
|
System.out.print(" [-q <quiet>]"); |
198 |
dl |
1.2 |
System.out.print(" #threads]"); |
199 |
|
|
System.out.println(); |
200 |
dl |
1.1 |
System.exit(0); |
201 |
|
|
} |
202 |
|
|
|
203 |
dl |
1.2 |
/** |
204 |
dl |
1.4 |
* Perform one run with the given parameters. Each run complete |
205 |
|
|
* when there are fewer than 2 active threads. When there is |
206 |
|
|
* only one remaining thread, it will have no one to exchange |
207 |
|
|
* with, so it is terminated (via interrupt). |
208 |
dl |
1.2 |
*/ |
209 |
jsr166 |
1.6 |
static void oneRun(int nThreads, int nSubpops, int subpopSize, int nGen) |
210 |
dl |
1.2 |
throws InterruptedException { |
211 |
dl |
1.4 |
Population p = new Population(nThreads, nSubpops, subpopSize, nGen); |
212 |
dl |
1.2 |
ProgressMonitor mon = null; |
213 |
|
|
if (verbose) { |
214 |
dl |
1.4 |
p.printSnapshot(0); |
215 |
dl |
1.2 |
mon = new ProgressMonitor(p); |
216 |
|
|
mon.start(); |
217 |
|
|
} |
218 |
|
|
long startTime = System.nanoTime(); |
219 |
|
|
p.start(); |
220 |
dl |
1.4 |
p.awaitDone(); |
221 |
dl |
1.2 |
long stopTime = System.nanoTime(); |
222 |
|
|
if (mon != null) |
223 |
|
|
mon.interrupt(); |
224 |
|
|
p.shutdown(); |
225 |
dl |
1.4 |
// Thread.sleep(100); |
226 |
dl |
1.2 |
|
227 |
dl |
1.1 |
long elapsed = stopTime - startTime; |
228 |
dl |
1.2 |
double secs = (double)elapsed / 1000000000.0; |
229 |
|
|
p.printSnapshot(secs); |
230 |
|
|
} |
231 |
dl |
1.1 |
|
232 |
|
|
|
233 |
dl |
1.2 |
/** |
234 |
dl |
1.4 |
* A Population creates the subpops, subpops, and threads for a run |
235 |
dl |
1.2 |
* and has control methods to start, stop, and report progress. |
236 |
|
|
*/ |
237 |
dl |
1.1 |
static final class Population { |
238 |
dl |
1.4 |
final Worker[] threads; |
239 |
|
|
final Subpop[] subpops; |
240 |
dl |
1.2 |
final Exchanger<Strand> exchanger; |
241 |
|
|
final CountDownLatch done; |
242 |
|
|
final int nGen; |
243 |
dl |
1.4 |
final int subpopSize; |
244 |
dl |
1.1 |
final int nThreads; |
245 |
|
|
|
246 |
dl |
1.4 |
Population(int nThreads, int nSubpops, int subpopSize, int nGen) { |
247 |
dl |
1.1 |
this.nThreads = nThreads; |
248 |
dl |
1.2 |
this.nGen = nGen; |
249 |
dl |
1.4 |
this.subpopSize = subpopSize; |
250 |
dl |
1.2 |
this.exchanger = new Exchanger<Strand>(); |
251 |
dl |
1.4 |
this.done = new CountDownLatch(nThreads - 1); |
252 |
|
|
|
253 |
|
|
this.subpops = new Subpop[nSubpops]; |
254 |
|
|
for (int i = 0; i < nSubpops; i++) |
255 |
|
|
subpops[i] = new Subpop(this); |
256 |
|
|
|
257 |
|
|
this.threads = new Worker[nThreads]; |
258 |
|
|
int maxExchanges = nGen * nSubpops / nThreads; |
259 |
|
|
for (int i = 0; i < nThreads; ++i) { |
260 |
|
|
threads[i] = new Worker(this, maxExchanges); |
261 |
|
|
} |
262 |
|
|
|
263 |
dl |
1.2 |
} |
264 |
|
|
|
265 |
|
|
void start() { |
266 |
dl |
1.4 |
for (int i = 0; i < nThreads; ++i) { |
267 |
jsr166 |
1.6 |
threads[i].start(); |
268 |
dl |
1.4 |
} |
269 |
dl |
1.2 |
} |
270 |
|
|
|
271 |
|
|
/** Stop the tasks */ |
272 |
|
|
void shutdown() { |
273 |
dl |
1.4 |
for (int i = 0; i < threads.length; ++ i) |
274 |
|
|
threads[i].interrupt(); |
275 |
dl |
1.2 |
} |
276 |
|
|
|
277 |
dl |
1.4 |
void threadDone() { |
278 |
dl |
1.2 |
done.countDown(); |
279 |
|
|
} |
280 |
|
|
|
281 |
dl |
1.4 |
/** Wait for tasks to complete */ |
282 |
|
|
void awaitDone() throws InterruptedException { |
283 |
dl |
1.2 |
done.await(); |
284 |
|
|
} |
285 |
|
|
|
286 |
dl |
1.4 |
int totalExchanges() { |
287 |
|
|
int xs = 0; |
288 |
jsr166 |
1.6 |
for (int i = 0; i < threads.length; ++i) |
289 |
dl |
1.4 |
xs += threads[i].exchanges; |
290 |
|
|
return xs; |
291 |
dl |
1.2 |
} |
292 |
|
|
|
293 |
dl |
1.4 |
/** |
294 |
|
|
* Prints statistics, including best and worst tour lengths |
295 |
|
|
* for points scaled in [0,1), scaled by the square root of |
296 |
|
|
* number of points. This simplifies checking results. The |
297 |
|
|
* expected optimal TSP for random points is believed to be |
298 |
|
|
* around 0.76 * sqrt(N). For papers discussing this, see |
299 |
|
|
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html |
300 |
|
|
*/ |
301 |
dl |
1.2 |
void printSnapshot(double secs) { |
302 |
dl |
1.4 |
int xs = totalExchanges(); |
303 |
|
|
long rate = (xs == 0)? 0L : (long)((secs * 1000000000.0) / xs); |
304 |
|
|
Chromosome bestc = subpops[0].chromosomes[0]; |
305 |
dl |
1.3 |
Chromosome worstc = bestc; |
306 |
dl |
1.4 |
for (int k = 0; k < subpops.length; ++k) { |
307 |
|
|
Chromosome[] cs = subpops[k].chromosomes; |
308 |
dl |
1.3 |
if (cs[0].fitness < bestc.fitness) |
309 |
|
|
bestc = cs[0]; |
310 |
|
|
int w = cs[cs.length-1].fitness; |
311 |
|
|
if (cs[cs.length-1].fitness > worstc.fitness) |
312 |
|
|
worstc = cs[cs.length-1]; |
313 |
|
|
} |
314 |
|
|
double sqrtn = Math.sqrt(cities.length); |
315 |
|
|
double best = bestc.unitTourLength() / sqrtn; |
316 |
|
|
double worst = worstc.unitTourLength() / sqrtn; |
317 |
dl |
1.4 |
System.out.printf("N:%4d T:%8.3f B:%6.3f W:%6.3f X:%9d R:%7d\n", |
318 |
|
|
nThreads, secs, best, worst, xs, rate); |
319 |
|
|
// exchanger.printStats(); |
320 |
|
|
// System.out.print(" s: " + exchanger.aveSpins()); |
321 |
|
|
// System.out.print(" p: " + exchanger.aveParks()); |
322 |
dl |
1.2 |
} |
323 |
|
|
} |
324 |
dl |
1.1 |
|
325 |
dl |
1.2 |
/** |
326 |
dl |
1.4 |
* Worker threads perform updates on subpops. |
327 |
dl |
1.2 |
*/ |
328 |
dl |
1.4 |
static final class Worker extends Thread { |
329 |
|
|
final Population pop; |
330 |
|
|
final int maxExchanges; |
331 |
|
|
int exchanges; |
332 |
|
|
final RNG rng = new RNG(); |
333 |
|
|
|
334 |
|
|
Worker(Population pop, int maxExchanges) { |
335 |
|
|
this.pop = pop; |
336 |
|
|
this.maxExchanges = maxExchanges; |
337 |
|
|
} |
338 |
|
|
|
339 |
|
|
/** |
340 |
|
|
* Repeatedly, find a subpop that is not being updated by |
341 |
|
|
* another thread, and run a random number of updates on it. |
342 |
|
|
*/ |
343 |
|
|
public void run() { |
344 |
|
|
try { |
345 |
|
|
int len = pop.subpops.length; |
346 |
|
|
int pos = (rng.next() & 0x7FFFFFFF) % len; |
347 |
|
|
while (exchanges < maxExchanges) { |
348 |
|
|
Subpop s = pop.subpops[pos]; |
349 |
|
|
AtomicBoolean busy = s.busy; |
350 |
|
|
if (!busy.get() && busy.compareAndSet(false, true)) { |
351 |
|
|
exchanges += s.runUpdates(); |
352 |
|
|
busy.set(false); |
353 |
|
|
pos = (rng.next() & 0x7FFFFFFF) % len; |
354 |
|
|
} |
355 |
|
|
else if (++pos >= len) |
356 |
|
|
pos = 0; |
357 |
|
|
} |
358 |
|
|
pop.threadDone(); |
359 |
|
|
} catch (InterruptedException fallthrough) { |
360 |
|
|
} |
361 |
|
|
} |
362 |
|
|
} |
363 |
|
|
|
364 |
|
|
/** |
365 |
jsr166 |
1.6 |
* A Subpop maintains a set of chromosomes.. |
366 |
dl |
1.4 |
*/ |
367 |
|
|
static final class Subpop { |
368 |
|
|
/** The chromosomes, kept in sorted order */ |
369 |
dl |
1.2 |
final Chromosome[] chromosomes; |
370 |
dl |
1.4 |
/** The parent population */ |
371 |
dl |
1.2 |
final Population pop; |
372 |
dl |
1.4 |
/** Reservation bit for worker threads */ |
373 |
|
|
final AtomicBoolean busy; |
374 |
|
|
/** The common exchanger, same for all subpops */ |
375 |
dl |
1.2 |
final Exchanger<Strand> exchanger; |
376 |
|
|
/** The current strand being exchanged */ |
377 |
|
|
Strand strand; |
378 |
|
|
/** Bitset used in cross */ |
379 |
|
|
final int[] inTour; |
380 |
|
|
final RNG rng; |
381 |
dl |
1.4 |
final int subpopSize; |
382 |
dl |
1.1 |
|
383 |
dl |
1.4 |
Subpop(Population pop) { |
384 |
dl |
1.2 |
this.pop = pop; |
385 |
dl |
1.4 |
this.subpopSize = pop.subpopSize; |
386 |
dl |
1.2 |
this.exchanger = pop.exchanger; |
387 |
dl |
1.4 |
this.busy = new AtomicBoolean(false); |
388 |
dl |
1.2 |
this.rng = new RNG(); |
389 |
|
|
int length = cities.length; |
390 |
|
|
this.strand = new Strand(length); |
391 |
|
|
this.inTour = new int[(length >>> 5) + 1]; |
392 |
dl |
1.4 |
this.chromosomes = new Chromosome[subpopSize]; |
393 |
|
|
for (int j = 0; j < subpopSize; ++j) |
394 |
dl |
1.2 |
chromosomes[j] = new Chromosome(length, rng); |
395 |
|
|
Arrays.sort(chromosomes); |
396 |
|
|
} |
397 |
|
|
|
398 |
|
|
/** |
399 |
dl |
1.4 |
* Run a random number of updates. The number of updates is |
400 |
|
|
* at least 1 and no more than subpopSize. This |
401 |
|
|
* controls the granularity of multiplexing subpop updates on |
402 |
|
|
* to threads. It is small enough to balance out updates |
403 |
|
|
* across tasks, but large enough to avoid having runs |
404 |
|
|
* dominated by subpop selection. It is randomized to avoid |
405 |
|
|
* long runs where pairs of subpops exchange only with each |
406 |
|
|
* other. It is hardwired because small variations of it |
407 |
|
|
* don't matter much. |
408 |
|
|
* |
409 |
jsr166 |
1.6 |
* @param g the first generation to run. |
410 |
dl |
1.4 |
*/ |
411 |
|
|
int runUpdates() throws InterruptedException { |
412 |
|
|
int n = 1 + (rng.next() & ((subpopSize << 1) - 1)); |
413 |
|
|
for (int i = 0; i < n; ++i) |
414 |
|
|
update(); |
415 |
|
|
return n; |
416 |
dl |
1.1 |
} |
417 |
|
|
|
418 |
dl |
1.2 |
/** |
419 |
dl |
1.4 |
* Choose a breeder, exchange strand with another subpop, and |
420 |
dl |
1.2 |
* cross them to create new chromosome to replace a chosen |
421 |
|
|
* dyer. |
422 |
|
|
*/ |
423 |
|
|
void update() throws InterruptedException { |
424 |
|
|
int b = chooseBreeder(); |
425 |
|
|
int d = chooseDyer(b); |
426 |
|
|
Chromosome breeder = chromosomes[b]; |
427 |
|
|
Chromosome child = chromosomes[d]; |
428 |
|
|
chooseStrand(breeder); |
429 |
|
|
strand = exchanger.exchange(strand); |
430 |
|
|
cross(breeder, child); |
431 |
|
|
fixOrder(child, d); |
432 |
|
|
} |
433 |
|
|
|
434 |
|
|
/** |
435 |
|
|
* Choose a breeder, with exponentially decreasing probability |
436 |
|
|
* starting at best. |
437 |
|
|
* @return index of selected breeder |
438 |
|
|
*/ |
439 |
|
|
int chooseBreeder() { |
440 |
dl |
1.4 |
int mask = (subpopSize >>> BREEDER_DECAY) - 1; |
441 |
dl |
1.2 |
int b = 0; |
442 |
|
|
while ((rng.next() & mask) != mask) { |
443 |
dl |
1.4 |
if (++b >= subpopSize) |
444 |
dl |
1.2 |
b = 0; |
445 |
|
|
} |
446 |
|
|
return b; |
447 |
|
|
} |
448 |
|
|
|
449 |
|
|
/** |
450 |
|
|
* Choose a chromosome that will be replaced, with |
451 |
jsr166 |
1.5 |
* exponentially decreasing probability starting at |
452 |
dl |
1.2 |
* worst, ignoring the excluded index |
453 |
|
|
* @param exclude index to ignore; use -1 to not exclude any |
454 |
|
|
* @return index of selected dyer |
455 |
|
|
*/ |
456 |
|
|
int chooseDyer(int exclude) { |
457 |
dl |
1.4 |
int mask = (subpopSize >>> DYER_DECAY) - 1; |
458 |
|
|
int d = subpopSize - 1; |
459 |
dl |
1.2 |
while (d == exclude || (rng.next() & mask) != mask) { |
460 |
|
|
if (--d < 0) |
461 |
dl |
1.4 |
d = subpopSize - 1; |
462 |
dl |
1.2 |
} |
463 |
|
|
return d; |
464 |
|
|
} |
465 |
|
|
|
466 |
jsr166 |
1.6 |
/** |
467 |
dl |
1.2 |
* Select a random strand of b's. |
468 |
|
|
* @param breeder the breeder |
469 |
|
|
*/ |
470 |
|
|
void chooseStrand(Chromosome breeder) { |
471 |
|
|
int[] bs = breeder.alleles; |
472 |
|
|
int length = bs.length; |
473 |
|
|
int strandLength = MIN_STRAND_LENGTH; |
474 |
|
|
while (strandLength < length && |
475 |
|
|
(rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK) |
476 |
|
|
strandLength++; |
477 |
|
|
strand.strandLength = strandLength; |
478 |
|
|
int[] ss = strand.alleles; |
479 |
|
|
int k = (rng.next() & 0x7FFFFFFF) % length; |
480 |
|
|
for (int i = 0; i < strandLength; ++i) { |
481 |
|
|
ss[i] = bs[k]; |
482 |
|
|
if (++k >= length) k = 0; |
483 |
|
|
} |
484 |
|
|
} |
485 |
|
|
|
486 |
|
|
/** |
487 |
|
|
* Copy current strand to start of c's, and then append all |
488 |
|
|
* remaining b's that aren't in the strand. |
489 |
|
|
* @param breeder the breeder |
490 |
|
|
* @param child the child |
491 |
|
|
*/ |
492 |
|
|
void cross(Chromosome breeder, Chromosome child) { |
493 |
|
|
for (int k = 0; k < inTour.length; ++k) // clear bitset |
494 |
|
|
inTour[k] = 0; |
495 |
|
|
|
496 |
|
|
// Copy current strand to c |
497 |
|
|
int[] cs = child.alleles; |
498 |
|
|
int ssize = strand.strandLength; |
499 |
|
|
int[] ss = strand.alleles; |
500 |
|
|
int i; |
501 |
|
|
for (i = 0; i < ssize; ++i) { |
502 |
|
|
int x = ss[i]; |
503 |
|
|
cs[i] = x; |
504 |
|
|
inTour[x >>> 5] |= 1 << (x & 31); // record in bit set |
505 |
|
|
} |
506 |
|
|
|
507 |
|
|
// Find index of matching origin in b |
508 |
|
|
int first = cs[0]; |
509 |
|
|
int j = 0; |
510 |
|
|
int[] bs = breeder.alleles; |
511 |
jsr166 |
1.6 |
while (bs[j] != first) |
512 |
dl |
1.2 |
++j; |
513 |
|
|
|
514 |
|
|
// Append remaining b's that aren't already in tour |
515 |
|
|
while (i < cs.length) { |
516 |
|
|
if (++j >= bs.length) j = 0; |
517 |
|
|
int x = bs[j]; |
518 |
|
|
if ((inTour[x >>> 5] & (1 << (x & 31))) == 0) |
519 |
|
|
cs[i++] = x; |
520 |
jsr166 |
1.6 |
} |
521 |
dl |
1.1 |
|
522 |
|
|
} |
523 |
|
|
|
524 |
dl |
1.2 |
/** |
525 |
|
|
* Fix the sort order of a changed Chromosome c at position k |
526 |
|
|
* @param c the chromosome |
527 |
jsr166 |
1.6 |
* @param k the index |
528 |
dl |
1.2 |
*/ |
529 |
|
|
void fixOrder(Chromosome c, int k) { |
530 |
|
|
Chromosome[] cs = chromosomes; |
531 |
dl |
1.3 |
int oldFitness = c.fitness; |
532 |
dl |
1.2 |
c.recalcFitness(); |
533 |
dl |
1.3 |
int newFitness = c.fitness; |
534 |
dl |
1.2 |
if (newFitness < oldFitness) { |
535 |
|
|
int j = k; |
536 |
|
|
int p = j - 1; |
537 |
|
|
while (p >= 0 && cs[p].fitness > newFitness) { |
538 |
|
|
cs[j] = cs[p]; |
539 |
|
|
j = p--; |
540 |
dl |
1.1 |
} |
541 |
dl |
1.2 |
cs[j] = c; |
542 |
|
|
} else if (newFitness > oldFitness) { |
543 |
|
|
int j = k; |
544 |
|
|
int n = j + 1; |
545 |
|
|
while (n < cs.length && cs[n].fitness < newFitness) { |
546 |
|
|
cs[j] = cs[n]; |
547 |
|
|
j = n++; |
548 |
dl |
1.1 |
} |
549 |
dl |
1.2 |
cs[j] = c; |
550 |
dl |
1.1 |
} |
551 |
|
|
} |
552 |
|
|
} |
553 |
|
|
|
554 |
dl |
1.2 |
/** |
555 |
|
|
* A Chromosome is a candidate TSP tour. |
556 |
|
|
*/ |
557 |
|
|
static final class Chromosome implements Comparable { |
558 |
|
|
/** Index of cities in tour order */ |
559 |
|
|
final int[] alleles; |
560 |
|
|
/** Total tour length */ |
561 |
dl |
1.3 |
int fitness; |
562 |
dl |
1.2 |
|
563 |
jsr166 |
1.6 |
/** |
564 |
dl |
1.2 |
* Initialize to random tour |
565 |
|
|
*/ |
566 |
|
|
Chromosome(int length, RNG random) { |
567 |
dl |
1.1 |
alleles = new int[length]; |
568 |
|
|
for (int i = 0; i < length; i++) |
569 |
|
|
alleles[i] = i; |
570 |
|
|
for (int i = length - 1; i > 0; i--) { |
571 |
dl |
1.2 |
int idx = (random.next() & 0x7FFFFFFF) % alleles.length; |
572 |
dl |
1.1 |
int tmp = alleles[i]; |
573 |
|
|
alleles[i] = alleles[idx]; |
574 |
|
|
alleles[idx] = tmp; |
575 |
|
|
} |
576 |
|
|
recalcFitness(); |
577 |
|
|
} |
578 |
dl |
1.2 |
|
579 |
|
|
public int compareTo(Object x) { // to enable sorting |
580 |
dl |
1.3 |
int xf = ((Chromosome)x).fitness; |
581 |
|
|
int f = fitness; |
582 |
dl |
1.2 |
return ((f == xf)? 0 :((f < xf)? -1 : 1)); |
583 |
dl |
1.1 |
} |
584 |
dl |
1.2 |
|
585 |
dl |
1.1 |
void recalcFitness() { |
586 |
dl |
1.2 |
int[] a = alleles; |
587 |
|
|
int len = a.length; |
588 |
|
|
int p = a[0]; |
589 |
dl |
1.3 |
long f = cities.distanceBetween(a[len-1], p); |
590 |
dl |
1.2 |
for (int i = 1; i < len; i++) { |
591 |
|
|
int n = a[i]; |
592 |
|
|
f += cities.distanceBetween(p, n); |
593 |
|
|
p = n; |
594 |
|
|
} |
595 |
dl |
1.3 |
fitness = (int)(f / len); |
596 |
|
|
} |
597 |
|
|
|
598 |
dl |
1.4 |
/** |
599 |
|
|
* Return tour length for points scaled in [0, 1). |
600 |
|
|
*/ |
601 |
dl |
1.3 |
double unitTourLength() { |
602 |
|
|
int[] a = alleles; |
603 |
|
|
int len = a.length; |
604 |
|
|
int p = a[0]; |
605 |
|
|
double f = cities.unitDistanceBetween(a[len-1], p); |
606 |
|
|
for (int i = 1; i < len; i++) { |
607 |
|
|
int n = a[i]; |
608 |
|
|
f += cities.unitDistanceBetween(p, n); |
609 |
|
|
p = n; |
610 |
|
|
} |
611 |
|
|
return f; |
612 |
dl |
1.2 |
} |
613 |
|
|
|
614 |
dl |
1.4 |
/** |
615 |
|
|
* Check that this tour visits each city |
616 |
|
|
*/ |
617 |
jsr166 |
1.6 |
void validate() { |
618 |
dl |
1.2 |
int len = alleles.length; |
619 |
|
|
boolean[] used = new boolean[len]; |
620 |
jsr166 |
1.6 |
for (int i = 0; i < len; ++i) |
621 |
dl |
1.2 |
used[alleles[i]] = true; |
622 |
jsr166 |
1.6 |
for (int i = 0; i < len; ++i) |
623 |
dl |
1.2 |
if (!used[i]) |
624 |
|
|
throw new Error("Bad tour"); |
625 |
dl |
1.1 |
} |
626 |
dl |
1.2 |
|
627 |
|
|
} |
628 |
|
|
|
629 |
|
|
/** |
630 |
dl |
1.4 |
* A Strand is a random sub-sequence of a Chromosome. Each subpop |
631 |
dl |
1.2 |
* creates only one strand, and then trades it with others, |
632 |
|
|
* refilling it on each iteration. |
633 |
|
|
*/ |
634 |
|
|
static final class Strand { |
635 |
|
|
final int[] alleles; |
636 |
|
|
int strandLength; |
637 |
|
|
Strand(int length) { alleles = new int[length]; } |
638 |
dl |
1.1 |
} |
639 |
dl |
1.2 |
|
640 |
dl |
1.1 |
/** |
641 |
jsr166 |
1.6 |
* A collection of (x,y) points that represent cities. |
642 |
dl |
1.1 |
*/ |
643 |
|
|
static final class CitySet { |
644 |
dl |
1.2 |
|
645 |
dl |
1.1 |
final int length; |
646 |
dl |
1.2 |
final int[] xPts; |
647 |
|
|
final int[] yPts; |
648 |
dl |
1.3 |
final int[][] distances; |
649 |
dl |
1.2 |
|
650 |
|
|
CitySet(int n) { |
651 |
dl |
1.1 |
this.length = n; |
652 |
dl |
1.2 |
this.xPts = new int[n]; |
653 |
|
|
this.yPts = new int[n]; |
654 |
dl |
1.3 |
this.distances = new int[n][n]; |
655 |
dl |
1.2 |
|
656 |
|
|
RNG random = new RNG(); |
657 |
dl |
1.1 |
for (int i = 0; i < n; i++) { |
658 |
dl |
1.2 |
xPts[i] = (random.next() & 0x7FFFFFFF); |
659 |
|
|
yPts[i] = (random.next() & 0x7FFFFFFF); |
660 |
dl |
1.1 |
} |
661 |
dl |
1.2 |
|
662 |
dl |
1.1 |
for (int i = 0; i < n; i++) { |
663 |
|
|
for (int j = 0; j < n; j++) { |
664 |
dl |
1.3 |
double dx = (double)xPts[i] - (double)xPts[j]; |
665 |
|
|
double dy = (double)yPts[i] - (double)yPts[j]; |
666 |
|
|
double dd = Math.hypot(dx, dy) / 2.0; |
667 |
|
|
long ld = Math.round(dd); |
668 |
jsr166 |
1.6 |
distances[i][j] = (ld >= Integer.MAX_VALUE)? |
669 |
dl |
1.3 |
Integer.MAX_VALUE : (int)ld; |
670 |
dl |
1.1 |
} |
671 |
|
|
} |
672 |
|
|
} |
673 |
dl |
1.2 |
|
674 |
dl |
1.3 |
/** |
675 |
|
|
* Returns the cached distance between a pair of cities |
676 |
|
|
*/ |
677 |
|
|
int distanceBetween(int i, int j) { |
678 |
dl |
1.2 |
return distances[i][j]; |
679 |
|
|
} |
680 |
dl |
1.3 |
|
681 |
|
|
// Scale ints to doubles in [0,1) |
682 |
|
|
static final double PSCALE = (double)0x80000000L; |
683 |
|
|
|
684 |
|
|
/** |
685 |
|
|
* Return distance for points scaled in [0,1). This simplifies |
686 |
|
|
* checking results. The expected optimal TSP for random |
687 |
|
|
* points is believed to be around 0.76 * sqrt(N). For papers |
688 |
|
|
* discussing this, see |
689 |
|
|
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html |
690 |
|
|
*/ |
691 |
|
|
double unitDistanceBetween(int i, int j) { |
692 |
|
|
double dx = ((double)xPts[i] - (double)xPts[j]) / PSCALE; |
693 |
|
|
double dy = ((double)yPts[i] - (double)yPts[j]) / PSCALE; |
694 |
|
|
return Math.hypot(dx, dy); |
695 |
|
|
} |
696 |
jsr166 |
1.6 |
|
697 |
dl |
1.2 |
} |
698 |
|
|
|
699 |
|
|
/** |
700 |
|
|
* Cheap XorShift random number generator |
701 |
|
|
*/ |
702 |
|
|
static final class RNG { |
703 |
|
|
/** Seed generator for XorShift RNGs */ |
704 |
|
|
static final Random seedGenerator = new Random(); |
705 |
|
|
|
706 |
|
|
int seed; |
707 |
|
|
RNG(int seed) { this.seed = seed; } |
708 |
dl |
1.3 |
RNG() { this.seed = seedGenerator.nextInt() | 1; } |
709 |
dl |
1.2 |
|
710 |
|
|
int next() { |
711 |
|
|
int x = seed; |
712 |
|
|
x ^= x << 6; |
713 |
|
|
x ^= x >>> 21; |
714 |
|
|
x ^= x << 7; |
715 |
|
|
seed = x; |
716 |
|
|
return x; |
717 |
dl |
1.1 |
} |
718 |
|
|
} |
719 |
|
|
|
720 |
dl |
1.2 |
static final class ProgressMonitor extends Thread { |
721 |
dl |
1.1 |
final Population pop; |
722 |
dl |
1.2 |
ProgressMonitor(Population p) { pop = p; } |
723 |
dl |
1.1 |
public void run() { |
724 |
dl |
1.2 |
double time = 0; |
725 |
dl |
1.1 |
try { |
726 |
dl |
1.2 |
while (!Thread.interrupted()) { |
727 |
|
|
sleep(SNAPSHOT_RATE); |
728 |
|
|
time += SNAPSHOT_RATE; |
729 |
|
|
pop.printSnapshot(time / 1000.0); |
730 |
dl |
1.1 |
} |
731 |
dl |
1.2 |
} catch (InterruptedException ie) {} |
732 |
dl |
1.1 |
} |
733 |
|
|
} |
734 |
|
|
} |