Tối ưu hóa đa hình thức khác gì so với tối ưu hóa đa mục tiêu?

Tối ưu hóa đa hình thức tìm kiếm nhiều nghiệm trong không gian biến số cho một hoặc nhiều hàm mục tiêu, trong khi tối ưu hóa đa mục tiêu giải quyết sự xung đột giữa nhiều mục tiêu khác nhau.

Tại sao các giải thuật di truyền tiêu chuẩn dễ thất bại khi tối ưu hàm đa đỉnh?

Giải thuật di truyền tiêu chuẩn chịu ảnh hưởng của hiện tượng trôi dạt di truyền và áp lực chọn lọc, khiến toàn bộ quần thể nhanh chóng hội tụ sớm về một đỉnh duy nhất và bỏ sót các cực trị khác.

Hai chỉ số PR và SR trong đánh giá tối ưu hóa đa đỉnh có ý nghĩa gì?

Chỉ số PR đo tỷ lệ phần trăm các đỉnh tối ưu được thuật toán tìm thấy trên tổng số đỉnh, còn chỉ số SR thể hiện tỷ lệ số lần chạy tìm ra trọn vẹn toàn bộ các đỉnh của bài toán.

Tối ưu hóa đa hình thức (multimodal optimization) là gì?

Tối ưu hóa đa hình thức là một phân ngành của lý thuyết tối ưu hóa và tính toán tiến hóa, tập trung vào việc tìm kiếm và duy trì đồng thời nhiều nghiệm tối ưu cục bộ hoặc toàn cục trong một lần thực thi thuật toán duy nhất. Thay vì chỉ hội tụ về một nghiệm duy nhất như các phương pháp truyền thống, phương pháp này bảo tồn tính đa dạng cấu trúc của quần thể nghiệm nhằm cung cấp nhiều phương án tương đương cho người ra quyết định. Bài viết trình bày cơ sở toán học, các kỹ thuật phân vùng sinh thái, tiêu chuẩn đánh giá thực nghiệm cùng những hạn chế và định hướng nghiên cứu hiện đại của bài toán này.

Bản chất toán học của bài toán tối ưu hóa đa đỉnh

Trong tối ưu hóa tham số thực, bài toán tìm cực trị thường được mô tả thông qua việc tìm kiếm các điểm trong không gian biến quyết định sao cho giá trị hàm mục tiêu đạt cực đại hoặc cực tiểu. Đối với hàm đơn đỉnh, không gian tìm kiếm chỉ tồn tại một điểm cực trị duy nhất, do đó các thuật toán dựa trên đạo hàm hoặc tìm kiếm cục bộ có thể dễ dàng tiếp cận lời giải tối ưu. Tuy nhiên, đối với hàm đa cực trị, địa hình thích nghi chứa đựng vô số đỉnh và thung lũng xen kẽ.

Giả sử hàm mục tiêu liên tục được định nghĩa trên không gian tìm kiếm đa chiều:

f: S \subseteq \mathbb{R}^D \rightarrow \mathbb{R}

với $S$ là không gian tìm kiếm giới hạn và $D$ là số chiều của bài toán. Một điểm $x^* \in S$ được gọi là điểm cực tiểu cục bộ nếu tồn tại một lân cận bán kính $\epsilon > 0$ sao cho:

f(x^*) \le f(x), \quad \forall x \in S \text{ thỏa mãn } \|x - x^*\| < \epsilon

Điểm $x^*$ là nghiệm tối ưu toàn cục nếu bất đẳng thức trên thỏa mãn với mọi $x$ trong toàn bộ không gian $S$ . Trong bài toán tối ưu hóa đa đỉnh, tập hợp nghiệm tối ưu toàn cục có thể chứa nhiều phần tử rời rạc có cùng giá trị hàm mục tiêu tối ưu. Mục tiêu của thuật toán không chỉ dừng lại ở việc xác định một phần tử bất kỳ mà phải định vị đầy đủ toàn bộ tập hợp các nghiệm tối ưu toàn cục cũng như các nghiệm tối ưu cục bộ chất lượng cao.

Theo khảo sát của Das và cộng sự (2011), hàm thử nghiệm Himmelblau trong không gian 2 chiều là một ví dụ tiêu biểu cho địa hình đa đỉnh đối xứng với 4 điểm cực tiểu toàn cục riêng biệt:

f(x, y) = (x^2 + y - 11)^2 + (x + y^2 - 7)^2

với $x$ và $y$ là hai tọa độ biến thực. Giá trị hàm mục tiêu tại cả 4 điểm cực tiểu toàn cục này đều đạt mức tuyệt đối bằng 0. Nếu áp dụng thuật toán tìm kiếm truyền thống, toàn bộ quần thể sẽ nhanh chóng rơi vào một điểm cực tiểu duy nhất và bỏ sót hoàn toàn 3 điểm tối ưu còn lại.

Thách thức hội tụ sớm và hiện tượng trôi dạt di truyền

Khi áp dụng các giải thuật di truyền tiêu chuẩn vào bài toán đa đỉnh, một rào cản nền tảng phát sinh từ hiện tượng trôi dạt di truyền. Trong quá trình chọn lọc tự nhiên mô phỏng, các cá thể có độ thích nghi cao hơn sẽ nhanh chóng chiếm ưu thế và nhân bản qua các thế hệ. Áp lực chọn lọc kết hợp với tác động ngẫu nhiên của toán tử lai ghép khiến toàn bộ quần thể mất đi tính đa dạng kiểu gen và kiểu hình, dẫn tới sự sụp đổ quần thể về một lưu vực hấp dẫn duy nhất.

Hiện tượng hội tụ sớm này ngăn cản việc khám phá các phân vùng tiềm năng khác trong không gian tìm kiếm. Để khắc phục sự trôi dạt di truyền, cộng đồng tính toán tiến hóa đã phát triển các cơ chế phân vùng sinh thái nhân tạo, lấy cảm hứng từ sự hình thành loài trong tự nhiên. Mỗi loài sinh học trong môi trường sống tự nhiên đều thích nghi với một ngách sinh thái cụ thể để tránh sự cạnh tranh trực tiếp, từ đó duy trì sự cộng sinh của nhiều dạng sống khác nhau.

Các kỹ thuật phân vùng sinh thái kinh điển

Theo tổng quan toàn diện của Li và cộng sự (2017) trên tạp chí IEEE Transactions on Evolutionary Computation, các phương pháp phân vùng sinh thái được thiết kế nhằm duy trì các phân quần thể độc lập khám phá song song nhiều đỉnh tối ưu. Bốn kỹ thuật nền tảng bao gồm:

1. Kỹ thuật chia sẻ độ thích nghi

Kỹ thuật chia sẻ độ thích nghi làm suy giảm giá trị thích nghi thô của các cá thể nằm trong cùng một vùng lân cận. Hàm suy giảm được tính toán dựa trên khoảng cách giữa các cá thể. Nếu một đỉnh tập trung quá nhiều cá thể, độ thích nghi chia sẻ của từng cá thể sẽ giảm mạnh, buộc các cá thể mới sinh ra phải di chuyển sang các đỉnh khác ít đông đúc hơn để tìm kiếm độ thích nghi cao hơn.

Độ thích nghi chia sẻ của cá thể thứ $i$ được xác định theo công thức:

f_{sh}(i) = \frac{f(i)}{\sum_{j=1}^{N_p} \operatorname{sh}(d_{ij})}

với $f(i)$ là giá trị độ thích nghi gốc của cá thể $i$ , $N_p$ là quy mô quần thể, $d_{ij}$ là khoảng cách không gian giữa cá thể $i$ và cá thể $j$ , và $\operatorname{sh}(d_{ij})$ là hàm chia sẻ tam giác phụ thuộc vào bán kính ngách. Hạn chế cốt lõi của phương pháp này là độ phức tạp tính toán khoảng cách theo cặp và sự phụ thuộc nghiêm ngặt vào tham số bán kính ngách cố định.

2. Kỹ thuật dồn cụm

Phương pháp dồn cụm bảo tồn tính đa dạng bằng cách chỉ cho phép cá thể con cạnh tranh thay thế với cá thể cha mẹ hoặc cá thể tương đồng nhất trong một tập hợp mẫu ngẫu nhiên. Trong phương pháp dồn cụm xác định, một tập hợp cá thể con sinh ra từ phép lai ghép sẽ so sánh khoảng cách với các cá thể cha mẹ tương ứng. Cá thể con chỉ thay thế cha mẹ nếu nó có độ thích nghi vượt trội, qua đó bảo toàn cấu trúc phân bố không gian qua từng chu kỳ tiến hóa mà không đòi hỏi tính toán khoảng cách toàn thể.

3. Kỹ thuật dọn dẹp phân vùng

Phương pháp dọn dẹp phân vùng áp dụng nguyên lý người chiến thắng nhận tất cả trong từng vùng bán kính xác định. Sau khi sắp xếp quần thể theo thứ tự giảm dần của độ thích nghi, cá thể có độ thích nghi cao nhất được chỉ định làm đại diện đỉnh. Mọi cá thể khác nằm trong phạm vi bán kính dọn dẹp xung quanh cá thể đại diện sẽ bị đặt độ thích nghi về mức triệt tiêu. Kỹ thuật này giúp giải phóng tài nguyên tính toán khỏi các nghiệm dư thừa tập trung xung quanh một đỉnh đã được định vị.

4. Kỹ thuật hình thành loài

Kỹ thuật hình thành loài phân chia quần thể thành các nhóm tách biệt dựa trên khoảng cách tới các cá thể hạt giống. Các cá thể hạt giống đóng vai trò tâm điểm của loài. Các toán tử lai ghép và đột biến chủ yếu diễn ra nội bộ bên trong từng loài, ngăn chặn hiện tượng sinh ra các cá thể con lai không khả thi nằm ở các thung lũng giữa hai đỉnh tối ưu xa nhau.

Bảng so sánh đặc tính các kỹ thuật phân vùng

Bảng tổng hợp dưới đây phân tích các đặc trưng vận hành, ưu điểm và hạn chế của bốn phương pháp phân vùng sinh thái nền tảng:

Phương pháp	Cơ chế duy trì đa dạng	Độ phức tạp tính toán	Hạn chế chính
Chia sẻ độ thích nghi	Suy giảm độ thích nghi theo mật độ lân cận	Bậc hai theo quy mô quần thể	Nhạy cảm cao với tham số bán kính ngách
Dồn cụm xác định	Thay thế chọn lọc theo khoảng cách cha con	Tuyến tính theo quy mô quần thể	Khả năng duy trì các đỉnh nhỏ còn hạn chế
Dọn dẹp phân vùng	Triệt tiêu độ thích nghi của các nghiệm lân cận	Phụ thuộc vào thuật toán sắp xếp độ thích nghi	Dễ loại bỏ nhầm các nghiệm tiềm năng chưa hội tụ
Hình thành loài	Phân nhóm quần thể quanh các cá thể hạt giống	Trung bình theo số lượng loài được hình thành	Cần xác định bán kính nhận diện loài phù hợp

Tiêu chuẩn đánh giá và bộ hàm thử nghiệm chuẩn

Để đánh giá định lượng năng lực của các thuật toán tối ưu hóa đa đỉnh, hội nghị quốc tế CEC 2013 đã thiết lập một bộ tiêu chuẩn gồm 20 bài toán thử nghiệm đa dạng do Li và cộng sự xây dựng. Bộ hàm này bao gồm các hàm đa thức, hàm tuần hoàn, hàm xoay và hàm dịch chuyển với số lượng đỉnh từ vài điểm đối xứng đến hàng trăm điểm phân bố bất đối xứng trong không gian nhiều chiều.

Theo chuẩn quy định trong nghiên cứu của Li và cộng sự (2017), hiệu năng của một thuật toán đa đỉnh được lượng hóa qua hai chỉ số cốt lõi:

Tỷ lệ đỉnh tìm được (Peak Ratio, PR): Đo lường tỷ lệ phần trăm trung bình giữa số lượng đỉnh tối ưu mà thuật toán định vị thành công trên tổng số đỉnh tối ưu thực tế đã biết trước, tính bình quân qua nhiều lần chạy độc lập.
Tỷ lệ thành công (Success Rate, SR): Tỷ lệ phần trăm số lần chạy mà thuật toán tìm ra trọn vẹn toàn bộ các nghiệm tối ưu toàn cục của bài toán mà không bỏ sót bất kỳ đỉnh nào.

Một đỉnh được coi là đã tìm thấy thành công nếu khoảng cách Euclid từ nghiệm tốt nhất của thuật toán tới nghiệm tối ưu lý thuyết nhỏ hơn một ngưỡng sai số xác định trước (thường quy ước ngưỡng chính xác đạt mức dung sai chặt).

Các hướng phát triển thuật toán hiện đại

Nghiên cứu về tối ưu hóa đa đỉnh đã đạt được những bước tiến quan trọng nhằm khắc phục sự phụ thuộc vào tham số hình học cố định:

Thuật toán tối ưu tâm niching thích nghi

Đáng chú ý, công trình của Jiang và cộng sự (2023) công bố trên tạp chí IEEE Transactions on Cybernetics đề xuất thuật toán tối ưu tâm niching thích nghi. Các tác giả chỉ ra rằng việc cố định bán kính ngách là nguyên nhân khiến các phương pháp truyền thống gặp khó khăn khi xử lý các bài toán có khoảng cách giữa các đỉnh không đồng đều. Thuật toán này tối ưu hóa tâm ngách trực tuyến thông qua việc kết hợp độ đo thích nghi - entropy và cơ chế đồng tiến hóa định hướng ngách, giúp nâng cao đáng kể tỷ lệ đỉnh tìm được trên bộ 20 hàm thử nghiệm tiêu chuẩn.

Mở rộng sang bài toán đa mục tiêu đa đỉnh

Theo tổng quan của Tanabe và Ishibuchi (2020) trên tạp chí IEEE Transactions on Evolutionary Computation, bài toán tối ưu hóa đa mục tiêu đa đỉnh nghiên cứu các hệ thống có nhiều nghiệm tối ưu trong không gian quyết định nhưng ánh xạ về cùng một mặt biên Pareto trong không gian mục tiêu. Các tác giả nhấn mạnh rằng các thuật toán tiến hóa đa mục tiêu tiêu chuẩn thường bỏ sót các nghiệm tương đương này do áp lực chọn lọc chỉ tập trung vào không gian mục tiêu, đòi hỏi phải tích hợp cơ chế phân vùng chuyên biệt trong không gian quyết định để bảo tồn trọn vẹn cấu trúc nghiệm.

Ứng dụng thực tiễn trong kỹ thuật và khoa học dữ liệu

Khả năng cung cấp đồng thời nhiều nghiệm tối ưu mang lại giá trị thực tiễn to lớn trong nhiều ngành công nghiệp và nghiên cứu khoa học:

Thiết kế kỹ thuật cơ khí và kết cấu: Khi thiết kế khung dàn chịu lực hoặc động cơ hàng không, các giải pháp tối ưu về mặt lý thuyết có thể gặp trở ngại khi chế tạo thực tế do giới hạn công nghệ gia công. Việc sở hữu danh mục nhiều phương án tương đương giúp kỹ sư linh hoạt thay thế giải pháp khi điều kiện sản xuất thay đổi.
Thiết kế phân tử thuốc và hóa sinh: Trong nghiên cứu dược lý, nhiều cấu trúc phân tử khác nhau có thể cùng thể hiện hoạt tính sinh học ức chế mục tiêu tương đương nhau. Tuy nhiên, các phân tử này có thể khác biệt lớn về độc tính, độ hòa tan hoặc chi phí tổng hợp. Tối ưu hóa đa đỉnh giúp xác định toàn bộ các phối tử tiềm năng trước khi tiến hành thử nghiệm lâm sàng tốn kém.
Lựa chọn đặc trưng trong máy học: Khi huấn luyện mô hình dự báo trên tập dữ liệu nhiều chiều, thường tồn tại nhiều tập con đặc trưng khác nhau mang lại độ chính xác phân loại tương đương. Thuật toán đa đỉnh giúp phát hiện các cấu hình đặc trưng thay thế để triển khai linh hoạt theo nguồn dữ liệu cảm biến sẵn có.

Hạn chế và các bài toán mở

Mặc dù đạt nhiều thành tựu lý thuyết, bài toán tối ưu hóa đa hình thức vẫn đối mặt với những rào cản kỹ thuật cơ bản:

Lời nguyền số chiều: Khi số chiều biến quyết định tăng cao, thể tích không gian tìm kiếm bùng nổ theo hàm mũ. Khoảng cách Euclid giữa các cá thể mất dần ý nghĩa phân biệt, khiến các kỹ thuật niching dựa trên khoảng cách hình học suy giảm hiệu quả nghiêm trọng.
Chi phí đánh giá hàm mục tiêu: Trong các bài toán mô phỏng vật lý phức tạp (như tính toán động lực học chất lưu hoặc phân tích phần tử hữu hạn), mỗi lần gọi hàm mục tiêu đòi hỏi thời gian tính toán rất lớn. Việc phân tán tài nguyên để nuôi dưỡng đồng thời nhiều phân quần thể có thể làm chậm tốc độ hội tụ của từng đỉnh riêng lẻ.
Khó khăn khi số lượng đỉnh không biết trước: Đa số các thuật toán tiến hóa vẫn đòi hỏi người dùng ước lượng sơ bộ quy mô quần thể đủ lớn để bao phủ các đỉnh. Nếu số lượng đỉnh thực tế vượt xa kích thước quần thể, hiện tượng cạnh tranh loại trừ sẽ dẫn đến việc bỏ sót các nghiệm quan trọng.