Tổng quan luận án
Công trình nghiên cứu giải quyết bài toán tối ưu hóa trong bối cảnh sự phát triển mạnh mẽ của công nghệ phần cứng và truyền thông từ những thập niên cuối thế kỷ XX, dẫn tới sự bùng nổ các hệ thống dữ liệu phục vụ kinh tế - xã hội. Nhu cầu xử lý các bài toán tối ưu hóa quy mô lớn, nhiều chiều và không gian trạng thái phức tạp đặt ra yêu cầu cấp thiết về các thuật toán tìm kiếm hiệu quả, vượt qua các giới hạn của phương pháp giải tích cổ điển và hệ chuyên gia.
Thông tin hành chính của luận án được xác định như sau:
- Tên đề tài: Ứng dụng thuật giải di truyền các bài toán hàm mục tiêu nhiều biến (trong phần Mở đầu tác giả xác định 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").
- Tác giả: Lê Chí Luận.
- Học vị/Loại tài liệu: Luận văn Tiến sỹ Công nghệ thông tin.
- Mã số chuyên ngành: 101 10.
- Người hướng dẫn khoa học: PGS.TSKH.
- Cơ sở đào tạo: Trường Đại học Kinh tế – Đại học Quốc gia Hà Nội.
- Năm hoàn thành: 2008 tại Hà Nội.
Mục tiêu nghiên cứu của luận án gồm ba nội dung chính:
- Hệ thống hóa cơ sở lý thuyết, nguyên lý vận hành, các tính chất cơ bản, kỹ thuật biểu diễn dữ liệu và hệ thống các toán tử của Thuật giải di truyền (Genetic Algorithms - GA).
- Nghiên cứu phương pháp luận và thuật toán ứng dụng GA để giải quyết các bài toán tối ưu hàm mục tiêu nhiều biến liên tục cũng như các bài toán tối ưu tổ hợp phức tạp.
- Thiết kế cấu trúc dữ liệu, thuật toán và cài đặt thử nghiệm các hàm mô phỏng toán tử GA trên máy tính để kiểm chứng tính hiệu quả trong việc tìm kiếm lời giải tối ưu.
Đối tượng và phạm vi nghiên cứu:
- Đối tượng nghiên cứu: Thuật giải di truyền (GA), các cấu trúc mã hóa cá thể (chuỗi nhị phân, mảng byte nén, mảng integer, chuỗi số thực, cấu trúc cây), các toán tử di truyền (chọn lọc, lai ghép, đột biến, tạo sinh), cơ chế đánh giá hàm thích nghi và các bài toán tối ưu hàm mục tiêu nhiều biến.
- Phạm vi nghiên cứu: Luận án tập trung vào lớp bài toán tối ưu hóa hàm mục tiêu với $N$ biến liên tục và các bài toán tối ưu tổ hợp kinh điển (bài toán lập lịch, bài toán lập thời khóa biểu, bài toán người bán hàng - Travelling Salesman Problem). Thời điểm nghiên cứu và bảo vệ luận án là năm 2008.
Tổng quan tài liệu và vị trí của luận án
Luận án điểm lại lịch sử hình thành và phát triển của các phương pháp giải quyết vấn đề và tối ưu hóa qua các giai đoạn:
- Phương pháp giải tích và định luật khoa học chính xác: Cho kết quả chính xác nhưng đòi hỏi phải thiết lập công thức và giả định điều kiện hoạt động gần với thực tế, khó thực hiện nhanh chóng đối với các hệ thống phức tạp.
- Hệ chuyên gia (Expert Systems): Phát triển mạnh từ thập niên 1970 - 1980 với các hệ thống tiêu biểu như Mycin, Prospector. Tuy nhiên, hệ chuyên gia bộc lộ nhược điểm khi gặp các tình huống chưa từng xảy ra và phụ thuộc vào việc thu thập tri thức chuyên gia vốn có thể thiếu trung thực hoặc kỹ thuật thu thập không thích ứng. Từ thập niên 1990, khuynh hướng quay trở lại mô phỏng quá trình thích nghi sinh học được chú trọng.
- Lịch sử phát triển của Thuật giải di truyền (GA):
- Thập niên 1950 - 1960: Fraser là người đầu tiên nêu lên sự tương đồng giữa quá trình tiến hóa sinh vật và chương trình tin học giả tưởng về GA.
- John Henry Holland (Đại học Michigan): Được xem là người khai sinh học thuyết Thuật giải di truyền, đúc kết hệ thống lý thuyết qua công trình sách Adaptation in Natural and Artificial Systems (xuất bản năm 1975).
- Kenneth De Jong và David E. Goldberg (Đại học Michigan): Cùng Holland xây dựng nền tảng lý thuyết và ứng dụng thực tiễn của GA. Kenneth De Jong là chủ biên đầu tiên của nguyệt san Evolutionary Computation (ra đời năm 1993).
- David E. Goldberg: Ứng dụng thành công GA trong kỹ thuật với đề tài Computer Aided Gas Pipeline Operation using Genetic Algorithms and Rule learning trên máy tính Apple II bằng ngôn ngữ Pascal, tối ưu hóa hệ thống phân phối mạng lưới đường ống dầu khí phức tạp.
- Chuck Karr: Ứng dụng lý thuyết GA trong luận án tiến sĩ kết hợp với Lôgic mờ (Fuzzy Logic) để chế tạo thiết bị đo lường trong khai thác mỏ, kiểm soát độ pH môi trường và điều khiển trực thăng.
- General Electric Co. (GE): Xây dựng chương trình Engineous dựa trên GA để tối ưu hóa thiết kế động cơ máy bay Boeing, cánh quạt tuabin nhà máy điện nguyên tử; Naval Surface Weapons Center (Bethesda, Maryland) sử dụng Engineous thiết kế cánh quạt tàu ngầm.
- Công ty Adolph Coors Company (ACC): Ứng dụng GA giải quyết bài toán điều độ sản xuất với hơn 500 mặt hàng và 16 dây chuyền sản xuất thay thế cơ chế "đến trước nhận trước" (First Come First Serve).
Khoảng trống nghiên cứu được luận án giải quyết là việc khắc phục hạn chế của thuật toán tìm kiếm leo núi (Hill-climbing) – vốn dễ bị mắc kẹt tại các đỉnh núi thấp (cực trị địa phương) – và sự bế tắc của phương pháp vét cạn trên không gian tìm kiếm cực lớn (ví dụ không gian $10^{30}$ mật mã mà siêu máy tính Cray thử 1 tỷ mã/giây cũng cần thời gian tương đương tuổi trái đất). Luận án xây dựng phương pháp luận hoàn chỉnh từ biểu diễn dữ liệu nhị phân/thực nén, xác định độ thích nghi linh hoạt (kết hợp độ phân ly) đến tối ưu hóa hàm mục tiêu nhiều biến.
Cơ sở lý thuyết và phương pháp nghiên cứu
Luận án dựa trên khung lý thuyết tiến hóa sinh học tự nhiên, trong đó quá trình tiến hóa duy trì tính tối ưu thông qua sinh sản, di truyền, đột biến và chọn lọc tự nhiên. GA là thuật toán tìm kiếm ngẫu nhiên (stochastic), làm việc trực tiếp trên các chuỗi biểu diễn giải pháp mà không phụ thuộc vào đạo hàm hay chi tiết hàm số.
Thuật ngữ chuyên ngành cốt lõi trong luận án:
| Từ tiếng Anh |
Từ viết tắt |
Thuật ngữ tiếng Việt |
Định nghĩa / Ý nghĩa |
| Genetic Algorithms |
GA |
Thuật giải di truyền |
Thuật toán tìm kiếm, tối ưu hóa mô phỏng quá trình tiến hóa sinh học |
| Artificial Neural Network |
ANN |
Mạng nơron nhân tạo |
Mô hình tính toán mô phỏng hệ thần kinh sinh học |
| Fuzzy Logic |
- |
Lôgic mờ |
Lý thuyết xử lý thông tin không chắc chắn hoặc mập mờ |
| Expert Systems |
- |
Hệ chuyên gia |
Chương trình tin học kết hợp tri thức chuyên gia giải quyết vấn đề |
| Chromosome |
- |
Nhiễm sắc thể |
Chuỗi mã hóa biểu diễn một giải pháp/lời giải |
| Genotype |
- |
Kiểu gen |
Tập hợp các giải pháp được duyệt xét để chọn đáp số thích nghi |
| Population |
- |
Quần thể |
Tập hợp toàn bộ các giải pháp trong một thế hệ |
| Fitness / Fitness function |
- |
Giá trị / Hàm thích nghi |
Tiêu chuẩn đánh giá độ tốt và khả năng sống sót của cá thể |
| Crossover |
- |
Lai ghép |
Phép biến hóa kết hợp các đoạn gen cha mẹ để tạo cá thể con |
| Mutation |
- |
Đột biến |
Phép biến hóa thay đổi ngẫu nhiên một hoặc một số gen |
| Reproduction |
- |
Tạo sinh / Tái sinh |
Quá trình sao chép cá thể sang thế hệ sau dựa vào độ thích nghi |
| Hill-climbing |
- |
Tìm kiếm leo núi |
Phương pháp tìm kiếm cục bộ hướng tới độ cao/độ tốt lớn hơn |
Một thuật giải di truyền hoàn chỉnh trong luận án gồm 5 thành phần:
- Cấu trúc dữ liệu biểu diễn không gian lời giải.
- Phương pháp khởi tạo quần thể ban đầu $P(0)$.
- Hàm định nghĩa độ thích nghi $eval(.)$ đóng vai trò môi trường đánh giá.
- Các phép toán di truyền (chọn lọc, lai ghép, đột biến, tạo sinh).
- Các tham số điều khiển (kích thước quần thể $N$, xác suất lai ghép $p_c$, xác suất đột biến $p_m$).
Phương pháp luận biểu diễn dữ liệu và các toán tử:
- Biểu diễn nhị phân:
- Mảng Byte: Mỗi byte lưu 1 bit, khai báo
ARRAY[0..N-1] OF BYTE (Pascal) hoặc unsigned char Cgen[N] (C). Truy xuất nhanh nhưng tốn bộ nhớ gấp 8 lần.
- Mảng Byte nén: Mỗi byte chứa 8 bit. Vị trí byte chứa bit thứ $n$ là
n SHR 3 (hoặc n >> 3), vị trí bit trong byte là n AND 7 (hoặc n & 7). Thao tác trích và gán bit thực hiện thông qua các phép toán logic AND, OR, NOT.
- Mảng Integer nén: Sử dụng độ dài từ máy tính (2 byte trong DOS, 4 byte trong Windows 9x như Delphi, Visual C++) kết hợp hàm
sizeof() để tăng tốc độ truy xuất.
- Biểu diễn số thực qua chuỗi nhị phân: Số thực $x \in [\min, \max]$ mã hóa bằng chuỗi nhị phân $A$ dài $L$ bit. Độ chính xác (bước lượng hóa) $g = \frac{\max - \min}{2^L - 1}$. Giá trị giải mã:
$$X = \min + \text{Decimal}(\langle A \rangle) \times g$$
trong đó $\text{Decimal}(\langle A \rangle) = \sum_{i=0}^{L-1} a_i 2^i$.
- Biểu diễn chuỗi số thực: Khai báo
ARRAY[0..N-1] OF real (Pascal) hoặc float Cgen[N] (C).
- Cấu trúc cây: Cấu trúc cây 2 nhánh biểu diễn các giải pháp có cấu trúc phân cấp.
- Phương pháp xác định độ thích nghi:
- Độ thích nghi tiêu chuẩn: Với quần thể $N$ cá thể và hàm mục tiêu $G(a_i)$:
$$F(a_i) = \frac{G(a_i)}{\sum_{j=1}^N G(a_j)}$$
- Độ thích nghi xếp hạng: Khắc phục hiện tượng di truyền cục bộ khi một cá thể vượt trội hút quần thể:
$$F(i) = p \times (1 - p)^{i - 1} \quad (p \in [0, 1])$$
- Độ thích nghi xếp hạng dựa trên độ phân ly: Đo lường độ phân kỳ của cá thể đối với toàn quần thể để duy trì tính đa dạng:
$$P(a_i) = \sum_{j=1, j \neq i}^N \frac{1}{|G(a_i) - G(a_j)|}$$
- Các toán tử lai ghép và tạo sinh:
- Lai ghép đơn điểm: Chọn ngẫu nhiên vị trí cắt $k \in [2, N-1]$ để tráo đổi đoạn gen.
- Lai ghép đa điểm: Chọn $m$ vị trí cắt $k_1, k_2, \dots, k_m$, giữ nguyên các đoạn vị trí lẻ và hoán đổi các đoạn vị trí chẵn.
- Lai ghép mặt nạ: Sử dụng chuỗi nhị phân mặt nạ $m_A$ và $m_B$ ($m_A = \text{NOT } m_B$) để trích xuất gen.
- Tạo sinh đường (áp dụng cho chuỗi số thực): $C_i = \min(A_i, B_i) + \alpha |B_i - A_i|$ với $\alpha \in [0, 1]$ hoặc $\alpha \in [-d, 1+d]$ ($d \ge 0$).
- Tạo sinh tức thời: Sử dụng dãy hệ số $\alpha_i \in [-d, 1+d]$ độc lập cho từng thành phần gen.
- Các toán tử đột biến:
- Đột biến nhị phân: Đảo bit $0 \leftrightarrow 1$ tại vị trí ngẫu nhiên với xác suất $p_m$.
- Đột biến trị thực: Giá trị mới $A' = A + S \times \text{range} \times \text{delta}$, trong đó $S \in {-1, 1}$ (xác suất 0.5), $\text{range} \le \text{độ lớn miền xác định} \times 0.1$, và $\text{delta} = \sum_{i=1}^{20} a_i 2^{-i}$ ($a_i = 1$ với xác suất $1/20$).
- Quy tắc chọn xác suất đột biến: Xác suất $p_m$ tỷ lệ nghịch với kích thước gen, giá trị phổ biến là $1/N$ (với $N$ là kích thước quần thể).
Nội dung chính theo từng chương
Chương 1: Trình bày tổng quan về giải thuật di truyền
Chương 1 làm rõ bản chất, lịch sử phát triển và các nguyên tắc nền tảng của GA. Phân tích sự chuyển dịch từ tìm kiếm ngẫu nhiên, tìm kiếm leo núi sang tìm kiếm tiến hóa đa cá thể kế thừa kinh nghiệm giữa các thế hệ. Chương này chi tiết hóa các mô hình mã hóa, kỹ thuật tính độ thích nghi, các toán tử di truyền và đưa ra các bài toán minh họa cụ thể.
Bài toán minh họa tìm nghiệm phương trình $X^2 = 64$ với hàm thích nghi xác định là $1000 - |X^2 - 64|$ trên quần thể 4 cá thể nhị phân 5 bit:
| Thứ tự |
Dãy nhị phân |
Giá trị thập phân |
Giá trị $X^2 - 64$ |
Hệ số thích nghi ban đầu |
Trạng thái sau lai ghép |
Giá trị thập phân mới |
Hệ số thích nghi mới |
| 1 |
00100 |
4 |
-48 |
952 |
Giữ nguyên |
4 |
952 |
| 2 |
10101 |
21 |
377 |
623 |
Loại bỏ |
- |
- |
| 3 |
01010 |
10 |
36 |
964 |
Giữ nguyên |
10 |
964 |
| 4 |
11000 |
24 |
512 |
488 |
Loại bỏ |
- |
- |
| Con 1 |
01000 |
8 |
0 |
- |
Lai tạo từ (4, 10) |
8 |
1000 |
| Con 2 |
00110 |
6 |
-28 |
- |
Lai tạo từ (4, 10) |
6 |
968 |
Kết quả sau 1 thế hệ lai ghép tại vị trí cắt giữa bit thứ 2 và 3 đã tìm ra nghiệm tối ưu tuyệt đối $X = 8$ (chuỗi 01000) đạt độ thích nghi 1000.
Chương 1 cũng trình bày Lý thuyết lập lịch (Scheduling) và ứng dụng GA vào bài toán lập thời khóa biểu:
- Bài toán lập lịch sửa chữa ô tô: Cho $n$ ô tô sẵn sàng tại thời điểm $r_i = 0$, mỗi ô tô có hạn định hoàn thành $d_i$ và thời gian sửa chữa $t_i$. Mục tiêu tìm thứ tự xử lý không ngắt quãng để tối đa hóa số lượng ô tô hoàn thành đúng hạn ($c_i \le d_i$).
- Bài toán lập thời khóa biểu: Lập lịch cho $K$ lớp, $D$ giáo viên, $V$ môn học trong 5 ngày/tuần, 6 tiết/ngày (tổng cộng 30 ca). Cấu trúc dữ liệu là ma trận kích thước $K \times 30$.
- Ràng buộc cứng (gán trọng số lỗi $0 - 1.000.000$): Một giáo viên chỉ dạy 1 lớp tại 1 thời điểm; mỗi lớp chỉ học 1 môn tại 1 thời điểm; các tiết của một môn tại một lớp phải do cùng một giáo viên phụ trách; một giáo viên dạy không quá 20 giờ/tuần.
- Ràng buộc mềm (gán trọng số lỗi $0 - 200.000$): Lớp có thể có giờ trống; lớp có thể học cùng một môn nhiều lần trong ngày; cân bằng giờ dạy giữa các giáo viên.
- Hàm thích nghi tổng hợp:
$$\text{Fitness} = (100 - X) + (20 - Y) + \text{bonus}$$
trong đó $X$ là tỷ lệ lỗi trung bình ràng buộc cứng, $Y$ là tỷ lệ lỗi trung bình ràng buộc mềm (nhân hệ số giảm 0.2). Kỹ thuật chọn lọc sử dụng cơ chế đấu loại (tournament).
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
Chương 2 trình bày tổng quan về bài toán tối ưu hóa đa biến, phân loại các phương pháp giải và thiết lập quy trình ứng dụng GA:
- Mô hình toán học: Biểu diễn các biến quyết định dưới dạng véc tơ nhị phân ghép nối từ các chuỗi con hoặc véc tơ số thực nhiều chiều.
- Thiết lập toán tử chuyên biệt: Xây dựng toán tử chọn lọc (
select), toán tử lai ghép (crossover), toán tử đột biến (mutation) và hàm thích nghi (fitness function) phù hợp với không gian tìm kiếm nhiều chiều.
- Bài toán 1: Bài toán cực tiểu hóa hàm số $f(x_1, x_2, \dots, x_N)$ với $N$ biến liên tục trên miền xác định cho trước.
- Bài toán 2: Bài toán người bán hàng (Travelling Salesman Problem - TSP), mô hình hóa hành trình đi qua các thành phố sao cho chi phí hoặc quãng đường là nhỏ nhất mà mỗi thành phố chỉ được đi qua đúng một lần.
Chương 3: Phân tích và cài đặt thử nghiệm
Chương 3 tập trung vào thiết kế kiến trúc phần mềm, xây dựng các module thuật toán và tiến hành thử nghiệm mô phỏng trên máy tính. Các cấu trúc hàm cốt lõi được xây dựng gồm:
| Tên hàm / Module |
Chức năng kỹ thuật trong thuật toán GA |
| Hàm khởi tạo giá trị ngẫu nhiên |
Tạo giá trị khởi tạo số học ngẫu nhiên cho các cá thể ban đầu |
| Hàm khởi tạo ngẫu nhiên (0 hoặc 1) theo xác suất |
Tạo chuỗi bit nhị phân cho các cá thể dựa trên phân bố xác suất |
| Hàm tính trị số thích nghi |
Đánh giá giá trị của từng cá thể qua hàm mục tiêu và ràng buộc |
Hàm chọn cá thể (select) |
Lựa chọn các cá thể có độ thích nghi cao vào tập sinh sản (chọn xén / đấu loại) |
Hàm mô phỏng toán tử đột biến (mutation) |
Thực hiện biến đổi gen nhị phân hoặc gen thực theo xác suất $p_m$ |
Hàm mô phỏng toán tử lai ghép (crossover) |
Thực hiện hoán đổi đoạn gen cha mẹ theo các điểm lai hoặc mặt nạ |
| Hàm khởi tạo quần thể |
Thiết lập quần thể thế hệ ban đầu $P(0)$ với kích thước ấn định |
| Hàm tạo sinh |
Thực hiện cơ chế sao chép cá thể thích nghi sang thế hệ tiếp theo |
Hàm tái tạo quần thể (reproduction) |
Tổng hợp các cá thể từ lai ghép, đột biến và tạo sinh để xây dựng $P(t+1)$ |
| Hàm thể hiện các bước của Thuật giải di truyền |
Điều khiển toàn bộ vòng lặp tiến hóa cho đến khi thỏa mãn điều kiện dừng |
Chương 3 tiến hành thử nghiệm trên mô hình thiết bị thí nghiệm cân bằng, ghi nhận hình ảnh minh họa trạng thái thiết bị trước khi cân bằng và sau khi cân bằng tại trang 83, khẳng định khả năng hội tụ và tìm kiếm tham số điều khiển của thuật toán.
Kết quả và những đóng góp mới
Các đóng góp chính được tổng kết trong luận án:
- Về lý thuyết và thuật toán:
- Hệ thống hóa các phương pháp mã hóa dữ liệu trong GA, tối ưu hóa bộ nhớ và tốc độ xử lý thông qua kỹ thuật mảng byte nén và mảng integer nén tương thích với độ dài từ máy tính.
- Phân tích các mô hình đánh giá độ thích nghi, kết hợp độ thích nghi xếp hạng với độ phân ly cá thể nhằm ngăn ngừa hiện tượng hội tụ sớm vào các cực trị địa phương.
- Xây dựng mô hình toán học và thuật toán GA để giải quyết bài toán cực tiểu hóa hàm mục tiêu $N$ biến liên tục và bài toán tối ưu hóa tổ hợp (lập lịch, lập thời khóa biểu, TSP).
- Về thực tiễn và ứng dụng:
- Thiết kế và lập trình hoàn chỉnh bộ thư viện các hàm mô phỏng đầy đủ các toán tử di truyền (khởi tạo, chọn lọc, lai ghép đơn/đa điểm/mặt nạ, đột biến nhị phân/trị thực, tạo sinh đường/tức thời).
- Áp dụng thành công thuật toán vào giải quyết bài toán lập thời khóa biểu với hệ thống ràng buộc cứng và mềm nhiều mức, cũng như thực nghiệm thành công trên mô hình thiết bị cân bằng.
Hạn chế và hướng nghiên cứu tiếp
- Hạn chế: Bản chất của GA là thuật toán ngẫu nhiên (stochastic), kết quả tìm kiếm mang tính xấp xỉ và phụ thuộc vào việc lựa chọn các tham số điều khiển (kích thước quần thể $N$, xác suất lai ghép $p_c$, xác suất đột biến $p_m$) cũng như cách thức thiết lập hàm thích nghi. Đối với các bài toán có không gian ràng buộc quá chặt chẽ, việc xử lý vi phạm ràng buộc đòi hỏi chi phí tính toán lớn.
- Hướng nghiên cứu tiếp:
- Tiếp tục nghiên cứu mở rộng thuật toán cho các bài toán tối ưu hóa đa mục tiêu phức tạp trong thực tế.
- Nghiên cứu kết hợp GA với các kỹ thuật trí tuệ nhân tạo khác như Mạng nơron nhân tạo (ANN) và Lôgic mờ (Fuzzy Logic) nhằm nâng cao tốc độ hội tụ và độ chính xác của nghiệm tìm kiếm.
Giá trị tham khảo
Luận án là tài liệu tham khảo hữu ích cho:
- Nghiên cứu sinh, học viên cao học và sinh viên ngành Công nghệ thông tin, Khoa học máy tính, Toán tin ứng dụng và Hệ thống thông tin trong việc nghiên cứu các thuật toán tiến hóa và tính toán mềm.
- Giảng viên đại học làm tài liệu giảng dạy các chuyên đề về Tối ưu hóa, Trí tuệ nhân tạo, và Thuật toán nâng cao.
- Kỹ sư phần mềm và chuyên gia tối ưu hóa quan tâm đến kỹ thuật lập trình thao tác bit/byte tối ưu hiệu năng, phương pháp giải quyết bài toán lập lịch công việc, lập thời khóa biểu và bài toán người bán hàng.
Câu hỏi thường gặp
1. Tại sao GA khắc phục được hạn chế của thuật toán tìm kiếm leo núi (Hill-climbing)?
Thuật toán tìm kiếm leo núi thông thường chỉ duy trì một trạng thái tìm kiếm duy nhất theo nguyên tắc "càng leo càng cao", do đó rất dễ bị mắc kẹt tại các đỉnh núi thấp (cực trị địa phương) mà không thể xuống núi để tìm ngọn núi cao nhất. GA giải quyết nhược điểm này bằng cách duy trì một quần thể gồm nhiều cá thể (nhiều người leo núi cùng lúc) và tạo ra nhiều thế hệ liên tiếp; những cá thể thích nghi nhất sẽ truyền kinh nghiệm (thông qua lai ghép và đột biến) cho các thế hệ sau, giúp mở rộng không gian tìm kiếm và tăng khả năng đạt tới cực trị toàn cục.
2. Trong bài toán lập thời khóa biểu ở Chương 1, các ràng buộc và hàm thích nghi được thiết kế như thế nào?
Bài toán biểu diễn thời khóa biểu dưới dạng ma trận $K \times 30$ ($K$ lớp, 30 tiết/tuần). Các ràng buộc được chia thành:
- Ràng buộc cứng: Giáo viên không dạy trùng giờ, lớp không học trùng môn, môn học tại một lớp do một giáo viên phụ trách, giáo viên dạy tối đa 20 giờ/tuần (gán trọng số từ 0 đến 1.000.000).
- Ràng buộc mềm: Giờ trống của lớp, môn học lặp lại trong ngày, cân bằng số giờ dạy giữa các giáo viên (gán trọng số từ 0 đến 200.000).
Hàm thích nghi được xác định theo công thức $\text{Fitness} = (100 - X) + (20 - Y) + \text{bonus}$, với $X$ và $Y$ lần lượt là tỷ lệ lỗi trung bình của ràng buộc cứng và ràng buộc mềm.
3. Kỹ thuật mã hóa mảng byte nén được vận hành như thế nào trong chương trình?
Trong mảng byte nén, mỗi byte lưu trữ 8 bit của chuỗi nhị phân. Để truy xuất bit thứ $n$:
- Xác định vị trí byte: Sử dụng phép toán dịch phải
n SHR 3 (trong Pascal) hoặc n >> 3 (trong C).
- Xác định vị trí bit trong byte: Sử dụng phép chia lấy dư
n AND 7 (trong Pascal) hoặc n & 7 (trong C).
- Đọc/ghi bit: Dùng lệnh
CASE hoặc switch kết hợp với các phép toán logic trên bit (AND, OR, NOT) với các mặt nạ lũy thừa của 2 ($1, 2, 4, 8, 16, 32, 64, 128$). Kỹ thuật này giúp tiết kiệm 8 lần dung lượng bộ nhớ so với mảng byte thông thường.
4. Sự khác biệt giữa toán tử tạo sinh đường và tạo sinh tức thời là gì?
Cả hai toán tử đều áp dụng cho cá thể kiểu chuỗi số thực:
- Tạo sinh đường: Sinh cá thể con $C$ nằm trên đường thẳng nối giữa hai điểm cha mẹ $A$ và $B$ theo công thức $C_i = \min(A_i, B_i) + \alpha |B_i - A_i|$, sử dụng duy nhất một hệ số $\alpha \in [-d, 1+d]$ cho tất cả các thành phần gen.
- Tạo sinh tức thời: Mở rộng từ tạo sinh đường nhưng sử dụng một dãy các hệ số $\alpha_i \in [-d, 1+d]$ độc lập cho từng thành phần gen thứ $i$ theo công thức $C_i = \min(A_i, B_i) + \alpha_i |B_i - A_i|$.
5. Cơ chế tính độ thích nghi dựa trên độ phân ly có vai trò gì?
Cơ chế này tính toán giá trị phân ly $P(a_i) = \sum_{j=1, j \neq i}^N \frac{1}{|G(a_i) - G(a_j)|}$. Giá trị $P(a_i)$ càng bé thì cá thể càng có độ phân ly mạnh so với các cá thể khác trong quần thể. Bằng cách kết hợp hạng theo độ tốt $G(a_i)$ và hạng theo độ phân ly $P(a_i)$, thuật toán tạo điều kiện cho các cá thể khác biệt (nằm ở các vùng sinh thái xa) có cơ hội sống sót và phát triển, ngăn chặn hiện tượng quần thể bị đồng nhất hóa quá sớm dẫn tới di truyền cục bộ.
Kết luận
Luận án của tác giả Lê Chí Luận đã trình bày hệ thống cơ sở lý thuyết, các toán tử và giải pháp kỹ thuật biểu diễn dữ liệu của Thuật giải di truyền nhằm giải quyết các bài toán tối ưu hóa hàm mục tiêu nhiều biến. Công trình kết hợp giữa phân tích mô hình toán học, thiết kế thuật toán mã hóa tối ưu bộ nhớ và cài đặt thực nghiệm hoàn chỉnh trên máy tính qua các bài toán tối ưu tổ hợp kinh điển và mô hình thiết bị cân bằng. Kết quả nghiên cứu khẳng định tiềm năng ứng dụng của thuật toán tiến hóa trong việc giải quyết các bài toán kỹ thuật và kinh tế - xã hội có không gian tìm kiếm lớn và cấu trúc phức tạp.
