1

そうですね、私は大学のプロジェクトで GA アルゴリズムを実行していますが、クロスオーバーを行っているときに、100 であるはずの個人の長さが変更されていることに気付きました。

100 個の City オブジェクト (巡回セールスマンのバージョン) の ArrayList を作成し、そこから 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 つだけを掲載します)。1 つまたは 2 つの繰り返しを太字で示しています。もっとあるかもしれませんが、1つは多すぎます！

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 の出現が 1 つだけ含まれるようにしています。

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() + ".");

popSizeが2で、shuffle結果が[1, 2]2 回である簡単な例を見てみましょう。

外側のループの最初の繰り返しの後、

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

外側のループの 2 回目の反復の後、次のようになります。

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

両方のパスに重複が含まれています。

于 2013-05-01T08:18:36.290 に答える
0

初心者の GA == 遺伝的アルゴリズムの場合。

標準的な GA 操作のいずれかにシャッフルを利用することは正しくありません。クロスオーバーでは、2 つの親があり、インデックスを見つけて、インデックスのそれらの部分を切り替えます。含まれているのがクロスオーバー方法である場合、それはまったく間違っています. 次のように見える必要があります。

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 に答える