自適應搜尋策略

以組合最佳化中的著名難題TSP (traveling salesman prob-lem)為例，提出了一種新穎的自適應搜尋策略，通過鄰域和候選集的相互配合，動態地調整候選集中分別用於集中性搜尋與多樣性搜尋的元素個數，較好地解決了集中性與多樣性的衝突問題。

基本介紹

• 中文名：自適應搜尋策略
• 外文名：Adaptive search strategy
• 定義：解決集中性與多樣性的衝突問題
• 提出：組合最佳化的著名難題TSP
• 分類：領域和候選集
• 套用學科：計算機技術

鄰域控制策略

將鄰域分為兩部分，前半部分元素稱為集中性元素，用於集中性搜尋;後半部分元素稱為多樣性元素，用於多樣性搜尋。

對於集中性元素要少而精，主要是質量要高，所以用插入法產生，以TSP為例，設城市規模為n，其算法描述如下:

1、任取一城市，插入到餘下的n一1個城市序列中，取巡迴路徑長度增加最短的一個序列作為一個集中性元素;

2、分別取下一個城市，重複上述過程，直至n個集中性元素生成完畢，對於多樣性元素要多而廣，儘可能是以前未曾搜尋過的區域，所以用隨機法產生，即隨機交換兩個城市的位置。

候選集控制策略

將候選集中的元素也分為兩部分，前半部分從鄰域的前部分中選評價值最佳的元素組成，稱為集中性元素，用於集中性搜尋;後半部分則從鄰域的後半部分元素中隨機選取組成，稱為多樣性元素，用於多樣性搜尋。程式運行時，集中性元素和多樣性元素的個數根據搜尋過程中解的質量而動態地變化。設候選集長度記為CL (candidate length)，候選集中集中性元素和多樣性元素的分界點長度記為DL(division length)，即前1 ~ DL個元素為集中性元素，後DL+1~CL個元素為多樣性元素。

算法疊代之前，首先進行參數設定，取DL =CL/2，即候選集中集中性元素和多樣性元素各占一半。在疊代搜尋過程中，DL按如下規則動態變化:

若本次疊代搜尋到的當前局部最優解好於前一步疊代所得的局部最優解，則DL =DL+1;

若本次疊代搜尋到的當前局部最優解等於或劣於前一步疊代所得的局部最優解，則DL =DL一1。

為確保搜尋的集中性，當DL=1時，則不再減小;為確保搜尋的多樣性，當DL=CL一1時，則不再增大即候選集在疊代過程中始終同時包括有集中性元素和多樣性元素，且至少1個。

策略的優點

DL按上述規則動態地變化使得:當解的質量有提高時，則候選集中的集中性元素增多，即進行集中性搜尋的機率增大，相應地，多樣性搜尋的機率降低;反之，當解的質量沒有提高時，則候選集中的多樣性元素增多，即進行多樣性搜尋的機率增大，相應地，集中性搜尋的機率減小這樣，TS就能根據搜尋進程中解的質量好壞而自動地進行集中性搜尋或多樣性搜尋，較好地解決了集中性搜尋與多樣性搜尋之間的矛盾。