Thuật giải di truyền và ứng dụng giải bài toán siêu trí tuệ Việt Nam

Heey yo 500 anh em, lâu lắm rồi mới quay trở lại viết blog. Cũng tại là dạo gần đây mình tập trung làm content bên mảng youtube nhiều quá, nên không sắp xếp đươc thời gian để viết bài bên đây. Nhưng cơ duyên là đợt rồi mình có đọc 1 cuốn sách liên quan đến trí tuệ nhân tạo, nói chung cuốn sách chủ yếu nói về việc trí tuệ nhân tạo sẽ thống trị loài người vân vân mây mây (mà mình cũng có review cuốn sách đó ở đây, anh chị em thấy hứng thú thì vào xem nhé). Sau khi đọc cuốn sách này thì mình lại có hứng để viết blog, thế là bài viết này ra đời =))
Ok, không dài dòng nữa, cùng mình tìm hiểu xem thuật giải di truyền là gì nhé, và cùng nhau code 1 chương trình giải 1 bài toán xuất hiện trong chương trình siêu trí tuệ Việt Nam mùa 2.
Các ứng dụng mình viết trong bài này đều đã được host lên ở đây, các bạn có thể vào xem nhé.

Thuật giải di truyền (Genetic Algorithm)

Để hiểu thuật giải di truyền là gì, thì chúng ta cần phải biết được thuyết tiến hóa của Darwin trước đã, vì thuật giải này được lấy ý tưởng từ thuyết tiến hóa này.
Theo Darwin, tiến hóa loài được hình thành do sự kết hợp của 3 yếu tố quan trọng: di truyền, đột biến và chọn lọc tự nhiên ( Cái này mình nhớ vì hồi xưa cấp 3 mình học chuyên sinh mà =)) ).
Lấy ví dụ loài bướm tiêu trong việc tiến hóa theo chọn lọc tự nhiên:
Ngày xửa ngày xưa, ở Anh có 1 đàn bướm tiêu, chúng là một đàn có nhiều con, và phần lớn chúng có màu đen và trắng.

Và để duy trì nòi giống, chúng phải giao phối với nhau, đây là quá trình di truyền. Và như chương trình sinh học cấp 3 đã dạy cho chúng ta biết, khi giao phối với nhau, thực chất là sự kết hợp của các cặp nhiễm sắc thể để tổng hợp tính trạng giữa bố và mẹ cho đứa con yêu dấu.

Nhưng, đây cũng là lúc những tác nhân môi trường khắc nhiệt của chúng ta phát huy tác động, và làm cho quá trình kết hợp này bị đột biến. Đột biến đã làm cho con con có những đặc tính không giống như bố mẹ mình.

Thế nên, trong đàn bướm trắng đen có xuất hiện những con bướm màu hường mộng mơ. Những con bướm màu hường này, thật là sặc sỡ, nó có thể dễ bị ăn thịt hơn, vì những con chim có thể phát hiện nó dễ dàng hơn. Thật tội nghiệp.

Nhưng, một ngày đẹp trời, có một dũng sĩ tên là Cuonglv1109 tới vùng đất loài bướm đang sống, và vẽ graffity. Dũng sĩ này cũng thuộc trường phái màu hường, do đó cả vùng đất bỗng chốc trở thành màu hường.

Và lúc này, những con bướm màu hường lại đạt được lợi thế. Những con bướm trắng và đen lại dễ bị tiêu diệt hơn vì quá dễ bị phát hiện. Và đây, Darwin gọi nó là chọn lọc tự nhiên.

Lúc này, trong quần thể con bướm số lượng bướm hường nhiều hơn, nên các con đời sau cũng dễ sinh ra có màu hường hơn.

Thế là, nhờ có dũng sĩ Cuonglv1109, đàn bướm từ trắng đen đã chuyển qua màu hường.

Và đó là thuyết tiến hóa của Darwin, vậy thì nó liên quan gì tới thuật giải di truyền. Ồ, hóa ra các nhà khoa học đã áp dụng thuyết tiến hóa để tạo nên thuật giải di truyền. Ví dụ, chúng ta đang muốn giải quyết một bài toán đơn giản là mò password. Password này gồm có 11 kí tự, chỉ cần đoán đúng 11 kí tự không cần theo thứ tự là sẽ giải được password. Ví dụ password cần giải là cuonglv1109.

Thuật giải di truyền sẽ tạo ra 1 quần thể gồm các password ngẫu nhiên có 11 kí tự. Ví dụ ở đây, ta có quần thể gồm 6 cá thể.

Những cá thể gần giống với password gốc nhất, là những cá thể có cơ hội sống cao hơn qua thế hệ sau, những cá thể khác với password nhất thì sẽ bị chết. Đây chính là chọn lọc tự nhiên.

Những cá thể sống sót sẽ giao phối với nhau, và sản sinh ra thế hệ con. Đây là quá trình di truyền.

Một vài cá thế con bị đột biến làm thay đổi 1 kí tự.

Thế hệ thứ 2 theo thuyết tiến hóa đã có độ chính xác cao hơn so với thế hệ đầu tiên. Quá trình này lặp đi lặp lại qua các thế hệ sẽ dẫn tới kết quả tìm ra được password.

Và đó chính là thuật giải di truyền.
Trong thuật giải di truyền có nhiều yếu tố cần phải xem xét. Trong đó có 2 yếu tố mà mình thấy quan trọng đó là:
Độ đột biến (mutation rate): tức là độ đột biến trong quần thể của bạn. Đây thực chất cũng là hyperparameter cần phải tối ưu.
Độ chọn lọc (Selection Rate): tức là mức độ chọn lọc cá thể, bao nhiêu cá thể phải chết đi.
Mình cũng đã viết 1 cái demo cho thuật giải này dựa trên câu chuyện đàn bướm ở trên.

Ý tưởng đơn giản là chúng ta có 1 đàn bướm ngẫu nhiên gồm nhiều con bướm với màu sắc khác nhau. Sau đó ta chọn màu cho môi trường chúng sống, qua các thế hệ thì những con bướm này sẽ chuyển thành màu gần gần giống với màu của môi trường. Cái demo này thì mình sẽ không giải thích code nha, tại nó sẽ tốn khá nhiều thời gian, mình sẽ dành thời gian để nói về ứng dụng giải bài toán siêu trí tuệ Việt Nam ở dưới. Code của demo này mình cũng đã push lên github ở đây, các bạn có thể clone về chạy thử
Vậy thì thuật giải di truyền này áp dụng được vào việc gì?
Như các bạn để ý, thuật giải di truyền này qua mỗi thế hệ, thì các cá thế ở thế hệ sau có độ chính xác cao hơn các cá thể ở thế hệ trước. Điều này sẽ được áp dụng vào việc tìm ra các hyperparameter trong máy học(Nếu như các bạn không hiểu hyperparameter, máy học là gì, thì có thể quay lại series nhận dạng hình ảnh bằng máy học do mình đã viết để đọc nhé). Vậy nên, người ta sẽ áp dụng thuật giải di truyền này vào máy học để máy có thể học đươc hiệu quả.
Nhưng hôm nay, mình sẽ áp dụng thuật giải di truyền này vào để giải một bài toán vừa mới được chiếu trên chương trình siêu trí tuệ Việt Nam mùa 2.

Ứng dụng giải bài toán siêu trí tuệ Việt Nam

Trong chương trình siêu trí tuệ Việt Nam mùa 2, mình có thấy 1 bài toán về mã đi tuần. Trong đó, thí sinh được cho 1 bàn cờ vua 8*8, và 2 ô bắt đầu và kết thúc.

Nhiệm vụ của tuyển thủ là phải giải bài mã đi tuần và bài toán điền số. Với bài toán mã đi tuần, các bạn có thể giải bằng back-tracking (mình đã viết ở trong bài này). Mà thực ra mình nói vậy thôi, chứ sau khi mình thử code thì thấy dùng back-tracking chạy lâu lắm các bạn ạ =(( .
Ở đây, chúng ta sẽ giải quyết bài toán thứ 2. Đó là phải điền số vào các ô trong bàn cờ sao cho: Tổng mỗi hàng, tổng mỗi cột phải bằng với 1 số cho trước bất kì (trong chương trình, con số này được ca sĩ Tóc Tiên chọn là 531)

Để giải quyết bài toán này, ý tưởng mình đưa ra đó là chúng ta sẽ tạo ra 1 quần thể những bàn cờ, với những con số bất kì được đặt trong bàn cờ đó. Ở đây mình tạo ra 1 quần thể có 1000 bàn cờ.

this.result = 531;
this.insta = 1000;        
this.mazes = [this.insta];
for(let i = 0; i< this.insta; i++) {
    this.mazes[i] = new Maze(result);
}

Sau đó chúng ta sẽ tính độ fit của mỗi cá thể so với kết quả đúng. Cách tính thì mình sẽ tính bằng cách tính tổng sự sai số của mỗi hàng, mỗi cột của bàn cờ. Cá thể có độ sai số càng cao, thì đột fit càng thấp. Tức là vào thế hệ sau sẽ càng dễ bị chết đi.

calculateScore(result){
        this.score = 0; // fitness score
        for (let i = 0; i < 8; i++) {
            let total = 0;
            for (let j = 0; j < 8; j++) {
               total += this.map[i][j];
            }
            this.score += Math.abs(result- total);
        }
        for (let i = 0; i < 8; i++) {
            let total = 0;
            for (let j = 0; j < 8; j++) {
                total += this.map[j][i];
            }
            this.score += Math.abs(result- total);
        }
    }

Độ chọn lọc mình đưa ra là 80% số lượng cá thể. Tức là sau mỗi thế hệ, sẽ có 800/1000 cá thể bị loại bỏ.

this.deathRate = 0.8*this.insta;
selection(){
        for(let i = 0 ; i < this.insta; i++){
            this.mazes[i].calculateScore(this.result);
        }
        this.mazes.sort((a, b) => a.score - b.score); //sort by fitness
        for(let i = this.mazes.length - this.deathRate; i < this.mazes.length; i++){ > 
            this.mazes[i].score = -1;
        }
    } <

Sau khi loại bỏ các cá thể, mình cho 200 cá thể còn lại lai tạo với nhau. Lai tạo ở đây là mình lấy giá trị trung bình của cha và mẹ cho đứa con

crossOverAndMutation(far, mom){
        for (let i = 0; i < 8; i++) {
            for (let j = 0; j < 8; j++) {
                this.map[i][j] =  Math.floor((far.map[i][j] + mom.map[i][j])/2);                
            }
        }
    }

Cuối cùng là quá trình đột biến. Ở đây mình cho đột biến bằng cách: Nếu giá trị của cha và mẹ khác nhau (tức là chưa tối ưu) thì mình sẽ chắc chắn cho đột biến tại ô đó +-2. Còn nếu giá trị của cha và mẹ giống nhau ( có sự tối ưu) thì mình cho tỉ lệ đột biến tại ô đó là 1% (với giá trị đột biển +- 1).

crossOverAndMutation(far, mom){
        for (let i = 0; i < 8; i++) {
            for (let j = 0; j < 8; j++) {
                this.map[i][j] =  Math.floor((far.map[i][j] + mom.map[i][j])/2);
                if(far.map[i][j]!=mom.map[i][j]){
                    let randNum = Math.floor(Math.random() * 4) ;
                    if(randNum%2==0){
                        this.map[i][j] +=2;
                    } else {
                        this.map[i][j] -= 2;
                    }
                } else {
                    let randNum = Math.floor(Math.random() * 100)
                    if(randNum===51){
                        this.map[i][j] +=1;
                    } else if(randNum===52){
                        this.map[i][j] -=1;
                    }
                }
                if(this.map[i][j]<=0){
                    this.map[i][j] =  1;
                }

            }
        }
    }

Quá trình chọn lọc tự nhiên, di truyền và đột biến cứ tiếp tục lặp đi lặp lại. Kết quả là chúng ta sẽ có được thế hệ sau, có bàn cờ giống với bàn cờ cần tìm nhất. Và khi xuất hiện một bàn cờ cần tìm (tức lúc này sai số = 0), thì chúng ta sẽ dừng lại.

while(true){
if(geneticAlgorithm.mazes[0].score == 0) {
                return;
            }
            geneticAlgorithm.selection();            
            geneticAlgorithm.crossOverAndMutation();
}

Tất cả code của ứng dụng này mình push hết lên đây rồi. Các bạn có thể lấy về chạy thử nhé.

Read More