Đồ Án Tối ưu số cho bài toán tối ưu một mục tiêu

MỞ ĐẦU


Ngày nay, các bài toán tối ưu thường xuất hiện trong kinh tế và kỹ thuật, chúng có nhiều ứng dụng rất rộng rãi và đa dạng.

Trên thế giới có rất nhiều giải thuật để giải các bài toán tối ưu. Trong đó, các giải thuật tiến hóa áp dụng cho các bài toán tối ưu một mục tiêu hay đa mục tiêu đã chứng tỏ tính hiệu quả của nó một cách rộng rãi trong những năm gần đây thông qua một số lượng lớn các áp dụng. Tuy nhiên, hầu hết các nghiên cứu hiện hành trên các ứng dụng của giải thuật tiến hóa để giải các bài toán tối ưu một hay nhiều mục tiêu đều tập trung trên các chiến lược xử lý các hàm mục tiêu, gán giá trị fitness và chọn lọc nhằm cố gắng đạt được mục đích là hướng dẫn việc tìm kiếm của giải thuật đến một miền thu hẹp có chứa lời giải tối ưu đối với bài toán tối ưu một mục tiêu hay biên tối ưu Pareto đối với bài toán tối ưu đa mục tiêu.

Tuy nhiên các lời giải tìm được thường là các lời giải xấp xỉ khá tốt nhưng không phải lời giải tối ưu (một mục tiêu) hay tối ưu Pareto (đa mục tiêu). Mặc dù các toán tử sinh sản như lai ghép và đột biến đã được cải tiến rất nhiều nhưng chúng vẫn sản sinh ra các cá thể con mà hoàn toàn không biết đến các cá thể con đó có khả năng tốt hơn hay xấu hơn cha mẹ của chúng như thế nào. Nói cách khác, lý do để các giải thuật tiến hóa thường không đạt được các lời giải tối ưu (một mục tiêu) hay tối ưu Pareto (đa mục tiêu) là các toán tử di truyền như lai ghép và đột biến theo kiểu truyền thống không đủ mạnh để sản sinh ra các cá thể tốt nhất như mong muốn.

Để vượt qua khó khăn đó, người ta đề xuất một hướng tiếp cận mới, được gọi là giải thuật Tìm Kiếm Ngẫu Nhiên Theo Xác Suất (TKNNTXS), để giải các bài toán tối ưu một hay nhiều mục tiêu. Hướng tiếp cận này có những đặc điểm sau
- Không cần thiết kế một hàm phụ trợ như các hàm phạt. Việc xử lý các hàm mục tiêu và các ràng buộc được tách biệt nhau. Xử lý trực tiếp trên các chữ số của biến quyết định để phát sinh lời giải khả thi tốt hơn và sử dụng chính các hàm mục tiêu làm hàm đo độ tốt của lời giải.

- Không sử dụng kỹ thuật di truyền truyền thống như lai ghép và đột biến tại một hay nhiều điểm. Việc sản sinh và tìm kiếm lời giải tối ưu là ngẫu nhiên được hướng dẫn bởi xác suất.