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

Chương trình để tạo ra một quần thể

Bước 1: Khởi tạo quần thể

Nếu chúng ta tạo ra một quần thể, chúng ta cần một cấu trúc dữ liệu để lưu trữ một danh sách các thành viên của quần thể đó. Trong hầu hết các trường hợp (ví dụ như trường hợp con khỉ gõ bàn phím), số lượng phần tử trong một quần thể là cố định, và do đó chúng ta sử dụng một mảng. (Sau này chúng ta sẽ thấy những ví dụ liên quan đến quần thể ngày càng tăng/thu hẹp và khi đó chúng ta sẽ sử dụng một ArrayList). Nhưng một mảng của cái gì? Chúng ta cần đối tượng để chứa thông tin di truyền cho một thành viên của quần thể. Hãy gọi nó là DNA.

class DNA {}

Quần thể sẽ là một mảng của các thực thể kiểu DNA.

DNA[] population = new DNA[100];

Nhưng class DNA sẽ có gì trong đó? Đối với một con khỉ gõ bàn phím, DNA của nó là một cụm từ ngẫu nhiên mà nó gõ được, một chuỗi các ký tự.

class DNA {
String phrase;
}

Mặc dù khai báo này phù hợp trong ví dụ cụ thể này, ta sẽ không sử dụng một kiểu String cho mã di truyền. Thay vào đó, ta sẽ sử dụng một mảng các kí tự.

class DNA {
//Mỗi gen là một phần tử của mảng. Chúng ta có 18 gen vì “to be or not to be” có 18 kí tự.
char[] genes = new char[18];
}

Bằng việc sử dụng một mảng, chúng ta có thể mở rộng chương trình ta viết cho các ví dụ khác. Ví dụ, DNA của một sinh vật trong một hệ thống vật lý có thể là một mảng của các PVectors – hoặc là một mảng số nguyên (màu RGB) cho một ảnh. Chúng ta có thể mô tả được một tập hợp các thuộc tính bất kì nào đó với một mảng, và mặc dù một String thì thuận tiện cho ví dụ rất cụ thể này, một array sẽ là nền tảng tốt hơn cho các ví dụ về sự tiến hóa trong tương lai.

class DNA {
char[] genes = new char[18];
DNA() {
for (int i = 0; i < genes.length; i++) {

//Chọn một kí tự ASCII ngẫu nhiên từ 32 đến 128
genes[i] = (char) random(32,128);
  }//for
 }//DNA()
}//class DNA

Giờ thì chúng ta có hàm tạo, chúng ta có thể quay lại hàm setup() và khởi tạo cho mỗi thực thể DNA trong array quần thể.

DNA[] population = new DNA[100];
void setup() {
  for (int i = 0; i < population.length; i++) {
    //Initializing each member of the population
    population[i] = new DNA();
  }
}

Class DNA của chúng ta hoàn toàn chưa hoàn chỉnh. Chúng ta cần cộng thêm các hàm khác để nó có thể thực hiện tất cả các nhiệm vụ trong giải thuật lập trình, những hàm này chúng ta sẽ thêm vào ở bước 2 và 3.

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() 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

About Author

Chia sẻ bài viết

Leave a Comment

Your email address will not be published. Required fields are marked *