次のようにコードをコピーします。
java.util.* をインポートします。
パブリック クラス Tsp {
private String cityName[]={"北京"、"上海"、"天津"、"重慶"、"ハルビン"、"長春"、"瀋陽"、"フフホト"、"石家荘"、"太原"、"済南" 、「鄭州」、「西安」、「蘭州」、「銀川」、「西寧」、「ウルムチ」、「合肥」、「南京」、「杭州」、「長沙」、「南昌」、「武漢」 、「成都」、「貴州」、「福建」、「台北」、「広州」、「海口」、「南寧」、「昆明」、「ラサ」、「香港」、「マカオ」};
//private String cityEnd[]=new String[34];
private int cityNum=cityName.length;//都市の数
private int PopSize = 50;
private int maxgens = 20000;
private double pxover = 0.8;
private double pmulation = 0.05;
プライベートロング[][] 距離 = 新しいロング[都市番号][都市番号];
private int range = 2000; //停止するタイミングを決定するために使用される配列範囲
プライベート クラスの遺伝子型 {
int city[] = new int[cityNum] //単一遺伝子の都市配列
長いフィットネス // この遺伝子のフィットネス
double selectP; //選択確率
doubleExceptp; // 期待される確率
int isSelected //選択されているかどうか
}
プライベート ジェノタイプ[] 都市 = 新しいジェノタイプ[ポップサイズ];
/**
* コンストラクター、人口を初期化します
*/
パブリック Tsp() {
for (int i = 0; i < PopSize; i++) {
都市[i] = 新しい遺伝子型();
int[] num = 新しい int[cityNum];
for (int j = 0; j < cityNum; j++)
num[j] = j;
int temp = 都市番号;
for (int j = 0; j < cityNum; j++) {
int r = (int) (Math.random() * temp);
都市[i].都市[j] = 数値[r];
num[r] = num[temp - 1];
温度--;
}
都市[i].フィットネス = 0;
都市[i].selectP = 0;
都市[i].excelp = 0;
都市[i].isSelected = 0;
}
initDistance();
}
/**
* 各集団の各遺伝的個体について適応度、選択確率、期待確率、選択されるかどうかを計算します。
*/
public void CalAll(){
for(int i = 0; i< PopSize; i++){
都市[i].フィットネス = 0;
都市[i].selectP = 0;
都市[i].excelp = 0;
都市[i].isSelected = 0;
}
CalFitness();
CalSelectP();
CalExceptP();
CalIsSelected();
}
/**
* 塗りつぶし、選択されていない個人に複数の選択を塗りつぶします
*/
パブリックボイドパッド(){
int ベスト = 0;
int bad = 0;
while(true){
while(citys[best].isSelected <= 1 && best<popSize-1)
最高++;
while(citys[bad].isSelected != 0 && bad<popSize-1)
悪い++;
for(int i = 0; i< cityNum; i++)
都市[悪い].都市[i] = 都市[最高].都市[i];
都市[最高].isSelected --;
都市[悪い].isSelected++;
悪い++;
if(最高 == ポップサイズ || 悪い == ポップサイズ)
壊す;
}
}
/**
*クロスサブジェクト機能
*/
パブリック void クロスオーバー() {
int x;
int y;
int Pop = (int)(popSize* pxover /2);
while(ポップ>0){
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
executeCrossover(x,y);//xy 2 つのエンティティがクロスオーバーを実行します
ポップ - ;
}
}
/**
* クロスオーバー機能の実行
* @param 個別の x
* @param 個別 y
* 個々の x と個々の y の最良の点セットの交差を実行して、次世代の都市シーケンスを生成します
*/
private voidexecuteCrossover(int x,int y){
整数次元 = 0;
for( int i = 0 ;i < cityNum; i++)
if(都市[x].都市[i] != 都市[y].都市[i]){
次元++;
}
int diffItem = 0;
double[] diff = 新しい double[次元];
for( int i = 0 ;i < cityNum; i++){
if(都市[x].都市[i] != 都市[y].都市[i]){
diff[diffItem] = 都市[x].都市[i];
都市[x].都市[i] = -1;
都市[y].都市[i] = -1;
diffItem++;
}
}
Arrays.sort(diff);
double[] temp = 新しい double[次元];
temp = gp(x, 次元);
for(int k = 0; k< 次元;k++)
for(int j = 0; j< 次元; j++)
if(temp[j] == k){
double item = temp[k];
温度[k] = 温度[j];
temp[j] = アイテム;
項目 = 差分[k];
diff[k] = diff[j];
diff[j] = アイテム;
}
int tempDimension = ディメンション;
int tempi = 0;
while(tempDimension> 0 ){
if(都市[x].都市[tempi] == -1){
city[x].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi++;
}
Arrays.sort(diff);
temp = gp(y, 次元);
for(int k = 0; k< 次元;k++)
for(int j = 0; j< 次元; j++)
if(temp[j] == k){
double item = temp[k];
温度[k] = 温度[j];
temp[j] = アイテム;
項目 = 差分[k];
diff[k] = diff[j];
diff[j] = アイテム;
}
tempDimension = 寸法;
テンポ = 0;
while(tempDimension> 0 ){
if(都市[y].都市[tempi] == -1){
都市[y].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi++;
}
}
/**
* @param 個人個人
* @param ディメンションディメンション
* @return 最適な点セット (cross 関数に使用される交点) は、executeCrossover() 関数で使用されます。
*/
private double[] gp(int 個別, int ディメンション){
double[] temp = 新しい double[次元];
double[] temp1 = 新しい double[次元];
int p = 2 * 次元 + 3;
while(!isSushu(p))
p++;
for(int i = 0; i< 次元; i++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (個人+1);
temp[i] = temp[i] - (int)temp[i];
if(温度[i]<0)
温度[i] = 1+温度[i];
}
for(int i = 0; i< 次元; i++)
temp1[i] = temp[i];
Arrays.sort(temp1);
//選別
for(int i = 0; i< 次元; i++)
for(int j = 0; j< 次元; j++)
if(temp[j]==temp1[i])
temp[j] = i;
戻り温度;
}
/**
* 突然変異
*/
パブリック void mutate(){
ダブルランダム;
内部温度;
int temp1;
int temp2;
for(int i = 0; i< PopSize; i++){
ランダム = Math.random();
if(ランダム<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
temp = 都市[i].都市[temp1];
都市[i].都市[temp1] = 都市[i].都市[temp2];
都市[i].都市[temp2] = 温度;
}
}
}
/**
* 現在の代数のすべての都市シーケンスとその関連パラメーターを出力します。
*/
public void print(){
/**
* 都市間の距離を初期化します
*/
private void initDistance(){
for (int i = 0; i < cityNum; i++) {
for (int j = 0; j < cityNum; j++){
距離[i][j] = Math.abs(ij);
}
}
}
/**
* すべての都市シーケンスの適合度を計算します
*/
private void CalFitness() {
for (int i = 0; i < PopSize; i++) {
for (int j = 0; j < cityNum - 1; j++)
都市[i].フィットネス += 距離[都市[i].都市[j]][都市[i].都市[j + 1]];
都市[i].フィットネス += 距離[都市[i].都市[0]][都市[i].都市[都市番号 - 1]];
}
}
/**
* 選択確率の計算
*/
private void CalSelectP(){
長い合計 = 0;
for(int i = 0; i< PopSize; i++)
合計 += 都市[i].フィットネス;
for(int i = 0; i< PopSize; i++)
city[i].selectP = (double)citys[i].fitness/sum;
}
/**
* 期待確率の計算
*/
プライベート void CalExceptP(){
for(int i = 0; i< PopSize; i++)
city[i].excelp = (double)citys[i].selectP * PopSize;
}
/**
* 都市の順序が優れているかどうかを計算し、より優れたものが選択され、次の世代に入力されます
*/
private void CalIsSelected(){
int needSelecte = ポップサイズ;
for(int i = 0; i< PopSize; i++)
if(都市[i].excel<1){
都市[i].isSelected++;
needSelecte --;
}
double[] temp = 新しい double[popSize];
for (int i = 0; i < PopSize; i++) {
// temp[i] = city[i].excelp - (int) city[i].excel;
// 温度[i] *= 10;
temp[i] = 都市[i].例外*10;
}
int j = 0;
while (needSelecte != 0) {
for (int i = 0; i < PopSize; i++) {
if ((int) temp[i] == j) {
都市[i].isSelected++;
必要選択--;
if (needSelecte == 0)
壊す;
}
}
j++;
}
}
/**
* @paramx
* 数値が素数かどうかを判断する @return 関数
*/
プライベートブール値 isSushu(int x){
if(x<2) は false を返します。
for(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) は false を返します。
true を返します。
}
/**
* @param x 配列
* @return x配列の値がすべて等しいかどうか。等しい場合、x.length生成の最適な結果が同じであることを意味し、アルゴリズムは終了します。
*/
プライベートブール値 isSame(long[] x){
for(int i = 0; i< x.length -1; i++)
if(x[i] !=x[i+1])
false を返します。
true を返します。
}
/**
* あらゆる世代に対して最適なパスシーケンスを出力します
*/
private void printBestRoute(){
CalAll();
長期 = 都市[0].フィットネス;
int インデックス = 0;
for (int i = 1; i < PopSize; i++) {
if(citys[i].fitness<temp){
temp = 都市[i].フィットネス;
インデックス = i;
}
}
System.out.println();
System.out.println("最適なパス シーケンス:");
for (int j = 0; j < cityNum; j++)
{
文字列 cityEnd[]={cityName[citys[index].city[j]]};
for(int m=0;m<cityEnd.length;m++)
{
System.out.print(cityEnd[m] + " ");
}
}
//System.out.print(citys[index].city[j] + cityName[citys[index].city[j]] + " ");
//System.out.print(cityName[citys[index].city[j]]);
System.out.println();
}
/**
* アルゴリズムの実行
*/
public void run(){
long[] 結果 = 新しいlong[範囲];
//結果はすべての数値が等しくないように初期化されます
for(int i = 0; i< 範囲; i++)
結果[i] = i;
int Index = 0; //配列内の位置
int num = 1 //第数世代;
while(maxgens>0){
System.out.println("----------------- "+num+" 生成---------------------- - ----");
CalAll();
プリント();
パッド（）;
クロスオーバー();
変異();
maxgens --;
長期 = 都市[0].フィットネス;
for (int i = 1; i< PopSize; i++)
if(citys[i].fitness<temp){
temp = 都市[i].フィットネス;
}
System.out.println("最適解: "+temp);
結果[インデックス] = 温度;
if(isSame(結果))
壊す;
インデックス++;
if(インデックス==範囲)
インデックス = 0;
数値++;
}
printBestRoute();
}
/**
* @param 開始時刻
* @param b 終了時刻
*/
public void CalTime(カレンダー a,カレンダー b){
長い x = b.getTimeInMillis() - a.getTimeInMillis();
長い y = x/1000;
x = x - 1000*y;
System.out.println("アルゴリズム実行時間: "+y+"."+x+" 秒");
}
/**
※プログラム入口
*/
public static void main(String[] args) {
カレンダー a = Calendar.getInstance() //開始時刻
Tsp tsp = 新しい Tsp();
tsp.run();
カレンダー b = Calendar.getInstance() //終了時刻
tsp.CalTime(a, b);
}
}