Tính toán tiến hoá sử dụng giải thật di truyền

Từ VLOS
Bước tới: chuyển hướng, tìm kiếm
TÍNH TOÁN TIẾN HOÁ SỬ DỤNG GIẢI THUẬT DI TRUYỀN


LỜI NÓI ĐẦU[sửa]

Tính toán tiến hóa (Evolutionary computation): ứng dụng các khái niệm sinh học như quần thể, biến dị và đấu tranh sinh tồn để sinh các lời giải ngày càng tốt hơn cho bài toán. Các phương pháp này thường được chia thành các thuật toán tiến hóa (ví dụ thuật toán gien) và trí tuệ bầy đàn (swarm intelligence) (chẳng hạn hệ kiến).
Giải thuật di truyền là một kỹ thuật của khoa học máy tính nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial optimization). Giải thuật di truyền là một phân ngành của giải thuật tiến hóa vận dụng các nguyên lý của tiến hóa như di truyền, đột biến, chọn lọc tự nhiên, và trao đổi chéo.
Giải thuật di truyền thường được ứng dụng nhằm sử dụng ngôn ngữ máy tính để mô phỏng quá trình tiến hoá của một tập hợp những đại diện trừu tượng (gọi là những nhiễm sắc thể) của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn đề. Tập hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
Thông thường, những giải pháp được thể hiện dưới dạng nhị phân với những chuỗi 0 và 1, nhưng lại mang nhiều thông tin mã hóa khác nhau. Quá trình tiến hóa xảy ra từ một tập hợp những cá thể hoàn toàn ngẫu nhiên ở tất cả các thế hệ. Trong từng thế hệ, tính thích nghi của tập hợp này được ước lượng, nhiều cá thể được chọn lọc định hướng từ tập hợp hiện thời (dựa vào thể trạng), được sửa đổi (bằng đột biến hoặc tổ hợp lại) để hình thành một tập hợp mới. Tập hợp này sẽ tiếp tục được chọn lọc lặp đi lặp lại trong các thế hệ kế tiếp của giải thuật. Sự tính toán tiến hoá sử dụng giải thuật di truyền sẽ đem lại một số điều mới, dựa vào máy tính, dự vào cơ chế chọn lọc và sinh sản tự nhiên mà chúng ta có thể phát triển tính toán mềm hay trí tuệ tính toán nhằm nghiên cứu mô hình tính toán mô phỏng hoạt động của con người hay sự tiến hoá tự nhiên. Sự tính toán này dựa trên các kỹ thuật cơ bản: logic mờ (Fuzzy Logic), mạng nơron nhân tạo (Neural Network), giải thuật di truyền (Genetic Algorithm) và mô phỏng tôi luyện (Simulated Annealing).

Chương 1: Tổng quan về giải thuật di truyền[sửa]

1.1. Giải thuật di truyền đơn giản[sửa]

1.1.1. Mã hoá[sửa]

1.1.2. Các toán tử di truyền[sửa]

1.2. Nền tảng toán học của giải thuật di truyền[sửa]

1.3. Giải thuật di truyền mã hoá số thực[sửa]

1.3.1. Toán tử chọn lọc[sửa]

1.3.2. Toán tử lai ghép[sửa]

1.3.3. Toán tử đột biến[sửa]

1.3.4. Toán tử tái tạo[sửa]

1.1.3. Sơ đồ chung cho giải thuật di truyền[sửa]

Chương 2. Tính toán tiến hoá[sửa]

2.1. Sự thích nghi trong tính toán tiến hoá[sửa]

2.2. Tác động của kích cỡ quần thể trong giải thuật di truyền mã hoá số thực[sửa]

2.2.1. Kích cỡ quần thể và số lần lặp[sửa]

2.3. Điều chỉnh tham số của toán tử lai ghép[sửa]

2.3.1. Phân tích các dạng lai ghép kinh điển[sửa]

2.3.2. Toán tử lai ghép SBX[sửa]

2.3.3. Điều kiện thành công của toán tử lai ghép[sửa]

2.4. Cơ cấu lựa chọn thích nghi toán tử lai ghép[sửa]

Chương 3. Một số ứng dụng tính toán tiến hoá[sửa]

3.1. Bài toán đa mục tiêu[sửa]

3.2. Bài toán tìm đường đi cho Robot[sửa]

TÀI LIỆU THAM KHẢO[sửa]

Tiếng Việt
[1]. Nguyễn Đình Phúc, Lập trình tiến hoá, NXB Giáo dục, 2001.
[2]. Bùi Công Cường, Nguyễn Doãn Phước, Hệ mờ mạng nơron và ứng dụng, NXB Khoa học và kỹ thuật, 2001.
[3]. Hoàn Kiếm, Lê Hoàng Thái, Giải thuật di truyền, cách giải tự nhiên các bài toán trên máy tính, NXB Giáo dục, 2000.
[4]. Vũ Xuân Mạnh, Phát triển một số kỹ thuật trong tính toán mềm, Luận án Tiến sĩ, Viện công nghệ thông tin - Hà Nội, 2006.

[5]. Bách khoa toàn thư mở, Http://vi.wikipedia.org, 2006.

Tiếng Anh
[6]. John H. Holland, Computer programs that "evolve" in ways that resemble natural selection can solve complex problems even their creators do not fully understand, http://www.econ.iastate.edu/tesfatsi/holland.GAIntro.htm, 2006.
[7]. Jean-Philippe Rennard, Ph.D. Genetic Algorithm Viewer: Demonstration of a Genetic Algorithm. http://www.rennard.org/alife/english/gavintrgb.html, May 2000.
[8]. Adam Marczyk, Genetic Algorithms and Evolutionary Computation, 2004.

Liên kết đến đây