【正文】 第七章 高級搜索 主要內(nèi)容 ? 局部搜索方法 ? 模擬退火算法 ? 遺傳算法 基本概念 優(yōu)化與組合優(yōu)化問題 ? 很多問題屬于優(yōu)化問題，或者可以轉(zhuǎn)化為優(yōu)化問題 ? 如 TSP問題，皇后問題 優(yōu)化問題的描述 ? 設(shè) x是決策變量， D是 x的定義域， f(x)是指標(biāo)函數(shù)， g(x)是約束條件集合。則優(yōu)化問題可以表示為，求解滿足 g(x)的 f(x)最小值問題。 ? 如果在定義域 D上，滿足條件 g(x)的解是有限的，則優(yōu)化問題稱為組合優(yōu)化問題。 ? ?)(|)(m in xgxfDx ?算法的時(shí)間復(fù)雜度 ? 對于組合優(yōu)化問題，由于其可能的解是有限的，當(dāng)問題的規(guī)模比較小時(shí)，總可以通過枚舉的方法獲得問題的最優(yōu)解，但當(dāng)問題的規(guī)模比較大時(shí)，就難于求解了。 ? 常用的算法復(fù)雜度函數(shù) )(),!(),(),2(),(),l o g(),(),( l o g l o g2 nnn nOnOnOOnOnnOnOnO 輸入量 n 復(fù)雜性函數(shù) 10 20 30 40 100 n 10ns 20ns 30ns 40ns 100ns nlogn 10ns 200ns n2 100ns 400ns 900ns 10us 2n n! 1013世紀(jì) 1029世紀(jì) 10139世紀(jì) 時(shí)間復(fù)雜性函數(shù)比較（ 10億次 /秒） 一些難的組合優(yōu)化問題 ? 旅行商問題 ? 背包問題 ? 裝箱問題 ? ... ? 尋求在可以接受的時(shí)間內(nèi)得到滿意解的方法 鄰域的概念 ? 鄰域，簡單的說就是一個(gè)點(diǎn)附近的其他點(diǎn)的集合。 ? 在距離空間，鄰域就是以某一點(diǎn)為中心的圓。 ? 組合優(yōu)化問題的定義： ? 設(shè) D是問題的定義域，若存在一個(gè)映射 N，使得： 則稱 N(S)為 S的鄰域。 DSNDSN 2)(: ???例：皇后問題 ? S={Si}表示一個(gè)可能解，其中 Si表示在第i行，第 Si列有一個(gè)皇后。 ? 如四皇后問題的一個(gè)解： S=(2, 4, 1, 3) Q Q Q Q ? 定義映射 N為棋盤上任意兩個(gè)皇后的所在行或列進(jìn)行交換，即 S中任意兩個(gè)元素交換位置。 ? 例：當(dāng) S = (2, 4, 1, 3)時(shí)，其鄰域?yàn)椋? ? N(S) = {(4, 2, 1, 3), (1, 4, 2, 3), (3, 4, 1, 2), (2, 1, 4, 3), (2, 3, 1, 4), (2, 4, 3, 1)} 例：旅行商問題 ? 用一個(gè)城市的序列表示一個(gè)可能的解。 ? 通過交換兩個(gè)城市的位置獲取 S的鄰居 ? 例：簡單交換方法 設(shè) S = (x1, x2, …x i1, xi, xi+1, …, x j1, xj, xj+1, …, x n) 則通過交換 xi和 xj兩個(gè)城市的位置可以得到 S的一個(gè)鄰居： S39。 = (x1, x2, …x i1, xj, xi+1, …, x j1, xi, xj+1, …, x n) x1 x2 xn xj+1 xj xj1 xi1 xi xi+1 x1 x2 xn xj+1 xj xj1 xi1 xi xi+1 ? 例：逆序交換方法 設(shè) xi、 xj是選取的兩個(gè)城市 ， 所謂的逆序交換方式是指 ， 通過逆轉(zhuǎn) xi、 xj兩個(gè)城市之間的城市次序來得到 S的鄰居 。 設(shè)： S = (x1, x2, … xi1, xi, xi+1, … , xj1, xj, xj+1, … , xn) 則： S39。 = (x1, x2, … xi1, xi, xj1, x j2… , xi+1, xj, xj+1, … , xn) x1 x2 xn xj+1 xj xj1 xi1 xi xi+1 x1 x2 xn xj+1 xj xj1 xi1 xi xi+1 局部搜索算法 ? 基本思想：在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。 ? 目標(biāo)可以是最大值，也可以是最小值。 ? 在后面的介紹中，如果沒有特殊說明，均假定是最小值。 局部搜索算法 （ Local Search） 1， 隨機(jī)的選擇一個(gè)初始的可能解 x0∈ D， xb=x0，P=N(xb)； 2， 如果不滿足結(jié)束條件 ， 則 3， Begin 4， 選擇 P的一個(gè)子集 P39。， xn為 P39。中的最優(yōu)解 5， 如果 f(xn) f(xb)， 則 xb ＝ xn， P = N(xb)， 轉(zhuǎn) 2； f(x)為指標(biāo)函數(shù) 。 6， 否則 P = P – P39。， 轉(zhuǎn) 2。 7， End 8， 輸出計(jì)算結(jié)果 9， 結(jié)束 例： 5城市旅行商問題 ● ● ● ● ● A B C D E 7 13 6 10 7 10 10 9 6 5 設(shè)初始的可能解： x0 = (a, b, c, d, e) f(xb) = f(x0) = 38 通過交換兩個(gè)城市獲得領(lǐng)域 P = {(a, c, b, d, e), (a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 設(shè)每次隨機(jī)從 P中選擇一個(gè)鄰居。 第一次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, c, b, d, e), f(xn) = 42, f(xn) f(xb), P = P – {xn} = {(a, d, c, b, e), (a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第二次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, d, c, b, e), f(xn) = 45, f(xn) f(xb), P = P – {xn} = {(a, e, c, d, b), (a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第三次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, e, c, d, b), f(xn) = 44, f(xn) f(xb), P = P – {xn} = {(a, b, d, c, e), (a, b, e, d, c), (a, b, c, e, d)} 第四次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, d, c, e), f(xn) = 44, f(xn) f(xb), P = P – {xn} = {(a, b, e, d, c), (a, b, c, e, d)} 第五次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, e, d, c), f(xn) = 34, f(xn) f(xb), xb = (a, b, e, d, c), P = {(a, e, b, d, c), (a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第六次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, e, b, d, c), f(xn) = 44, f(xn) f(xb), P = P – {xn} = {(a, d, e, b, c), (a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第七次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, d, e, b, c), f(xn) = 39, f(xn) f(xb), P = P – {xn} = {(a, c, e, d, b), (a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第八次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, c, e, d, b), f(xn) = 38, f(xn) f(xb), P = P – {xn} = {(a, b, d, e, c), (a, b, c, d, e), (a, b, e, c, d)} 第九次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, d, e, c), f(xn) = 38, f(xn) f(xb), P = P – {xn} = {(a, b, c, d, e), (a, b, e, c, d)} 第十次循環(huán) 從 P中選擇一個(gè)元素， 假設(shè) xn = (a, b, c, d, e), f(xn) = 38, f(xn) f(xb), P = P – {xn} = {(a, b, e, c, d)} 第十一次循環(huán) 從 P中選擇一個(gè)元素 ， 假設(shè) xn = (a, b, e, c, d), f(xn) = 41, f(xn) f(xb), P = P – {xn} = {} P等于空 ， 算法結(jié)束 ， 得到結(jié)果為 xb = (a, b, e, d, c), f(xb) = 34。 存在的問題 ? 局部最優(yōu)問題 解決方法 ? 每次并不一定選擇鄰域內(nèi)最優(yōu)的點(diǎn)，而是依據(jù)一定的概率，從鄰域內(nèi)選擇一個(gè)點(diǎn)，指標(biāo)函數(shù)優(yōu)的點(diǎn)，被選中的概率比較大，而指標(biāo)函數(shù)差的點(diǎn)，被選中的概率比較小。 選擇概率的計(jì)算 ? 設(shè)求最大值： ???)(m ax)()()(xNxjiijxfxfxP選擇概率的計(jì)算 ? 當(dāng)求最小值時(shí)： ? ?)(11)(1))(1()(1)(m ax)(m axm axm i nixNxjiixPxNxPxPxPj????????局部搜索算法 1（ Local Search 1） 1， 隨機(jī)的選擇一個(gè)初始的可能解 x0∈ D， xb=x0，P=N(xb) 2， 如果不滿足結(jié)束條件 ， 則 3， Begin 4， 對于所有的 x∈ P