Link tải luận văn miễn phí cho ae Kết Nối
I. Giới thiệu chung. 2
II. Giải thuật gene. 3
1. Các khái niệm. 3
2. Cấu trúc cơ bản của GAs. 4
III. Áp dụng thuật toán gene vào bài toán Knapsack 02. 9
1. Mô tả bài toán. 9
2. Phương án giải bài toán. 9
IV. Ưu và nhược điểm. 11
1. Ưu điểm. 11
2. Nhược điểm. 11
V. Kết luận. 11
Tài liệu tham khảo: 12
I. Giới thiệu chung.
Xuất phát từ khái niệm lý thuyết Darwin của sự tồn tại thích hợp nhất và được John Holland đưa ra lần đầu tiên vào năm 1975. Thuật toán gene (GAs – Genetic Algorithms) là thuật toán tìm kiếm, chọn lựa giải pháp tối ưu để giải quyết các bài toán khác nhau dựa trên mô phỏng cơ chế tiến hoá của tự nhiên.
Trong cơ thể sinh vật, các gene liên kết với nhau theo cấu trúc dạng chuỗi gọi là nhiễm sắc thể (Chromosomes), nó đặc trưng co mỗi loài và quyết định sự sống còn của cơ thể đó. Trong tự nhiên một loài muốn tồn tại phải thích nghi với môi trường, cơ thể sống nào thích nghi với môi trường tốt thì tồn tại và phát triển, ngược lại với những loài không thích nghi với môi trường sống sẽ bị đào loại bỏ và dần dần tuyệt chủng. Môi trường tự nhiên thay đổi nên cấu trúc nhiễm sắc thể cũng thay đổi để thích nghi với môi trường nên thế hệ sau luôn có độ thích nghi cao hơn thế hệ trước. Dựa vào đó các nhà khoa học máy tính xây dựng nên môi trường giải thuật tìm kiếm dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hoá, gọi là giải thuật gene.
Năm 1989, Goldberg chỉ ra sự khác nhau chủ yếu giữa GAs và phương pháp tối ưu truyền thống như sau:
- GAs sử dụng theo xác suất, không phải theo quyết định, để tìm kiếm các quy tắc.
- GAs sử dụng các thông tin từ hàm mục tiêu, không sư dụng thông tin biết được khác.
- Đăc trưng của GAs là sử dụng chính sự mã hoá của tập hợp biến quyết định, không phải là biến quyết định chính bản thân.
- Những sự tìm kiếm của GAs xuất phát từ tập hợp các biến quyết định của quần thể, không phải tập hợp biến quyết định riêng lẻ.
II. Giải thuật gene.
1. Các khái niệm.
- Nhiễm sắc thể (Chromosomes):
o Trong GAs mỗi cá thể được mã hoá bởi 1 cấu trúc dữ liệu mô tả cấu trúc gen của cá thể đó, ta gọi là nhiễm sắc thể. Chúng thay mặt cho không gian của các giải pháp ứng cử viên. Nhiễm sắc thể có thể được mã hoá nhị phân, hoán vị, giá trị và mã hoá cây.
o Đối với bài toán chiếc ba lô loại 2, ta sử dụng mã hoá giá trị.
- Quần thể (Population):
o Là một tập hợp các cá thể, được tiến hoá từ thế hệ này tới thế hệ khác phụ thuộc vào sự thích nghi của các cá thể.
- Thế hệ (Generation):
o GAs sẽ làm việc trên các cá thể của nhiều quần thể, mỗi quần thể ứng với một giai đoạn phát triển gọi là thế hệ.
- Hàm thích nghi (Fitness function):
o GAs yêu cầu 1 hàm thích nghi để chứa điểm của mỗi cá thể trong cộng đồng hiện tại. Từ đó có thể tính toán giải pháp nào được mã hoá và nắm được cách mà chúng giải quyết vấn đề.
- Kỳ vọng (Hope):
o Hy vọng hế hệ sinh ra sẽ chứa lời giải tốt cho bài toán.
- Toán tử tái sinh (Reproduction) hay toán tử chọn lọn (Selection):
o Các cá thể tốt được chọn lọc để đưa vào thế hệ sau dựa trên hàm thích nghi.
- Toán tử lại ghép (Crossover):
o Hai cá thể cha mẹ trao đổi các Gen để tạo ra 2 cá thể con.
- Toán tử đột biến (Mutation):
o Một cá thể thay đổi 1 số Gen không theo quy luật để tạo ra thế hệ mới.
2. Cấu trúc cơ bản của GAs.
a. Mã hoá (Encoding).
- Mã hoá nhị phân (Binary Encoding – BE):
o Là kiểu mã hoá thông dụng nhất bởi vì: nghiên cứu đầu tiên về thuật toán Gen sử dụng kiểu mã hóa này và bởi vì nó đơn giản.
o Trong BE, mọi nhiễm sắc thể là chuỗi bits - 0 or 1.
o NST A 101100101100101011100101
o NST B 111111100000110000011111
o Các mã hóa này thường không tự nhiên cho nhiều bài toán và thỉnh thoảng sai sau khi thự hiện các phép toán lai ghép và đột biến.
- Mã hoá hoán vị (Permutation Encoding – PE):
o Có thể sử dụng để giải quyết các bài toán có thứ tự như: Người bán hàng
o Trong PE, tất cả các NST là chuỗi các số biểu diễn vị trí trong một dãy.
o NST A 1 5 3 2 6 4 7 9 8
o NST B 8 5 6 7 2 3 1 4 9
o PEđược sử dụng trong các bài toán có thứ tự. Trong một vài trường hợp, việc hiệu chỉnh lai ghép và đột biến phải thực hiện để tạo ra NST phù hợp.
- Mã hoá giá trị (Value Encoding – VE):
o Được sử dụng trong các bài toán mà việc mã hóa nhị phân là khó thực hiện (Như bài toán knapsack 02).
o Trong VE mỗi nhiễm sắc thể là một chuỗi các giá trị có thể nhận dạng bất kỳ tùy thuộc vào từng bài toán cụ thể.
o NST A 1.2324 5.3243 0.4556 2.3293 2.4545
o NST B ABDJEIFJDHDIERJFDLDFLFEGT
o NST C (back), (back), (right), (forward), (left)
o Với kiểu mã hóa này thường sẽ phải xây dựng một số phép lai ghép và đột biến cho các bài tóan cụ thể.
- Mã hoá dạng cây (Tree Encoding – TE):
o TE thường được sử dụng trong các bài toán hay các biểu thức suy luận.
o Trong TE, mỗi NST là một cây gồm các đối tượng như là các hàm hay các câu lệnh của ngôn ngữ lập trình.
o TE thường được dùng đối với các bìa tóan suy luận hay các cấu trúc có thể biểu diễn bằng cây.
o Các phép lai ghép và đột biến đối với kiểu mã hóa này cũng tương đối dễ thực hiện.
b. Khởi tạo quần thể.
- Thường được chọn random dựa vào yêu cầu bài toán.
c. Hàm thích nghi.
- Hàm thích nghi định nghĩa tiêu chuẩn để xếp hạng các giả thuyết tiềm ẩn và để chọn lọc chúng theo xác suất để đưa vào quần thể thế hệ kế tiếp.
- Mỗi bài toán có một hàm thích nghi riêng.
d. Chọn lọc.
- Các nhiễm sắc thể được chọn từ quần thể là các cha cho lai ghép (crossover).
- Theo thuyết tiến hoá của Darwin những cá thể tốt nhất sẽ được họn để lai ghép.
- Có nhiều phương pháp lựa chọn như:
o Roulette Wheel Selection:
Nhiễm sắc thể được chọn thông qua độ thích nghi của chúng.
Nhiễm sắc thể tốt hơn (mang hàm ý xác suất) được chọn.
Minh họa về phương pháp chọn:
Đặt các NST lên roulette wheel.
Kích thước của đoạn trong roulete wheel tương ứng với giá trị của hàm thích nghi.
Một hòn bi được lăn trong roulette wheel và NST nơi nó dừng lại được lựa chọn.
NST với giá trị thích nghi lớn sẽ được chọn nhiều hơn.
Tiến trình trên có thể được mô tả bởi thuật toán sau:
• [Tính tổng] Tính tổng S của giá trị thích nghi của tất cả cá thể trong quần thể.
• [Lựa chọn] Chọn ngẫu nhiên một giá trị r trong đoạn (0,S).
• [Vòng lặp] Với giá trị ngẫu nhiên r đã chọn, tương ứng với các thể nào đó khi hình thành S thì cá thể đó được chọn cho thế hệ kế tiếp.
o Rank Selection:
Roulette Wheel Selection sẽ có vấn đề khi có sự khác nhau lớn giữa các độ thích nghi.
Ví dụ: nếu NST tốt nhất có độ thích nghi là 90% thì các NST khác rất ít cơ hội được lựa chọn.
Rank selection tính hạng quần thể đầu tiên và sau đó mọi NST nhận lại giá trị thích nghi được định nghĩa bởi hạng của chúng.
NST tồi nhất sẽ có độ thích nghi là 1, NST tồi thứ hai là 2 etc. và NST tốt nhất sẽ có độ thích nghi là N (Số nhiễm sắc
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:
I. Giới thiệu chung. 2
II. Giải thuật gene. 3
1. Các khái niệm. 3
2. Cấu trúc cơ bản của GAs. 4
III. Áp dụng thuật toán gene vào bài toán Knapsack 02. 9
1. Mô tả bài toán. 9
2. Phương án giải bài toán. 9
IV. Ưu và nhược điểm. 11
1. Ưu điểm. 11
2. Nhược điểm. 11
V. Kết luận. 11
Tài liệu tham khảo: 12
I. Giới thiệu chung.
Xuất phát từ khái niệm lý thuyết Darwin của sự tồn tại thích hợp nhất và được John Holland đưa ra lần đầu tiên vào năm 1975. Thuật toán gene (GAs – Genetic Algorithms) là thuật toán tìm kiếm, chọn lựa giải pháp tối ưu để giải quyết các bài toán khác nhau dựa trên mô phỏng cơ chế tiến hoá của tự nhiên.
Trong cơ thể sinh vật, các gene liên kết với nhau theo cấu trúc dạng chuỗi gọi là nhiễm sắc thể (Chromosomes), nó đặc trưng co mỗi loài và quyết định sự sống còn của cơ thể đó. Trong tự nhiên một loài muốn tồn tại phải thích nghi với môi trường, cơ thể sống nào thích nghi với môi trường tốt thì tồn tại và phát triển, ngược lại với những loài không thích nghi với môi trường sống sẽ bị đào loại bỏ và dần dần tuyệt chủng. Môi trường tự nhiên thay đổi nên cấu trúc nhiễm sắc thể cũng thay đổi để thích nghi với môi trường nên thế hệ sau luôn có độ thích nghi cao hơn thế hệ trước. Dựa vào đó các nhà khoa học máy tính xây dựng nên môi trường giải thuật tìm kiếm dựa trên cơ sở chọn lọc tự nhiên và quy luật tiến hoá, gọi là giải thuật gene.
Năm 1989, Goldberg chỉ ra sự khác nhau chủ yếu giữa GAs và phương pháp tối ưu truyền thống như sau:
- GAs sử dụng theo xác suất, không phải theo quyết định, để tìm kiếm các quy tắc.
- GAs sử dụng các thông tin từ hàm mục tiêu, không sư dụng thông tin biết được khác.
- Đăc trưng của GAs là sử dụng chính sự mã hoá của tập hợp biến quyết định, không phải là biến quyết định chính bản thân.
- Những sự tìm kiếm của GAs xuất phát từ tập hợp các biến quyết định của quần thể, không phải tập hợp biến quyết định riêng lẻ.
II. Giải thuật gene.
1. Các khái niệm.
- Nhiễm sắc thể (Chromosomes):
o Trong GAs mỗi cá thể được mã hoá bởi 1 cấu trúc dữ liệu mô tả cấu trúc gen của cá thể đó, ta gọi là nhiễm sắc thể. Chúng thay mặt cho không gian của các giải pháp ứng cử viên. Nhiễm sắc thể có thể được mã hoá nhị phân, hoán vị, giá trị và mã hoá cây.
o Đối với bài toán chiếc ba lô loại 2, ta sử dụng mã hoá giá trị.
- Quần thể (Population):
o Là một tập hợp các cá thể, được tiến hoá từ thế hệ này tới thế hệ khác phụ thuộc vào sự thích nghi của các cá thể.
- Thế hệ (Generation):
o GAs sẽ làm việc trên các cá thể của nhiều quần thể, mỗi quần thể ứng với một giai đoạn phát triển gọi là thế hệ.
- Hàm thích nghi (Fitness function):
o GAs yêu cầu 1 hàm thích nghi để chứa điểm của mỗi cá thể trong cộng đồng hiện tại. Từ đó có thể tính toán giải pháp nào được mã hoá và nắm được cách mà chúng giải quyết vấn đề.
- Kỳ vọng (Hope):
o Hy vọng hế hệ sinh ra sẽ chứa lời giải tốt cho bài toán.
- Toán tử tái sinh (Reproduction) hay toán tử chọn lọn (Selection):
o Các cá thể tốt được chọn lọc để đưa vào thế hệ sau dựa trên hàm thích nghi.
- Toán tử lại ghép (Crossover):
o Hai cá thể cha mẹ trao đổi các Gen để tạo ra 2 cá thể con.
- Toán tử đột biến (Mutation):
o Một cá thể thay đổi 1 số Gen không theo quy luật để tạo ra thế hệ mới.
2. Cấu trúc cơ bản của GAs.
a. Mã hoá (Encoding).
- Mã hoá nhị phân (Binary Encoding – BE):
o Là kiểu mã hoá thông dụng nhất bởi vì: nghiên cứu đầu tiên về thuật toán Gen sử dụng kiểu mã hóa này và bởi vì nó đơn giản.
o Trong BE, mọi nhiễm sắc thể là chuỗi bits - 0 or 1.
o NST A 101100101100101011100101
o NST B 111111100000110000011111
o Các mã hóa này thường không tự nhiên cho nhiều bài toán và thỉnh thoảng sai sau khi thự hiện các phép toán lai ghép và đột biến.
- Mã hoá hoán vị (Permutation Encoding – PE):
o Có thể sử dụng để giải quyết các bài toán có thứ tự như: Người bán hàng
o Trong PE, tất cả các NST là chuỗi các số biểu diễn vị trí trong một dãy.
o NST A 1 5 3 2 6 4 7 9 8
o NST B 8 5 6 7 2 3 1 4 9
o PEđược sử dụng trong các bài toán có thứ tự. Trong một vài trường hợp, việc hiệu chỉnh lai ghép và đột biến phải thực hiện để tạo ra NST phù hợp.
- Mã hoá giá trị (Value Encoding – VE):
o Được sử dụng trong các bài toán mà việc mã hóa nhị phân là khó thực hiện (Như bài toán knapsack 02).
o Trong VE mỗi nhiễm sắc thể là một chuỗi các giá trị có thể nhận dạng bất kỳ tùy thuộc vào từng bài toán cụ thể.
o NST A 1.2324 5.3243 0.4556 2.3293 2.4545
o NST B ABDJEIFJDHDIERJFDLDFLFEGT
o NST C (back), (back), (right), (forward), (left)
o Với kiểu mã hóa này thường sẽ phải xây dựng một số phép lai ghép và đột biến cho các bài tóan cụ thể.
- Mã hoá dạng cây (Tree Encoding – TE):
o TE thường được sử dụng trong các bài toán hay các biểu thức suy luận.
o Trong TE, mỗi NST là một cây gồm các đối tượng như là các hàm hay các câu lệnh của ngôn ngữ lập trình.
o TE thường được dùng đối với các bìa tóan suy luận hay các cấu trúc có thể biểu diễn bằng cây.
o Các phép lai ghép và đột biến đối với kiểu mã hóa này cũng tương đối dễ thực hiện.
b. Khởi tạo quần thể.
- Thường được chọn random dựa vào yêu cầu bài toán.
c. Hàm thích nghi.
- Hàm thích nghi định nghĩa tiêu chuẩn để xếp hạng các giả thuyết tiềm ẩn và để chọn lọc chúng theo xác suất để đưa vào quần thể thế hệ kế tiếp.
- Mỗi bài toán có một hàm thích nghi riêng.
d. Chọn lọc.
- Các nhiễm sắc thể được chọn từ quần thể là các cha cho lai ghép (crossover).
- Theo thuyết tiến hoá của Darwin những cá thể tốt nhất sẽ được họn để lai ghép.
- Có nhiều phương pháp lựa chọn như:
o Roulette Wheel Selection:
Nhiễm sắc thể được chọn thông qua độ thích nghi của chúng.
Nhiễm sắc thể tốt hơn (mang hàm ý xác suất) được chọn.
Minh họa về phương pháp chọn:
Đặt các NST lên roulette wheel.
Kích thước của đoạn trong roulete wheel tương ứng với giá trị của hàm thích nghi.
Một hòn bi được lăn trong roulette wheel và NST nơi nó dừng lại được lựa chọn.
NST với giá trị thích nghi lớn sẽ được chọn nhiều hơn.
Tiến trình trên có thể được mô tả bởi thuật toán sau:
• [Tính tổng] Tính tổng S của giá trị thích nghi của tất cả cá thể trong quần thể.
• [Lựa chọn] Chọn ngẫu nhiên một giá trị r trong đoạn (0,S).
• [Vòng lặp] Với giá trị ngẫu nhiên r đã chọn, tương ứng với các thể nào đó khi hình thành S thì cá thể đó được chọn cho thế hệ kế tiếp.
o Rank Selection:
Roulette Wheel Selection sẽ có vấn đề khi có sự khác nhau lớn giữa các độ thích nghi.
Ví dụ: nếu NST tốt nhất có độ thích nghi là 90% thì các NST khác rất ít cơ hội được lựa chọn.
Rank selection tính hạng quần thể đầu tiên và sau đó mọi NST nhận lại giá trị thích nghi được định nghĩa bởi hạng của chúng.
NST tồi nhất sẽ có độ thích nghi là 1, NST tồi thứ hai là 2 etc. và NST tốt nhất sẽ có độ thích nghi là N (Số nhiễm sắc
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