การใช้งาน Java ของการแบ่งปันตัวอย่างอัลกอริทึมทางพันธุกรรม (การพิมพ์ข้อมูลเมือง)

คัดลอกรหัสรหัสดังต่อไปนี้:

นำเข้า 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);

-

-