問題タブ [mathematical-optimization]

このコードではすべてが明らかだと思いますが、このコードではコンパイル エラーが発生してい
ます。using 名前空間ディレクティブは名前空間にのみ適用できます。「System.Math」は名前空間ではなく型です

数学関数の使い方 Math クラスで使用できるすべての数学関数のリストはどこで取得できますか?

ありがとうございました。

巡回セールスマン問題 (TSP) を解決するために遺伝的アルゴリズムを実装しました。ミューテーションのみを使用すると、クロスオーバーを追加する場合よりも優れたソリューションが見つかります。通常のクロスオーバー メソッドが TSP で機能しないことはわかっているので、Ordered Crossover メソッドとPMX Crossoverメソッドの両方を実装しましたが、どちらも悪い結果に悩まされました。

私が使用している他のパラメータは次のとおりです。

変異: シングル スワップ変異または反転サブシーケンス変異 (ここで Tiendil が説明したように) で、変異率は 1% から 25% の間でテストされています。

選択: ルーレット盤の選択

フィットネス関数: 1 / ツアーの距離

母集団のサイズ: 100、200、500 をテストしました。GA も 5 回実行して、さまざまな開始母集団を用意しました。

停止条件：2500世代

同じ 26 ポイントのデータセットを使用すると、突然変異率の高い純粋な突然変異を使用して、通常、約 500 ～ 600 距離の結果が得られます。クロスオーバーを追加すると、結果は通常 800 距離の範囲になります。もう1つの紛らわしいことは、問題を解決するために非常に単純な山登りアルゴリズムも実装したことです.1000回実行すると（GAを5回実行するよりも高速です）、約410〜450の距離で結果が得られます. GAを使用してより良い結果を得るために。

クロスオーバーを追加すると GA のパフォーマンスが低下する理由について何か考えはありますか? そして、ローカル最大値を見つけたら探索する方法がないため、ローカル最大値に固執する単純なヒルクライムアルゴリズムよりもパフォーマンスがはるかに悪いのはなぜですか?

アスペクト比 Aitem (X:Y) の N 個の長方形のアイテムがあります。
縦横比が Aview の長方形の表示領域があります

項目は、表のようなレイアウト (つまり、r 行、c 列) に配置する必要があります。

個々のアイテムが最大になるように、理想的なグリッド行 x 列は何ですか? (行 * 列 >= N、もちろん - つまり、「未使用」のグリッドの場所があるかもしれません)。

単純なアルゴリズムでは、rows = 1..N を反復処理し、必要な列数を計算して、行/列のペアを最大の項目に保つことができます。

ただし、非反復アルゴリズムがあるかどうかは疑問です (たとえば、Aitem = Aview = 1 の場合、rows / cols は sqrt(N) で近似できます)。

以下のコードを検討してください。このコードは、固定レートで 1 秒のバッチでデータを処理することになっています。これは全体的なシステムの一部であり、あまり時間がかかることはありません。

1 秒相当のデータを 100 ロット以上実行すると、プログラムは 35 秒 (または 35%) かかり、この関数をループで実行します。テスト ループは、特に Ada.RealTime でタイミングが調整されます。データは事前​​に生成されるため、実行時間の大部分は間違いなくこのループにあります。

処理時間を最小限に抑えるためにコードを改善するにはどうすればよいですか?

コードは、SSE2 を備えた P3 である Intel Pentium-M で実行されます。

テスト用の擬似コード

X、Y、Z、Vx、Vy(デカルト5D)と方位角、仰角(Angular 2D)をLat Long Altに変換する式を誰かが持っていますか? ありがとう。

整数のセットであるNアイテムのセットがあります。それが順序付けられていると仮定して、 と呼びましょうI[1..N]。セットが与えられた場合、との空でない共通部分を持つcandidateサブセットを見つける必要があります。Icandidate

たとえば、次の場合:

次のように を定義しようとしていますvalid_items(items, candidate)。

I特定のセットと変数セットを最適化しようとしていcandidateます。現在、私はキャッシングでこれを行っていitems_containing[n] = {the sets which contain n}ます。上記の例では、次のようになります。

つまり、0 はどの項目にも含まれず、1 は項目 1 に含まれ、2 は項目 1 と 2 に含まれ、2 は項目 2 に含まれ、3 は項目 2 に含まれ、4 と 5 は項目 3 に含まれます。

そうすれば、定義できますvalid_items(I, candidate) = union(items_containing[n] for n in candidate)。

このユニオンの結果をキャッシュするための (妥当なサイズの) より効率的なデータ構造はありますか? スペースの明らかな例は2^N受け入れられませんが、受け入れられるNでしょN*log(N)う。

私の問題は、概念的にはアナグラムを解くのと似ていますが、辞書検索だけを使用することはできません。本当の言葉ではなく、もっともらしい言葉を見つけようとしています。

一連のテキストの文字に基づいて N-gram モデル (今のところ、N=2) を作成しました。ここで、文字のランダムなシーケンスが与えられたので、遷移確率に従って、それらを最も可能性の高いシーケンスに並べ替えたいと思います。これを始めたときは、ビタビ アルゴリズムが必要だと思っていましたが、詳しく調べてみると、ビタビ アルゴリズムは、観測された出力に基づいて一連の隠れ確率変数を最適化します。出力シーケンスを最適化しようとしています。

これについて読むことができるよく知られたアルゴリズムはありますか? それとも、Viterbi で正しい方向に進んでいるのに、それを適用する方法がわかりませんか?

アップデート

この問題についてより多くの洞察を求めるために報奨金を追加しました。(効率的なアプローチが不可能な理由を説明する分析、シミュレーテッド アニーリング以外のヒューリスティック/近似など)

C# の二次計画問題を解決する無料のパッケージを知っている人はいますか?

私はググっていくつか見つけました。しかし、どれが最高で最速かを判断するのは困難です。お気に入りの人はいますか？

私は次のようなアルゴリズムを探しています：

重なり合う可能性のある長方形のセット（すべて「回転されていない」、（左、上、右、下）の連符などとして均一に表すことができる）が与えられると、（回転されていない）最小のセットが返されます。同じ領域を占める重複しない長方形。

一見簡単そうに見えますが、注意が必要です（少なくとも効率的に実行するため）。

この/アイデア/ポインタの既知の方法はありますか？

必ずしも最小ではないが、ヒューリスティックに小さいセットのメソッドも興味深いので、有効な出力セットを生成するメソッドも興味深いものです。

私は最適化問題についてほとんど知らないので、うまくいけば、これは私にとって教訓になるでしょう：

ウィジェットの数とローターの数が固定されている場合、各ウィジェットとローターを1回しか使用できない合計値を最大化する、一連のウィジェットとローターのペアを取得するにはどうすればよいでしょうか。