原文鏈接：https://cloud.tencent.com/developer/article/1146127

1.1 什么是局部搜索算法？

局部搜索是解決最優化問題的一種啟發式算法。因為對于很多復雜的問題，求解最優解的時間可能是極其長的。因此誕生了各種啟發式算法來退而求其次尋找次優解或近似最優解，局部搜索就是其中一種。它是一種近似算法（Approximate algorithms）。

局部搜索算法是從爬山法改進而來的。簡單來說，局部搜索算法是一種簡單的貪心搜索算法，該算法每次從當前解的鄰域解空間中選擇一個最好鄰居作為下次迭代的當前解，直到達到一個局部最優解(local optimal solution)。局部搜索從一個初始解出發，然后搜索解的鄰域，如有更優的解則移動至該解并繼續執行搜索，否則就停止算法獲得局部最優解。

1.2 算法思想過程

局部搜索會先從一個初始解開始，通過鄰域動作。產生初始解的鄰居解，然后根據某種策略選擇鄰居解。一直重復以上過程，直到達到終止條件。

不同局部搜索算法的區別就在于：鄰域動作的定義以及選擇鄰居解的策略。這也是決定算法好壞的關鍵之處。

1.3 什么又是鄰域動作？

其實鄰域動作就是一個函數。那么，通過這個函數，針對當前解s，產生s對應的鄰居解的一個集合。比如：

對于一個bool型問題，其當前解為：s = 1001，當將鄰域動作定義為翻轉其中一個bit時，得到的鄰居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。同理，當將鄰域動作定義為互換相鄰bit時，得到的鄰居解的集合N(s)={0101,1001,1010}.

02 簡單局部搜索

在開始我們的迭代局部搜索之前，還是先來給大家科普幾個簡單局部搜索算法。他們也是基于個體的啟發式算法（Single solution）。

2.1 爬山法（HILL-CLIMBING）

請閱讀推文 干貨 | 用模擬退火(SA, Simulated Annealing)算法解決旅行商問題

2.2 模擬退火（SIMULATED ANNEALING）

請閱讀推文 干貨 | 用模擬退火(SA, Simulated Annealing)算法解決旅行商問題

2.3 禁忌搜索算法(Tabu Search)

請閱讀推文 干貨 | 十分鐘掌握禁忌搜索算法求解帶時間窗的車輛路徑問題(附C++代碼和詳細代碼注釋) 及 干貨|十分鐘快速復習禁忌搜索(c++版)

03 迭代局部搜索（Iterated Local Search, ILS）

3.1 介紹

迭代局部搜索屬于探索性局部搜索方法（EXPLORATIVE LOCAL SEARCH METHODS）的一種。它在局部搜索得到的局部最優解上，加入了擾動，然后再重新進行局部搜索。

3.2 過程描述

注：下文的局部搜索(或者LocalSearch)指定都是內嵌的局部搜索。類似于上面介紹的幾種……

＊

迭代局部搜索過程：

＊初始狀態：best_solution(最優解)、current_solution(當前解)。

＊從初始解(best_solution)中進行局部搜索，找到一個局部最優解s1(best_solution)。

＊擾動s1(best_solution)，獲得新的解s2(current_solution)。

＊從新解s2(current_solution)中進行局部搜索，再次找到一個局部最優解s3(best_solution)。

＊基于判斷策略，對s3(current_solution)好壞進行判斷。選擇是否接受s3(current_solution)作為新的best_solution。

＊直到達到邊界條件，不然跳回第二步一直循環搜索。

其圖解如下：

偽代碼如下：

04 代碼時間

以下代碼用于求解TSP旅行商問題。

【注：代碼和程序基于win32平臺跑的，點擊閱讀原文可以直接下載或者移步留言區獲取下載鏈接】

我就不做IO了，相信需要的朋友做個IO也不是什么難事吧……

//TSP問題 迭代局部搜索求解代碼 //基于Berlin52例子求解 //作者：infinitor //時間：2018-04-12 #include <iostream> #include <cmath> #include <stdlib.h> #include <time.h> #include <vector> #include <windows.h> #include <memory.h> #include <string.h> #include <iomanip>#define DEBUGusing namespace std;#define CITY_SIZE 52 //城市數量//城市坐標 typedef struct candidate {int x;int y; }city, CITIES;//優化值 int **Delta; //解決方案 typedef struct Solution {int permutation[CITY_SIZE]; //城市排列int cost; //該排列對應的總路線長度 }SOLUTION; // 計算鄰域操作優化值 int calc_delta(int i, int k, int *tmp, CITIES * cities);//計算兩個城市間距離 int distance_2city(city c1, city c2);//根據產生的城市序列，計算旅游總距離 int cost_total(int * cities_permutation, CITIES * cities);//獲取隨機城市排列, 用于產生初始解 void random_permutation(int * cities_permutation);//顛倒數組中下標begin到end的元素位置, 用于two_opt鄰域動作 void swap_element(int *p, int begin, int end);//鄰域動作 反轉index_i <-> index_j 間的元素 void two_opt_swap(int *cities_permutation, int *new_cities_permutation, int index_i, int index_j);//本地局部搜索，邊界條件 max_no_improve void local_search(SOLUTION & best, CITIES * cities, int max_no_improve);//將城市序列分成4塊，然后按塊重新打亂順序。 //用于擾動函數 void double_bridge_move(int *cities_permutation, int * new_cities_permutation);//擾動 void perturbation(CITIES * cities, SOLUTION &best_solution, SOLUTION &current_solution);//迭代搜索 void iterated_local_search(SOLUTION & best, CITIES * cities, int max_iterations, int max_no_improve);// 更新Delta void Update(int i, int k, int *tmp, CITIES * cities);//城市排列 int permutation[CITY_SIZE]; //城市坐標數組 CITIES cities[CITY_SIZE];//berlin52城市坐標，最優解7542好像 CITIES berlin52[CITY_SIZE] = { { 565,575 },{ 25,185 },{ 345,750 },{ 945,685 },{ 845,655 }, { 880,660 },{ 25,230 },{ 525,1000 },{ 580,1175 },{ 650,1130 },{ 1605,620 }, { 1220,580 },{ 1465,200 },{ 1530,5 },{ 845,680 },{ 725,370 },{ 145,665 }, { 415,635 },{ 510,875 },{ 560,365 },{ 300,465 },{ 520,585 },{ 480,415 }, { 835,625 },{ 975,580 },{ 1215,245 },{ 1320,315 },{ 1250,400 },{ 660,180 }, { 410,250 },{ 420,555 },{ 575,665 },{ 1150,1160 },{ 700,580 },{ 685,595 }, { 685,610 },{ 770,610 },{ 795,645 },{ 720,635 },{ 760,650 },{ 475,960 }, { 95,260 },{ 875,920 },{ 700,500 },{ 555,815 },{ 830,485 },{ 1170,65 }, { 830,610 },{ 605,625 },{ 595,360 },{ 1340,725 },{ 1740,245 } };int main() {srand(1);int max_iterations = 600;int max_no_improve = 50;//初始化指針數組 Delta = new int*[CITY_SIZE];for (int i = 0; i < CITY_SIZE; i ++)Delta[i] = new int[CITY_SIZE];SOLUTION best_solution;iterated_local_search(best_solution, berlin52, max_iterations, max_no_improve);cout << endl<<endl<<"搜索完成！ 最優路線總長度 = " << best_solution.cost << endl;cout << "最優訪問城市序列如下：" << endl;for (int i = 0; i < CITY_SIZE;i++){cout << setw(4) << setiosflags(ios::left) << best_solution.permutation[i];}cout << endl << endl;return 0; }//計算兩個城市間距離 int distance_2city(city c1, city c2) {int distance = 0;distance = sqrt((double)((c1.x - c2.x)*(c1.x - c2.x) + (c1.y - c2.y)*(c1.y - c2.y)));return distance; }//根據產生的城市序列，計算旅游總距離 //所謂城市序列，就是城市先后訪問的順序，比如可以先訪問ABC，也可以先訪問BAC等等 //訪問順序不同，那么總路線長度也是不同的 //p_perm 城市序列參數 int cost_total(int * cities_permutation, CITIES * cities) {int total_distance = 0;int c1, c2;//逛一圈，看看最后的總距離是多少for (int i = 0; i < CITY_SIZE; i++){c1 = cities_permutation[i];if (i == CITY_SIZE - 1) //最后一個城市和第一個城市計算距離{c2 = cities_permutation[0];}else{c2 = cities_permutation[i + 1];}total_distance += distance_2city(cities[c1], cities[c2]);}return total_distance; }//獲取隨機城市排列 void random_permutation(int * cities_permutation) {int i, r, temp;for (i = 0; i < CITY_SIZE; i++){cities_permutation[i] = i; //初始化城市排列，初始按順序排}for (i = 0; i < CITY_SIZE; i++){//城市排列順序隨機打亂r = rand() % (CITY_SIZE - i) + i;temp = cities_permutation[i];cities_permutation[i] = cities_permutation[r];cities_permutation[r] = temp;} }//顛倒數組中下標begin到end的元素位置 void swap_element(int *p, int begin, int end) {int temp;while (begin < end){temp = p[begin];p[begin] = p[end];p[end] = temp;begin++;end--;} }//鄰域動作 反轉index_i <-> index_j 間的元素 void two_opt_swap(int *cities_permutation, int *new_cities_permutation, int index_i, int index_j) {for (int i = 0; i < CITY_SIZE; i++){new_cities_permutation[i] = cities_permutation[i];}swap_element(new_cities_permutation, index_i, index_j); }int calc_delta(int i, int k, int *tmp, CITIES * cities){int delta = 0;/*以下計算說明：對于每個方案，翻轉以后沒必要再次重新計算總距離只需要在翻轉的頭尾做個小小處理比如：有城市序列 1-2-3-4-5 總距離 = d12 + d23 + d34 + d45 + d51 = A翻轉后的序列 1-4-3-2-5 總距離 = d14 + d43 + d32 + d25 + d51 = B由于 dij 與 dji是一樣的，所以B也可以表示成 B = A - d12 - d45 + d14 + d25下面的優化就是基于這種原理*/if (i == 0){if (k == CITY_SIZE - 1){delta = 0;}else{delta = 0- distance_2city(cities[tmp[k]], cities[tmp[k + 1]])+ distance_2city(cities[tmp[i]], cities[tmp[k + 1]])- distance_2city(cities[tmp[CITY_SIZE - 1]], cities[tmp[i]])+ distance_2city(cities[tmp[CITY_SIZE - 1]], cities[tmp[k]]);}}else{if (k == CITY_SIZE - 1){delta = 0- distance_2city(cities[tmp[i - 1]], cities[tmp[i]])+ distance_2city(cities[tmp[i - 1]], cities[tmp[k]])- distance_2city(cities[tmp[0]], cities[tmp[k]])+ distance_2city(cities[tmp[i]], cities[tmp[0]]);}else{delta = 0- distance_2city(cities[tmp[i - 1]], cities[tmp[i]])+ distance_2city(cities[tmp[i - 1]], cities[tmp[k]])- distance_2city(cities[tmp[k]], cities[tmp[k + 1]])+ distance_2city(cities[tmp[i]], cities[tmp[k + 1]]);}}return delta; }/*去重處理，對于Delta數組來說，對于城市序列1-2-3-4-5-6-7-8-9-10，如果對3-5應用了鄰域操作2-opt ， 事實上對于7-10之間的翻轉是不需要重復計算的。 所以用Delta提前預處理一下。當然由于這里的計算本身是O（1） 的，事實上并沒有帶來時間復雜度的減少（更新操作反而增加了復雜度） 如果delta計算 是O（n）的，這種去重操作效果是明顯的。 */void Update(int i, int k, int *tmp, CITIES * cities){if (i && k != CITY_SIZE - 1){i --; k ++;for (int j = i; j <= k; j ++){for (int l = j + 1; l < CITY_SIZE; l ++){Delta[j][l] = calc_delta(j, l, tmp, cities);}}for (int j = 0; j < k; j ++){for (int l = i; l <= k; l ++){if (j >= l) continue;Delta[j][l] = calc_delta(j, l, tmp, cities);}}}// 如果不是邊界，更新(i-1, k + 1)之間的 else{for (i = 0; i < CITY_SIZE - 1; i++){for (k = i + 1; k < CITY_SIZE; k++){Delta[i][k] = calc_delta(i, k, tmp, cities);}} }// 邊界要特殊更新 } //本地局部搜索，邊界條件 max_no_improve //best_solution最優解 //current_solution當前解 void local_search(SOLUTION & best_solution, CITIES * cities, int max_no_improve) {int count = 0;int i, k;int inital_cost = best_solution.cost; //初始花費int now_cost = 0;SOLUTION *current_solution = new SOLUTION; //為了防止爆棧……直接new了，你懂的for (i = 0; i < CITY_SIZE - 1; i++){for (k = i + 1; k < CITY_SIZE; k++){Delta[i][k] = calc_delta(i, k, best_solution.permutation, cities);}}do{//枚舉排列for (i = 0; i < CITY_SIZE - 1; i++){for (k = i + 1; k < CITY_SIZE; k++){//鄰域動作two_opt_swap(best_solution.permutation, current_solution->permutation, i, k);now_cost = inital_cost + Delta[i][k];current_solution->cost = now_cost;if (current_solution->cost < best_solution.cost){count = 0; //better cost found, so resetfor (int j = 0; j < CITY_SIZE; j++){best_solution.permutation[j] = current_solution->permutation[j];}best_solution.cost = current_solution->cost;inital_cost = best_solution.cost;Update(i, k, best_solution.permutation, cities);}}}count++;} while (count <= max_no_improve); }//將城市序列分成4塊，然后按塊重新打亂順序。 //用于擾動函數 void double_bridge_move(int *cities_permutation, int * new_cities_permutation) {int temp_perm[CITY_SIZE];int pos1 = 1 + rand() % (CITY_SIZE / 4);int pos2 = pos1 + 1 + rand() % (CITY_SIZE / 4);int pos3 = pos2 + 1 + rand() % (CITY_SIZE / 4);int i;vector<int> v;//第一塊for (i = 0; i < pos1; i++){v.push_back(cities_permutation[i]);}//第二塊for (i = pos3; i < CITY_SIZE; i++){v.push_back(cities_permutation[i]);}//第三塊for (i = pos2; i < pos3; i++){v.push_back(cities_permutation[i]);}//第四塊for (i = pos1; i < pos2; i++){v.push_back(cities_permutation[i]);}for (i = 0; i < (int)v.size(); i++){new_cities_permutation[i] = v[i];} }//擾動 void perturbation(CITIES * cities, SOLUTION &best_solution, SOLUTION &current_solution) {double_bridge_move(best_solution.permutation, current_solution.permutation);current_solution.cost = cost_total(current_solution.permutation, cities); }//迭代搜索 //max_iterations用于迭代搜索次數 //max_no_improve用于局部搜索邊界條件 void iterated_local_search(SOLUTION & best_solution, CITIES * cities, int max_iterations, int max_no_improve) {SOLUTION *current_solution = new SOLUTION;//獲得初始隨機解random_permutation(best_solution.permutation);best_solution.cost = cost_total(best_solution.permutation, cities);local_search(best_solution, cities, max_no_improve); //初始搜索for (int i = 0; i < max_iterations; i++){perturbation(cities, best_solution, *current_solution); //擾動+判斷是否接受新解local_search(*current_solution, cities, max_no_improve);//繼續局部搜索//找到更優解if (current_solution->cost < best_solution.cost){for (int j = 0; j < CITY_SIZE; j++){best_solution.permutation[j] = current_solution->permutation[j];}best_solution.cost = current_solution->cost;}cout << setw(13) << setiosflags(ios::left) <<"迭代搜索 " << i << " 次\t" << "最優解 = " << best_solution.cost << " 當前解 = " << current_solution->cost << endl;}}

總結

以上是生活随笔為你收集整理的迭代局部搜索算法(Iterated local search)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。