問題定義

サラリーマンがナップザックを担いで走り回っている。各拠点には、Itemが落ちている。Itemには価値と重さが設定されており、サラリーマンが持つことができる最大重さが決まっている。サラリーマンは必要な拠点にのみ訪問し、ナップザックにItemを入れていく。

目標

• 最短のルートかつ必要な場所のみを巡回し、最大のItem価値を目指す。

条件と制約

• サラリーマン
  • 制約
    • 人数
      • 1
    • サラリーマンが持てる荷物の最大容量は設定しないものの、少ないほど良いとする
• Item
  • 各Itemには容量と価値、Itemの座標が設定されている。
    • 制約
      • 容量
        • 0 < w <= 10
      • 価値
        • 0 < v <= 10
• 拠点
  • 各拠点には複数のItemが落ちている。その中から1つだけアイテムを拾うことができる。
    • 制約
      • 拠点数
        • 10 <= n <= 100
      • Item数
        • 5で固定
      • 座標
        • 1 <= (x, y), <= 1000
      • 座標 (0, 0)をスタート地点とする。
• 移動距離と時間
  • 座標で1の長さを移動するのに1の時間がかるとする。

適応度

• min(1/(ナップサックの内のItem価値の合計), 移動距離, 総重量)とする。

遺伝子設計

• 遺伝子を固定長とする。各遺伝子に対して、訪れる、訪れないを選択する遺伝子を入れる。 [(訪問の有無, 訪問する拠点ID, 拾うItemID)]

考察

• トータルのdistanceが大きくなる方向に働きやすい。よって、distanceを減らしつつ、減らしてもfitnessが大きく変わらないような工夫を加える必要がある。
  • 試しにindividualクラスにshave_geneという、確率で遺伝子長を半分にするメソッドを入れたものの効果なし。
• 山田さんより: 最適化する関数をmin(x,y)のような形にした方が良い。悪い部分を修正するようにする。