TSP Basics: NL

Showing posts with label NL. Show all posts

Saturday, April 15, 2017

Stop search after encountering the successor

Less popular speed-up is using search cut after encountering a successor of given city when iterating on its neighbors. The idea is based on the observation that lead to 2-opt fixed radius search.

We consider neighbours of city X1 to find a good candidate for Y1, the first of endpoints of second link to remove. If we make a 2-opt move, then Y1 would be the new tour successor of X1, so it should not be in distance from X1 greater then is X2, the current successor. Otherwise, the new link would be longer than the current one. Since we consider neighbors of X1 in ascending order of their distance from this city, encountering X2 during search means that all subsequent neighbors would give longer links to X1.

...
  for neighbor_1 in 0 .. numberOfNeigbors-1:
    Y2 = neighbor[X1][neighbor_1]
    j  = (position[Y2] + N - 1) mod N
    Y1 = tour[j]

    if (Y1 == X2):  # speed-up
      break
...

Analogous condition can be used in 3-opt, also for Z1, although justification in the case of 3-opt is not so strong, even when forcing only Y1 != X2.

Note that this condition rejects some valid 3-opt moves, Node Shifts that are used in 2.5-opt:

This speed-up is very effective and can be used instead of popular don’t look bits solution.

The full code for simple 3-opt and the speed-up in one loop only is as follows:

proc One_City_3_Opt_NC(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int): bool =
  type
    Move3 = object
      i, j, k: Tour_Index
      optCase: Reconnection_3_optCase
      gain: Length_Gain
  var
    improved: bool
    i, j, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    k_6, k_7:  Tour_Index
    Z1_6, Z2_6, Z1_7, Z2_7: City_Number
    gainExpected: Length_Gain
    goodMove: Move3
  
  improved = false
  goodMove.gain = 0
  block three_loops:
    
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
      else:
        i  = (N + basePos - 1) mod N
      X1 = tour[i]
      X2 = tour[(i+1) mod N]
 
      for neighbor_1 in 0 .. numberOfNeigbors-1:
        # new edges in optCase=6: *X1-Y2*, Y1-Z1, X2-Z2
        # new edges in optCase=7: *X1-Y2*, X2-Z1, Y1-Z2
        Y2 = neighbor[X1][neighbor_1]
        j  = (position[Y2] + N - 1) mod N
        Y1 = tour[j]

        if (Y1 != X1) and (Y1 != X2):
          gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
          if gainExpected > goodMove.gain:
            improved = true
            goodMove = Move3(i: i,  j: j,  k: j,
                             optCase: opt3_case_1, gain: gainExpected)

        if (Y1 == X2):  # NOTE
          break

        for neighbor_2 in 0 .. numberOfNeigbors-1:
          # new edges in optCase=6: X1-Y2, *Y1-Z1*, X2-Z2
          Z1_6 = neighbor[Y1][neighbor_2]
          k_6  = position[Z1_6]
          Z2_6 = tour[(k_6 + 1) mod N]
          # new edges in optCase=7: X1-Y2, X2-Z1, *Y1-Z2*
          Z2_7 = neighbor[Y1][neighbor_2]
          k_7  = (position[Z2_7] + N - 1) mod N
          Z1_7 = tour[k_7]
          
          if Between(i, j, k_6):
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_6, Z2_6,
                                           opt3_case_6)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: j,  k: k_6,
                               optCase: opt3_case_6, gain: gainExpected)

          if Between(i, j, k_7):
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_7, Z2_7,
                                           opt3_case_7)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: j,  k: k_7,
                               optCase: opt3_case_7, gain: gainExpected)

  if improved:
    Make_3_Opt_Move(tour,
                    goodMove.i,  goodMove.j,  goodMove.k,
                    goodMove.optCase,  position)
  result = improved

proc LS_3_Opt_NC(tour: var Tour_Array;
                 neighbor: Neighbor_Matrix;
                 neighborListLen: int = N-1) =
  var
    locallyOptimal: bool = false
    improved: bool
    baseCity: City_Number
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)
  
  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      improved = One_City_3_Opt_NC(tour, basePos, neighbor, position,
                                   numberOfNeigbors)
      if improved:
        locallyOptimal = false

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by some 2-opt and 3-opt algorithms. Random planar problems, N=200.
Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	106.52	114.46
	NN + 2opt	4721	88.17	90.89	94.52
	NN + 2opt Take Best	5119	87.53	89.09	91.25
	NN + 3opt-ND(24)	5851	86.44	87.94	89.65
	NN + 3opt-NC(24)	3589	85.76	87.89	89.86
2	NN	100	100.00	104.27	110.57
	NN + 2opt	3623	90.30	92.45	95.40
	NN + 2opt Take Best	3889	89.07	90.67	92.78
	NN + 3opt-ND(24)	5551	88.31	89.59	92.20
	NN + 3opt-NC(24)	2959	88.36	89.46	91.41
3	NN	100	100.00	110.24	122.10
	NN + 2opt	3839	91.03	94.61	97.58
	NN + 2opt Take Best	4450	90.34	91.70	94.47
	NN + 3opt-ND(24)	5808	88.72	90.63	92.96
	NN + 3opt-NC(24)	3634	88.82	90.71	92.56
4	NN	100	100.00	106.87	114.35
	NN + 2opt	3955	87.53	90.64	94.81
	NN + 2opt Take Best	4521	87.10	89.33	91.84
	NN + 3opt-ND(24)	5785	85.53	87.35	90.17
	NN + 3opt-NC(24)	3423	85.99	87.44	89.56
5	NN	100	100.00	106.86	113.89
	NN + 2opt	3723	90.16	93.61	96.94
	NN + 2opt Take Best	4421	89.79	92.18	95.17
	NN + 3opt-ND(24)	5982	88.61	90.61	92.40
	NN + 3opt-NC(24)	3691	88.57	90.66	94.46
6	NN	100	100.00	106.80	114.76
	NN + 2opt	4853	85.03	88.16	92.81
	NN + 2opt Take Best	5087	85.07	86.95	91.02
	NN + 3opt-ND(24)	5882	83.19	84.86	87.59
	NN + 3opt-NC(24)	3823	83.69	85.11	88.18
7	NN	100	100.00	104.23	110.78
	NN + 2opt	4487	86.00	88.67	92.58
	NN + 2opt Take Best	5287	84.92	86.93	88.92
	NN + 3opt-ND(24)	5882	83.92	85.59	88.45
	NN + 3opt-NC(24)	3923	83.63	85.60	88.26
8	NN	100	100.00	109.86	116.72
	NN + 2opt	5285	86.01	89.92	93.72
	NN + 2opt Take Best	5951	86.04	89.06	91.54
	NN + 3opt-ND(24)	5985	84.57	86.88	90.18
	NN + 3opt-NC(24)	3523	84.83	86.74	89.65
9	NN	100	100.00	104.99	110.15
	NN + 2opt	4321	87.50	90.42	93.91
	NN + 2opt Take Best	4721	87.01	88.96	90.70
	NN + 3opt-ND(24)	5951	85.97	87.41	89.39
	NN + 3opt-NC(24)	4055	85.51	87.37	89.05
10	NN	100	100.00	106.83	115.85
	NN + 2opt	4321	90.29	92.68	96.71
	NN + 2opt Take Best	4721	89.26	90.50	92.66
	NN + 3opt-ND(24)	5717	89.08	90.35	92.09
	NN + 3opt-NC(24)	3823	89.15	90.24	91.92

Wednesday, April 5, 2017

3-opt with Neighbor Lists and DLB – simple

Compare the code below with the code for 2-opt with neighbor lists and DLB and notice that this algorithm is simplified, not truly bi-directional version.

proc One_City_3_Opt_ND(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int;
                       DontLook: var DLB_Array): bool =
  type
    Move3 = object
      i, j, k: Tour_Index
      optCase: Reconnection_3_optCase
      gain: Length_Gain
  var
    improved: bool
    i, j, k: Tour_Index
    X1, X2, Y1, Y2, Z1, Z2: City_Number
    k_6, k_7:  Tour_Index
    Z1_6, Z2_6, Z1_7, Z2_7: City_Number
    gainExpected: Length_Gain
    goodMove: Move3
  
  improved = false
  goodMove.gain = 0
  block three_loops:
    
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
      else:
        i  = (N + basePos - 1) mod N
      X1 = tour[i]
      X2 = tour[(i+1) mod N]
 
      for neighbor_1 in 0 .. numberOfNeigbors-1:
        # new edges in optCase=6: *X1-Y2*, Y1-Z1, X2-Z2
        # new edges in optCase=7: *X1-Y2*, X2-Z1, Y1-Z2
        Y2 = neighbor[X1][neighbor_1]
        j  = (position[Y2] + N - 1) mod N
        Y1 = tour[j]

        if (Y1 != X1) and (Y1 != X2):
          gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
          if gainExpected > goodMove.gain:
            improved = true
            goodMove = Move3(i: i,  j: j,  k: j,
                             optCase: opt3_case_1, gain: gainExpected)

        for neighbor_2 in 0 .. numberOfNeigbors-1:
          # new edges in optCase=6: X1-Y2, *Y1-Z1*, X2-Z2
          Z1_6 = neighbor[Y1][neighbor_2]
          k_6  = position[Z1_6]
          Z2_6 = tour[(k_6 + 1) mod N]
          # new edges in optCase=7: X1-Y2, X2-Z1, *Y1-Z2*
          Z2_7 = neighbor[Y1][neighbor_2]
          k_7  = (position[Z2_7] + N - 1) mod N
          Z1_7 = tour[k_7]
          
          if Between(i, j, k_6):
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_6, Z2_6,
                                           opt3_case_6)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: j,  k: k_6,
                               optCase: opt3_case_6, gain: gainExpected)

          if Between(i, j, k_7):
            gainExpected = Gain_From_3_Opt(X1, X2, Y1, Y2, Z1_7, Z2_7,
                                           opt3_case_7)
            if gainExpected > goodMove.gain:
              improved = true
              goodMove = Move3(i: i,  j: j,  k: k_7,
                               optCase: opt3_case_7, gain: gainExpected)

  if improved:
    Set_DLB_off(DontLook,
                  [ tour[goodMove.i], tour[(goodMove.i + 1) mod N],
                    tour[goodMove.j], tour[(goodMove.j + 1) mod N],
                    tour[goodMove.k], tour[(goodMove.k + 1) mod N] ])
    Make_3_Opt_Move(tour,
                    goodMove.i,  goodMove.j,  goodMove.k,
                    goodMove.optCase,  position)
  result = improved

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by some 2-opt and 3-opt algorithms. Random planar problems, N=100.
Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	111.12	122.44
	NN + 2opt	1360	88.94	92.58	98.91
	NN + 2opt Take Best	1140	89.47	91.75	95.40
	NN + 3opt	79166	87.99	89.61	92.82
	NN + 3opt-ND(24)	4586	87.99	89.86	94.22
2	NN	100	100.00	107.46	119.61
	NN + 2opt	1146	90.85	94.70	100.03
	NN + 2opt Take Best	1046	88.59	92.09	97.39
	NN + 3opt	69473	87.22	89.89	94.23
	NN + 3opt-ND(24)	4586	87.22	89.87	93.04
3	NN	100	100.00	106.81	117.56
	NN + 2opt	681	88.92	93.34	97.90
	NN + 2opt Take Best	881	89.38	92.28	96.22
	NN + 3opt	66112	87.85	89.53	93.19
	NN + 3opt-ND(24)	4106	87.68	89.07	92.68
4	NN	100	100.00	108.58	116.96
	NN + 2opt	1460	85.60	88.52	92.28
	NN + 2opt Take Best	1253	85.40	86.87	89.81
	NN + 3opt	73226	83.14	84.80	87.22
	NN + 3opt-ND(24)	4586	83.15	85.01	87.43
5	NN	100	100.00	110.59	124.43
	NN + 2opt	1146	92.73	95.42	98.30
	NN + 2opt Take Best	940	91.43	93.58	97.02
	NN + 3opt	72393	90.91	92.32	94.66
	NN + 3opt-ND(24)	4166	90.91	92.27	93.67
6	NN	100	100.00	107.15	118.12
	NN + 2opt	1253	89.35	92.71	98.25
	NN + 2opt Take Best	939	88.74	90.81	92.73
	NN + 3opt	69373	87.94	89.63	91.73
	NN + 3opt-ND(24)	4373	88.20	90.00	92.09
7	NN	100	100.00	110.20	121.48
	NN + 2opt	1253	92.30	95.31	98.94
	NN + 2opt Take Best	939	91.53	93.94	97.52
	NN + 3opt	65306	90.41	91.74	94.38
	NN + 3opt-ND(24)	4273	90.41	91.63	93.30
8	NN	100	100.00	105.35	112.99
	NN + 2opt	1253	88.20	92.02	97.83
	NN + 2opt Take Best	833	88.69	90.72	95.39
	NN + 3opt	66980	87.66	88.77	94.75
	NN + 3opt-ND(24)	4273	87.66	89.34	92.54
9	NN	100	100.00	107.15	115.57
	NN + 2opt	781	92.08	95.79	100.95
	NN + 2opt Take Best	875	90.94	94.06	98.73
	NN + 3opt	71681	89.76	91.35	94.37
	NN + 3opt-ND(24)	4393	89.76	91.32	93.54
10	NN	100	100.00	106.56	113.89
	NN + 2opt	1253	87.07	90.87	94.98
	NN + 2opt Take Best	1040	86.66	88.63	91.83
	NN + 3opt	71353	86.01	87.64	90.86
	NN + 3opt-ND(24)	4273	86.01	87.41	91.10

Tuesday, April 4, 2017

2-opt with Neighbor Lists and Best from given City – alternative

Note

This example of code does not contain any new ideas and can be skipped by a reader.

proc One_City_2_Opt_N_Best_From_City(tour: var Tour_Array;
                                     basePos: Tour_Index;
                                     neighbor: Neighbor_Matrix;
                                     position: var City_Position_In_Tour;
                                     numberOfNeigbors: int): bool =
  ## Makes the best of improving moves starting from given city
  type
    Move2 = object
      i, j: Tour_Index
      gain: Length_Gain
  var
    improved: bool
    i, i_pred, i_succ, j, j_pred, j_succ: Tour_Index
    X0, X0_pred, X0_succ, Y0, Y0_pred, Y0_succ: City_Number
    gainExpected: Length_Gain
    bestMove: Move2

  improved = false
  bestMove.gain = 0
  
  i   = basePos
  X0  = tour[i]
  i_pred = (N + i - 1) mod N
  i_succ = (i + 1) mod N
  X0_pred = tour[i_pred]
  X0_succ = tour[i_succ]

  for neighbor_number in 0 .. numberOfNeigbors-1:
    Y0 = neighbor[X0][neighbor_number]    
    j  = position[Y0]
    j_pred = (N + j - 1) mod N
    j_succ = (j + 1) mod N
    Y0_pred = tour[j_pred]
    Y0_succ = tour[j_succ]

    if (X0_succ != Y0) and (Y0_succ != X0):
      gainExpected  = Gain_From_2_Opt(X0, X0_succ, Y0, Y0_succ)
      if gainExpected > bestMove.gain:
        bestMove = Move2(i: i,  j: j,  gain: gainExpected)
        improved = true
    if (X0_pred != Y0) and (Y0_pred != X0):
      gainExpected = Gain_From_2_Opt(X0_pred, X0, Y0_pred, Y0)
      if gainExpected > bestMove.gain:
        bestMove = Move2(i: i_pred,  j: j_pred,  gain: gainExpected)
        improved = true
  if improved:
    Make_2_Opt_Move(tour, bestMove.i, bestMove.j, position)
  result = improved

Monday, April 3, 2017

2-opt with Neighbor Lists and Best from given City

proc One_City_2_Opt_N_Best_From_City(tour: var Tour_Array;
                                     basePos: Tour_Index;
                                     neighbor: Neighbor_Matrix;
                                     position: var City_Position_In_Tour;
                                     numberOfNeigbors: int): bool =
  ## Makes the best of improving moves starting from given city
  type
    Move2 = object
      i, j: Tour_Index
      gain: Length_Gain
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    gainExpected: Length_Gain
    bestMove: Move2

  improved = false
  bestMove.gain = 0
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[(i+1) mod N]  # == tour[basePos]

      for neighbor_number in 0 .. numberOfNeigbors-1:
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          continue

        gainExpected = Gain_From_2_Opt(X1, X2, Y1, Y2)
        if  gainExpected > bestMove.gain:
          bestMove = Move2(i: i,  j: j,  gain: gainExpected)
          improved = true
  if improved:
    Make_2_Opt_Move(tour, bestMove.i, bestMove.j, position)
  result = improved

proc LS_2_Opt_N_BC(tour: var Tour_Array;
                   neighbor: Neighbor_Matrix;
                   neighborListLen: int = N-1) =
  ## Optimizes tour using 2-opt with neighbor lists and fixed radius,
  ## for each city makes the best of improving moves that starts from it
  var
    locallyOptimal: bool = false
    improved: bool
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      improved = One_City_2_Opt_N_Best_From_City(tour, basePos,
                                                 neighbor, position,
                                                 numberOfNeigbors)
      if improved:
        locallyOptimal = false

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by some 2-opt algorithms. Random planar problems, N=200.
Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	109.58	116.87
	NN + 2opt	4421	89.66	92.50	96.98
	NN + 2opt Take Best	4953	87.93	90.77	92.79
	NN + 2opt-NR(24)	265	88.94	91.32	95.01
	NN + 2opt-ND(24)	231	88.72	92.77	96.39
	NN + 2opt-NDR(24)	134	89.36	92.05	95.94
	NN + 2opt-N-BC(24)	497	89.20	92.18	96.75
	NN + 2opt-NR-BC(24)	234	88.42	90.90	95.06
2	NN	100	100.00	106.22	113.13
	NN + 2opt	4289	88.27	91.20	95.07
	NN + 2opt Take Best	5053	88.53	90.12	92.64
	NN + 2opt-NR(24)	265	87.78	90.26	93.83
	NN + 2opt-ND(24)	265	88.96	91.51	94.93
	NN + 2opt-NDR(24)	131	87.83	90.79	93.90
	NN + 2opt-N-BC(24)	499	87.83	90.74	93.97
	NN + 2opt-NR-BC(24)	231	87.11	89.91	93.20
3	NN	100	100.00	110.81	122.10
	NN + 2opt	3503	90.58	94.09	99.85
	NN + 2opt Take Best	4259	90.31	93.01	96.21
	NN + 2opt-NR(24)	201	90.76	93.92	97.50
	NN + 2opt-ND(24)	175	90.50	94.74	100.37
	NN + 2opt-NDR(24)	125	91.10	94.47	99.50
	NN + 2opt-N-BC(24)	403	90.69	94.09	99.06
	NN + 2opt-NR-BC(24)	177	90.26	93.54	97.36
4	NN	100	100.00	108.19	115.51
	NN + 2opt	4155	89.16	92.48	97.91
	NN + 2opt Take Best	4821	88.63	91.13	94.83
	NN + 2opt-NR(24)	331	88.18	91.57	96.27
	NN + 2opt-ND(24)	234	89.36	93.08	96.79
	NN + 2opt-NDR(24)	131	88.74	91.82	96.09
	NN + 2opt-N-BC(24)	597	88.44	92.33	96.40
	NN + 2opt-NR-BC(24)	199	88.23	91.66	95.12
5	NN	100	100.00	105.47	111.66
	NN + 2opt	3100	88.44	91.20	94.82
	NN + 2opt Take Best	3125	87.93	90.83	93.19
	NN + 2opt-NR(24)	198	87.55	90.33	93.73
	NN + 2opt-ND(24)	198	88.04	91.80	95.37
	NN + 2opt-NDR(24)	123	88.07	90.98	95.03
	NN + 2opt-N-BC(24)	322	88.06	91.21	94.08
	NN + 2opt-NR-BC(24)	173	87.45	90.11	94.13
6	NN	100	100.00	106.99	115.27
	NN + 2opt	5119	88.61	91.70	95.36
	NN + 2opt Take Best	5553	86.74	89.36	92.40
	NN + 2opt-NR(24)	297	87.67	90.39	93.91
	NN + 2opt-ND(24)	234	87.99	91.14	94.90
	NN + 2opt-NDR(24)	131	87.63	90.75	93.93
	NN + 2opt-N-BC(24)	500	87.49	90.55	93.80
	NN + 2opt-NR-BC(24)	231	86.69	89.70	91.95
7	NN	100	100.00	109.06	119.98
	NN + 2opt	4853	87.43	90.86	95.27
	NN + 2opt Take Best	4753	86.14	89.41	94.34
	NN + 2opt-NR(24)	265	85.74	89.66	95.14
	NN + 2opt-ND(24)	265	87.58	91.12	96.98
	NN + 2opt-NDR(24)	134	86.64	90.15	96.67
	NN + 2opt-N-BC(24)	565	86.83	90.74	95.90
	NN + 2opt-NR-BC(24)	331	85.83	89.68	95.53
8	NN	100	100.00	106.79	113.15
	NN + 2opt	4953	87.26	91.30	95.33
	NN + 2opt Take Best	5651	87.65	89.53	92.11
	NN + 2opt-NR(24)	231	88.07	90.27	93.96
	NN + 2opt-ND(24)	234	88.31	91.60	95.67
	NN + 2opt-NDR(24)	131	88.13	90.99	95.28
	NN + 2opt-N-BC(24)	500	87.81	90.11	94.61
	NN + 2opt-NR-BC(24)	231	87.36	89.20	92.07
9	NN	100	100.00	104.58	109.98
	NN + 2opt	4089	87.86	91.80	95.52
	NN + 2opt Take Best	5019	87.18	89.66	91.63
	NN + 2opt-NR(24)	399	87.96	90.73	94.13
	NN + 2opt-ND(24)	231	88.53	91.94	94.86
	NN + 2opt-NDR(24)	365	88.24	91.06	94.24
	NN + 2opt-N-BC(24)	929	88.03	91.00	94.26
	NN + 2opt-NR-BC(24)	531	87.73	90.29	93.77
10	NN	100	100.00	106.10	113.14
	NN + 2opt	6682	88.46	90.90	94.87
	NN + 2opt Take Best	5585	87.82	89.72	91.80
	NN + 2opt-NR(24)	297	87.94	90.73	95.79
	NN + 2opt-ND(24)	234	87.70	91.51	94.74
	NN + 2opt-NDR(24)	165	87.96	91.18	96.28
	NN + 2opt-N-BC(24)	563	87.88	90.56	93.03
	NN + 2opt-NR-BC(24)	234	86.44	89.79	92.67

Saturday, April 1, 2017

2-opt with Neighbor Lists and optional DLB and FR

Note

This example of code does not contain any new ideas and can be skipped by a reader.

proc One_City_2_Opt_NDR(tour: var Tour_Array;
                        basePos: Tour_Index;
                        neighbor: Neighbor_Matrix;
                        position: var City_Position_In_Tour;
                        numberOfNeigbors: int;
                        DontLook: var DLB_Array;
                        useDLB: bool;
                        useFixedRadius: bool): bool =
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    d_X1_X2, d_X1_Y1: Length

  improved = false
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[(i+1) mod N]  # == tour[basePos]
      d_X1_X2 = distance(X1, X2)

      for neighbor_number in 0 .. numberOfNeigbors-1:
        # after 2-opt move new tour would contain direct link X1-Y1,
        # so we look for city Y1 among cities that are close to city X1
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          # 2-opt is for non-adjacent links only
          # by constuction X1 != Y1
          continue
          
        d_X1_Y1 = distance(X1, Y1)
          
        if useFixedRadius:
          if d_X1_Y1 > d_X1_X2:
            break

        # the same as: Gain_From_2_Opt(X1, X2, Y1, Y2) > 0
        if (d_X1_X2 + distance(Y1, Y2)) -
           (d_X1_Y1 + distance(X2, Y2)) > 0:
          if useDLB:
            Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_NDR(tour: var Tour_Array;
                  neighbor: Neighbor_Matrix;
                  neighborListLen: int = N-1;
                  useDLB: bool = true;
                  useFixedRadius: bool = true) =
  ## Optimizes the given tour using 2-opt with neighbor lists
  ## and with optional Don't Look Bits (DLB) and fixed radis
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  if useDLB:
    Set_DLB_off(DontLook, tour)  
  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      if useDLB and isDLB_on(DontLook, baseCity):
        continue
      improved = One_City_2_Opt_NDR(tour, basePos, neighbor, position,
                                    numberOfNeigbors, DontLook,
                                    useDLB, useFixedRadius)
      if improved:
        locallyOptimal = false
      else:
        if useDLB:
          Set_DLB_on(DontLook, baseCity)

Thursday, March 30, 2017

2-opt with Neighbor Lists and Don't Look Bits

proc One_City_2_Opt_ND(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int;
                       DontLook: var DLB_Array): bool =
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number

  improved = false
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[(i+1) mod N]  # == tour[basePos]

      for neighbor_number in 0 .. numberOfNeigbors-1:
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          continue

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Set_DLB_off(DontLook, [X1, X2, Y1, Y2])
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_ND(tour: var Tour_Array;
                 neighbor: Neighbor_Matrix;
                 neighborListLen: int = N-1) =
  ## Optimizes the given tour using 2-opt with neighbor lists
  ## and dDon't Look Bits (DLB)
  var
    locallyOptimal: bool = false
    improved: bool
    DontLook: DLB_Array
    baseCity: City_Number
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  Set_DLB_off(DontLook, tour)
  
  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      baseCity = tour[basePos]
      if isDLB_on(DontLook, baseCity):
        continue
      improved = One_City_2_Opt_ND(tour, basePos, neighbor, position,
                                   numberOfNeigbors, DontLook)
      if not improved:
        Set_DLB_on(DontLook, baseCity)
      else:
        locallyOptimal = false

Wednesday, March 29, 2017

2-opt with Neighbor Lists and Fixed Radius

proc One_City_2_Opt_NR(tour: var Tour_Array;
                       basePos: Tour_Index;
                       neighbor: Neighbor_Matrix;
                       position: var City_Position_In_Tour;
                       numberOfNeigbors: int): bool =
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number
    radius: Length

  improved = false
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[(i+1) mod N]  # == tour[basePos]
      radius = distance(X1, X2)

      for neighbor_number in 0 .. numberOfNeigbors-1:
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          continue
          
        if distance(X1, Y1) > radius:
          break

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_NR(tour: var Tour_Array;
                 neighbor: Neighbor_Matrix;
                 neighborListLen: int = N-1) =
  ## Optimizes tour using 2-opt with neighbor lists and fixed radius
  var
    locallyOptimal: bool = false
    improved: bool
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      improved = One_City_2_Opt_NR(tour, basePos, neighbor,
                                   position, numberOfNeigbors)
      if improved:
        locallyOptimal = false

Monday, March 27, 2017

2-opt with Neighbor Lists

proc One_City_2_Opt_N(tour: var Tour_Array;
                      basePos: Tour_Index;
                      neighbor: Neighbor_Matrix;
                      position: var City_Position_In_Tour;
                      numberOfNeigbors: int): bool =
  ## Optimizes the given tour using 2-opt with neighours lists
  # For each edge looks for improvement considering neigbours
  # in ascending order of their distance
  var
    improved: bool
    pos_Y2, i, j: Tour_Index
    X1, X2, Y1, Y2: City_Number

  improved = false
  block two_loops:
    for direction in [forward, backward]:
      if direction == forward:
        i  = basePos
        X1 = tour[i]
        X2 = tour[(i+1) mod N]
      else:
        i  = (N + basePos - 1) mod N
        X2 = tour[i]
        X1 = tour[(i+1) mod N]  # == tour[basePos]

      for neighbor_number in 0 .. numberOfNeigbors-1:
        # after 2-opt move new tour would contain direct link X1-Y1,
        # so we look for city Y1 among cities that are close to city X1
        Y1 = neighbor[X1][neighbor_number]
        if direction == forward:
          j = position[Y1]
          Y2 = tour[(j+1) mod N]
        else:
          j  = (N + position[Y1] - 1) mod N  # pos[Y1] == j+1
          Y2 = tour[j]

        if (X2 == Y1) or (Y2 == X1):
          # 2-opt is for non-adjacent links only
          # by constuction X1 != Y1
          continue

        if Gain_From_2_Opt(X1, X2, Y1, Y2) > 0:
          Make_2_Opt_Move(tour, i, j, position)
          improved = true
          break two_loops
  result = improved

proc LS_2_Opt_N(tour: var Tour_Array;
                       neighbor: Neighbor_Matrix;
                       neighborListLen: int = N-1) =
  ## Optimizes the given tour using 2-opt with neighbor lists
  var
    locallyOptimal: bool = false
    improved: bool
    position: City_Position_In_Tour

  let numberOfNeigbors = min(neighborListLen, len(neighbor[0]))
  position = Create_Position_In_Tour(tour)

  while not locallyOptimal:
    locallyOptimal = true
    for basePos in 0 .. N-1:
      improved = One_City_2_Opt_N(tour, basePos, neighbor,
                                  position, numberOfNeigbors)
      if improved:
        locallyOptimal = false

Some simple statistics

Relative time, best length, average length and worst length for all tours created by NN heuristic and improved by 2-opt and 2-opt with neighbor lists (number of neighbors in parentheses). Random planar problems, N=100.
Problem #	Method	Time	Best	Avg	Worst
1	NN	100	100.00	113.18	126.03
	NN + 2opt	1253	92.30	95.93	101.34
	NN + 2opt-N(99)	939	92.98	95.97	101.72
	NN + 2opt-N(48)	520	92.89	95.89	101.72
	NN + 2opt-N(24)	313	92.89	95.56	101.72
2	NN	100	100.00	106.57	115.38
	NN + 2opt	875	86.02	90.98	96.83
	NN + 2opt-N(99)	1074	86.18	91.23	96.04
	NN + 2opt-N(48)	587	86.18	91.24	94.55
	NN + 2opt-N(24)	293	86.99	91.23	95.95
3	NN	100	100.00	106.76	115.62
	NN + 2opt	1566	82.10	84.87	92.41
	NN + 2opt-N(99)	933	82.80	85.41	90.72
	NN + 2opt-N(48)	526	83.05	85.70	91.73
	NN + 2opt-N(24)	306	82.10	85.66	90.70
4	NN	100	100.00	108.63	115.55
	NN + 2opt	1666	88.48	91.57	98.65
	NN + 2opt-N(99)	940	88.63	92.46	97.13
	NN + 2opt-N(48)	520	88.63	92.69	98.92
	NN + 2opt-N(24)	206	88.37	92.66	97.79
5	NN	100	100.00	107.56	119.38
	NN + 2opt	1046	91.27	94.17	98.35
	NN + 2opt-N(99)	933	90.99	94.80	100.14
	NN + 2opt-N(48)	419	91.85	94.73	98.68
	NN + 2opt-N(24)	206	90.70	94.69	100.00
6	NN	100	100.00	110.60	121.69
	NN + 2opt	1566	87.96	90.86	94.66
	NN + 2opt-N(99)	933	87.79	92.33	96.87
	NN + 2opt-N(48)	420	88.09	92.28	96.82
	NN + 2opt-N(24)	313	87.73	91.84	96.76
7	NN	100	100.00	111.52	123.61
	NN + 2opt	1146	90.06	94.45	97.38
	NN + 2opt-N(99)	833	91.00	94.72	98.71
	NN + 2opt-N(48)	419	90.69	94.67	97.86
	NN + 2opt-N(24)	313	90.64	94.52	97.86
8	NN	100	100.00	111.82	121.50
	NN + 2opt	1360	86.57	90.28	94.59
	NN + 2opt-N(99)	1040	86.77	90.28	95.18
	NN + 2opt-N(48)	519	86.64	90.09	94.81
	NN + 2opt-N(24)	313	86.77	89.86	95.55
9	NN	100	100.00	116.59	127.95
	NN + 2opt	1460	90.19	95.30	104.15
	NN + 2opt-N(99)	1040	90.82	96.62	105.77
	NN + 2opt-N(48)	626	90.82	96.74	105.77
	NN + 2opt-N(24)	313	90.82	96.60	105.77
10	NN	100	100.00	108.10	118.75
	NN + 2opt	881	89.68	94.35	98.28
	NN + 2opt-N(99)	874	89.96	94.64	97.56
	NN + 2opt-N(48)	487	91.84	94.73	99.41
	NN + 2opt-N(24)	200	91.23	94.23	99.17

Position of given city in tour

Using neighbor lists forces us to use some convenient and quick method to determine for given city (a neighbor) what is its position in current tour. We use an array indexed by city numbers and storing corresponding positions.

type
  City_Position_In_Tour = array[City_Number, Tour_Index]

proc Create_Position_In_Tour(tour: Tour_Array): City_Position_In_Tour =
  ## Creates array with position of each city in tour
  var
    position: City_Position_In_Tour

  for pos in 0 .. N-1:
    position[tour[pos]] = pos
  result = position

Note that array of positions should be updated during any action that changes the tour, be it reversing a segment:

proc Reverse_Segment(tour: var Tour_Array;
                     startIndex, endIndex: Tour_Index;
                     position: var City_Position_In_Tour) =
  ## Reverses order of elements in segment [startIndex, endIndex]
  ## of tour, and updates positon[] array used with neighbour lists
  var
    left, right: Tour_Index

  let inversionSize = ((endIndex - startIndex + 1 + N) mod N) div 2
 
  left  = startIndex
  right = endIndex

  for counter in 1 .. inversionSize:
    swap(tour[left], tour[right])

    position[tour[left]]  = left
    position[tour[right]] = right

    left  = (left + 1) mod N
    right = (N + right - 1) mod N

...or shifting a segment:

proc Shift_Segment(tour: var Tour_Array; i, j, k: Tour_Index;
                   position: var City_Position_In_Tour) =
  ## Shifts the segment of tour:
  ## cities from t[i+1] to t[j] from their current position to position
  ## after current city t[k], that is between cities t[k] and t[k+1].
  ## Accordingly updates positon[] array.
  # Assumes:  k, k+1 are not within the segment [i+1..j]
  let
    segmentSize = (j - i + N) mod N
    shiftSize = ((k - i + N)  - segmentSize + N) mod N
    offset = i + 1 + shiftSize
  var
    pos, posNew: Tour_Index
    segment: seq[City_Number] = newSeq[City_Number](segmentSize)

  # make a copy of the segment before shift
  for pos in 0 .. segmentSize-1:
    segment[pos] = tour[(pos + i+1) mod N]

  # shift to the left by segmentSize all cities between old position
  # of right end of the segment and new position of its left end
  pos  = (i + 1) mod N
  for counter in 1 .. shiftSize:
    tour[pos] = tour[(pos + segmentSize) mod N]
    position[tour[pos]]  = pos
    pos  = (pos + 1) mod N
  #end_for counter loop

  # put the copy of the segment into its new place in the tour
  for pos in 0 .. segmentSize-1:
    posNew = (pos + offset) mod N 
    tour[posNew] = segment[pos]    
    position[tour[posNew]] = posNew

Sunday, March 26, 2017

Nearest neighbor lists

Note that neighbor lists are used to speed up the process of optimization, and using them may cost slightly worse quality of resulting tours, even if it not always occurs.

type
  Neighbor_Matrix = array [City_Number, seq[City_Number]]

proc Build_Neighbors_Matrix(No_Of_Neigbors: int = N-1): Neighbor_Matrix =
  ## Builds array of No_Of_Neigbors nearest neighbors of each city
  # neighbor[i][j] is j-th nearest neighbour of city number i.
  var
    currentCity, otherCity: City_Number
    idx: int
    neighbors_of_currentCity: seq[City_Number]
    neighbor: Neighbor_Matrix

  newSeq(neighbors_of_currentCity, N-1)
  for currentCity in 0 .. N-1:
    # create sequence of all neighbors of current city:
    idx = 0
    for otherCity in 0 .. N-1:
      if otherCity != currentCity:
        neighbors_of_currentCity[idx] = otherCity
        idx = idx + 1

    # Sort elements in neighbors_of_currentCity by ascending distance
    # to currentCity (use any convenient method of sorting), then take
    # first No_Of_Neigbors cities from the result.
    sort(neighbors_of_currentCity) do (x,y: City_Number) -> int:
      result = cmp(distance(currentCity, x), distance(currentCity, y))

    neighbor[currentCity] = @[]
    setlen(neighbor[currentCity], No_Of_Neigbors)
    for idx in 0 .. No_Of_Neigbors-1:
      neighbor[currentCity][idx] = neighbors_of_currentCity[idx]
  result = neighbor