Tuesday, August 29, 2017

LK – subsequent 3-opt move

Subsequent move in Lin-Kernighan optimization does not need to be 2-opt as in original algorithm. We can use 3-opt as well, or any other sequential type of move:

proc LK_Subsequent3Move(c1, c2: City_Number;
                        G1a: var Length_Gain;
                        cLast: var City_Number): bool =
  # cLast is set to last city in sequential move when promising move
  # has been found and applied
  var
    improved: bool
    c3, c4, c5, c6: City_Number
    c2_pred, c2_succ: City_Number
    c3_pred, c3_succ: City_Number
    c4_pred, c4_succ: City_Number
    c5_pred, c5_succ: City_Number
    fwd: bool
    c4_A, c4_B:  City_Number
    G1, Ga, G2a, G2, G3a, gainFromCloseUp: Length_Gain
    tried_c3, tried_c5: int
    tourOrder2, tourOrder3: int
    c3_BG, c4_BG, c5_BG, c6_BG: City_Number
    Ga_BG: Length_Gain
    tourOrder_BG: int

  improved = false
  fwd = (c2 == t_succ(c1))
  c2_succ = t_succ(c2)
  c2_pred = t_pred(c2)

  block find_promising_moves:
    tried_c3 = 0
    Ga_BG = 0
    for c3 in neighbors(c2):
      if tried_c3 >= Max_Breadth_S:
        break
      if (c3 == c2_succ) or (c3 == c2_pred):
        continue
      if isLinkAdded(c2, c3):
        continue
      G1 = G1a - distance(c2, c3)
      if G1 <= 0:
        break
      c3_succ = t_succ(c3)
      c3_pred = t_pred(c3)
      if fwd:
        c4_A = t_pred(c3)
        c4_B = t_succ(c3)
      else:
        c4_A = t_succ(c3)
        c4_B = t_pred(c3)
      for c4 in [c4_A, c4_B]:
        if isLinkAdded(c4, c1):
          continue
        tried_c3 = tried_c3 + 1
        G2a = G1 + distance(c3, c4)
        if (c4 == c4_B):
          tourOrder2 = TO_1234
        else:
          tourOrder2 = TO_1243
          gainFromCloseUp = G2a - distance(c4, c1)
          if gainFromCloseUp > 0:  # improving move found
            improved = true
            Make_2opt_Move(c1, c2, c3, c4)
            tourLen = tourLen - gainFromCloseUp
            G1a = G2a
            cLast = c4
            # don't look bits for c1, c2 should be set at previous level
            Set_DLB_off(DontLook, [c3, c4])
            break find_promising_moves
        # 3-opt
        c4_succ = t_succ(c4)
        c4_pred = t_pred(c4)
        tried_c5 = 0
        for c5 in neighbors(c4):
          if tried_c5 >= Max_Breadth_S:
            break
          if (c5 == c4_succ) or (c5 == c4_pred):
            continue
          if isLinkAdded(c4, c5):
            continue
          G2 = G2a - distance(c4, c5)
          if G2  <= 0:
            break
          c5_succ = t_succ(c5)
          c5_pred = t_pred(c5)
          for c6 in [c5_succ, c5_pred]:
            if (c6 == c1):
              continue
            if isLinkAdded(c6, c1):
              continue
            tourOrder3 = TO_00
            case tourOrder2
            of TO_1234:
              if inOrder(c2, c5, c3, fwd):
                if inOrder(c2, c6, c5, fwd):
                  tourOrder3 = TO_126534
                else:
                  tourOrder3 = TO_125634
            of TO_1243:
              if inOrder(c2, c5, c4, fwd):
                if inOrder(c2, c6, c5, fwd):
                  continue
                else:
                  tourOrder3 = TO_125643
              else:
                if inOrder(c3, c6, c5, fwd):
                  tourOrder3 = TO_124365
            else:
              continue
            #end_case tourOrder2
            if tourOrder3 == TO_00:
              continue
            tried_c5 = tried_c5 + 1
            G3a = G2 + distance(c5, c6)
            gainFromCloseUp = G3a - distance(c6, c1)
            if gainFromCloseUp > 0:
              improved = true
              Make_3opt_Move(c1, c2, c3, c4, c5, c6, tourOrder3)
              tourLen = tourLen - gainFromCloseUp
              G1a = G3a
              cLast = c6
              Set_DLB_off(DontLook, [c3, c4, c5, c6])
              break find_promising_moves
            if G3a > Ga_BG:
              Ga_BG = G3a
              c3_BG  = c3
              c4_BG  = c4
              c5_BG  = c5
              c6_BG  = c6
              tourOrder_BG = tourOrder3
    #end loop for c3
  #end block find_promising_moves

  block make_best_3move:
    if improved:
      break make_best_3move
    if Ga_BG <= 0:
      break make_best_3move
    Make_3opt_Move(c1, c2,
                   c3_BG, c4_BG, c5_BG, c6_BG, tourOrder_BG)
    G1a = Ga_BG
    cLast = c6_BG
    AddtoLinksAdded(c3_BG, c4_BG)
    AddtoLinksAdded(c5_BG, c6_BG)
    Set_DLB_off(DontLook, [c3_BG, c4_BG, c5_BG, c6_BG])
  #end block make_best_3move

  result = improved

Beware

Note that while 2-opt move is just single exchange of two pairs of links, 3-opt move constists of two or three such exchanges. Therefore we should modify the way we count levels for subsequent moves (needed to restrict their number). Instead of incrementing local SubseqLvl variable inside LK_5Move or LK_scheme, we should make it a global variable and increment it while actually performing the basic tour transformation, that is: inside Exchange_Links.

Thursday, August 10, 2017

LK – alternative calling subsequent moves

Used with bigger values for breadths (eg. 24, 24, 24, 24, 24, Max_Breadth_K=3) gives similar results, but is up to two times faster than the code showed previously. Some people find this approach also simpler and more convincing.

type
  PromisingMove = object
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10: City_Number
    Ga: Length_Gain
    moveType: int
    tourOrder: int
const
  HalfListSize = 20
var
  promisingMoves: array[0..2*HalfListSize, PromisingMove]
  emptyListPos: int

proc ClearPromisingMoves() =
  for i in 0 .. len(promisingMoves)-1:
    promisingMoves[i].Ga = 0
  emptyListPos = 0

proc SortPromisingMoves() =
  sort(promisingMoves) do (x,y: PromisingMove) -> int:
       result = cmp(y.Ga, x.Ga)

proc AddToPromisingMoves(move: PromisingMove) =
  promisingMoves[emptyListPos] = move
  emptyListPos = emptyListPos + 1
  if emptyListPos > 2*HalfListSize:
    # sort list by gain, then treat worse half as not filled
    SortPromisingMoves()
    emptyListPos = HalfListSize + 1

proc GetAllPromisigMoves(): seq[PromisingMove] =
  var
    allMoves: seq[PromisingMove]
  allMoves = @[]  # empty list (sequence)
  SortPromisingMoves()
  for i in 0 .. min(emptyListPos, HalfListSize)-1:
    allMoves.add(promisingMoves[i])
  result = allMoves
proc LK_5Move(c1, c2, c3, c4, c5, c6, c7, c8: City_Number;
              G4a: Length_Gain;
              tourOrderPrev: int): bool =
  var
    ...
    move: PromisingMove
...    
  move.c1 = c1
  move.c2 = c2
  move.c3 = c3
  move.c4 = c4
  move.c5 = c5
  move.c6 = c6
  move.c7 = c7
  move.c8 = c8
...
  block find_promising_moves:
    ...
  #end_block find_promising_moves
    
  block evaluate_promising_moves:
    ...
      if moveType != move_type_0: # connecting move
        gainFromCloseUp = Ga - distance(c10, c1)
        if gainFromCloseUp > 0:
          # improving move found
          improved = true
          Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                         tourOrder)
          tourLen = tourLen - gainFromCloseUp
          Set_DLB_off(DontLook,
                      [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
          break evaluate_promising_moves
          
      when true: # not OPT_6_IMPLEMENTED
        move.c9  = c9 
        move.c10 = c10
        move.Ga  = Ga
        move.moveType  = moveType
        move.tourOrder = tourOrder
        AddToPromisingMoves(move)
    #end_loop for mve
  #end_block evaluate_promising_moves
  result = improved
proc LK_1SubsequentMoves():bool =
  var
    improved: bool
    promisingMovesList: seq[PromisingMove]
    breadth: int
    c1, c2, c3, c4, c5, c6, c7, c8, c9, c10:  City_Number
    Ga: Length_Gain
    tourOrder: int
    moveType: int
    searching: bool
    c2subseq, cLast:  City_Number

  improved = false
  block evaluate_promising_moves:
    # here we should try to use general subsequent move
    # after temporary applying 5-opt move
    promisingMovesList = GetAllPromisigMoves()
    breadth = min(len(promisingMovesList), Max_Breadth_K)  ## NOTE
    if breadth == 0:
      break evaluate_promising_moves

    Save_Tour()
    Save_DLB()
    for mve in 0 .. breadth-1:
      c1  = promisingMovesList[mve].c1
      c2  = promisingMovesList[mve].c2
      c3  = promisingMovesList[mve].c3
      c4  = promisingMovesList[mve].c4
      c5  = promisingMovesList[mve].c5
      c6  = promisingMovesList[mve].c6
      c7  = promisingMovesList[mve].c7
      c8  = promisingMovesList[mve].c8
      c9  = promisingMovesList[mve].c9
      c10 = promisingMovesList[mve].c10
      Ga  = promisingMovesList[mve].Ga
      #moveType = promisingMovesList[mve].moveType
      tourOrder = promisingMovesList[mve].tourOrder

      c2subseq = c10
      cLast = c10
      LinksAddedClear()
      AddtoLinksAdded(c2, c3)
      AddtoLinksAdded(c4, c5)
      AddtoLinksAdded(c6, c7)
      AddtoLinksAdded(c8, c9)
      Make_5opt_Move(c1, c2, c3, c4, c5, c6, c7, c8, c9, c10,
                     tourOrder)
      Set_DLB_off(DontLook,
                  [c1, c2, c3, c4, c5, c6, c7, c8, c9, c10])
      searching = true
      SubseqLvl = 0
      while searching:
        improved = LK_Subsequent3Move(c1, c2subseq, Ga, cLast)
        if improved:
          break evaluate_promising_moves
        else:
          if c2subseq == cLast: # end of promising moves
            Restore_Tour()
            Restore_DLB()
            searching = false
          else:
            c2subseq = cLast
        if SubseqLvl >= Max_Depth:
          searching = false
          Restore_Tour()
          Restore_DLB()
    #end_loop log mve
  #end_block evaluate_promising_moves
  result = improved
proc LK_scheme() =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number

  position = Create_Position_In_Tour(tour)
  Set_DLB_off(DontLook, tour)

  while not locallyOptimal:
    locallyOptimal = true
    for baseCity in 0 .. N-1:
      if isDLB_on(DontLook, baseCity):
        continue 

      ClearPromisingMoves()
      # first move:
      improved = LK_1Move(baseCity)
      # subsequent moves:
      if not improved:
        improved = LK_1SubsequentMoves()

      if improved:
        locallyOptimal = false
      else:
        Set_DLB_on(DontLook, baseCity)

    #end_loop for baseCity
  #end_while not locallyOptimal