📄 optimizenodesnearapoint.java
字号:
int slotAfters[],
TravellerChromosome tc
)
{
TravellerWorld world = tc.getWorld();
double increment = 0.0D;
int howManySlots = slotBeginnings.length;
int howManyCodons = permutation.length;
int placeInPermutation = 0;
for (int i = 0; i < howManySlots; i++)
{
if ( slotCounts[i] == 0 )
{
increment +=
world.getDistance
(
tc.getCity(slotBefores[i]),
tc.getCity(slotAfters[i])
);
}
else
{
increment +=
world.getDistance
(
tc.getCity(slotBefores[i]),
cityList[permutation[placeInPermutation].intValue()]
);
for ( int j = 1; j < slotCounts[i]; j++ )
{
increment +=
world.getDistance
(
cityList[permutation[placeInPermutation + j - 1].intValue()],
cityList[permutation[placeInPermutation + j].intValue()]
);
}
increment +=
world.getDistance
(
cityList
[
permutation[placeInPermutation + slotCounts[i] - 1].intValue()
],
tc.getCity(slotAfters[i])
);
placeInPermutation += slotCounts[i];
}
}
return increment;
}
private int[][] findSlots( int cityList[], TravellerChromosome tc )
{
int genomeLength = tc.getNumCities();
int slotBefores[] = new int[cityList.length];
int slotBeginnings[] = new int[cityList.length];
int slotEndings[] = new int[cityList.length];
int slotAfters[] = new int[cityList.length];
for ( int i = 0; i < cityList.length; i++ )
{
slotBefores[i] = -1;
slotBeginnings[i] = -1;
slotEndings[i] = -1;
slotAfters[i] = -1;
}
int howManySlots = 0;
/*
** We take advantage here of the design that tc.getCity() is working
** in modular coordinates, so our arithmetic here can be sloppy about
** array boundaries.
*/
/*
** Go forward looking for the end of a slot.
*/
for ( int i = 0; i < genomeLength; i++ )
{
if
(
( inList( tc.getCity( i ), cityList ) )
&&
(! inList( tc.getCity( i + 1 ), cityList ) )
)
{
slotEndings[howManySlots] = i;
slotAfters[howManySlots] = i + 1;
/*
** Go backward from there looking for the beginning of the same slot.
*/
for (int j = 0; j < genomeLength; j++)
{
if
(
( inList( tc.getCity( i - j ), cityList ) )
&&
(! inList( tc.getCity( i - j - 1 ), cityList ) )
)
{
slotBeginnings[howManySlots] =
( i - j + genomeLength ) % genomeLength;
slotBefores[howManySlots] =
( i - j - 1 + genomeLength ) % genomeLength;
howManySlots++;
break;
}
}
}
}
/*
** Produce arrays sized for the numbers actually found, so that the
** array lengths accurately define the count of their valid contents.
*/
int slotPredecessors[] = new int[howManySlots];
int slotStarts[] = new int[howManySlots];
int slotStops[] = new int[howManySlots];
int slotSuccessors[] = new int[howManySlots];
for ( int i = 0; i < howManySlots; i++ )
{
slotPredecessors[i] = slotBefores[i];
slotStarts[i] = slotBeginnings[i];
slotStops[i] = slotEndings[i];
slotSuccessors[i] = slotAfters[i];
}
int slotList[][] =
{
slotPredecessors,
slotStarts,
slotStops,
slotSuccessors,
};
return slotList;
}
private boolean inList( int c, int list[] )
{
for (int i = 0; i < list.length; i++)
{
if (c == list[i]) { return true; }
}
return false;
}
private int listIndex( int c, int list[] )
{
for (int i = 0; i < list.length; i++)
{
if (c == list[i]) { return i; }
}
return -1;
}
private int [] pickCities( TravellerWorld world, int permuteSize )
{
MersenneTwister mt = MersenneTwister.getTwister();
/*
** Pick a location in the working canvas playfield area from which to
** reach out for the nearest permuteSize cities.
*/
double x =
mt.nextDouble( 0.0D, TravellerCanvas.WORKING_DIMENSIONS.getWidth() );
double y =
mt.nextDouble( 0.0D, TravellerCanvas.WORKING_DIMENSIONS.getHeight() );
if (this.DB) { System.out.println("pickedCities at: " + x + "," + y ); }
int cities[] = new int[permuteSize];
double distances[] = new double[permuteSize];
for ( int i = 0; i < permuteSize; i++ )
{
cities[i] = -1;
distances[i] = Double.MAX_VALUE;
}
int genomeLength = world.getNumberOfCities();
if (this.DB)
{
System.out.println( "pickCities, cities: " + Debugging.dump(cities) );
System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
}
for ( int i = 0; i < genomeLength; i++ )
{
double cityExactLocation[] = world.getCityExactLocation(i);
double cx = cityExactLocation[TravellerWorld.CITY_X];
double cy = cityExactLocation[TravellerWorld.CITY_Y];
double distance =
Math.sqrt( ( ( cx - x ) * ( cx - x ) ) + ( ( cy - y ) * ( cy - y ) ) );
if (this.DB) { System.out.println( "pickCities OK to inner loop" ); }
double dtemp;
int ctemp;
int itemp = i;
for ( int j = 0 ; j < permuteSize; j++ )
{
if ( distance < distances[j] )
{
dtemp = distances[j];
ctemp = cities[j];
distances[j] = distance;
cities[j] = itemp;
distance = dtemp;
itemp = ctemp;
}
}
if (this.DB)
{
System.out.println( "pickCities, cities,i: " + Debugging.dump(cities) + i );
System.out.println( "pickCities, distances: " + Debugging.dump(distances) );
}
}
return cities;
}
private void dive(int slot[], int depth, Vector v)
{
depth++;
/*
** Since we pass arrays by reference, and will be modifying the array at
** each deeper level of recursion but wanting it intact for further work
** when we return, we must create a new copy at each level for the
** effort there.
*/
int recurse[] = new int[slot.length];
for (int i = 0; i < slot.length; i++) { recurse[i] = slot[i]; }
if ( depth < slot.length)
{
while (recurse[depth - 1] != 0)
{
recurse[depth - 1]--;
recurse[depth]++;
int saveAs[] = new int[slot.length];
/*
** We need to make a new array copy to save into the returned vector,
** we will clobber recurse when we next come up for air if we do more
** work on it in this loop, and again, v is getting a reference, so it
** needs to be a reference to a separate, never modified copy.
*/
for (int i = 0; i < slot.length; i++)
{
saveAs[i] = recurse[i];
}
v.add(saveAs);
if ( ( depth + 1 ) < slot.length ) { dive( recurse, depth, v ); }
}
}
}
private Vector slotCounts(int codons, int slots)
{
Vector v = new Vector(10, 10);
int slot[] = new int[slots];
for (int i = 0; i < slots; i++)
{
slot[i] = 0;
}
slot[0] = codons;
int depth = 0;
/*
** We can safely add slot to v, slot is never itself modified in dive()
*/
v.add(slot);
/*
** We pass v down, and whenever a new slot fill pattern is found, it is
** appended to v.
*/
dive( slot, depth, v);
return v;
}
}
/*
[How this algorithm works, from my original "to do" list writeup.]
Consider dropping a random point on the map, computing distances to all cities,
sorting, selecting the M closest, removing them from the genome while keeping
track of the S <= M slots they leave behind, then permuting all combinations of
the removed genomes and reinserting them in permuted order in all possible
subsettings into the voids left behind:
For example, given genome:
a b c d e f g h i j k l m
remove, say, d e h j as the closest to the given point (u,v), leaving
S = three slots "1", "2", "3":
a b c 1 f g 2 i 3 k l m
Permutations: Subsets: Child genomes:
d e h j () () dehj a b c f g i d e h j k l m
() d ehj a b c f g d i e h j k l m
() de hj a b c f g d e i h j k l m
() deh j a b c f g d e h i j k l m
() dehj () a b c f g d e h j i k l m
d () ehj a b c d f g i e h j k l m
d e hj a b c d f g e i h j k l m
d eh j a b c d f g e h i j k l m
d ehj () a b c d f g e h j i k l m
de () hj a b c d e f g i h j k l m
de h j a b c d e f g h i j k l m (original!)
de hj () a b c d e f g h j i k l m
deh () j a b c d e h f g i j k l m
deh j () a b c d e h f g j i k l m
dehj () () a b c d e h j f g i k l m
and similarly for the permutations below...
d e j h
d h e j
d h j e
d j e h
d j h e
e d h j
e d j h
e h d j
e h j d
e j d h
e j h d
h d e j
h d j e
h e d j
h e j d
h j d e
h j e d
j d e h
j d h e
j e d h
j e h d
j h d e
j h e d
The number of permutations is of course M! The number of subsets of M
items subsetted in a frozen order into S containers is more complicated
to compute, and turns out to be most easily read from Pascal's triangle:
..1 ... ... ...
..1 .12 ... ... ...
..1 .11 .78 ... ...
..1 .10 .66 364 ... ...
..1 ..9 .55 286 1365 ...
..1 ..8 .45 220 1001 4368 ...
..1 ..7 .36 165 715 3003 12376
..1 ..6 .28 120 495 2002 8008 31824
..1 ..5 .21 .84 330 1287 5005 19448
..1 ..4 .15 .56 210 792 3003 11440 43758
..1 ..3 .10 .35 126 462 1716 6435 24310
..1 ..2 ..6 .20 .70 252 924 3432 12870 48620
..1 ..3 .10 .35 126 462 1716 6435 24310
..1 ..4 .15 .56 210 792 3003 11440 43758
..1 ..5 .21 .84 330 1287 5005 19448
..1 ..6 .28 120 495 2002 8008 31824
..1 ..7 .36 165 715 3003 12376
/ ..1 ..8 .45 220 1001 4368 ...
/ ..1 ..9 .55 286 1365 ...
Example: / ..1 .10 .66 364 ... ...
The sixth diagonal, used for M=5, ..1 .11 .78 ... ...
has values 1, 6, 21, 56, 126, 252 ..1 .12 ... ... ...
for S = 1 2 3 4 5 6 slots' ..1 ... ... ...
total ways to subdivide those M items without
regard for their identity/value into S slots.
Where the M+1st diagonal contains, in order, the number of subsets of M for
S = 1 , 2, 3, 4, ... slots. Obviously, remembering that these subsettings
must be multiplied by the number of permutations of M to get the total
number of new genomes to be generated and for which fitnesses must be
calculated, the number of cities allowed must be severely limited:
Number of child genomes generated by permuting M cities and then listing each
permutation in all possible same-ordered subsets partitioned among S <= M
slots, as illustrated above.
Cities
\ M 1 2 3 4 5 6 7 8 9
S \ - - -- --- ----- ------ ------- --------- -----------
1 | 1 2 6 24 120 720 5040 40320 362880
S 2 | 6 24 120 720 5040 40320 362880 3628800
l 3 | 60 360 2520 18060 181440 1814400 19958400
o 4 | 840 6720 60480 604800 6652800 79833600
t 5 | 15120 151200 1663200 19958400 259459200
s 6 | 322640 3991680 51891840 726485760
7 | 8648640 121080960 1816214400
8 | 259459200 4141347200
9 | 8821612800
While geometry might suggest that usually a less than maximal number
of slots will occur, the worst cases are such that a producer / consumer,
rather than list passing, technology must be incorporated before an M
larger than 4 can reasonably be allowed. Passing a vector of even 2520
chromosomes all at once, for five cities that create three slots, an
easily realized situation, would likely kill the Java engine. Anyway, a
producer / consumer technology recommends itself for lots of other
reasons, particularly where croppers are concerned, and the thing being
produced is empty population slots to be refilled.
Alternately, of course, emitting the single best result would suffice.
[No queuing was implemented for this heuristic, the latter suggestion
prevailed by its simplicity to implement. By adding adaptive permutation
limits, the ugly worst cases are mostly avoided by getting the points
fairly well locally organized along the tour before using large numbers
of permutees, so that fewer slots are produced in the general case than
would happen at the beginning of a purely randomly seeded problem.]
*/
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -