3

タイトルでごめんなさい。率直に言って、私の質問がナップサック問題に関連しているかどうかさえわかりません。遺伝的アルゴリズムについていくつか読んでいて、この「ナップサック問題」を見つけました。

私は正しい方向に私を蹴る誰かが必要です：

工場向けのPythonWebアプリケーションを開発しています。したがって、工場では、注文と呼ばれるものがあります。注文には1つまたは複数の製品が含まれています。不一致の概念があります。これは、実際には、特定の製品が注文に表示される量がどれだけ少ないかを示すために使用される負の数です。

列が製品で行が注文であるマトリックスを考えてみてください。すべての注文（行）にすべての製品（列）が含まれていると仮定します。ここでも、注文1から注文8および5の製品、製品1から製品5の8つの注文があります。

仮に、製品1の不一致が6であると仮定します。ランダムに、8つの注文すべてに6を均等に分割する必要があります。したがって、明らかに2つの注文には不一致の数量はありません。次に、製品2の不一致が9になります。不一致の数量を8つの注文に可能な限り均等に、ランダムに分割します。これは各製品に当てはまります。ここでキッカーが登場します。すべての注文で不一致をランダムに分割している間、注文ごとの不一致の合計（その行を意味する）を最小限に抑える必要があります。これは、注文全体の不一致の合計を可能な限り最小にする必要があることを意味します。

    |-----|-----|-----|-----|-----|
    |  P1 |  P2 |  P3 |  P4 |  P5 |
    -------------------------------
O1  |  2  |  1  |  1  |  0  |  2  |  6
    -------------------------------
O2  |  1  |  2  |  1  |  1  |  1  |  6
    -------------------------------
O3  |  2  |  2  |  1  |  0  |  1  |  6
    -------------------------------
O4  |  1  |  2  |  0  |  1  |  1  |  5
    -------------------------------
       6     7     3     2     5

わかりますか？これをPythonでコーディングする必要がありますが、どこから始めればよいのかわかりません。

4

3 に答える 3

2

最小化したい目的関数（行の合計の最大値）が線形ではないことを除いて、ほとんど整数線形計画問題があります。scipy最適化問題を解くために見てください。

このスレッド、https：//scicomp.stackexchange.com/questions/83/is-there-a-high-quality-nonlinear-programming-solver-for-pythonも役立つ場合があります。

于 2012-07-17T14:46:51.110 に答える
1

したがって、OPの問題には2つの要件があります。ランダムかつ均等です。少し矛盾しているので、「本当にランダム」は不可能だと思います。

これが私の試みです

OPの例を使用すると、4つの注文と5つの製品があります。最初の製品から始めて、数値をランダムに分割するため、各製品には少なくともfloor（6/4）=1の不一致があります。次に、残りの2つの不一致を2つの製品にランダムに配置します。

    |-----|
    |  P1 |
    -------
O1  |  2  | 2
    -------
O2  |  1  | 1
    -------
O3  |  2  | 2
    -------
O4  |  1  | 1
    -------
       6

次に、2番目の製品を処理します。同様に、最初にランダムに数値を分割するため、各製品には少なくともfloor（7/4）=1の不一致があります。残りの3つの不一致については、可能な限り均等にするために、最初にO2とO4に割り当てます。これは、前回は他の不一致より1つ少ないミスマッチであるためです。残りの1つの不一致については、製品の1つにランダムに割り当てます。

    |-----|-----|
    |  P1 |  P2 |
    -------------
O1  |  2  |  1  | 3
    -------------
O2  |  1  |  2  | 3
    -------------
O3  |  2  |  2  | 4
    -------------
O4  |  1  |  2  | 3
    -------------
       6     7

すべての製品に対してこのプロセスを繰り返します。

この方法を使用すると、可能な限り均一であることが保証され（最大の違いは1です）、ある程度のランダム性も得られます

于 2012-07-17T20:26:30.323 に答える
0

このようにするとします。

注文するアイテムのシーケンスがあります。このシーケンスは、最初の製品のアイテムと、それに続く2番目の製品のアイテムで構成されます。

最初のアイテムを最初の注文に入れ、2番目のアイテムを2番目の注文に入れ、次のように、アイテムがなくなるまで、ある時点でもう一度最初の注文にラップアラウンドします。

それはうまくいくでしょうか？

于 2012-07-17T20:09:35.693 に答える