Copiez le code comme suit :
importer java.util.* ;
classe publique Tsp {
private String cityName[]={"Pékin","Shanghai","Tianjin","Chongqing","Harbin","Changchun","Shenyang","Hohhot","Shijiazhuang","Taiyuan","Jinan" "Zhengzhou", "Xi'an", "Lanzhou", "Yinchuan", "Xining", "Urumqi", "Hefei", "Nanjing", "Hangzhou", "Changsha", "Nanchang", "Wuhan". ," Chengdu","Guizhou","Fujian","Taipei","Guangzhou","Haikou","Nanning","Kunming","Lhassa","Hong Kong","Macao"};
//chaîne privée cityEnd[]=new String[34];
private int cityNum=cityName.length;//Nombre de villes
private int popSize = 50 ; //Taille de la population
private int maxgens = 20000 ; //Nombre d'itérations
double pxover privé = 0,8 ; //probabilité de croisement
double pmulation privée = 0,05 ; //Probabilité de mutation
private long[][] distance = new long[cityNum][cityNum];
private int range = 2000 ; //Plage du tableau utilisée pour déterminer quand arrêter
génotype de classe privée {
int city[] = new int[cityNum]; //Séquence de ville d'un seul gène
longue forme physique ; //Fitness de ce gène
double selectP; //Probabilité de sélection
double saufp; //probabilité attendue
int isSelected; //S'il est sélectionné
}
private génotype[] villes = nouveau génotype[popSize];
/**
* Constructeur, initialise la population
*/
public Tsp() {
pour (int i = 0; i < popSize; i++) {
villes[i] = nouveau génotype();
int[] num = nouveau int[cityNum];
pour (int j = 0; j < cityNum; j++)
num[j] = j;
int temp = cityNum;
pour (int j = 0; j < cityNum; j++) {
int r = (int) (Math.random() * temp);
villes[i].city[j] = num[r];
num[r] = num[temp - 1];
temp--;
}
villes[i].fitness = 0;
villes[i].selectP = 0;
villes[i].saufp = 0;
villes[i].isSelected = 0;
}
initDistance();
}
/**
* Calculez la condition physique, la probabilité de sélection, la probabilité attendue et si elle est sélectionnée pour chaque individu génétique dans chaque population.
*/
public void CalAll(){
pour(int i = 0; i< popSize; i++){
villes[i].fitness = 0;
villes[i].selectP = 0;
villes[i].saufp = 0;
villes[i].isSelected = 0;
}
CalFitness();
CalSelectP();
CalExceptP();
CalIsSelected();
}
/**
* Remplissez, remplissez plusieurs sélections dans des individus non sélectionnés
*/
tampon vide public(){
int meilleur = 0 ;
int mauvais = 0 ;
tandis que(vrai){
while(citys[best].isSelected <= 1 && best<popSize-1)
meilleur ++ ;
while(citys[bad].isSelected != 0 && bad<popSize-1)
mauvais++ ;
pour(int i = 0; i< cityNum; i++)
villes[mauvaises].city[i] = villes[meilleures].city[i];
villes[best].isSelected --;
villes[mauvais].isSelected++;
mauvais++ ;
si (meilleur == popSize ||mauvais == popSize)
casser;
}
}
/**
* Fonction transversale
*/
public void crossover() {
entier x ;
int y;
int pop = (int)(popSize* pxover /2);
pendant que(pop>0){
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
executeCrossover(x,y);//xy deux entités exécutent le crossover
populaire--;
}
}
/**
* Exécuter la fonction de croisement
* @param individuel x
* @param individuel y
* Effectuer l'intersection des meilleurs ensembles de points pour l'individu x et l'individu y pour générer la séquence urbaine de nouvelle génération
*/
private void executeCrossover(int x,int y){
dimension entière = 0 ;
pour (int i = 0 ;i < cityNum; i++)
si(villes[x].ville[i] != villes[y].ville[i]){
dimension++;
}
int diffItem = 0 ;
double[] diff = nouveau double[dimension];
pour (int i = 0 ;i < cityNum; i++){
si(villes[x].ville[i] != villes[y].ville[i]){
diff[diffItem] = villes[x].ville[i];
villes[x].ville[i] = -1;
villes[y].ville[i] = -1;
diffItem++;
}
}
Arrays.sort(diff);
double[] temp = nouveau double[dimension];
temp = gp(x, dimension);
pour(int k = 0; k< dimension;k++)
pour(int j = 0; j< dimension; j++)
si(temp[j] == k){
élément double = temp[k];
temp[k] = temp[j];
temp[j] = élément ;
article = diff[k];
diff[k] = diff[j];
diff[j] = élément ;
}
int tempDimension = dimension ;
temps int = 0 ;
pendant que(tempDimension> 0 ){
si(villes[x].ville[tempi] == -1){
villes[x].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi++;
}
Arrays.sort(diff);
temp = gp(y, dimension);
pour(int k = 0; k< dimension;k++)
pour(int j = 0; j< dimension; j++)
si(temp[j] == k){
élément double = temp[k];
temp[k] = temp[j];
temp[j] = élément ;
article = diff[k];
diff[k] = diff[j];
diff[j] = élément ;
}
tempDimension = dimension ;
temps = 0 ;
pendant que(tempDimension> 0 ){
si(villes[y].ville[tempi] == -1){
villes[y].city[tempi] = (int)diff[dimension - tempDimension];
tempDimension --;
}
tempi++;
}
}
/**
* @param individuel individuel
* @param dimension dimension
* @return Le meilleur ensemble de points (le point d'intersection utilisé pour la fonction cross) est utilisé dans la fonction executeCrossover()
*/
privé double[] gp(int individuel, dimension int){
double[] temp = nouveau double[dimension];
double[] temp1 = nouveau double[dimension];
int p = 2 * dimension + 3 ;
pendant que(!isSushu(p))
p++;
pour(int i = 0; i< dimension; i++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (individu+1);
temp[i] = temp[i] - (int)temp[i];
si(temp[i]<0)
temp[i] = 1+temp[i];
}
pour(int i = 0; i< dimension; i++)
temp1[je] = temp[je];
Tableaux.sort(temp1);
//Trier
pour(int i = 0; i< dimension; i++)
pour(int j = 0; j< dimension; j++)
si(temp[j]==temp1[i])
temp[j] = je;
température de retour ;
}
/**
* Mutations
*/
public void muter(){
double aléatoire ;
température int;
int temp1;
int temp2;
pour(int i = 0; i< popSize; i++){
aléatoire = Math.random();
if(aléatoire<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
temp = villes[i].ville[temp1];
villes[i].city[temp1] = villes[i].city[temp2];
villes[i].city[temp2] = temp;
}
}
}
/**
* Imprimer toutes les séquences de villes de l'algèbre actuelle et leurs paramètres associés
*/
public void print(){
/**
* Initialiser la distance entre les villes
*/
privé vide initDistance(){
pour (int i = 0; i < cityNum; i++) {
pour (int j = 0; j < cityNum; j++){
distance[i][j] = Math.abs(ij);
}
}
}
/**
* Calculer la condition physique de toutes les séquences urbaines
*/
privé vide CalFitness() {
pour (int i = 0; i < popSize; i++) {
pour (int j = 0; j < cityNum - 1; j++)
villes[i].fitness += distance[villes[i].city[j]][villes[i].city[j + 1]];
villes[i].fitness += distance[villes[i].city[0]][villes[i].city[cityNum - 1]];
}
}
/**
* Calculer la probabilité de sélection
*/
vide privé CalSelectP(){
somme longue = 0 ;
pour(int i = 0; i< popSize; i++)
somme += villes[i].fitness ;
pour(int i = 0; i< popSize; i++)
villes[i].selectP = (double)villes[i].fitness/sum;
}
/**
* Calculer la probabilité attendue
*/
privé vide CalExceptP(){
pour(int i = 0; i< popSize; i++)
villes[i].saufp = (double)villes[i].selectP * popSize;
}
/**
* Calculez si la séquence de villes est meilleure, la meilleure sera sélectionnée et entrerez dans la prochaine génération
*/
privé vide CalIsSelected(){
int needSelecte = popSize;
pour(int i = 0; i< popSize; i++)
if( villes[i].saufp<1){
villes[i].isSelected++;
besoinSélectionner --;
}
double[] temp = nouveau double[popSize];
pour (int i = 0; i < popSize; i++) {
// temp[i] = villes[i].saufp - (int) villes[i].saufp;
// temp[i] *= 10;
temp[i] = villes[i].saufp*10;
}
entier j = 0 ;
while (needSelecte != 0) {
pour (int i = 0; i < popSize; i++) {
si ((int) temp[i] == j) {
villes[i].isSelected++;
needSelecte--;
si (besoinSélection == 0)
casser;
}
}
j++;
}
}
/**
* @paramx
* Fonction @return pour déterminer si un nombre est premier
*/
booléen privé isSushu(int x){
if(x<2) renvoie faux ;
pour(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) renvoie false ;
renvoie vrai ;
}
/**
* @param x tableau
* @return Si les valeurs du tableau x sont toutes égales, cela signifie que le résultat optimal de la génération x.length est le même et l'algorithme se termine.
*/
booléen privé isSame(long[] x){
pour(int i = 0; i< x.length -1; i++)
si(x[i] !=x[i+1])
renvoie faux ;
renvoie vrai ;
}
/**
* Imprimez la séquence de chemin optimale pour n'importe quelle génération
*/
privé vide printBestRoute(){
CalAll();
température longue = villes[0].fitness ;
indice int = 0 ;
pour (int i = 1; i < popSize; i++) {
si(villes[i].fitness<temp){
temp = villes[i].fitness;
indice = je ;
}
}
System.out.println();
System.out.println("Meilleure séquence de chemin :");
pour (int j = 0; j < cityNum; j++)
{
String cityEnd[]={cityName[citys[index].city[j]]};
pour(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();
}
/**
* Exécution de l'algorithme
*/
public void run(){
long[] résultat = nouveau long[range] ;
//le résultat est initialisé pour que tous les nombres ne soient pas égaux
pour(int i = 0; i< plage; i++)
résultat[i] = i;
int index = 0; //Position dans le tableau
int num = 1; //Numième génération
pendant que(gensmax>0){
System.out.println("----------------- Génération "+num+"---------------------------------- - ----");
CalAll();
imprimer();
tampon();
croisement();
subir une mutation();
maxgens --;
température longue = villes[0].fitness ;
pour (int i = 1; i< popSize; i++)
si(villes[i].fitness<temp){
temp = villes[i].fitness;
}
System.out.println("Solution optimale : "+temp);
résultat[index] = temp;
si (est identique (résultat))
casser;
indice++;
si (index == plage)
indice = 0 ;
num++;
}
printBestRoute();
}
/**
* @param une heure de début
* @param b heure de fin
*/
public void CalTime (Calendrier a, Calendrier b) {
long x = b.getTimeInMillis() - a.getTimeInMillis();
y long = x/1000 ;
x = x - 1000*y ;
System.out.println("Durée d'exécution de l'algorithme : "+y+"."+x+" secondes");
}
/**
* Entrée au programme
*/
public static void main (String[] arguments) {
Calendrier a = Calendar.getInstance(); //Heure de début
Tsp tsp = new Tsp();
tsp.run();
Calendrier b = Calendar.getInstance(); //Heure de fin
cuillère à café.CalTime(a, b);
}
}