[發(fā)明專利]最優(yōu)化問題的求解方法及其系統(tǒng)

無效

• 申請?zhí)枺?/td>: 200580036999.4
• 申請日: 2005-10-21
• 公開（公告）號: CN101065742A
• 公開（公告）日: 2007-10-31
• 發(fā)明（設(shè)計）人: 艾夏克·艾拉米利;斯瑞尼瓦司·那查甘地
• 申請（專利權(quán)）人: 奈特普軟體有限公司
• 主分類號: G06F15/18
• 分類號: G06F15/18
• 代理公司: 中原信達知識產(chǎn)權(quán)代理有限責(zé)任公司
• 代理人: 謝麗娜;陳肖梅

技術(shù)領(lǐng)域

本發(fā)明有關(guān)最優(yōu)化領(lǐng)域；特別是指一種基于本地搜索技術(shù)在一組約束下的最優(yōu)化問題的求解方法及其系統(tǒng)。

背景技術(shù)

在所有工業(yè)中都存在最優(yōu)化問題。例如，最優(yōu)化問題涉及生產(chǎn)線上的計畫、調(diào)度和產(chǎn)品制造的制程。這些制程通常比較復(fù)雜，而且取決于很多因素，如設(shè)備的可變生產(chǎn)量、制造過程的多個階段、使用單一資源的多種產(chǎn)品的生產(chǎn)、人力或制程限制以及具體工業(yè)的其它特定因素(例如產(chǎn)品生產(chǎn)周期)等。一般而言，可存在大量用來管理這些工藝的規(guī)則或約束。因此，在環(huán)境約束條件內(nèi)如何計畫、調(diào)度或配置以最優(yōu)地完成這些制程是十分重要的。

求解最優(yōu)化問題的常規(guī)技術(shù)包括人工和自動最優(yōu)化方法。人工方法需要人的介入。通過人工方法獲得的最優(yōu)化程度很大程度上取決于所涉及的人的技能和經(jīng)驗，以及最優(yōu)化問題的大小(由對應(yīng)于該最優(yōu)化問題的潛在解的數(shù)目和約束的數(shù)目表示)。同時，人工方法耗時、棘手而且可導(dǎo)致例如不良的解品質(zhì)和人為錯誤等問題。隨著最優(yōu)化問題牽涉的范圍越廣，人工方法變得不可行。自動最優(yōu)化方法利用定義好的算法求解最優(yōu)化問題。一類常見的自動最優(yōu)化方法是基于本地搜索(LS)的概念。該技術(shù)涵蓋了一系列組合啟發(fā)式算法(combinatorialheuristics)，如模擬退火算法(simulated?annealing)、遺傳算法(geneticalgorithm)、禁忌搜索(taboo?search)算法和演化算法(evolutionaryalgorithm)。以下提供了此類啟發(fā)式算法的參考，包括“Facts，Conjecturesand?Improvements?for?Simulated?Annealing”，作者P.Salamon、P.Sibani和R.Frost，于2002年由SIAM?Monograph出版。

而“Genetic?Algorithms?and?Engineering?Design”，作者M.Gen和R.Chang，于1997年由John?Wiley?&?Sons出版，提供了另一個此類啟發(fā)式算法。

再者，“Modern?Heuristic?Techniques?for?Combinatorial?Problems”，作者Colin?Reeves，于1993年由Halsted?Press出版，也提供了另一個此類啟發(fā)式算法。

LS技術(shù)通過在解的區(qū)間內(nèi)制造局部運動(local?move)來求解最優(yōu)化問題。舉例來說，制造—調(diào)度問題的解可為生產(chǎn)調(diào)度的數(shù)學(xué)表達式，其實際上是制造不同物品所依據(jù)的時間表。在所有的LS啟發(fā)式算法中，通過方便的機制產(chǎn)生一個或一個以上解。可使用任何方便的機制，因為最初的一組解無需滿足任何約束；因此，它們甚至可隨機生成。LS啟發(fā)式算法通過較小改變或局部改變來系統(tǒng)地提煉該組解。此產(chǎn)生一組新的候選解。用于生成這些局部改變的技術(shù)根據(jù)所使用的LS啟發(fā)式算法不同而不同。然后，評估該組候選解，以判定對現(xiàn)有約束的欠缺或違反。基于根據(jù)所使用的啟發(fā)式算法不同而變化的接受標準，接受該等候選解中的一個或一個以上。重復(fù)此過程，直到這些解無可觀改善，或超過計算預(yù)算。實際上，獲得高品質(zhì)的解需要大量運動(move)，且LS啟發(fā)式算法的實際利用率取決于對照若干約束對大量(近10δ至108個)候選解的有效評估。

通常，對解的評估是針對整個解。這需要高速且存儲容量大的計算機。如果評估以增量方式實施(即，僅評估發(fā)生變化的解的鄰域)，那么該方法是特別針對于特定約束，且取決于局部運動發(fā)生的方式。這需要廣泛且延續(xù)的軟件開發(fā)或其它產(chǎn)品開發(fā)。因此，很明顯，所拖延的計算時間和高成本限制了基于本地搜索的方法的實際使用。

因此，需要發(fā)展一種能加速計算過程，同時能有效求解實際最優(yōu)化問題的技術(shù)。這種技術(shù)應(yīng)該是成本有效的。還應(yīng)有可能將其實施于工作站和PC上，而過程需要最少的人力干預(yù)。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種用于有一組約束的最優(yōu)化問題的求解方法及其系統(tǒng)。

本發(fā)明的另一個目的在于提供一種對用于有一組約束的最優(yōu)化問題的一組解進行增量評估的求解系統(tǒng)及其方法。

本發(fā)明的又一個目的是提供一種用于最優(yōu)化問題的求解系統(tǒng)及其方法，其中對解的評估與約束的性質(zhì)無關(guān)。

本發(fā)明的再一個目的是提供一種用于最優(yōu)化問題的求解系統(tǒng)及其方法，其中對解的評估與候選解是以何種方式產(chǎn)生的無關(guān)。