元启发式算法常用操作详解

1. 问题描述

很多问题的优化可以建模为基于序列的优化，如旅行商问题（TSP）,排产问题，各类资源分配问题等，不同的序列有不同的优度。寻找最优序列的问题是NP难问题（其解空间为N!）。

2. 解决方法

1. 常用两种方法解决这类问题：一种是启发式算法，基于问题本身的规则得到较好的可行解，本质是贪心算法，这种方法速度较快，但因与问题本身联系紧密（problem-specific）,导致其通用性较差。

2. 另一种方法是元启发式算法，例如遗传算法、禁忌搜索算法、蚁群算法、模拟退火算法等。这类方法从进化，物理等过程中受到启发，得到一种解空间的搜索策略，因其搜索策略独立于问题本身（problem-independent）,因此通用性强。这类方法有两个最本质的操作：

○ 选择

○ 改变

3. 选择

选择的策略基本分为三类：

1. 选择最优解（遗传算法常选择前N个最优解，防止进入局部极小值；禁忌搜索选择1个最优的解，通过禁忌策略跳出局部极小值）。

2. 轮盘赌选择（根据每个解的评价值S，通过某种映射F（线性、指数等），得到每个解的概率P，然后根据概率选择解），公式：P = F(S)，从而避免选择最优解，陷入局部极小值。

3. 锦标赛选择（从所有解中随机抽取N个，再从N个中找最优解），有点神经网络中dropout的思想，也是种避免陷入局部极小值的策略。

4. 改变

常用的改变策略有交叉和变异，但本质都是从一个解改变为另一个解，如基于序列优化的问题，就是从一个序列，变为另一个序列（1,2,3 -> 2,1,3）,改变策略要兼顾保留原始解已有的良好结构，同时高效的探索新的结构。改变策略对于元启发式算法的效果和效率起到决定性作用，因此本文主要重点介绍几个变异算子。

1. Swap(交换算子)

a. 基本操作：随机交换序列中的一对（或多对）数字，形成新序列。

b. 代码：

def swap_operator(vector, pair_number=1):

    '''

    # 交换算子 swap

    :param vector: [0,1,2,3]

    :param pair_number: 交换对数  > 0

    :return: 交换后的vector

    '''

    # 复制，否则会影响原数组

    vector_copy = vector.copy()

    # 生成若干对交换索引

    # swap_index = np.random.choice(range(0, len(vector)), [pair_number, 2],replace=False) # 不重复

    swap_index = np.random.randint(0, len(vector), [pair_number, 2]) # 随机

    # 交换元组按正序排列

    swap_index.sort()

    # 将索引对应的数字交换

    for pair in swap_index:

        vector_copy[pair[0]], vector_copy[pair[1]] = vector_copy[pair[1]], vector_copy[pair[0]]   # 交换两个数

    return vector_copy

2. Cross(交叉算子)

a. 基本操作：序列自交叉，将序列分组，随机按组打乱重排。

b. 代码：

def cross_operator(vector, slice_number=4):

    '''

    # 交叉算子 cross

    :param vector: [0,1,2,3]

    :param slice_number: 切割位个数  > 0

    :return: 交叉后的vector

    '''

    # 生成若干个切割位索引

    # cross_index = np.random.choice(range(0, len(vector)), slice_number, replace=False) # 不重复

    cross_index = np.random.randint(0, len(vector), slice_number) # 随机

    # 对索引排序，否则切割会有重复数组

    cross_index.sort()

    # 按切割索引切分数组

    vector = np.hsplit(np.asarray(vector), cross_index)

    # 将子片段打乱 shuffle

    np.random.shuffle(vector)

    # 形成新的数组

    vector = [i for array in vector for i in array]

    return vector

3. Flip(翻转算子)

a. 基本操作：将序列分组，每组翻转后重组。

b. 代码：

def flip_operator(vector, slice_number=2):

    '''

    # 翻转算子 flip

    :param vector: [0,1,2,3]

    :param slice_number: slice_number: 切割位个数  > 0

    :return: 翻转后的vector

    '''

    # 生成若干个切割位索引

    # flip_index = np.random.choice(range(0, len(vector)), slice_number, replace=False) # 不重复

    flip_index = np.random.randint(0, len(vector), slice_number) # 随机

    # 对索引排序，否则切割会有重复数组

    flip_index.sort()

    # 按切割索引切分数组

    vector = np.hsplit(np.asarray(vector),  flip_index)

    # 对每个子数组翻转 [1, 2, 3] -> [3, 2, 1]

    vector = [i for array in vector for i in array[::-1]]

    return vector

4. Untie(解结算子)

a. 基本操作：将序列分为三段，对中间一段翻转，形成新序列。

b. 代码：

def untie_operator(vector):

    '''

    # 结结算子 untie

    :param vector: [0,1,2,3]

    :return: 翻转中间数组后的vector

    '''

    # 复制，否则会影响原数组

    vector_copy = vector.copy()

    # 生成一对交换索引

    # untie_index = np.random.choice(range(0, len(vector)), [pair_number, 2],replace=False) # 不重复

    untie_index = np.random.randint(0, len(vector), 2) # 随机

    # 对索引排序，否则无法翻转数组

    untie_index.sort()

    # 将索引对应的数字交换

    vector_copy[untie_index[0]:untie_index[1]] = vector_copy[untie_index[0]:untie_index[1]][::-1]    # 翻转某一段数组

    return vector_copy

5. Shift(转移算子)

a. 基本操作：将序列中的一个数字转移到序列中的另一个位置。

b. 代码：

def shift_operator(vector):

    '''

    # 转移算子 shift

    :param vector: [0,1,2,3]

    :param shift_number: 转移个数  > 0

    :return: 转移后的vector

    '''

    # 复制，否则会影响原数组

    vector_copy = list(vector.copy())

    # 生成若干对转移索引

    # shift_index = np.random.choice(range(0, len(vector)), 2,replace=False) # 不重复

    shift_index = np.random.randint(0, len(vector), 2) # 随机

    # 将索引对应的第一个数字插入到第二个数字前

    if shift_index[0] <= shift_index[1]:

        vector_copy.insert(shift_index[1], vector_copy[shift_index[0]])

        vector_copy.pop(shift_index[0])

    else:

        vector_copy.insert(shift_index[1], vector_copy.pop(shift_index[0]))

    return vector_copy

6. Graft(嫁接算子)

a. 基本操作：将序列中的一段序列转移到序列中的另一个位置

b. 代码：

def graft_operator(vector):

    '''

    # 嫁接算子 graft

    :param vector: [0,1,2,3]

    :param shift_number: 转移个数  > 0

    :return: 嫁接后的vector

    '''

    # 生成若干个切割位索引

    # graft_index = np.random.choice(range(0, len(vector)), slice_number, replace=False) # 不重复

    graft_index = np.random.randint(0, len(vector), 2)  # 随机

    # 对索引排序，否则切割会有重复数组

    graft_index.sort()

    # 按切割索引切分数组

    vector = np.hsplit(np.asarray(vector), graft_index)

    # 将中间序列插入到新序列

    new_vector = list(vector[0])[::-1] + list(vector[-1])[::-1]

    # 随机一个插入位点

    index = np.random.randint(len(new_vector))

    # 合并为新数组

    vector = new_vector[:index] + list(vector[1]) + new_vector[index:]

    return vector

7. Cross_and_untie(组合算子)

a. 基本操作：交叉算子和解锁算子的组合操作。

b. 代码：

def cross_and_untie_operator(vector, slice_number=2):

    '''

    # 交叉结结算子 cross

    :param vector: [0,1,2,3]

    :param slice_number: 切割位个数  > 0

    :return: 交叉后的vector

    '''

    # 生成若干个切割位索引

    # cross_index = np.random.choice(range(0, len(vector)), slice_number, replace=False) # 不重复

    cross_index = np.random.randint(0, len(vector), slice_number) # 随机

    # 对索引排序，否则切割会有重复数组

    cross_index.sort()

    # 按切割索引切分数组

    vector = np.hsplit(np.asarray(vector), cross_index)

    # 将子片段打乱 shuffle

    np.random.shuffle(vector)

    # 随机选择一个数组进行翻转

    index = np.random.randint(len(vector))

    # index = 1

    vector[index] = vector[index][::-1]

    # 对每个子数组翻转,形成新数组 [1, 2, 3] -> [3, 2, 1]

    vector = [i for array in vector for i in array]

    return vector

8. 总结：

# 第一代：swap, 第二代：cross, flip, 第三代：untie, shift, graft

# shift: 能找到接近最优值的算子, 但不稳定

# untie: 能在最快时间找到接近最优解的算子， 稳定性很强

# cross_and_untie: 种群数量足够大时，效果优于untie算子