Tổng quan về luận án

Lập trình tiến hóa (Genetic Programming - GP) là một nhánh đột phá của thuật toán tiến hóa (Evolutionary Algorithms) và học máy metaheuristic, sở hữu năng lực đặc biệt trong việc đồng thời tìm kiếm cấu trúc mô hình tối ưu lẫn tối ưu hóa tham số mà không cần giả định trước dạng hàm số. Khác với các mô hình học máy "hộp đen" (black-box) như mạng nơ-ron sâu (Deep Neural Networks), các giải pháp do GP tiến hóa dưới dạng cây cú pháp (syntax trees) có khả năng diễn giải toán học tường minh (interpretability). Tuy nhiên, rào cản cốt tử hạn chế GP tham gia vào dòng chảy chủ lưu của trí tuệ nhân tạo (AI/ML) chính là sự phụ thuộc nặng nề vào các toán tử thuần túy cú pháp (syntactic-based operators). Bản chất ánh xạ kiểu gen - kiểu hình (genotype-phenotype mapping) phức tạp và gồ ghề (rugged fitness landscape) dẫn đến việc một đột biến cú pháp nhỏ có thể gây ra biến động hành vi khổng lồ, hoặc ngược lại, làm suy giảm nghiêm trọng tính tương đồng giữa cha mẹ và con cái (offspring-parent locality). Hệ quả trực tiếp là sự bùng nổ kích thước chương trình vô ích — hiện tượng phình to mã nguồn (code bloat) — đi kèm với quá khớp (overfitting) và suy giảm tốc độ hội tụ.

Luận án tiến sĩ chuyên ngành Cơ sở toán học cho tin học (Mã số: 9 46 01 10) của tác giả Chu Thị Hướng, dưới sự hướng dẫn khoa học của TS. Nguyễn Quang Uy và PGS. TS. Nguyễn Xuân Hoài tại Học viện Kỹ thuật Quân sự (Hà Nội, 2019), mang tiêu đề "Semantics-Based Selection and Code Bloat Reduction Techniques for Genetic Programming", đã thiết lập một bước tiến mang tính cách mạng nhằm giải quyết triệt để hai điểm nghẽn học thuật này.

                  ┌────────────────────────────────────────────────────────┐
                  │    GENETIC PROGRAMMING: PHÂN TÍCH HÀNH VI NGỮ NGHĨA     │
                  └──────────────────────────┬─────────────────────────────┘
                                             │
             ┌───────────────────────────────┴───────────────────────────────┐
             ▼                                                               ▼
┌─────────────────────────┐                                     ┌─────────────────────────┐
│     CHỌN LỌC ĐA CHIỀU   │                                     │  KIỂM SOÁT CODE BLOAT   │
│   (Vectơ sai số e(p))   │                                     │  (Xấp xỉ ngữ nghĩa SAT) │
├─────────────────────────┤                                     ├─────────────────────────┤
│ • TS-R (Random)         │                                     │ • SAT-GP (Approx Term)  │
│ • TS-S (Size-biased)    │                                     │ • SAS-GP (Approx Sub)   │
│ • TS-P (Probabilistic)  │                                     │ • PP-AT (Prune & Plant) │
│ ➔ Tăng đa dạng ngữ nghĩa│                                     │ ➔ Triệt tiêu code bloat │
└─────────────────────────┘                                     └─────────────────────────┘

Khoảng trống nghiên cứu (Research Gaps) cụ thể được xác định từ y văn quốc tế bao gồm:

  1. Cơ chế chọn lọc truyền thống bỏ qua thông tin ngữ nghĩa đa chiều: Các kỹ thuật chọn lọc phổ biến như Tournament Selection chuẩn (Blickle & Thiele, 1995) chỉ dựa hoàn toàn vào một giá trị thích nghi vô hướng duy nhất (scalar fitness như Mean Squared Error - MSE hoặc Mean Absolute Error - MAE), làm mất hoàn toàn phân phối sai số chi tiết trên từng ca kiểm thử (fitness cases). Các nỗ lực tích hợp ngữ nghĩa vào chọn lọc trước đó như Semantic in Selection - SiS (Galván-López et al., 2011) chỉ áp dụng ngưỡng khoảng cách thô sơ để loại trừ cá thể trùng lặp mà không khai thác ý nghĩa thống kê của hành vi sai số.
  2. Sự đánh đổi giữa kiểm soát kích thước mã và độ chính xác mô hình: Các phương pháp kiểm soát code bloat kinh điển (như áp lực tinh giản Parsimony Pressure, giới hạn độ sâu cây của Koza, hay phân phối kích thước quần thể) thường làm suy giảm nghiêm trọng khả năng khớp dữ liệu huấn luyện. Ngược lại, phương pháp Lập trình tiến hóa ngữ nghĩa hình học (Geometric Semantic Genetic Programming - GSGP của Moraglio et al., 2012) tuy tạo ra bề mặt thích nghi đơn cực (unimodal landscape) nhưng lại làm phình to kích thước cá thể theo hàm mũ qua từng thế hệ, đòi hỏi chi phí bộ nhớ không thể duy trì. Kỹ thuật truyền ngược ngữ nghĩa (Semantic Backpropagation của Krawiec et al., 2013) thì phụ thuộc hoàn toàn vào việc tìm kiếm trong thư viện chương trình con (library search), gây tắc nghẽn tính toán.

Hệ thống câu hỏi nghiên cứu và giả thuyết khoa học của luận án:

  • RQ1: Làm thế nào để khai thác phân phối thống kê của vectơ sai số ngữ nghĩa nhằm nâng cao hiệu quả chọn lọc cá thể mà không làm mất tính ngẫu nhiên và đa dạng của quần thể?
    • H1: Tích hợp kiểm định thống kê phi tham số (non-parametric hypothesis testing) vào Tournament Selection sẽ nâng cao đa dạng ngữ nghĩa (semantic diversity), giảm kích thước cá thể và tăng cường năng lực khái quát hóa trên dữ liệu chưa biết.
  • RQ2: Liệu có thể sinh trực tiếp một cây con nhỏ có ngữ nghĩa xấp xỉ một vectơ ngữ nghĩa đích mà không cần dựa vào thư viện chương trình con dựng sẵn?
    • H2: Kỹ thuật xấp xỉ ngữ nghĩa giải tích kết hợp với truyền ngược ngữ nghĩa cho phép thay thế hoặc cắt tỉa các nhánh cây dư thừa, triệt tiêu code bloat mà vẫn duy trì hoặc cải thiện độ chính xác mô hình.
  • RQ3: Mô hình cấu trúc quần thể phân cấp có thể nâng cao hiệu năng tìm kiếm GP trên tập dữ liệu quy mô lớn hay không?
    • H3: Phân chia tiến hóa thành hai pha với các tiểu quần thể (Multiple Subpopulations GP - MS-GP) được huấn luyện trên các tập dữ liệu con lấy mẫu sẽ giúp tối ưu hóa cả thời gian chạy lẫn kích thước nghiệm.

Khung lý thuyết của nghiên cứu được xây dựng trên nền tảng Lý thuyết không gian ngữ nghĩa lấy mẫu (Sampling Semantics Theory - Vanneschi et al., 2014), Lý thuyết hình học ngữ nghĩa (Moraglio et al., 2012) và Lý thuyết kiểm định giả thuyết thống kê (Wilcoxon signed-rank test). Phạm vi thực nghiệm của luận án bao phủ một tập hợp đồ sộ các bài toán quy chuẩn (benchmarks) như họ hàm Koza (Koza-1 đến Koza-3), họ hàm Nguyễn (Nguyen-1 đến Nguyen-10), họ hàm Korns (Korns-1), các bộ dữ liệu thực tế từ kho lưu trữ Machine Learning UCI và bài toán dự báo chuỗi thời gian bán lẻ thực tế (Retail sales time series forecasting giai đoạn 01/09/2016 đến 31/12/2016). Các thử nghiệm được tiến hành với 30 đến 100 lần chạy độc lập cho mỗi cấu hình (kích thước quần thể 500–1024 cá thể, tiến hóa 50–250 thế hệ, độ sâu tối đa 17), tạo nên một công trình có ý nghĩa đột phá cả về mặt toán học giải thuật lẫn ứng dụng thực tiễn.

Literature Review và Positioning

Phân tích tổng hợp y văn quốc tế cho thấy các phương pháp tiếp cận ngữ nghĩa trong GP có thể chia thành hai trường phái chính theo phân loại của Vanneschi et al. (2014):

                                  TIẾP CẬN NGỮ NGHĨA TRONG GP
                                                │
                ┌───────────────────────────────┴───────────────────────────────┐
                ▼                                                               ▼
  INDIRECT SEMANTIC METHODS                                       DIRECT SEMANTIC METHODS
  (Phương pháp gián tiếp)                                         (Phương pháp trực tiếp)
  ─────────────────────────                                       ───────────────────────
  • McPhee et al. (2008): Semantic Contexts                       • Moraglio et al. (2012): GSGP (SGX, SGM)
  • Beadle & Johnson (2008): SDC (ROBDDs)                         • Nguyen et al. (2016): SSGX (Subtree level)
  • Nguyen Quang Uy et al. (2009-2011): SAC, SSC, MSSC            • Martins et al. (2018): GSGP-Red
  • Galván-López et al. (2011): SiS                               • Krawiec & Pawlak (2013): LGX, RDO, AGX
  • Chen et al. (2017-2018): AGSX, PC, RSM                        • Pawlak & Krawiec (2017): CM, CX

Trường phái gián tiếp tập trung bảo toàn tính đa dạng và độ cục bộ ngữ nghĩa thông qua việc chấp nhận hoặc từ chối các cá thể sinh ra từ toán tử cú pháp chuẩn. Khởi xướng bởi McPhee et al. (2008) với phân tích ngữ nghĩa ngữ cảnh (semantic contexts) trên miền Boolean, tiếp nối bởi Beadle và Johnson (2008) với toán tử Semantically-Driven Crossover (SDC) sử dụng Reduced Ordered Binary Decision Diagrams (ROBDDs) để loại bỏ các con non tương đương ngữ nghĩa với cha mẹ. Trên miền hàm giá trị thực, việc đánh giá tương đương ngữ nghĩa là một bài toán thuộc lớp NP-hard (Nguyen et al., 2009; Vanneschi et al., 2014). Do đó, Nguyễn Quang Uy cùng các cộng sự (2009, 2011) đã tiên phong đề xuất Semantics Aware Crossover (SAC), Semantic Similarity based Crossover (SSC) và Most Semantically Similar Crossover (MSSC), sử dụng khoảng cách ngữ nghĩa trên tập mẫu huấn luyện trong khoảng $[\alpha, \beta]$ để dẫn dắt quá trình lai ghép. Tuy nhiên, điểm yếu cố hữu của các phương pháp gián tiếp là chi phí thời gian tiến hóa rất lớn do phải liên tục sinh thử và hủy bỏ cá thể không đạt tiêu chí (trial-and-error overhead).

Trường phái trực tiếp tác động thẳng vào cấu trúc kiểu hình. Đỉnh cao là công trình của Moraglio et al. (2012) về Geometric Semantic Genetic Programming (GSGP) với hai toán tử lai ghép hình học (SGX) và đột biến hình học (SGM), tạo ra con non bằng phép tổ hợp lồi (convex combination) từ cha mẹ: $$t = (p_1 \cdot tr) + (p_2 \cdot (1 - tr))$$ trong đó $tr$ là một hàm ngẫu nhiên có miền giá trị trong đoạn $[0, 1]$. Dù chứng minh được việc biến đổi không gian tìm kiếm thành đơn cực đối với hàm lỗi lồi, GSGP vấp phải vấn đề tăng trưởng kích thước cây theo hàm mũ: kích thước cá thể con bằng tổng kích thước cha mẹ cộng thêm cây ngẫu nhiên $tr$. Các giải pháp khắc phục sau đó như SSGX (Nguyen et al., 2016), GSGP-Red (Martins et al., 2018) hay Geometric Dispersion (Oliveira et al., 2018) vẫn chưa thể giải quyết triệt để sự cồng kềnh bộ nhớ. Mặt khác, Krawiec và Pawlak (2013) đề xuất thuật toán truyền ngược ngữ nghĩa (Semantic Backpropagation) và các toán tử Random Desired Operator (RDO), Approximate Geometric Crossover (AGX), cùng các biến thể mở rộng như Angle-aware Geometric Semantic Crossover (AGSX - Chen et al., 2017), Perpendicular Crossover (PC) và Random Segment Mutation (RSM - Chen et al., 2018). Dẫu vậy, các toán tử này đều yêu cầu duy trì và tra cứu trên một thư viện chương trình con tĩnh khổng lồ, làm hạn chế tính linh hoạt của giải thuật.

Cuộc tranh luận học thuật cốt lõi tồn tại giữa hai quan điểm:

  • Quan điểm Cú pháp & Tinh giản hình thức: Khẳng định rằng duy trì cấu trúc cú pháp nhỏ gọn bằng cách phạt kích thước (Parsimony Pressure - Luke & Panait, 2006) là đủ để tối ưu hóa tính toán, song thực tế lại gây mất mát nghiêm trọng độ chính xác.
  • Quan điểm Ngữ nghĩa hình học thuần túy: Cho rằng cấu trúc cú pháp không quan trọng bằng vị trí kiểu hình trong không gian ngữ nghĩa (Moraglio et al., 2012), chấp nhận kích thước cây bùng nổ để đổi lấy sự hội tụ toán học.

Luận án của Chu Thị Hướng đã định vị chính xác ở giao điểm đột phá: Tích hợp phân tích thống kê phi tham số vào quá trình chọn lọc giải đấu để khai thác ngữ nghĩa đa chiều mà không tăng kích thước mẫu, đồng thời thiết lập cơ chế xấp xỉ ngữ nghĩa trực tiếp (Semantic Approximation) loại bỏ hoàn toàn sự phụ thuộc vào thư viện chương trình con.

Khi so sánh với nghiên cứu SiS của Galván-López et al. (2011) và RDO của Pawlak & Krawiec (2017), giải pháp của luận án vượt trội ở khả năng vừa giảm kích thước cây nghiệm (code bloat reduction) vừa duy trì sai số kiểm tra (testing error) tối ưu dưới điều kiện dữ liệu có nhiễu cực lớn.

Đóng góp lý thuyết và khung phân tích

Đóng góp cho lý thuyết

Luận án mở rộng sâu sắc Lý thuyết không gian ngữ nghĩa lấy mẫu (Sampling Semantics Theory). Cho tập chương trình $P$, tập đầu vào $I$ và tập đầu ra $O$, ánh xạ ngữ nghĩa được định nghĩa là $s: P \to S$. Với tập $n$ ca kiểm thử $F = {(in_1, y_1), (in_2, y_2), \dots, (in_n, y_n)}$, ngữ nghĩa của chương trình $p$ là một điểm trong không gian $n$ chiều: $$s(p) = (p(in_1), p(in_2), \dots, p(in_n)) \in \mathbb{R}^n$$

Thay vì chỉ xem xét khoảng cách Euclid hoặc Manhattan giữa $s(p)$ và vectơ mục tiêu $y = (y_1, \dots, y_n)$ để tính một giá trị độ thích nghi vô hướng $f(p) = d(s(p), y)$, luận án đưa ra khái niệm bản chất về Vectơ sai số (Error Vector): $$e(p) = (|s(p)_1 - y_1|, |s(p)_2 - y_2|, \dots, |s(p)_n - y_n|)$$

                               SO SÁNH CÁ THỂ: TỪ VÔ HƯỚNG ĐẾN ĐA CHIỀU
                               
  CẬN TRUYỀN THỐNG (Vô hướng)                     ĐÓNG GÓP CỦA LUẬN ÁN (Phân tích vectơ sai số)
  ─────────────────────────────                   ──────────────────────────────────────────────
  Chương trình p ➔ e(p) ➔ f(p) = Σ|e_i|           Chương trình p ➔ e(p) = (|e_1|, |e_2|, ..., |e_n|)
  Chương trình q ➔ e(q) ➔ f(q) = Σ|e_i|           Chương trình q ➔ e(q) = (|e_1|, |e_2|, ..., |e_n|)
               │                                               │
               ▼                                               ▼
     So sánh f(p) < f(q)?                           Kiểm định Wilcoxon Signed-Rank Test:
  (Mất toàn bộ cấu trúc phân phối)                  W = Σ sign(e(p)_i - e(q)_i) · R_i, p-value < 0.05
                                                    ➔ Khẳng định sự vượt trội có ý nghĩa thống kê!

Đóng góp lý thuyết nền tảng của luận án là chuyển đổi mô hình so sánh cá thể từ việc so khớp giá trị vô hướng sang Kiểm định so sánh cặp phân phối sai số thông qua kiểm định phi tham số Wilcoxon signed-rank test. Đối với hai cá thể $p$ và $q$, kiểm định Wilcoxon thực hiện trên hai vectơ sai số $e(p)$ và $e(q)$ để xác định xem sự khác biệt về năng lực giải quyết bài toán giữa hai cá thể có ý nghĩa thống kê ở mức ý nghĩa $\alpha = 0.05$ hay không:

  • Giả thuyết $H_0$: Không có sự khác biệt giữa phân phối sai số của $p$ và $q$.
  • Giả thuyết $H_1$: Phân phối sai số của một cá thể vượt trội hơn cá thể kia.

Sự chuyển dịch mô thức này chứng minh rằng: Một cá thể có tổng sai số nhỏ hơn (fitness tốt hơn) chưa chắc đã có ưu thế thống kê vượt trội trên toàn bộ tập ca kiểm thử. Việc áp dụng kiểm định thống kê cho phép duy trì các cá thể có hành vi độc đáo (niche behaviors), ngăn ngừa hiện tượng hội tụ sớm vào cực trị địa phương và tạo áp lực chọn lọc dựa trên sự tin cậy thống kê thực sự.

Khung phân tích độc đáo

Khung phân tích của luận án tích hợp chặt chẽ ba lý thuyết trụ cột:

  1. Formal Semantics & Semantic Backpropagation: Sử dụng giải thuật truyền ngược ngữ nghĩa để xác định chính xác ngữ nghĩa mong muốn (desired semantics) tại một nút trung gian bất kỳ trên cây cú pháp.
  2. Non-parametric Statistical Inference: Ứng dụng kiểm định Wilcoxon vào toán tử chọn lọc giải đấu.
  3. Parsimony Optimization Strategy: Tận dụng các tiêu chí hình thức (kích thước cá thể) làm biến phụ trợ trong trường hợp không có sự khác biệt thống kê về ngữ nghĩa.
       ┌────────────────────────────────────────────────────────────────────────┐
       │             KHUNG PHÂN TÍCH TÍCH HỢP ĐỘC ĐÁO CỦA LUẬN ÁN               │
       └───────────────────────────────────┬────────────────────────────────────┘
                                           │
         ┌─────────────────────────────────┼─────────────────────────────────┐
         ▼                                 ▼                                 ▼
┌─────────────────────────┐     ┌─────────────────────────┐     ┌─────────────────────────┐
│  SEMANTIC APPROXIMATION │     │   STATISTICAL TOURNAMENT│     │ MULTIPLE SUBPOPULATIONS │
│     TECHNIQUE (SAT)     │     │      SELECTION (TS)     │     │         (MS-GP)         │
├─────────────────────────┤     ├─────────────────────────┤     ├─────────────────────────┤
│ • Tính Desired Semantics│     │ • TS-R (Random tie-break│     │ • Pha 1: Tiểu quần thể  │
│ • Khởi tạo cây con nhỏ  │     │ • TS-S (Size tie-break) │     │   tiến hóa trên mẫu con │
│ • Tối ưu trực tiếp      │     │ • TS-P (Probabilistic)  │     │ • Pha 2: Gộp quần thể   │
│ ➔ Không cần Library!    │     │ ➔ Giữ đa dạng ngữ nghĩa │     │   chạy trên toàn bộ data│
└─────────────────────────┘     └─────────────────────────┘     └─────────────────────────┘

Trên cơ sở đó, luận án thiết lập kỹ thuật Xấp xỉ ngữ nghĩa (Semantic Approximation Technique - SAT). Khác với các công trình trước đây của Krawiec et al. vốn tìm kiếm một cây con thay thế trong một thư viện hữu hạn cho trước $L$, SAT trực tiếp sinh trưởng một cây con cục bộ có kích thước nhỏ (độ sâu từ 1 đến 3) có ngữ nghĩa xấp xỉ tối đa với vectơ ngữ nghĩa mong muốn $s^*$. Ba phương pháp giảm code bloat được thiết kế từ khung phân tích này:

  • SAT-GP (Substituting a Subtree with an Approximate Terminal): Thay thế một cây con cồng kềnh bằng một hằng số hoặc biến đầu vào xấp xỉ tối ưu.
  • SAS-GP (Substituting a Subtree with an Approximate Subprogram): Sinh trực tiếp một cây con nhỏ có hành vi tương đương để thay thế nhánh cây phức tạp.
  • PP-AT (Prune and Plant based on Approximate Terminal): Cắt tỉa nhánh cây dư thừa và tái cấy ghép các nút kết thúc xấp xỉ nhằm tối ưu hóa toàn diện cấu trúc cây.

Điều kiện biên (Boundary Conditions): Khung phân tích được xác lập chặt chẽ cho bài toán Hồi quy biểu tượng (Symbolic Regression) trên miền giá trị thực với tập ca kiểm thử hữu hạn $n \ge 30$ (đảm bảo điều kiện kích thước mẫu cho kiểm định tiệm cận Wilcoxon).

Phương pháp nghiên cứu tiên tiến

Thiết kế nghiên cứu

Nghiên cứu theo đuổi hệ hình Thực chứng (Positivism) với phương pháp định lượng thực nghiệm nghiêm ngặt. Thiết kế nghiên cứu đa cấp (Multi-level Experimental Design) được xây dựng xuyên suốt:

  • Cấp độ Nút (Node-level): Phân tích ngữ nghĩa cục bộ và truyền ngược sai số qua các hàm số học ${+, -, *, /}$ và hàm lượng giác ${\sin, \cos, \exp}$.
  • Cấp độ Cá thể (Individual-level): Đo lường kích thước cây (số lượng nodes), độ sâu, sai số huấn luyện (training fitness) và sai số kiểm tra (testing error).
  • Cấp độ Quần thể (Population-level): Đánh giá khoảng cách ngữ nghĩa trung bình (semantic diversity), tốc độ phình to mã (bloat rate) và mức độ quá khớp (overfitting metric).
                      THIẾT KẾ NGHIÊN CỨU ĐA CẤP (MULTI-LEVEL DESIGN)
                      
   ┌─────────────────────────────────────────────────────────────────────────────┐
   │ CẤP QUẦN THỂ: Đo lường Semantic Diversity, Overfitting Index, Bloat Rate    │
   └──────────────────────────────────────┬──────────────────────────────────────┘
                                          │
   ┌──────────────────────────────────────┴──────────────────────────────────────┐
   │ CẤP CÁ THỂ: Đo lường Testing Error Median, Tree Size (Nodes), Depth         │
   └──────────────────────────────────────┬──────────────────────────────────────┘
                                          │
   ┌──────────────────────────────────────┴──────────────────────────────────────┐
   │ CẤP NÚT/CẤU TRÚC: Phân tích Desired Semantics, Semantic Backpropagation     │
   └─────────────────────────────────────────────────────────────────────────────┘

Quy trình nghiên cứu rigorous

Quy trình thực nghiệm tuân thủ các chuẩn mực cao nhất của cộng đồng tiến hóa quốc tế (White et al., 2013):

  1. Khởi tạo quần thể: Áp dụng phương pháp Ramped Half-and-Half với khoảng độ sâu khởi tạo từ 2 đến 6, đảm bảo sự phong phú về hình thái cây ban đầu.
  2. Tham số tiến hóa:
    • Kích thước quần thể: $N = 500$ (cho các bài toán chuẩn) và $N = 1024$ (cho các bài toán phức tạp).
    • Số thế hệ tiến hóa: $G = 50 - 250$ thế hệ.
    • Xác suất toán tử: Lai ghép (Crossover) = 0.9; Đột biến (Mutation) = 0.05 - 0.1; Sao chép (Reproduction) = 0.1.
    • Giới hạn độ sâu tối đa (Max depth) = 17 tầng (tương đương chuẩn Koza).
    • Kích thước giải đấu (Tournament size): Thử nghiệm toàn diện trên các kích thước $K = 3$, $K = 5$ và $K = 7$.
  3. Thuật toán chọn lọc đề xuất:
    • TS-R (Tournament Selection with Random): Trong một giải đấu gồm $K$ cá thể, so sánh cá thể tốt nhất hiện tại $A$ với ứng viên $B$. Sử dụng kiểm định Wilcoxon trên $e(A)$ và $e(B)$. Nếu một cá thể vượt trội có ý nghĩa thống kê ($p < 0.05$), cá thể đó thắng. Nếu không có sự khác biệt thống kê ($p \ge 0.05$), chọn ngẫu nhiên giữa $A$ và $B$.
    • TS-S (Tournament Selection with Size): Nếu kiểm định Wilcoxon không chỉ ra sự khác biệt có ý nghĩa thống kê giữa $A$ và $B$, cá thể có kích thước nhỏ hơn (ít nodes hơn) sẽ được chọn. Đây là cơ chế trực tiếp đưa áp lực tinh giản vào chọn lọc mà không làm biến dạng hàm thích nghi.
    • TS-P (Tournament Selection with Probability): Nếu không có sự khác biệt thống kê, cá thể nhỏ hơn được chọn với xác suất $P_{size}$ và cá thể lớn hơn được chọn với xác suất $1 - P_{size}$.
                 QUY TRÌNH TOÁN TỬ CHỌN LỌC THỐNG KÊ (TS-R, TS-S, TS-P)
                 
                        ┌─────────────────────────────────────┐
                        │   Lấy 2 cá thể A và B trong Tour    │
                        └──────────────────┬──────────────────┘
                                           │
                                           ▼
                        ┌─────────────────────────────────────┐
                        │    Tính vectơ sai số e(A) & e(B)    │
                        │    Chạy kiểm định Wilcoxon (p-val)  │
                        └──────────────────┬──────────────────┘
                                           │
                    ┌──────────────────────┴──────────────────────┐
                    ▼ (p < 0.05: Có khác biệt)                    ▼ (p ≥ 0.05: Tương đương)
        ┌─────────────────────────┐                   ┌───────────────────────────────┐
        │ Cá thể có tổng hạng sai │                   │  XỬ LÝ TRƯỜNG HỢP HÒA (TIE):   │
        │ số nhỏ hơn chiến thắng  │                   ├───────────────────────────────┤
        └─────────────────────────┘                   │ • TS-R: Chọn ngẫu nhiên 50/50 │
                                                      │ • TS-S: Chọn cá thể nhỏ hơn   │
                                                      │ • TS-P: Chọn nhỏ hơn với xác  │
                                                      │         suất P_size           │
                                                      └───────────────────────────────┘
  1. Triangulation và Tính hợp lệ: Độ tin cậy (reliability) và tính hợp lệ cấu trúc (construct validity) được bảo đảm bằng cách lặp lại 30–100 runs độc lập với các seed ngẫu nhiên khác nhau. Mọi kết luận so sánh đều dựa trên kiểm định cặp Wilcoxon signed-rank test đa mẫu với mức ý nghĩa $p < 0.05$.

Data và phân tích

Nghiên cứu sử dụng hệ thống dữ liệu toàn diện:

  • Tập bài toán chuẩn nhân tạo: Các bài toán kinh điển gồm Koza-1 ($x^4 + x^3 + x^2 + x$), Koza-2 ($x^5 - 2x^3 + x$), Koza-3 ($x^6 - 2x^4 + x^2$), các hàm đa thức và lượng giác đa biến Nguyễn (Nguyen-1 đến Nguyen-10), và bài toán 5 biến Korns-1 ($1.57 + 24.3v$). Miền huấn luyện và kiểm tra được lấy mẫu độc lập từ phân phối đều $U[a, b]$ hoặc lưới điểm cách đều $E[a, b]$.
  • Dữ liệu có nhiễu (Noisy Data): Bổ sung nhiễu Gaussian trắng vào đầu ra với các mức độ khác nhau nhằm kiểm tra độ bền vững (robustness checks) của giải thuật.
  • Dữ liệu thực tế và thuật toán đối chứng: So sánh trực tiếp với các thuật toán học máy hàng đầu thông qua phần mềm chuyên dụng và thư viện chuẩn: Support Vector Regression (SVR - tối ưu qua Grid Search $C, \gamma, \epsilon$), Decision Tree Regressor (DT), và Random Forest (RF - 100 cây quyết định).

Phát hiện đột phá và implications

Những phát hiện then chốt

Dữ liệu thực nghiệm của luận án cung cấp bằng chứng thuyết phục về các đóng góp đột phá:

                  SO SÁNH HIỆU NĂNG TỔNG THỂ TRÊN CÁC TRỤ CỘT CHÍNH
                  
  Chỉ số đánh giá            Standard GP       SiS (Galván-López)     Đề xuất (TS-S / SAT-GP)
  ─────────────────────────────────────────────────────────────────────────────────────────────
  Median Testing Error       Trung bình        Cải thiện nhẹ          Tối ưu vượt trội (p < 0.01)
  Kích thước cây (Nodes)     Bùng nổ (Bloat)   Lớn                    Giảm 40% - 65%
  Đa dạng ngữ nghĩa          Thấp              Khá                    Rất cao (Semantic Distance lớn)
  Khả năng kháng nhiễu       Kém (Overfit)     Trung bình             Rất cao (Vectơ sai số bền vững)
  Thời gian chạy (Runtime)   Nhanh             Chậm (Trial-reject)    Tối ưu (Nhanh hơn RDO/AGX)

  1. Khả năng triệt tiêu Code Bloat vượt trội của TS-S: Trên toàn bộ các bài toán chuẩn với kích thước giải đấu $K = 3$ và $K = 7$, TS-S làm giảm kích thước nghiệm trung bình từ 40% đến 65% so với Standard GP và SiS. Cụ thể, trên các hàm thử nghiệm F1, F13, F17 và F25, đường cong tăng trưởng kích thước của Standard GP tăng dựng đứng theo thế hệ (hiện tượng phình mã điển hình), trong khi TS-S duy trì kích thước ổn định dưới 50 nodes mà không làm suy giảm độ thích nghi tốt nhất (Mean of Best Fitness).

  2. Duy trì Đa dạng ngữ nghĩa (Semantic Diversity): Kết quả đo lường khoảng cách ngữ nghĩa trung bình (Average Semantic Distance) chứng minh quần thể tiến hóa dưới sự dẫn dắt của TS-S và TS-R có khoảng cách ngữ nghĩa giữa các cá thể lớn hơn có ý nghĩa thống kê so với Standard GP. Tỷ lệ bác bỏ giả thuyết vô hiệu $H_0$ trong kiểm định Wilcoxon nội bộ giải đấu đạt từ 65% đến 85%, khẳng định toán tử chọn lọc thống kê đã tạo ra sự phân hóa hành vi sâu sắc.

  3. Tính bền vững vượt bậc trên Dữ liệu chứa nhiễu: Khi đưa nhiễu ngẫu nhiên vào dữ liệu huấn luyện, Standard GP bị quá khớp nghiêm trọng do cố gắng tiến hóa các nhánh cây phức tạp để "học vẹt" nhiễu. Ngược lại, TS-S và TS-P đạt Median Testing Error thấp hơn rõ rệt. Do cơ chế kiểm định Wilcoxon xem các biến động nhỏ do nhiễu là "không có ý nghĩa thống kê", giải thuật tự động kích hoạt tiêu chí chọn cá thể có kích thước nhỏ hơn, tạo nên năng lực chính quy hóa tự nhiên (implicit regularization).

  4. Hiệu năng đột phá của Xấp xỉ ngữ nghĩa (SAT-GP, SAS-GP, PP-AT): Tỷ lệ sinh ra con non tốt hơn (Percentage of Better Offspring) của các toán tử dựa trên SAT cao gấp 2.5 đến 4 lần so với toán tử đột biến chuẩn và vượt trội so với RDO của Pawlak & Krawiec. Đáng chú ý, PP-AT vừa giảm mạnh độ phức tạp hàm số (Function Complexity), vừa duy trì sai số kiểm tra ở mức tối thiểu.

  5. Chiến thắng trước các thuật toán Machine Learning truyền thống: Trên tập dữ liệu chuỗi thời gian thực tế $\log(\text{unit sale} + 1)$ và các bài toán UCI, GP tích hợp kỹ thuật xấp xỉ ngữ nghĩa đạt sai số dự báo cạnh tranh trực tiếp và trong nhiều trường hợp vượt qua SVR và Random Forest, trong khi mang lại lợi thế vượt trội là cung cấp công thức toán học tường minh cho các nhà phân tích.

Implications đa chiều

  • Về mặt lý thuyết: Luận án đã giải quyết thành công nghịch lý giữa tính đa dạng ngữ nghĩa và hiện tượng phình to mã nguồn, chứng minh rằng không cần hy sinh độ chính xác để đổi lấy sự nhỏ gọn của mô hình nếu thông tin ngữ nghĩa được khai thác đúng đắn ở cấp độ phân tích thống kê.
  • Về mặt phương pháp luận: Cung cấp một quy trình mẫu mực về việc đưa các kiểm định thống kê phi tham số vào bên trong các vòng lặp nội tại của thuật toán tiến hóa, mở đường cho việc áp dụng trên Lập trình tiến hóa tuyến tính (Linear GP) và Lập trình tiến hóa Descartes (Cartesian GP).
  • Về mặt ứng dụng thực tiễn: Cung cấp công cụ mô hình hóa mạnh mẽ cho các bài toán dự báo tài chính, chuỗi cung ứng logistics, và phân tích tín hiệu kỹ thuật trong quốc phòng — những lĩnh vực đòi hỏi mô hình vừa chính xác cao vừa phải minh bạch về mặt cơ chế.

Limitations và Future Research

Nhìn nhận một cách khách quan và khoa học, luận án tồn tại một số giới hạn nghiên cứu (Limitations):

  1. Chi phí tính toán của kiểm định thống kê: Việc tính toán kiểm định Wilcoxon trên từng cặp cá thể trong giải đấu làm tăng thời gian chạy của bước chọn lọc ($O(n \log n)$ với $n$ là số ca kiểm thử). Khi số lượng fitness cases lên tới hàng chục nghìn điểm, chi phí này trở thành một rào cản đáng kể.
  2. Phạm vi bài toán: Nghiên cứu tập trung chủ yếu vào bài toán Hồi quy biểu tượng đơn đầu ra (Single-output Symbolic Regression). Việc mở rộng sang bài toán phân loại đa lớp (Multi-class Classification) đòi hỏi phải tái cấu trúc lại định nghĩa không gian ngữ nghĩa và kiểm định thống kê tương ứng (ví dụ sử dụng kiểm định Chi-square hoặc Cohen's Kappa).
  3. Độ nhạy tham số: Hiệu năng của TS-P phụ thuộc vào việc thiết lập xác suất $P_{size}$, hiện vẫn được lựa chọn dựa trên kinh nghiệm thực nghiệm mà chưa có cơ chế tự thích nghi (self-adaptation) theo thời gian thực.

Chương trình nghiên cứu tương lai (Future Research Agenda):

  • Hướng 1 (Mở rộng quy mô tính toán): Tận dụng kiến trúc tính toán song song trên GPU để tính toán đồng thời ma trận kiểm định thống kê và vectơ sai số cho quần thể quy mô lớn.
  • Hướng 2 (Phân loại đa lớp & Rời rạc): Phát triển toán tử chọn lọc thống kê ngữ nghĩa cho bài toán phân loại dữ liệu y sinh và an ninh mạng.
  • Hướng 3 (Tự thích nghi tham số): Thiết lập cơ chế thích nghi động cho xác suất chọn lọc và ngưỡng xấp xỉ ngữ nghĩa dựa trên độ biến thiên entropy của quần thể qua từng thế hệ.
  • Hướng 4 (Tích hợp Deep GP): Ứng dụng kỹ thuật xấp xỉ ngữ nghĩa SAT vào việc tối ưu hóa cấu trúc kiến trúc mạng nơ-ron sâu (Deep Neural Architecture Search).

Tác động và ảnh hưởng

  • Tác động học thuật (Academic Impact): Luận án đã công bố 7 công trình khoa học chất lượng cao, bao gồm 1 bài báo trên tạp chí quốc tế uy tín danh mục ISI/SCI-Q1 (Applied Soft Computing), 3 bài báo tại các hội nghị quốc tế chuyên ngành hàng đầu, 1 bài báo tạp chí chuyên ngành trong nước, cùng 2 công trình SCIE-Q1 và tạp chí trong nước gửi đăng trong giai đoạn hoàn thiện. Các công bố này tạo nền tảng trích dẫn vững chắc cho cộng đồng nghiên cứu GP trên thế giới về mảng Semantic GP.
  • Chuyển đổi công nghiệp (Industry Transformation): Đóng góp giải pháp mô hình hóa dữ liệu tự động cho các ngành công nghiệp đòi hỏi tính minh bạch cao như Tài chính (Fintech), Chuỗi cung ứng (Dự báo nhu cầu hàng hóa bán lẻ), và Y tế (Mô hình hóa dữ liệu lâm sàng).
  • Ý nghĩa quốc phòng và xã hội: Được thực hiện tại Học viện Kỹ thuật Quân sự, nghiên cứu cung cấp các thuật toán nền tảng phục vụ xử lý tín hiệu radar, nhận dạng mục tiêu và dự báo tham số kỹ thuật quân sự trong điều kiện dữ liệu đo đạc bị nhiễu nghiêm trọng.

Đối tượng hưởng lợi

                                  ĐỐI TƯỢNG HƯỞNG LỢI TRỰC TIẾP
                                                │
         ┌──────────────────────────────┬───────┴──────────────────────┬──────────────────────────────┐
         ▼                              ▼                              ▼                              ▼
┌──────────────────┐           ┌──────────────────┐           ┌──────────────────┐           ┌──────────────────┐
│Nghiên cứu sinh & │           │Nhà khoa học cấp  │           │Kỹ sư AI/ML & R&D │           │Chuyên gia phân   │
│Học viên cao học  │           │cao (Academics)   │           │công nghiệp       │           │tích & Hoạch định │
├──────────────────┤           ├──────────────────┤           ├──────────────────┤           ├──────────────────┤
│Tiếp cận phương   │           │Khai thác khung lý│           │Ứng dụng mã nguồn │           │Sở hữu mô hình dự │
│pháp luận kết hợp │           │thuyết kiểm định  │           │GP giải thích được│           │báo tường minh,   │
│toán thống kê và  │           │ngữ nghĩa để mở   │           │vào chuỗi cung    │           │chính xác cao trên│
│tiến hóa thực tiễn│           │rộng bài toán mới │           │ứng, tài chính    │           │dữ liệu có nhiễu  │
└──────────────────┘           └──────────────────┘           └──────────────────┘           └──────────────────┘
  • Nghiên cứu sinh & Học viên cao học: Sở hữu tài liệu tham khảo chuẩn mực về phương pháp luận kết hợp giữa lý thuyết toán học xác suất thống kê và kỹ thuật lập trình tiến hóa hiện đại; kế thừa các benchmark code và giao thức kiểm thử chặt chẽ.
  • Nhà khoa học cấp cao (Senior Academics): Tiếp cận một khung phân tích mở rộng về không gian ngữ nghĩa lấy mẫu, cung cấp nền tảng để phát triển các lý thuyết tiến hóa đa mục tiêu (Multi-objective Evolutionary Theory).
  • Kỹ sư R&D trong công nghiệp: Nắm bắt thuật toán tối ưu hóa Symbolic Regression có khả năng kháng bloat, phục vụ phát triển các hệ thống AI có khả năng giải thích (Explainable AI - XAI), thay thế các mạng nơ-ron "hộp đen" trong các bài toán dự báo trọng yếu.
  • Chuyên gia phân tích chính sách & Dữ liệu: Ứng dụng mô hình dự báo chuỗi thời gian có độ chính xác cao và độ bền vững trước dữ liệu nhiễu để ra quyết định quản trị chuỗi cung ứng và điều hành vĩ mô.

Câu hỏi chuyên sâu

1. Đóng góp lý thuyết độc đáo nhất của luận án là gì và mở rộng lý thuyết nào?

Đóng góp lý thuyết độc đáo nhất là việc mở rộng Lý thuyết không gian ngữ nghĩa lấy mẫu (Sampling Semantics Theory) thông qua việc cấu trúc hóa vectơ sai số $e(p)$ và tích hợp Kiểm định giả thuyết phi tham số Wilcoxon vào cơ chế so sánh cá thể. Thay vì giản lược toàn bộ hành vi của chương trình về một giá trị thích nghi vô hướng $f(p)$, luận án chứng minh rằng việc bảo tồn cấu trúc phân phối sai số đa chiều giúp phân biệt chính xác sự vượt trội về mặt thống kê giữa các cá thể, thiết lập nền tảng toán học cho các toán tử chọn lọc định hướng ngữ nghĩa.

2. Điểm cải tiến phương pháp luận của TS-S so với các nghiên cứu tiền nhiệm quốc tế?

So với Tournament Selection chuẩn của Blickle & Thiele (1995) (chỉ so sánh scalar fitness) và Semantic in Selection (SiS) của Galván-López et al. (2011) (chỉ lọc bỏ cá thể có khoảng cách ngữ nghĩa dưới ngưỡng mà không phân tích sai số), TS-S của luận án tạo ra bước đột phá hai giai đoạn:

  • Giai đoạn 1: Đánh giá ý nghĩa thống kê của sự khác biệt hành vi qua kiểm định Wilcoxon ở mức $\alpha = 0.05$.
  • Giai đoạn 2: Khi hai cá thể tương đương về mặt thống kê, TS-S ưu tiên tuyệt đối cá thể có kích thước nhỏ hơn. Phương pháp này lồng ghép áp lực tinh giản tự nhiên vào tiến hóa mà không làm biến dạng bề mặt thích nghi như các kỹ thuật phạt kích thước truyền thống.

3. Phát hiện thực nghiệm nào gây bất ngờ nhất và bằng chứng dữ liệu hỗ trợ?

Phát hiện bất ngờ nhất là Năng lực tự chính quy hóa kháng nhiễu (Noise Resilience) vượt trội của TS-S trên dữ liệu có độ biến động cao. Trên tập dữ liệu chứa nhiễu Gaussian, trong khi GP chuẩn và SiS bị suy giảm nghiêm trọng độ chính xác kiểm tra do tiến hóa các cây khổng lồ để khớp với nhiễu, TS-S lại đạt Median Testing Error thấp hơn và kích thước cây nhỏ hơn từ 50-60%. Dữ liệu kiểm định Wilcoxon chỉ ra rằng trong môi trường nhiễu, sự khác biệt sai số giữa các cá thể trên các điểm nhiễu bị triệt tiêu ý nghĩa thống kê ($p \ge 0.05$), buộc giải thuật liên tục lựa chọn cây nhỏ hơn, từ đó loại bỏ hiện tượng quá khớp một cách tự động.

4. Giao thức tái lập thực nghiệm (Replication Protocol) có được cung cấp đầy đủ không?

Luận án cung cấp chi tiết toàn diện giao thức thực nghiệm bao gồm: danh mục hàm mục tiêu toán học và khoảng lấy mẫu của toàn bộ các bài toán benchmark (Bảng 1.2), bảng tham số tiến hóa chuẩn mực (Bảng 1.1 và Bảng 2.2), quy tắc xây dựng tập huấn luyện/kiểm tra, cấu hình tham số Grid Search cho các thuật toán đối chứng SVR, DT, RF (Bảng 3.7), cùng thuật toán giả mã chi tiết cho từng biến thể chọn lọc và xấp xỉ ngữ nghĩa.

5. Chương trình nghiên cứu 10 năm được vạch ra như thế nào?

Lộ trình 10 năm được định hình qua ba giai đoạn chiến lược:

  • Giai đoạn 1 (1-3 năm): Mở rộng kỹ thuật chọn lọc thống kê ngữ nghĩa sang Lập trình tiến hóa đa mục tiêu (MOEA/D, NSGA-III) và bài toán phân loại đa lớp.
  • Giai đoạn 2 (3-5 năm): Phát triển thư viện tối ưu hóa song song trên nền tảng GPU/TPU, tích hợp SAT vào quy trình tự động thiết kế kiến trúc học sâu (AutoML / Deep GP).
  • Giai đoạn 3 (5-10 năm): Xây dựng hệ thống Trí tuệ nhân tạo biểu tượng tự giải thích (Self-explainable Symbolic AI Engine) phục vụ khám phá định luật vật lý và mô hình hóa hệ thống động lực phức hợp trong khoa học vũ trụ và quốc phòng.

Kết luận

Luận án tiến sĩ của tác giả Chu Thị Hướng đã hoàn thành xuất sắc toàn bộ các mục tiêu nghiên cứu đề ra, mang lại những giá trị khoa học cốt lõi:

  1. Đề xuất ba phương pháp chọn lọc giải đấu dựa trên phân tích thống kê ngữ nghĩa (TS-R, TS-S, TS-P): Tiên phong ứng dụng kiểm định phi tham số Wilcoxon vào so sánh vectơ sai số, giải quyết đồng thời bài toán nâng cao đa dạng ngữ nghĩa và kiểm soát phình to mã nguồn.
  2. Phát triển Kỹ thuật xấp xỉ ngữ nghĩa độc lập (SAT): Xây dựng thành công thuật toán sinh trực tiếp cây con xấp xỉ ngữ nghĩa mong muốn từ giải thuật truyền ngược ngữ nghĩa, giải phóng GP khỏi sự phụ thuộc vào thư viện chương trình con định sẵn.
  3. Thiết lập hệ thống phương pháp giảm Code Bloat hiệu năng cao (SAT-GP, SAS-GP, PP-AT): Giảm từ 40% đến 65% kích thước chương trình, nâng cao tỷ lệ con non vượt trội và duy trì độ phức tạp mô hình ở mức tối ưu.
  4. Đề xuất kiến trúc tiến hóa đa tiểu quần thể (MS-GP): Cải tiến khung tiến hóa hai pha giúp tăng tốc độ hội tụ và tối ưu hóa tài nguyên tính toán trên các tập dữ liệu quy mô lớn.
  5. Chứng minh thực nghiệm toàn diện và vượt trội: Xác lập hiệu năng xuất sắc của các phương pháp đề xuất trên hệ thống benchmark chuẩn quốc tế, dữ liệu có nhiễu, dữ liệu chuỗi thời gian thực tế và vượt qua các thuật toán Machine Learning kinh điển (SVR, Random Forest).
  6. Mở ra ba nhánh nghiên cứu đột phá: Đặt nền móng vững chắc cho việc nghiên cứu chọn lọc thống kê trong tiến hóa đa mục tiêu, mở rộng ngữ nghĩa sang miền phân loại rời rạc, và tích hợp lập trình tiến hóa giải thích được vào dòng chảy trí tuệ nhân tạo hiện đại.