Luận án tốt nghiệp

4

Phần 0

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.

Phần 1

TỔNG QUAN

I. Khái quát:

Phần mềm áp dụng giải thuật Tìm Kiếm Ngẫu Nhiên Theo Xác Suất để tìm ra các đáp số tối ưu cho bài toán một mục tiêu (Bài toán Min hoặc bài toán Max). Tuy nhiên, phân mềm không đưa ra các đáp số đã tìm được là tối ưu nhất, chỉ là tương đối.

Mục đích của phần mềm này là:

v Đưa ra đáp số tối ưu cho bài toán một mục tiêu. Từ đó, có thể giúp mọi người giải quyết vấn đề của họ.

v Giúp người học giải các bài toán tối ưu bằng máy tính.

v Phạm vi sử dụng:

Chương trình sẽ được sử dụng trong các trường học để giúp cho người học tìm ra các đáp án tối ưu cho bài toán tối ưu với độ chính xác cao nhất.

Sử dụng trong việc tìm ra phương án tối ưu để giải quyết các vấn đề phức tạp.

II. Người sử dụng:

Các lập trình viên, người phân tích thiết kế và mọi người.

III. Nhiệm vụ:

Tìm ra các phương án tối ưu cho bài toán một mục tiêu.

Ngôn ngữ cài đặt cho chương trình là Visual Basic 6.0