انسخ رمز الكود كما يلي:
import java.util.*;
الطبقة العامة Tsp {
Private String cityName[]={"Beijing"، "Shanghai"، "Tianjin"، "Chongqing"، "Harbin"، "Changchun"، "Shenyang"، "Hohhot"، "Shijiazhuang"، "Taiyuan"، "Jinan" "تشنغتشو"، "شيان"، "لانتشو"، "ينتشوان"، "شينينغ"، "أورومتشي"، "خفي"، "نانجينغ"، "هانغتشو"، "تشانغشا"، "نانتشانغ"، "ووهان" "،" تشنغدو"، "قويتشو"، "فوجيان"، "تايبيه"، "قوانغتشو"، "هايكو"، "ناننينغ"، "كونمينغ"، "لاسا"، "هونج كونج"، "ماكاو"}؛
// سلسلة خاصة cityEnd[]=new String[34];
Private int cityNum=cityName.length;// عدد المدن
Private int popSize = 50; // حجم السكان
Private int maxgens = 20000; // عدد التكرارات
pxover مزدوج خاص = 0.8؛ // احتمال التقاطع
التكاثر المزدوج الخاص = 0.05؛ // احتمالية الطفرة
خاص طويل[][] المسافة = جديد طويل[cityNum][cityNum];
نطاق int الخاص = 2000؛ // نطاق الصفيف المستخدم لتحديد وقت التوقف
النمط الجيني للطبقة الخاصة {
int city[] = new int[cityNum]; // تسلسل المدينة لجين واحد
اللياقة البدنية الطويلة // لياقة هذا الجين
تحديد مزدوج P؛ // احتمالية الاختيار
استثناء مزدوج؛ // الاحتمال المتوقع
int isSelected; // سواء تم تحديده
}
النمط الجيني الخاص[] المدن = النمط الجيني الجديد[popSize];
/**
* منشئ، تهيئة السكان
*/
Tsp العامة () {
لـ (int i = 0; i < popSize; i++) {
المدن[i] = النمط الجيني الجديد ()؛
int[] num = new int[cityNum];
لـ (int j = 0; j < cityNum; j++)
عدد[j] = j;
int temp = cityNum;
لـ (int j = 0; j < cityNum; j++) {
int r = (int) (Math.random() * temp);
city[i].city[j] = num[r];
num[r] = num[temp-1];
درجة حرارة--؛
}
المدن[i].fitness = 0;
مدن[i].selectP = 0;
المدن[i].exceptp = 0;
المدن[i].isSelected = 0;
}
initDistance();
}
/**
* حساب اللياقة البدنية، واحتمال الاختيار، والاحتمال المتوقع، وما إذا كان تم اختياره لكل فرد وراثي في كل مجموعة سكانية.
*/
الفراغ العام CalAll () {
for(int i = 0; i< popSize; i++){
المدن[i].fitness = 0;
مدن[i].selectP = 0;
المدن[i].exceptp = 0;
المدن[i].isSelected = 0;
}
كال فيتنس();
CalSelectP();
CalExceptP();
CalIsSelected();
}
/**
* املأ، املأ تحديدات متعددة بأفراد غير محددين
*/
لوحة الفراغ العامة () {
إنت أفضل = 0؛
كثافة العمليات سيئة = 0؛
بينما (صحيح) {
بينما (citys[best].isSelected <= 1 && best<popSize-1)
أفضل++؛
بينما (citys[bad].isSelected != 0 && bad<popSize-1)
سيئة++؛
ل(int i = 0; i< cityNum; i++)
مدن[سيئة].مدينة[i] = مدن[أفضل].مدينة[i];
المدن[الأفضل].isSelected --;
مدن[سيئة].isSelected++;
سيئة++؛
إذا (الأفضل == حجم البوب ||سيئ == حجم البوب)
استراحة؛
}
}
/**
* وظيفة عبر الموضوع
*/
تقاطع الفراغ العام () {
كثافة العمليات س؛
كثافة العمليات ذ؛
int pop = (int)(popSize* pxover /2);
بينما (البوب> 0) {
x = (int)(Math.random()*popSize);
y = (int)(Math.random()*popSize);
ExecuteCrossover(x,y);//xy يقوم كيانان بتنفيذ التقاطع
البوب--؛
}
}
/**
* تنفيذ وظيفة التقاطع
* @param فرد x
* @param فرد ذ
* قم بإجراء تقاطع أفضل مجموعات النقاط للفرد x والفرد y لإنشاء تسلسل مدينة الجيل التالي
*/
تنفيذ الفراغ الخاص (int x,int y){
البعد الصحيح = 0؛
ل(int i = 0;i <cityNum; i++)
إذا(citys[x].city[i] != المدن[y].city[i]){
البعد++;
}
int diffItem = 0;
double[] diff = new double[dimension];
ل(int i = 0 ;i < cityNum; i++){
إذا(citys[x].city[i] != المدن[y].city[i]){
diff[diffItem] = city[x].city[i];
مدن[x].city[i] = -1;
مدن[y].city[i] = -1;
diffItem++;
}
}
Arrays.sort(diff);
double[] temp = new double[dimension];
درجة الحرارة = gp(x, البعد);
ل(int ك = 0; ك< البعد;ك++)
ل(int j = 0; j< البعد; j++)
إذا (درجة الحرارة [ي] == ك){
عنصر مزدوج = درجة الحرارة [ك]؛
درجة الحرارة[ك] = درجة الحرارة[ي];
temp[j] = item;
العنصر = فرق[ك];
diff[k] = diff[j];
diff[j] = item;
}
int tempDimension = Dimension;
درجة الحرارة المؤقتة = 0;
بينما (درجة الحرارة> 0 ) {
إذا(citys[x].city[tempi] == -1){
city[x].city[tempi] = (int)diff[dimension - tempDimension];
البعد المؤقت --;
}
درجة الحرارة++;
}
Arrays.sort(diff);
درجة الحرارة = gp(y, Dimension);
ل(int ك = 0; ك< البعد;ك++)
ل(int j = 0; j< البعد; j++)
إذا (درجة الحرارة [ي] == ك){
عنصر مزدوج = درجة الحرارة [ك]؛
درجة الحرارة[ك] = درجة الحرارة[ي];
temp[j] = item;
العنصر = فرق[ك];
diff[k] = diff[j];
diff[j] = item;
}
tempDimension = Dimension;
درجة الحرارة = 0؛
بينما (درجة الحرارة> 0 ){
إذا(citys[y].city[tempi] == -1){
city[y].city[tempi] = (int)diff[dimension - tempDimension];
البعد المؤقت --;
}
درجة الحرارة++;
}
}
/**
* @param فرد فردى
* البعد البعد @param
* @return يتم استخدام أفضل مجموعة نقاط (نقطة التقاطع المستخدمة للدالة المتقاطعة) في وظيفة ExecuteCrossover ()
*/
مزدوج خاص[] gp(int فردي، int Dimension){
double[] temp = new double[dimension];
double[] temp1 = new double[dimension];
كثافة العمليات = 2 * البعد + 3؛
بينما(!isSushu(ع))
ص++;
ل(int i = 0; i< البعد; i++){
temp[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (individual+1);
temp[i] = temp[i] - (int)temp[i];
إذا (درجة الحرارة [أنا] <0)
درجة الحرارة[i] = 1+درجة الحرارة[i];
}
ل(int i = 0; i< البعد; i++)
temp1[i] = temp[i];
Arrays.sort(temp1);
//نوع
ل(int i = 0; i< البعد; i++)
ل(int j = 0; j< البعد; j++)
إذا (درجة الحرارة [ي] == درجة الحرارة 1 [i])
درجة الحرارة [ي] = أنا؛
درجة حرارة العودة؛
}
/**
* الطفرات
*/
تحور الفراغ العام () {
عشوائي مزدوج؛
درجة الحرارة الدولية؛
كثافة العمليات 1؛
درجة الحرارة الدولية 2؛
for(int i = 0; i< popSize; i++){
عشوائي = Math.random();
إذا (عشوائي <= بمولتيشن) {
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
درجة الحرارة = المدن[i].city[temp1];
مدن[i].city[temp1] = مدن[i].city[temp2];
city[i].city[temp2] = temp;
}
}
}
/**
* طباعة جميع تسلسلات المدينة للجبر الحالي والمعلمات المرتبطة بها
*/
طباعة باطلة عامة () {
/**
* تهيئة المسافة بين المدن
*/
الفراغ الخاص initDistance(){
لـ (int i = 0; i < cityNum; i++) {
لـ (int j = 0; j < cityNum; j++){
المسافة[i][j] = Math.abs(ij);
}
}
}
/**
* حساب مدى ملاءمة جميع تسلسلات المدينة
*/
باطلة خاصة CalFitness () {
لـ (int i = 0; i < popSize; i++) {
لـ (int j = 0; j < cityNum - 1; j++)
city[i].fitness += distance[citys[i].city[j]][citys[i].city[j + 1]];
city[i].fitness += distance[citys[i].city[0]][citys[i].city[cityNum - 1]];
}
}
/**
* حساب احتمال الاختيار
*/
باطلة خاصة CalSelectP () {
مجموع طويل = 0؛
ل(int i = 0; i< popSize; i++)
مجموع += المدن[i].fitness;
ل(int i = 0; i< popSize; i++)
citys[i].selectP = (double)citys[i].fitness/sum;
}
/**
* حساب الاحتمال المتوقع
*/
الفراغ الخاص CalExceptP(){
ل(int i = 0; i< popSize; i++)
مدن[i].exceptp = (مزدوج)citys[i].selectP * popSize;
}
/**
* احسب ما إذا كان تسلسل المدينة أفضل، سيتم اختيار الأفضل ودخول الجيل التالي
*/
الفراغ الخاص CalIsSelected(){
int needSelecte = popSize;
ل(int i = 0; i< popSize; i++)
إذا (المدن[i].exceptp<1){
مدن[i].isSelected++;
needSelecte --;
}
double[] temp = new double[popSize];
لـ (int i = 0; i < popSize; i++) {
// temp[i] = مدن[i].exceptp - (int) مدن[i].exceptp;
// درجة الحرارة [i] *= 10;
temp[i] = city[i].exceptp*10;
}
كثافة العمليات ي = 0;
بينما (بحاجة إلى تحديد! = 0) {
لـ (int i = 0; i < popSize; i++) {
إذا ((int) درجة الحرارة[i] == j) {
مدن[i].isSelected++;
needSelecte--;
إذا (بحاجة إلى تحديد == 0)
استراحة؛
}
}
ي++;
}
}
/**
* @paramx
* وظيفة @return لتحديد ما إذا كان الرقم أوليًا أم لا
*/
منطقية خاصة isSushu(int x){
إذا (x<2) قم بإرجاع خطأ؛
ل(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) يُرجع false;
عودة صحيحة؛
}
/**
* @param x مصفوفة
* @return ما إذا كانت قيم المصفوفة x متساوية، إذا كانت متساوية، فهذا يعني أن النتيجة المثلى لتوليد x.length هي نفسها، وتنتهي الخوارزمية
*/
منطقية خاصة هيSame(long[] x){
ل(int i = 0; i< x.length -1; i++)
إذا (س[i] !=x[i+1])
عودة كاذبة.
عودة صحيحة؛
}
/**
* طباعة تسلسل المسار الأمثل لأي جيل
*/
طباعة باطلة خاصةBestRoute(){
CalAll();
درجة الحرارة الطويلة = المدن[0].اللياقة البدنية؛
مؤشر كثافة العمليات = 0؛
لـ (int i = 1; i < popSize; i++) {
إذا (المدن[i].اللياقة البدنية<درجة الحرارة){
درجة الحرارة = المدن[i].fitness;
الفهرس = أنا؛
}
}
System.out.println();
System.out.println("أفضل تسلسل للمسار:");
لـ (int j = 0; j < cityNum; j++)
{
String cityEnd[]={cityName[citys[index].city[j]]};
ل(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();
}
/**
* تنفيذ الخوارزمية
*/
تشغيل الفراغ العام () {
long[] result = new long[range];
// تتم تهيئة النتيجة بحيث لا تكون جميع الأرقام متساوية
ل(int i = 0; i< range; i++)
النتيجة[i] = i;
مؤشر int = 0; // الموضع في الصفيف
int num = 1; // توليد العدد
بينما (ماكسجينس> 0) {
System.out.println("----------------- الجيل "+num+"--------------------- - ----");
CalAll();
مطبعة()؛
وسادة ()؛
كروس () ؛
تحور ()؛
ماكسجنز --;
درجة الحرارة الطويلة = المدن[0].اللياقة البدنية؛
لـ (int i = 1; i< popSize; i++)
إذا (المدن[i].اللياقة البدنية<درجة الحرارة){
درجة الحرارة = المدن[i].fitness;
}
System.out.println("الحل الأمثل:"+temp);
النتيجة [الفهرس] = درجة الحرارة؛
إذا (هو نفسه (النتيجة))
استراحة؛
الفهرس++;
إذا (الفهرس == النطاق)
الفهرس = 0؛
رقم++;
}
printBestRoute();
}
/**
* @param وقت البدء
*param b نهاية الوقت
*/
الفراغ العام CalTime(التقويم أ،التقويم ب){
long x = b.getTimeInMillis() - a.getTimeInMillis();
طويل ص = س/1000؛
س = س - 1000*ص؛
System.out.println("وقت تنفيذ الخوارزمية: "+y+"."+x+" ثانية");
}
/**
* مدخل البرنامج
*/
public static void main(String[] args) {
التقويم أ = Calendar.getInstance(); // وقت البدء
Tsp tsp = new Tsp();
tsp.run();
التقويم ب = Calendar.getInstance(); // وقت الانتهاء
tsp.CalTime(a, b);
}
}