Đặt vấn đề Trong cuộc sống nảy sinh rất nhiều bài toán chứng thực: chứng thực chữ ký điện tử, chứng thực tài liệu. Bài toán có thể được viết như sau: - Cho trước một đối tượng A. - _ Cần chứng thực một đối tượng X có phải là A hay không? Nếu X đúng là A thì hệ thống trả lời là THẬT, ngược lại hệ thống trả lời là GIA (phân biệt THẬT / GIẢ). Đồng thời tìm ra phương pháp để rút ngắn thời gian chứng thực (phát hiện GIA nhanh nhất).
Và bài toán cơ bản của bài toán chứng thực trên là chứng thực vector có chiều dai L. Cách giải quyết bài toán Thực chất, vấn đề cơ bản của bài toán là tìm ra một hoán vị tối ưu, chứng thực vector X có phải là vector A cho trước hay không? Hoán ưu là một thứ tự các vị trí có khả năng bị “giả” nhất. Hoán vi tối ưu là kết quả của việc học từ thực tế. Giả sử có một bộ T gồm các vector “giả” thường xuất hiện.
Từ tập T này, ta sẽ tìm xem vị trí nào thường hay bị “giả” nhất và đưa nó lên các vị trí đầu. Theo cách đó, khi chứng thực X, không duyệt theo thứ tự thông thường mà duyệt theo thứ tự của hoán vị tối ưu đó, để có thể tìm ra vị trí “giả nhanh nhất”, tối ưu được tốc độ tìm kiếm. Ung dụng của bài toán chứng thực vector Nhận dạng vân tay Để chứng thực các cá nhân, nhận dạng vân tay là một phương pháp được sử dụng nhiều hơn các phương pháp sinh trắc học khác. Lý do chính đó là vì các dấu vân tay là duy nhất và không bị biến đồi theo thời gian.
Xác suất hai cá nhân - thậm chí ngay cả anh em (hoặc chị em) sinh đôi cùng trứng - có cùng một bộ dấu vân tay là 1 trên 64 tỉ. Người ta có thé làm phẫu thuật thay da ngón tay, nhưng chỉ sau một thời gian dấu vân tay lại được hồi phục như ban đầu. Kỹ thuật nhận dạng vân tay bảo đảm độ tin cậy và tính én định cao; do đó phương pháp này được sử dụng nhiều trong các ứng dụng ở nhiều lĩnh vực khác nhau như thương mại điện tử, hệ thống mạng, bản quyền phần mềm và các thiết bị đầu cuối (như chuột và bàn phím). Ngoài ra, kỹ thuật này còn được ứng dụng trong các cỗ máy rút tiền tự động (ATM), các khóa cửa an toàn và các thẻ thông minh.
Nhìn chung, bài toán nhận dạng vân tay được giải quyết bằng phương pháp chứng thực vector như sau: Trước hết nhận vào không gian ảnh vân tay, sau đó biến đổi các ảnh vân tay về đạng vector. Và tiến hành so sánh nhận đạng. Các phương pháp giái quyết bài toán nhận dạng — chứng thực Có các nhóm phương pháp chính để giải quyết bài toán nhận dạng — chứng thực, đó là gom cụm, vét cạn, và sử dụng cây nhận dạng. Gom cụm Gom cụm được xem là một vấn đề quan trọng nhất trong lĩnh vực học không giám sát.
Vì thế, phương pháp này đề cập đến việc tim ra một cầu trúc trong một tap hợp các dữ liệu chưa được gán nhãn. Ta có thể định nghĩa gom cụm như sau: gom cụm là một quá trình tổ chức các đối tượng vào các nhóm, mà các đối tượng trong từng nhóm này có điểm tương đồng nào đó. Vì thế, một cụm là một tập hợp các đối tượng có điểm tương tự nhau và không giống các đối tượng thuộc nhóm khác. Ưu điểm của việc giải quyết bài toán nhận dạng — chứng thực bằng phương pháp gom cụm là xử lý nhanh, do so sánh đối tượng cần chứng thực- nhận dang với một cụm các đối tượng có những điểm tương đồng.
Tuy nhiên, khuyết điểm của phương pháp này là độ chính xác không cao, đo có thể trong quá trình tạo cụm, các điểm tương đồng chưa được lấy chính xác. Vét cạn Vét cạn có thể được diễn giải là duyệt hết không gian tìm kiếm, so khớp từng cặp phần tử của đối tượng cần nhận dạng với các đối tượng đã có trong cơ sở dữ liệu. Ưu điểm của phương pháp này là độ chính xác rất cao. Tuy nhiên, trong trường hợp không gian tìm kiếm rộng lớn, thì tốc độ thực hiện lại rất chậm.
Cây nhận dạng Sử dụng cây nhận dạng dé phân loại các đối tượng về n lớp cho trước. Định nghĩa cây nhân dạng Một cây nhận dạng có độ rộng n được định nghĩa như sau : Cho trước hai số nguyên dương n, L và P = {0, I,. Cây nhận dạng có độ rộng n trên P là bộ 4: A=(V,E,e,ồ} Trong đó : V là tập đỉnh E là tập nhánh Ánh xạe:(V\T)x{+,-} >E T là tập các đối tượng cần kiểm tra (tập n nút đích (gồm n nút lá), TcV Ánh xạ ö : V > P( Sao cho 8“! (x) =T) Trong đó, gọi e(v, +), e(v, -) lần lượt là nhánh thế trái, nhánh thế phải của v € V và (V, E) gọi là cây nền. Biểu diễn cây nhân dang Một cây nhận dang có thé được biéu diễn dưới dạng đồ thị như sau: Hình 1.2: Biểu diễn cây nhận dạng Phương pháp cây nhận dạng khắc phục được các khuyết điểm của các phương pháp trên, đó là tăng tốc độ nhận dạng mà vẫn đảm bảo được độ chính xác cao, do việc so sánh đối tượng cần nhận dạng với các đối tượng đã có trong cơ sở dữ liệu thông qua tập đỉnh của cây (tập các thuộc tính của các đối tượng đã được sắp thứ tự ưu tiên).
Cây chứng thực THAT ~ GIA Cây chứng thực là một trường hợp của cây nhận dạng (1.4c) trong đó có độ rộng n = 2 ứng với hai giá trị THẬT - GIẢ. Thực chất, cây chứng thực là một tập thứ tự đỉnh tối ưu với tiêu chí đánh giá là phát hiện “giả” nhanh nhất, chỉ áp dụng cho bài toán chứng thực vector: xác định một đối tượng bất kỳ là THẬT hay GIẢ (1. Áp dụng cây chứng thực cho bài toán chứng thực vector 1. So sánh phương pháp cây chứng thực với phương pháp vét cạn truyền thống Bài toán chứng thực vector (1.2a) có thé phát biểu chỉ tiết như sau: Cho Vector đăng ký: P = {0.C, V}L € OrnAr, sai số e € RL, và vector cần chứng thực X = {0.
Xác định khoảng cách: 6 = ||X-PII e RX Nếu 8 < ¢ => X “là” THAT. Ngược lại X “là” GIẢ. Yêu cầu: phát hiện GIẢ nhanh nhát. Để giải quyết bài toán này, sử dụng 2 phương pháp: vét cạn và cây chứng thực tối ưu.3: Hai phương pháp chứng thực Nhận thấy: - V6i phương pháp vét can: Nếu phần tử sai khác ở cuối vector thì tốc độ chứng thực sẽ chậm.
- _ Với phương pháp sử dụng cây chứng thực tối ưu (tập thứ tự duyệt tối ưu): đảm bảo khắc phục được nhược điểm trên. Ví dụ: Cho vector P = {p¡, pạ,. , Pio), và vector X = {XỊ, Xa,. Cần xác định xem X có phải là P hay không? Giả sử cho trước các giá trị xác suất “giả” của từng Xi.
Với phương pháp vét cạn: phải duyệt từ đầu đến cuối vector. Tại mỗi thời điểm thứ i, cần so khớp giữa X; và P;. Với phương pháp cây chứng thực tối ưu: Do đã sắp thứ tự mức độ “giả” của các X; giảm dan, ta sẽ duyệt theo thứ tự mức độ “giả” giảm dan đó. Đồ thi so sánh giữa 2 phương pháp trên được thé hiện trong hình dưới: Phương pháp vét cạn Phương pháp cây chứng thực tối ưu 12345678916 9108 4 75263 1 Hình 1.4: Đồ thị so sánh hai phương pháp chứng thực: bằng vét cạn và bằng cây chứng thực tối ưu 1.
Các phương pháp tìm cây chứng thực tối wu Với mục tiêu là là tìm ra tập thứ tự tối ưu (cây chứng thực tối ưu), ta có thê sử dụng các phương pháp truyền thống với nền tảng toán học vững chắc như ID3, ASSISTANT, C4. Nhìn chung, các phương pháp này đều dựa trên nguyên tắc: duyệt toàn bộ không gian các cây nhận dạng rồi từ đó mới tìm ra được cây tối ưu. Như vậy, các phương pháp này thường thích hợp với những bài toán có không gian thuộc tính nhỏ (số lượng thuộc tính không nhiều). Tuy nhiên, với các bài toán chứng thực khác trong đó có số lượng các thuộc tính rất lớn (như chứng thực gene, chứng thực ảnh.), các phương pháp truyền thống khi áp dụng để giải quyết bài toán này thường sẽ tốn thời gian và tăng độ phức tạp tính toán.
Lúc này, chúng tôi sử dụng thuật giải di truyền dé tim ra cây chứng thực tối ưu. Với phương pháp thuật giải di truyền, không cần vét cạn toàn bộ không gian các thuộc tính (toàn bộ không gian các cây chứng thực) mà. vẫn tìm ra các cây chứng thực tối ưu dựa trên cơ sở hàm lượng giá của từng cây. Như vậy, thuật giải đi truyền tiết kiệm được thời gian hơn, đồng thời cũng giảm được độ phức tạp tính toán so với các phương pháp khác.
Kếtluận Tom lại, chương này trình bay lý thuyết tổng quan về bài toán nhận dạng mẫu tổng quát, bài toán chứng thực vector, và các phương pháp đề giải quyết bài toán này. Dựa trên việc nhận xét các phương pháp, chúng tôi nhận thấy được các ưu điểm của việc sử dụng thuật giải di truyền trong việc tìm cây chứng thực tối ưu, và sử dụng phương pháp này trong việc chứng thực các đối tượng là ảnh. Chương 2: ÁP DỤNG THUẬT GIẢI DI TRUYÈN TÌM CÂY CHỨNG THỰC TÓI ƯU 2. Giới thiệu Trong chương này, chúng tôi sẽ tìm hiểu về: thuật giải đi truyền, ứng dụng thuật giải đi truyền dé tối ưu hàm rời rac tông quát, và áp dụng thuật giải di truyền trong việc tim cây chứng thực tối ưu.
Thuật giải di truyền 2. Tóm tắt lịch sử hình thành Y niệm về thuật giải di truyền đã được một số nhà sinh vật học nêu ra từ nhũng năm 50, 60 của thế kỷ XX.Fraser là người đầu tiên nêu lên sự tương đồng giữa sự tiến hóa của sinh vật và chương trình tin học giả tưởng về GA. Tuy nhiên chính tiến sĩ John Henry Holland, đại học Michigan, mới là người triển khai ý tưởng và phương thức giải quyết vấn đề dựa theo sự tiến hóa của con người. Chính ông cùng các sinh viên của trường đại học Michigan đã phát triển nó trong suốt những năm 1960 — 1970.
Trong tác pham Sự thích nghỉ trong tự nhiên và các hệ thống nhân tạo được xuất bản năm 1975, tiến sĩ đã giới thiệu thuật giải di truyền như là một sự trừu tượng hóa của sự tiến hóa sinh học và đưa ra một khung nhìn mang tính lý thuyết về sự thích nghỉ làm nền tảng cho GA.