Giới thiệu dự án

Bối cảnh và thực trạng ngành

Trong kỹ nghệ máy tính và tự động hóa công nghiệp, các bài toán Tối ưu hóa (Optimization) đóng vai trò then chốt trong việc tìm kiếm các cấu hình thiết kế tối ưu, nâng cao hiệu năng hệ thống và giảm thiểu chi phí vận hành. Theo các báo cáo thống kê từ IEEE Computational Intelligence Society và Gartner, hơn 78% các bài toán kỹ thuật phức tạp trong thế giới thực—từ thiết kế mạch VLSI, khí động học cánh máy bay đến tổng hợp phân tử dược phẩm—đều thuộc lớp bài toán Tối ưu hóa đa cực trị (Multimodal Optimization - MMO).

                f(x)
                 ^
                 |          Cực tiểu địa phương (Local Min)
                 |                 *
                 |               /   \             Cực tiểu toàn cục (Global Min)
                 |     *        /     \                  *
                 |   /   \     /       \                / \
                 |  /     \   /         \              /   \
                 | /       \_/           \____________/     \
                 +---------------------------------------------> x
                   Không gian tìm kiếm đa cực trị liên tục D chiều

Khác với bài toán đơn cực trị (Unimodal Optimization) vốn chỉ tìm một nghiệm cực trị duy nhất, MMO đòi hỏi thuật toán phải tự động dò tìm và định vị đồng thời tất cả các nghiệm cực tiểu/cực đại toàn cục (Global Optima) phân biệt trong không gian tìm kiếm đa chiều $\mathcal{S} \subseteq \mathbb{R}^D$. Khi tiếp cận dưới dạng hộp đen (black-box optimization), thông tin duy nhất mà thuật toán thu nhận được là giá trị hàm mục tiêu $f(x)$ kèm chi phí truy xuất tương ứng (Function Evaluations - FEs), không có thông tin giải tích hay đạo hàm bậc nhất, bậc hai.

Vấn đề cốt lõi và các điểm nghẽn kỹ thuật (Pain Points)

Mặc dù các Thuật toán Tiến hóa Đa cực trị (Multimodal Evolutionary Algorithms - MEAs) như Hill-Valley Evolutionary Algorithm (HillVallEA) đã đạt được nhiều đột phá về mặt số liệu, lĩnh vực này vẫn đối mặt với những rào cản nghiêm trọng:

  1. Thiếu tính trực quan và khả năng giải thích (Explainability Bottleneck): Các báo cáo nghiên cứu MEAs hiện nay hầu như chỉ dừng lại ở các bảng số liệu tĩnh (bảng Mean, Standard Deviation của Peak Ratio/F1-score), hoàn toàn thiếu công cụ trực quan hóa động để phân tích cơ chế dịch chuyển của quần thể qua các thế hệ.
  2. Hiện tượng mất mát thông tin khi giảm chiều: Các kỹ thuật giảm số chiều kinh điển như Principal Component Analysis (PCA) hay t-Distributed Stochastic Neighbor Embedding (t-SNE) làm biến dạng cấu trúc không gian hình học gốc, làm mất tính liên tục của quỹ đạo tìm kiếm.
  3. Giới hạn của các mô hình mạng hiện hữu: Mô hình Mạng cực trị địa phương (Local Optima Network - LON) đòi hỏi mọi trạng thái trung gian phải là nghiệm cực trị địa phương hội tụ hoàn toàn. Trong khi đó, mô hình Mạng quỹ đạo tìm kiếm kinh điển (Search Trajectory Network - STN của Ochoa) chỉ biểu diễn nghiệm đại diện đơn lẻ cho bài toán đơn cực trị; khi áp dụng vào MMO, STN dẫn đến sự bùng nổ số lượng nút/cạnh chồng chéo, khiến việc phân tích hành vi quần thể và kho lưu trữ nghiệm (Archive) bị tắc nghẽn.

Mục tiêu nghiên cứu cụ thể

  1. Thiết kế và chuẩn hóa mô hình mạng quỹ đạo: Đề xuất phương pháp MDSTN (Search Trajectory Network for Multimodal Domain) nhằm mô hình hóa toàn bộ tiến trình biến đổi trạng thái của kho lưu trữ nghiệm $\mathcal{A}$ dưới dạng đồ thị có hướng (Directed Graph).
  2. Xây dựng cơ chế mã hóa lưới không gian đa cực trị: Thiết lập giải thuật mã hóa không gian đa chiều thành các khối siêu lập phương (hypercubes) thông qua hệ số phân chia $PF$ (Partition Factor), tạo mã định danh duy nhất (State ID) cho mỗi trạng thái quần thể.
  3. Phân tích bóc tách cấu trúc vi mô của MEAs: Khảo sát vai trò độc lập và tương tác tương hỗ giữa các thành phần Tìm kiếm toàn cục (Global Search: URR, NBC, HVC) và Tìm kiếm địa phương (Local Search: $(1+\lambda)$-ES, AMaLGaM-IDEAs).
  4. Xây dựng chiến lược tinh chỉnh siêu tham số: Khai thác MDSTN để phát hiện hiện tượng kẹt cực trị địa phương (stagnation) và xác định không gian siêu tham số $(\eta_{inc}, \eta_{dec}, \sigma_{min})$ tối ưu nhằm nâng cao tốc độ hội tụ và độ chính xác.

Phương pháp tiếp cận và cơ sở lập luận

Nghiên cứu lấy đối tượng cốt lõi là Kho lưu trữ nghiệm $\mathcal{A}$ (Archive)—thành phần phản ánh chính xác nhất năng lực tích lũy nghiệm tối ưu của MEA qua từng vòng lặp. Bằng cách kết hợp lý thuyết đồ thị với kỹ thuật phân rã không gian dạng lưới hypercube cố định, MDSTN không làm thay đổi đặc tính hàm mục tiêu và cho phép theo dõi trực tiếp chuỗi chuyển trạng thái:

$$\mathcal{A}_0 \xrightarrow{e_1} \mathcal{A}_1 \xrightarrow{e_2} \dots \xrightarrow{e_T} \mathcal{A}^*$$

Kết quả kỳ vọng và chỉ số đo lường (Measurable Metrics)

  • Chỉ số Recall (Peak Ratio - $PR$): Tỷ lệ nghiệm cực tiểu toàn cục phân biệt tìm được trong $\mathcal{A}$ so với tổng số nghiệm thực tế của bài toán trong bán kính dung sai $\epsilon = 10^{-5}$:

    $$\text{Recall} = \frac{GO_{\mathcal{A}_a}}{GO}$$

  • Chỉ số Precision: Đo lường độ tinh gọn của kho lưu trữ, đánh giá mức độ loại bỏ nghiệm dư thừa:

    $$\text{Precision} = \frac{GO_{\mathcal{A}_a}}{|\mathcal{A}_a|}$$

  • Ngân sách đánh giá hàm mục tiêu (Budget - $b$): Kiểm soát nghiêm ngặt trong khoảng $5 \times 10^4 \le b \le 4 \times 10^5$ FEs theo chuẩn CEC'2013.

Phạm vi và giới hạn nghiên cứu

  • Phạm vi: Bài toán tối ưu hóa liên tục không ràng buộc dạng hộp đen với số chiều $D \in [1, 20]$ trên bộ 20 hàm chuẩn CEC'2013.
  • Giới hạn: Nghiên cứu không can thiệp cấu trúc hàm mục tiêu nội tại mà chỉ đo lường thông qua các lời gọi hàm (Function Evaluations); các nghiệm số được xử lý dưới biểu diễn dấu phẩy động 64-bit IEEE 754.

Phân tích và thiết kế giải pháp

Phân tích hiện trạng

Bảng so sánh các giải pháp phân tích hành vi thuật toán tối ưu hóa

Giải pháp Cơ chế cốt lõi Ưu điểm Nhược điểm / Hạn chế đối với MMO
PCA / t-SNE Projection Chiếu giảm chiều dữ liệu tọa độ $\mathbb{R}^D \to \mathbb{R}^2$ Trực quan hóa tọa độ phân bố nghiệm trên mặt phẳng 2D. Làm méo khoảng cách Euclidean thực tế; mất thông tin liên kết quỹ đạo theo thời gian; chi phí tính toán cao $O(N^2)$.
Local Optima Network (LON) Đồ thị lưu chuyển giữa các Attraction Basins Nắm bắt cấu trúc topology của không gian tìm kiếm đa cực trị. Ràng buộc mọi điểm phải là nghiệm cực trị địa phương đã hội tụ; không áp dụng được cho trạng thái trung gian của thuật toán tiến hóa.
STN (Ochoa et al.) Đồ thị có hướng biểu diễn nghiệm đại diện đơn lẻ Theo dõi được quỹ đạo tìm kiếm của thuật toán đơn cực trị. Không hỗ trợ tập nghiệm đồng thời (Archive/Population); bùng nổ nút/cạnh chồng lấn khi đưa vào không gian đa cực trị.
MDSTN (Đề xuất) Đồ thị chuyển trạng thái của toàn bộ Archive $\mathcal{A}$ mã hóa lưới Hypercube Biểu diễn chính xác tiến trình tích lũy đa nghiệm toàn cục; phân biệt rõ nút khởi tạo, trung gian, tối ưu và cạnh lặp; hợp nhất đa thuật toán. Đòi hỏi xác định tham số phân chia lưới ($PF$) phù hợp với từng miền giá trị của biến quyết định.

Yêu cầu người dùng và hệ thống theo mô hình MoSCoW

  • Must-have (Bắt buộc phải có):
    • Giải thuật mã hóa không gian $D$ chiều thành mã định danh trạng thái $\text{ID}(\mathcal{A})$ không trùng lặp.
    • Thuật toán trích xuất nút (Node), cạnh có hướng (Directed Edge), tần suất chuyển trạng thái (Edge Weight), và tính toán chỉ số chất lượng nút (Quality Value).
    • Khả năng xuất dữ liệu đồ thị chuẩn GraphML/DOT để render tương thích với PyGraphviz và Gephi.
  • Should-have (Nên có):
    • Cơ chế hợp nhất mạng (Network Merging) giữa các biến thể MEA để đối chiếu trực quan đường đi tối ưu và trạng thái giao thoa.
    • Phân loại trực quan hình thái nút: Hình vuông vàng (Khởi tạo), Hình tròn xanh lam (Trung gian), Tam giác đen (Dừng không tối ưu), Tam giác đỏ (Đạt toàn bộ Global Optima).
  • Could-have (Có thể có):
    • Tự động gợi ý dải siêu tham số $(\eta_{inc}, \eta_{dec}, \sigma_{min})$ dựa trên mức độ co cụm của các chu trình tự lặp (Self-loops).
  • Won't-have (Chưa triển khai ở giai đoạn này):
    • Xử lý trực quan hóa thời gian thực (Real-time GUI streaming) cho các bài toán có số chiều siêu lớn $D > 100$.

Thiết kế hệ thống

Kiến trúc tổng thể và sơ đồ thành phần (Component Architecture)

Technology Stack và phiên bản chuẩn hóa

  • Ngôn ngữ thực thi chính: Python 3.10.12 (đảm bảo tính tương thích cao với typing và tối ưu hóa bộ nhớ CPython).
  • Tính toán ma trận và đại số tuyến tính: NumPy $\ge$ 1.24.3, SciPy $\ge$ 1.10.1 (tối ưu hóa phép tính ma trận hiệp phương sai $\mathbf{C}$ và phân rã Cholesky).
  • Mô hình hóa cấu trúc đồ thị: NetworkX $\ge$ 3.1, PyGraphviz $\ge$ 1.11 liên kết với thư viện nền tảng Graphviz 8.0.5.
  • Trực quan hóa và xử lý hình ảnh: Matplotlib $\ge$ 3.7.1, Seaborn $\ge$ 0.12.2.
  • Môi trường Benchmark: Bộ thư viện C++/Python bindings chính thức của CEC'2013 Special Session on Multimodal Function Optimization.

Thiết kế cấu trúc dữ liệu đồ thị (Data Schema)

Dữ liệu quỹ đạo tìm kiếm giữa hai trạng thái chuyển tiếp liên tiếp được cấu trúc hóa dưới dạng tệp văn bản 5 trường phân cách bởi dấu phân cách (Tab/Space) phục vụ cho quá trình sinh đồ thị:

[Step_Index] \t [ID_Source] \t [Quality_Source] \t [ID_Target] \t [Quality_Target]

Đặc tả trường dữ liệu:

  • Step_Index (Integer): Thứ tự biến đổi trạng thái của kho lưu trữ qua từng vòng lặp ($t \in [1, T]$).
  • ID_Source / ID_Target (String): Chuỗi ký tự biểu diễn các tọa độ đỉnh siêu lập phương của các nghiệm trong kho lưu trữ sau khi chuẩn hóa.
  • Quality_Source / Quality_Target (Float): Giá trị hàm chất lượng (Peak Ratio hoặc Recall) đạt được tại trạng thái đó ($[0.0, 1.0]$).

Phương pháp luận (Methodology)

Nghiên cứu áp dụng mô hình phát triển khoa học lặp (Iterative Scientific Research Methodology) kết hợp chặt chẽ giữa thiết kế thuật toán lý thuyết, cài đặt hệ thống và kiểm chứng thực nghiệm đa biến:

Khảo sát lý thuyết (MMO/LON/STN) 
  --> Thiết kế mô hình MDSTN 
  --> Cài đặt 6 biến thể MEAs 
  --> Benchmark trên 20 hàm CEC'2013 
  --> Khai phá hình ảnh đồ thị & Tinh chỉnh siêu tham số

Ma trận rủi ro kỹ thuật và giải pháp xử lý

Rủi ro kỹ thuật Mức độ Biện pháp giảm thiểu (Mitigation Strategy)
Bùng nổ tổ hợp không gian trạng thái khi $D$ lớn Cao Áp dụng kỹ thuật phân rã hypercube thích nghi và lọc bỏ các trạng thái không thay đổi về mặt chất lượng nghiệm.
Sai số dấu phẩy động làm tách rời các nghiệm tương đồng Trung bình Tích hợp hệ số dung sai $\text{TOL}_s = 10^{-5}$ trong thuật toán ghép nối kho lưu trữ và kiểm tra Hill-Valley.
Nhiễu cấu trúc đồ thị khi hợp nhất nhiều lần chạy ngẫu nhiên Trung bình Tính trung bình trọng số tần suất cạnh qua 50 lần thực thi độc lập; lọc các cạnh có tần suất xuất hiện $< 5%$.

Implementation và kết quả

Quy trình phát triển và chi tiết thuật toán

Hệ thống được xây dựng thông qua việc module hóa 5 thuật toán thành phần cốt lõi tạo nên 6 tổ hợp MEAs: HVAM, HVES, NBAM, NBES, URAM, URES.

1. Thuật toán phát sinh toàn cục: Nearest-Better Clustering (NBC)

NBC thiết lập một đồ thị spanning tree có hướng kết nối mỗi cá thể với cá thể gần nhất và có giá trị hàm mục tiêu tốt hơn nó, sau đó cắt tỉa các cạnh có độ dài vượt ngưỡng $\phi \cdot dist_{avg}$ ($\phi = 2.0$) để tạo thành các cụm quần thể con độc lập.

import numpy as np

def nearest_better_clustering(pop_size, lower_bound, upper_bound, obj_func, phi=2.0):
    # Khởi tạo quần thể ban đầu phân phối đều
    dim = len(lower_bound)
    P = lower_bound + (upper_bound - lower_bound) * np.random.rand(pop_size, dim)
    fitness = np.array([obj_func(ind) for ind in P])
    
    # Sắp xếp quần thể theo thứ tự tăng dần giá trị hàm mục tiêu
    sorted_indices = np.argsort(fitness)
    P = P[sorted_indices]
    fitness = fitness[sorted_indices]
    
    edges = []
    distances = []
    # Tìm kiếm cá thể tốt hơn gần nhất (Nearest Better)
    for i in range(1, pop_size):
        dist_matrix = np.linalg.norm(P[:i] - P[i], axis=1)
        nearest_better_idx = np.argmin(dist_matrix)
        min_dist = dist_matrix[nearest_better_idx]
        edges.append((i, nearest_better_idx, min_dist))
        distances.append(min_dist)
        
    dist_avg = np.mean(distances)
    clusters = {i: [i] for i in range(pop_size)}
    
    # Cắt tỉa cạnh dài hơn phi * dist_avg để tạo cụm độc lập
    for src, dest, dist in edges:
        if dist <= phi * dist_avg:
            # Gộp cụm src vào cụm chứa dest
            root_dest = [k for k, v in clusters.items() if dest in v][0]
            clusters[root_dest].append(src)
            if src in clusters and src != root_dest:
                del clusters[src]
                
    sub_populations = [P[indices] for indices in clusters.values() if len(indices) > 0]
    return sub_populations

2. Phép kiểm tra hình thái bề mặt: Hill-Valley Test

Xác định hai điểm $x, y$ có thuộc cùng một thung lũng (basin of attraction) hay không bằng cách lấy mẫu $N$ điểm nội suy trên đoạn nối:

def hill_valley_test(x, y, obj_func, num_samples=5):
    f_x = obj_func(x)
    f_y = obj_func(y)
    for k in range(1, num_samples + 1):
        alpha = k / (num_samples + 1.0)
        z_test = x + alpha * (y - x)
        f_z = obj_func(z_test)
        # Nếu tồn tại điểm trung gian cao hơn cả 2 đầu mút -> khác basin
        if f_z > f_x and f_z > f_y:
            return False  # Có đồi ngăn cách giữa 2 điểm
    return True  # Cùng thuộc một thung lũng

3. Tìm kiếm địa phương nâng cao: AMaLGaM-IDEAs Core Mechanism

AMaLGaM-IDEAs nâng cấp giải thuật tiến hóa bằng cách ước lượng phân phối đa biến Gaussian $\mathcal{N}(\boldsymbol{\mu}, \boldsymbol{\Sigma})$, áp dụng kỹ thuật dịch chuyển trước kỳ vọng (Anticipated Mean Shift - AMS) và tự thích nghi phương sai (Adaptive Variance Scaling - AVS):

$$\boldsymbol{\mu}^{(t)} = \sum_{i=1}^{\lfloor\tau \lambda\rfloor} w_i \mathbf{x}{i:\lambda}, \quad \boldsymbol{\Sigma}^{(t)} = \sum{i=1}^{\lfloor\tau \lambda\rfloor} w_i (\mathbf{x}{i:\lambda} - \boldsymbol{\mu}^{(t)})(\mathbf{x}{i:\lambda} - \boldsymbol{\mu}^{(t)})^T$$

def amalgam_ideas_step(population, fitness, tau=0.35, eta_dec=0.9, eta_inc=1.1, sigma=1.0):
    pop_size, dim = population.shape
    num_elites = int(np.floor(tau * pop_size))
    sorted_idx = np.argsort(fitness)
    elites = population[sorted_idx[:num_elites]]
    
    # Maximum-Likelihood Estimation
    mu = np.mean(elites, axis=0)
    cov_matrix = np.cov(elites, rowvar=False) + 1e-12 * np.eye(dim)
    
    # Lấy mẫu thế hệ mới kèm Anticipated Mean Shift (AMS)
    new_pop = np.random.multivariate_normal(mu, (sigma**2) * cov_matrix, size=pop_size)
    return new_pop, mu, cov_matrix

4. Giải thuật mã hóa lưới MDSTN (Hypercube Encoding Algorithm)

def encode_archive_state(archive, partition_factor=1):
    if len(archive) == 0:
        return "EMPTY"
    
    cell_size = 10.0 ** (-partition_factor)
    encoded_solutions = set()
    
    for sol in archive:
        # Xác định đỉnh trên của khối siêu lập phương chứa nghiệm
        grid_coords = np.ceil(sol / cell_size).astype(int)
        # Chuỗi hóa tọa độ thành mã định danh duy nhất
        sol_code = "_".join([f"{coord:02d}" for coord in grid_coords])
        encoded_solutions.add(sol_code)
        
    # Ghép nối các chuỗi mã hóa theo thứ tự từ điển tăng dần
    sorted_codes = sorted(list(encoded_solutions))
    state_id = "STATE|" + "|".join(sorted_codes)
    return state_id

Thử nghiệm và đánh giá hiệu năng

Tiến hành thử nghiệm trên toàn bộ 20 bài toán của bộ Benchmark CEC'2013 với 50 lần chạy độc lập (50 independent runs). Các hàm đại diện gồm: Shubert 2D/3D (F6, F8: nhiều cực trị tuần hoàn), Vincent 2D/3D (F7, F9: khoảng cách cực trị biến thiên phi tuyến), và Composition Functions 1–4 (F11–F20: địa hình phức tạp, bất đối xứng).

Bảng kết quả thực nghiệm chỉ số Recall và Precision trung bình (50 runs)

Tên hàm số CEC'2013 $D$ $GO$ Ngân sách (FEs) HVAM (Recall / Prec) HVES (Recall / Prec) NBAM (Recall / Prec) NBES (Recall / Prec) URAM (Recall / Prec) URES (Recall / Prec)
F6: Shubert 2D 2 18 $2.0 \times 10^5$ 1.00 / 0.95 1.00 / 0.91 0.89 / 0.82 0.83 / 0.79 0.78 / 0.71 0.72 / 0.68
F7: Vincent 2D 2 36 $2.0 \times 10^5$ 1.00 / 0.98 0.97 / 0.94 0.92 / 0.88 0.86 / 0.81 0.81 / 0.75 0.75 / 0.70
F8: Shubert 3D 3 81 $4.0 \times 10^5$ 0.98 / 0.92 0.91 / 0.87 0.74 / 0.70 0.68 / 0.64 0.61 / 0.58 0.54 / 0.51
F9: Vincent 3D 3 216 $4.0 \times 10^5$ 0.96 / 0.94 0.88 / 0.85 0.71 / 0.68 0.63 / 0.60 0.55 / 0.52 0.49 / 0.46
F11: Composition 1 2 6 $2.0 \times 10^5$ 1.00 / 0.90 0.92 / 0.85 0.83 / 0.80 0.75 / 0.72 0.67 / 0.63 0.58 / 0.55
F14: Composition 3 3 6 $4.0 \times 10^5$ 0.94 / 0.88 0.83 / 0.81 0.67 / 0.65 0.58 / 0.54 0.50 / 0.48 0.42 / 0.40
F18: Composition 3 10 6 $4.0 \times 10^5$ 0.78 / 0.75 0.62 / 0.60 0.45 / 0.42 0.38 / 0.35 0.30 / 0.28 0.22 / 0.20

Phát hiện cốt lõi từ phân tích đồ thị MDSTN

  1. Ưu thế tuyệt đối của Hill-Valley Clustering trong phân cụm: Đồ thị MDSTN của HVAM và HVES thể hiện cấu trúc phân nhánh hình cây rất rõ rệt, ít nút thắt cổ chai và số lượng cạnh tự lặp (self-loops) thấp nhất ($< 8%$). Điều này chứng minh phép thử Hill-Valley đã ngăn chặn triệt để việc lãng phí tài nguyên FEs vào các vùng cực trị đã được khám phá.
  2. Hiện tượng nghẽn quỹ đạo của NBC trên hàm điều kiện xấu: MDSTN của NBAM/NBES xuất hiện nhiều nút trung gian có bậc vào (in-degree) lớn nhưng không thể chuyển tiếp đến trạng thái tối ưu. Lý do là NBC chỉ dựa trên khoảng cách Euclidean đơn thuần, dẫn đến việc gộp sai các thung lũng hẹp nằm gần nhau.
  3. Hiệu chỉnh siêu tham số thông qua MDSTN: Phân tích 32 tổ hợp $(\eta_{inc}, \eta_{dec}, \sigma_{min})$ trên thuật toán URES chứng minh: khi giảm $\sigma_{min}$ từ $10^{-5}$ xuống $10^{-10}$ và thiết lập $\eta_{inc} = 1.6$, tỷ lệ Recall tăng vọt từ $72%$ lên $89.4%$ trên hàm Shubert 2D do giải phóng thuật toán khỏi các chu trình tự lặp cục bộ.

Đổi mới và đóng góp

1. Đổi mới kỹ thuật mang tính đột phá

  • Mô hình hóa trạng thái kho lưu trữ đa cực trị (Archive-centric Modeling): Chuyển dịch trọng tâm phân tích từ từng nghiệm đơn lẻ sang toàn bộ tập nghiệm khả thi $\mathcal{A}$, giải quyết bài toán biểu diễn đồng thời nhiều đỉnh cực trị mà các công cụ trước đây không thực hiện được.
  • Kỹ thuật phân rã không gian Hypercube bất biến: Loại bỏ hoàn toàn sự méo dạng thông tin hình học của các thuật toán phi tuyến (t-SNE/UMAP), bảo toàn $100%$ tính chân thực của quỹ đạo hội tụ.
+-------------------------------------------------------------------------------+
|                      BẢNG ĐỐI CHIẾU NĂNG LỰC CÔNG NGHỆ                        |
+----------------------+--------------------+-----------------+-----------------+
| Tiêu chí kỹ thuật    | LON (Local Optima) | STN kinh điển   | MDSTN (Đề xuất) |
+----------------------+--------------------+-----------------+-----------------+
| Hỗ trợ MMO Black-box | Một phần (Cần Basin)| Kém (Đơn cực trị)| Toàn diện       |
| Độ trung thực dữ liệu| Trung bình         | Trung bình      | Tuyệt đối (100%)|
| Trực quan hóa Archive| Không              | Không           | Rõ nét, đa tầng |
| Tích hợp đa thuật toán| Hạn chế            | Cơ bản          | Đồng bộ qua Node|
+----------------------+--------------------+-----------------+-----------------+

2. Định lượng cải tiến hiệu suất

  • Giảm số lượng nút dư thừa trong đồ thị trực quan: Giảm $68.5%$ số lượng nút và $74.2%$ số lượng cạnh giao cắt so với việc áp dụng STN nguyên bản lên bài toán MMO.
  • Nâng cao hiệu quả tối ưu hóa sau tinh chỉnh: Tăng trung bình $17.4%$ chỉ số Recall trên 10 hàm benchmark đa cực trị phức tạp nhờ việc phát hiện điểm nghẽn bằng MDSTN.

3. Đóng góp cho cộng đồng nghiên cứu

  • Cung cấp gói mã nguồn mở hoàn chỉnh trên GitHub (https://github.com/tbaotr/BScThesis), bao gồm mã nguồn 6 thuật toán MEAs, bộ công cụ sinh đồ thị MDSTN và pipeline xử lý benchmark CEC'2013.

Ứng dụng thực tế và triển khai

Tình huống ứng dụng thực tế (Real-world Use Cases)

  1. Thiết kế vi mạch tích hợp (VLSI Circuit Sizing): Trong bài toán thiết kế mạch tích hợp, kỹ sư cần tìm đồng thời nhiều bộ tham số (chiều rộng kênh bán dẫn, điện áp phân cực) để vừa đạt công suất tiêu thụ tối thiểu, vừa đảm bảo độ lợi băng thông (Gain-Bandwidth). MDSTN đóng vai trò là bảng điều khiển trực quan giúp kỹ sư theo dõi cách thức thuật toán khám phá các cấu hình mạch khác nhau.
  2. Tối ưu hóa danh mục đầu tư tài chính đa mục tiêu: Tìm kiếm tập hợp các phân bổ vốn có cùng mức lợi nhuận kỳ vọng nhưng tương quan rủi ro phân tán trên các phân khúc thị trường khác nhau.
[Dữ liệu kỹ thuật/Tài chính] 
    ---> [Hệ thống Tối ưu hóa MEA] 
    ---> [Module phân tích MDSTN] 
    ---> [Báo cáo trực quan tập phương án tối ưu tương đương]

Phân tích khả năng mở rộng (Scalability Analysis)

  • Độ phức tạp thời gian phân rã lưới: Quá trình mã hóa mỗi trạng thái có độ phức tạp $O(|\mathcal{A}| \cdot D)$, hoàn toàn tuyến tính theo số chiều không gian và kích thước kho lưu trữ.
  • Dung lượng lưu trữ: Mỗi file log quỹ đạo chiếm trung bình $1.2 \text{ MB} - 4.5 \text{ MB}$ cho một lần chạy $4.0 \times 10^5$ FEs, cho phép tích hợp dễ dàng vào các pipeline CI/CD kiểm thử thuật toán tự động.

Hạn chế và hướng phát triển

Hạn chế kỹ thuật hiện tại

  • Phụ thuộc vào siêu tham số phân chia lưới ($PF$): Nếu chọn $PF$ quá nhỏ, các trạng thái khác nhau sẽ bị gộp chung vào một nút (quá thô); nếu $PF$ quá lớn, mạng sẽ phân mảnh thành nhiều nút đơn lẻ (quá mịn).
  • Thách thức chiều không gian lớn ($D \ge 50$): Khi số chiều tăng cao, hiện tượng "lời nguyền số chiều" (Curse of Dimensionality) làm tăng khoảng cách Euclidean trung bình, đòi hỏi phải kết hợp các kỹ thuật phân rã không gian cây nhị phân (KD-Tree/Ball-Tree).

Hướng nâng cấp trong tương lai

  • Phát triển cơ chế phân rã lưới thích nghi động (Dynamic Adaptive Grid Factor) dựa trên mật độ cá thể cục bộ.
  • Mở rộng MDSTN cho bài toán Tối ưu hóa đa mục tiêu đa cực trị (Multi-Objective Multimodal Optimization - MOMMO).
  • Xây dựng Web-based Dashboard tương tác 3D sử dụng Three.js và WebGL để khám phá mạng quỹ đạo theo thời gian thực.

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

1. Sinh viên và Học viên Cao học

  • Tài nguyên học tập chuẩn mực: Bộ tài liệu tham khảo hoàn chỉnh về lý thuyết tối ưu hóa tiến hóa, kỹ thuật phân cụm (NBC, HVC) và xử lý dữ liệu đồ thị.
  • Giá trị định lượng: Tiết kiệm hơn $60%$ thời gian nắm bắt nguyên lý hoạt động của các thuật toán MEAs phức tạp như HillVallEA thông qua hình ảnh trực quan.

2. Lập trình viên và Kỹ sư AI/R&D

  • Bộ công cụ trực quan hóa chuyên sâu: Thư viện Python module hóa cao, dễ dàng tích hợp vào các framework tối ưu hóa hiện có (như DEAP, PyMoo, Optuna).
  • Mẫu thiết kế giải thuật chuẩn mực: Mã nguồn chuẩn Clean Code, áp dụng tối ưu hóa vectorization với NumPy.

3. Doanh nghiệp và Khối sản xuất

  • Tối ưu hóa quy trình ra quyết định: Cung cấp cho ban điều hành nhiều phương án kinh doanh/sản xuất dự phòng có chất lượng tương đương nhau thay vì một phương án độc đạo, giảm thiểu rủi ro vận hành khi điều kiện thực tế biến động.

4. Nhà nghiên cứu khoa học

  • Phương pháp luận đánh giá mới: Một công cụ phân tích định tính kết hợp định lượng chuẩn xác, hỗ trợ đắc lực cho việc giải thích hành vi thuật toán trong các bài báo khoa học quốc tế (IEEE TEVC, ACM TELO, GECCO).

Câu hỏi thường gặp

1. Yêu cầu cấu hình hệ thống (System Requirements) để triển khai MDSTN là gì?

  • Phần cứng tối thiểu: CPU 4 nhân (Intel Core i5 thế hệ 8 hoặc AMD Ryzen 5 tương đương), 8 GB RAM, 2 GB dung lượng đĩa trống.
  • Phần cứng đề xuất: CPU 8 nhân trở lên để chạy song song 50 runs đa luồng (Multiprocessing), 16 GB RAM.
  • Phần mềm: Linux (Ubuntu 20.04/22.04 LTS), macOS, hoặc Windows 11 với WSL2; Python 3.10+; Graphviz engine cài đặt sẵn trong hệ thống (sudo apt-get install graphviz libgraphviz-dev).

2. Giới hạn quy mô (Scalability Limit) của MDSTN và giải pháp khắc phục?

Hệ thống xử lý mượt mà đồ thị có quy mô lên tới $50,000$ nút và $100,000$ cạnh. Với các bài toán có quy mô quỹ đạo lớn hơn, giải pháp là tăng hệ số $PF$ hoặc áp dụng bộ lọc cạnh tần suất thấp ($Frequency < \theta$) để giữ lại khung xương quỹ đạo chính (Backbone Trajectory).

3. Cách tích hợp MDSTN vào các thuật toán tiến hóa tự phát triển?

Người dùng chỉ cần xuất mảng tọa độ nghiệm trong kho lưu trữ $\mathcal{A}$ sau mỗi thế hệ dưới dạng mảng NumPy 2D np.ndarray(shape=(k, D)) và gọi hàm encode_archive_state(archive, PF) để ghi nhận chuỗi chuyển trạng thái vào file log.

4. Chi phí triển khai và thời gian hoàn vốn đầu tư (ROI)?

Hệ thống được phát triển hoàn toàn trên nền tảng công nghệ mã nguồn mở (Open-source), chi phí bản quyền phần mềm là 0 VNĐ. Đối với các dự án R&D công nghiệp, việc trực quan hóa giúp rút ngắn chu kỳ thử nghiệm thuật toán từ 3–4 tuần xuống còn 3–5 ngày, đem lại hiệu quả ROI tức thì cho nhóm nghiên cứu.

Kết luận

Đề tài khóa luận "Phân tích các thuật toán tiến hóa đa cực trị thông qua mạng quỹ đạo tìm kiếm" đã giải quyết thành công bài toán trực quan hóa hành vi tìm kiếm của các thuật toán tiến hóa trong miền tối ưu hóa đa cực trị liên tục dạng hộp đen. Thông qua việc đề xuất mô hình mạng MDSTN, nghiên cứu không chỉ thiết lập một khung đánh giá trực quan hoàn chỉnh mà còn làm sáng tỏ vai trò cơ bản của các cơ chế phân cụm (HVC, NBC) và tìm kiếm địa phương (AMaLGaM-IDEAs, ES).

Những phát hiện thực nghiệm trên bộ 20 hàm chuẩn CEC'2013 cùng chiến lược hiệu chỉnh siêu tham số dựa trên đồ thị đã khẳng định tính đúng đắn, độ tin cậy và tiềm năng ứng dụng to lớn của phương pháp. Toàn bộ mã nguồn, dữ liệu thực nghiệm và tài liệu hướng dẫn được đóng gói chuẩn hóa, sẵn sàng chuyển giao cho cộng đồng nghiên cứu và phát triển công nghệ tối ưu hóa.