Скопируйте код кода следующим образом:
импортировать java.util.*;
общественный класс Tsp {
Private String cityName[]={"Пекин","Шанхай","Тяньцзинь","Чунцин","Харбин","Чанчунь","Шэньян","Хух-Хото","Шицзячжуан","Тайюань","Цзинань" ,"Чжэнчжоу","Сиань","Ланьчжоу","Иньчуань","Синин","Урумчи","Хэфэй","Нанкин","Ханчжоу","Чанша","Наньчан","Ухань" , «Чэнду», «Гуйчжоу», «Фуцзянь», «Тайбэй», «Гуанчжоу», «Хайкоу», «Наньнин», «Куньмин», «Лхаса», «Гонконг», «Макао»};
//частная строка cityEnd[]=new String[34];
Private int cityNum=cityName.length;//Количество городов
Private int popSize = 50 // Размер населения;
Private int maxgens = 20000 //Количество итераций;
частный двойной pxover = 0,8 // вероятность пересечения;
частная двойная pmulation = 0,05 // Вероятность мутации;
частное длинное[][] расстояние = новое длинное[cityNum][cityNum];
Private int range = 2000 //Диапазон массива, используемый для определения момента остановки
генотип частного класса {
int city[] = new int[cityNum] //Последовательность городов одного гена;
длительная пригодность //Приспособленность этого гена;
двойной selectP // Вероятность выбора
двойное исключениеp // ожидаемая вероятность
int isSelected; //Выбран ли он
}
частный генотип[] города = новый генотип[popSize];
/**
* Конструктор, инициализируем популяцию
*/
общественный Tsp() {
for (int я = 0; я <popSize; я++) {
города[i] = новый генотип();
int[] num = новый int[cityNum];
for (int j = 0; j <cityNum; j++)
число [j] = j;
интервал темп = cityNum;
for (int j = 0; j <cityNum; j++) {
int r = (int) (Math.random() * temp);
города[i].city[j] = число[r];
число[r] = число[темп - 1];
температура--;
}
города[i].фитнес = 0;
города[i].selectP = 0;
города[i].кромеp = 0;
города[i].isSelected = 0;
}
инициализация();
}
/**
* Рассчитайте приспособленность, вероятность отбора, ожидаемую вероятность и то, выбрана ли она для каждого генетического индивидуума в каждой популяции.
*/
общественная недействительность CalAll() {
for(int я = 0; я< popSize; я++){
города[i].фитнес = 0;
города[i].selectP = 0;
города[i].кромеp = 0;
города[i].isSelected = 0;
}
КалФитнес();
КалВыбратьП();
КалИсключениеП();
КалВыбрано();
}
/**
* Заполните, заполните несколько выделенных фрагментов невыделенными лицами
*/
публичная недействительная панель(){
целое лучшее = 0;
интервал плохой = 0;
в то время как (правда) {
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(best == popSize ||плохо == popSize)
перерыв;
}
}
/**
* Функция перекрестной темы
*/
общественный недействительный кроссовер () {
интервал х;
интервал y;
int pop = (int)(popSize* pxover /2);
в то время как (поп> 0) {
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
ExecuteCrossover(x,y);//xy два объекта выполняют пересечение
поп--;
}
}
/**
* Выполнить функцию кроссовера
* @param индивидуальный x
* @param индивидуальный y
* Выполните пересечение лучших наборов точек для отдельных x и отдельных y, чтобы создать последовательность городов следующего поколения.
*/
частная пустота выполнитьCrossover (int x, int y) {
целое измерение = 0;
for(int i = 0;i <cityNum; i++)
if(citys[x].city[i] != города[y].city[i]){
размерность++;
}
интервал diffItem = 0;
двойной [] diff = новый двойной [размер];
for( int я = 0 ;i <cityNum; я++){
if(citys[x].city[i] != города[y].city[i]){
diff[diffItem] = города[x].city[i];
города[x].city[i] = -1;
города[y].city[i] = -1;
диффитем++;
}
}
Arrays.sort(разница);
двойной [] temp = новый двойной [размер];
температура = gp(x, размерность);
for(int k = 0; k< измерение;k++)
for(int j = 0; j< измерение; j++)
если(temp[j] == k){
двойной элемент = temp[k];
темп[к] = темп[j];
темп [j] = элемент;
элемент = разница [к];
разница[к] = разница[j];
разница [j] = элемент;
}
int tempDimension = измерение;
интервал темп = 0;
в то время как (tempDimension> 0) {
if(citys[x].city[tempi] == -1){
города[x].city[tempi] = (int)diff[размерность - tempDimension];
темпдименсион --;
}
темпи++;
}
Arrays.sort(разница);
температура = gp(y, размерность);
for(int k = 0; k< измерение;k++)
for(int j = 0; j< измерение; j++)
если(temp[j] == k){
двойной элемент = temp[k];
темп[к] = темп[j];
темп [j] = элемент;
элемент = разница [к];
разница[к] = разница[j];
разница [j] = элемент;
}
tempDimension = измерение;
темп = 0;
в то время как (tempDimension> 0) {
if(citys[y].city[tempi] == -1){
города[y].city[tempi] = (int)diff[размерность - tempDimension];
темпдименсион --;
}
темпи++;
}
}
/**
* @param отдельное лицо
* @param измерение измерения
* @return Лучший набор точек (точка пересечения, используемая для функции пересечения) используется в функции выполненияCrossover().
*/
частный двойной [] gp(int индивидуальное, int измерение){
двойной [] temp = новый двойной [размер];
двойной [] temp1 = новый двойной [размер];
int p = 2 * размерность + 3;
пока(!isSushu(p))
р++;
for(int i = 0; i< измерение; я++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (индивидуальный+1);
temp[i] = temp[i] - (int)temp[i];
если(темп[я]<0)
температура[я] = 1+темп[я];
}
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++)
если (темп[j]==temp1[i])
темп [j] = я;
температура возврата;
}
/**
* Мутации
*/
общественная недействительность мутировать () {
двойной рандом;
внутренняя температура;
интервал темп1;
интервал темп2;
for(int я = 0; я< popSize; я++){
случайный = Math.random();
if(random<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
temp = города[i].city[temp1];
города[i].city[temp1] = города[i].city[temp2];
города[i].city[temp2] = темп;
}
}
}
/**
* Распечатать все городские последовательности текущей алгебры и связанные с ними параметры.
*/
общественная недействительная печать () {
/**
* Инициализировать расстояние между городами
*/
частная пустота initDistance () {
for (int я = 0; я <cityNum; я++) {
for (int j = 0; j <cityNum; j++){
расстояние[i][j] = Math.abs(ij);
}
}
}
/**
* Рассчитать пригодность всех городских последовательностей.
*/
частная недействительность CalFitness() {
for (int я = 0; я <popSize; я++) {
for (int j = 0; j <cityNum - 1; j++)
города[i].fitness += расстояние[города[i].город[j]][города[i].город[j + 1]];
города[i].fitness += расстояние[города[i].city[0]][города[i].city[cityNum - 1]];
}
}
/**
* Рассчитать вероятность выбора
*/
частная пустота CalSelectP(){
длинная сумма = 0;
for(int i = 0; i< popSize; i++)
сумма += города[i].фитнес;
for(int i = 0; i< popSize; i++)
города[i].selectP = (double)города[i].фитнес/сумма;
}
/**
* Рассчитать ожидаемую вероятность
*/
частная пустота CalExceptP(){
for(int i = 0; i< popSize; i++)
города[i].Exceptionp = (double)citys[i].selectP * popSize;
}
/**
* Подсчитайте, лучше ли последовательность городов, лучший будет выбран и войдет в следующее поколение
*/
частная пустота CalIsSelected(){
ИНТ NeedSelecte = popSize;
for(int i = 0; i< popSize; i++)
если(города[i].кромеp<1){
города[i].isSelected++;
нужноВыбрать --;
}
двойной [] temp = новый двойной [popSize];
for (int я = 0; я <popSize; я++) {
// temp[i] = города[i].Exceptionp - (int) города[i].Exceptionp;
// темп[i] *= 10;
temp[i] = города[i].Exceptionp*10;
}
интервал j = 0;
в то время как (needSelecte != 0) {
for (int я = 0; я <popSize; я++) {
if ((int) temp[i] == j) {
города[i].isSelected++;
нужноВыбрать--;
если (needSelecte == 0)
перерыв;
}
}
j++;
}
}
/**
* @парам х
* Функция @return для определения того, является ли число простым
*/
частное логическое значение isSushu(int x){
если (х<2) вернуть ложь;
for(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) возвращает false;
вернуть истину;
}
/**
* @param x массив
* @return Все ли значения массива x равны. Если равны, это означает, что оптимальный результат генерации x.length одинаковый, и алгоритм завершается.
*/
частное логическое значение isSame(long[] x){
for(int i = 0; i< x.length -1; i++)
если(х[i] !=x[i+1])
вернуть ложь;
вернуть истину;
}
/**
* Распечатайте оптимальную последовательность путей для любого поколения.
*/
частная пустота printBestRoute () {
КалВсе();
долгая температура = города[0].фитнес;
внутренний индекс = 0;
for (int я = 1; я <popSize; я++) {
if(citys[i].fitness<temp){
temp = города[i].фитнес;
индекс = я;
}
}
Система.out.println();
System.out.println("Лучшая последовательность путей:");
for (int j = 0; j <cityNum; j++)
{
String 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]]);
Система.out.println();
}
/**
* Выполнение алгоритма
*/
общественный недействительный запуск () {
длинный [] результат = новый длинный [диапазон];
//результат инициализируется так, что все числа не равны
for(int i = 0; i< диапазон; i++)
результат [я] = я;
int index = 0 //Позиция в массиве
int num = 1 //Генерация числа
в то время как (maxgens> 0) {
System.out.println("----------------- Генерация "+num+" -------------------- - ----");
КалВсе();
печать();
площадка();
кроссовер();
мутировать();
Максгенс --;
долгая температура = города[0].фитнес;
for (int i = 1; i< popSize; i++)
if(citys[i].fitness<temp){
temp = города[i].фитнес;
}
System.out.println("Оптимальное решение: "+temp);
результат[индекс] = температура;
если (isSame (результат))
перерыв;
индекс++;
если (индекс == диапазон)
индекс = 0;
число++;
}
печатьBestRoute();
}
/**
* @param время начала
* @param b время окончания
*/
public void CalTime (Календарь a, Календарь b) {
long x = b.getTimeInMillis() - a.getTimeInMillis();
длинный у = х/1000;
х = х - 1000*у;
System.out.println("Время выполнения алгоритма: "+y+"."+x+" секунд");
}
/**
* Вход в программу
*/
public static void main(String[] args) {
Календарь a = Calendar.getInstance(); //Время начала
Tsp tsp = новый Tsp();
tsp.run();
Календарь b = Calendar.getInstance(); //Время окончания
tsp.CalTime(а, б);
}
}