1

是的，我正在为一个大学项目做一个 GA 算法，但是当我做 Crossover 时，我注意到我的个人长度发生了变化，它应该是 100。

我正在创建一个包含 100 个 City 对象的 ArrayList（它是 Traveling Salesman 的一个版本），并从中创建一个包含 100 个 Id 数字的路径并将其传递给 String[]。id 从 0 到 99。但是，当我使用 Collections 类进行随机播放时，它正在随机播放它们，但它也是重复的条目。这是代码。

Random r = new Random(seed);
for (int i = 0; i < popSize; i++){ // popSize is population size which is 100 normally
    Collections.shuffle(baseInd, r); //baseInd is the ArrayList of 100 City objects
    for (int ii = 0; ii < baseInd.size(); ii++){
        indPath[ii] += String.valueOf(baseInd.get(ii).getID() + "."); // This is getting the current baseInd and outputting the ID to a String.
    }
    indDist[i] = Double.toString(calculateDistance(baseInd)); //method to calculate the distance from start to end on a individual.

}

这是当前的示例输出（我只会发布前 3 个，因为它很冗长）并且我已经加粗了一两次重复。可能有更多，但一个太多了！

0：60+74+94+39+13+76+42+60+59+27+3+19+13+44+90+33+3+84+94+66+26+15+30+65+ 75+37+82+86+97+60+54+10+72+22+87+59+68+82+58+33+94+13+70+58+54+31+93+25+91+ 10+94+14+89+73+39+67+12+41+99+46+28+62+32+96+37+46+9+81+33+36+42+ 77 +1+21+ 39+61+41+81+23+73+42+13+66+35+51+64+2+11+96+87+75+24+50+8+86+52+32+35+73+ 77+距离：13781+834427040787

1：2+89+43+7+58+32+71+44+96+63+2+57+12+34+53+43+94+14+97+18+91+40+18+86+ 46+70+46+46+46+98+50+0+45+44+94+34+17+ 89 +72+1+9+99+40+97+ 88 +3+12+38+5+ 41+2+26+74+96+33+33+29+16+74+18+10+13+96+12+16+76+77+2+0+ 89 +18+36+88+56+ 35+33+28+ 88 +35+86+61+98+99+66+31+90+23+86+45+74+2+88+80+84+19+33+81+23+90+ 37+ 距离：14157+066270019255

2：69+13+20+68+8+80+58+26+57+1+45+73+83+13+32+58+10+17+76+25+99+29+28+31+ 68+95+88+91+19+22+86+97+75+64+1+49+19+88+55+96+3+62+23+ 45 +31+63+39+52+70+ 70+35+2+86+49+34+49+7+2+72+37+37+81+46+23+82+7+35+65+74+64+80+43+48+3+ 5+46+35+30+94+55+47+ 45 +79+83+58+40+95+94+98+84+28+94+61+87+1+40+83+55+18+ 74+ 距离：13178+332276530997

}

我确保 baseInd 仅包含 0 到 99 的一次出现。

for (int a = 0; a < baseInd.size(); a++){
    System.out.print(baseInd.get(a).getID() + "+");
}

它肯定似乎（也许！）是造成它的洗牌。有任何想法吗？

--- 更多代码 ----

这是创建 City 对象的方法。它从 .csv 文件中读取。我不关心这个，因为上面的代码在任何洗牌之前都会打印出 0 到 99。

public static ArrayList<City> createBaseInd(ArrayList<City> baseInd){

            BufferedReader reader;
            try {
                reader = new BufferedReader(new FileReader("towns.csv"));
        String line;
        String[] lines;

        while ((line = reader.readLine()) != null)
        {
            lines = line.split(",");
            baseInd.add(new City(lines[0], Double.parseDouble(lines[1]), Double.parseDouble(lines[2]), Integer.parseInt(lines[3]))); //Struct is Name, X Co Ord, Y Co Ord, ID
        }
        reader.close();
    } catch (IOException e) {
        System.out.println("file not found");
                e.printStackTrace();
            }

        return baseInd;
}

没有什么我可以真正添加与问题相关的内容，因为问题发生在创建 baseInd 并且在输出的此时尚未编辑输出（通过突变或交叉）之后。

4

2 回答 2

2

您应该将内部循环中的索引从

indPath[ii] += String.valueOf(baseInd.get(ii).getID() + ".");

至

indPath[i] += String.valueOf(baseInd.get(ii).getID() + ".");

让我们看一个简单的例子 where popSizeis2和两次的shuffle结果：[1, 2]

在外循环的第一次迭代之后，你有

indPath[0] => 1.
indPath[1] => 2.

在外循环的第二次迭代之后，你有

indPath[0] => 1.1.
indPath[1] => 2.2.

两条路径都包含重复项。

于 2013-05-01T08:18:36.290 回答
0

对于未启动的 GA == 遗传算法。

对任何标准 GA 操作使用 shuffle 都是不正确的。通过交叉，你有两个父母，你找到一个索引，并切换索引的那些部分。如果包含的是您的交叉方法，那是完全错误的。它需要看起来像这样：

public TwoParents crossOver(ArrayList<> parentA, ArrayList<> parentB) {

  TwoParents toReturn = new TwoParents();  //This holds the new parent A and B.

  int index = r.nextInt(parentA.size());  //The crossover point

  //This is the copying part
  for(int i = 0;i<index;i++) {
    toReturn.parentA.add(parentA[i]);
    toReturn.parentB.add(parentB[i]);
  }

  //Now we crossover
  for(int i = index;i<parentA.size();i++) {
    toReturn.parentA.add(parentB[i]);
    toReturn.parentB.add(parentA[i]);
  }

  //return both parents
  return toReturn;
}

这是一个有趣的应用程序，但如果你必须访问所有城市，那么变异不是适用的运算符。

于 2013-05-01T08:04:45.780 回答