[科普中国]-自适应搜索策略

邻域控制策略

将邻域分为两部分，前半部分元素称为集中性元素，用于集中性搜索;后半部分元素称为多样性元素，用于多样性搜索。

对于集中性元素要少而精，主要是质量要高，所以用插入法产生，以TSP为例，设城市规模为n，其算法描述如下:

1、任取一城市，插入到余下的n一1个城市序列中，取巡回路径长度增加最短的一个序列作为一个集中性元素;

2、分别取下一个城市，重复上述过程，直至n个集中性元素生成完毕，对于多样性元素要多而广，尽可能是以前未曾搜索过的区域，所以用随机法产生，即随机交换两个城市的位置。1

候选集控制策略将候选集中的元素也分为两部分，前半部分从邻域的前部分中选评价值最佳的元素组成，称为集中性元素，用于集中性搜索;后半部分则从邻域的后半部分元素中随机选取组成，称为多样性元素，用于多样性搜索。程序运行时，集中性元素和多样性元素的个数根据搜索过程中解的质量而动态地变化。设候选集长度记为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个。1

策略的优点DL按上述规则动态地变化使得:当解的质量有提高时，则候选集中的集中性元素增多，即进行集中性搜索的概率增大，相应地，多样性搜索的概率降低;反之，当解的质量没有提高时，则候选集中的多样性元素增多，即进行多样性搜索的概率增大，相应地，集中性搜索的概率减小这样，TS就能根据搜索进程中解的质量好坏而自动地进行集中性搜索或多样性搜索，较好地解决了集中性搜索与多样性搜索之间的矛盾。1