【文章內(nèi)容簡介】 7 . 9 4 7 5 1 5 8 . 0 7 4 2 8 . 0 7 0 1 8 . 0 0 9 3 7 . 9 4 7 5 1 5 2 3 4 . 6 4 1 . 5 9 1 . 5 4 0 . 7 8 0 . 0 06 0 8 . 6 4 6 2 2 0 9 . 0 3 6 1 8 . 7 4 2 6 8 . 7 0 6 4 8 . 6 4 6 2 2 0 1 0 0 5 . 0 6 4 . 5 1 1 . 1 1 0 . 7 0 0 . 0 07 0 9 . 3 4 5 6 5 3 9 . 6 8 8 3 9 . 5 0 7 4 9 . 4 7 5 1 9 . 3 4 5 8 0 2 1 9 7 . 3 1 3 . 6 7 1 . 7 3 1 . 3 9 0 . 0 08 0 9 . 9 6 8 1 5 2 1 0 . 2 2 7 6 1 0 . 1 8 5 2 1 0 . 1 2 6 4 9 . 9 7 8 2 5 6 1 4 9 1 . 2 2 2 . 6 0 2 . 1 8 1 . 5 9 0 . 1 09 0 1 0 . 5 4 6 0 6 9 1 0 . 8 3 6 4 1 0 . 7 2 6 0 1 0 . 6 8 7 3 1 0 . 5 4 6 0 6 9 5 5 8 8 . 9 5 2 . 7 5 1 . 7 1 1 . 3 4 0 . 0 01 0 0 1 1 . 0 8 2 5 2 7 1 1 . 5 7 4 2 1 1 . 2 8 9 1 1 1 . 2 8 6 5 1 1 . 0 8 5 9 4 8 1 5 0 3 6 . 2 5 4 . 4 4 1 . 8 6 1 . 8 4 0 . 0 8A v e r a g e 3 . 6 1 1 . 4 7 1 . 1 8 0 . 0 120 四 . 圓形 packing問題 ? 測試集 3（不等圓情況）： ? 12個(gè)算例中有 3個(gè)得到新的世界記錄。 R e s u l t s o f B F f o r u n e q u a l c i r c l e i n s t a n c e s o f S t o y a n a n d Y a s k o vI n s t a n c e n tB FS Y 1 3 0 7 . 3 0 7 . 2 1 7 . 2 1 0 7 . 2 1 0 0 7 . 2 7 3 2 7 . 3 1 4 6 1 1 4 8 0S Y 2 2 0 6 . 3 4 6 . 2 7 6 . 4 5 0 6 . 3 3 9 3 6 . 3 1 2 5 6 . 3 3 9 9 3 0 0 3S Y 3 2 5 6 . 4 5 6 . 4 2 6 . 5 6 0 6 . 4 8 4 2 6 . 4 6 2 9 6 . 4 5 7 3 3 8 6 5S Y 4 3 5 9 . 1 6 9 . 0 5 9 . 3 5 0 9 . 2 7 4 5 9 . 1 6 3 3 8 . 9 9 8 2 4 8 4S Y 5 1 0 0 1 3 . 2 0 1 3 . 1 7 1 3 . 4 0 0 1 3 . 2 7 4 2 1 3 . 1 5 2 3 1 3 . 3 9 0 3 1 8 6 5S Y 6 1 0 0 1 4 . 9 5 1 4 . 9 4 1 5 . 2 1 0 1 5 . 1 4 7 6 1 4 . 9 8 3 2 1 5 . 2 3 1 1 6 8 7 5S Y 1 4 1 1 0 — — 1 5 . 0 0 9 1 4 . 8 3 5 1 1 4 . 4 7 8 0 1 4 . 8 9 7 2 5 9 3 2S Y 5 6 2 0 0 — — 2 0 . 3 0 3 2 0 . 2 0 2 2 1 9 . 7 8 1 7 2 0 . 2 2 3 6 1 0 6 2 6S Y 1 0 3 0 0 — — 2 3 . 1 9 9 2 2 . 9 0 7 0 2 2 . 6 1 3 3 2 2 . 9 5 1 2 4 4 4 4 6S Y 2 0 2 0 0 — — 2 0 . 2 1 0 1 9 . 8 0 2 0 1 9 . 5 5 3 1 1 9 . 3 4 7 8 9 8 7 9S Y 3 0 2 5 0 — — 2 0 . 5 9 3 2 0 . 3 0 6 0 2 0 . 0 6 4 5 2 0 . 3 7 7 4 2 3 4 7 1S Y 4 0 3 5 0 — — 2 9 . 1 7 1 2 8 . 8 8 8 9 2 8 . 4 2 3 8 2 8 . 9 2 1 5 3 4 6 7 81 . 00Ar1 . 50Ar20H Mr0B Sr0B Fr10H Mr21 3. 圓形 packing問題 ? 350個(gè)圓的布局結(jié)果。 22 五、禁忌搜索算法 ? （一）禁忌搜索 （ Tabu Search, 或 Taboo Search, 簡記為 TS）由 Glover（ 1986年）提出。禁忌搜索最重要的思想是：標(biāo)記已搜索到的局部最優(yōu)的一些對象，并在進(jìn)一步的迭代搜索中盡量避開這些對象（而不是絕對禁止），從而保證對不同的有效搜索途徑的探索。 23 五、禁忌搜索算法 ? 基本過程是 ：給定一個(gè)當(dāng)前解（初始解）和一種鄰域，然后在當(dāng)前解的鄰域中確定若干候選解；若最佳候選解對應(yīng)的目標(biāo)值優(yōu)于“ best so far”狀態(tài)，則忽視其禁忌特性，用其替換當(dāng)前解和“ best so far”狀態(tài)，并將相應(yīng)的對象加入禁忌表，同時(shí)修改禁忌表中各對象的任期；若不存在上述候選解，則在候選解中選擇非禁忌的最佳狀態(tài)為新的當(dāng)前解，而無視它與當(dāng)前解的優(yōu)劣，同時(shí)將相應(yīng)的對象加入禁忌表，并修改禁忌表中各對象的任期；如此重復(fù)上述迭代搜索過程，直到滿足停止準(zhǔn)則。 24 五、禁忌搜索算法 ? （二）簡單禁忌搜索算法的步驟： （ 1）給定算法參數(shù)，隨機(jī)產(chǎn)生 初始解 x，置 禁忌表 為空。 （ 2）判斷算法 終止條件 是否滿足？若是，則結(jié)束算法并輸出優(yōu)化結(jié)果；否則，繼續(xù)以下步驟。 （ 3）利用當(dāng)前解 x的 鄰域函數(shù) 產(chǎn)生其所有（或若干）鄰域解，并從中確定若干 候選解 。 （ 4）對候選解判斷 藐視準(zhǔn)則 是否滿足？若成立，則用滿足藐視準(zhǔn)則的最佳狀態(tài) y替換 x成為新的當(dāng)前解，并用與 y對應(yīng)的 禁忌對象 替換最早進(jìn)入禁忌表的禁忌對象，同時(shí)用 y替換“ best so far”狀態(tài)，并修改禁忌表中各對象的任期，然后轉(zhuǎn)步驟（ 6）；否則，繼續(xù)以下步驟。 （ 5）判斷候選解對應(yīng)的各狀態(tài)的禁忌屬性，選擇候選解集中非禁忌對象對應(yīng)的最佳狀態(tài)為新的當(dāng)前解，同時(shí)修改禁忌表中各對象的任期。 （ 6）轉(zhuǎn)步驟（ 2）。 25 五、禁忌搜索算法 ? （三）禁忌搜索的關(guān)鍵參數(shù)和操作 （ 1）初始解和適配值函數(shù)； （ 2）鄰域結(jié)構(gòu)和禁忌對象； （ 3）候選解選擇； （ 4）禁忌表及其長度； （ 5）藐視準(zhǔn)則； （ 6）其中搜索和分散搜索策略； （ 7）終止準(zhǔn)則。 其中，鄰域函數(shù)是基于局部鄰域搜索的思想，用于實(shí)現(xiàn)鄰域搜索；禁忌表和禁忌對象的設(shè)置，體現(xiàn)了算法避免迂回搜索的特點(diǎn)；藐視準(zhǔn)則，則是對優(yōu)良狀態(tài)的獎(jiǎng)勵(lì)，它是對禁忌策略的一種放松。 26 五、禁忌搜索算法 ? 適配值函數(shù) 可以將目標(biāo)函數(shù)直接作為適配值函數(shù) 。也可以將目標(biāo)函數(shù)的變形作為適配值函數(shù)，譬如對極小值