---
# System prepended metadata

title: Tabu_search

---

介紹
===
### 目的
Tabu search適合處理組合最佳化的問題，特別是那些具有大量解空間和複雜搜索空間的問題，並藉由歷史列表避免重複計算，以免搜尋停滯不前。

### 概念
Tabu saerch會利用歷史列表儲存過去走訪過的解，並在每次更新後都去查詢列表中是否有過相同解，若有則重新進入Move，沒有則紀錄於列表內，並將當下最佳解紀錄更新;直到ireration達到次數限制才會中止程式，並回傳目前最佳解。
### 執行結果
![Tabu_Search _reslut](https://hackmd.io/_uploads/B1oXlAvRT.png)


### [Github](https://github.com/Grandpawarr/Tabu_Search)


CODE
===
說明
---
- 一開始會隨機生成Deception Problem 初始值
- 進入iteration
>- 由演算法演化下一個問題
>- 驗證其是否合法與在歷史紀錄內
>- 判斷是否為最佳解
- 輸出結果

隨筆
---

- 本次實做OOP概念為架構[參考範例](https://www.codeproject.com/Articles/108830/Inheritance-and-Polymorphism-in-C)
- 希望能建立易於維護且有物件概念的程式碼
- 
main
---
### 1.initial
- 隨機產生初始值，並分析與計算，將結果存於history list中


```Cpp=
tabu_t *T_initial()
{
    /** Initial TabuSearch
     *  1.Allocation memory
     *  2.Initializing tabuSearch value
     *  3.Initializing interface for access to functions
     */
    tabu_t *Tnew = (tabu_t *)malloc(sizeof(tabu_t));
    if (!Tnew)
    {
        perror("message:");
        return 0;
    }

    Tnew->listsize = 0;
    Tnew->showsize = 0;

    Tnew->Move = TabuSearch_Move;
    Tnew->Algo = TabuSearch_Algo;
    Tnew->Addlist = TabuSearch_AddHistoryList;
    Tnew->Display = TabuSearch_Display;

    /** Generate the first Deception Problem
     *  1.allocation memory
     *  2.generate the bit contant
     */
    char *Dstr = (char *)calloc((int)(MaxBit) + 1, sizeof(char));
    if (!Dstr)
    {
        free(Tnew);
        perror("message:");
        return 0;
    }

    for (int i = 0; i < MaxBit; i++)
        Dstr[i] = getRandom(0, 1) + '0';

    /**
     * Add Deception Problem to the history list and the best value
     */
    deception_t *Dnew = D_new(Dstr);
    if (!Dnew)
    {
        free(Tnew);
        free(Dstr);
        perror("message:");
        return 0;
    }
    Tnew->histoylist[0] = *Dnew;

    Tnew->Best = Tnew->histoylist[0];

    /**
     * Print initial value
     */
    printf("The Initial value:\n");
    if (Tnew->histoylist[0].Display(&Tnew->histoylist[0]))
    {
        printf("!!Display!!\n");
    }
    Tnew->showsize++;

    free(Dstr);

    return Tnew;
}
```

### 2.Move
- 過演算法演化下一個問題
- 驗證其是否合法，並判斷此數值是否已在history list中
- 若成功，則存於history list，若list長度超過預設值，則將最早的紀錄刪除

```cpp=
void TabuSearch_Move(tabu_t *head)
{
    /** Generate next Deception Problem via preview
     *
     * str : Next Deception Problem bit
     * isLoop : Break while loop condition
     * isFind : Used to determine whether a is in the Tabu list
     *
     * Generate next Deception Problem via TabuSearch algorithm and
     * confirm whether it is in the Tabu list
     * If in the Tabu list,regerenate
     *
     */
    char *str;
    int isLoop = 1;
    while (isLoop)
    {
        str = head->Algo(head->histoylist[head->listsize].Dbinary);

        int isFound = 0;
        for (int i = 0; i < head->showsize; i++)
        {
            if (strcmp(str, head->histoylist[i].Dbinary) == 0)
            {
                isFound = 1;
                break;
            }
        }
        if (!isFound)
            isLoop = 0;
    }

    /**
     * Create Deception Problem
     * Add Deception Problem to the Tabu list
     */
    deception_t *Dnew = D_new(str);
    if (!Dnew)
    {
        perror("message:");
        return;
    }

    head->Addlist(head, Dnew);
}
```
### 3.main()
```cpp=
int main()
{
    // Random seed
    srand(time(NULL));

    /** Tabu Search Initial
     * Intial Tabu Search variable , function and
     * randomly create the first Deception Problem
     */
    tabu_t *head = T_initial();

    /** Iteration
     * Evolve the next problem by the algorithm
     * End after 1000 iteration
     * @note
     * comment at the bottom and delete it to generate the Tabu Search logs
     */
    for (int i = 1; i < NumberOfIteration; i++)
    {
        //printf("====================\t%d\t==================\n",i);

        head->Move(head);

        /*
        if (head->Display(head))
        { 
            printf("!!ERROR:Display!!\n");
        }
        */
        
    }

    /** Final
     * 1.show the best result for the ultimate Tabu Search
     * 2.pause the screen until enter is pressed
     */
    printf("====================\tFINAL\t==================\n");
    printf("The Best vlaue is : \n");
    if (head->Best.Display(&head->Best))
    {
        printf("!!Display!!\n");
    }

    printf("Press Enter to exit...\n");
    while (getchar() != '\n')
    {
    };

    return 0;
}
```

Tuba Search
---

### 結果顯示
```cpp=
The Initial value:
input:11001010011110101100111100000011110001000111000110, Dvalue:1007620550
====================	FINAL	==================
The Best vlaue is : 
input:10110101111000000101111110010110110001000011100001, Dvalue:2119897313

```
### 0.初值設定
- 歷史表單大小(預設20)
- 迭代次數(預設1000)
```cpp=
#define HistoryListSize 20 //tabu list size
#define NumberOfIteration 1000  //1000
```

### 1.架構

```cpp=
typedef struct TabuSearch
{
    int listsize;                            /**< Tabu list current length */
    int showsize;                            /**< The value of how large an array needs to be displayed */
    deception_t histoylist[HistoryListSize]; /**< Tabu history */
    deception_t Best;                        /**< The Best solution */
    fptrMove Move;                           /**< TabuSearch Move*/
    fptrAlgo Algo;                           /**< TabuSearch Algorithm*/
    fptrAddHistoryList Addlist;              /**< Add Deception Problem to Tabu history*/
    fptrDisplay Display;                     /**< Display the Tabu history and the best solution */

} tabu_t;
```

### 2.Algorithm
- 演算法用使用給與的數值，隨機交換2個不同bit，產生下一個新數值
```cpp=
char *TabuSearch_Algo(char *Dstr)
{
    /**
     * Allocate memory
     */
    char *str = (char *)calloc((int)MaxBit, sizeof(char));
    if (!str)
    {
        perror("message:");
        return 0;
    }

    /** Generate next Deception Problem via preview
     *
     *  1.Copy the previous value
     *  2.Randomly generate two position 
     *   if the bits in both position are the same,do it again
     *  3.Swap two charactor
     * 
     */

    strncpy(str, Dstr, MaxBit);

    int pos1, pos2;
    do
    {
        pos1 = getRandom(0, MaxBit - 1);
        pos2 = getRandom(0, MaxBit - 1);
    } while ((str[pos1] == str[pos2]));

    cSwap(&str[pos1], &str[pos2]);

    return str;
}
```
### 3.Add Problem to history list
- 判斷歷史表單是否滿，若滿則將最舊資料刪除，並將最新資料更新於此
- 最佳價值和上個iteration做比較，若有較好則更新，若不是則維持
```cpp=
void TabuSearch_AddHistoryList(tabu_t *head, deception_t *D)
{
    /** Add new Deception Problem to Tabu history
     * 
     * 1.Determine the Tabu history is full,
     * if fully,update the listsize to -1
     * 2.Add Deception Problem to the Tabu history
     * 3.Update showsize
     * 
    */
    if (head->listsize + 1 > HistoryListSize - 1)
        head->listsize = -1;

    head->histoylist[++head->listsize] = *D;

    if (head->showsize < HistoryListSize)
        head->showsize++;

    /**
     * Judgment Best value
    */
    if (*D->Dvalue > *head->Best.Dvalue)
        head->Best = *D;
}
```
### 4.History list 顯示
```cpp=
int TabuSearch_Display(tabu_t *head)
{
    /**
     * Show history list
     */
    for (int i = 0; i < head->showsize; i++)
    {
        printf("[%2d] ", i);
        if (head->histoylist[i].Display(&head->histoylist[i]))
        {
            printf("!!ERROR:Display!!\n");
            return 1;
        }
    }

    /**
     *  Show Best solution
     */
    printf("Best:");
    if (head->Best.Display(&head->Best))
    {
        printf("!!ERROR:Display!!\n");
        return 1;
    }

    return 0;
}
```

Deception Problem
---
### 公式
- 公式:
>- $f(x)=\mid B2D(s)-2^{n-2} \mid,s_{i}\in\{0,1\},n>2$
- 範例：
>- $f(10100)=\mid (16+4)-2^{2-2} \mid = 12$

### 0.初值設定
- 最大Deception problem bit 數(預設50)
```cpp=
#define MaxBit 50
```
### 1.架構
```cpp=
typedef struct Deception
{
    char* Dbinary;//Deception bit(random configuration)
    long long* Dvalue;//Deception value
    fptrDelete Delete;//destructor
    fpterFunction Function;//calculation function
    fpterDisplay Display;//show input and answer 
    
}deception_t;
```

### 2.建構子
- 辨別使用者輸入是否合法
- 建立個數值的初始值
- 建立個函數指標
```cpp=
deception_t *D_new(const char *const str)
{
    /**
     * str check
     * confirm whether the entered str is legal
     * 1.determines whether the number of characters in a string is within the specified limit
     * 2.determine whether the number of characters in the string is 0/1 or not
     */
    int len = strlen(str);
    if (len != MaxBit * sizeof(char))
    {
        printf("!!Error:enter number must be match %d bits!!\n", (int)MaxBit);
        return 0;
    }
    else
    {
        for (int i = 0; i < len; i++)
        {
            if (*(str + i) != '0' && *(str + i) != '1')
            {
                printf("!!Error:enter char must be 0 or 1!!\n");
                return 0;
            }
        }
    }

    /** Initial Deception Problem
     * 1.allocation memory
     * 2.initializing interface for access to functions
     */
    deception_t *new = (deception_t *)malloc(sizeof(deception_t));
    if (!new)
    {
        perror("message:");
        return 0;
    }

    new->Delete = D_delete;
    new->Function = D_function;
    new->Display = D_display;

    /*
     * Dbinary setting
     * copy str to Dbinary
     */
    new->Dbinary = (char *)calloc(len + 1, sizeof(char));
    if (!new->Dbinary)
    {
        perror("message:");
        return 0;
    }
    strncpy(new->Dbinary, str, len);

    /*
     * setting Dvalue
     * calculation Deception Problem value
     */
    new->Dvalue = malloc(sizeof(int));
    if (!new->Dbinary)
    {
        perror("message:");
        return 0;
    }

    D_function(new);

    return new;
}
```

### 3.解構子
- 刪除動態記憶體
```cpp=
void D_delete(deception_t *const D)
{
    free(D->Dbinary);
    free(D->Dvalue);
    free(D);
}
```
### 4.公式
- 計算二元bit長度
- 將二進位轉換成十進位
- 套入公式取得最終價值
```cpp=
void D_function(deception_t *const D)
{
    /**
     * Calculation the binary number length
     * len : D->Dbinary number length
     * bitLen : Actual D.Dbinary number length
     *
     * Query from the beginning to the end of the string
     * If the beginning is 0, then bitLen -1 until 1 is encountered
     *
     */
    int len = strlen(D->Dbinary);
    int bitLen = len;
    for (int i = 0; i < len; i++)
    {
        if (D->Dbinary[i] == '1')
        {
            i = len + 1;
        }
        bitLen--;
    }
    bitLen++;

    /**
     * Calculation the Decetion Problem value here
     * 1.Convery binary to decimal
     * 2.Function calculation
     */
    long long sum = D_coveryDinaryToDecimal(D->Dbinary, &bitLen);

    sum = (long long)abs(sum - (long long)pow(2, len - 2));

    *D->Dvalue = sum;
}

```

### 5.顯示
- 使用者輸入的二進位
- 公式計算後的價值
```cpp=
int D_display(deception_t *const D)
{
    if (!D)
    {
        perror("message:");
        return 1;
    }

    printf("input:%s, Dvalue:%11lld\n", D->Dbinary, *(D->Dvalue));
    return 0;
}
```

作業規定
===
- 使用語言： C or C++ 
- 欲解決問題： 利用Tabu Search演算法找出deception problem之最佳解(或接近最佳解) ，Tabu Search之iteration次數設定為1000，deception problem 之Bits數量設定為50。
*Tabu Search演算法之作法及定義可於附檔Essentials-metaheuristic-algorithm.pdf內參考。
- 程式規定： 
>- 作業內請包含原始碼、編譯後執行檔及-- readme.txt文字檔，並打包為一份壓縮檔。readme.txt檔案內說明程式的執行方式及記錄執行結果，執行結果請紀錄找到的最佳的解並且截圖，格式不限。
>-	程式碼內請加上註解。
>- Deception Problem是一個最大化問題
>- n為bits數