2

01MKP の ACO を実装しようとしています。私の入力値は OR-Library mknap1.txt からのものです。私のアルゴリズムによると、最初にアイテムをランダムに選択します。次に、構築グラフの他のすべての項目の確率を計算します。確率方程式は、フェレモン レベルとヒューリスティック情報に依存します。

p[i]=(tau[i]*n[i]/Σ(tau[i]*n[i]).

私の pheremon マトリックスのセルは、初期値 (0.2) で定数値を持っています。このため、次のアイテムを見つけようとすると、フェレモン マトリックスが 0.2 のために無効になります。したがって、私の確率関数は、ヒューリスティック情報をチェックして、次に進むアイテムを決定します。ご存知のように、発見的情報方程式は

n[i]=profit[i]/Ravg.

(Ravg はリソース制約の平均です)。このため、私の問題です。関数は、最大の利益値を持つアイテムを選択します。(最初の繰り返しで、私のアルゴリズムが 600 の利益を持つアイテムをランダムに選択したとしましょう。次に、2 回目の繰り返しで、2400 の利益値を選択します。しかし、OR-Library では、2400 の利益値を持つアイテムがリソース違反を引き起こします。 2番目に選ばれたのは、利益が2400のアイテムです。

私のアルゴリズムに何か問題がありますか？ACOについて何か知っている人が私を助けてくれることを願っています. 前もって感謝します。

入力値:

6 10 3800//no of items (n) / no of resources (m) // the optimal value
 100 600 1200 2400 500 2000//profits of items (6)
 8 12 13 64 22 41//resource constraints matrix (m*n)
 8 12 13 75 22 41
 3 6  4  18 6  4
 5 10 8  32 6  12
 5 13 8  42 6  20
 5 13 8  48 6  20
 0 0  0  0  8  0
 3 0  4  0  8  0
 3 2  4  0  8  4
 3 2  4  8  8  4
 80 96 20 36 44 48 10 18 22 24//resource capacities.

私のアルゴリズム:

for i=0 to max_ant
 for j=0; to item_number
 if j==0
 {
  item=rand()%n
  ant[i].value+=profit[item]
  ant[i].visited[j]=item
 }
 else
 {
  calculate probabilities for all the other items in P[0..n]
  find the biggest P value.
  item=biggest P's item.
  check if it is in visited list
  check if it causes resource constraint.
  if everthing is ok:
   ant[i].value+=profit[item]
   ant[i].visited[j]=item
  }//end of else
 }//next j
 update pheremon matrix => tau[a][b]=rou*tau[a][b]+deltaTou
}//next i
4

0 に答える 0