Tìm hiểu thuật toán SHA-256

Bài này chúng ta sẽ tìm hiểu về thuật toán hash, mà cụ thể là thuật toán Hash SHA-256.

Hash function (hàm băm) là gì?

Hash function (hàm băm) hiểu đơn giản là một hàm có khả năng băm nát data nếu chúng ta đưa data vào cho nó :)). 

Đặc điểm của hash function đó là với cùng 1 đầu vào, thì nó sẽ băm ra đúng 1 kết quả duy nhất.

Ví dụ : Đầu vào của chúng ta là "cuonglv" thì hàm băm sẽ băm ra thành kết quả: "431ebbdd7efdcedc28b3ace1ec7b19302a834c9085f943d2af3036361b155e7d"

Hash function có một đặc điểm đó nữa là từ output sau khi bị băm xong, thì ko có cách nào truy ngược lại input được hết. 

Ví dụ : từ chuỗi "431ebbdd7efdcedc28b3ace1ec7b19302a834c9085f943d2af3036361b155e7d" không có cách nào bạn truy ngược được về input ban đầu là "cuonglv" được cả.

Theo mình thì chủ yếu người đọc blog của mình đều là dân lập trình cả, nên giới thiệu hàm băm tới đây mình nghĩ có lẽ vậy là đã đủ rồi =)) Vì chắc chắn anh em lập trình ít nhiều cũng xài hash 1 lần nào đó rồi.

Vậy nên phần tiếp theo của bài này sẽ nói sâu về 1 hàm băm có tên là SHA-256. 

SHA-256 là gì?

Đơn giản SHA-256 cũng là 1 hash function, vậy nên nó cũng chứa trong nó 2 đặc tính của hash fuction ở trên. SHA-256 này nó được cục an ninh quốc gia Mỹ tạo ra, nên độ đẳng cấp của nó còn cao hơn, đó là nó có thêm 1 đặc tính nữa: việc tìm ra chuỗi input thứ 2 để cho ra cùng 1 output là điều bất khả thi.

Ví dụ: "cuonglv" khi cho vào SHA-256 sẽ cho ra kết quả : "431ebbdd7efdcedc28b3ace1ec7b19302a834c9085f943d2af3036361b155e7d". Và để tìm được 1 cái input nào đó khác "cuonglv" mà cũng cho ra được "431ebbdd7efdcedc28b3ace1ec7b19302a834c9085f943d2af3036361b155e7d" là điều bất khả thi.

Tất nhiên trên lý thuyết là được, nhưng thực tế chưa ai làm được thôi. =)) Tại sao lý thuyết lại có việc 2 input ra cùng 1 output được. Thì đơn giản là vầy, cái hàm SHA-256 này, dù bạn có đưa input ngắn tới đâu (1 kí tự "a") hay bạn có đưa input dài thòng lòng như nội dung của 1 cuốn sách, thì hàm băm này cũng cho ra 1 kết quả dài 64 kí tự. Suy ra là chắc chắn sẽ có trường hợp 2 input cho ra cùng 1 kết quả giống nhau rồi. Nhưng mà để tìm được 2 chuỗi này gần như là bất khả thi.

Ok, luyên thuyên đủ rồi. Bây giờ chúng ta sẽ đi vào tìm hiểu thuật giải của mã băm này, xem đội ngũ của cục an ninh quốc gia Mỹ nghĩ ra được 1 thuật toán như nào, có quá xịn sò hay ko.

Thuật toán SHA-256

SHA-256 là một hàm băm, do đó mà nó phải có những thứ có thể làm rối loạn được data ban đầu, và từ đó không cho phép chúng ta truy ngược được input. SHA-256 làm rối được mọi thứ lên nhờ có những constants và function mà chúng ta sẽ xem sau đây.

Constants

K constant : bao gồm 64 giá trị được tạo nên bằng cách sau.

Bắt đầu từ số nguyên tố đầu tiên là 2.

Tính căn bậc 3 của số nguyên tố này, ta được 1.259921...

Bỏ phần nguyên, lấy phần thập phân lại ta được 0.259921...

Sau đó nhân kết quả với 2 mũ 32 ta được : 1116352408.8404646

Cuối cùng ta bỏ phần thập phân đi ta được: 1116352408

Và đây cũng chính là giá trị đầu tiên trong 64 giá trị K của thuật toán SHA-256. Những giá trị tiếp theo, chúng ta lại tiếp tục tính với số nguyên tố tiếp theo là số 3.

Bạn có thể bật f12 lên để chạy đoạn code này :

function isPrime(num) {
  for(var i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}
var k = [];
var i = 0;
for(var j=2; i < 64; j++) {
   if(isPrime(j)) {
      k[i] = Math.floor(Math.cbrt(j)%1*(Math.pow(2,32)));
      i++;
   }
}
k

chúng ta sẽ có được kết quả là 64 giá trị K của SHA-256.

[1116352408, 1899447441, 3049323471, 3921009573, 961987163, 1508970993, 2453635748, 2870763221, 3624381080, 310598401, 607225278, 1426881987, 1925078388, 2162078206, 2614888103, 3248222580, 3835390401, 4022224774, 264347078, 604807628, 770255983, 1249150122, 1555081692, 1996064986, 2554220882, 2821834349, 2952996808, 3210313671, 3336571891, 3584528711, 113926993, 338241895, 666307205, 773529912, 1294757372, 1396182291, 1695183700, 1986661051, 2177026350, 2456956037, 2730485921, 2820302411, 3259730800, 3345764771, 3516065817, 3600352804, 4094571909, 275423344, 430227734, 506948616, 659060556, 883997877, 958139571, 1322822218, 1537002063, 1747873779, 1955562222, 2024104815, 2227730452, 2361852424, 2428436474, 2756734187, 3204031479, 3329325298]

Để dễ nhìn thì mình thấy người ta chủ yếu chuyển nó về hex, và do đó mình cũng học theo người ta đưa nó về dạng hex =))

['0x428a2f98', '0x71374491', '0xb5c0fbcf', '0xe9b5dba5', '0x3956c25b', '0x59f111f1', '0x923f82a4', '0xab1c5ed5', '0xd807aa98', '0x12835b01', '0x243185be', '0x550c7dc3', '0x72be5d74', '0x80deb1fe', '0x9bdc06a7', '0xc19bf174', '0xe49b69c1', '0xefbe4786', '0xfc19dc6', '0x240ca1cc', '0x2de92c6f', '0x4a7484aa', '0x5cb0a9dc', '0x76f988da', '0x983e5152', '0xa831c66d', '0xb00327c8', '0xbf597fc7', '0xc6e00bf3', '0xd5a79147', '0x6ca6351', '0x14292967', '0x27b70a85', '0x2e1b2138', '0x4d2c6dfc', '0x53380d13', '0x650a7354', '0x766a0abb', '0x81c2c92e', '0x92722c85', '0xa2bfe8a1', '0xa81a664b', '0xc24b8b70', '0xc76c51a3', '0xd192e819', '0xd6990624', '0xf40e3585', '0x106aa070', '0x19a4c116', '0x1e376c08', '0x2748774c', '0x34b0bcb5', '0x391c0cb3', '0x4ed8aa4a', '0x5b9cca4f', '0x682e6ff3', '0x748f82ee', '0x78a5636f', '0x84c87814', '0x8cc70208', '0x90befffa', '0xa4506ceb', '0xbef9a3f7', '0xc67178f2']

Initial Hash : bao gồm 8 giá trị được khởi tạo như sau

Tương tự như với K constant, Initial Hash cũng được khởi tạo từ số nguyên tố. Nhưng thay vì dùng căn bậc 3 của số nguyên tố, thì chúng ta sẽ tính căn bậc 2. Còn ở những bước sau thì làm y hệt như cách tạo K constant.

Ví dụ: Với số nguyên tố đầu tiên là 2. Thì chúng ta sẽ có Initial Hash đầu tiên là : 1779033703

Tương tự như vậy, chúng ta có thể tính được 7 giá trị Initial Hash còn lại. Bạn có thể chạy đoạn code sau:

function isPrime(num) {
  for(var i = 2; i < num; i++)
    if(num % i === 0) return false;
  return num > 1;
}
var k = [];
var i = 0;
for(var j=2; i < 8; j++) {
   if(isPrime(j)) {
      k[i] = Math.floor(Math.sqrt(j)%1*(Math.pow(2,32)));
      i++;
   }
}
k

chúng ta sẽ có được kết quả là 8 giá trị Initial Hash:

[1779033703, 3144134277, 1013904242, 2773480762, 1359893119, 2600822924, 528734635, 1541459225]

Mình sẽ chuyển nó về dạng hex là:

['0x6a09e667', '0xbb67ae85', '0x3c6ef372', '0xa54ff53a', '0x510e527f', '0x9b05688c', '0x1f83d9ab', '0x5be0cd19']

Operations:

Tiếp theo chúng ta sẽ ôn lại một vài operation cơ bản đã được học ở trường.

Phép dịch phải (Shift right)

Phép dịch phải đơn giản là bạn dịch chuyển dữ liệu ở dạng binary (dạng thập phân - cái kiểu mà 0101 ấy) qua bên phải. 

Ví dụ: ta có chuỗi "00000000000000000000000000000101". Bây giờ dịch phải 1 đơn vị sẽ được "00000000000000000000000000000010".

nếu ta dịch thêm 2 đơn vị nữa sẽ được: "00000000000000000000000000000000"

Trong javascript thì bạn có thể dùng ">>>" để thực hiện phép dịch phải:

Phép đảo phải (Rotate right)

Khác với phép dịch phải, chúng ta sẽ bỏ đi những giá trị bị dịch đi, thì ở phép đảo phải, những giá trị bị dịch chuyển sẽ quay ngược trở lại đầu chuỗi

Ví dụ: ta có chuỗi "00000000000000000000000000000101". Bây giờ dịch phải 1 đơn vị sẽ được "10000000000000000000000000000010".

nếu ta dịch thêm 2 đơn vị nữa sẽ được: "10100000000000000000000000000000"

Với 32 bit, trong javascript bạn có thể thực hiện đảo phải bằng đoạn code dưới đây:

function rightRotate(value, amount) {
  return (value>>>amount) | (value<<(32 - amount));
}

Phép XOR:

Phép XOR cũng khá đơn giản, 2 giá trị mà giống nhau thì XOR trả về 0, khác nhau thì trả về 1

Trong javascript bạn có thể thực hiện phép XOR bằng "^"

Functions:

Trong SHA-256 cũng có chứa một vài hàm mà các bạn cũng cần phải điểm qua:

Hàm Gamma 0:

Giả sử cho 1 biến x (ví dụ là 00000000000000000000010010100101, thì hàm gamma 0 sẽ làm những việc sau: 

Đầu tiên là tạo ra x1 bằng cách rotate right (đảo phải) x 7 đơn vị

Tiếp tục tạo ra x2 bằng cách rotate right x 18 đơn vị

Tạo ra x3 bằng cách Shift right (dịch phải) x 3 đơn vị

Cuối cùng là XOR x1, x2 và x3 lại với nhau:

Hàm Gamma 1:

hàm này y hệt như hàm Gamma 0. Chỉ có điều hàm nay đổi đơn vị dịch chuyển.

Ví dụ cho x 00000000000000000000010010100101

Tạo ra x1 bằng cách rotate right 17 đơn vị

Tạo ra x2 bằng cách rotate right 19 đơn vị

Tạo ra x3 bằng cách shift right 10 đơn vị

Cuối cùng là XOR x1, x2 và x3 lại với nhau

Hàm Sigma 0:

Cũng na ná 2 hàm trên, chỉ có điều 3 bước đều là rotate chứ không có xài shift.

Ví dụ cho x 00000000000000000000010010100101

Tạo ra x1 bằng cách rotate right 2 đơn vị

Tạo ra x2 bằng cách rotate right 13đơn vị

Tạo ra x3 bằng cách rotate right 22 đơn vị

Cuối cùng là XOR x1, x2 và x3 lại với nhau

Hàm Sigma 1:

Tương tự như sigma 0, nhưng đổi đơn vị rotate

Ví dụ cho x 00000000000000000000010010100101

Tạo ra x1 bằng cách rotate right 6 đơn vị

Tạo ra x2 bằng cách rotate right 11 đơn vị

Tạo ra x3 bằng cách rotate right 25 đơn vị

Cuối cùng là XOR x1, x2 và x3 lại với nhau

Hàm choice

function Choice(x, y, z) {
        return ((x & y) ^ ((~x) & z));
}

Hàm này thì nó sẽ nhận vào 3 đối số x, y, z. Logic của nó đơn giản như sau:

Nếu x = 1 thì output sẽ là y.

nếu x = 0 thì output sẽ là z

Ví dụ hàm choice với dãy nhị phân x =  01010101, y = 11111111, z = 00000000. Thì sẽ ra kết quả: 01010101

Hàm Majority

function Majority(x, y, z) {
      return ((x & y) ^ (x & z) ^ (y & z));
}

Nghe tên hàm là biết luôn rồi ha. Hàm này nhận 3 đối số x, y, z. Kết quả sẽ là số chiếm phần đa số.

Ví dụ: x =1 , y =1 , z =0 , thì kết quả Majority = 1. Vì số 1 xuất hiện 2 lần, còn số 0 chỉ xuất hiện 1 lần thôi.

Tương tự, x = 1, y =0, z =0 thì Majority = 0. Vì số 0 xuất hiện nhiều lần hơn số 1.

Với x = 10101010, y = 11111111, z = 00000000. Kết quả Majority sẽ là 10101010.

Vậy là chúng ta đã điểm qua hết những Constant và Function được sử dụng trong SHA-256. Bây h sẽ là lúc chúng ta bước vào tìm hiểu xem, thuật toán này chạy như thế nào. 

Quỳ trình băm

Khởi tạo chuỗi binary

Ví dụ chuỗi chúng ta cần băm là "cuonglv". Đầu tiên chúng ta cần phải đưa nó về dạng binary trước. Thì cách để chuyển từ text mà sang binary thì cứ bám vào ascii code thôi. Theo ascii thì "cuonglv" sẽ được chuyển thành : "01100011011101010110111101101110011001110110110001110110"

Vì chuỗi "cuonglv" có độ dài 7 kí tự, nên khi chuyển qua chuổi binary thì sẽ đài 7*8 = 56 bit. Việc tiếp theo chúng ta cần làm là thêm 1 bit "1" vào sau chuỗi trên:

Chuỗi của chúng ta hiện tại là 57 bit rồi. Bây giờ ta sẽ tìm 1 số X sao cho số X này lớn hơn 57 (57 ở đây là số bit của chuỗi chúng ta vừa tạo), và 57 + X + 64 sẽ chia hết cho 512. Và trong trường hợp này,  X chúng ta tìm được là 391. Vì 391 > 57, và 57 + 391 + 64 = 512 chia hết cho 512.

Bước tiếp theo là chũng ta thêm vào chuỗi binary X giá trị 0. Trong trường hợp này chúng ta sẽ thêm 391 giá trị 0 và được chuỗi sau.

Chuỗi này cần thêm 64 bit nữa mới hoàn thành. 64 bit cuối cùng này được tạo ra bằng cánh lấy độ dài bit của chuỗi "cuonglv" và chuyển nó về dạng bit. 

Ví dụ: "cuonglv" có độ dài bit là 56. 56 chuyển về binary sẽ là "111000". Chúng ta sẽ thêm 58 số 0 vào trước "111000" cho đủ 64 kí tự. Ta được 64 kí tự cần tìm là : 

Ta nối 64 kí tự này vào chuỗi ở trên ta được chuỗi cuối cùng là : 

Trong trường hợp này, chuỗi dài tổng cộng 512 bit.

Xử lý block

Sau khi tạo được chuổi binary, chúng ta sẽ chia nó ra thành các block, mỗi block này dài 512 bit. Trong trường hợp này, vì độ dài chuỗi của chúng ta chỉ có 512 bit, nên chúng ta chỉ có 1 block duy nhất.

Bắt đầu với block số 1 (cũng là block duy nhất của chúng ta), ta sẽ chia 512 bit thành 16 chuỗi, mỗi chuỗi dài 32 bit. Ta được 16 chuỗi sau:

W1 : 01100011011101010110111101101110
W2 : 01100111011011000111011010000000
W3 : 00000000000000000000000000000000
W4 : 00000000000000000000000000000000
W5 : 00000000000000000000000000000000
W6 : 00000000000000000000000000000000
W7 : 00000000000000000000000000000000
W8 : 00000000000000000000000000000000
W9 : 00000000000000000000000000000000
W10 : 00000000000000000000000000000000
W11 : 00000000000000000000000000000000
W12 : 00000000000000000000000000000000
W13 : 00000000000000000000000000000000
W14 : 00000000000000000000000000000000
W15 : 00000000000000000000000000000000
W16 : 00000000000000000000000000111000

Việc tiếp theo của chúng ta là tạo ra thêm 48 chuỗi nữa. Ta bắt đầu với chuỗi thứ 17. Công thức để tạo ra chuỗi mới như sau:

W[n] = W[n-16] + gamma0(W[n-15]) + W[n-7] + gamma1(W[n-2])

Ví dụ ta tìm chuỗi thứ 17, lúc này n = 17. Ta có W[17] = W[1] + gamma0(W[2]) + W[10] + gamma1(W[14]). Lần lượt ta có: 

W[1] = 01100011011101010110111101101110

gamma0(W[2]) = gamma0(01100111011011000111011010000000) = 00010001100000110100111111100110

W[10] = 00000000000000000000000000000000

gamma1(W[14]) = gamma1(00000000000000000000000000000000) = 00000000000000000000000000000000

Cuối cùng ta cộng 4 giá trị này lại sẽ được W[17] = 01110100111110001011111101010100 . Trong trường hợp kết quả cộng lại có số bit dài hơn 32 bit, thì chúng ta bỏ đi bit thừa bên trái để thành 32 bit.

Tính tương tự cho những chuỗi tiếp theo ta sẽ có được tổng cộng 64 chuỗi.

Compression

Chúng ta đã tính ra ở lúc đầu bài được 8 initial hash rồi. Mình sẽ đưa nó về mã nhị phân là :

h1: 01101010000010011110011001100111
h2: 10111011011001111010111010000101
h3: 00111100011011101111001101110010
h4: 10100101010011111111010100111010
h5: 01010001000011100101001001111111
h6: 10011011000001010110100010001100
h7: 00011111100000111101100110101011
h8: 01011011111000001100110100011001

Bây giờ chúng ta sẽ dựa vào từng chuỗi W trong 64 chuỗi ở trên để phá nát 8 cái Initial Hash này.

Bắt đầu với W1. Ta sẽ đi tính T1 theo công thức :

T1 = Sigma1(H5) + Choice(H5 + H6 + H7) + H8 + K1 + W1

Ta có:

Sigma1(H5) = 00110101100001110010011100101011

Choice(H5 + H6 + H7) = 00011111100001011100100110001100

H8 = 01011011111000001100110100011001

K1 = 01000010100010100010111110011000

W1 = 01100011011101010110111101101110

T1 = 01010110111011010101110011010110 . 

Tiếp tục ta tính T2 theo công thức:

T2 = Sigma0(H1) + Majority(H1, H2, H3);

Ta có :

Sigma0(H1) = 11001110001000001011010001111110

Majority(H1,H2,H3) = 00111010011011111110011001100111

T2 = 00001000100100001001101011100101

Tiếp theo, ta sẽ bỏ đi giá trị H8. Rồi dịch chuyển các giá trị H đi 1 đơn vị. Ví dụ, h2 sẽ lấy giá trị h1, h3 lấy giá trị của h2...ta sẽ có giá trị hash mới :

h1: 
h2: 01101010000010011110011001100111
h3: 10111011011001111010111010000101
h4: 00111100011011101111001101110010
h5: 10100101010011111111010100111010
h6: 01010001000011100101001001111111
h7: 10011011000001010110100010001100
h8: 00011111100000111101100110101011

H1 lúc này sẽ bằng T1 + T2. Ta có bảng h1 = 01011111011111011111011110111011. h5 = h5 + T1. h5 lúc này sẽ = 11111100001111010101001000010000. Bảng hash sẽ thành:

h1: 01011111011111011111011110111011
h2: 01101010000010011110011001100111
h3: 10111011011001111010111010000101
h4: 00111100011011101111001101110010
h5: 11111100001111010101001000010000
h6: 01010001000011100101001001111111
h7: 10011011000001010110100010001100
h8: 00011111100000111101100110101011

Và quá trình tính T1, T2 và cập nhật lại bảng Hash sẽ được lặp thêm 63 lần nữa dựa vào K và W. Sau mỗi lần lặp bảng Hash lại bị thay đổi. Cuối cùng ta sẽ có bẳng hash như sau:

h1: 01101010000010011110011001100111
h2: 10111011011001111010111010000101
h3: 00111100011011101111001101110010
h4: 10100101010011111111010100111010
h5: 01010001000011100101001001111111
h6: 10011011000001010110100010001100
h7: 00011111100000111101100110101011
h8: 01011011111000001100110100011001

Bây giờ ta sẽ lẩy h1 của bảng hash này cộng với h1 của initial hash ban đầu với nhau để được giá trị h1 mới là : 01101010000010011110011001100111 + 01101010000010011110011001100111 = 01000011000111101011101111011101.

Tính tương tự cho các h còn lại, ta được 1 bảng hash mới là:

h1: 01000011000111101011101111011101
h2: 01111110111111011100111011011100
h3: 00101000101100111010110011100001
h4: 11101100011110110001100100110000
h5: 00101010100000110100110010010000
h6: 10000101111110010100001111010010
h7: 10101111001100000011011000110110
h8: 00011011000101010101111001111101

Vì chúng ta chỉ có 1 block duy nhất thôi. nên tiến trình tới đây là dừng. Nếu như còn có thêm các block khác nữa, thì cái bảng hash mới này, sẽ là initial hash cho block thứ 2 tính toán. Và kết quả hash của block thứ 2 sẽ là initial hash của block thứ 3...và đến cuối cùng sẽ có 1 bảng hash cuối cùng được tạo ra.

Từ bảng hash này, chúng ta sẽ chuyển nó về dạng hex:

h1 : 431ebbdd
h2 : 7efdcedc
h3 : 28b3ace1
h4 : ec7b1930
h5 : 2a834c90
h6 : 85f943d2
h7 : af303636
h8 : 1b155e7d

Kết quả của hàm SHA-256 là chuỗi kí tự được nối từ 8 mã hash trên: 431ebbdd7efdcedc28b3ace1ec7b19302a834c9085f943d2af3036361b155e7d

Ok, và đó là tất cả những gì mà thuật toán SHA-256 làm. Thực sự là phức tạp đấy. Mình ngồi viết bài này thôi mà đã thấy mù cả đầu rồi, cũng mong các bạn qua bài này có thể hiểu được cơ chế tính toán băm của SHA-256 và hiểu được tại sao nó lại bảo mật đến vậy.

Read More

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