Link tải luận văn miễn phí cho ae Kết Nối
MỞ ĐẦU........................................................................................................7
Chương 1. THUẬT GIẢI DI TRUYỀN ......................................................8
1.1. Tổng quan về thuật giải di truyền [2] .........................................................8
1.1.1. Thuật giải di truyền là gì?.......................................................................8
1.1.2. Lịch sử phát triễn của giải thuật di truyền...............................................9
1.1.3. Từ ngẫu nhiên đến thuật giải di truyền .................................................10
1.1.4. Một số ứng dụng nổi bật của thuật giải di truyền..................................12
1.2. Các nguyên tắc cơ bản của thuật giải di truyền [1]..................................14
1.2.1. Những tính chất cơ bản của thuật giải di truyền....................................14
1.2.2. Các bước trong việc áp dụng thuật giải di truyền..................................18
1.2.3. Các phương pháp mã hoá trong thuật giải di truyền..............................19
1.2.4. Một vài ví dụ minh hoạ ........................................................................41
1.2.5. Kết Luận ..............................................................................................52
1.3. Các giai đoạn cần thực hiện để giải quyết bài toán bằng thuật giải di
truyền ................................................................................................................54
1.3.1. Mối liên hệ giữa thuật giải di truyền và sự tiến hoá ..............................54
1.3.2. Những tính chất quan trọng của thuật giải di truyền .............................56
1.3.3. Một số vấn đề liên quan đến thuật giải di truyền?.................................57
Chương 2. ỨNG DỤNG GIẢI THUẬT DI TRUYỀN ĐỂ GIẢI CÁC BÀI
TOÁN TỐI ƯU NHIỀU BIẾN.................................................................... 59
2.1. Bài toán tối ưu. .......................................................................................59
2.1.1. §Æt vÊn ®Ò. ............................................................................59
2.1.2 Một số ví dụ về bài toán tối ưu..............................................................60
2.1.3. Một số ứng dụng nổi bật của bài toán tối ưu.........................................62
2.2. Ứng dụng giải thuật di truyền để giải các bài toán tối ưu nhiều
biến [2]. ............................................................................................................65
2.2.1. Đặt vấn đề............................................................................................65
2.2.2. Biễu diễn các biến bằng véc tơ nhị phân..............................................65
2.2.3. Toán tử chọn cá thể (select)..........................................................66
2.2.4. Toán tử lai ghép (cross over) ........................................................67
2.2.5. Toán tử đột biến (mutation) ...........................................................67
2.2.7. Bài toán cực tiểu hàm f với n biến liên tục ...........................................69
Bài toán 1: Bài toán cực tiểu hàm với N biến [2] ..................................106
2.2.6. Hàm thích nghi (fitness)..................................................................68
Bài toán 2: Travelling Salesman Problem(TSP) ....................................111
KẾT LUẬN................................................................................................ 120
TÀI LIỆU THAM KHẢO......................................................................... 121
MỞ ĐẦU
Từ vài thập niên trở lại đây, với những tác động mạnh mẽ của các tiến bộ
trong công nghệ phần cứng và truyền thông, các hệ thống dữ liệu phục vụ cho các
lĩnh vực kinh tế - xã hội đã phát triển bùng nổ, Vì vậy, tui chọn hướng nghiên cứu
"Ứng dụng của thuật giải di truyền để giải các bài toán tối ưu nhiều biến" làm đề tài
nghiên cứu cho luận văn của mình. Ngoài phần mở đầu và kết luận, cấu trúc nội
dung của luận văn bao gồm có 3 chương:
Chương 1: Trình bày tổng quan về giải thuật di truyền, trả lời câu hỏi “giải
thuật di truyền là gì?”. Trình bày những nét chính về lịch sử phát triển của giải
thuật di truyền và những ứng dụng nổi bật của giải thuật di truyền trong các lĩnh
vực khoa học kỹ thuật và cuộc sống. Bên cạnh đó giới thiệu các nguyên tắc cơ bản
của thuật giải di truyền. Tính chất cơ bản của thuật giải di truyền, các bước trong
việc áp dụng thuật giải di truyền, các phương pháp hoá của thuật giải di truyền và
một số ví dụ cụ thể. Cũng trong chương này sẽ giải thích một số thắc mắc liên quan
đến thuật giải di truyền và trình bày mối liên hệ giữa giải thuật di truyền và sự tiến
hoá.
Chương 2: trình bày những nét tổng quan nhất về bài toán tối ưu. Trả lời câu
hỏi “ bài toán tối ưu là gì?” Nêu lên một số ứng dụng nổi bật của bài toán tối ưu,
giới thiệu các phương pháp giải các bài toán tối ưu và đưa ra một số ví dụ về bài
toán tối ưu. Trình bày về ứng dụng của giải thuật di truyền để giải các bài toán tối
ưu nhiều biến. Trình bày cách biểu diễn các biến bằng véc tơ nhị phân, toán tử chọn
cá thể, toán tử lai ghép, toán tử đột biến, hàm thích nghi. Trình bày về thuật giải để
giải bài toán cực tiểu hàm f với n biến liên tục.
Chương 3: Phân tích và cài đặt thử nghiệm . Phần kết luận trình bày tóm tắt
về các nội dung thực hiện trong luận văn, đồng thời đưa ra các vấn đề nghiên cứu
tiếp cho tương lai.

Chương 1.
THUẬT GIẢI DI TRUYỀN
1.1. Tổng quan về thuật giải di truyền [2]
1.1.1. Thuật giải di truyền là gì?
Trong sinh hoạt hàng ngày, thường gặp nhiều vấn đề từ đơn giản đến phức tạp.
Có những vấn đề liên quan đến sinh hoạt cá nhân như chọn trường cho con em, tìm
lộ trình ngắn nhất để đi làm mỗi ngày hay những vấn đề liên quan đến công việc
tại cơ quan như: hoạch định chương trình chạy máy để tận dụng khả năng các dụng
cụ, đảm bảo chất lượng và thoả mãn yêu cầu của khách hàng...
Để giải quyết vấn đề, ở nhiều trường hợp, chúng ta có vô số giải pháp nhưng
không có giải pháp vạn năng theo nghĩa chúng có thể giải mọi lớp bài toán với hiệu
quả cao, có những trường hợp quá phức tạp không có giải pháp nào trước mắt hay
không biết phải bắt đầu tìm kiếm từ đâu.
Để giải quyết vấn đề thường dựa vào các cách sau đây:
1. Dựa trên các công thức toán học hay những định luật khoa học (tiếp cận
chính xác).
2. Dựa theo ý kiến của các chuyên gia lĩnh vực (tiếp cận kinh nghiệm).
3. Dựa theo sự tiến hoá, bắt chước các qui trình thích nghi và tiến hoá của sinh
giới nói chung.
cách dựa trên các công thức toán học hay những định luật khoa học
thường cho những đáp số chính xác. Tuy nhiên yếu điểm chính của nó là phải tìm ra
công thức hay giả tưỏng những điều kiện hoạt động cho giống với thực tế, điều này
không thể thực hiện một cách dễ dàng và nhanh chóng.
Trong hơn 20 năm qua, lĩnh vực trí tuệ nhân tạo đã được sử dụng để giúp giải
quyết vấn đề. Nguyên tắc cơ bản của cách này là kết hợp kiến thức của các
chuyên gia với chương trình tin học để dùng máy tính thay con người giải quyết vấn
đề một cách khôn ngoan. Nhiều chương trình tin học như Mycin, Prospector v.v…
đã thành công trong một số lĩnh vực cụ thể; tuy nhiên đối với những vấn đề chưa hề
xảy ra, hệ chuyên gia không thể giúp giải quyết được vấn đề. Nhược điểm quan
trọng nhất của hệ chuyên gia là khi thu thập kiến thức của các chuyên gia lĩnh vực,
chúng ta không có được những ý kiến trung thực có thể vì các chuyên gia thiếu tinh

thần hợp tác hay cũng có thể do kỹ thuật thu nhập không thích nghi. Do đó kể từ
những năm 90, thế kỉ 20, hệ chuyên gia không còn là kỹ thuật thích hợp nhất để giải
quyết vấn đề. Từ đấy, khuynh hướng trở về với bản thể con người được xem là cứu
cánh để giải quyết vấn đề.
Trong những năm 70, Mạng nơron nhân tạo, Logic mờ, cùng với Thuật giải di
truyền được nghiên cứu và áp dụng thành công trong việc giải quyết các trường hợp
phức tạp.
Nhìn chung con người và sinh vật đều phải tiến hoá để thích nghi với hoàn
cảnh. Vào thời kỳ đồ đá con người phải sống trong hang núi và dùng các dụng cụ
thô sơ. Những bộ lạc du mục phải biết sống cho thích nghi với thời tiết và địa
phương mà họ tạm cư. Sang thời đại tin học, mọi sinh hoạt đều diễn ra quanh máy
vi tính nhiệm màu.
Các nhà khảo cổ đã tìm ra những chứng tích của các loài khủng long sống hơn
triệu triệu năm trên quả đất này. Vào thời đó nhiệt độ của địa cầu còn khá nóng nên
mọi sinh vật phải có da dày, chân cao để chạy nhanh. Tiến hoá cho thích nghi với
điều kiện của môi trường chung quanh để tồn tại và phát triển là chứng cớ hiển
nhiên mà con người và sinh vậtt đã phải thực hiện.
Tiến hoá cho thích nghi không có nghĩa là luôn luôn tìm ra giải pháp
tuyệt đối cho vấn đề, nhưng có thể chỉ là tương đối trong điều kiện cho phép.
1.1.2. Lịch sử phát triễn của giải thuật di truyền
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, thế kỉ XX. A.S. Fraser là người đầu tiên đã nêu lên sự tương đồng giữa
sự tiến hoá của sinh vật và chương trình tin học giả tưởng về GA. Tuy nhiên chính
John Henry Holland, đại học Michigan, mới là ngưòi triển khai ý tưởng và phương
thức giải quýêt vấn đề dựa theo sự tiến hoá của con người. Ông bắt đầu bằng những
bài giảng và bài báo, sau đó đúc kết các ý tưởng thành sách: Adaptation in Natural
and Artificial Systems, xuất bản năm 1975. J.H. Holland được xem là “người khai
sinh “ của học thuyết Thuật giải di truyền. Trong giai đoạn đầu, thập niên 70 và 80,
thế kỉ XX, phần lớn các nhà nghiên cứu và ứng dụng của GA đều được đào tạo tại
đại học Michigan, và dưới sự hướng dẫn của J.H. Holland. J.H. Holland và một số
đồng nghiệp như Kenneth De Jong, David E. Goldberg đã dần dần xây dựng nền tảng lý thuyết và thực hiện các áp dụng của GA để giải quýêt các vấn đề phức tạp
trong thực tế.
Tạp chí đầu tiên về lý thuyết và ứng dụng của GA là nguyệt san Evulutionary
Computation (1993) do Kenneth De Jong chủ biên, ngoài ra còn có nguyệt san AI
Expert, Artificial Intelligent cũng thường có bài đề cập về GA.
Tuy chỉ mới được hình thành cách đây chưa đầy 25 năm, GA đã có được cơ sở
toán học vững chắc về lý thuyết và số lượng những áp dụng ngày càng gia tăng bao
gồm nhiều lĩnh vực khác nhau.
GA đã kết hợp với các kỹ thuật thuộc lĩnh vực trí tuệ nhân tạo như Expert
Systems (Hệ chuyên gia), Mạng nơron nhân tạo (Artificial Neural Network) và
Lôgic mờ (Fuzzy Logic) nhằm tìm giải pháp tối ưu cho những vấn đề phức tạp mà
cách cổ điển đã không giải quýêt thoả đáng.
GA được ứng dụng trong nhiều lĩnh vực khác nhau, từ khoa học tự nhiên đến
khoa học nhân văn, từ kỹ thuật sang thương vụ và kinh tế- tài chính. Nhìn chung,
những ứng dụng này có thể chia làm ba nhóm chính:
 Tìm mô hình tối ưu. Tìm kiếm và tối ưu hoá giải pháp là đề tài thích hợp
nhất của GA.
 Hoạch định quy trình sản xuất, lộ trình chuyển vận, cách bố trí các bộ phận
trong môi trường. Những ứng dụng loại này được dùng trong ngành giao
thông, chế tạo sản phẩm, tiếp thị v.v…
 Chọn lựa các nhóm hay thành phần trong một tổ chức.
Chúng ta cũng có thể sắp xếp các ứng dụng theo lĩnh vực như: quản trị, kinh
tế- tài chính, kỹ thuật, nghiên cứu và phát triển.
1.1.3. Từ ngẫu nhiên đến thuật giải di truyền
Xét bài toán tìm mật mã để mở khoá với mật mã là một con số thập phân có
30 chữ số với giả sử rằng ổ khoá này chỉ có thể mở bằng một mật mã duy nhất. Đối
với bài toán này không gian tìm kiếm là 1030, nghĩa là sẽ có tổng cộng 1030 mật mã
khác nhau. Để giải quyết vấn đề này ta thường chỉ nghĩ đến hai phương pháp : Vét
cạn toàn bộ hay thử ngẫu nhiên các mật mã. Ta phát sinh ( ngẫu nhiên hoặc
tuâầntự theo một quy tắc duyệt nào đó) các mã khoá rồi thử xem mật mã này có thể
là mã khoá đúng không. Với phương pháp này, để có được một mật mã với khả
năng mở được ổ khoá là trên 50%, ta đã phải phát sinh nhiều hơn 1030/2 mật mã.
Con số này quá lớn, trên thực tế, nếu dùng siêu máy tính Cray và giả sử rằng cứ
mỗi một phần tỷ giây thì máy này có thể phát sinh và thử nghiệm được một mật mã
Trình bày tổng quan về giải thuật di truyền, trả lời câu hỏi "giải thuật di truyền là gì?", giới thiệu các nguyên tắc cơ bản của thuật giải di truyền, các giai đoạn cần thực hiện để giải quyết bài toán bằng thuật giải di truyền. Trình bày những nét tổng quan về bài toán tối ưu; nêu một số ứng dụng của bài toán tối ưu, giới thiệu các phương pháp giải các bài toán tối ưu. Ứng dụng của giải thuật di truyền để giải các bài toán tối ưu nhiều biến. Các cách biểu diễn các biến bằng véc tơ nhị phân, toán tử chọn cá thể, toán tử lai ghép, toán tử đột biến, hàm thích nghi; thuật giải để giải bài toán cực tiểu hàm f với n biến liên tục. Phân tích và cài đặt thử nghiệm
Luận văn ThS. Công nghệ thông tin -- Trường Đại học Công Nghệ. Đại học Quốc gia Hà Nội, 2008


3J8hV5220u8f6NC

---