LỜI NÓI ĐẦU

Trong thực tế cuộc sống, các bài toán liên quan đến hệ thống nhận thức, tri thức của con người, đều hàm chứa những đại lượng, thông tin, mà bản chất là không chính xác, không chắc chắn, không đầy đủ . cho các hệ thống ra quyết định.

Ví dụ: Sẽ chẳng bao giờ có thông tin, dữ liệu, cũng như các mô hình tính toán đầy đủ và chính xác cho bài toán dự báo thời tiết.

Trong lĩnh vực khoa học cũng vậy, các hệ thống phức tạp trên thực tế thường không thể mô tả đầy đủ, và chính xác bởi các phương trình toán học truyền thống. Kết quả là những cách tiếp cận kinh điển dựa trên kỹ thuật phân tích, và các phương trình toán học nhanh chóng không còn phù hợp. Vì thế công nghệ tính toán mềm chính là giải pháp cần thiết trong lĩnh vực này.

Công nghệ tính toán mềm bao gồm 3 thành phần chính:

- Điều khiển mờ (Fuzzy Control)

- Mạng nơ-ron nhân tạo (Neural Network)

- Giải thuật di truyền (Genetic Algorithm)

Do thời gian không nhiều và khối lượng công việc tìm hiểu khá lớn nên trong khuôn khổ đồ án tốt nghiệp này, để tìm hiểu cho sâu, em tập trung nghiên cứu giải thuật di truyền.

Hiện nay, thuật toán di truyền cùng với logic mờ được ứng dụng rộng rãi trong các lĩnh vực phức tạp, các vấn đề khó, sử dụng các kỹ thuật tìm kiếm lời giải, với không gian tìm kiếm rất lớn, nhất là những bài toán cần có sự lượng giá, đánh giá sự tối ưu của kết quả thu được. Chính vì vậy, thuật giải di truyền đã trở thành đề tài nghiên cứu thú vị và đem đến nhiều ứng dụng trong thực tiễn.

Xuất phát từ những vấn đề trên, khóa luận đã tìm hiểu, nghiên cứu giải thuật di truyền. Sau đó sử dụng giải thuật di truyền cổ điển kết hợp với phương pháp thống kê ngôn ngữ học giải quyết bài toán “Dò tìm mã DES”.

Khóa luận không tránh khỏi những thiếu sót, rất mong được sự giúp đỡ, chỉ bảo của thầy cô và các bạn!

MỤC LỤC

LỜI NÓI ĐẦU 5

Chương 1: TÍNH TOÁN MỀM . 6

1.1. KHÁI NIỆM TÍNH TOÁN MỀM . 6

1.2. PHÂN BIỆT TÍNH TOÁN MỀM VÀ TÍNH TOÁN CỨNG 7

1.3. TẠI SAO CẦN PHẢI CÓ TÍNH TOÁN MỀM . 8

1.4. CÁC KỸ THUẬT TRONG TÍNH TOÁN MỀM . 9

1.4.1. Logic mờ (Fuzzy Logic – FL) 9

1.4.2. Mạng Nơron (Neural Network – NN). 10

1.4.3. Chương trình tiến hóa (Evolutionary Computation – EC) 11

Chương 2: GIẢI THUẬT DI TRUYỀN 12

2.1. KHÁI NIỆM GIẢI THUẬT DI TRUYỀN 12

2.1.1. Đặc trưng của thuật toán di truyền kinh điển. 12

2.1.2. Cơ sở sinh học của giải thuật di truyền. 13

2.1.3. Tư tưởng của giải thuật di truyền. 14

2.1.4. Hoạt động của giải thuật di truyền. 15

2.2. CẤU TRÚC GIẢI THUẬT DI TRUYỀN ĐƠN GIẢN 17

2.2.1. Tái tạo. 18

2.2.2. Lai ghép. 20

2.2.3. Đột biến. 21

2.3. SƠ ĐỒ GIẢI THUẬT DI TRUYỀN 22

2.4. MỘT SỐ CẢI TIẾN CỦA THUẬT TOÁN DI TRUYỀN ĐƠN GIẢN 23

2.4.1. Cải tiến phương pháp chọn lọc. 23

2.4.1.1. Chọn lọc xếp hạng (Rank Selection) 23

2.4.1.2. Chọn lọc cạnh tranh (Tournament selection) 24

2.4.2. Cải tiến toán tử lai ghép. 24

2.4.2.1. Lai ghép ánh xạ từng phần (PMX – Partial Mappel Crossover) 24

2.4.2.2. Lai ghép có trật tự (OX – Order Crossover) 25

2.4.2.3. Lai ghép dựa trên vị trí (Possition Base Crossover) 26

2.4.2.4. Lai ghép dựa trên thứ tự (Order – Base Crossover) 27

2.4.2.5. Lai ghép có chu trình (CX – Cycle Crossover) 28

2.4.2.6. Lai ghép thứ tự tuyến tính (LOX – Linea Order Crossover) 29

2.4.3. Cải tiến về hàm mục tiêu. 30

2.4.3.1. Chuyển đổi hàm mục tiêu thành hàm thích nghi 30

2.4.3.2. Phép sửa đổi hàm thích nghi theo từng bước lặp. 31

2.5. BÀI TOÁN TỐI ƯU HÀM SỐ 32

Chương 3: HỆ MÃ HÓA DỮ LIỆU DES. 34

3.1. HỆ MÃ HÓA 34

3.1.1. Khái niệm mã hóa. 35

3.1.2. Phân loại mã hóa. 35

3.1.2.1. Hệ mã hóa khóa đối xứng. 36

3.1.2.2. Hệ mã hóa khóa phi đối xứng (hệ mã hóa khóa công khai) 37

3.2. HỆ MÃ HÓA DES. 39

3.2.1. Giới thiệu hệ mã hóa DES. 39

3.2.2. Quy trình mã hóa DES. 40

3.2.2.1. Sơ đồ: 41

3.2.2.2. Thực hiện mã hóa theo sơ đồ. 41

3.2.2.3. Tính các khóa con k1, k2, , k16 từ khóa gốc K. 42

3.2.2.4. Tính hàm f(Ri-1, ki) 44

3.2.3. Quy trình giải mã DES. 49

3.2.4. Ví dụ. 50

3.2.5. Độ an toàn của Hệ mã hóa DES. 52

Chương 4: PHƯƠNG PHÁP THỐNG KÊ NGÔN NGỮ HỌC VÀ GIẢI THUẬT

DI TRUYỀN ĐỂ DÒ TÌM KHÓA MẬT 53

4.1. TẦN XUẤT XUẤT HIỆN CỦA CÁC CHỮ CÁI TRONG BẢN RÕ

TIẾNG ANH 53

4.1.1. Các kí tự hiếm gặp (Có tần suất xuất hiện thấp): z, q, j, x, k, v. 53

4.1.2. Các kí tự hay gặp (Có tần suất xuất hiện cao). 54

4.2. DÒ TÌM KHÓA BẰNG THỐNG KÊ NGÔN NGỮ HỌC VÀ

THUẬT TOÁN GA 57

4.2.1. Giai đoạn 1: 58

4.2.2. Giai đoạn 2. 60

KẾT LUẬN 62

TÀI LIỆU THAM KHẢO 6