圖的最大二等分問(wèn)題的新型條件梯度算法.pdf

2 0 1 4 年 3月 高等學(xué)校 計(jì)算數(shù)學(xué) 學(xué)報(bào) 第 3 6卷第 1期 圖的最大二等分問(wèn)題的新型條件梯度算法 張芳 陳志平 西安交通大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院計(jì)算科學(xué)系 西安 7 1 0 0 4 9 N EW CONDI TI ON AL GRA DI ENT ALG ORI THM S FOR TH E GRAPH M AX BI S ECTI ON PROBLEM Zh a ng Fa n g Ch e n Zh i p i n g D e p a r t me n t o f C o mp u t i n g S c i e n c e S c h o o l o f Ma t h e ma t i c s a n d S t a t i s t i c s Xi a n J i a o t o n g U n i v e r s i t y X i a n 7 1 0 0 4 9 A bs t r a c t Due t o i t s wi d e a p pl i c a t i on a r e a s a nd i n t r a c t a b i l i t y t he g r a ph ma x bi s e c t i o n Dr o bl e m i s no w a ho t t o p i c i n c o mbi na t o r i a l o pt i m i z a t i o n I n t hi s pa pe r ne w c on t i nu a t i o n r e l a xa t i o n mod e l s f o r t he g r a ph ma x bi s e c t i o n p r o b l e m ha v e be e n p r o po s e d b y u s i n g t h e a d v a n t a g e s o f t h e s e m i de fin i t e p r o g r a mm i ng r e l a xa t i o n an d t h e r a nk t wo r e l a xa t i o n Af t e r s t ud y i ng t h e o r e t i c a l p r o pe r t i e s of o u r c o n t i n ua t i on r e l a xa t i o n mo de l s t wo d i fi e r e nt de s c e n t d i r e c t i o ns a r e c o n s t r u c t e d de r i v e d f r o m whi c h a r e t wo n e w c o nd i t i o n a l g r a d i e n t a l g o r i t h m s f o r s o l v i n g t h e g r a p h m a x bi s e c t i o n Dr o b l e m W e ha v e e s t a b l i s h e d t h e c o n v e r g e n c e a nd fin i t e t e r mi n a t i o n p r o pe r t i e s for t h e pr o po s e d a l g o r i t h ms Ext e ns i v e nu me r i c a l e x pe r i me n t s s ho w t h a t c o mpa r e d wi t h e xi s t i ng a l g o r i t h ms o ur n e w a l g o r i t h ms c a n n o t o nl y q ui c k l y fin d be t t e r a pp r o x i m a t e s ol ut i o n s b ut a l s o e ffi c i e nt l y s o l v e t he l a r g e s c a l e g r a ph ma x bi s e c t i o n p r o bl e ms K e v W O r ds g r a p h ma x bi s e c t i o n p r o bl e m s e mi d e fi ni t e pr og r a ms c o n di t i o na l g r a d i e nt a l g o r i t hm d e s c e n t di r e c t i o n c o n v e x c o n s t r a i n t AMS 2 0 0 0 s u b j e c t c l a s s i fi c a t i o n s 9 0 C2 7 9 0 C 5 9 中圖法分類(lèi)號(hào)0 2 2 1 2 國(guó)家自 然科學(xué)基金 7 0 9 7 1 1 0 9 7 1 3 7 1 1 5 2 和西安交通大學(xué)基本科研業(yè)務(wù)費(fèi)自由 探索類(lèi)項(xiàng)目 0 8 1 4 3 0 3 2 資助 收稿日期 2 0 1 0 0 2 0 9 2 0 1 4 年 3月 高 等 學(xué) 校 計(jì) 算 數(shù) 學(xué) 學(xué) 報(bào) 8 7 1 引 言 給定無(wú)向圖 G E 其中 V 1 2 幾 為 G的節(jié)點(diǎn)集合 E為 G的邊集合 如果 i J E 定義在此邊上的非負(fù)權(quán)值為 w i j w j i 否則 wi j 0 對(duì)稱(chēng)的權(quán)值矩陣記 為 W Wi 圖的最大二等分 問(wèn)題就是把給定的無(wú)向賦權(quán) 圖 G的節(jié)點(diǎn)分成個(gè)數(shù)相 同 的兩部分 s和 雪 s 這意味著無(wú)向圖 G節(jié)點(diǎn)的個(gè)數(shù) 仃必須是偶數(shù) 使得兩節(jié)點(diǎn)分別 在 s 雪中的邊 的權(quán)值 w i j的總和最大 即 圖的最大二等分問(wèn)題是組合優(yōu)化中一類(lèi)非常重要的問(wèn)題 它在網(wǎng)絡(luò)優(yōu)化 工程技術(shù)中 有著廣泛的應(yīng)用 許多 網(wǎng)絡(luò)問(wèn)題都可以轉(zhuǎn)化為圖的最大二等分問(wèn)題 例如超大規(guī)模集成 電 路的設(shè)計(jì)等 由于該問(wèn)題是 NP h a r d問(wèn)題 很難獲得其精確解 近年來(lái) 人們已經(jīng)提出了求 解該 問(wèn)題 的各種啟發(fā)式近似算法 其中松馳算法就是非常典型的一種 F r i e z e和 J e r r u m 通過(guò)推廣 Go e ma n s 和 Wi l l i ms o n 的半定規(guī)劃 S DP 松弛以及 O 8 7 8 5 7近似算法 給出 了圖的最大二等分 問(wèn)題的 0 6 5 1近似算法 Y e 3 改進(jìn)了 0 6 5 1算法 得到圖的最大二等分 問(wèn)題的 0 6 9 9近似算法 H a l p e r i n和 Z w i c h 利用三角不等式 并基于更強(qiáng)的 S DP松弛 將近似 比進(jìn)一步提高到 0 7 0 1 6 F e i g e 和 L a n g b e r g 基于 S DP的取整技巧 提出了隨機(jī)投 影隨機(jī)取整的方法 將近似 比提高到 0 7 0 2 8 同時(shí) 利用 S DP松弛解給出了一個(gè)較好的上 界 在此基礎(chǔ)上利用隨機(jī)算法得到了較好的近似解 該算法對(duì)于圖的節(jié)點(diǎn)數(shù) 目較小時(shí)很有 效 但 隨著圖的節(jié)點(diǎn)數(shù) 目的增 加 轉(zhuǎn)化所得 的 S D P松弛模型變量的數(shù) 目會(huì)呈幾何級(jí)數(shù)增 加 這增加了問(wèn)題求解的難度 B u r e r Mo n t e ir o和 Z h a n g 提出了求解圖的最大割問(wèn)題的秩二松弛算法 6 并由此得 到圖的最大二等分問(wèn)題的秩二松弛方法 該方法的優(yōu)點(diǎn)是所構(gòu)造秩二松弛模型變量的數(shù) 目沒(méi)有增加 有利于求解大規(guī)模問(wèn)題 但是 秩二松弛模型導(dǎo)致其 目標(biāo)函數(shù)非凸 不能保證 獲得原問(wèn)題最優(yōu)值的一個(gè)上界 通常是通過(guò)增加迭代次數(shù)和對(duì)初始值的擾動(dòng)來(lái)提高 目標(biāo) 函數(shù)值 本文在吸取半定規(guī)劃松弛及秩二松弛方法的優(yōu)點(diǎn) 克服其缺點(diǎn)的基礎(chǔ)上 將圖的最大 二等分 問(wèn)題松弛為連續(xù)化的優(yōu)化 問(wèn)題 該連續(xù)化方法不僅沒(méi)有增加問(wèn)題的維數(shù) 而且保持 了目標(biāo)函數(shù)良好的分析性質(zhì) 基于所論證的該連續(xù)化模型的特征 本文給出了兩種不同下 降方向的構(gòu)造方法 得到了求解圖的最大二等分問(wèn)題的兩種不同形式的條件梯度算法 分 析了算法的收斂性和有限步終止性 并進(jìn)行了大量的數(shù)值實(shí)驗(yàn) 數(shù)值試驗(yàn)結(jié)果表明 該算 法能在較短時(shí)間內(nèi)找到圖的最大二等分問(wèn)題更好的近似解 而且可有效求解大規(guī)模 問(wèn)題 具體地 我們引入二值變量 X i 1 2 n 若 i S 令 X t 若 i s 令 U S S X a 張芳等 圖的最大二等分問(wèn)題的新型條件梯度算法 第 1期 X i 一1 則 圖的最 大二 等分 l 司題 司以表述 為 m a x叫 w ij 1 s t e Tz 0 MB 1 X l i 1 2 凡 其中 X X l X 2 X n e 1 1 1 T R 我們注意到 m a x Z l w 1 X i X j m a x 一 W ij X i X j 一 m i n 若 記 它 僅 與 權(quán) 值 矩 陣 有 關(guān) 當(dāng) 給 定 時(shí) 為 正 常 數(shù) 于 是 我 們 可 以 i J 將模型 MB1 轉(zhuǎn)化為如下與之等價(jià)的最小值問(wèn)題 叫 T e T 0 MB 2 X 1 i 1 2 n 對(duì)模型 MB 2 進(jìn)行連續(xù)化松弛 記約束區(qū)域 D le X 0 一 1 X i 1 i 1 2 禮 得到如下模型 叫 MB 3 如果忽略掉模型 MB 3 中的等式約束 E T x 0 記約束區(qū)域 D l 一1 X i 1 i 1 2 禮 則得到如下僅有上下界約束的連續(xù)化松弛模型 叫 丟 M B 4 本文中 我們將通過(guò)求解模型 MB 3 和 MB 4 找到圖的最大二等分問(wèn)題的近似解 2 條件梯度算法 熟知 負(fù)梯度方 向是函數(shù)下降最快的方 向 但對(duì)于約束優(yōu)化 問(wèn)題 若取 負(fù)梯度方 向作 為搜索方向 就可能越出約束區(qū)域 因此不能直接取負(fù)梯度方向?yàn)樗阉鞣较?必須考慮約 2 0 1 4 年 3月 高 等 學(xué) 校 計(jì) 算 數(shù) 學(xué) 學(xué) 報(bào) 束條件的限制 條件梯度算法就是在求解無(wú)約束優(yōu)化問(wèn)題的最速下降法的基礎(chǔ)上提出來(lái) 的 7 為導(dǎo)出求解圖的最大二等分問(wèn)題的有效條件梯度算法 下面我們首先分析連續(xù)化松 弛模型 MB 3 和 MB 4 的性質(zhì) 引理 1 模型 MB 3 中的約束區(qū)域 D x le X 0 一 1 1 i 1 2 禮 是 緊凸集 證明對(duì)于任意的 X Y D及 0 1 有 一 1 1 1 Y 1 因此有 1 z 1 一 1 即 1 一 D 又 e t a 0 是線(xiàn)性函數(shù) 所以 D為凸集 易知 D為緊集 引理 2 模型 MB 3 中的目標(biāo)函數(shù)的梯度 W 是 L i p s c h i t z 連續(xù)的 即存在常數(shù) L 0 使得對(duì)于任意的 Y D 都有 ll i t 一W Jl L ll Y ll 成立 證明 Il W 一W lI l W X W Y II ll WT Y II 0 根 據(jù) 條 件 梯 度 算 法 的 步5 有 k 去 又由i o 的 確 定 方 法 易 知 當(dāng) 時(shí)式 2 1 是不成立的 因此必有 1 W x P 2 i o 1 一 由上式及定理 1的結(jié)論 2 有 1 一 f 2 2 1 2 0 1 4 年 3月 高 等 學(xué) 校 計(jì) 算 數(shù) 學(xué) 學(xué) 報(bào) 因?yàn)?z x D D是緊凸集 故有 ll P lI 1l z x 一 C 其中 C 是正常數(shù) 利用式 2 2 從 2 1 可以得到 w x k 1 一 p 一叫 z 叫 p 叫 p p z 2 3 8 L l l P l I 8 L c 將不等式 2 3 兩邊對(duì)所有的 0 1 2 m一1 相加得到 m一 1 w z TM 一 一 叫 p 2 4 因?yàn)榻?在緊凸集D上連續(xù) 故叫 在D上能達(dá)到最小值 記 叫 叫 z m i n z 因此 不等式 2 4 可以寫(xiě)為 m 一 1 叫 P 8 L c 2 z 一 w x 8 L c 一 叫 k O 其 中 P 是 正 項(xiàng) 級(jí) 數(shù) 部 分 和 數(shù) 列 有 上 界 故 該 級(jí) 數(shù) 收 斂 根 據(jù) 收 斂 級(jí) 數(shù) 的 k O 必要條件有 l 叫 z P 0 于是有 l i P 0 一 十 oo oo 定理 2的結(jié)論表嘰 所設(shè)計(jì)條件梯度算法第 6步的終止條件是合理的 定理 3 由條件梯度算法所產(chǎn)生的序列 的任意一個(gè)聚點(diǎn) 將滿(mǎn)足 叫 在 D上 的極小點(diǎn)的必要條件 證明設(shè) 是 的一個(gè)聚點(diǎn) 則存在一子列 使得1 i m J 1 u 因?yàn)?叫 p 叫 z x 一 以及 z z D 不妨設(shè)l i m z 根據(jù)定理 2的結(jié)論及 的連續(xù)性 必有 l im 叫 P l i ra 叫 p k o o 3 o o l i ra Z Z rU 2 一z J o o 由上式有 z 叫 z D 張芳等 圖的最大二等分問(wèn)題的新型條件梯度算法 第 1期 上不等式說(shuō)明 滿(mǎn)足 w x 在 D上的極小點(diǎn)的必要條件 3 圖的最大二等分問(wèn)題的條件梯度算法 通過(guò)上節(jié)的分析 我們可以看出 通過(guò)條件梯度算法求解模型 MB3 的該算法要么有 限步終止 要么得到一下降序列 在條件梯度算法的迭代過(guò)程中 關(guān)鍵的步驟是 步 2中如何選取 使得 mi x z W z 成立 對(duì)于圖的最大二等分 問(wèn)題 我們有 W x z 去 T Wx Wx z 厶 注意到 Z D D 1e T X 0 一 1 X i 1 i 1 2 n 為線(xiàn)性約束空間 易知 Wx 作為 的函數(shù)必在 D 的邊界上取得極值 于是 我們可以進(jìn)一步改進(jìn)上節(jié)所給 條件梯度算法 具體地 將步 2做如下兩種細(xì)化 方法 A對(duì)向量 Wx 的分量按升序排列 得到的向量記為 d w 如果 Wx i 在 d w 中的位置為前半部分 取 1 1 2 5 否則z i 一 1 蕓 1 禮 易知 這種選取滿(mǎn)足等分條件 e T z 0 方法 B方法 A中z x 的選取受到條件 e T z 0的限制 所以我們選用模型 MB 4 以上引理及定理對(duì)模型 MB 4 仍然成立 于是 我們記 W X d w 若 d w 0 則取 z i 1 否則 取 z i 一 1 由該方法中z x 的選取所得的 X 并不一定滿(mǎn)足約束條件 e T x 0 所以我們使用貪婪算法來(lái)平衡 X中取正負(fù) 1 的分量數(shù)目 設(shè) S i ls i g n x i 1 不一 定等于蕓 不失一般性 設(shè)IS I 等 我們 借鑒文 中的方法 將S中多余的節(jié)點(diǎn)采用下述 方法轉(zhuǎn)換到 雪中 對(duì)于任意節(jié)點(diǎn) i S 令 W 巧 記 1 2 ls 1 s 取 s i l i 2 等 這樣選取則滿(mǎn)足二等分條件 lV s l 且產(chǎn)生所對(duì)應(yīng)的 z 即 若 i s 記 1 否則 記 一 1 定理 4 設(shè) 為由條件梯度算法 A或 B所產(chǎn)生的迭代序列 則算法步 6的終止 條件成立時(shí) 有 i 0 且算法的輸出解是 1 一 1 解 證明若算法步 6的終止條件 l W P l 成立 即 W x P 趨于零 則由 定理 1的結(jié)論 2 知 w x p 一w x 0 于是 算法步 5中試探法求步長(zhǎng)的不等式成立時(shí) 有 i 0 D O 一 Z l Z 叫 n 目 2 0 1 4 年 3月 高 等 學(xué) 校 計(jì) 算 數(shù) 學(xué) 學(xué) 報(bào) 又因?yàn)?i 0時(shí) 有 1 于是有 X X a k P 由方法 A和 B中 Z 的 選取知 Z 1 一 1 即算法的輸出解是 1 一 1 解 基于上述兩種不同的下降方向的選取 我們就可以得到求解圖的最大二等分問(wèn)題的 條件梯度算法 我們稱(chēng)由方法 A細(xì)化步 2 得到的算法為條件梯度算法 A 由方法 B細(xì)化 步 2 得到的算法為條件梯度算法 B 下面我們通過(guò)數(shù)值實(shí)驗(yàn)來(lái)驗(yàn)證算法 A和算法 B求解 圖的最大二等分問(wèn)題的實(shí)際效果 4 數(shù)值實(shí)驗(yàn) 在這里 條件梯度算法 A和算法 B將分別用于求解模型 MB 3 和 MB 4 并與用文 獻(xiàn) 中的算法 比較 記文獻(xiàn) 中算法為 c 所有算法均通過(guò) MA TL A B 7 0 1實(shí)現(xiàn) 使用 計(jì)算機(jī)的配置 C P U為 P e n t i u m 2 4 GH Z 內(nèi)存為 1 9 6 G B Wi n d o w s XP操作系統(tǒng) 我們給 出低維和高維兩組實(shí)驗(yàn)結(jié)果 在低維情況中 利用文獻(xiàn) 中的問(wèn)題 1 問(wèn) 題 3和 問(wèn)題 5作為對(duì)初始點(diǎn)選取 的測(cè)試 實(shí)驗(yàn)結(jié)果如表 4 1 其 中 V a l u e為 目標(biāo)函數(shù) 值 V A V B V C分別為由算法 A 算法 B 算法 C計(jì)算所得的目標(biāo)函數(shù)值 T i m e 為計(jì)算 所消耗的 C P U時(shí)間 s 為秒 T A T B T C分別為算法 A 算法 B 算法 c計(jì)算所消耗的 C P U時(shí)間 s 為秒 I t e r 為迭代次數(shù) I A I B I c分別為算法A 算法 B 算法 c的迭代次 數(shù) 為收斂點(diǎn)正負(fù) 1的數(shù) 目之差 AB AC分別為算法 A 算法 B 算法 C收斂 點(diǎn)正負(fù) 1的數(shù) 目之差 測(cè)試結(jié)果表 明初始點(diǎn)的選取對(duì)實(shí)驗(yàn)結(jié)果基本上沒(méi)有影響 因此 在 后面的 數(shù)值實(shí)驗(yàn)中均取初始值為 z 0 5 0 5 一 0 5 一 0 5 T 即前 蕓個(gè)取為0 5 后 等個(gè)取為 一 0 5 表 4 1 低維情況下三種算法所得試驗(yàn)結(jié)果的比較 問(wèn)題 場(chǎng)l u e T i me s I t e r VB VC TB TC I A I B I C A B C 1 38 3 8 3 8 0 01 0 0 0 0 0 0 0 0 01 0 0 4 9 2 5 O 一 1 l 3 1 9 1 9 1 9 0 0 0 0 0 0 0 0 0 0 0 01 0 0 11 1 2 1 0 4 0 0 0 5 7 7 7 0 0 0 0 0 0 0 0 0 0 0 00 0 0 2 3 2 7 0 1 2 從表 4 1可以看出 在獲得相同的近似最優(yōu)解的情況下 條件梯度算法 A和 B的 C P U時(shí)間短 迭代次數(shù)少 正負(fù) 1的數(shù) 目差小 明顯優(yōu)于算法 c 在高維情況中 我們用如下的隨機(jī)方法產(chǎn)生無(wú)向賦權(quán)圖 給定閥值 P 對(duì)于任意的 J E 1 n 用隨機(jī)函數(shù) R a n d n 產(chǎn)生一個(gè) 0 1 間的均勻分布的隨機(jī)矩陣 如果該隨機(jī) 矩陣中的元素小于P 則節(jié)點(diǎn) i 和節(jié)點(diǎn) J 之間有邊連接 其中表 4 2中 n 1 0 0 P 0 5 如 9 4 張芳等 圖的最大二等分問(wèn)題的新型條件梯度算法 第 1期 果節(jié)點(diǎn) i 和節(jié)點(diǎn) J之間有邊連接 則取邊的權(quán)值 w i j 為該元素乘 1 0 0 再除以 P之后向上取 整 否則 w i j 0 即 w i j 是 0 1 0 0 間的一個(gè)隨機(jī)整數(shù) 表 4 3中n 5 0 0 P 0 9 如果節(jié) 點(diǎn) i 和節(jié)點(diǎn) J 之間有邊連接 則邊的權(quán)值 w ij 取法同上 否則 w i j 0 即 w ij 也是 0 1 0 0 間的一個(gè)隨機(jī)整數(shù) 表 4 4中 n 1 0 0 0 P 0 1 如果節(jié)點(diǎn) i 和節(jié)點(diǎn) J之間有邊連接 則邊 的權(quán)值取為 w i j 1 否則 wi j 0 表中的符號(hào)與低維情況中含義相同 表 4 2 三種算法對(duì)由n 1 0 0 p 0 5 時(shí)隨機(jī)產(chǎn)生賦權(quán)圖的實(shí)驗(yàn)結(jié)果的比較 T e s t 曬l u e T i me s I t e r VB VC TB TC I A I B I C A B C 1 7 06 1 7 7 05 0 0 6 6 7 71 0 0 1 0 0 0 01 0 0 0 0 7 0 0 1 0 11 2 2 5 0 1 7 2 7 2 42 3 72 31 3 6 6 2 87 0 0 1 0 0 0 01 0 0 0 0 5 0 0 9 9 1 5 8 0 1 1 3 7 09 7 9 71 5 7 3 6 9 6 3 6 0 0 1 0 0 0 01 0 0 0 0 5 0 0 l 1 1 8 1 8 8 0 1 1 4 7 5 4 0 9 7 5 2 9 5 7 01 7 5 0 0 1 0 0 0 01 0 0 0 0 5 0 0 1 1 1 3 9 8 0 0 8 5 7 3 5 1 5 7 3 4 8 9 7 1 1 54 0 0 1 0 0 0 0 40 0 0 0 7 0 0 1 1 3 3 1 8 8 0 0 6 6 7 3 7 5 1 7 3 7 4 3 7 0 4 83 0 0 1 0 0 0 02 0 0 0 0 8 0 0 1 1 1 1 2 2 7 0 0 1 7 71 3 4 5 7 1 5 9 7 6 8 2 0 9 0 01 0 0 0 0 2 0 0 0 0 30 0 1 2 1 8 71 0 1 1 8 7 0 8 0 6 7 0 6 4 2 6 6 4 0 0 0 0 2 0 0 0 0 2 0 0 0 0 40 0 1 3 21 1 2 7 0 0 3 9 7 3 3 8 3 7 41 1 3 6 8 9 5 7 0 01 0 0 0 0 2 0 0 0 07 0 0 8 20 1 6 7 0 0 9 1 0 71 9 7 8 7 0 7 3 0 7 1 0 0 7 0 01 0 0 0 0 1 0 0 0 08 0 0 8 1 7 2 2 7 0 1 7 從表 4 2可以看出 與算法 C相 比 條件梯度算法 A和算法 B獲得 的可行解的 目標(biāo) 函數(shù)值一致的大 C P U時(shí)間一致的短 迭代次數(shù)一致的少 收斂點(diǎn)正負(fù) 1的數(shù) 目差也較少 表 4 3 三種算法對(duì)由 n 5 0 0 p 0 9時(shí)隨機(jī)產(chǎn)生賦權(quán)圖的實(shí)驗(yàn)結(jié)果的 比較 T e s t 場(chǎng)l u e T i me s I t e r VB VC TA TB TC I A I B I C A B C 1 2 9 3 0 9 2 6 2 9 3 4 9 3 6 2 8 6 51 9 8 0 2 6 0 0 1 3 6 0 0 1 1 5 0 0 1 8 6 6 2 6 4 0 1 4 0 2 2 9 2 7 2 4 5 2 9 2 4 3 0 0 2 8 62 7 7 5 0 2 0 0 0 0 6 4 0 0 2 5 5 0 0 2 6 4 8 51 3 0 1 1 3 3 2 9 3 2 3 8 6 2 9 3 1 5 5 4 2 8 9 47 4 3 0 2 1 0 0 0 7 4 0 0 1 0 3 2 0 0 2 7 61 2 3 9 8 0 0 2 7 4 2 9 2 2 0 1 7 2 9 2 0 8 5 3 2 85 7 2 7 2 0 1 1 0 0 0 4 9 0 0 3 0 31 0 0 1 3 4 5 7 61 0 0 7 5 2 9 3 0 2 51 2 9 3 4 7 4 3 2 8 9 2 2 2 2 0 1 4 0 0 0 6 8 0 0 5 2 6 0 0 1 5 6 0 1 2 2 9 0 0 2 5 6 2 9 3 61 1 7 2 9 3 81 4 8 2 8 6 1 9 9 2 0 21 0 0 0 8 5 0 0 2 6 5 0 0 2 2 8 0 61 1 0 1 8 7 2 9 3 5 7 31 2 9 3 81 7 6 2 8 6 8 0 6 2 0 1 8 0 0 0 9 5 0 0 1 5 4 0 0 1 9 9 1 3 60 0 0 3 2 8 2 9 3 4 7 6 6 2 9 3 5 9 7 7 2 8 7 7 0 7 9 0 21 0 0 0 41 0 0 2 9 2 0 0 2 3 3 4 6 67 0 0 3 1 9 2 9 2 7 8 41 2 9 2 5 41 0 2 8 7 0 4 2 4 0 1 7 0 0 0 5 0 0 0 3 5 4 0 0 2 0 4 4 8 2 3 0 0 4 1 0 2 9 2 8 4 61 2 9 3 3 4 5 8 2 8 8 1 6 0 0 0 09 0 0 0 7 6 0 0 1 4 6 0 0 1 2 6 3 3 3 3 0 0 3 0 2 0 1 4 年 3月 高 等 學(xué) 校 計(jì) 算 數(shù) 學(xué) 學(xué) 報(bào) 從表 4 3可以看 出 與算法 C相 比 除了 T e s t l 之外 其他的 T e s t 實(shí)驗(yàn)結(jié)果中由條件 梯度算法 A和算法 B獲得的可行解的 目標(biāo)函數(shù)值較大 C P U時(shí)間較短 迭代次數(shù)較少 收 斂點(diǎn)正負(fù) 1的數(shù) 目差較少 表 4 4 三種算法對(duì) 由 n 1 0 0 0 p 0 1時(shí)隨機(jī)產(chǎn)生賦權(quán)圖的實(shí)驗(yàn)結(jié)果的比較 T e s t 場(chǎng)l u e Ti me s I t e r VB VC TB TC I A I B I C A B C 1 2 8 21 7 2 82 0 3 2 6 90 8 1 9 6 0 0 1 3 8 0 0 3 3 7 0 0 3 3 41 1 5 9 0 1 6 3 2 2 8 45 4 2 8 3 6 9 2 6 92 1 1 3 2 0 0 1 1 5 0 0 7 6 9 0 0 4 4 2 8 4 0 8 0 0 21 3 2 8 31 2 2 8 3 4 5 2 7 3 4 6 0 7 9 0 0 1 6 7 0 0 4 9 3 0 0 2 6 4 5 2 4 8 0 一 l 1 2 2 4 2 8 1 6 9 2 8 2 9 0 2 7 01 6 0 8 2 0 0 1 1 0 0 0 1 7 62 0 0 2 3 3 9 9 3 6 1 1 9 4 5 2 8 2 0 5 2 8 2 3 2 2 7 2 7 2 1 45 0 0 1 69 00 3 09 00 49 49 1 6 5 0 3 1 47 6 2 8 1 9 7 2 8 2 6 7 2 8 2 5 5 0 97 0 0 1 2 3 0 0 1 3 9 5 0 0 2 7 4 2 7 44 0 1 47 7 2 8 2 5 1 2 8 3 4 1 2 7 3 2 8 1 0 9 0 0 2 01 0 0 3 9 2 0 0 4 0 6 8 2 31 0 0 1 41 8 2 83 7 1 2 83 3 6 27 0 8 6 1 5 0 0 0 2 4 4 0 0 2 4 6 0 0 5 5 7 9 1 4 3 0 0 1 2 7 9 2 8 3 04 2 8 31 7 2 72 1 9 1 2 0 0 0 2 2 5 0 0 1 6 8 0 0 4 5 8 3 9 7 0 2 2 0 9 1 0 2 8 3 87 2 8 4 3 7 2 7 0 47 0 8 5 0 0 1 6 1 0 0 6 9 0 0 0 3 1 5 1 4 0 7 0 2 0 從表 4 4可以看出 與算法 C相 比 除了 T e s t 9之外 其他 T e s t的實(shí)驗(yàn)結(jié)果 中由條 件梯度算法 A和算法 B獲得的可行解的 目標(biāo)函數(shù)值較大 C P U時(shí)間較短 迭代次數(shù)較少 收斂點(diǎn)正負(fù) 1的數(shù) 目差較少 為了進(jìn)一步測(cè)試條件梯度算法求解大規(guī)模 圖的最大二等分 問(wèn)題 的實(shí)際效果 我們用 如下的隨機(jī)方法產(chǎn)生大規(guī)模的無(wú) 向賦權(quán)圖 給定閥值 P 0 5 分別取節(jié)點(diǎn)數(shù) n 1 0 0 0 2 0 0 0 8 0 0 0 對(duì)于任意的 i J 1 n 用隨機(jī)函數(shù) R a n d n 產(chǎn)生一個(gè) 0 1 問(wèn) 的均勻分布的隨機(jī)矩陣 如果該隨機(jī)矩陣中的元素小于 P 則節(jié)點(diǎn) i 和節(jié)點(diǎn)J之間有邊連 接 取邊的權(quán)值 W i 1 否則 W t 0 不同情形下所需運(yùn)行時(shí)間見(jiàn)表 4 5 9 6 張芳等 圖的最大二等分問(wèn)題的新型條件梯度算法 第 1期 表 4 5 對(duì)由 禮較大 p 0 5時(shí)條件梯度算法求解大規(guī)模圖的最大二等分問(wèn)題的運(yùn)行時(shí)間 節(jié)點(diǎn)數(shù) n 1 0 0 0 2 0 0 0 3 0 0 0 4 0 0 0 5 0 0 0 6 0 0 0 7 0 0 0 8 0 0 0 算法 A的 C P U時(shí)間 s 1 6 2 0 4 1 4 0 2 1 0 8 0 4 4 8 9 0 1 1 0 8 9 0 1 4 2 8 1 0 4 0 7 2 7 0 N A 算法 B的 C P U時(shí)間 s 2 2 8 0 1 6 3 6 0 9 1 9 5 0 1 5 5 4 3 0 3 5 9 1 6 0 3 4 2 1 9 0 6 5 7 3 8 0 N A 從表 4 5可以看 出 條件梯度算法能夠在比較短的時(shí)間內(nèi)求得較大規(guī)模圖的最大二 等分問(wèn)題的近似解 當(dāng) n 8 0 0 0時(shí) 程序顯示內(nèi)存不足 同時(shí) 我們可以看到 與算法 B 相比 算法 A在求解較大規(guī)模的問(wèn)題時(shí)運(yùn)行時(shí)間要短 參 考 文 獻(xiàn) 1 Fr i e z e A a n d J e r r u m M I mp r o v e d a p pr o x i m a t i o n a l g o r i t h ms f o r M a x k c u t a n d M a x bi s e c t i o n Pr o c e d i n g s o f t h e 4 t h Al g o r i t h m i c a 1 9 9 7 1 8 6 7 8 1 2 Go e ma n s M X a n d W i l l i ms o n D P I mp r o v e d a p p r o x i ma t i o n a l g o r i t h ms for ma x i mu m c u t a n d s a t i s fia b i l i t y p r o b l e ms u s i ng s e mi d e fi n i t e p r o g r a mmi n g J o u r n a