Link tải luận văn miễn phí cho ae Kết Nối
Tiểu luận môn Thuật Toán và Phương Pháp Giải Quyết Vấn Đề Tìm hiểu thuật giải di truyền và ứng dụng vào đoán password
Mục lục
1. Tổng quan về Thuật giải di truyền và các ứng dụng...........................................................................3
1.1 Metaheuristic là gì...........................................................................................................................3
1.2 Tìm hiểu Thuật giải di truyền và ứng dụng........................................................................................3
1.2.1 Giới thiệu thuật giải di truyền:........................................................................................................3
1.2.2 Các bước chính của thuật giải di truyền:.........................................................................................4
1.2.3 Các thành phần cơ bản của thuật giải di truyền...............................................................................4
1.2.4 Cấu trúc giải thuật di truyền tổng quát.....................................................................................6
2. Ứng dụng thuật toán di truyền vào bài toán đoán password gồm 6 chữ số.................................9
2.1. Giới thiệu bài toán............................................................................................................................9
2.2. Thiết kế thuật giải di truyền đoán password..............................................................................11
2.3 Cài đặt thuật giải di truyền bằng C#................................................................................................11
2.4 Màn hình chính:...............................................................................................................................14
3. Kết luận................................................................................................................................................14
Tài liệu tham khảo.....................................................................................................................................15
1. Tổng quan về Thuật giải di truyền và các ứng dụng.
1.1 Metaheuristic là gì
Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc
giải quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược
khác nhau trong việc khám phá không gian tìm kiếm bằng cách sử dụng những
cách khác nhau và phải đạt được sự cân bằng giữa tính đa dạng và
chuyên sâu của không gian tìm kiếm. Một cài đặt thành công của metaheuristic
trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu
thập được trong quá trình tìm kiếm để xác định được những vùng với những lời
giải có chất lượng cao gần tối ưu. Những ví dụ của metaheuristic bao gồm giải
thuật luyện thép (SA - Simulated Annealing), giải thuật di truyền (GA - Genetic
Algorithm), giải thuật đàn kiến (ACO ), tìm kiếm tabu (Tabu search)
1.2 Tìm hiểu Thuật giải di truyền và ứng dụng
1.2.1 Giới thiệu thuật giải di truyền:
Genetic Algorithms tạm dịch là Thuật giải di truyền (ngắn gọn gọi là GA) bắt
nguồn từ ý niệm tiến hóa để tồn tại và phát triển trong tự nhiên.
GA là cách giải quyết vấn đề bắt chước lối hành xử của con người để
tồn tại và phát triển. Nó giúp tìm ra giải pháp tối ưu hay tốt nhất trong điều kiện
thời gian và không gian cho phép.
GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải pháp sau
đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích
nghi hơn để tạo sinh và biến hóa nhằm mục đích tạo ra nhiều giải pháp mới có
hệ số thích nghi ngày càng cao
Hệ số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp.
Cấu trúc dữ liệu + giải thuật di truyền = chương trình tiến hóa.
Thuật ngữ “chương trình tiến hóa” trong công thức trên là khái niện dùng để
chỉ các chương trình máy tính có sử dụng thuật toán tìm kiếm và tối ưu hóa
dựa trên nguyên lý tiến hóa tự nhiên
1.2.2 Các bước chính của thuật giải di truyền:
Bước 1: Chọn mô hình (model) để tượng trưng cho các giải pháp. Các mô hình
có thể là dãy (String) những số nhị phân: 1 và 0, thập phân và có thể là chữ hay
hỗn hợp giữa chữ và số.
Bước 2: Chọn hàm số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp.
2
Bước 3: Tiếp tục các hình thức biến hóa cho đến khi đạt được các giải pháp tốt
nhất hay đến khi thời gian cho phép chấm dứt.
1.2.3 Các thành phần cơ bản của thuật giải di truyền
Quá trình lai ghép (phép lai)
+Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kỳ trong quần thể. Giả sử các
nhiễm sắc thể của cha mẹ đều có m gen.
+Tạo một số ngẫu nhiên trong khoảng từ 1 đến m-1 (ta gọi là điểm lai).
+Đưa hai cá thể mới này vào quẩn thể để tham gia các quá trình tiến hóa tiếp
theo.
Quá trình đột biến (phép đột biến)
+Chọn ngẫu nhiên một cá thể bất kỳ cha mẹ trong quần thể.
+Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m, 1 ≤ k ≤ m.
+Thay đổi gen thứ k và trả cá thể này về quần thể để tham giá quá trình tiến
hóa tiếp theo
Quá trình sinh sản
+Tính độ thích nghi của từng cá thể trong quẩn thể hiện hành, lập bảng
cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá thể). Giả sử
quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i
là Fti, tổng độ thích nghi của toàn quần thể là Fm.
+Tạo một số ngẫu nhiên F trong đoạn từ 0 đến Fm.
+Chọn cá thể thứ k đầu tiên thỏa mãn F ≥ Ftk đưa vào quần thể của thế hệ
mới.
Mỗi cặp bố mẹ sinh hai con theo một trong hai phương pháp sau
+Vô tính
Mỗi ấu nhi là một bản sao chính xác từ cha
Mỗi ấu nhi là một bản sao chính xác từ mẹ
+Hữu tính (giao nhau)
Một vài bits được sao từ mẹ, vài bits được sao chép từ cha
Cứ tiếp tục sao từ một cặp bố mẹ cho đến chừng nào điểm giao
nhau, thì sao chép từ cặp bố mẹ khác.
Quá trình chọn lọc
+Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.
+Loại bỏ các cá thể cuối dãy để chỉ giữ lại n cá thể tốt nhất. Ở đây, tả giả sử
quần thể có kích thước cố định n.
Điều kiện dừng của giải thuật:
Chúng ta sẽ khảo sát điều kiện đơn giản nhất để dừng khi số thế hệ vượt quá
một ngưỡng cho trước. Trong một số phiên bản về chương trình tiến hoá
không phải mọi cá thể đều tiến hoá lại. Vài cá thể trong đó có khả năng vượt
từ thế hệ này sang thế hệ khác mà không thay đổi gì cả. Trong những trường
hợp như vậy, chúng ta đếm số lần lượng hàm.
Nếu số lần lượng hàm vượt quá một hằng xác định trước thì dừng việc tìm
kiếm.
Chúng ta nhận thấy, các điều kiện dừng ở trên giả thiết rằng người sử dụng đã
biết đặc trưng của hàm, có ảnh hưởng như thế nào tới chiều dài tìm kiếm.
Trong một số trường hợp khó có thể xác định số lượng thế hệ (hay lượng giá
hàm) phải là bao nhiêu. Giải thuật có thể kết thúc khi cơ hội cho một cải
thiện quan trọng chưa bắt đầu.
Có hai loại điều kiện dừng cơ bản. Các điều kiện này dùng các đặc trưng tìm
kiếm để quyết định ngừng quá trình tìm kiếm .
-Dựa trên cấu trúc nhiễm sắc thể: do sự hội tụ của quần thể bằng cách kiểm
soát số alen được hội tụ, ở đây alen được coi như hội tụ nếu một số phần trăm
quần thể đã định trước có cùng (hay tương đương đối với các biểu diễn
không nhị phân) giá trị trong alen này. Nếu số alen hội tụ vượt quá số phần
trăm nào đó của tổng số alen, việc tìm kiếm sẽ kết thúc.
-Dựa trên ý nghĩa đặc biệt của một nhiễm sắc thể: đo tiến bộ của giải thuật
trong một số thế hệ cho trước. Nếu tiến bộ này nhỏ hơn một hằng số ε xác
định, kết thúc tìm kiếm.
1.2.4 Cấu trúc giải thuật di truyền tổng quát
Bắt đầu
3. Kết luận
Cùng với sự phát triển nhanh chóng, vượt bậc của ngành công nghiệp máy tính,
nhu cầu của người dùng đối với máy tính ngày một cao hơn: không chỉ giải
quyết những công việc lưu trữ, tính toán bình thường, người dùng còn mong đợi
máy tính có khả năng thông minh hơn, có thể giải quyết vấn đề như con người.
Thuật giải di truyền được sử dụng vào nhiều lĩnh vực. Ứng dụng trong bài viết
chỉ ở mức ví dụ sơ đẳng nhất về thuật giải di truyền. Hướng phát triển của tiểu
luận sau này là có thể đề xuất thiết kế, phương pháp áp dụng thuật giải di truyền
để xây dựng hệ thống thông minh như hổ trợ ra quyết định.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Tiểu luận môn Thuật Toán và Phương Pháp Giải Quyết Vấn Đề Tìm hiểu thuật giải di truyền và ứng dụng vào đoán password
Mục lục
1. Tổng quan về Thuật giải di truyền và các ứng dụng...........................................................................3
1.1 Metaheuristic là gì...........................................................................................................................3
1.2 Tìm hiểu Thuật giải di truyền và ứng dụng........................................................................................3
1.2.1 Giới thiệu thuật giải di truyền:........................................................................................................3
1.2.2 Các bước chính của thuật giải di truyền:.........................................................................................4
1.2.3 Các thành phần cơ bản của thuật giải di truyền...............................................................................4
1.2.4 Cấu trúc giải thuật di truyền tổng quát.....................................................................................6
2. Ứng dụng thuật toán di truyền vào bài toán đoán password gồm 6 chữ số.................................9
2.1. Giới thiệu bài toán............................................................................................................................9
2.2. Thiết kế thuật giải di truyền đoán password..............................................................................11
2.3 Cài đặt thuật giải di truyền bằng C#................................................................................................11
2.4 Màn hình chính:...............................................................................................................................14
3. Kết luận................................................................................................................................................14
Tài liệu tham khảo.....................................................................................................................................15
1. Tổng quan về Thuật giải di truyền và các ứng dụng.
1.1 Metaheuristic là gì
Metaheuristic là một cách gọi chung cho các giải thuật heuristic trong việc
giải quyết các bài toán tổ hợp khó. Metaheuristic bao gồm những chiến lược
khác nhau trong việc khám phá không gian tìm kiếm bằng cách sử dụng những
cách khác nhau và phải đạt được sự cân bằng giữa tính đa dạng và
chuyên sâu của không gian tìm kiếm. Một cài đặt thành công của metaheuristic
trong một bài toán tổ hợp phải cân bằng giữa sự khai thác được kinh nghiệm thu
thập được trong quá trình tìm kiếm để xác định được những vùng với những lời
giải có chất lượng cao gần tối ưu. Những ví dụ của metaheuristic bao gồm giải
thuật luyện thép (SA - Simulated Annealing), giải thuật di truyền (GA - Genetic
Algorithm), giải thuật đàn kiến (ACO ), tìm kiếm tabu (Tabu search)
1.2 Tìm hiểu Thuật giải di truyền và ứng dụng
1.2.1 Giới thiệu thuật giải di truyền:
Genetic Algorithms tạm dịch là Thuật giải di truyền (ngắn gọn gọi là GA) bắt
nguồn từ ý niệm tiến hóa để tồn tại và phát triển trong tự nhiên.
GA là cách giải quyết vấn đề bắt chước lối hành xử của con người để
tồn tại và phát triển. Nó giúp tìm ra giải pháp tối ưu hay tốt nhất trong điều kiện
thời gian và không gian cho phép.
GA xét đến toàn bộ các giải pháp, bằng cách xét trước nhất một số giải pháp sau
đó loại bỏ những thành phần không thích hợp và chọn những thành phần thích
nghi hơn để tạo sinh và biến hóa nhằm mục đích tạo ra nhiều giải pháp mới có
hệ số thích nghi ngày càng cao
Hệ số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp.
Cấu trúc dữ liệu + giải thuật di truyền = chương trình tiến hóa.
Thuật ngữ “chương trình tiến hóa” trong công thức trên là khái niện dùng để
chỉ các chương trình máy tính có sử dụng thuật toán tìm kiếm và tối ưu hóa
dựa trên nguyên lý tiến hóa tự nhiên
1.2.2 Các bước chính của thuật giải di truyền:
Bước 1: Chọn mô hình (model) để tượng trưng cho các giải pháp. Các mô hình
có thể là dãy (String) những số nhị phân: 1 và 0, thập phân và có thể là chữ hay
hỗn hợp giữa chữ và số.
Bước 2: Chọn hàm số thích nghi để dùng làm tiêu chuẩn đánh giá các giải pháp.
2
Bước 3: Tiếp tục các hình thức biến hóa cho đến khi đạt được các giải pháp tốt
nhất hay đến khi thời gian cho phép chấm dứt.
1.2.3 Các thành phần cơ bản của thuật giải di truyền
Quá trình lai ghép (phép lai)
+Chọn ngẫu nhiên hai (hay nhiều) cá thể bất kỳ trong quần thể. Giả sử các
nhiễm sắc thể của cha mẹ đều có m gen.
+Tạo một số ngẫu nhiên trong khoảng từ 1 đến m-1 (ta gọi là điểm lai).
+Đưa hai cá thể mới này vào quẩn thể để tham gia các quá trình tiến hóa tiếp
theo.
Quá trình đột biến (phép đột biến)
+Chọn ngẫu nhiên một cá thể bất kỳ cha mẹ trong quần thể.
+Tạo một số ngẫu nhiên k trong khoảng từ 1 đến m, 1 ≤ k ≤ m.
+Thay đổi gen thứ k và trả cá thể này về quần thể để tham giá quá trình tiến
hóa tiếp theo
Quá trình sinh sản
+Tính độ thích nghi của từng cá thể trong quẩn thể hiện hành, lập bảng
cộng dồn các giá trị thích nghi (theo số thứ tự gán cho từng cá thể). Giả sử
quần thể có n cá thể. Gọi độ thích nghi của cá thể thứ i là Fi, tổng dồn thứ i
là Fti, tổng độ thích nghi của toàn quần thể là Fm.
+Tạo một số ngẫu nhiên F trong đoạn từ 0 đến Fm.
+Chọn cá thể thứ k đầu tiên thỏa mãn F ≥ Ftk đưa vào quần thể của thế hệ
mới.
Mỗi cặp bố mẹ sinh hai con theo một trong hai phương pháp sau
+Vô tính
Mỗi ấu nhi là một bản sao chính xác từ cha
Mỗi ấu nhi là một bản sao chính xác từ mẹ
+Hữu tính (giao nhau)
Một vài bits được sao từ mẹ, vài bits được sao chép từ cha
Cứ tiếp tục sao từ một cặp bố mẹ cho đến chừng nào điểm giao
nhau, thì sao chép từ cặp bố mẹ khác.
Quá trình chọn lọc
+Sắp xếp quần thể theo thứ tự độ thích nghi giảm dần.
+Loại bỏ các cá thể cuối dãy để chỉ giữ lại n cá thể tốt nhất. Ở đây, tả giả sử
quần thể có kích thước cố định n.
Điều kiện dừng của giải thuật:
Chúng ta sẽ khảo sát điều kiện đơn giản nhất để dừng khi số thế hệ vượt quá
một ngưỡng cho trước. Trong một số phiên bản về chương trình tiến hoá
không phải mọi cá thể đều tiến hoá lại. Vài cá thể trong đó có khả năng vượt
từ thế hệ này sang thế hệ khác mà không thay đổi gì cả. Trong những trường
hợp như vậy, chúng ta đếm số lần lượng hàm.
Nếu số lần lượng hàm vượt quá một hằng xác định trước thì dừng việc tìm
kiếm.
Chúng ta nhận thấy, các điều kiện dừng ở trên giả thiết rằng người sử dụng đã
biết đặc trưng của hàm, có ảnh hưởng như thế nào tới chiều dài tìm kiếm.
Trong một số trường hợp khó có thể xác định số lượng thế hệ (hay lượng giá
hàm) phải là bao nhiêu. Giải thuật có thể kết thúc khi cơ hội cho một cải
thiện quan trọng chưa bắt đầu.
Có hai loại điều kiện dừng cơ bản. Các điều kiện này dùng các đặc trưng tìm
kiếm để quyết định ngừng quá trình tìm kiếm .
-Dựa trên cấu trúc nhiễm sắc thể: do sự hội tụ của quần thể bằng cách kiểm
soát số alen được hội tụ, ở đây alen được coi như hội tụ nếu một số phần trăm
quần thể đã định trước có cùng (hay tương đương đối với các biểu diễn
không nhị phân) giá trị trong alen này. Nếu số alen hội tụ vượt quá số phần
trăm nào đó của tổng số alen, việc tìm kiếm sẽ kết thúc.
-Dựa trên ý nghĩa đặc biệt của một nhiễm sắc thể: đo tiến bộ của giải thuật
trong một số thế hệ cho trước. Nếu tiến bộ này nhỏ hơn một hằng số ε xác
định, kết thúc tìm kiếm.
1.2.4 Cấu trúc giải thuật di truyền tổng quát
Bắt đầu
3. Kết luận
Cùng với sự phát triển nhanh chóng, vượt bậc của ngành công nghiệp máy tính,
nhu cầu của người dùng đối với máy tính ngày một cao hơn: không chỉ giải
quyết những công việc lưu trữ, tính toán bình thường, người dùng còn mong đợi
máy tính có khả năng thông minh hơn, có thể giải quyết vấn đề như con người.
Thuật giải di truyền được sử dụng vào nhiều lĩnh vực. Ứng dụng trong bài viết
chỉ ở mức ví dụ sơ đẳng nhất về thuật giải di truyền. Hướng phát triển của tiểu
luận sau này là có thể đề xuất thiết kế, phương pháp áp dụng thuật giải di truyền
để xây dựng hệ thống thông minh như hổ trợ ra quyết định.
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links