[發明專利]最優化問題的求解方法及其系統

無效

• 申請號: 200580036999.4
• 申請日: 2005-10-21
• 公開（公告）號: CN101065742A
• 公開（公告）日: 2007-10-31
• 發明（設計）人: 艾夏克·艾拉米利;斯瑞尼瓦司·那查甘地
• 申請（專利權）人: 奈特普軟體有限公司
• 主分類號: G06F15/18
• 分類號: G06F15/18
• 代理公司: 中原信達知識產權代理有限責任公司
• 代理人: 謝麗娜;陳肖梅

1.一種在一組約束下的最優化問題的求解方法，其特征在于，該方法包含：

a.評估在該組約束下的該最優化問題的一組解；

b.基于與評估期間違反了至少一個約束的該組解相對應的該組約束，生成初始違反度量組和狀態組；

c.利用一組操作數生成一組從該組解衍生出的候選解，其中每個操作數以一組變化點為特征；

d.在該等變化點評估該組候選解；

e.基于一接受標準，測試一被評估的候選解的可接受性；

f.若所測試的候選解被接受，則基于被接受的候選解更新違反度量和狀態；

g.重復步驟e至步驟f，直到所有被評估的候選解都經過接受性測試；及

h.重復步驟c至步驟g，直到滿足一終結標準。

2.如權利要求1所述的求解方法，其特征在于評估該最優化問題的該組解的步驟包括利用零狀態評估該組解。

3.如權利要求1所述的求解方法，其特征在于包括將每個違反度量映像至一成本之步驟，該映像步驟包括：

a.基于一定義函數變換每個違反度量；

b.規范化每個經過變換的違反度量；

c.基于與各變量相關的優先權換算每個規范化的違反度量；及

d.合計經過換算的違反度量，以生成與違反約束相關的成本。

4.如權利要求1所述的求解方法，其特征在于通過該組操作數執行的運算包括解的交換、插入、移位和刪除運算中的至少一個運算。

5.如權利要求1所述的求解方法，其特征在于評估該組候選解的步驟包括：在與對應的操作數相關的各變化點，增量評估該組候選解中的一個候選解。

6.如權利要求1所述的求解方法，其特征在于增量評估該候選解，直到該候選解與對應解邏輯相等，且該候選解所對應的狀態與該對應解所對應的狀態邏輯相等。

7.如權利要求1所述的求解方法，其特征在于當發生下列情形時，滿足該終結標準：a.已完成預定數目的迭代；或b.經過預定數目的迭代，該組候選解的改善程度小于預定改善程度。

8.如權利要求7所述的求解方法，其特征在于該預定數目的迭代的完成是基于：a.該最優化問題的復雜度；和b.求解該最優化問題可用的時間。

9.一種用于在一組約束下的最優化問題的求解系統，其特征在于，該系統包含：

一用以評估在該組約束下的該最優化問題的一組解的構件；

一用以基于與評估期間違反了至少一個約束的該組解相對應的該組約束，生成初始違反度量組和狀態組的構件；

一用以運算該組解生成一組候選解的構件；

一用以比較解和狀態的構件；

一用以基于一接受標準接受被評估的解的構件；以及

一用以基于被接受的解更新違反度量的構件。

10.一種用于在一組約束下的最優化問題的求解系統，其特征在于，該系統包含：

一用以評估該最優化問題的解、生成解的違反度量和更新違反度量和狀態的評估單元；

一用以運算一解以生成一候選解的運算單元，其與該評估單元相連接；以及

一用以接受該最優化問題的一解的接收單元，其與該評估單元相連接。

11.如權利要求10所述的求解系統，其特征在于該評估單元包含一用于生成和更新一違反度量的步進器。

12.如權利要求11所述的求解系統，其特征在于該步進器基于判定對至少一個約束的違反的至少一個規則來判定違反。

13.如權利要求10所述的求解系統，其特征在于該評估單元包含一用于比較一對解和一對狀態的比較器。

14.如權利要求10所述的求解系統，其特征在于該評估單元包含一用于儲存與一狀態對應的信息的存儲陣列。

15.如權利要求10所述的求解系統，其特征在于該評估單元包含一用于儲存所生成的解的存儲陣列。

16.一種用于在一組約束下的最優化問題的求解之計算機程序產品，其特征在于，該計算機程序產品包含：

a.用于評估在一組約束下的最優化問題的一組解的程序指令構件；

b.用于基于與評估期間違反了至少一個約束的該組解相對應的該組約束，生成初始違反度量組和狀態組的程序指令構件；

c.用于利用一組操作數生成一組從該組解衍生出的候選解的程序指令構件，其中每個操作數以一組變化點為特征；

d.用于在所生成的變化點評估該組候選解的程序指令構件；

e.用于基于一接受標準，測試一被評估的候選解的可接受性的程序指令構件；

f.基于被接受的候選解更新違反度量和狀態的程序指令構件；以及

g.檢查是否滿足一終結標準的程序指令構件。