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 |
jsr166 |
1.12 |
* explained at http://creativecommons.org/publicdomain/zero/1.0/ |
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 |
jsr166 |
1.19 |
* <li>Select a breeder b from the subpop |
22 |
|
|
* <li>Create a strand of its tour with a random starting point and length |
23 |
|
|
* <li>Offer the strand to the exchanger, receiving a strand from |
24 |
|
|
* another subpop |
25 |
|
|
* <li>Combine b and the received strand using crossing function to |
26 |
|
|
* create new chromosome c. |
27 |
|
|
* <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 |
jsr166 |
1.17 |
static final int DEFAULT_MAX_THREADS = Math.max(4, NCPUS + NCPUS/2); |
43 |
dl |
1.4 |
|
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 |
jsr166 |
1.7 |
* with exponential decay 2^(-(1/(RANDOM_STRAND_MASK + 1) |
92 |
dl |
1.2 |
* 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 |
jsr166 |
1.14 |
* Performs one run with the given parameters. Each run completes |
205 |
dl |
1.4 |
* 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 |
jsr166 |
1.10 |
double secs = (double) elapsed / 1000000000.0; |
229 |
dl |
1.2 |
p.printSnapshot(secs); |
230 |
|
|
} |
231 |
dl |
1.1 |
|
232 |
dl |
1.2 |
/** |
233 |
dl |
1.4 |
* A Population creates the subpops, subpops, and threads for a run |
234 |
dl |
1.2 |
* and has control methods to start, stop, and report progress. |
235 |
|
|
*/ |
236 |
dl |
1.1 |
static final class Population { |
237 |
dl |
1.4 |
final Worker[] threads; |
238 |
|
|
final Subpop[] subpops; |
239 |
dl |
1.2 |
final Exchanger<Strand> exchanger; |
240 |
|
|
final CountDownLatch done; |
241 |
|
|
final int nGen; |
242 |
dl |
1.4 |
final int subpopSize; |
243 |
dl |
1.1 |
final int nThreads; |
244 |
|
|
|
245 |
dl |
1.4 |
Population(int nThreads, int nSubpops, int subpopSize, int nGen) { |
246 |
dl |
1.1 |
this.nThreads = nThreads; |
247 |
dl |
1.2 |
this.nGen = nGen; |
248 |
dl |
1.4 |
this.subpopSize = subpopSize; |
249 |
dl |
1.2 |
this.exchanger = new Exchanger<Strand>(); |
250 |
dl |
1.4 |
this.done = new CountDownLatch(nThreads - 1); |
251 |
|
|
|
252 |
|
|
this.subpops = new Subpop[nSubpops]; |
253 |
|
|
for (int i = 0; i < nSubpops; i++) |
254 |
|
|
subpops[i] = new Subpop(this); |
255 |
|
|
|
256 |
|
|
this.threads = new Worker[nThreads]; |
257 |
|
|
int maxExchanges = nGen * nSubpops / nThreads; |
258 |
|
|
for (int i = 0; i < nThreads; ++i) { |
259 |
|
|
threads[i] = new Worker(this, maxExchanges); |
260 |
|
|
} |
261 |
|
|
|
262 |
dl |
1.2 |
} |
263 |
|
|
|
264 |
|
|
void start() { |
265 |
dl |
1.4 |
for (int i = 0; i < nThreads; ++i) { |
266 |
jsr166 |
1.6 |
threads[i].start(); |
267 |
dl |
1.4 |
} |
268 |
dl |
1.2 |
} |
269 |
|
|
|
270 |
|
|
/** Stop the tasks */ |
271 |
|
|
void shutdown() { |
272 |
dl |
1.4 |
for (int i = 0; i < threads.length; ++ i) |
273 |
|
|
threads[i].interrupt(); |
274 |
dl |
1.2 |
} |
275 |
|
|
|
276 |
dl |
1.4 |
void threadDone() { |
277 |
dl |
1.2 |
done.countDown(); |
278 |
|
|
} |
279 |
|
|
|
280 |
dl |
1.4 |
/** Wait for tasks to complete */ |
281 |
|
|
void awaitDone() throws InterruptedException { |
282 |
dl |
1.2 |
done.await(); |
283 |
|
|
} |
284 |
|
|
|
285 |
dl |
1.4 |
int totalExchanges() { |
286 |
|
|
int xs = 0; |
287 |
jsr166 |
1.6 |
for (int i = 0; i < threads.length; ++i) |
288 |
dl |
1.4 |
xs += threads[i].exchanges; |
289 |
|
|
return xs; |
290 |
dl |
1.2 |
} |
291 |
|
|
|
292 |
dl |
1.4 |
/** |
293 |
|
|
* Prints statistics, including best and worst tour lengths |
294 |
|
|
* for points scaled in [0,1), scaled by the square root of |
295 |
|
|
* number of points. This simplifies checking results. The |
296 |
|
|
* expected optimal TSP for random points is believed to be |
297 |
|
|
* around 0.76 * sqrt(N). For papers discussing this, see |
298 |
|
|
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html |
299 |
|
|
*/ |
300 |
dl |
1.2 |
void printSnapshot(double secs) { |
301 |
dl |
1.4 |
int xs = totalExchanges(); |
302 |
jsr166 |
1.10 |
long rate = (xs == 0) ? 0L : (long) ((secs * 1000000000.0) / xs); |
303 |
dl |
1.4 |
Chromosome bestc = subpops[0].chromosomes[0]; |
304 |
dl |
1.3 |
Chromosome worstc = bestc; |
305 |
dl |
1.4 |
for (int k = 0; k < subpops.length; ++k) { |
306 |
|
|
Chromosome[] cs = subpops[k].chromosomes; |
307 |
dl |
1.3 |
if (cs[0].fitness < bestc.fitness) |
308 |
|
|
bestc = cs[0]; |
309 |
|
|
int w = cs[cs.length-1].fitness; |
310 |
|
|
if (cs[cs.length-1].fitness > worstc.fitness) |
311 |
|
|
worstc = cs[cs.length-1]; |
312 |
|
|
} |
313 |
|
|
double sqrtn = Math.sqrt(cities.length); |
314 |
|
|
double best = bestc.unitTourLength() / sqrtn; |
315 |
|
|
double worst = worstc.unitTourLength() / sqrtn; |
316 |
dl |
1.4 |
System.out.printf("N:%4d T:%8.3f B:%6.3f W:%6.3f X:%9d R:%7d\n", |
317 |
|
|
nThreads, secs, best, worst, xs, rate); |
318 |
|
|
// exchanger.printStats(); |
319 |
|
|
// System.out.print(" s: " + exchanger.aveSpins()); |
320 |
|
|
// System.out.print(" p: " + exchanger.aveParks()); |
321 |
dl |
1.2 |
} |
322 |
|
|
} |
323 |
dl |
1.1 |
|
324 |
dl |
1.2 |
/** |
325 |
dl |
1.4 |
* Worker threads perform updates on subpops. |
326 |
dl |
1.2 |
*/ |
327 |
dl |
1.4 |
static final class Worker extends Thread { |
328 |
|
|
final Population pop; |
329 |
|
|
final int maxExchanges; |
330 |
|
|
int exchanges; |
331 |
|
|
final RNG rng = new RNG(); |
332 |
|
|
|
333 |
|
|
Worker(Population pop, int maxExchanges) { |
334 |
|
|
this.pop = pop; |
335 |
|
|
this.maxExchanges = maxExchanges; |
336 |
|
|
} |
337 |
|
|
|
338 |
|
|
/** |
339 |
|
|
* Repeatedly, find a subpop that is not being updated by |
340 |
|
|
* another thread, and run a random number of updates on it. |
341 |
|
|
*/ |
342 |
|
|
public void run() { |
343 |
|
|
try { |
344 |
|
|
int len = pop.subpops.length; |
345 |
|
|
int pos = (rng.next() & 0x7FFFFFFF) % len; |
346 |
|
|
while (exchanges < maxExchanges) { |
347 |
|
|
Subpop s = pop.subpops[pos]; |
348 |
|
|
AtomicBoolean busy = s.busy; |
349 |
|
|
if (!busy.get() && busy.compareAndSet(false, true)) { |
350 |
|
|
exchanges += s.runUpdates(); |
351 |
|
|
busy.set(false); |
352 |
|
|
pos = (rng.next() & 0x7FFFFFFF) % len; |
353 |
|
|
} |
354 |
|
|
else if (++pos >= len) |
355 |
|
|
pos = 0; |
356 |
|
|
} |
357 |
|
|
pop.threadDone(); |
358 |
|
|
} catch (InterruptedException fallthrough) { |
359 |
|
|
} |
360 |
|
|
} |
361 |
|
|
} |
362 |
|
|
|
363 |
|
|
/** |
364 |
jsr166 |
1.16 |
* A Subpop maintains a set of chromosomes. |
365 |
dl |
1.4 |
*/ |
366 |
|
|
static final class Subpop { |
367 |
|
|
/** The chromosomes, kept in sorted order */ |
368 |
dl |
1.2 |
final Chromosome[] chromosomes; |
369 |
dl |
1.4 |
/** The parent population */ |
370 |
dl |
1.2 |
final Population pop; |
371 |
dl |
1.4 |
/** Reservation bit for worker threads */ |
372 |
|
|
final AtomicBoolean busy; |
373 |
|
|
/** The common exchanger, same for all subpops */ |
374 |
dl |
1.2 |
final Exchanger<Strand> exchanger; |
375 |
|
|
/** The current strand being exchanged */ |
376 |
|
|
Strand strand; |
377 |
|
|
/** Bitset used in cross */ |
378 |
|
|
final int[] inTour; |
379 |
|
|
final RNG rng; |
380 |
dl |
1.4 |
final int subpopSize; |
381 |
dl |
1.1 |
|
382 |
dl |
1.4 |
Subpop(Population pop) { |
383 |
dl |
1.2 |
this.pop = pop; |
384 |
dl |
1.4 |
this.subpopSize = pop.subpopSize; |
385 |
dl |
1.2 |
this.exchanger = pop.exchanger; |
386 |
dl |
1.4 |
this.busy = new AtomicBoolean(false); |
387 |
dl |
1.2 |
this.rng = new RNG(); |
388 |
|
|
int length = cities.length; |
389 |
|
|
this.strand = new Strand(length); |
390 |
|
|
this.inTour = new int[(length >>> 5) + 1]; |
391 |
dl |
1.4 |
this.chromosomes = new Chromosome[subpopSize]; |
392 |
|
|
for (int j = 0; j < subpopSize; ++j) |
393 |
dl |
1.2 |
chromosomes[j] = new Chromosome(length, rng); |
394 |
|
|
Arrays.sort(chromosomes); |
395 |
|
|
} |
396 |
|
|
|
397 |
|
|
/** |
398 |
dl |
1.4 |
* Run a random number of updates. The number of updates is |
399 |
|
|
* at least 1 and no more than subpopSize. This |
400 |
|
|
* controls the granularity of multiplexing subpop updates on |
401 |
|
|
* to threads. It is small enough to balance out updates |
402 |
|
|
* across tasks, but large enough to avoid having runs |
403 |
|
|
* dominated by subpop selection. It is randomized to avoid |
404 |
|
|
* long runs where pairs of subpops exchange only with each |
405 |
|
|
* other. It is hardwired because small variations of it |
406 |
|
|
* don't matter much. |
407 |
|
|
* |
408 |
jsr166 |
1.15 |
* @param g the first generation to run |
409 |
dl |
1.4 |
*/ |
410 |
|
|
int runUpdates() throws InterruptedException { |
411 |
|
|
int n = 1 + (rng.next() & ((subpopSize << 1) - 1)); |
412 |
|
|
for (int i = 0; i < n; ++i) |
413 |
|
|
update(); |
414 |
|
|
return n; |
415 |
dl |
1.1 |
} |
416 |
|
|
|
417 |
dl |
1.2 |
/** |
418 |
jsr166 |
1.14 |
* Chooses a breeder, exchanges strand with another subpop, and |
419 |
|
|
* crosses them to create new chromosome to replace a chosen |
420 |
dl |
1.2 |
* dyer. |
421 |
|
|
*/ |
422 |
|
|
void update() throws InterruptedException { |
423 |
|
|
int b = chooseBreeder(); |
424 |
|
|
int d = chooseDyer(b); |
425 |
|
|
Chromosome breeder = chromosomes[b]; |
426 |
|
|
Chromosome child = chromosomes[d]; |
427 |
|
|
chooseStrand(breeder); |
428 |
|
|
strand = exchanger.exchange(strand); |
429 |
|
|
cross(breeder, child); |
430 |
|
|
fixOrder(child, d); |
431 |
|
|
} |
432 |
|
|
|
433 |
|
|
/** |
434 |
jsr166 |
1.14 |
* Chooses a breeder, with exponentially decreasing probability |
435 |
dl |
1.2 |
* starting at best. |
436 |
|
|
* @return index of selected breeder |
437 |
|
|
*/ |
438 |
|
|
int chooseBreeder() { |
439 |
dl |
1.4 |
int mask = (subpopSize >>> BREEDER_DECAY) - 1; |
440 |
dl |
1.2 |
int b = 0; |
441 |
|
|
while ((rng.next() & mask) != mask) { |
442 |
dl |
1.4 |
if (++b >= subpopSize) |
443 |
dl |
1.2 |
b = 0; |
444 |
|
|
} |
445 |
|
|
return b; |
446 |
|
|
} |
447 |
|
|
|
448 |
|
|
/** |
449 |
jsr166 |
1.14 |
* Chooses a chromosome that will be replaced, with |
450 |
jsr166 |
1.5 |
* exponentially decreasing probability starting at |
451 |
jsr166 |
1.14 |
* worst, ignoring the excluded index. |
452 |
dl |
1.2 |
* @param exclude index to ignore; use -1 to not exclude any |
453 |
|
|
* @return index of selected dyer |
454 |
|
|
*/ |
455 |
|
|
int chooseDyer(int exclude) { |
456 |
dl |
1.4 |
int mask = (subpopSize >>> DYER_DECAY) - 1; |
457 |
|
|
int d = subpopSize - 1; |
458 |
dl |
1.2 |
while (d == exclude || (rng.next() & mask) != mask) { |
459 |
|
|
if (--d < 0) |
460 |
dl |
1.4 |
d = subpopSize - 1; |
461 |
dl |
1.2 |
} |
462 |
|
|
return d; |
463 |
|
|
} |
464 |
|
|
|
465 |
jsr166 |
1.6 |
/** |
466 |
dl |
1.2 |
* Select a random strand of b's. |
467 |
|
|
* @param breeder the breeder |
468 |
|
|
*/ |
469 |
|
|
void chooseStrand(Chromosome breeder) { |
470 |
|
|
int[] bs = breeder.alleles; |
471 |
|
|
int length = bs.length; |
472 |
|
|
int strandLength = MIN_STRAND_LENGTH; |
473 |
|
|
while (strandLength < length && |
474 |
|
|
(rng.next() & RANDOM_STRAND_MASK) != RANDOM_STRAND_MASK) |
475 |
|
|
strandLength++; |
476 |
|
|
strand.strandLength = strandLength; |
477 |
|
|
int[] ss = strand.alleles; |
478 |
|
|
int k = (rng.next() & 0x7FFFFFFF) % length; |
479 |
|
|
for (int i = 0; i < strandLength; ++i) { |
480 |
|
|
ss[i] = bs[k]; |
481 |
|
|
if (++k >= length) k = 0; |
482 |
|
|
} |
483 |
|
|
} |
484 |
|
|
|
485 |
|
|
/** |
486 |
jsr166 |
1.14 |
* Copies current strand to start of c's, and then appends all |
487 |
dl |
1.2 |
* remaining b's that aren't in the strand. |
488 |
|
|
* @param breeder the breeder |
489 |
|
|
* @param child the child |
490 |
|
|
*/ |
491 |
|
|
void cross(Chromosome breeder, Chromosome child) { |
492 |
|
|
for (int k = 0; k < inTour.length; ++k) // clear bitset |
493 |
|
|
inTour[k] = 0; |
494 |
|
|
|
495 |
|
|
// Copy current strand to c |
496 |
|
|
int[] cs = child.alleles; |
497 |
|
|
int ssize = strand.strandLength; |
498 |
|
|
int[] ss = strand.alleles; |
499 |
|
|
int i; |
500 |
|
|
for (i = 0; i < ssize; ++i) { |
501 |
|
|
int x = ss[i]; |
502 |
|
|
cs[i] = x; |
503 |
|
|
inTour[x >>> 5] |= 1 << (x & 31); // record in bit set |
504 |
|
|
} |
505 |
|
|
|
506 |
|
|
// Find index of matching origin in b |
507 |
|
|
int first = cs[0]; |
508 |
|
|
int j = 0; |
509 |
|
|
int[] bs = breeder.alleles; |
510 |
jsr166 |
1.6 |
while (bs[j] != first) |
511 |
dl |
1.2 |
++j; |
512 |
|
|
|
513 |
|
|
// Append remaining b's that aren't already in tour |
514 |
|
|
while (i < cs.length) { |
515 |
|
|
if (++j >= bs.length) j = 0; |
516 |
|
|
int x = bs[j]; |
517 |
|
|
if ((inTour[x >>> 5] & (1 << (x & 31))) == 0) |
518 |
|
|
cs[i++] = x; |
519 |
jsr166 |
1.6 |
} |
520 |
dl |
1.1 |
|
521 |
|
|
} |
522 |
|
|
|
523 |
dl |
1.2 |
/** |
524 |
jsr166 |
1.14 |
* Fixes the sort order of a changed Chromosome c at position k. |
525 |
dl |
1.2 |
* @param c the chromosome |
526 |
jsr166 |
1.6 |
* @param k the index |
527 |
dl |
1.2 |
*/ |
528 |
|
|
void fixOrder(Chromosome c, int k) { |
529 |
|
|
Chromosome[] cs = chromosomes; |
530 |
dl |
1.3 |
int oldFitness = c.fitness; |
531 |
dl |
1.2 |
c.recalcFitness(); |
532 |
dl |
1.3 |
int newFitness = c.fitness; |
533 |
dl |
1.2 |
if (newFitness < oldFitness) { |
534 |
|
|
int j = k; |
535 |
|
|
int p = j - 1; |
536 |
|
|
while (p >= 0 && cs[p].fitness > newFitness) { |
537 |
|
|
cs[j] = cs[p]; |
538 |
|
|
j = p--; |
539 |
dl |
1.1 |
} |
540 |
dl |
1.2 |
cs[j] = c; |
541 |
|
|
} else if (newFitness > oldFitness) { |
542 |
|
|
int j = k; |
543 |
|
|
int n = j + 1; |
544 |
|
|
while (n < cs.length && cs[n].fitness < newFitness) { |
545 |
|
|
cs[j] = cs[n]; |
546 |
|
|
j = n++; |
547 |
dl |
1.1 |
} |
548 |
dl |
1.2 |
cs[j] = c; |
549 |
dl |
1.1 |
} |
550 |
|
|
} |
551 |
|
|
} |
552 |
|
|
|
553 |
dl |
1.2 |
/** |
554 |
|
|
* A Chromosome is a candidate TSP tour. |
555 |
|
|
*/ |
556 |
|
|
static final class Chromosome implements Comparable { |
557 |
|
|
/** Index of cities in tour order */ |
558 |
|
|
final int[] alleles; |
559 |
|
|
/** Total tour length */ |
560 |
dl |
1.3 |
int fitness; |
561 |
dl |
1.2 |
|
562 |
jsr166 |
1.6 |
/** |
563 |
jsr166 |
1.14 |
* Initializes to random tour. |
564 |
dl |
1.2 |
*/ |
565 |
|
|
Chromosome(int length, RNG random) { |
566 |
dl |
1.1 |
alleles = new int[length]; |
567 |
|
|
for (int i = 0; i < length; i++) |
568 |
|
|
alleles[i] = i; |
569 |
|
|
for (int i = length - 1; i > 0; i--) { |
570 |
dl |
1.2 |
int idx = (random.next() & 0x7FFFFFFF) % alleles.length; |
571 |
dl |
1.1 |
int tmp = alleles[i]; |
572 |
|
|
alleles[i] = alleles[idx]; |
573 |
|
|
alleles[idx] = tmp; |
574 |
|
|
} |
575 |
|
|
recalcFitness(); |
576 |
|
|
} |
577 |
dl |
1.2 |
|
578 |
|
|
public int compareTo(Object x) { // to enable sorting |
579 |
jsr166 |
1.9 |
int xf = ((Chromosome) x).fitness; |
580 |
dl |
1.3 |
int f = fitness; |
581 |
jsr166 |
1.8 |
return ((f == xf) ? 0 :((f < xf) ? -1 : 1)); |
582 |
dl |
1.1 |
} |
583 |
dl |
1.2 |
|
584 |
dl |
1.1 |
void recalcFitness() { |
585 |
dl |
1.2 |
int[] a = alleles; |
586 |
|
|
int len = a.length; |
587 |
|
|
int p = a[0]; |
588 |
dl |
1.3 |
long f = cities.distanceBetween(a[len-1], p); |
589 |
dl |
1.2 |
for (int i = 1; i < len; i++) { |
590 |
|
|
int n = a[i]; |
591 |
|
|
f += cities.distanceBetween(p, n); |
592 |
|
|
p = n; |
593 |
|
|
} |
594 |
jsr166 |
1.10 |
fitness = (int) (f / len); |
595 |
dl |
1.3 |
} |
596 |
|
|
|
597 |
dl |
1.4 |
/** |
598 |
jsr166 |
1.14 |
* Returns tour length for points scaled in [0, 1). |
599 |
dl |
1.4 |
*/ |
600 |
dl |
1.3 |
double unitTourLength() { |
601 |
|
|
int[] a = alleles; |
602 |
|
|
int len = a.length; |
603 |
|
|
int p = a[0]; |
604 |
|
|
double f = cities.unitDistanceBetween(a[len-1], p); |
605 |
|
|
for (int i = 1; i < len; i++) { |
606 |
|
|
int n = a[i]; |
607 |
|
|
f += cities.unitDistanceBetween(p, n); |
608 |
|
|
p = n; |
609 |
|
|
} |
610 |
|
|
return f; |
611 |
dl |
1.2 |
} |
612 |
|
|
|
613 |
dl |
1.4 |
/** |
614 |
jsr166 |
1.14 |
* Checks that this tour visits each city. |
615 |
dl |
1.4 |
*/ |
616 |
jsr166 |
1.6 |
void validate() { |
617 |
dl |
1.2 |
int len = alleles.length; |
618 |
|
|
boolean[] used = new boolean[len]; |
619 |
jsr166 |
1.6 |
for (int i = 0; i < len; ++i) |
620 |
dl |
1.2 |
used[alleles[i]] = true; |
621 |
jsr166 |
1.6 |
for (int i = 0; i < len; ++i) |
622 |
dl |
1.2 |
if (!used[i]) |
623 |
|
|
throw new Error("Bad tour"); |
624 |
dl |
1.1 |
} |
625 |
dl |
1.2 |
|
626 |
|
|
} |
627 |
|
|
|
628 |
|
|
/** |
629 |
dl |
1.4 |
* A Strand is a random sub-sequence of a Chromosome. Each subpop |
630 |
dl |
1.2 |
* creates only one strand, and then trades it with others, |
631 |
|
|
* refilling it on each iteration. |
632 |
|
|
*/ |
633 |
|
|
static final class Strand { |
634 |
|
|
final int[] alleles; |
635 |
|
|
int strandLength; |
636 |
|
|
Strand(int length) { alleles = new int[length]; } |
637 |
dl |
1.1 |
} |
638 |
dl |
1.2 |
|
639 |
dl |
1.1 |
/** |
640 |
jsr166 |
1.6 |
* A collection of (x,y) points that represent cities. |
641 |
dl |
1.1 |
*/ |
642 |
|
|
static final class CitySet { |
643 |
dl |
1.2 |
|
644 |
dl |
1.1 |
final int length; |
645 |
dl |
1.2 |
final int[] xPts; |
646 |
|
|
final int[] yPts; |
647 |
dl |
1.3 |
final int[][] distances; |
648 |
dl |
1.2 |
|
649 |
|
|
CitySet(int n) { |
650 |
dl |
1.1 |
this.length = n; |
651 |
dl |
1.2 |
this.xPts = new int[n]; |
652 |
|
|
this.yPts = new int[n]; |
653 |
dl |
1.3 |
this.distances = new int[n][n]; |
654 |
dl |
1.2 |
|
655 |
|
|
RNG random = new RNG(); |
656 |
dl |
1.1 |
for (int i = 0; i < n; i++) { |
657 |
dl |
1.2 |
xPts[i] = (random.next() & 0x7FFFFFFF); |
658 |
|
|
yPts[i] = (random.next() & 0x7FFFFFFF); |
659 |
dl |
1.1 |
} |
660 |
dl |
1.2 |
|
661 |
dl |
1.1 |
for (int i = 0; i < n; i++) { |
662 |
|
|
for (int j = 0; j < n; j++) { |
663 |
jsr166 |
1.10 |
double dx = (double) xPts[i] - (double) xPts[j]; |
664 |
|
|
double dy = (double) yPts[i] - (double) yPts[j]; |
665 |
dl |
1.3 |
double dd = Math.hypot(dx, dy) / 2.0; |
666 |
|
|
long ld = Math.round(dd); |
667 |
jsr166 |
1.8 |
distances[i][j] = (ld >= Integer.MAX_VALUE) ? |
668 |
jsr166 |
1.10 |
Integer.MAX_VALUE : (int) ld; |
669 |
dl |
1.1 |
} |
670 |
|
|
} |
671 |
|
|
} |
672 |
dl |
1.2 |
|
673 |
dl |
1.3 |
/** |
674 |
jsr166 |
1.11 |
* Returns the cached distance between a pair of cities. |
675 |
dl |
1.3 |
*/ |
676 |
|
|
int distanceBetween(int i, int j) { |
677 |
dl |
1.2 |
return distances[i][j]; |
678 |
|
|
} |
679 |
dl |
1.3 |
|
680 |
|
|
// Scale ints to doubles in [0,1) |
681 |
jsr166 |
1.10 |
static final double PSCALE = (double) 0x80000000L; |
682 |
dl |
1.3 |
|
683 |
|
|
/** |
684 |
jsr166 |
1.11 |
* Returns distance for points scaled in [0,1). This simplifies |
685 |
dl |
1.3 |
* checking results. The expected optimal TSP for random |
686 |
|
|
* points is believed to be around 0.76 * sqrt(N). For papers |
687 |
|
|
* discussing this, see |
688 |
|
|
* http://www.densis.fee.unicamp.br/~moscato/TSPBIB_home.html |
689 |
|
|
*/ |
690 |
|
|
double unitDistanceBetween(int i, int j) { |
691 |
jsr166 |
1.10 |
double dx = ((double) xPts[i] - (double) xPts[j]) / PSCALE; |
692 |
|
|
double dy = ((double) yPts[i] - (double) yPts[j]) / PSCALE; |
693 |
dl |
1.3 |
return Math.hypot(dx, dy); |
694 |
|
|
} |
695 |
jsr166 |
1.6 |
|
696 |
dl |
1.2 |
} |
697 |
|
|
|
698 |
|
|
/** |
699 |
|
|
* Cheap XorShift random number generator |
700 |
|
|
*/ |
701 |
|
|
static final class RNG { |
702 |
|
|
/** Seed generator for XorShift RNGs */ |
703 |
|
|
static final Random seedGenerator = new Random(); |
704 |
|
|
|
705 |
|
|
int seed; |
706 |
|
|
RNG(int seed) { this.seed = seed; } |
707 |
jsr166 |
1.13 |
RNG() { this.seed = seedGenerator.nextInt() | 1; } |
708 |
dl |
1.2 |
|
709 |
|
|
int next() { |
710 |
|
|
int x = seed; |
711 |
|
|
x ^= x << 6; |
712 |
|
|
x ^= x >>> 21; |
713 |
|
|
x ^= x << 7; |
714 |
|
|
seed = x; |
715 |
|
|
return x; |
716 |
dl |
1.1 |
} |
717 |
|
|
} |
718 |
|
|
|
719 |
dl |
1.2 |
static final class ProgressMonitor extends Thread { |
720 |
dl |
1.1 |
final Population pop; |
721 |
dl |
1.2 |
ProgressMonitor(Population p) { pop = p; } |
722 |
dl |
1.1 |
public void run() { |
723 |
dl |
1.2 |
double time = 0; |
724 |
dl |
1.1 |
try { |
725 |
dl |
1.2 |
while (!Thread.interrupted()) { |
726 |
|
|
sleep(SNAPSHOT_RATE); |
727 |
|
|
time += SNAPSHOT_RATE; |
728 |
|
|
pop.printSnapshot(time / 1000.0); |
729 |
dl |
1.1 |
} |
730 |
dl |
1.2 |
} catch (InterruptedException ie) {} |
731 |
dl |
1.1 |
} |
732 |
|
|
} |
733 |
|
|
} |