![](http://oshiete.xgoo.jp/images/v2/pc/qa/question_title.png?5a7ff87)
複雑な関数の最小値を求めるためのプログラムを製作しています。
4つの独立な変数からなる関数を最小にする変数を探し出したいのですが、
効率の良いプログラムがなかなか作れません。
これまで試してみたのは、まずある適当な変数の組み合わせを任意に決め、
それを基準にそこから変数を少しだけずらしたとき、
関数の値が元よりも小さくなったら、ずらした変数を新たな基準として
より小さな関数値になる変数を探していく……
というものですが、どうも関数が複雑な曲線を描いているらしく、
極値を数多く持っているようで、この手法ではすぐ極値につかまってしまい、
最小値にたどりつけません。
結局、変数の取りうる組み合わせを全てしらみつぶしに調べる方法にしたのですが、
充分な精度をもたせるためには膨大な計算量が必要となってしまいまったく実用的でありません。
このような多変数関数の最小値を求めるために有効なアルゴリズムはありませんでしょうか?
No.2ベストアンサー
- 回答日時:
最適化問題と呼ばれる話です。
最小化(または最大化)したい関数を「目的関数」といい、
目的関数の変数に対する拘束条件を表した式を「制約条件式」といいます。
目的関数、制約条件の性質によって解法が異なります。
典型的なものでは、
(a) 目的関数が線形で制約条件式も線形(これを線形計画問題といいます)なら「シンプレックス法」
http://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2% …
(b) 目的関数も制約条件式も非線形なら(これを非線形計画問題といいます)「ニュートン法」、「共役勾配法」など。
(c) 制約条件が離散値をとるなら(これを整数計画問題や組み合わせ最適化問題といいます)・・・解法がいろいろありすぎるほどあります(汗)
基本的な考え方はどれも同じで、
> まずある適当な変数の組み合わせを任意に決め、
> それを基準にそこから変数を少しだけずらしたとき、
> 関数の値が元よりも小さくなったら、ずらした変数を新たな基準として
> より小さな関数値になる変数を探していく……
を数学的にちゃんとやってるだけのこと。
で、近年は計算機の力を使ってガラガラポンで答えを出してしまおうと言う手法がもてはやされて、
(d) 探索空間の中からランダムに変数の値をとって来て近似最適解を求めようとするモンテカルロ法や、
(e) 局所解に陥ったら乱数で適度に変数の値を微小に揺らして局所解から脱出する機会をあたえるシミュレーテッド・アニーリング法
(f) 変数の値の組み合わせ方を遺伝子の塩基配列に見立てて、ランダムに交差を行い、優秀な遺伝子(より最適解に近いもの)をのこすジェネティックアルゴリズム
などの方法で組み合わせ問題をといてしまおうという考え方があります。
いずれにしても、問題の性質によって使うべき手法が決まります。(b)~(f)は必ず最適解が求まると言う保証がないのでお気をつけください。
力技でよければ、解空間を全探索すれば必ず最適解が求まりますが、これは現実的じゃないですからお勧めしません。
遅くなりましたがお礼申し上げます。
回答ありがとうございました。
モンテカルロ法は知っていましたが、なるほど、ランダムに計算するというのは
実はそれなりに効率の良い方法なんですね。
解空間の全探索は試したことがあるんですが、
一つの解を求めるのに数十時間かかってしまいました。
ある意味で信頼性は一番高いのですが、やっぱり現実的じゃないですね。
No.4
- 回答日時:
このような場合、必ず最小値が求まるというアルゴリズムは見つかっていません。
GA(遺伝的アルゴリズム)とか「焼き鈍し(SA)法」とかありますが、これらは、単純な勾配法(質問者さんが試された方法よりもう少し高速な方法、基本は同じ)よりも極地にとらわれない(可能性がある)というだけで、最小値が必ず求まる方法ではありません。ただ、運がよければ見つかるかもしれない、というだけです。
救いは変数が4つ程度ということです。新たに GA や SA を勉強するのが面倒であれば、質問者さんのアルゴリズムで、初期値を複数にしてその結果の中から最小値を選ぶ、というのでもいいような気もします。ただ、変数の数がもっと多くなると探索空間が広くなるので、この方法では難しいでしょう。
この回答への補足
みなさん、情報ありがとうございます。
一通り、紹介していただいたアルゴリズムを調べて、
挑戦してみたいと思います。
取り急ぎご連絡まで。
遅くなりましたがお礼申し上げます。
回答ありがとうございました。
必勝のアルゴリズムはまだ発明されていないのですね。
なんだか意外な感じがします。
初期値を複数にして、というのは試してみたのですが、
どうも、求まる解は初期値に大きく依存しているようで、
充分な精度を達成するには結構な数の初期値を試す必要があって、
結局、全探索と同じようなことになってしまいました。
どんな解空間になっているのか、一度目で見てみたいものです。
No.3
- 回答日時:
その関数が連続関数で、かつとりうる変数の範囲に制約がない(-∞から∞までとれる)なら、
Differential Evolution (DE)
というアルゴリズムがいいと思います。
遺伝的アルゴリズムの一種ですが、計算量の割にはかなり強力です。
遅くなりましたがお礼申し上げます。
回答ありがとうございました。
Differential Evolution,
日本語で言うと差分発展とか微分展開とかでしょうか?
ちょっと検索して見つけたのが以下のサイトです。
http://www.icsi.berkeley.edu/~storn/code.html
今回、自分が考えていたものは、変数が有限の範囲の制約をもっていたので、
これについては詳しく調べませんでした。
せっかく教えてくださったのに、すみません。
No.1
- 回答日時:
遺伝的アルゴリズム(Genetic Algorithm)とかですと、こういった「だまし問題」に対しても、それなりの計算時間で、それなりの性能を発揮します。
アルゴリズム入門 : 第 5 章 知識情報処理入門
http://www.microsoft.com/japan/msdn/academic/Art …
遅くなりましたが、お礼申し上げます。
回答ありがとうございました。
なるほど、遺伝的アルゴリズムというものがあるんですね。
自分はC言語をやっていますので、以下のサイトが参考になりました。
http://www6.plala.or.jp/mnagaku/cmag/ac19999/
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- Visual Basic(VBA) Excel のユーザー定義関数でソルバーが動作しない 1 2022/09/05 19:51
- 数学 数学?算数の問題です どのような解答になりますか? 2 2022/04/22 04:46
- 高校 三次関数のグラフにつきまして 3 2022/05/15 11:14
- C言語・C++・C# 3つの倍精度浮動小数点値の平均を求めて、3つの引数全てを平均値に変更するメソッドを作成し、キーボード 1 2022/07/13 16:04
- 数学 2変数関数の極値 1 2022/11/07 19:04
- 数学 2変数関数の条件つき極値問題について、 ラグランジュ未定乗数法で候補点を求めたあと、 ①ヘッセ行列の 4 2022/11/13 18:14
- 数学 条件付き極値問題といわれる問題です。ラグランジュの乗数法 について、質問したいことがあります。 条件 3 2023/05/15 21:38
- C言語・C++・C# プログラム内から、MIDIファイルの一部分だけを再生する方法 1 2023/02/15 11:08
- 数学 【高1 数学Ⅰ 二次関数】 二次関数 f(x)=x^2-4ax+8a がある。ただし、aは正の定数と 3 2022/07/23 15:46
- 数学 特定の座標点を通る回帰を行う方法について。 2 2022/10/10 10:27
関連するカテゴリからQ&Aを探す
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
正しい五十音順について
-
画像から文字を認識してテキス...
-
偏りのある乱数のアルゴリズム
-
OpenCVのライセンスについて
-
プログラミング
-
Dijkstraて
-
ルービックキューブの解法プロ...
-
ダミーヘッドを使ったリストの...
-
暗号化・復号化のアルゴリズム...
-
障害物回避プログラム
-
VBAの学習について
-
最大公約数を求めたい!
-
Visual studio2019 C#で生まれ...
-
多変数関数の最小値を求めるプ...
-
テンプレートマッチングの高速...
-
5人のテストの点数を入力すると...
-
シミュレーテッドアニーリング...
-
BCDについて
-
アルゴリズムとプロトコールの違い
-
迷路プログラム
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
正しい五十音順について
-
Dijkstraて
-
Stuck
-
BCDについて
-
[ EXCEL VBA ] 図形を読み込む...
-
期間重複チェックがわかりません
-
アルゴリズムとプロトコールの違い
-
複数の点を最短距離で全て繋ぐ...
-
グループを均等に分けるには?...
-
5人のテストの点数を入力すると...
-
ハノイの塔のさいきアルゴリズ...
-
ハッシュアルゴリズム
-
偏りのある乱数のアルゴリズム
-
C♯で電卓を作成しています。演...
-
多変数関数の最小値を求めるプ...
-
あいまい検索(文字列一致率)
-
JPEG圧縮で8×8に分割する理由に...
-
シードを考慮したトーナメント...
-
画像から文字を認識してテキス...
-
vbaで、連立方程式を解く方法に...
おすすめ情報