First of all, Lin-Kernighan algorithm contains specific, justified exceptions to the four main rules. Rule number 2 requires that for each step we should be able to immediately stop adding further steps and obtain a valid tour. Naturally, this is not to be fulfilled for first step. But at the second step sequence 12-34 does not conform this rule: it is disconnecting move, producing two disjoined cycles. On the other hand, it would not be desirable to not allow this sequence, since it is needed to obtain two of all four pure 3-opt moves. Therefore original LK algorithm uses the principle of feasibility of tour starting from the third exchange, and not for the first two exchanges (2-opt level). Some variants of LK algorithm go even further and allow disconnecting moves at level of 3-opt or 4-opt moves, to examine more valid sequential 4-opt and 5-opt moves in next steps.
An outline of this part of original LK algorithm can be implemented as follows (we split code into chunks):
To make the code simple and clear we use global variables for tour and neighbor lists representation:
var
tour: Tour_Array # current tour
tourLen: Length # current length of tour
position: City_Position_In_Tour
neighbor: Neighbor_Matrix
numberOfNeigbors: int
DontLook: DLB_Array
These variables are used explicitly only in few low level procs, to keep the most of the code independent on this specific representation. Note that except these, all other procs use city numbers only, not their positions.
proc t_pred(city: City_Number): City_Number {.inline.} =
## returns tour predecessor for given city
result = tour[(N + position[city] - 1) mod N]
proc t_succ(city: City_Number): City_Number {.inline.} =
## returns tour successor for given city
result = tour[(position[city] + 1) mod N]
For the same reason instead of writing:
for neighbor_number in 0 .. numberOfNeigbors-1:
c3 = neighbor[c2][neighbor_number]
we will use more abstract:
for c3 in neighbors(c2):
which in Nim language can be provided by iterator:
iterator neighbors(city: City_Number): City_Number =
var i = 0
while i < numberOfNeigbors:
yield neighbor[city][i]
inc(i)
proc LK_1Move(c1: City_Number): bool =
const
level = 0
var
improved: bool
c2: City_Number
c1_pred, c1_succ: City_Number
G1a: Length_Gain
improved = false
c1_succ = t_succ(c1)
c1_pred = t_pred(c1)
# try moves with breaking link between c1 and one of its tour
# tour neigbors; if failed then try c1 with the other tour neighbor
block find_improving_move:
for c2 in [c1_succ, c1_pred]:
# tests:
# c2!=c1 by construction (c2 is a tour neighbor of c1)
G1a = distance(c1, c2)
improved = LK_2Move(c1, c2, G1a)
if improved:
break find_improving_move
#end_for loop
#end_block find_improving_move
result = improved
(As may be noticed in above code, backtracking is limited: the alternative for c2 is examined only when no improving sequence starting with c1 and current c2 has been found.)
proc LK_2Move(c1, c2: City_Number;
G1a: Length_Gain): bool =
const
level = 1
var
improved: bool
c3, c4: City_Number
c2_pred, c2_succ: City_Number
c3_pred, c3_succ: City_Number
fwd: bool
G1: Length_Gain
G2a, gainFromCloseUp: Length_Gain
tried_c3: int = 0
tourOrder: int
moveType: int
improved = false
fwd = (c2 == t_succ(c1))
c2_succ = t_succ(c2)
c2_pred = t_pred(c2)
block find_promising_moves:
for c3 in neighbors(c2):
# after 2-opt move new tour would contain direct link
# between cities c2 and c3, so we look for c3 among
# cities that are close to city c2
# tests:
# when c3 is one of tour neighbors of c2,
# then the link (c2,c3) already exists in tour
# and we cannot *add* it to the tour
if (c3 == c2_succ) or (c3 == c2_pred):
continue
G1 = G1a - distance(c2, c3)
if G1 <= 0: # c3 is too far from c2 -- no more promising moves
break
# if G1 > 0:
# limit breadth to speed up searching
tried_c3 = tried_c3 + 1
if tried_c3 > Max_Breadth_1:
break find_promising_moves
c3_succ = t_succ(c3)
c3_pred = t_pred(c3)
for c4 in [c3_pred, c3_succ]:
# testing available variants
if fwd and (c4 == c3_succ) or
not fwd and (c4 == c3_pred):
# disconnecting move
tourOrder = TO_1234
moveType = move_type_0 # not a valid move
else:
tourOrder = TO_1243
moveType = move_type_2 # 2-opt move
G2a = G1 + distance(c3, c4)
if moveType != move_type_0: # connecting move
gainFromCloseUp = G2a - distance(c4, c1)
if gainFromCloseUp > 0:
# improving move found
improved = true
Make_2opt_Move(c1, c2, c3, c4)
tourLen = tourLen - gainFromCloseUp
Set_DLB_off(DontLook, [c1, c2, c3, c4])
break find_promising_moves
if LK_3Move(c1, c2, c3, c4,
G2a, tourOrder):
improved = true
break find_promising_moveses
#end_loop for c4
#end_loop for neighbor_number
#end_block find_promising_moves
result = improved
Note that backtracking in original LK is always limited. The alternative for c4 is examined only when no improving sequence starting with given c1, c2, c3 and current c4 has been found. Similarly, alternative candidate for c3 is examined only when no improving sequence starting with given c1, c2 and current c3 has been found.
To speed up searching without considerable loss of quality the original LK limits searching for c3 and c5 to first 5 candidates. This can be implemented by use of MaxBreadth(level) function or by some constants (program parameters):
# Maximum number of candidates to examine for endpoint
# of link added at given level of search for move.
# 1 means only one candidate should be considered
# 0 means no candidate, constructing a sequence stops at this level
# In original LK algorithm breadth is 5 for levels 1 and 2,
# and 1 for deeper levels. (They used GE-635, with speed <1 MIPS).
# Make some tests and adjust the values to your preferences.
const
Max_Breadth_1 = 5 # for level 1
Max_Breadth_2 = 5 # for level 2
Max_Breadth_3 = 3 # for level 3
Max_Breadth_4 = 3 # for level 4
Since candidate lists for c3, c5... are anyway limited and additionally the search is terminated when partial sum of gains is not positive, one may not use MaxBreadth(level), in hope of obtaining better results at cost of increased runtime.
No comments:
Post a Comment