OptHub

群集シミュレーションを用いた発生交通量推定

2022年 進化計算コンペ 単目的部門の問題
群集シミュレーションを用いた発生交通量推定

Input / Output

When submitting a solution to a match, please make sure to meet the following conditions.

sop-demo1(チュートリアル問題)

sop-demo1では全ての参加者がルート誘導に従うと仮定します.ルート誘導に従うエージェント(Guided)のみでシミュレーションを行うため,各時間のGuidedエージェントの出発人数を最適化してください.エージェントタイプは一つであるため,決定変数は長さ300の1次元配列です.配列の各要素は0以上45以下の整数です.配列の総和,すなわちエージェントの総数は4500です.sop-demo1は混合ガウス分布を用いて作成した単純な出発人数ヒストグラムを使用しています.sop-1, sop-2の出発人数ヒストグラムとは傾向が異なりますので注意して下さい.

入力フォーマット

長さ300の1次元整数配列です.

時刻 人数(Guided) 探索範囲
19:00 variable[0] 0, 1, ..., 45
19:01 variable[1] 0, 1, ..., 45
... ... ...
23:59 variable[299] 0, 1, ..., 45
入力フォーマットの例
[6,6,6,6,7,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,11,11,11,12,12,12,12,13,13,13,14,14,14,15,15,15,16,16,16,17,17,17,18,18,18,19,19,19,20,20,20,21,21,21,22,22,22,23,23,23,24,24,24,25,25,25,26,26,26,26,27,27,27,28,28,28,28,29,29,29,29,29,30,30,30,30,30,31,31,31,31,31,31,31,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,32,31,31,31,31,31,31,31,30,30,30,30,30,29,29,29,29,28,28,28,28,27,27,27,27,26,26,26,25,25,25,24,24,24,24,23,23,23,22,22,22,21,21,21,20,20,19,19,19,18,18,18,17,17,17,16,16,16,15,15,15,15,14,14,14,13,13,13,12,12,12,11,11,11,11,10,10,10,10,9,9,9,8,8,8,8,8,7,7,7,7,6,6,6,6,6,5,5,5,5,5,5,4,4,4,4,4,4,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
制約条件
  • 制約条件1: エージェントの合計
    m=1MGuided(tm)=4500\sum^{M}_{m=1} {\rm Guided}(t_m) = 4500
  • 制約条件2: 各時刻の人数合計
    0Guided(tm)450 \leq {\rm Guided}(t_m) \leq 45

Guided(tm){\rm Guided}(t_m) : 時刻 tmt_m におけるGuidedエージェントの発生人数

出力フォーマット

"id", "objective", "constraint", "info", "score", "evaluation_error", "scoring_error"をキーにもつJSONオブジェクトです.

  • "id"は送信した各解に割り振られる固有のidです.
  • "objective"には ϵobs\epsilon^{\rm obs} (目的関数値)が入ります.
    制約条件を違反している場合でも(異常に大きな値を入れるなどしてシミュレーションが実行不可能な場合を除いて)目的関数値は正しく計算されます.実行不可能解の目的関数値を探索に用いることはできますが,"score"には反映されませんのでご注意ください.
  • "constraint"には制約条件1, 2に対する違反量が入ります.実行可能解は両方の違反量が0となります.
    constraint1: 4,500m=1MGuided(tm)|4,500 - \sum^{M}_{m=1} {\rm Guided}(t_m)|
    constraint2: m=1Mmax(Guided(tm)45,0)\sum^{M}_{m=1} \max({\rm Guided}(t_m)-45, 0)
  • "info"にはカメラのデータと各Tracked Agentに対する評価値が格納されます.
  • "score"はあなたがこれまでこの問題に送信した解の最小目的関数値です.
  • "evaluation_error"にはシミュレーションの実行時にエラーが発生した場合のエラーメッセージが格納されます.
  • "scoring_error"にはシミュレーション結果を出力フォーマットに変換する際にエラーが発生した場合のエラーメッセージが格納されます.

infoのフォーマットは以下の通りです.

"info": [
  [カメラのデータ],
  [
    [Route1のTracked Agentの各評価値],
    [Route2のTracked Agentの各評価値],
    [Route3のTracked Agentの各評価値]
  ]
]
  • カメラのデータは,目的関数の ϵdest\epsilon^{\rm dest} に含まれる N^dest(tm)\hat N^{\rm dest}(t_m) です.シミュレーション上で時刻 tmt_{m} に駅に到着したエージェントの数を示します.実際に観測された到着人数 Ndest(tm)N^{\rm dest}(t_m) は,以下のJSONファイルを参照してください.

==これらのカメラのデータおよび上記のJSONファイルはガウシアンフィルタ適用前のデータとなります.$\epsilon^{\rm dest}$を計算する際には,どちらのデータに対してもガウシアンフィルタを適用する必要がありますのでご注意ください.==

  • Tracked Agentの各評価値は,目的関数の ϵˉpac\bar{\epsilon}^{\rm pac} に含まれる 1Mam=1Ma(P(a,tm)P^(a,tm))2\frac{1}{M_a} \sum_{m = 1}^{M_a} (P(a, t_m) - \hat{P}(a, t_m))^2 です.Tracked Agentごとの評価値を示します.それぞれのRouteで10分毎にTracked Agentが発生するため[3]×[30]の実数値配列となります.
出力フォーマットの例
{"id": 110435, "objective": 52.77159060743308, "constraint": [0, 0], "info": [[0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 7.0, 4.0, 8.0, 4.0, 5.0, 11.0, 4.0, 10.0, 5.0, 9.0, 9.0, 6.0, 9.0, 9.0, 11.0, 8.0, 9.0, 11.0, 8.0, 13.0, 8.0, 10.0, 9.0, 16.0, 3.0, 0.0, 22.0, 7.0, 0.0, 16.0, 10.0, 6.0, 0.0, 21.0, 7.0, 0.0, 16.0, 11.0, 7.0, 26.0, 32.0, 16.0, 0.0, 16.0, 12.0, 28.0, 0.0, 32.0, 23.0, 1.0, 15.0, 13.0, 14.0, 3.0, 32.0, 30.0, 7.0, 34.0, 17.0, 7.0, 7.0, 33.0, 31.0, 33.0, 17.0, 30.0, 7.0, 0.0, 32.0, 34.0, 14.0, 16.0, 33.0, 34.0, 13.0, 32.0, 33.0, 2.0, 32.0, 35.0, 23.0, 34.0, 32.0, 34.0, 6.0, 16.0, 33.0, 33.0, 13.0, 32.0, 33.0, 18.0, 16.0, 33.0, 31.0, 1.0, 33.0, 34.0, 26.0, 32.0, 34.0, 28.0, 32.0, 33.0, 34.0, 33.0, 16.0, 34.0, 32.0, 11.0, 33.0, 34.0, 22.0, 29.0, 34.0, 18.0, 7.0, 33.0, 33.0, 7.0, 31.0, 33.0, 26.0, 32.0, 33.0, 34.0, 33.0, 32.0, 34.0, 34.0, 21.0, 32.0, 34.0, 33.0, 22.0, 34.0, 30.0, 13.0, 33.0, 33.0, 7.0, 32.0, 33.0, 20.0, 33.0, 34.0, 36.0, 34.0, 17.0, 32.0, 34.0, 20.0, 34.0, 33.0, 32.0, 18.0, 34.0, 34.0, 14.0, 32.0, 33.0, 24.0, 31.0, 33.0, 24.0, 33.0, 34.0, 36.0, 32.0, 16.0, 30.0, 29.0, 8.0, 33.0, 35.0, 2.0, 15.0, 34.0, 25.0, 1.0, 32.0, 34.0, 2.0, 32.0, 33.0, 31.0, 0.0, 34.0, 16.0, 32.0, 15.0, 1.0, 16.0, 2.0, 19.0, 28.0, 0.0, 16.0, 5.0, 6.0, 7.0, 11.0, 7.0, 0.0, 16.0, 6.0, 2.0, 11.0, 15.0, 10.0, 0.0, 14.0, 6.0, 9.0, 0.0, 4.0, 8.0, 8.0, 12.0, 10.0, 9.0, 0.0, 1.0, 7.0, 2.0, 10.0, 0.0, 5.0, 1.0, 0.0, 6.0, 1.0, 7.0, 0.0, 10.0, 2.0, 2.0, 7.0, 4.0, 4.0, 4.0, 1.0, 1.0, 3.0, 2.0, 2.0, 1.0, 1.0, 1.0, 2.0, 0.0, 1.0, 0.0, 2.0, 1.0, 0.0, 2.0, 0.0, 2.0, 1.0, 1.0, 1.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0], [[0.0, 0.571168786246563, 1.5375287800716801, 6.519211650920848, 3.3610123275847408, 6.185471905442011, 19.62656333348374, 53.826689426948114, 22.801082927628023, 26.29251457706631, 39.385419188317925, 39.62478217446185, 30.934674224384345, 4.53646878948068, 7.614573222153033, 14.51173976525453, 27.7415236189467, 44.68574256220237, 91.16350434328677, 68.71703424160648, 37.096351374103904, 0.7537313680111996, 1.359186327683925, 2.0694177797716735, 5.142799316210169e-06, 0.021849784458950996, 8.092688336991247e-06, 0.5661020932452587, 0.566319161692769, 0.5661020932452587], [1.6765780760231297, 1.5547867339742945, 1.420856648561899, 0.016241865833810036, 0.5498613732747181, 13.547921692546998, 1.2067633100563544, 12.02853028618408, 22.25967127623541, 1.7282715859571933, 4.957146121525968, 43.221302003458554, 17.30829350316043, 29.22455626786185, 79.1605935893076, 103.46782367002896, 146.0305559798592, 186.90974046850567, 161.82867552104534, 123.68219371095257, 74.26669037829546, 5.286470450969449, 2.0542717055696644, 2.485566253546687, 0.5771017455501588, 0.8820528396675664, 1.6184984365504915, 1.343110140300239, 0.694471470150408, 0.12544688242684124], [1.709023704490396, 2.239886207915846, 1.6073605470825802, 0.4272558095209209, 0.8300130895982601, 40.9720897511046, 5.723012773325591, 2.040997320387061, 57.933511188311776, 1.6765957540007548, 6.131762781529624, 55.35321301685309, 26.785511334830478, 112.38171213955974, 133.86724477898682, 174.61766599823608, 234.75834424478273, 286.94165422958145, 273.470110674851, 192.0526220667677, 97.81150504637813, 1.3214071742818132, 0.9469705083089777, 2.1981247383389437, 0.7802617008510662, 0.5665535101580099, 1.5723751625772202, 2.319520404023387, 0.5665537761582486, 0.021856186933591048]]], "score": 52.77159060743308, "evaluation_error": null, "scoring_error": null}

sop-demo2(チュートリアル問題)

sop-demo2は各時間に出発した人数だけでなく,その歩行者の属性(エージェントタイプ)も推定する問題です.ルート誘導に従うエージェント(Guided)に加えてBusyとSlowエージェントの出発人数を最適化してください.3種類のエージェントを合計した人数は4500人です.決定変数はサイズ3×300の2次元配列(属性×時刻)です.sop-demo2は混合ガウス分布を用いて作成した単純な出発人数ヒストグラムを使用しています.sop-1, sop-2の出発人数ヒストグラムとは傾向が異なりますので注意して下さい.

入力フォーマット

サイズ3×300の2次元整数配列です.

時刻 人数(Guided) 人数(Busy) 人数(Slow)
19:00 variable[0][0] variable[l][0] variable[2][0]
19:01 variable[0][1] variable[1][1] variable[2][1]
... ... ... ...
23:59 variable[0][299] variable[1][299] variable[2][299]
入力フォーマットの例
[[6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,9,9,9,9,9,9,9,10,10,10,10,10,10,11,11,11,11,11,11,11,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,17,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,15,15,15,15,15,15,15,15,15,15,15,14,14,14,14,14,14,14,14,13,13,13,13,13,13,13,13,12,12,12,12,12,12,12,11,11,11,11,11,11,11,10,10,10,10,10,10,9,9,9,9,9,9,9,8,8,8,8,8,8,8,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,5,5,5,5,5,5,5,5,5,4,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,7,7,7,7,7,7,7,7,7,6,6,6,6,6,6,6,5,5,5,5,5,5,4,4,4,4,4,4,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]
制約条件
  • 制約条件1
    変数の合計 m=1M(Guided(tm)+Busy(tm)+Slow(tm))=4500\sum^{M}_{m=1} ({\rm Guided}(t_m) + {\rm Busy}(t_m) + {\rm Slow}(t_m)) = 4500
    Guided(tm){\rm Guided}(t_m) : 時刻 tmt_m におけるGuidedエージェントの発生人数
    Busy(tm){\rm Busy}(t_m) : 時刻 tmt_m におけるBusyエージェントの発生人数
    Slow(tm){\rm Slow}(t_m) : 時刻 tmt_m におけるSlowエージェントの発生人数
  • 制約条件2
    各時刻の人数合計  0Guided(tm)+Busy(tm)+Slow(tm)450 \leq {\rm Guided}(t_m) + {\rm Busy}(t_m) + {\rm Slow}(t_m) \leq 45
出力フォーマット

sop-demo1と同じです.

sop-1

sop-1では全ての参加者がルート誘導に従うと仮定します.ルート誘導に従うエージェント(Guided)のみでシミュレーションを行うため,各時間のGuidedエージェントの出発人数を最適化してください.エージェントの総数は4660エージェントタイプは一つであるため,決定変数の長さは300です.

入力フォーマット

sop-demo1と同じです.

制約条件
  • 制約条件1: エージェントの合計
    m=1MGuided(tm)=4660\sum^{M}_{m=1} {\rm Guided}(t_m) = 4660
  • 制約条件2: 各時刻の人数合計
    0Guided(tm)450 \leq {\rm Guided}(t_m) \leq 45

Guided(tm){\rm Guided}(t_m) : 時刻 tmt_m におけるGuidedエージェントの発生人数

出力フォーマット

sop-demo1と同じです.

sop-2

sop-2は各時間に出発した人数だけでなく,その歩行者の属性(エージェントタイプ)も推定する問題です.ルート誘導に従うエージェント(Guided)に加えてBusyとSlowエージェントの出発人数を最適化してください.3種類のエージェントを合計した人数は4079人です.

入力フォーマット

sop-demo2と同じです.

制約条件
  • 制約条件1
    変数の合計 m=1M(Guided(tm)+Busy(tm)+Slow(tm))=4079\sum^{M}_{m=1} ({\rm Guided}(t_m) + {\rm Busy}(t_m) + {\rm Slow}(t_m)) = 4079
    Guided(tm){\rm Guided}(t_m): 時刻 tmt_m におけるGuidedエージェントの発生人数
    Busy(tm){\rm Busy}(t_m): 時刻 tmt_m におけるBusyエージェントの発生人数
    Slow(tm){\rm Slow}(t_m): 時刻 tmt_m におけるSlowエージェントの発生人数
  • 制約条件2
    各時刻の人数合計  0Guided(tm)+Busy(tm)+Slow(tm)450 \leq {\rm Guided}(t_m) + {\rm Busy}(t_m) + {\rm Slow}(t_m) \leq 45
出力フォーマット

sop-demo2と同じです.

補足

計算時間の観点から実際の花火大会に相当する数万人のエージェントを用いたシミュレーションをそのまま出題することは困難でした.そこで本コンペティションでは,これまでの調査で得られた測定データから推定した出発人数ヒストグラムをもとに歩行者の総数が4000人程度となるようスケールダウンした問題を作成しました.また,人工ヒストグラムを入力としてシミュレーションから得られた到着人数,移動軌跡の情報を誤差評価に用いる実観測データとしています.

シミュレーション可視化ツール

sop-demoのシミュレーションを行い,シミュレーション内容を動画化できます.内容理解の参考にお使いください.
下記のコマンドにより,カレントディレクトリに"output.mp4"が作成されます.

# echo [val1,val2,...,val300] | docker run -v "$(pwd)":/output --rm -i tkmnet/masbench-video:latest
# 下の例ではパラメータの数を省略しています.作成完了には数分かかります.

echo [10,10,10,10,10,10,10] | docker run -v "$(pwd)":/output --rm -i tkmnet/masbench-video:latest

実行にはDockerが必要です.Dockerのインストール方法は,Docker公式のドキュメントを参照してください.
(Snappy(snapコマンド)でインストールしたDockerの場合,Dockerの実行自体がサンドボックス化されるため,カレントディレクトリに出力がされないので注意してください.)