Genetic Programming - Thuật toán di truyền

Chọn lọc tự nhiên là quá trình mà các cá thể có đặc điểm di truyền phù hợp nhất với môi trường sống sẽ có nhiều khả năng sống sót và sinh sản hơn. Qua thời gian, các đặc điểm có lợi này sẽ được truyền lại cho thế hệ sau, làm tăng khả năng thích nghi của quần thể với môi trường. Ví dụ, hươu cao cổ có cổ dài hơn có thể tiếp cận nguồn lá cây cao, giúp chúng sống sót tốt hơn trong môi trường khan hiếm thức ăn dưới thấp. Các yếu tố như sự thay đổi môi trường, cạnh tranh sinh tồn và biến dị di truyền đều đóng vai trò quan trọng trong quá trình này. Nhờ chọn lọc tự nhiên, các loài có thể tiến hóa và phát triển để phù hợp với điều kiện sống không ngừng biến đổi.

Lấy cảm hứng từ quá trình chọn lọc tự nhiên, nhà khoa học máy tính John Holland đã phát minh ra thuật toán di truyền vào những năm 1960. Thuật toán này cũng đã đặt nền tảng cho các phương pháp tối ưu tiến hóa, mở đường cho các nghiên cứu và ứng dụng hiện đại trong AI, Machine Learning.

Bài toán ví dụ

Có một căn phòng chứa \(n\) bóng đèn, mỗi bóng đèn có thể đang sáng hoặc đang tắt. Để điều khiển việc tắt hoặc mở bóng đèn, có một bản \(n\) các công tắc đặt bên ngoài phòng. Làm cách nào bạn có thể bật sáng toàn bộ các bóng đèn trong phòng với bảng công tắc này với các điều kiện:

• Bạn không được vào phòng để xem trạng thái bóng đèn mà chỉ có duy nhất một thông tin là có bao nhiêu bóng đang bật

• Bạn không biết là công tắc nào ứng với cái đèn nào trong phòng

• Công tắc chỉ có hai trạng thái hoặc gạt lên hoặc gạt xuống và không biết ứng với trạng thái mở hay tắt đèn

Dĩ nhiên, bạn có thể giải bài toán này bằng cách lần lượt gạt từng công tắc và kiểm tra xem có bao nhiêu bóng đang được bật để rồi tìm ra trạng thái của bảng công tắc để bật toàn bộ bóng đèn. Trong bài toán này, mình xin giới thiệu một phương pháp để giải bài toán trên bằng thuật toán di truyền.

Khởi tạo

Ý tưởng chủ đạo của thuật toán là ta sẽ khởi tạo ngẫu nhiên một quần thể (population) các lời giải. Mỗi lời giải thể hiện một trạng thái của bảng công tắc và được xem như một cá thể (individual) trong quần thể. Với mỗi lời giải sẽ có một số lượng đèn được bật tương ứng, đây cũng chính là thông số đánh giá chất lượng của một lời giải (fitness). Để thực hiện thuật toán, ta lựa chọn (selection) những lời giải có fitness tốt nhất, lấy thông tin nhiễm sắc thể (chromosome) của chúng đem lai ghép (crossover) với nhau để tạo ra lời giải mới để đưa vào quần thể. Để giúp cho quần thể có tính đa dạng, đôi khi chúng ta sẽ tạo ra biến dị (mutation) trong khi lai tạo ra cá thể mới.

Đối với bàn toán này, ta sẽ xem một trạng thái của bảng công tắc như là một nhiễm sắc thể (chromosome), có giá trị là mảng các bit 0 và 1 tương ứng với trạng thái gạt lên và và gạt xuống của mỗi công tắc. Như vậy một chromosome là một mảng chứa \(n\) phần tử. Một hàm số đánh giá fitness của mỗi cá thể bằng cách đưa ra số lượng đèn đang bật tương ứng với cá thể ấy. Như vậy mỗi cá thể sẽ có 2 thành phần: chromosome và fitness score.

Thuật toán

Thuật toán bao gồm 3 thành phần chính như sau:

• Chọn lọc cá thể tốt nhất (Selection): ta chọn ra \(m\) cá thể trong quần thể sao cho những cá thể có fitness score càng cao thì tỷ lệ được chọn càng cao. Thuật toán có thể được hình dung như sau:

  

     selection() {       
            // Calculate the sum of all fitness scores
            const sum = this.population.reduce((acc, individual) => acc + individual.fitnessScore, 0);
            const selected = [];
            const numIndividuals = 2;
            for (let i = 0; i < numIndividuals; i++) {
                let random = Math.random() * sum;
                let current = 0;
                // Select an individual based on the fitness score            
                for (let j = 0; j < this.population.length; j++) {
                    // Add the fitness score of the current individual
                    current += this.population[j].fitnessScore;
                    // until the sum is greater than the random value
                    // the individual is selected
                    if (random <= current) {
                        selected.push(this.population[j]);
                        break;
                    }
                }
            }
            return selected;
        }
  

• Lai ghép (Crossover): Lấy 2 cá thể \(A,B\) trong \(m \) cá thể được chọn và thực hiện lai ghép bằng cách lấy \(k\) bit đầu của chromosome \(A\) tráo với \(k\) bit đầu của chomosome \(B\) để tạo ra 2 chromosome mới. Ví dụ: Chromosome \(A=11001\), chromosome \(B=10101\), ta lấy 2 bit đầu của \(A\) và \(B\) tráo nhau để tạo ra chromosome \(C=\underbrace{11}_{A} \underbrace{101}_{B}\) và \(D=\underbrace{10}_{B} \underbrace{001}_{A}\)

    crossover(parent1, parent2) {
            // Randomly select a split point
            const splitPoint = Math.floor(Math.random() * parent1.chromosome.length);
            // Create two children by combining the parents
            // and swapping the chromosome parts        
            const child1 = new Individual(parent1.chromosome.slice(0, splitPoint) + parent2.chromosome.slice(splitPoint));
            const child2 = new Individual(parent2.chromosome.slice(0, splitPoint) + parent1.chromosome.slice(splitPoint));
            return [child1, child2];
        }
  

• Biến dị (Mutation): Với các cá thể mới vừa tạo ra, có một tỷ lệ nhỏ biến dị bằng cách thay ngẫu nhiên một bit nào đó của chromosome này từ 0 thành 1 hoặc ngược lại từ 1 thành 0. Ví dụ: khi biến dị xảy ra trên \(C = 11101 \implies C_{mutated}=11100\) biến dị tại vị trí cuối biến 1 thành 0.

    mutation(individual) {
            let chromosome = '';
            for (let i = 0; i < individual.chromosome.length; i++) {
                // Flip the bit with a probability of mutationRate
                if (Math.random() < this.mutationRate) {
                    chromosome += individual.chromosome[i] === '0' ? '1' : '0';
                } else {
                    chromosome += individual.chromosome[i];
                }
            }
            individual.chromosome = chromosome;
        }
  

Các bước của thuật toán:

• Bước 1:

  • Khởi tạo một số các cá thể ngẫu nhiên

  • Với mỗi cá thể, dùng fitness function để tính fitness score cho mỗi cá thể thông qua chromosome của nó

  • Thiết lập một hằng số \(T\) là threshold tượng trưng cho tỷ lệ xảy ra đột biến

• Lặp:

  • Bước 2: Chọn lọc

  • Bước 3: Lai ghép để tạo ra cá thể mới từ các cá thể được chọn lọc ở Bước 3

  • Bước 4: Thực hiện biến dị cho cá thể mới. Tại mỗi bit của chromosome, một số ngẫu nhiên \(x\) được tạo ra, nếu \(x < T\) thực hiện biến dị bằng cách swap bit.

  • Bước 5: Đưa cá thể ấy vào quần thể để thay thế những cá thể có fitness yếu nhất

  • Ngừng lặp nếu cá thể mới đã thỏa mãn yêu cầu tìm kiếm hoặc đã lặp một số lần đủ lớn

evolve(target) {
        // Calculate the fitness score for each individual
        this.population.forEach(individual => individual.fitnessScore = this.calculateFitness(individual, target));        
        // Select two individuals from the population
        const selected = this.selection();
        // Perform crossover
        const children = this.crossover(selected[0], selected[1]);
        // Perform mutation
        this.mutation(children[0]);
        this.mutation(children[1]);
        // Calculate the fitness score for the children
        children[0].fitnessScore = this.calculateFitness(children[0], target);
        children[1].fitnessScore = this.calculateFitness(children[1], target);        
        // sort the population by fitness score
        this.population.sort((a, b) => a.fitnessScore - b.fitnessScore);
        // Replace the two worst individuals with
        // the two children
        this.population[0] = children[0];
        this.population[1] = children[1];
    }

Demo