第三次作业题涉及到一个新的优化算法： Two Edge Exchange，也叫2-opt算法。

1 Two Edge Exchange Move理论基础

2-opt算法是一个非常著名的路线规划的优化方法。其核心是，每次去除两条不相邻的路径，并将产生的子序列重新连接起来。过程如图所示：

2-opt图解

这个概念也可以应用于工业生产中的订单排期。在这里，在一个订单序列中，订单不仅作为单独的元素被考虑，订单之间的连接（路径或边）也被考虑。如果订单直接跟随订单，这两个订单通过一个链接，或 "边"，连接。因此，所谓的TwoEdge Exchange Move可以定义如下：

一个TwoEdgeExchange Move描述了两对订单和的连接交换。在这里，连接可能不相邻。连接和被移除，并且被重新连接的路径或者边为：和。

a) 第一次交换

给出以下的生产序列 s=[0,1,2,3,4,5,6]。手动执行以下TwoEdgeExchange-Move：
。

• 答案：

*提示：思路很简单，把原本连着的 i 和 i+1 以及 j 和 j+1 断开，再把 i 和 j 连起来， i+1 和 j+1 也要连起来

b) 计算复杂度

确定TwoEdge Exchange-Move邻域的复杂性。假设一个解决方案由长度为的置换表示，并且成立。

注：复杂性是的函数。

• 答案：

3 TwoEdgeExchange-Move 代码实现

用TwoEdge Exchange-Move邻域来扩展前八章中创建的求解器Solver 。创建 "TwoEdgeExchangeMove"和 "TwoEdgeExchangeNeighborhood"类。

在数据集InputFlowshopSIST20.json上测试邻域。使用BestImprovement策略和FCFS初始方案。

# 2 classes in Neighborhood.py
class TwoEdgeExchangeMove:
# 这个类借鉴了前面内容中，列表元素交换的思路。我们首先定义TwoEdgeExchangeMove类，定义类的时候要注意类应具有普遍性，也就是说类应该能够适用于交换任意两个位置的订单。
# 看构造函数的参数表，我们首先需要一个初始排列，还有我们想要交换位置的元素的索引。然后在构造函数中完成交换过程，并把交换位置后的列表赋给self.Permutation，即这个类的对象的属性。
# 这样，每当我们构造一个TwoEdgeExchangeMove的对象（在循环中），这个对象的Permutation属性就被确定了
    def __init__(self, initialPermutation, indexA, indexB):
        self.Permutation = list(initialPermutation)
        self.IndexA = indexA
        self.IndexB = indexB

        # 这里需要注意细节，python中的列表包含左边，不包含右边
        # 另外还要理解2-opt的交换过程，简单说就是从序列中选两个点，A和B，A左边和B右边的节点和路径保持不变，AB中间的节点颠倒顺序
        list_left = initialPermutation[0: indexA+1]
        list_mid = reversed(initialPermutation[indexA+1: indexB+1])
        list_right = initialPermutation[indexB+1: ]

        self.Permutation = list_left+list(list_mid)+list_right

class TwoEdgeExchangeNeighborhood(BaseNeighborhood):
    def __init__(self, inputData, initialPermutation, evaluationLogic, solutionPool):
        super().__init__(inputData, initialPermutation, evaluationLogic, solutionPool)
        self.Type = 'TwoEdgeExchange'

    def DiscoverMoves(self):
        for i in range(0, len(self.Permutation)-4):
            for j in range(i+3, len(self.Permutation)-1):
                
                twoEdgeExchangeMove = TwoEdgeExchangeMove(self.Permutation, i, j)

                self.Moves.append(twoEdgeExchangeMove)

# ImprovementAlgorithm.py
def CreateNeighborhood(self, neighborhoodType, bestCurrentSolution):
    if neighborhoodType == 'Swap':
        return SwapNeighborhood(self.InputData, bestCurrentSolution.Permutation, self.EvaluationLogic, self.SolutionPool)
    elif neighborhoodType == 'Insertion':
        return InsertionNeighborhood(self.InputData, bestCurrentSolution.Permutation, self.EvaluationLogic, self.SolutionPool)
    elif neighborhoodType == 'TwoEdgeExchange':
        return TwoEdgeExchangeNeighborhood(self.InputData, bestCurrentSolution.Permutation, self.EvaluationLogic, self.SolutionPool)
    else:
        raise Exception(f"Neighborhood type {neighborhoodType} not defined.")

from Solver import *


data = InputData("InputFlowshopSIST20.json")

localSearch = IterativeImprovement(data, 'BestImprovement', ['TwoEdgeExchange'])

solver = Solver(data, 1008)

solver.RunLocalSearch(
    constructiveSolutionMethod='FCFS',
    algorithm=localSearch)