2

我正在尝试为 01MKP 实施 ACO。我的输入值来自 OR-Library mknap1.txt。根据我的算法，首先我随机选择一个项目。然后我计算构造图上所有其他项目的概率。概率方程取决于信息素水平和启发式信息。

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

我的信息素矩阵的单元格在初始值 (0.2) 时具有恒定值。出于这个原因，当我试图找到下一个项目时，由于 0.2，pheremon 矩阵变得无效。所以，我的概率函数确定下一个要走的项目，检查启发式信息。如你所知，启发式信息方程是

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

（Ravg 是资源约束的平均值）。出于这个原因，我的概率。功能选择具有最大利润价值的项目。（假设在第一次迭代中，我的算法随机选择了一个具有 600 利润的项目。然后在第二次迭代中，选择 2400 利润值。但是，在 OR-Library 中，具有 2400 利润值的项目会导致资源违规。无论我做，第二个选择的是有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