元啟發式算法常用操作詳解

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算子

運籌優化 EI企業智能 EI創新孵化Lab

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。