派單--路徑規(guī)劃

多起點(diǎn)局部搜索(multi-start local search)

Iterated local search（迭代局部搜索）
  • 優(yōu)化
    • 用于擾動(dòng)的double_bridge_move函數(shù)；
    • 產(chǎn)生隨機(jī)初始解的方法、delta數(shù)組的計(jì)算；
    • 將距離表示為double型以提高精度；
局部搜索 解決最優(yōu)化 是啟發(fā)式算法
    • 啟發(fā)式算法來退而求其次尋找次優(yōu)解或近似最優(yōu)解，局部搜索就是其中一種。它是一種近似算法（Approximate algorithms）
    • 鄰域動(dòng)作的定義以及選擇鄰居解的策略
    • 鄰域動(dòng)作：
      針對當(dāng)前解s，產(chǎn)生s對應(yīng)的鄰居解的一個(gè)集合。
對于一個(gè)bool型問題，其當(dāng)前解為：s = 1001，
當(dāng)將鄰域動(dòng)作定義為翻轉(zhuǎn)其中一個(gè)bit時(shí)，
得到的鄰居解的集合N(s)={0001,1101,1011,1000}，其中N(s) ∈ S。
同理，當(dāng)將鄰域動(dòng)作定義為互換相鄰bit時(shí)，
得到的鄰居解的集合N(s)={0101,1001,1010}.
簡單局部搜索
  • 爬山法
  • 模擬退火
  • 禁忌搜索算法
迭代局部搜索

在局部搜索得到的局部最優(yōu)解上，加入了擾動(dòng)，然后再重新進(jìn)行局部搜索


image.png

image.png
image.png
求解TSP旅行商問題
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png

image.png
////////////////////////

//TSP問題 迭代局部搜索求解代碼

//基于Berlin52例子求解

//作者：infinitor

//時(shí)間：2018-04-12

//修改：舟寒丶 

//修改時(shí)間：2019-12-2

////////////////////////



#include <iostream>

#include <cmath>

#include <stdlib.h>

#include <time.h>

#include <vector>

#include <windows.h>

#include <memory.h>

#include <string.h>

#include <iomanip>



#define DEBUG



using namespace std;



#define CITY_SIZE 52 //城市數(shù)量





//城市坐標(biāo)

typedef struct candidate

{

    int x;

    int y;

}city, CITIES;



//優(yōu)化值

double **Delta; 



//解決方案

typedef struct Solution

{

    int permutation[CITY_SIZE]; //城市排列

    double cost;                        //該排列對應(yīng)的總路線長度

}SOLUTION;

// 計(jì)算鄰域操作優(yōu)化值 

double calc_delta(int i, int k, int *tmp, CITIES * cities);



//計(jì)算兩個(gè)城市間距離

double distance_2city(city c1, city c2);



//根據(jù)產(chǎn)生的城市序列，計(jì)算旅游總距離

double cost_total(int * cities_permutation, CITIES * cities);



//獲取隨機(jī)城市排列, 用于產(chǎn)生初始解

void random_permutation(int * cities_permutation);



//顛倒數(shù)組中下標(biāo)begin到end的元素位置, 用于two_opt鄰域動(dòng)作

void swap_element(int *p, int begin, int end);



//鄰域動(dòng)作 反轉(zhuǎn)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);



//判斷接受準(zhǔn)則

bool AcceptanceCriterion(int *cities_permutation, int *new_cities_permutation, CITIES * p_cities);



//將城市序列分成4塊，然后按塊重新打亂順序。

//用于擾動(dòng)函數(shù)

void double_bridge_move(int *cities_permutation, int * new_cities_permutation,CITIES * cities);



//擾動(dòng)

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];

//城市坐標(biāo)數(shù)組

CITIES cities[CITY_SIZE];





//berlin52城市坐標(biāo)，最優(yōu)解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;

    //初始化指針數(shù)組 

    Delta = new double*[CITY_SIZE];

    for (int i = 0; i < CITY_SIZE; i ++)

        Delta[i] = new double[CITY_SIZE];

    

    SOLUTION best_solution;



    iterated_local_search(best_solution, berlin52, max_iterations, max_no_improve);



    cout << endl<<endl<<"搜索完成！最優(yōu)路線總長度 = " << best_solution.cost << endl;

    cout << "最優(yōu)訪問城市序列如下：" << endl;

    for (int i = 0; i < CITY_SIZE;i++)

    {

        cout << setw(4) << setiosflags(ios::left) << best_solution.permutation[i];

    }



    cout << endl << endl;



    return 0;

}



//計(jì)算兩個(gè)城市間距離

double distance_2city(city c1, city c2)

{

    double distance = 0;

    distance = sqrt((double)((c1.x - c2.x)*(c1.x - c2.x) + (c1.y - c2.y)*(c1.y - c2.y)));



    return distance;

}



//根據(jù)產(chǎn)生的城市序列，計(jì)算旅游總距離

//所謂城市序列，就是城市先后訪問的順序，比如可以先訪問ABC，也可以先訪問BAC等等

//訪問順序不同，那么總路線長度也是不同的

//p_perm 城市序列參數(shù)

double cost_total(int * cities_permutation, CITIES * cities)

{

    double total_distance = 0;

    int c1, c2;

    //逛一圈，看看最后的總距離是多少

    for (int i = 0; i < CITY_SIZE; i++)

    {

        c1 = cities_permutation[i];

        if (i == CITY_SIZE - 1) //最后一個(gè)城市和第一個(gè)城市計(jì)算距離

        {

            c2 = cities_permutation[0];

        }

        else

        {

            c2 = cities_permutation[i + 1];

        }

        total_distance += distance_2city(cities[c1], cities[c2]);

    }



    return total_distance;

}



//獲取隨機(jī)城市排列

void random_permutation(int * cities_permutation)

{

    int n=CITY_SIZE;

    int temp[CITY_SIZE];

    for(int i=0;i<CITY_SIZE;i++)

       temp[i]=i; 

    for(int i=0;i<CITY_SIZE-1;i++)

    {

        int r=rand()%n;

        cities_permutation[i]=temp[r];

        temp[r]=temp[n-1];

        n--;

    }

    cities_permutation[CITY_SIZE-1]=temp[0];

     

}



//顛倒數(shù)組中下標(biāo)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--;

    }

}



//鄰域動(dòng)作 反轉(zhuǎn)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);

}



double calc_delta(int i, int k,  int *tmp, CITIES * cities)

{

    /*

    

                以下計(jì)算說明：

                對于每個(gè)方案，翻轉(zhuǎn)以后沒必要再次重新計(jì)算總距離

                只需要在翻轉(zhuǎn)的頭尾做個(gè)小小處理



                比如：

                有城市序列   1-2-3-4-5 總距離 = d12 + d23 + d34 + d45 + d51 = A

                翻轉(zhuǎn)后的序列 1-4-3-2-5 總距離 = d14 + d43 + d32 + d25 + d51 = B

                由于 dij 與 dji是一樣的，所以B也可以表示成 B = A - d12 - d45 + d14 + d25

                下面的優(yōu)化就是基于這種原理

    */

    double delta=0;

    if((i==0)&&(k==CITY_SIZE-1))

       delta=0;

    else

    {

        int i2=(i-1+CITY_SIZE)%CITY_SIZE;

        int k2=(k+1)%CITY_SIZE; 

        delta = 0

                - distance_2city(cities[tmp[i2]], cities[tmp[i]])

                + distance_2city(cities[tmp[i2]], cities[tmp[k]])

                - distance_2city(cities[tmp[k]], cities[tmp[k2]])

                + distance_2city(cities[tmp[i]], cities[tmp[k2]]);

    }

    return delta;



}



/*

    去重處理，對于Delta數(shù)組來說，對于城市序列1-2-3-4-5-6-7-8-9-10，如果對3-5應(yīng)用了鄰域操作2-opt ， 事實(shí)上對于

    7-10之間的翻轉(zhuǎn)是不需要重復(fù)計(jì)算的。所以用Delta提前預(yù)處理一下。

    

    當(dāng)然由于這里的計(jì)算本身是O（1） 的，事實(shí)上并沒有帶來時(shí)間復(fù)雜度的減少（更新操作反而增加了復(fù)雜度） 

    如果delta計(jì)算 是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最優(yōu)解

//current_solution當(dāng)前解

void local_search(SOLUTION & best_solution, CITIES * cities, int max_no_improve)

{

    int count = 0;

    int i, k;



    double inital_cost = best_solution.cost; //初始花費(fèi)



    double 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++)

            {

                //鄰域動(dòng)作

                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 reset

                    for (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);

}



//判斷接受準(zhǔn)則

bool AcceptanceCriterion(int *cities_permutation, int *new_cities_permutation, CITIES * cities)

{

    int AcceptLimite=500;

    int c1=cost_total(cities_permutation, cities);

    int c2=cost_total(new_cities_permutation, cities)-500;

    if (c1<c2)

      return false;

    else

      return true;

}



//將城市序列分成4塊，然后按塊重新打亂順序。

//用于擾動(dòng)函數(shù)

void double_bridge_move(int *cities_permutation, int * new_cities_permutation,CITIES * cities)

{

    /*對這一段函數(shù)，我們提出修改。因?yàn)閷?shí)際上按原代碼的方法并不能將

     第一大塊有效的擾動(dòng)。同時(shí)，固定的擾動(dòng)方法在第二次擾動(dòng)后會(huì)大致恢

     復(fù)原來的情形，只有少部分改變。我們提出一種將位置標(biāo)簽pos放入數(shù)組，

     再進(jìn)行隨記排序來擾動(dòng)的方案。同時(shí)去掉vector，這太傻了。

     再補(bǔ)充一下，我認(rèn)為除3比除4更好。

     順便修改了一下acceptance。*/

     

    int pos[5];

    pos[0]= 0; 

    pos[1]= rand()%(CITY_SIZE/3)+1;

    pos[2]= rand()%(CITY_SIZE/3)+CITY_SIZE/3;

    pos[3]= rand()%(CITY_SIZE/3)+(CITY_SIZE/3)*2;

    pos[4]= CITY_SIZE;

     

    int n=4;

    int random_order[4],temp[4];

    for(int i=0;i<4;i++)

       temp[i]=i; 

    for(int i=0;i<3;i++)

    {

        int r=rand()%n;

        random_order[i]=temp[r];

        temp[r]=temp[n-1];

        n--;

    }

    random_order[3]=temp[0];

    

    int deadprotect=0;

    do

    {

        int i=0;

        for (int j=pos[random_order[0]];j<pos[random_order[0]+1];j++)

        {

            new_cities_permutation[i]=cities_permutation[j];

            i++;

        }

    

        for (int j=pos[random_order[1]];j<pos[random_order[1]+1];j++)

        {

            new_cities_permutation[i]=cities_permutation[j];

            i++;

        }

    

        for (int j=pos[random_order[2]];j<pos[random_order[2]+1];j++)

        {

            new_cities_permutation[i]=cities_permutation[j];

            i++;

        }

    

        for (int j=pos[random_order[3]];j<pos[random_order[3]+1];j++)

        {

            new_cities_permutation[i]=cities_permutation[j];

            i++;

        }

        

        deadprotect++;

        //cout<<deadprotect;

        //cout<<endl;

        if (deadprotect==5) break;

 

    }while(AcceptanceCriterion(cities_permutation, new_cities_permutation, cities));

}





//擾動(dòng)

void perturbation(CITIES * cities, SOLUTION &best_solution, SOLUTION &current_solution)

{

    double_bridge_move(best_solution.permutation, current_solution.permutation,berlin52);

    current_solution.cost = cost_total(current_solution.permutation, cities);

}



//迭代搜索

//max_iterations用于迭代搜索次數(shù)

//max_no_improve用于局部搜索邊界條件

void iterated_local_search(SOLUTION & best_solution, CITIES * cities, int max_iterations, int max_no_improve)

{

    SOLUTION *current_solution = new SOLUTION;



    //獲得初始隨機(jī)解

    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); //擾動(dòng)+判斷是否接受新解

        local_search(*current_solution, cities, max_no_improve);//繼續(xù)局部搜索



        //找到更優(yōu)解

        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" << "最優(yōu)解 = " << best_solution.cost << " 當(dāng)前解 = " << current_solution->cost << endl;

    }



}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 局部搜索算法 目錄： 1、數(shù)學(xué)定義 2、過程描述 3、算法簡介 4、總結(jié) 1、數(shù)學(xué)定義 局部搜索是解決最優(yōu)化問題的...
    迷之菌閱讀 10,471評論 0贊 3
  • 姓名：李鴻彬 學(xué)號：16040520011 轉(zhuǎn)載自http://blog.csdn.net/u010159842/...
    The_HotBean閱讀 13,347評論 0贊 6
  • 廢話不多，直接正文！ 本次考試中，摘錄了這幾個(gè)學(xué)生的習(xí)作。他們優(yōu)美的語言，獨(dú)特的見解，可以讓其余的學(xué)生學(xué)習(xí)一下！
    七秒鐘的記憶_384c閱讀 1,650評論 0贊 1
  • 攝影需要激情。沒有激情，攝影就是體力勞動(dòng)；有了激情，那就變成了樂趣和享受?？扉T，記錄眼前的場景，那只是愛好者；把場...
    每日愛圖閱讀 221評論 0贊 0
  • 說起國內(nèi)的景觀，大都索然無味，我當(dāng)然不是空口無憑，這些年我去過的什么這個(gè)寺那個(gè)廟，又是什么耗資幾千萬修剪的什么水...
    布雷路閱讀 485評論 1贊 2

友情鏈接更多精彩內(nèi)容