按需最優(yōu)計(jì)算方法及其算法設(shè)計(jì)策略研究

□李曉亞

(中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院應(yīng)用數(shù)學(xué)研究所，北京 100190)

最優(yōu)化、人工智能、組合數(shù)學(xué)、邏輯以及其它領(lǐng)域中提出的許多最基本的離散計(jì)算問題，屬于一類被稱為NP難問題。我們既不知道這些問題的多項(xiàng)式時(shí)間算法，也不能證明這些問題不存在多項(xiàng)式時(shí)間算法。設(shè)計(jì)快速實(shí)時(shí)而又有效的算法策略的初衷，是為了提高解決這些實(shí)際問題的效率。其中大多數(shù)問題都是半結(jié)構(gòu)化甚至是非結(jié)構(gòu)化，因此要面臨的一個(gè)主要障礙是，目前從理論上還沒有一個(gè)廣泛的通用的架構(gòu)可以分析這類問題的復(fù)雜性本質(zhì)。以我們通常面臨的組合優(yōu)化問題為例，其中絕大部分都是NP難問題，這類問題暫時(shí)無法找到多項(xiàng)式時(shí)間算法來求得其精確解。至今，理論工作者已經(jīng)發(fā)現(xiàn)了成千上萬個(gè)NP完全問題，但卻沒有對(duì)實(shí)際應(yīng)用當(dāng)中的解決方式給出一個(gè)系統(tǒng)的指導(dǎo)，而只是針對(duì)問題零散地設(shè)計(jì)各種近似算法、啟發(fā)式算法等來求得問題的解。當(dāng)問題規(guī)模很大時(shí)，直接求解其精確解是不可行的，那么應(yīng)該采取怎樣的算法或策略來求解這類NP難問題呢?

另一方面，考察問題的需求主要是以下幾個(gè)方面:如果想要快速得到一個(gè)大規(guī)模問題的精確解，需要付出多大的代價(jià)呢?需要什么樣的計(jì)算機(jī)資源呢?或者說，如果想要幾分鐘得到一個(gè)調(diào)度方案，那么能得到一個(gè)什么樣的方案，即所得方案與最理想方案的近似程度或者精確程度最高能達(dá)到多少?在這類問題中，很多實(shí)例只有在最壞情況下或從理論層面看才是難解的，而實(shí)際中出現(xiàn)大部分情況都可用有效的算法求得較滿意的解，并且問題實(shí)例的復(fù)雜程度與問題條件結(jié)構(gòu)之間具有比較強(qiáng)的相關(guān)性。問題的結(jié)構(gòu)越有序即不確定性越小，則問題計(jì)算難度越低;問題的結(jié)構(gòu)越混亂即不確定性越大，則計(jì)算難度越高。而問題條件一旦確定，我們就可以按照決策者對(duì)計(jì)算時(shí)間和計(jì)算精度的需求匹配最佳算法，從而確定出至少需要什么樣的計(jì)算資源。反過來，已知計(jì)算時(shí)間的需求和計(jì)算資源，從而確定能得到多高精度的解。決策者確定出解的近似度和已有的計(jì)算資源，從而確定至少需要多長(zhǎng)時(shí)間求出符合該目標(biāo)的解。［1，2］在以往的研究中，學(xué)者們或者注重于理論，希冀給出最優(yōu)算法或證明近似算法的最壞情況;或者偏重于應(yīng)用，通過模擬找到具有很好的實(shí)際效果的啟發(fā)式算法。這兩種思路各有所長(zhǎng)，但也均有不足之處。在實(shí)際生活生產(chǎn)當(dāng)中，很多問題往往不是靠單一類算法求解就能得到最滿意的答案，目前也很少見到將理論與應(yīng)用兩種算法設(shè)計(jì)思路結(jié)合起來使用的例子?；诖?，為了系統(tǒng)化地求解這類組合優(yōu)化問題，我們首次提出按需最優(yōu)計(jì)算方法，綜合考慮可用的計(jì)算機(jī)資源、數(shù)據(jù)資源和模型資源的性能、問題實(shí)例的復(fù)雜程度，以及用戶對(duì)計(jì)算時(shí)間以及計(jì)算精度的具體要求等參數(shù)因素，通過比較匹配，依策略選擇精確算法、近似算法以及不同計(jì)算規(guī)模的啟發(fā)式算法來對(duì)問題進(jìn)行求解。

一、按需最優(yōu)計(jì)算方法的提出

在當(dāng)今競(jìng)爭(zhēng)局勢(shì)日益激烈、可用資源日益緊缺、信息知識(shí)不斷膨脹的環(huán)境下，如何滿足來自于外界以及內(nèi)部的各種需求，實(shí)現(xiàn)高效管理、有效決策就顯得意義重大。同時(shí)，人們對(duì)這類問題解決模式的需求巨大，并且一旦模式有效，由此產(chǎn)生的社會(huì)影響、科學(xué)影響也會(huì)是十分深遠(yuǎn)的。Holland在《隱秩序－適應(yīng)性造就復(fù)雜性》書中，強(qiáng)調(diào)了在尋找支配復(fù)雜適應(yīng)系統(tǒng)行為的一般原理中，數(shù)學(xué)扮演著一個(gè)非常重要的角色，并預(yù)言在復(fù)雜自適應(yīng)系統(tǒng)的研究中，只有數(shù)學(xué)才能帶我們走完全程。［3］Holland的預(yù)言是有依據(jù)的，因?yàn)閺?fù)雜自適應(yīng)系統(tǒng)(CAS)中面臨的大量問題往往都是NP難或NP完全的，卻要面對(duì)快速計(jì)算和高效決策之間的矛盾，也就是求解時(shí)間與求解精度之間的矛盾，要緩解這種矛盾，采用以往的通過建立數(shù)學(xué)模型庫(kù)和方法庫(kù)來實(shí)現(xiàn)決策支持功能的模式已經(jīng)難以實(shí)現(xiàn)，這對(duì)科學(xué)界尤其是算法界提出了新的挑戰(zhàn)。解決此類問題，由于其復(fù)雜性特點(diǎn)，通過某一方案是很難系統(tǒng)解決的，這就需要構(gòu)建決策支持系統(tǒng)來輔助決策;并且，由于問題的不確定性，根據(jù)問題條件變化和決策者的需求變化，該系統(tǒng)需要具有設(shè)計(jì)個(gè)性化方案模式的功能;而由于問題本身開放性特點(diǎn)，隨著時(shí)間變化和周圍環(huán)境變化，具有動(dòng)態(tài)演化的特點(diǎn)，因此所構(gòu)建的決策支持系統(tǒng)要能實(shí)時(shí)自適應(yīng)。基于這種更好地求解問題的需求，我們提出一種新的模式，即:按需最優(yōu)計(jì)算方法，通過設(shè)計(jì)一種新的基于優(yōu)化算法思想的決策模式，以期對(duì)客觀世界中普遍具有開放性、不確定性和復(fù)雜性特點(diǎn)的熱點(diǎn)問題進(jìn)行深入探討，以滿足實(shí)時(shí)高效的決策需求。

按需最優(yōu)計(jì)算算法設(shè)計(jì)的理論框架綜合了“運(yùn)籌學(xué)”、“按需計(jì)算”、“連續(xù)管理”、“復(fù)雜自適應(yīng)系統(tǒng)”理論。在信息技術(shù)行業(yè)，“按需計(jì)算”指根據(jù)用戶的需求，動(dòng)態(tài)地提供相應(yīng)的IT資源。這種按需服務(wù)具有兩種特點(diǎn):“動(dòng)態(tài)”和“適量”?！皠?dòng)態(tài)”表示隨時(shí)汲取，“適量”表示不會(huì)因買多了而產(chǎn)生不必要的浪費(fèi)。復(fù)雜自適應(yīng)系統(tǒng)理論是遺傳算法之父Holland提出來的，其理念在于提出具有適應(yīng)能力的、主動(dòng)的個(gè)體，可以根據(jù)環(huán)境的變化改變自己的行為規(guī)則，以求生存和發(fā)展。這里的每一個(gè)獨(dú)立的個(gè)體在系統(tǒng)中都在探索一種個(gè)體最優(yōu)的策略，從系統(tǒng)整體的角度，如何設(shè)計(jì)競(jìng)爭(zhēng)規(guī)則，使每個(gè)獨(dú)立體的最優(yōu)選擇的結(jié)果“加和”，得到對(duì)整體優(yōu)化更好的策略。這一思想與算法博弈論的主旨相似，算法博弈論的核心目標(biāo)是為策略環(huán)境下的問題設(shè)計(jì)算法，將問題所研究系統(tǒng)的形成與運(yùn)作視為一個(gè)博弈過程:由眾多的尋求自身利益極大化的參與者通過相互作用實(shí)現(xiàn)。［4］

二、算法設(shè)計(jì)策略

具體來講，目前已有的各種算法設(shè)計(jì)技術(shù)或策略涉及到啟發(fā)式算法、分治策略、動(dòng)態(tài)規(guī)劃、近似算法、算法復(fù)雜性理論等，分為以下四類:1)基于貪心策略的啟發(fā)式算法研究:一個(gè)算法是貪心的，如果它是通過一些小的步驟來建立一個(gè)解，在每一步根據(jù)局部情況選擇一個(gè)決定使得某些主要的指標(biāo)能得到優(yōu)化。［5］由于在實(shí)際中常常面臨的是大規(guī)模問題，設(shè)計(jì)的各種近似算法速度很可能達(dá)不到要求。Holland提出的遺傳算法理論，［6］以及模擬退火算法，人工神經(jīng)網(wǎng)絡(luò)，禁忌搜索算法，演化算法，蟻群算法，量子算法等等，都是比較流行的啟發(fā)式算法。啟發(fā)式算法雖然并未有理論證明其與最優(yōu)解之間的差異程度，但在工程應(yīng)用中，很多時(shí)候要找到一個(gè)有效算法并嚴(yán)格地證明其近似程度，也是比較困難的，因此啟發(fā)式算法在實(shí)踐中被廣為應(yīng)用。［7］2)近似算法研究:組合優(yōu)化中的絕大部分問題都是NP難問題。NP難問題的精確算法的計(jì)算時(shí)間復(fù)雜度常常是指數(shù)級(jí)別的，即求得問題精確解所花費(fèi)的時(shí)間隨著問題規(guī)模的增長(zhǎng)而指數(shù)式增加。由于NP完全問題的難于求解性，一種可行而實(shí)用的策略是在有限或允許的時(shí)間內(nèi)尋找問題盡可能好的近似解。近似算法可以快速有效地得出一個(gè)問題的次優(yōu)解，且提供一個(gè)估計(jì)出計(jì)算結(jié)果與真正最優(yōu)解之間的差異程度的數(shù)量表示，因此，在沒有多項(xiàng)式算法的情況下，近似算法也是一種比較好的選擇。近似算法是處理難解的組合優(yōu)化問題的一個(gè)非常重要和有效的方法。它可以在多項(xiàng)式時(shí)間內(nèi)求得問題的一個(gè)解，并使其目標(biāo)函數(shù)值與最優(yōu)解的目標(biāo)函數(shù)值之比不超過一個(gè)常數(shù)。［8］3)動(dòng)態(tài)規(guī)劃算法研究:動(dòng)態(tài)規(guī)劃算法的基本思想是將問題分解為一系列子問題，通過一種類似于蠻力搜索的迭代過程得到子問題的最優(yōu)解，然后通過重新解釋這個(gè)過程，把它作為由建立越來越大的子問題的解而工作的迭代算法。［5］4)復(fù)雜性研究:應(yīng)用數(shù)學(xué)面臨的一個(gè)重大問題就是如何理解復(fù)雜性。傳統(tǒng)的科學(xué)研究所采用的自上而下(Top－down)的方式并不總能解釋自然界中的現(xiàn)象，取而代之的是自組織、自適應(yīng)和涌現(xiàn)等新的復(fù)雜現(xiàn)象。［9］Feldman分析了動(dòng)態(tài)系統(tǒng)是如何處理信息的，并引入無序性的概念，認(rèn)為一個(gè)系統(tǒng)的復(fù)雜性體現(xiàn)在以下方面:組織，結(jié)構(gòu)，記憶，規(guī)則，以及模式等。通過運(yùn)用復(fù)雜熵的概念，利用信息論中的熵的概念來反映問題結(jié)構(gòu)的無序程度，并分析仿真了其變化特征。［10］

針對(duì)NP難問題，傳統(tǒng)方法的解決思路一般退而求其次采用設(shè)計(jì)一個(gè)近似算法求出近似解，或者設(shè)計(jì)一個(gè)啟發(fā)式算法得出一個(gè)可行解，甚至也有給問題設(shè)計(jì)一些加強(qiáng)條件，即問題的一種特殊情形，并證明這種情形下的問題是一個(gè)P問題，然后針對(duì)該情形設(shè)計(jì)多項(xiàng)式算法求解。但是，如何系統(tǒng)化地求解這類NP難問題目前仍然沒有學(xué)者給出思路。我們知道，在實(shí)際生活生產(chǎn)當(dāng)中，很多問題往往不是籠統(tǒng)地靠單一算法求解就能得到滿意的答案的。事實(shí)上，已經(jīng)有許多不同的方法或技巧可以用來設(shè)計(jì)求解NP難問題，特別是某種形式的組合優(yōu)化問題的不同性能、不同形式的算法，并且在求解NP難問題上已有的方法或思路已初步體現(xiàn)出按需最優(yōu)計(jì)算方法的算法策略設(shè)計(jì)特點(diǎn)。一般而言，對(duì)于一類計(jì)算難度大的問題，我們通過尋找統(tǒng)一的啟發(fā)式算法或近似算法來快速地求解其近似解。［11，12］但是，對(duì)于下列類型的問題情形也統(tǒng)一采用啟發(fā)式算法或近似算法得到近似解是不合理的:一類是具有特殊結(jié)構(gòu)，由多項(xiàng)式時(shí)間算法可求解得到精確解的問題情形;另一類是可以直接通過枚舉快速得到最優(yōu)解的小規(guī)模問題。Woeginger總結(jié)分析了一類超多項(xiàng)式算法的特點(diǎn)，并對(duì)不同的超多項(xiàng)式算法技術(shù)分類，較為全面地羅列了各種算法設(shè)計(jì)技術(shù)對(duì)應(yīng)的可精確求解的NP難問題。［13］Papadimitriou等探討了算法有效性設(shè)計(jì)與問題復(fù)雜性之間的關(guān)系，指出許多NP難問題未被求解不是因?yàn)閱栴}是難的，而是因?yàn)槿藗冞€未找到合適的可以對(duì)它們進(jìn)行求解的有效算法設(shè)計(jì)技術(shù)。［14］

基于以上分析調(diào)研，本文研究了利用按需最優(yōu)計(jì)算方法來設(shè)計(jì)NP難問題的算法設(shè)計(jì)方法。其基本策略如下:給定一個(gè)NP難問題，通過某種復(fù)雜性規(guī)律來給出其復(fù)雜程度的量化表示，定義為復(fù)雜熵E。假設(shè)綜合考慮了用戶對(duì)精度的要求、用戶對(duì)計(jì)算時(shí)間的要求、可用計(jì)算資源的性能等因素以后，得到用戶可以承受的計(jì)算復(fù)雜熵的上界為Q。具體策略為1)若E=0，選擇精確算法(枚舉算法);2)若0＜E＜Q，建議選擇枚舉算法或者動(dòng)態(tài)規(guī)劃算法;3)若E ＞Q，建議選擇啟發(fā)式算法進(jìn)行求解，也可設(shè)計(jì)近似算法對(duì)其進(jìn)行求解。這里，按需最優(yōu)計(jì)算體現(xiàn)在:當(dāng)確定了問題實(shí)例的復(fù)雜程度以后，決策者或用戶可選擇最合適的算法，算法的選擇取決于實(shí)例的復(fù)雜熵、計(jì)算機(jī)的性能、用戶對(duì)精度以及計(jì)算時(shí)間的要求。

三、結(jié)論

按需最優(yōu)計(jì)算方法旨在針對(duì)廣泛的NP難問題，設(shè)計(jì)快速、實(shí)時(shí)的算法策略，根據(jù)用戶的計(jì)算需求以及問題的復(fù)雜程度進(jìn)行算法設(shè)計(jì)，滿足需求與現(xiàn)實(shí)的最佳平衡。按需最優(yōu)計(jì)算方法起源于應(yīng)用，落足到理論，即考慮系統(tǒng)建模中的優(yōu)化，又探索算法設(shè)計(jì)中的新方法，是搭建于理論與應(yīng)用之間的橋，實(shí)現(xiàn)理論與應(yīng)用的融合。

［1］李文林.數(shù)學(xué):新的黃金時(shí)代［M］.上海:上海教育出版社，1997.

［2］王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析［M］.北京:電子工業(yè)出版社，2004.

［3］霍蘭著，陳禹，方美琪，韓暉，周曉牧等譯.隱秩序［M］.上海:上?？萍冀逃霭嫔纾?000.

［4］Noam Nisan，Tim Roughgarden，Eva Tardos，Vijay V.Vazirani.Algorithmic Game Theory［M］.Cambridge University press，2007.

［5］Jon Kleinberg，Eva Tardos著，張立昂，曲婉玲譯.算法設(shè)計(jì)［M］.北京:清華大學(xué)出版社，2007.

［6］John H.Holland.Genetic Algorithm – Computer programs that“evolve”in ways that resemble natural selection can solve complex problems even their creators do not fully understand［J］.Scientific American，July:66－72，1992.

［7］越民義.組合優(yōu)化導(dǎo)論［M］.杭州:浙江科學(xué)技術(shù)出版社，2001.

［8］堵丁柱，葛可一，胡曉東.近似算法的設(shè)計(jì)與分析［M］.北京:高等教育出版社，2011.

［9］李大潛等.2011－2020年我國(guó)數(shù)學(xué)學(xué)科發(fā)展戰(zhàn)略研究［R］.2010.

［10］D P Feldman，C S McTague，J P Crutchfield.The organization of intrinsic computation:Complexity－entropy diagrams and the diversity of natural information processing［J］.Chaos，18(4)，2008:043106.

［11］C E Moustakas.Heuristic research:design，methodology，and applications［M］.Sage Publications，Inc，1990.

［12］D Pisinger，S Ropke.A general Heuristic for Vehicle Routing Problems［J］.Computers and Operations Research，34(8)，August:2403－2435，2007.

［13］G J Woeginger.Exact Algorithms for NP － Hard Problems:A survey［C］.Combinatorial Optimization(Edmonds Festschrift)，LNCS 2570:185 －207，2003.

［14］H R Lewis，C H Papadimitriou.The Efficiency of Algorithms［J］.Scientific American，238(1)，96－109，Jan 1978.