1

序章

特定のタイプ（たとえば、水バケツを取り上げます）で満たされた配列を、2つの値（この場合は重量と体積）を設定して分割する必要があります。 1000未満のボリュームの合計の差（必須）。これは、完全にフェッチされた遺伝的アルゴリズムなどである必要はありませんが、私が現在持っているものよりも優れているはずです...

現在の実装

どうすればよいかわからないため、配列を2つの同じ長さの配列に分割し（配列は不均一な数のアイテムで埋めることができます）、空白の可能性のあるスポットを両方の値が0のアイテムに置き換えることから始めました。サイドは同じ量のアイテムを持っている必要はありません、私はそれ以外の方法でそれを処理する方法を知らなかっただけです。

これらを配布した後、私は次のようにそれらを最適化しようとしています：

func (main *Main) Optimize() {
    for {
        difference := main.Difference(WEIGHT)

        for i := 0; i < len(main.left); i++ {
            for j := 0; j < len(main.right); j++ {
                if main.DifferenceAfter(i, j, WEIGHT) < main.Difference(WEIGHT) {
                    main.left[i], main.right[j] = main.right[j], main.left[i]
                }
            }
        }

        if difference == main.Difference(WEIGHT) {
            break
        }
    }

    for main.Difference(CAPACITY) > 1000 {
        leftIndex := 0
        rightIndex := 0
        liters := 0
        weight := 100

        for i := 0; i < len(main.left); i++ {
            for j := 0; j < len(main.right); j++ {
                if main.DifferenceAfter(i, j, CAPACITY) < main.Difference(CAPACITY) {
                    newLiters := main.Difference(CAPACITY) - main.DifferenceAfter(i, j, CAPACITY)
                    newWeight := main.Difference(WEIGHT) - main.DifferenceAfter(i, j, WEIGHT)

                    if newLiters > liters && newWeight <= weight || newLiters == liters && newWeight < weight {
                        leftIndex = i
                        rightIndex = j
                        liters = newLiters
                        weight = newWeight
                    }
                }
            }
        }

        main.left[leftIndex], main.right[rightIndex] = main.right[rightIndex], main.left[leftIndex]
    }
}

関数：

main.Difference（const）は、2つの辺の間の絶対差を計算します。引数として取られる定数は、の差を計算するための値を決定します。

main.DifferenceAfter（i、j、const）は、2つのバケット間のスワップをシミュレートします。iは左側のバケットで、jは右側のバケットであり、結果の絶対差を計算します。定数は、チェックする値を再度決定します。

説明：

基本的に、これは重みを最適化することから始まります。これは、最初のforループが行うことです。すべての反復で、切り替えることができるバケットのすべての可能な組み合わせを試行し、その後の差が現在の差よりも小さい場合（より良い分散をもたらす）、それらを切り替えます。重みがそれ以上変化しない場合は、forループから抜け出します。完璧ではありませんが、これは非常にうまく機能し、私が達成しようとしていることに対してこれは許容できると思います。

次に、ボリュームに基づいて分散を最適化することになっているため、合計の差は1000未満です。ここでは、切り替える前に、より注意深く、実行で最適な組み合わせを検索しようとしました。したがって、最大の容量変更をもたらすバケットスイッチを検索し、これの間のトレードオフも検索することになっていますが、最初に試行したバケットの組み合わせがリットルと重量の変数を設定し、次の可能な組み合わせになるという欠陥があります。大幅に削減されています。

結論

ここにもう少し数学を含める必要があると思いますが、正直にここで立ち往生していて、ここで続行する方法がわからないので、あなたから助けを求めたいと思います。基本的に、ここで私を助けることができます。

4

2 に答える 2

2

前に述べたように、あなたの問題は実際にはボリュームの違いに制約がある制約付き最適化問題です。

数学的には、これは、ボリュームの差が1000未満であるという制約の下で、ボリュームの差を最小化することになります。線形最適化問題として表現する最も簡単な方法は次のとおりです。

min weights . x
    subject to  volumes . x < 1000.0
                for all i, x[i] = +1 or -1

a . bベクトル内積はどこにありますか。この問題が解決されると、すべてのインデックスがx = +1最初の配列に対応し、すべてのインデックスがx = -12番目の配列に対応します。

残念ながら、0-1整数計画法はNP困難であることが知られています。それを解決する最も簡単な方法は、空間の徹底的な力ずくの探索を実行することですが、すぐに手に負えなくなる可能性のあるすべての2^n可能なベクトルx（元のベクトルとベクトルnの長さ）をテストする必要があります。このトピックに関する多くの文献があり、より効率的なアルゴリズムがありますが、それらは特定の問題や制約のセットに非常に固有であることがよくあります。「線形整数計画法」をグーグルで検索して、このトピックで何が行われたかを確認できます。weightsvolumes

最も簡単なのは、ヒューリスティックベースのブルートフォース検索を実行することだと思います。この検索で​​は、ボリュームの制約から抜け出すときに検索ツリーを早期に整理し、制約の近くにとどまります（原則として、線形の解法）。最適化問題は実行可能なスペースの端にあります）。

この種の最適化について読みたいと思うかもしれないいくつかの記事があります：

最適化の記事や数学全般に精通していない場合は、ウィキペディアの記事で優れた紹介が提供されますが、このトピックに関するほとんどの記事では、すぐに適応できる（擬似）コードがすぐに示されます。

あなたnが大きい場合、ある時点で、ソリューションがどれだけ最適であるかと、それを計算できる速度との間でトレードオフを行う必要があると思います。あなたの解決策はおそらく最適ではありませんが、徹底的な検索よりもはるかに高速です。問題の正確な構成によっては、より適切なトレードオフがある場合があります。

于 2012-11-02T12:41:54.020 に答える
1

あなたの場合、重量の違いは客観的であるように見えますが、体積の違いは単なる制約です。つまり、重量の違いの属性を（可能な限り小さく）最適化し、の違いの条件を満たすソリューションを探しているということです。ボリューム属性（合計<1000）。この場合、それは単一の目的制約付き最適化問題です。

一方、多目的最適化に関心がある場合は、パレートフロンティアの概念を確認することをお勧めします：http：//en.wikipedia.org/wiki/Pareto_efficiency。これは、多様性を失わないという、さまざまな目的で利点を備えた複数の優れたソリューションを維持するのに適しています。

于 2012-11-02T02:27:34.897 に答える