最適化アルゴリズムは、この関数に最大値または最小値を与える関数の入力パラメーターのセットを決定しようとします。たとえば、可能な限り多くの缶を製造するための金属シートの最適な切断 (または可能な限り多くのシャツを製造するための生地など) を追求します。この最適化は、制約なしまたは制約 のもとで実行できます。2 番目のケースは、ラグランジュ乗数法で微分可能な関数 (およびエベレットアルゴリズムで微分不可能な関数) の場合は 1 番目のケースに縮小されます。
もちろん、関数について何も知らない場合、問題自体は解決できません (おそらく、入力値の非常に特殊な組み合わせによって、検出を逃れることができる非常に高い値または低い値が発生する可能性があります)。関数について得られるさまざまな知識に関連付けられたアルゴリズムが微分可能である場合、最も効率的なアルゴリズムの 1 つは共役勾配です。
2004 年に知られている方法は (もちろん徹底的な列挙や代数解析は別として)、関数の大域的な極値を確実に見つけることを可能にするものはありません。決定可能な極値は常にドメインに対してローカルであり、多くの場合、この場合でも関数のいくつかの特性 (たとえば、特定のケースではcontinuity )が必要になります。
メタヒューリスティックは、困難な最適化問題の場合に大域最適を近似しようとする最適化アルゴリズムのクラスです。ただし、結果の信頼性を保証するものではありません。
詳細
- 決定問題P に関連付けられた最適化問題のアルゴリズムを A とします。
- O p t ( i ) は、問題 P のインスタンス i の最適解です。
- Cost ( i ) は、解 j の k’ 値です。
- A は多項式であり、次のようになります。
- もっている ： $$ {I(P)\rightarrow S : i\rightarrow j \in s(i)} $$、 C P ( i , j ) = yes iとなります。
- $$ {\exist} $$c、i に依存しない定数。次のとおりです。
