ฉันจะไม่แนะนำหลักการโดยละเอียดและคำจำกัดความเฉพาะของอัลกอริทึมทางพันธุกรรมที่นี่ หากคุณต้องการทราบคุณสามารถใช้ Baidu เพื่อเรียนรู้ได้ ที่นี่ฉันจะแนะนำความเข้าใจของคุณเกี่ยวกับอัลกอริทึมทางพันธุกรรมสั้น ๆ บทความนี้ใช้กฎไบนารีสำหรับการเข้ารหัสยีน
แนวคิดอัลกอริทึม:
อัลกอริทึมทางพันธุกรรมหมายถึงทฤษฎีวิวัฒนาการของดาร์วินและเชื่อว่าสปีชีส์กำลังพัฒนาไปในทิศทางที่เป็นบวก (การอยู่รอดของผู้ที่เหมาะสมที่สุด) ดังนั้นจึงสามารถพิจารณาได้ว่าหลังจากพีชคณิตเพียงพอค่าสูงสุดที่ได้รับใกล้เคียงกับค่าสูงสุดที่แท้จริง
ขั้นตอนอัลกอริทึม:
ส่วนการใช้งานอัลกอริทึม-ยีน
1. ประชากรแต่ละคน (ที่นี่พิจารณาโครโมโซม) ในแต่ละบุคคลเราเพิ่มคุณลักษณะสองอย่างให้กับบุคคลนี้คือความเหมาะสม (ค่าฟังก์ชัน) ที่สอดคล้องกับยีนและยีนของแต่ละบุคคล
โครโมโซมระดับสาธารณะ {บูลีนส่วนตัว [] ยีน; // ลำดับยีนคะแนนส่วนตัวสองคะแนน; // คะแนนฟังก์ชั่นที่สอดคล้องกัน} 2. สร้างลำดับยีนแบบสุ่ม ไม่ว่าแต่ละตำแหน่งของยีนคือ 0 หรือ 1 นี่เป็นวิธีที่สุ่มอย่างสมบูรณ์เพื่อให้บรรลุ
โครโมโซมสาธารณะ (ขนาด int) {ถ้า (ขนาด <= 0) {return; } เริ่มต้น (ขนาด); สำหรับ (int i = 0; i <size; i ++) {ยีน [i] = math.random ()> = 0.5; }} โมฆะส่วนตัวเริ่มต้น (ขนาด int) {ถ้า (ขนาด <= 0) {return; } ยีน = บูลีนใหม่ [ขนาด]; - 3. แปลงยีนเป็นค่าที่สอดคล้องกันตัวอย่างเช่นจำนวนที่สอดคล้องกับ 101 คือ 5 และใช้การดำเนินการบิตที่นี่เพื่อนำไปใช้
สาธารณะ int getNum () {ถ้า (ยีน == null) {return 0; } int num = 0; สำหรับ (บูลีนบูล: ยีน) {num << = 1; if (bool) {num += 1; }} return num; - 4. หากการกลายพันธุ์ของยีนเกิดขึ้นตำแหน่งของการกลายพันธุ์จะถูกนำไปใช้อย่างสมบูรณ์ในวิธีการสุ่ม หลักการการกลายพันธุ์คือการเปลี่ยนจาก 1 เป็น 0 และ 0 เป็น 1
การกลายพันธุ์ของโมฆะสาธารณะ (int num) {// อนุญาตให้กลายพันธุ์ int size = gene.length; สำหรับ (int i = 0; i <num; i ++) {// มองหาตำแหน่งการกลายพันธุ์ int at = ((int) (math.random () * ขนาด)) % ขนาด; // ค่าหลังจากการกลายพันธุ์บูลีนบูล =! ยีน [ที่]; ยีน [ที่] = บูล; - 5. การโคลนนิ่งยีนใช้ในการผลิตรุ่นต่อไป ขั้นตอนนี้คือการคัดลอกยีนที่มีอยู่
โคลนโครโมโซมคงที่สาธารณะ (โครโมโซมสุดท้าย c) {ถ้า (c == null || c.gene == null) {return null; } โครโมโซมสำเนา = โครโมโซมใหม่ (); Copy.InitGenesize (C.Gene.Length); สำหรับ (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.gene [i]; } ส่งคืนสำเนา; - 6. พ่อแม่ทั้งสองผลิตรุ่นต่อไปและที่นี่บุคคลสองคนผลิตลูกหลานสองคน ยีนที่เฉพาะเจาะจงใดที่แตกต่างจากนักเรียนจะสุ่มอย่างสมบูรณ์
รายการคงที่สาธารณะ <Hromosome> พันธุกรรม (โครโมโซม P1, โครโมโซม P2) {ถ้า (p1 == null || p2 == null) {// มีหนึ่งในโครโมโซมที่ว่างเปล่า } if (p1.gene == null || p2.gene == null) {// มีหนึ่งในโครโมโซมที่ไม่มีลำดับยีนและไม่ได้สร้าง null return รุ่นต่อไป; } if (p1.gene.length! = p2.gene.length) {// ความยาวของลำดับยีนโครโมโซมไม่ได้สร้าง null return รุ่นต่อไป; } โครโมโซม C1 = โคลน (P1); โครโมโซม C2 = โคลน (P2); // สร้างตำแหน่ง cross-swap ขนาด int แบบสุ่ม = c1.gene.length; int a = ((int) (math.random () * ขนาด)) ขนาด %; int b = ((int) (math.random () * ขนาด)) ขนาด %; int min = a> b? B: A; int max = a> b? A: B; // ยีน cromex ที่ตำแหน่งสำหรับ (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.gene [i]; c2.gene [i] = t; } รายการ <Hromosome> list = new ArrayList <Hromosome> (); list.add (C1); list.add (C2); รายการคืน; - อัลกอริทึมการใช้งานอัลกอริทึม
1. สำหรับอัลกอริทึมทางพันธุกรรมเราจำเป็นต้องมีประชากรที่สอดคล้องกันและค่าคงที่บางอย่างที่เราต้องตั้งค่า: จำนวนประชากร, ความยาวของยีน, จำนวนการกลายพันธุ์ของยีน, อัตราการกลายพันธุ์ของยีน ฯลฯ สำหรับรายละเอียดโปรดดูรหัสต่อไปนี้:
บทคัดย่อระดับสาธารณะคลาส GeneticalGorithm {รายการส่วนตัว <SHOMOSOME> ประชากร = ใหม่ arrayList <Hromosome> (); // ประชากรส่วนตัว int popsize = 100; // จำนวนประชากร int private int genesize; // ความยาวสูงสุด int maxiternum = 500; // การกลายพันธุ์สูงสุด ความยาวแบบอะซิงโครนัสการสร้าง INT ส่วนตัว = 1; // ปัจจุบันมีกี่ชั่วอายุคนที่สืบทอดมา BestScore; // คะแนนที่ดีที่สุดส่วนตัวสองส่วนที่เลวร้ายที่สุด; // คะแนนแย่ที่สุดสองเท่าส่วนตัวสองเท่า; // คะแนนรวมสองค่าเฉลี่ยสองค่าเฉลี่ย; // คะแนนเฉลี่ยส่วนตัวสองเท่า x; // บันทึกค่า x ที่ดีที่สุดในประชากรประวัติศาสตร์เอกชนคู่ y; // บันทึกค่า y ที่ดีที่สุดในประชากรประวัติศาสตร์ส่วนตัว int genei; // พีชคณิตที่ XY ตั้งอยู่} 2. เริ่มต้นประชากร ในตอนต้นของอัลกอริทึมทางพันธุกรรมเราจำเป็นต้องเริ่มต้นประชากรดั้งเดิมซึ่งเป็นรุ่นแรกดั้งเดิม
โมฆะส่วนตัว init () {สำหรับ (int i = 0; i <popsize; i ++) {population = arrayList ใหม่ <Hromosome> (); โครโมโซม Chro = โครโมโซมใหม่ (Genesize); PUSIC.ADD (Chro); } cacultescore (); - 3. หลังจากมีประชากรเริ่มต้นแล้วเราจำเป็นต้องคำนวณความเหมาะสมของประชากรเช่นเดียวกับการออกกำลังกายที่ดีที่สุดการออกกำลังกายที่เลวร้ายที่สุดและการออกกำลังกายโดยเฉลี่ย ฯลฯ
โมฆะส่วนตัว cacultescore () {setChromosomescore (population.get (0)); bestscore = pumple.get (0) .getScore (); worstscore = pumple.get (0) .getScore (); totalsCore = 0; สำหรับ (โครโมโซม chro: ประชากร) {setchromosomescore (chro); if (chro.getScore ()> bestScore) {// ตั้งค่ายีนที่ดีที่สุด bestScore = chro.getScore (); if (y <bestscore) {x = changex (chro); y = bestscore; Genei = Generation; }} if (chro.getScore () <worstscore) {// ตั้งค่ายีนที่เลวร้ายที่สุด WORSTSCORE = chro.getScore (); } totalsCore += chro.getScore (); } AverAgesCore = totalScore / popsize; // ค่าเฉลี่ยที่เกิดจากปัญหาความถูกต้องมากกว่าค่าที่ดีที่สุดตั้งค่าเฉลี่ยเป็นค่า averagescore = averagescore> bestScore? Bestscore: Averagescore; - 4. เมื่อคำนวณความฟิตของแต่ละบุคคลเราจำเป็นต้องคำนวณค่า y ที่สอดคล้องกันตามยีน ที่นี่เราตั้งวิธีนามธรรมสองวิธีในการใช้งานการใช้งานเฉพาะโดยการใช้งานคลาส
โมฆะส่วนตัว setChromosomescore (โครโมโซม chro) {ถ้า (chro == null) {return; } double x = changex (chro); double y = caculyy (x); chro.setscore (y); } / ** * @param chro * @return * @description: แปลงไบนารีเป็น X * / บทคัดย่อสาธารณะที่สอดคล้องกัน Double Changex (โครโมโซม chro); / ** * @param x * @return * @description: คำนวณค่า y ตาม x y = f (x) */ บทคัดย่อสาธารณะ double caculyy (double x); 5. หลังจากคำนวณความเหมาะสมของประชากรเราจำเป็นต้องใช้วิธีการพนันแผ่นเสียงเพื่อเลือกบุคคลที่สามารถสร้างรุ่นต่อไปได้ มีเงื่อนไขที่นี่เฉพาะในกรณีที่ความฟิตของแต่ละบุคคลไม่น้อยกว่าความฟิตเฉลี่ยคนรุ่นต่อไปจะเกิด (ผู้ที่เหมาะสมที่สุดอยู่รอด)
โครโมโซมส่วนตัว getParentChromosome () {double slice = math.random () * totalscore; ผลรวมสองเท่า = 0; สำหรับ (โครโมโซม chro: ประชากร) {sum += chro.getScore (); // ไปที่ตำแหน่งที่สอดคล้องกันและความฟิตไม่น้อยกว่าความฟิตเฉลี่ยถ้า (sum> slice && chro.getScore ()> = averagescore) {return chro; }} return null; - 6. หลังจากเลือกบุคคลที่สามารถสร้างรุ่นต่อไปคุณต้องผสมพันธุ์เพื่อผลิตรุ่นต่อไป
โมฆะส่วนตัว Evolve () {รายการ <SHORMOSOME> ChildPopulation = New ArrayList <Hromosome> (); // สร้างประชากรรุ่นต่อไปในขณะที่ (childpopulation.size () <popsize) {โครโมโซม p1 = getParentchromosome (); โครโมโซม P2 = getParentchromosome (); รายการ <Hromosome> เด็ก = Chromosome.Genetic (P1, P2); ถ้า (เด็ก! = null) {สำหรับ (โครโมโซม chro: เด็ก) {childpopulation.add (chro); }}} // แทนที่ประชากรเก่าด้วยรายการประชากรใหม่ <Hromosome> T = ประชากร; ประชากร = เด็ก t.clear (); t = null; // การกลายพันธุ์ของยีน (); // คำนวณความฟิตของประชากรใหม่ cacultescore (); - 7. การกลายพันธุ์ทางพันธุกรรมอาจเกิดขึ้นในระหว่างกระบวนการผลิตรุ่นต่อไป
การกลายพันธุ์ของโมฆะส่วนตัว () {สำหรับ (โครโมโซม chro: ประชากร) {ถ้า (math.random () <กลายพันธุ์) {// การกลายพันธุ์ของยีนเกิดขึ้น int int mutationnum = (int) (math.random () * maxmutationNum); Chro.mutation (MutationNum); - 8. ทำซ้ำขั้นตอนข้างต้นทีละขั้นตอน
โมฆะสาธารณะ caculte () {// เริ่มต้นการสร้างประชากร = 1; init (); ในขณะที่ (Generation <maxiternum) {// วิวัฒนาการทางพันธุกรรมที่เป็นที่นิยม (); พิมพ์(); Generation ++; -เขียนคลาสการใช้งาน
เนื่องจากคลาสของอัลกอริทึมทางพันธุกรรมข้างต้นเป็นคลาสนามธรรมเราจึงต้องเขียนคลาสการใช้งานสำหรับกรณีเฉพาะโดยสมมติว่าเราคำนวณค่าสูงสุดของ y = 100-log (x) บน [6,106]
1. เราสมมติว่าความยาวของยีนคือ 24 (ความยาวของยีนถูกกำหนดโดยความยาวที่มีประสิทธิภาพของผลลัพธ์ที่ต้องการ) ดังนั้นค่าไบนารีสูงสุดที่สอดคล้องกันคือ 1 << 24 เราทำการตั้งค่าต่อไปนี้
Public Class GeneticalGorithmtest ขยาย Geneticetygorithm {สาธารณะคงที่สุดท้าย int num = 1 << 24; Public GeneticalGorithMtest () {Super (24); - 2. ใช้วิธีนามธรรมของค่า x
@Override สาธารณะ Double Changex (โครโมโซม chro) {// วิธีการที่สร้างขึ้นอัตโนมัติ todo return return ((1.0 * chro.getNum () / num) * 100) + 6; - 3. ใช้วิธีนามธรรมของ Y
@Override public double caculyy (double x) {// todo วิธีการสร้างอัตโนมัติ stub return 100 - math.log (x); -การรันผลลัพธ์
คิดถึงอัลกอริทึมทางพันธุกรรม
ฉันได้อ่านคำแนะนำมากมายเกี่ยวกับอัลกอริทึมทางพันธุกรรม โซลูชั่นที่ดีที่สุดที่กล่าวถึงข้างต้นเป็นค่าส่วนใหญ่ของรุ่นสุดท้าย ฉันมีคำถาม ทำไมฉันถึงรู้ว่าค่ามากที่สุดในทุกแถบด้านบนนั่นคือค่า XY ในโปรแกรมทำไมฉันถึงใช้ค่า XY เป็นค่าผลลัพธ์สุดท้ายของอัลกอริทึมทางพันธุกรรมได้
กรอกรหัส
1. คลาสโครโมโซม
/ ***@คำอธิบาย: โครโมโซมทางพันธุกรรม*/ แพ็คเกจ com.lulei.genetic.algorithm; นำเข้า java.util.arraylist; นำเข้า java.util.list; โครโมโซมระดับสาธารณะ {บูลีนส่วนตัว [] ยีน; // ลำดับยีนคะแนนส่วนตัวสองคะแนน; // ฟังก์ชั่นที่สอดคล้องกันคะแนนสาธารณะสองเท่าได้รับ () {คะแนนคืน; } โมฆะสาธารณะ setScore (คะแนนสองเท่า) {this.score = คะแนน; } / *** @param size* ลำดับยีนที่สร้างขึ้นแบบสุ่ม* / โครโมโซมสาธารณะ (ขนาด int) {ถ้า (ขนาด <= 0) {return; } เริ่มต้น (ขนาด); สำหรับ (int i = 0; i <size; i ++) {ยีน [i] = math.random ()> = 0.5; }} / *** สร้างยีนใหม่* / โครโมโซมสาธารณะ () {} / *** @param c* @return* @description: การโคลนนิ่งยีน* / โครโมโซมคงที่สาธารณะ } โครโมโซมสำเนา = โครโมโซมใหม่ (); Copy.InitGenesize (C.Gene.Length); สำหรับ (int i = 0; i <c.gene.length; i ++) {copy.gene [i] = c.gene [i]; } ส่งคืนสำเนา; } / *** @param size* @description: เริ่มต้นความยาวยีน* / โมฆะส่วนตัวเริ่มต้น (ขนาด int) {ถ้า (ขนาด <= 0) {return; } ยีน = บูลีนใหม่ [ขนาด]; } /** * @param c1 * @param c2 * @description: การสร้างพันธุกรรมเพื่อสร้างรุ่นต่อไป * /รายการคงที่สาธารณะ <Shromosome> พันธุกรรม (โครโมโซม P1, โครโมโซม P2) {ถ้า (p1 == null || p2 == null) {// } if (p1.gene == null || p2.gene == null) {// มีหนึ่งในโครโมโซมที่ไม่มีลำดับยีนและไม่ได้สร้าง null return รุ่นต่อไป; } if (p1.gene.length! = p2.gene.length) {// ความยาวของลำดับยีนโครโมโซมไม่ได้สร้าง null return รุ่นต่อไป; } โครโมโซม C1 = โคลน (P1); โครโมโซม C2 = โคลน (P2); // สร้างตำแหน่ง cross-swap ขนาด int แบบสุ่ม = c1.gene.length; int a = ((int) (math.random () * ขนาด)) ขนาด %; int b = ((int) (math.random () * ขนาด)) ขนาด %; int min = a> b? B: A; int max = a> b? A: B; // ยีน cromex ที่ตำแหน่งสำหรับ (int i = min; i <= max; i ++) {boolean t = c1.gene [i]; c1.gene [i] = c2.gene [i]; c2.gene [i] = t; } รายการ <Hromosome> list = new ArrayList <Hromosome> (); list.add (C1); list.add (C2); รายการคืน; } /*** @param num* @description: การแปรผันเกิดขึ้นในตำแหน่ง NUM ของยีน Num* /การกลายพันธุ์โมฆะสาธารณะ (int num) {// อนุญาตให้กลายพันธุ์ int size = gene.length; สำหรับ (int i = 0; i <num; i ++) {// ค้นหาตำแหน่งการกลายพันธุ์ int at = ((int) (math.random () * ขนาด)) % ขนาด; // ค่าหลังจากการกลายพันธุ์บูลีนบูล =! ยีน [ที่]; ยีน [ที่] = บูล; }} / *** @return* @description: แปลงยีนเป็นตัวเลขที่สอดคล้องกัน* / public int getNum () {ถ้า (ยีน == null) {return 0; } int num = 0; สำหรับ (บูลีนบูล: ยีน) {num << = 1; if (bool) {num += 1; }} return num; - 2. คลาส Geneticalgorithm
/ ** *@คำอธิบาย: */ แพ็คเกจ com.lulei.genetic.algorithm; นำเข้า java.util.arraylist; นำเข้า java.util.list; บทคัดย่อระดับสาธารณะคลาส GeneticalGorithm {รายการส่วนตัว <SHORMOSOME> ประชากร = ใหม่ ArrayList <CHROMOSOME> (); private int popsize = 100; // จำนวนที่นิยม private int genesize; // ความยาวของยีนสูงสุด int maxiternum = 500; // จำนวนสูงสุดของการวนซ้ำส่วนตัวการกลายพันธุ์สองครั้ง = 0.01; // ความน่าจะเป็นของการกลายพันธุ์ของยีน Bestscore สองครั้งส่วนตัว; // คะแนนที่ดีที่สุดสองเท่าส่วนตัว WORSTSCORE; // คะแนนที่แย่ที่สุดสองเท่าส่วนตัวสองเท่า; // คะแนนรวมสองค่าเฉลี่ยสองค่าเฉลี่ย; // คะแนนเฉลี่ยสองเท่าส่วนตัว x; // บันทึกค่า x ที่ดีที่สุดในประชากรประวัติศาสตร์เอกชนคู่ y; // บันทึกค่า y ที่ดีที่สุดในประวัติศาสตร์ประชากรส่วนตัว int genei; // พีชคณิตโดยที่ XY ตั้งอยู่ในที่สาธารณะ Geneticalgorithm (int genesize) {this.genesize = genesize; } โมฆะสาธารณะ caculte () {// เริ่มต้นการสร้างประชากร = 1; init (); ในขณะที่ (Generation <maxiternum) {// วิวัฒนาการทางพันธุกรรมที่เป็นที่นิยม (); พิมพ์(); Generation ++; }} / *** @description: ผลลัพธ์ผลลัพธ์* / private void print () { System.out.println ("-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- System.out.println ("การออกกำลังกายที่เลวร้ายที่สุดคือ" + Worstscore); @Description: เริ่มต้นประชากร*/ private void init () {สำหรับ (int i = 0; i <popsize; i ++) {ประชากร = arraylist ใหม่ <Chromosome> (); เป็นโมฆะ Evolve () {รายการ <SHORMOSOME> ChildPopulation = arrayList ใหม่ <Hromosome> (); P2) (เด็ก ๆ ! @return * @description: รูเล็ตเลือกโครโมโซมที่สามารถสืบทอดรุ่นต่อไปได้ */ โครโมโซมส่วนตัว getParentchromosome () {slice คู่ = math.random () * totalscore; {return chro;}}} null; SetChromosomescore (chro); chro.getScore (); chro: ประชากร) {ถ้า (math.random () <การกลายพันธุ์) {// การกลายพันธุ์ของยีนเกิดขึ้น int mutationnum = (int) (math.random () * maxmutationnum); {ถ้า chro == null) {return; ค่า y ตาม x y = f (x) */ บทคัดย่อสาธารณะ double caculyy (double x); Setmaxiternum (int maxiternum) {this.maxiternum = maxiternum; GetWorstscore () {return worstscore; 3. คลาส Geneticalgorithmtest
/ ** *@คำอธิบาย: */ แพ็คเกจ com.lulei.genetic.algorithm; Public Class GeneticalGorithmtest ขยาย Geneticetygorithm {สาธารณะคงที่สุดท้าย int num = 1 << 24; Public GeneticalGorithMtest () {Super (24); } @Override Public Double Changex (โครโมโซม chro) {// วิธีการที่สร้างขึ้นอัตโนมัติ todo return return ((1.0 * chro.getNum () / num) * 100) + 6; } @Override public double caculatey (double x) {// วิธีการที่สร้างอัตโนมัติ todo stub return 100 - math.log (x); } โมฆะคงที่สาธารณะหลัก (String [] args) {GeneticalGorithMTest Test = ใหม่ GeneticalGorithMTest (); test.caculte (); -ข้างต้นเป็นการแนะนำรายละเอียดเกี่ยวกับอัลกอริทึมทางพันธุกรรม Java ฉันหวังว่ามันจะเป็นประโยชน์สำหรับทุกคนในการเรียนรู้อัลกอริทึมทางพันธุกรรมของ Java