Sự tiến hóa của code [P7]

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

Bước 2 nói rằng, “Đánh giá mức độ thích ứng của mỗi phần tử trong quần thể và xây một bể giao phối”. Trước tiên hãy viết chương trình để đánh giá mức độ thích ứng của các thực thể (các thành viên trong quần thể). Trước đó chúng ta đã nói một hàm thích ứng khả dĩ là tổng số ký tự được gõ đúng. Hãy chỉnh lại hàm thích ứng này một chút như sau:

Fitness = Tổng số ký tự đúng/Tổng số ký tự

Chúng ta sẽ tính mức độ thích ứng ở đâu? Bởi vì class DNA chứa thông tin di truyền (tức cụm từ mà chúng ta sẽ kiểm tra với cụm từ mục tiêu), chúng ta có thể viết một hàm bên trong class DNA để tính điểm số thích ứng. Giả sử cụm từ mục tiêu của chúng ta là:

String target = "to be or not to be";

Chúng ta có thể so sánh mỗi “gen” của đối tượng với mỗi ký tự của cụm từ gốc, tăng điểm số lên 1 mỗi khi chúng ta có được một ký tự đúng.

class DNA {
  //Chúng ta khai báo một biến khác trong class DNA để tính mức độ thích ứng
  float fitness;
  //hàm tính điểm thích ứng
 
  void fitness () {
    int score = 0;
    for (int i = 0; i < genes.length; i++) {
      //có giống với kí tự gốc hay không?
      if (genes[i] == target.charAt(i)) {
        //Nếu giống, tăng điểm số lên 1
        score++;
      }
    }

    //mức độ thích ứng bằng điểm số trên tổng chiều dài của gen
    fitness = float(score)/target.length();
  }

Trong hàm draw(), việc đầu tiên ta làm là gọi hàm fitness() của mỗi phần tử trong quần thể.

void draw() {
  for (int i = 0; i < population.length; i++) {
    population[i].fitness();
  }

Sau khi chúng ta đã có điểm số thích ứng, chúng ta có thể xây bể giao phối, thứ chúng ta cần cho bước sinh sản. Bể giao phối là một cấu trúc dữ liệu mà từ đó ta chọn ra 2 cá thể cha mẹ. Hãy nhớ lại rằng việc chọn cá thể cha mẹ dựa trên nguyên lý xác suất tương ứng với giá trị thích ứng. Chúng ta chọn kiểu dữ liệu của bể giao phối là ArrayList.

ArrayList<DNA> matingPool = new ArrayList<DNA>();
for (int i = 0; i < population.length; i++) {
  //n bằng fitness nhân với 100, cho ta một kết quả số nguyên
  int n = int(population[i].fitness * 100);
    for (int j = 0; j < n; j++) {
      //thêm mỗi thành viên của quần thể vào bể giao phối n lần
      matingPool.add(population[i]);
    }
  }

Bước 3: Sinh sản

Bây giờ thì bể giao phối đã được tạo, đây là lúc để tạo ra cá thể con. Bước đầu tiên là chọn 2 cá thể cha mẹ. Một lần nữa, chúng ta được tùy ý để chọn 2 cá thể cha mẹ. Sự tùy ý này phản chiếu một cách chắc chắn về cách sinh sản của loài người và cũng là phương tiện tiêu chuẩn trong thuật toán di truyền truyền thống. Bạn có thể chọn sinh sản vô tính với một cá thể cha mẹ, hoặc đi đến một kế hoạch rằng một cá thể con có thể được tạo ra từ DNA của ba hoặc bốn cá thể cha mẹ. Đối với ví dụ này, chúng ta sẽ chọn phương án có hai cá thể cha mẹ và gọi chúng là parentA và parent B.

Điều đầu tiên ta cần là hai số nguyên ngẫu nhiên từ 0 cho tới giá trị kích thước của ArrayList.

int a = int(random(matingPool.size()));
int b = int(random(matingPool.size()));

Chúng ta sẽ lấy DNA của cá thể cha mẹ từ bể giao phối bằng 2 chỉ số này.

DNA parentA = matingPool.get(a);
DNA parentB = matingPool.get(b);

Ở ví dụ này, ta không quan tâm đến việc hai thực thể parentA và parentB có thể trùng nhau.

Sau khi có được 2 cá thể cha mẹ, ta sẽ thực hiện trao đổi chéo để tạo ra DNA cho cá thể con, sau đó ta sẽ thực hiện đột biến.

DNA child = parentA.crossover(parentB);
child.mutate();

Tất nhiên, hàm crossover()và mutate() không phải tự nhiên mà có. Chúng ta phải viết chúng trong class DNA. Hàm crossover() – trao đổi chéo, nhận một thực thể DNA như là một tham số và trả về một thực thể kiểu DNA mới, một cá thể con.

DNA crossover(DNA partner) {
    /*Cá thể con là một thực thể kiểu DNA. Lưu ý là DNA của cá thể con sẽ được tạo ngẫu nhiên bời hàm tạo, nhưng chúng ta sẽ viết đè lên sử dụng DNA của cá thể cha mẹ*/
    DNA child = new DNA();
    //Chọn một điểm giữa ngẫu nhiên trong mảng gen
    int midpoint = int(random(genes.length));

    for (int i = 0; i < genes.length; i++) {
      /*nếu i nằm trước điểm giữa, lấy DNA của một cá thể cha mẹ, nếu I nằm sau điểm giữa, lấy DNA của cá thể còn lại*/
      if (i > midpoint) child.genes[i] = genes[i];
      else child.genes[i] = partner.genes[i];
    }

    //trả về cá thể con
    return child;
  }

Hàm mutate() – đột biến thì đơn giản hơn hàm trao đổi chéo. Hàm này như sau:

void mutate() {
  //kiểm tra mỗi phần tử gen của mảng
    for (int i = 0; i < genes.length; i++) {
      if (random(1) < mutationRate) {
        //Đột biến, tạo một kí tự ngẫu nhiên
        genes[i] = (char) random(32,128);
      }//if
    }//for
  }//function

Kết quả

//Biến cho giải thuật

//Tỷ lệ đột biến
float mutationRate;

//số lượng dân số của quần thể
int totalPopulation = 150;

//mảng quần thể
DNA[] population;

//Bể giao phối ArrayList
ArrayList<DNA> matingPool;

//Cụm từ mục tiêu
String target;

void setup() {
  size(640, 360);
  //Khởi tạo cụm từ mục tiêu và tỷ lệ đột biến
  target = "to be or not to be";
  mutationRate = 0.01;
  //Bước 1: Khởi tạo quần thể
  population = new DNA[totalPopulation];
  for (int i = 0; i < population.length; i++) {
    population[i] = new DNA();
  }
}

void draw() {
//Bước 2: Chọn lọc
//Bước 2a: Tính toán mức độ thích ứng
  for (int i = 0; i < population.length; i++) {
    population[i].fitness();
  }
//Bước 2b: Xây bể giao phối
  ArrayList<DNA> matingPool = new ArrayList<DNA>();
   for (int i = 0; i < population.length; i++) {
  //thêm mỗi thành viên n lần tương ứng với điểm số thích ứng
    int n = int(population[i].fitness * 100);
    for (int j = 0; j < n; j++) {
      matingPool.add(population[i]);
    }
  }

//Bước 3: Tái tạo
  for (int i = 0; i < population.length; i++) {
    int a = int(random(matingPool.size()));
    int b = int(random(matingPool.size()));
    DNA partnerA = matingPool.get(a);
    DNA partnerB = matingPool.get(b);

//Bước 3a: Trao đổi chéo
    DNA child = partnerA.crossover(partnerB);

Bước 3b: Đột biến
    child.mutate(mutationRate);

/*Lưu ý là ta đã viết đè quần thể với các cá thể con mới. Khi hàm draw() chạy, chúng ta sẽ thực hiện tất cả các bước này một lần nữa với quần thể mới*/
    population[i] = child;

  }

}

Class DNA của chúng ta như sau:

class DNA {
  char[] genes;
  float fitness;
  // Tạo DNA ngẫu nhiên

  DNA() {
    genes = new char[target.length()];
    for (int i = 0; i < genes.length; i++) {
      genes[i] = (char) random(32,128);
    }
  }

//Tính toán mức độ thích ứng
  void fitness() {
     int score = 0;
     for (int i = 0; i < genes.length; i++) {
        if (genes[i] == target.charAt(i)) {
          score++;
        }//for
     }//fitness()

     fitness = float(score)/target.length();
  }

  //Trao đổi chéo
  DNA crossover(DNA partner) {
    DNA child = new DNA(genes.length);
    int midpoint = int(random(genes.length));
    for (int i = 0; i < genes.length; i++) {
      if (i > midpoint) child.genes[i] = genes[i];
      else  child.genes[i] = partner.genes[i];
    }
    return child;
  }

  //Đột biến
  void mutate(float mutationRate) {
    for (int i = 0; i < genes.length; i++) {
      if (random(1) < mutationRate) {
        genes[i] = (char) random(32,128);
      }//if
    }//for
  }//function

 //Chuyển sang kiểu String—Kiểu hình.
  String getPhrase() {
    return new String(genes);
  }
}
//END