Differential Evolution
[สารบัญกลุ่มเรื่องที่กำลังศึกษา]
เนื้อหาตอนนี้สรุปจาก Section ที่ 2 ของบทความ Differential Evolution - A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces (Journal of Global Optimization 11: 341-359, 1997) ของ Rainer Storn กับ Kenneth Price
Differential Evolution (DE) เป็นอีกเทคนิคหนึ่งในตระกูล evolutionary algorithm ซึ่งผู้เขียนเคยส่งเข้าประกวด ICEO ครั้งแรก (1996) แล้วประสบผลสำเร็จ บอกว่าเป็น evolutionary algorithm ที่เร็วที่สุด DE เป็น parallel direct search method ที่ใช้ D-dimentional parameter vector จำนวน NP ตัวเป็นประชากรของรุ่น G
xi,G เมื่อ i = 1, 2, ..., NP
ซึ่งเราสร้าง vector ชุดนี้ได้โดยการสุ่มให้ครอบคลุมทั้ง parameter space หรือถ้าเป็นกรณีที่มี preliminary solution อยู่แล้ว ก็อาจจะใช้คำตอบดังกล่าวเป็นตัวตั้งต้นแล้วสร้างรุ่นแรกจากการเพิ่มสมาชิกที่ค่าเบี่ยงเบนจากคำตอบนั้นกระจายแบบปกติเข้าไปให้ได้ NP ตัว
จากนั้น DE จะสร้าง parameter vector ชุดใหม่ เรียกว่า trial vector จากขั้นตอน mutation กับ crossover แล้วเปรียบเทียบ trial vector กับ target vector (ซึ่งก็คือประชากรรุ่น G นั่นแหละ) โดยใช้ greedy criterion กล่าวคือ ใครให้ค่า cost function ต่ำกว่ากัน คนนั้นก็จะไปโผล่ในรุ่น G+1 ขั้นตอนนี้เรียกว่า selection แล้วทำซ้ำ mutation, crossover, selection, mutation ... ไปจนถึงจำนวนรุ่นที่กำหนด แล้วเอาประชากรตัวที่ดีที่สุดจากรุ่นสุดท้ายเป็นคำตอบ
ดูรายละเอียดของแต่ละขั้นตอน
Mutationเราเอา target vector xi,G เมื่อ i = 1, 2, ..., NP มาสร้าง mutant vector ด้วย
ui,G+1 = xr1,G + F*(xr2,G - xr3,G)
เมื่อ index r1, r2, r3 ∈ {1, 2, ..., NP} ถูกสุ่มขึ้นมาไม่ซ้ำกันและไม่ซ้ำกับ i (เพราะฉะนั้น DE ต้องการประชากรอย่างน้อย 4 คน), F เป็นจำนวนจริงคงที่ ∈ [0,2] ตัวอย่างการสร้าง mutant vector สองมิติแสดงดังรูป
Crossoverสิ่งที่เราจะได้รับจากขั้นตอนนี้คือ D-dimentional trial vector ui,G+1 = (u1i,G+1, u2i,G+1, ..., uDi,G+1) ซึ่งสร้างจาก
uji,G+1 = vji,G+1 ถ้า randb(j) <= CR หรือ j = rnbr(i)
uji,G+1 = xji,G ถ้าไม่ใช่เงื่อนไขแรก
เมื่อ randb(j) คือ ค่าสุ่มในช่วง [0,1] ซึ่งเป็นการสุ่มแบบ uniform ของ parameter ตัวที่ j, CR คือ ค่าคงที่ crossover ∈ [0,1] เช่นกัน, และ rnbr(i) คือ การสุ่ม index ตัวหนึ่งจากเซ็ต {1, 2, ..., D} เพื่อเป็นการรับประกันว่า จะมีพารามิเตอร์อย่างน้อยหนึ่งตัวของ ui,G+1 ที่มาจาก mutant vector vi,G+1
ขั้นตอน crossover แสดงตัวอย่างกรณีที่มีพารามิเตอร์ 7 ตัวดังรูป
Selectionเป็นการเปรียบเทียบ trial vector ui,G+1 กับ target vector xi,G ว่าใครจะได้เป็น target vector รุ่นถัดไป xi,G+1
ใน Section ที่ 4 ของบทความพูดถึงการเลือก NP, F, CR โดยมีคำแนะนำว่า NP ระหว่าง 5*D ถึง 10*D เวิร์ก, F = 0.5 เวิร์ก, CR ให้ลองที่ 0.1 และ CR ยิ่งมากยิ่งเร็ว ดังนั้น ครั้งแรกควรเริ่มที่ CR = 0.9 หรือ 0.1 ก่อนเพื่อดูว่าคำตอบแบบเร็ว ๆ เป็นไปได้มั้ย
| Create Date : 28 มกราคม 2558 |
| Last Update : 28 มกราคม 2558 16:53:54 น. |
|
1 comments
|
| Counter : 998 Pageviews. |
 |
|
|
ฝากข้อความหลังไมค์
Rss Feed
ผู้ติดตามบล็อก : 85 คน [
ให้ใจหายใจ สุขภาพ วิธีลดความอ้วน การดูแลสุขภาพ อาหารเพื่อสุขภาพ ออกกำลังกาย สุขภาพผู้หญิง สุขภาพผู้ชาย สุขภาพจิต โรคและการป้องกัน สมุนไพรไทย ผู้หญิง ศัลยกรรม ความสวยความงาม แม่ตั้งครรภ์ สุขภาพแม่ตั้งครรภ์ พัฒนาการตั้งครรภ์ 40 สัปดาห์ อาหารสำหรับแม่ตั้งครรภ์ โรคขณะตั้งครรภ์ การคลอด หลังคลอด การออกกำลังกาย ทารกแรกเกิด สุขภาพทารกแรกเกิด ผิวทารกแรกเกิด การพัฒนาการของเด็กแรกเกิด การดูแลทารกแรกเกิด โรคและวัคซีนสำหรับเด็กแรกเกิด เลี้ยงลูกด้วยนมแม่ อาหารสำหรับทารก เด็กโต สุขภาพเด็ก ผิวเด็ก การพัฒนาการเด็ก การดูแลเด็ก โรคและวัคซีนเด็ก อาหารสำหรับเด็ก การเล่นและการเรียนรู้ ครอบครัว ชีวิตครอบครัว ปัญหาภายในครอบครัว ความเชื่อ คนโบราณ