คัดลอกรหัสรหัสดังต่อไปนี้:
นำเข้า java.util.*;
Tsp ระดับสาธารณะ {
ชื่อเมืองสตริงส่วนตัว[]={"ปักกิ่ง", "เซี่ยงไฮ้", "เทียนจิน", "ฉงชิ่ง", "ฮาร์บิน", "ฉางชุน", "เสิ่นหยาง", "โฮฮอต", "ฉือเจียจวง", "ไท่หยวน", "จี่หนาน" ,"เจิ้งโจว", "ซีอาน", "หลานโจว", "หยินฉวน", "ซีหนิง", "อุรุมชี", "เหอเฟย", "หนานจิง", "หางโจว", "ฉางซา", "หนานชาง", "อู่ฮั่น" ," เฉิงตู", "กุ้ยโจว", "ฝูเจี้ยน", "ไทเป", "กวางโจว", "ไหโข่ว", "หนานหนิง", "คุนหมิง", "ลาซา", "ฮ่องกง", "มาเก๊า"};
//private String cityEnd[]=สตริงใหม่[34];
int cityNum=cityName.length;//จำนวนเมือง
int popSize ส่วนตัว = 50; // ขนาดประชากร
int maxgens ส่วนตัว = 20,000; // จำนวนการวนซ้ำ
pxover สองเท่าส่วนตัว = 0.8; // ความน่าจะเป็นแบบครอสโอเวอร์
pmulation สองเท่าส่วนตัว = 0.05; // ความน่าจะเป็นในการกลายพันธุ์
ยาวส่วนตัว [] [] ระยะทาง = ยาวใหม่ [cityNum] [cityNum];
ช่วง int ส่วนตัว = 2000; // ช่วงอาร์เรย์ใช้เพื่อกำหนดว่าจะหยุดเมื่อใด
จีโนไทป์คลาสส่วนตัว {
int city[] = new int[cityNum]; //ลำดับเมืองของยีนเดียว
ฟิตเนสยาว //ความฟิตของยีนนี้
double selectP; // ความน่าจะเป็นในการเลือก
ยกเว้นสองเท่า; // ความน่าจะเป็นที่คาดหวัง
int isSelected; // ไม่ว่าจะถูกเลือกหรือไม่
-
จีโนไทป์ส่วนตัว [] เมือง = จีโนไทป์ใหม่ [popSize];
-
* Constructor เริ่มต้นประชากร
-
Tsp สาธารณะ () {
สำหรับ (int i = 0; i < popSize; i++) {
เมือง [i] = จีโนไทป์ใหม่ ();
int[] num = ใหม่ int[cityNum];
สำหรับ (int j = 0; j <cityNum; j++)
หมายเลข[เจ] = เจ;
int temp = เมืองนัม;
สำหรับ (int j = 0; j <cityNum; j++) {
int r = (int) (Math.random() * temp);
เมือง[i].เมือง[j] = num[r];
เลข [r] = เลข [อุณหภูมิ - 1];
อุณหภูมิ--;
-
เมือง[i].ฟิตเนส = 0;
เมือง [i] .selectP = 0;
เมือง [i] .ยกเว้นp = 0;
เมือง [i] .isSelected = 0;
-
initDistance();
-
-
* คำนวณความเหมาะสม ความน่าจะเป็นในการเลือก ความน่าจะเป็นที่คาดหวัง และไม่ว่าจะเลือกสำหรับแต่ละบุคคลทางพันธุกรรมในแต่ละประชากรหรือไม่
-
โมฆะสาธารณะ CalAll () {
สำหรับ (int i = 0; i< popSize; i++){
เมือง[i].ฟิตเนส = 0;
เมือง [i] .selectP = 0;
เมือง [i] .ยกเว้นp = 0;
เมือง [i] .isSelected = 0;
-
แคลฟิตเนส();
CalSelectP();
CalExceptP();
CalIsSelected();
-
-
* กรอก กรอกตัวเลือกหลายรายการลงในบุคคลที่ไม่ได้เลือก
-
แผ่นโมฆะสาธารณะ () {
int ดีที่สุด = 0;
int แย่ = 0;
ในขณะที่ (จริง) {
ในขณะที่ (เมือง [ดีที่สุด] .isSelected <= 1 && ดีที่สุด <popSize-1)
ดีที่สุด++;
ในขณะที่ (เมือง [ไม่ดี] .isSelected != 0 && bad<popSize-1)
แย่++;
สำหรับ (int i = 0; i< cityNum; i++)
เมือง[ไม่ดี].เมือง[i] = เมือง[ดีที่สุด].เมือง[i];
เมือง [ดีที่สุด] .isSelected --;
เมือง [ไม่ดี] .isSelected ++;
แย่++;
ถ้า (ดีที่สุด == popSize || ไม่ดี == popSize)
หยุดพัก;
-
-
-
* ฟังก์ชั่นข้ามเรื่อง
-
ครอสโอเวอร์โมฆะสาธารณะ () {
อินท์ x;
อินท์ วาย;
int ป๊อป = (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 เพื่อสร้างลำดับเมืองรุ่นต่อไป
-
โมฆะส่วนตัวดำเนินการครอสโอเวอร์ (int x, int y) {
มิติข้อมูลภายใน = 0;
สำหรับ (int i = 0 ;i < cityNum; i++)
if(เมือง[x].เมือง[i] != เมือง[y].เมือง[i]){
มิติ++;
-
int diffItem = 0;
double[] diff = คู่ใหม่ [มิติ];
สำหรับ (int i = 0 ;i < cityNum; i++){
if(เมือง[x].เมือง[i] != เมือง[y].เมือง[i]){
diff[diffItem] = เมือง[x].เมือง[i];
เมือง[x].เมือง[i] = -1;
เมือง[y].เมือง[i] = -1;
รายการต่าง++;
-
-
อาร์เรย์.sort(แตกต่าง);
double[] temp = สองมิติใหม่;
อุณหภูมิ = gp(x, มิติ);
สำหรับ(int k = 0; k< มิติ;k++)
สำหรับ (int j = 0; j<มิติ; j++)
ถ้า (อุณหภูมิ [j] == k) {
รายการคู่ = อุณหภูมิ [k];
อุณหภูมิ[k] = อุณหภูมิ[j];
อุณหภูมิ[j] = รายการ;
รายการ = ความแตกต่าง [k];
ต่าง[k] = ต่าง[เจ];
diff[j] = รายการ;
-
int tempDimension = มิติ;
int เทมปิ = 0;
ในขณะที่(มิติอุณหภูมิ> 0 ){
if(เมือง[x].เมือง[อุณหภูมิ] == -1){
เมือง[x].เมือง[tempi] = (int)diff[มิติ - tempDimension];
อุณหภูมิมิติ --;
-
เทมปิ++;
-
อาร์เรย์.sort(แตกต่าง);
อุณหภูมิ = gp (y, มิติ);
สำหรับ (int k = 0; k < มิติ; k ++)
สำหรับ (int j = 0; j<มิติ; j++)
ถ้า (อุณหภูมิ [j] == k) {
รายการคู่ = อุณหภูมิ [k];
อุณหภูมิ[k] = อุณหภูมิ[j];
อุณหภูมิ[j] = รายการ;
รายการ = ความแตกต่าง [k];
ต่าง[k] = ต่าง[เจ];
diff[j] = รายการ;
-
tempDimension = มิติ;
เทมปี = 0;
ในขณะที่(มิติอุณหภูมิ> 0 ){
if(เมือง[y].เมือง[ชั่วคราว] == -1){
เมือง[y].เมือง[tempi] = (int)diff[มิติ - tempDimension];
อุณหภูมิมิติ --;
-
เทมปิ++;
-
-
-
* @param บุคคล บุคคล
* มิติมิติ @param
* @return ชุดจุดที่ดีที่สุด (จุดตัดที่ใช้สำหรับฟังก์ชัน cross) ถูกใช้ในฟังก์ชันExecuteCrossover()
-
ส่วนตัวสองเท่า [] gp (int บุคคล, int มิติ) {
double[] temp = สองมิติใหม่;
double[] temp1 = คู่ใหม่ [มิติ];
int p = 2 * มิติ + 3;
ในขณะที่(!isSushu(p))
พี++;
สำหรับ (int i = 0; i< มิติ; i++){
อุณหภูมิ[i] = 2*Math.cos(2*Math.PI*(i+1)/p) * (รายบุคคล+1);
อุณหภูมิ[i] = อุณหภูมิ[i] - (int)อุณหภูมิ[i];
ถ้า(อุณหภูมิ[i]<0)
อุณหภูมิ[i] = 1+อุณหภูมิ[i];
-
สำหรับ (int i = 0; i< มิติ; i++)
temp1[i] = อุณหภูมิ[i];
อาร์เรย์.sort(temp1);
//เรียงลำดับ
สำหรับ (int i = 0; i< มิติ; i++)
สำหรับ (int j = 0; j<มิติ; j++)
ถ้า(อุณหภูมิ[j]==temp1[i])
อุณหภูมิ[j] = ฉัน;
อุณหภูมิกลับ;
-
-
* การกลายพันธุ์
-
โมฆะสาธารณะกลายพันธุ์ () {
สุ่มสองครั้ง;
อุณหภูมิภายใน;
int temp1;
int temp2;
สำหรับ (int i = 0; i< popSize; i++){
สุ่ม = Math.random();
ถ้า (สุ่ม<=pmultation){
temp1 = (int)(Math.random() * (cityNum));
temp2 = (int)(Math.random() * (cityNum));
อุณหภูมิ = เมือง [i] . เมือง [temp1];
เมือง[i].เมือง[temp1] = เมือง[i].เมือง[temp2];
เมือง [i] . เมือง [temp2] = อุณหภูมิ;
-
-
-
-
* พิมพ์ลำดับเมืองทั้งหมดของพีชคณิตปัจจุบันและพารามิเตอร์ที่เกี่ยวข้อง
-
โมฆะสาธารณะ พิมพ์ () {
-
* เริ่มต้นระยะห่างระหว่างเมือง
-
โมฆะส่วนตัว 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++)
เมือง[i].ฟิตเนส += ระยะทาง[เมือง[i].เมือง[j]][เมือง[i].เมือง[j + 1]];
เมือง[i].ฟิตเนส += ระยะทาง[เมือง[i].เมือง[0]][เมือง[i].เมือง[cityNum - 1]];
-
-
-
* คำนวณความน่าจะเป็นในการเลือก
-
โมฆะส่วนตัว CalSelectP(){
ผลรวมยาว = 0;
สำหรับ (int i = 0; i< popSize; i++)
ผลรวม += เมือง [i] .fitness;
สำหรับ (int i = 0; i< popSize; i++)
เมือง[i].selectP = (สองเท่า)เมือง[i].ฟิตเนส/ผลรวม;
-
-
* คำนวณความน่าจะเป็นที่คาดหวัง
-
โมฆะส่วนตัว CalExceptP(){
สำหรับ (int i = 0; i< popSize; i++)
เมือง[i].ยกเว้นp = (สองเท่า)เมือง[i].selectP * popSize;
-
-
* คำนวณว่าลำดับเมืองดีกว่าหรือไม่ ระบบจะเลือกลำดับที่ดีกว่าและเข้าสู่รุ่นต่อไป
-
โมฆะส่วนตัว CalIsSelected () {
int needSelecte = ป๊อปไซส์;
สำหรับ (int i = 0; i< popSize; i++)
ถ้า( เมือง[i].ยกเว้นp<1){
เมือง [i] .isSelected ++;
ต้องการเลือก --;
-
double[] temp = ใหม่ double[popSize];
สำหรับ (int i = 0; i < popSize; i++) {
// temp[i] = เมือง[i].ยกเว้นp - (int) เมือง[i].ยกเว้นp;
// อุณหภูมิ[i] *= 10;
temp[i] = เมือง[i].ยกเว้นp*10;
-
อินท์เจ = 0;
ในขณะที่ (needSelecte != 0) {
สำหรับ (int i = 0; i < popSize; i++) {
ถ้า ((int) อุณหภูมิ [i] == j) {
เมือง [i] .isSelected ++;
ต้องเลือก--;
ถ้า (needSelecte == 0)
หยุดพัก;
-
-
เจ++;
-
-
-
* @param x
* ฟังก์ชัน @return เพื่อตรวจสอบว่าตัวเลขนั้นเป็นจำนวนเฉพาะหรือไม่
-
บูลีนส่วนตัว isSushu (int x) {
ถ้า(x<2) กลับเท็จ;
สำหรับ(int i=2;i<=x/2;i++)
if(x%i==0&&x!=2) กลับเท็จ;
กลับเป็นจริง;
-
-
* @param x อาร์เรย์
* @return ค่าของอาร์เรย์ x ทั้งหมดเท่ากันหรือไม่ หากเท่ากัน แสดงว่าผลลัพธ์ที่ดีที่สุดของการสร้าง x.length เท่ากัน และอัลกอริทึมจะสิ้นสุดลง
-
บูลีนส่วนตัว isSame (ยาว [] x) {
สำหรับ (int i = 0; i< x.length -1; i++)
ถ้า(x[i] !=x[i+1])
กลับเท็จ;
กลับเป็นจริง;
-
-
* พิมพ์ลำดับเส้นทางที่เหมาะสมที่สุดสำหรับรุ่นใดก็ได้
-
โมฆะส่วนตัว printBestRoute(){
แคลออล();
อุณหภูมิสูง = เมือง[0].ฟิตเนส;
ดัชนี int = 0;
สำหรับ (int i = 1; i < popSize; i++) {
if(เมือง[i].ฟิตเนส<อุณหภูมิ){
temp = เมือง[i].ฟิตเนส;
ดัชนี = ฉัน;
-
-
System.out.println();
System.out.println("ลำดับเส้นทางที่ดีที่สุด:");
สำหรับ (int j = 0; j <cityNum; j++)
-
สตริง cityEnd[]={cityName[citys[index].city[j]]};
สำหรับ(int m=0;m<cityEnd.length;m++)
-
System.out.print(เมืองEnd[m] + " ");
-
-
//System.out.print(เมือง[ดัชนี].เมือง[j] + ชื่อเมือง[เมือง[ดัชนี].เมือง[j]] + " ");
//System.out.print(cityName[เมือง[ดัชนี].เมือง[j]]);
System.out.println();
-
-
* การดำเนินการอัลกอริทึม
-
โมฆะสาธารณะวิ่ง () {
ยาว [] ผลลัพธ์ = ยาวใหม่ [ช่วง];
//ผลลัพธ์ถูกเตรียมใช้งานเพื่อให้ตัวเลขทั้งหมดไม่เท่ากัน
สำหรับ (int i = 0; i< range; i++)
ผลลัพธ์[i] = ฉัน;
ดัชนี int = 0; // ตำแหน่งในอาร์เรย์
int num = 1; // การสร้างหมายเลข
ในขณะที่(สูงสุด>0){
System.out.println("----------------- "+num+" รุ่น -------------------- - ----");
แคลออล();
พิมพ์();
เบาะ();
ครอสโอเวอร์();
กลายพันธุ์();
แม็กซ์เจนส์ --;
อุณหภูมิสูง = เมือง[0].ฟิตเนส;
สำหรับ (int i = 1; i< popSize; i++)
if(เมือง[i].ฟิตเนส<อุณหภูมิ){
temp = เมือง[i].ฟิตเนส;
-
System.out.println("วิธีแก้ปัญหาที่เหมาะสมที่สุด: "+temp);
ผลลัพธ์ [ดัชนี] = อุณหภูมิ;
ถ้า (เหมือนกัน (ผลลัพธ์))
หยุดพัก;
ดัชนี++;
ถ้า(ดัชนี==ช่วง)
ดัชนี = 0;
หมายเลข++;
-
printBestRoute();
-
-
* @param เวลาเริ่มต้น
* @param b เวลาสิ้นสุด
-
โมฆะสาธารณะ CalTime (ปฏิทิน a, ปฏิทิน b) {
ยาว x = b.getTimeInMillis() - a.getTimeInMillis();
ยาว y = x/1,000;
x = x - 1,000*y;
System.out.println("เวลาดำเนินการอัลกอริทึม: "+y+"."+x+" วินาที");
-
-
* ทางเข้าโปรแกรม
-
โมฆะคงที่สาธารณะ main (String [] args) {
ปฏิทิน a = Calendar.getInstance(); //เวลาเริ่มต้น
Tsp tsp = Tsp ใหม่();
ช้อนชา.run();
ปฏิทิน b = Calendar.getInstance(); //เวลาสิ้นสุด
ช้อนชา CalTime(a, b);
-
-