局部搜索算法详解

转载声明：这篇文章是从网上好多文章总结摘抄来的，所以也不算是我写的，没法标出原转载网址；

通常考察一个算法的性能通常用局部搜索能力和全局收敛能力这两个指标。局部搜索是指能够无穷接近最优解的能力，而全局收敛能力是指找到全局最优解所在大致位置的能力。局部搜索能力和全局搜索能力，缺一不可。向最优解的导向，对于任何智能算法的性能都是很重要的。

定义：

描述算法时需用到领域的概念，所谓领域，简单的说即是给定点附近其他点的集合。在距离空间中，领域一般被定义为以给定点为圆心的一个圆；而在组合优化问题中，领域一般定义为由给定转化规则对给定的问题域上每结点进行转化所得到的问题域上结点的集合。公式描述如下：

设D为问题定义域，若存在一映射N，使得：

N:S∈D→N(S)∈2^D

则称N(S)为N的领域，A∈2^D为N的邻居。

局部搜索（Local Search）的一般过程是：

4, IF h(n) y == N - 1))) // 同在副对角线上 return true; return (pQueen_1->x == pQueen_2->x || pQueen_1->y == pQueen_2->y)? true:false; // 判定同行同列 } //////////////////////////////////////////////////////////////////////////////////// unsigned CountOfConflict(pQUEEN pN_Queen, unsigned n) { unsigned i, j, Count = 0; for (i = 0; i < n - 1; i++) for (j = i + 1; j < n; j++) if (isConflict(pN_Queen + i, pN_Queen + j)) Count++; return Count; } /////////////////////////////////////////////////////////////////////////////////// bool ChangeTwoQueen(GRID ChessBroad[][N], pQUEEN pN_Queen, unsigned n) { int tmp, h1, h2; unsigned i, j, Count = 0; // 冲突数目 bool *isavH_1, *isavH_2; // 指向一维数组，用来标识两层循环中可用的皇后 isavH_1 = new bool[n]; isavH_2 = new bool[n]; for (i = 0; i < n; i++) isavH_1[i] = isavH_2[i] = true; // 初始均可用 Count = CountOfConflict(pN_Queen, n); // 两层循环产生从n个元素中选择个的组合数 for (i = 0; i < n - 1; i++) { //随机选择一个可用的皇后作为第一组合数h1 while (1) { h1 = rand() % n; if (isavH_1[h1]) { isavH_1[h1] = false; // 第二组合数从尚未选为第一组合数集合中选择 for (j = 0; j < n; j++) isavH_2[j] = isavH_1[j]; break; } } for (j = i + 1; j < n; j++) { //随机选择一个可用的皇后作为第二组合数h2 while (1) { h2 = rand() % n; if (isavH_2[h2]) { isavH_2[h2] = false; break; } } // 交换标号为h1，h2皇后的x坐标 tmp = pN_Queen[h1].x; pN_Queen[h1].x = pN_Queen[h2].x; pN_Queen[h2].x = tmp; if (Count > CountOfConflict(pN_Queen, n)) { // 更改相应的棋格 ChessBroad[pN_Queen[h2].x][pN_Queen[h1].y].pQueen = NULL; ChessBroad[pN_Queen[h1].x][pN_Queen[h2].y].pQueen = NULL; ChessBroad[pN_Queen[h1].x][pN_Queen[h1].y].pQueen = pN_Queen + h1; ChessBroad[pN_Queen[h2].x][pN_Queen[h2].y].pQueen = pN_Queen + h2; return true; } else { tmp = pN_Queen[h1].x; pN_Queen[h1].x = pN_Queen[h2].x; pN_Queen[h2].x = tmp; } // 交换标号为h1、h2皇后的y坐标 tmp = pN_Queen[h1].y; pN_Queen[h1].y = pN_Queen[h2].y; pN_Queen[h2].y = tmp; if (Count > CountOfConflict(pN_Queen, n)) { // 更改相应的棋格 ChessBroad[pN_Queen[h1].x][pN_Queen[h2].y].pQueen = NULL; ChessBroad[pN_Queen[h2].x][pN_Queen[h1].y].pQueen = NULL; ChessBroad[pN_Queen[h1].x][pN_Queen[h1].y].pQueen = pN_Queen + h1; ChessBroad[pN_Queen[h2].x][pN_Queen[h2].y].pQueen = pN_Queen + h2; return true; } else { tmp = pN_Queen[h1].y; pN_Queen[h1].y = pN_Queen[h2].y; pN_Queen[h2].y = tmp; } } } // 不存在这样的交换则返回false return false; } //////////////////////////////////////////////////////////////////////////////////// void PrintChessBroad(GRID ppChessBroad[][N], unsigned n) { unsigned i, j; printf("\n"); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (ppChessBroad[i][j].pQueen == NULL) printf("*\t"); else printf("H\t"); } printf("\n\n\n"); } } //////////////////////////////////////////////////////////////////////////////////// int _tmain(int argc, _TCHAR* argv[]) { GRID ChessBroad[N][N]; QUEEN nQueen[N]; while (1) { InitChessBroad(ChessBroad, nQueen, N); while (1) { // 完成皇后的布局 if (0 == CountOfConflict(nQueen, N)) { PrintChessBroad(ChessBroad, N); return 1; } if (!ChangeTwoQueen(ChessBroad, nQueen, N)) break; } } return 0; }