介紹
===
### 目的
Tabu search適合處理組合最佳化的問題，特別是那些具有大量解空間和複雜搜索空間的問題，並藉由歷史列表避免重複計算，以免搜尋停滯不前。
### 概念
Tabu saerch會利用歷史列表儲存過去走訪過的解，並在每次更新後都去查詢列表中是否有過相同解，若有則重新進入Move，沒有則紀錄於列表內，並將當下最佳解紀錄更新;直到ireration達到次數限制才會中止程式，並回傳目前最佳解。
### 執行結果
### [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數
Sign in with Wallet
Connect another wallet