อัลกอริทึม การค้นหาเชิงวิวัฒนาการ (Evolutionary Search) ใน C++- คำอธิบาย ตัวอย่าง และโค้ด

อัลกอริทึมการค้นหาวิวัฒนาการเป็นวิธีการเพิ่มประสิทธิภาพตามกลไกของวิวัฒนาการตามธรรมชาติ อัลกอริทึมนี้จำลองกระบวนการวิวัฒนาการของบุคคลภายในประชากรหลายชั่วอายุคนเพื่อหาทางออกที่ดีที่สุดสำหรับปัญหา

มันทำงานอย่างไร

1. การเริ่มต้นประชากร: สร้างประชากรเริ่มต้นของบุคคลที่สร้างขึ้นแบบสุ่ม
2. การประเมิน: ประเมินคุณภาพของแต่ละคนในกลุ่มประชากรตามหน้าที่วัตถุประสงค์หรือเกณฑ์การประเมิน
3. การคัดเลือก: เลือกกลุ่มย่อยของบุคคลที่ดีที่สุดจากประชากรปัจจุบันตามความน่าจะเป็นหรือเกณฑ์การคัดเลือก
4. วิวัฒนาการ: สร้างเจเนอเรชันใหม่โดยใช้การดำเนินการแบบครอสโอเวอร์และการกลายพันธุ์กับบุคคลที่เลือก
5. การวนซ้ำ: ทำซ้ำขั้นตอนที่ 2 ถึง 4 ในหลายรุ่นจนกว่าจะได้ผลลัพธ์ที่น่าพอใจหรือถึงจำนวนการวนซ้ำที่กำหนดไว้ล่วงหน้า

ตัวอย่าง: การเพิ่มประสิทธิภาพ Fibonacci ฟังก์ชันโดยใช้การค้นหาแบบวิวัฒนาการ

พิจารณาปัญหาการหาค่าสูงสุดของ Fibonacci ฟังก์ชัน F(x) = F(x-1) + F(x-2) โดยที่ F(0) = 0, F(1) = 1 เราต้องการหาค่าของ x ซึ่ง F(x) ถูกขยายให้ใหญ่สุด วิธีการค้นหาแบบวิวัฒนาการสามารถสร้างประชากรของค่า x แบบสุ่ม วิวัฒนาการพวกมันข้ามรุ่นเพื่อค้นหาค่า x ที่เหมาะสมที่สุด

ตัวอย่างโค้ดในภาษา C++

#include <iostream>  
#include <vector>  
#include <cstdlib>  
#include <ctime>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int evolutionSearchFibonacci(int populationSize, int numGenerations) {  
    srand(time(0));  
  
    std::vector<int> population(populationSize);  
    for(int i = 0; i < populationSize; ++i) {  
        population[i] = rand() % populationSize;  
    }  
  
    for(int gen = 0; gen < numGenerations; ++gen) {  
        int bestIndex = 0;  
        for(int i = 1; i < populationSize; ++i) {  
            if(fibonacci(population[i]) > fibonacci(population[bestIndex])) {  
                bestIndex = i;  
            }  
        }  
  
        // Crossover and mutation operations can be applied here  
  
        // Example: Replace the worst individual with the best individual  
        population[0] = population[bestIndex];  
    }  
  
    return population[0];  
}  
  
int main() {  
    int populationSize = 50;  
    int numGenerations = 100;  
    int result = evolutionSearchFibonacci(populationSize, numGenerations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

ในตัวอย่างนี้ เราใช้วิธี Evolutionary Search เพื่อปรับ Fibonacci ฟังก์ชัน ให้เหมาะสม เราสร้างประชากรด้วยค่า x แบบสุ่ม พัฒนาพวกมันข้ามรุ่นโดยเลือกบุคคลที่ดีที่สุดและใช้การดำเนินการแบบครอสโอเวอร์และการกลายพันธุ์