SỬ DỤNG GIẢI THUẬT TÌM KIẾM THEO XÁC SUẤT GIẢI MỘT
LỚP BÀI TOÁN TỐI ƯU HAY NHIỀU MỤC TIÊU
Trần Văn Hạo, Nguyễn Hữu Thông
Khoa Toán-Tin, Đại học Sư phạm Tp. HCM
thong_nh2002@yahoo.com

Tóm tắt
    Xét một lớp bài toán tối ưu một mục tiêu có tính chất sau: Tồn tại một số k (1≤k<n) cố định không phụ thuộc vào kích thước n của bài toán sao cho chỉ cần chọn k biến để thay đổi giá trị thì có khả năng tìm được một lời giải tốt hơn lời giải hiện hành, ký hiệu lớp bài toán này là Ok. Bài báo này đề xuất một kỹ thuật tối ưu số mới, giải thuật Tìm Kiếm Theo Xác Suất (TKTXS), để giải các bài toán tối ưu một mục tiêu thuộc lớp Ok. Giải thuật TKTXS sử dụng các xác suất để điều khiển quá trình tìm kiếm các lời giải tối ưu. Chúng tôi tính toán các xác suất cho khả năng xuất hiện một lời giải tốt hơn lời giải hiện hành trong mỗi lần lặp của giải thuật, và khi thực thi giải thuật TKTXS chúng tôi tạo các điều kiện tốt cho sự xuất hiện này xảy ra. Chúng tôi đã thử nghiệm hướng tiếp cận này bằng cách áp dụng giải thuật TKTXS trên một số bài toán tối ưu thử nghiệm một và nhiều mục tiêu, và chúng
tôi đã tìm được các kết quả tốt rất ổn định.

    Từ khoá: Tối ưu số, Ngẫu nhiên, Xác suất

A SEARCH VIA PROBABILITY ALGORITHM FOR SOLVING A
CLASS OF SINGLE OR MULTI-OBJECTIVE OPTIMAL PROBLEMS
Tran Van Hao, Nguyen Huu Thong
Faculty of Mathemetics and Computer Science, HCMC University of Pedagogy
thong_nh2002@yahoo.com

Abstract
    We consider a class of single-objective optimization problems having the character: there is a fixed number k (1≤k<n) that is independent of the size n of the problem such that if we only need to change values of k variables then it has the ability to find a better solution than the current one, the class of problems is signed Ok. This paper proposes a new numerical optimization technique, Search via Probability (SVP) algorithm, for solving single-objective optimization problems of the class Ok. The SVP algorithm uses probabilities to control the process of searching for optimal solutions. We calculate probabilities of the appearance of a better solution than the current one on each of iterations, and on the performance of SVP algorithm we create good conditions for its appearance. We tested this approach by implementing the SVP algorithm on some test single-objective and multi-objective optimization problems, and we found good and very stable results.

    Key words: Numerical optimization, Stochastic, Probability.