Wednesday, June 7, 2017

Lin-Kernighan algorithm basics – part 2

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