กลยุทธ์เชิงวิวัฒนาการ

## ประวัติ
กลยุทธ์เชิงวิวัฒนาการถูกพัฒนาขึ้นมาโดย อิงโก เรเชนเบิร์ค Ingo Rechenberg และ ฮานส์-พอลล์ ชเวอเฟล Hans-Paul Schwefel ในช่วง 1970s ในตอนแรกนั้นกลยุทธ์เชิงวิวัฒนาการถูกพัฒนามาเพื่อ
แก้ปัญหาการออกแบบทางวิศวกรรม ในเรื่อง การหาค่าเหมาะสมของรูปร่างทางอากาศพลศาสตร์ (aerodynamic shape optimization)

## ลักษณะและการหาคำตอบของกลยุทธ์เชิงวิวัฒนาการ

กลยุทธ์เชิงวิวัฒนาการมีลักษณะสำคัญ ดังนี้
# กลยุทธ์เชิงวิวัฒนาการมีการออกแบบตัวแปรจากการเขียนโปรแกรมจริง ๆ เนื่องจากเป็นการออกแบบการวิวัฒนาการในระดับของลักษณะที่แสดงออก (Phenotype) ของแต่ละตัว
# กลยุทธ์เชิงวิวัฒนาการขึ้นอยู่กับการเลือกที่กำหนดได้และการกลายพันธุ์สำหรับการวิวัฒนาการ
# กลยุทธ์เชิงวิวัฒนาการใช้ตัวแปรเชิงกลยุทธ์

กลยุทธ์เชิงวิวัฒนาการนำหลักการของการวิวัฒนาการทางชีวภาพมาใช้ กล่าวคือ กระบวนกาคัดเลือกตามธรรมชาติ และกฎการอยู่รอดของผู้ที่เหมาะสมที่สุด (survival of the fittest)
โดยในการทำซ้ำแต่ละครั้งจะมีการคัดเลือกเพื่อตัดคำตอบที่อ่อนแอกว่าออกไป และคำตอบที่เหลือที่มี ค่าความแข็งแรง (fitness value) สูงกว่าจะถูกนำไปทำให้แตกแล้วรวมตัวกับคำตอบอื่น ๆ (recombine)

หรืออาจจะมีการเปลี่ยนแปลงค่าของคำตอบต่างๆเล็กน้อย (mutate) ทั้งการรวมตัวกับคำตอบอื่นและการเปลี่ยนแปลงค่าของคำตอบจะถูกทำไปเรื่อย ๆ
เพื่อสร้างคำตอบที่เหมาะสมระดับสากล (global optimization)ในกลยุทธ์เชิงวิวัฒนาการ ตัวแปรต่าง ๆ จะถูกแทนในรูปแบบที่ มีความยาวคงที่ และ เป็นค่าจริง ในเส้นสมมติ (fixed-length real-valued vector) แต่ละตำแหน่งในเส้นสมมติจะสอดคล้องกับลักษณะของแต่ละตัวแปร

วิธีหลักในการผลิตลูกหลานของตัวแปรในกลยุทธ์เชิงวิวัฒนาการคือ การกลายพันธุ์ของเกาส์ (Gaussian Mutation) เป็นการบวกค่าสุ่มจากการกระจายของเกาส์ (Gaussian Distribution) เข้าไปในแต่ละสมาชิกของเส้นสมมติรุ่นพ่อแม่เพื่อให้ได้เส้นสมมติรุ่นลูกดังภาพ และอีกวิธีที่ถูกใช้คือ การแตกแล้วรวมตัวกันใหม่ของสารพันธุกรรมขั้นกลาง (Intermediate Recombination) ซึ่งคือการนำเส้นสมมติพ่อ เส้นสมมติแม่มาหาค่าเฉลี่ยกัน โดยทำตัวต่อตัว เพื่อสร้างเส้นสมมติรุ่นลูกดังภาพ

center|thumb|300px| Gaussian Mutation
center|thumb|300px|Intermediate Recombination

ในการเลือกของกลยุทธ์เชิงวิวัฒนาการนั้นมีข้อจำกัดน้อยกว่าขั้นตอนวิธีเชิงพันธุกรรม (Genetic -Algorithm) และการโปรแกรมเชิงพันธุกรรม (Genetic Programming) เพราะ ลักษณะของการแทนตัวแปรเป็นเส้นสมมตินั้นสามารถสามารถหาค่าเฉลี่ยเพื่อหาเส้นสมมติรุ่นลูกได้ง่าย โดยปกติ พ่อแม่ N ตัวจะลูกเลือกอย่างสุ่มแบบเท่าเทียมกัน ไม่ขึ้นอยู่กับค่าของพ่อแม่แต่ละตัว และลูกหลานมากกว่า N ตัวจะถูกผลิตจากการแตกแล้วรวมตัวกันใหม่ของสารพันธุกรรมพ่อแม่ แล้วจะมีการเลือกผู้รอดชีวิต N ตัวโดยมีวิธีในการเลือกที่ถูกกำหนดไว้ โดยผู้รอดชีวิตสามารถถูกเลือกได้จากลูกหลานที่ดีที่สุด N ตัว หรือ จะเลือกจากทั้งพ่อแม่และลูกหลานที่ดีที่สุด N ตัวก็ได้

## รหัสเทียมของกลยุทธ์เชิงวิวัฒนาการ

 Input: μ,λ,ProblemSize                                  //จำนวนพ่อแม่,จำนวนลูก,ขนาดปัญหา
 Output: S[best]                                         //คำตอบที่ดีที่สุดของปัญหา
 
 Population F=\sum_{i=1}^{n-1}d_{i,(i+1)}+d_{n,1}

di,(i+1) ระยะทางระหว่างเมืองที่ i และเมืองที่ i+1 ของการเดินทาง และ dn,1 คือ ระยะทางระหว่างเมืองแรกกับเมืองสุดท้ายของการเดินทาง

## ดูเพิ่ม
*Evolutionary Strategy book 

## อ้างอิง

## แหล่งข้อมูลอื่น
* Evolutionary Strategies Paper
* The CMA Evolution Strategy 
* Tutorial 3: Build a Floating-Point Evolution Strategies Problem  

หมวดหมู่:ขั้นตอนวิธีเชิงวิวัฒนาการ
หมวดหมู่:ขั้นตอนวิธีเฟ้นสุ่ม