ĐẠI HỌC QUỐC GIA TP. HỒ CHÍ MINH TRƯỜNG ĐẠI HỌC BÁCH KHOA --------------------------------------- NGU ỄN N TRỌNG ƯỚ Ư NG Ệ SỐ Ư NG TR N W NT RS ẰNG T UR ST Chuyên ngành : Khoa học máy tính Mã số: 62480101 LUẬN VĂN T ẠC SĨ THÀNH PHỐ HỒ CHÍ MINH, tháng 07 năm 2014 CÔNG TRÌNH ĐƢỢC HOÀN THÀNH TẠI TRƢỜNG ĐẠI HỌC BÁCH KHOA –ĐHQG –HCM Cán bộ hƣớng dẫn khoa học: PGS.TS Dƣơng Tuấn Anh (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 1 : TS. Võ Đình Bảy (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Cán bộ chấm nhận xét 2 : TS. Lƣ Nhật Vinh (Ghi rõ họ, tên, học hàm, học vị và chữ ký) Luận văn thạc sĩ đƣợc bảo vệ tại Trƣờng Đại học Bách Khoa, ĐHQG Tp.
HCM ngày 14 tháng 07 năm 2014 Thành phần Hội đồng đánh giá luận văn thạc sĩ gồm: (Ghi rõ họ, tên, học hàm, học vị của Hội đồng chấm bảo vệ luận văn thạc sĩ) 1. Dƣơng Tuấn Anh 2. Nguyễn Văn Minh Mẫn 3. Huỳnh Tƣờng Nguyên Xác nhận của Chủ tịch Hội đồng đánh giá LV và Trƣởng Khoa quản lý chuyên ngành sau khi luận văn đã đƣợc sửa chữa (nếu có).
CHỦ TỊCH HỘ ĐỒNG TRƯỞNG KHOA ĐẠI HỌC QUỐC GIA TP.HCM CỘNG HÒA XÃ HỘI CHỦ NG Ĩ V ỆT NAM TRƯỜNG ĐẠI HỌC BÁCH KHOA Độc lập - Tự do - Hạnh phúc NHIỆM VỤ LUẬN VĂN T Ạ SĨ Họ tên học viên: NGUYỄN MINH TRỌNG. Ngày, tháng, năm sinh: 20/10/1988. Nơi sinh: Long An. Chuyên ngành: Khoa học máy tính.
TÊN ĐỀ TÀI: Ƣớc lƣợng các hệ số cho phƣơng pháp làm trơn hàm mũ Winters bằng metaheuristic. NHIỆM VỤ VÀ NỘI DUNG: 1. Hiện thực các giải thuật metaheuristic căn bản : giải thuật leo đồi, giải thuật tìm kiếm Tabu, giải thuật mô phỏng luyện kim bằng ngôn ngữ C#. Hiện thực một giải thuật cải tiến metaheuristic : giải thuật mô phỏng luyện kim tái nung nóng bằng ngôn ngữ C#.
Nghiên cứu phần mềm R : thực thi lệnh và đánh giá các giản đồ tƣơng quan phục vụ cho mô hình SARIMA. So sánh các kết quả thu đƣợc giữa các giải thuật metaheuristic. So sánh kết quả thu đƣợc trong phƣơng pháp làm trơn hàm mũ Winters và mô hình SARIMA. Hiện thực phương pháp làm trơn hàm mũ Winters trong môi trƣờng trực tuyến.
NGÀY GIAO NHIỆM VỤ : 19/08/2013 IV. NGÀY HOÀN THÀNH NHIỆM VỤ: 22/06/2014 V. CÁN BỘ ƯỚNG DẪN : PGS.TS DƢƠNG TUẤN ANH Tp. tháng 07 năm 2013 CÁN BỘ ƯỚNG DẪN TRƯỞNG KHOA (Họ tên và chữ ký) (Họ tên và chữ ký) LỜI CÁ N Lời đầu tiên trong luận văn này em xin gửi lời cám ơn chân thành đến thầy PGS.
TS Dƣơng Tuấn Anh, thầy đã dành nhiều thời gian, công sức và tâm huyết để truyền đạt kiến thức hƣớng dẫn em trong suốt thời thời gian thực hiện luận văn tốt nghiệp. Kế đến, em xin gửi lời cám ơn đến quý thầy cô đã giảng dạy và truyền đạt những kiến thức hữu ích cho em trong suốt thời gian tham gia học tập tại trƣờng Đại học Bách Khoa thành phố Hồ Chí Minh. Và em xin chân thành cám ơn các anh chị và bạn bè đã tạo điều kiện giúp đỡ em trong việc thu thập dữ liệu thực hiện luận văn này. Em xin chân thành cám ơn quý thầy cô trong hội đồng đánh giá luận văn thạc sĩ đã dành thời gian cho luận văn của em và cho em biết thêm nhiều kiến thức mới.
Cuối cùng em xin cám ơn đến gia đình và bạn bè đã động viên giúp đỡ em trong quá trình thực hiện luận văn này. i TÓM TẮT LUẬN VĂN T ẠC SĨ Luận văn này đƣợc thực hiện với mục tiêu chứng minh giải thuật metaheuristic có thể áp dụng cho việc xác định các hệ số alpha, beta và gamma tốt hơn phƣơng pháp vét cạn thông thƣờng trong phương pháp làm trơn hàm mũ Winters. Đồng thời, luận văn cũng đánh giá kết quả thu đƣợc từ các giải thuật metaheuristic nhằm xác định giải thuật nào sẽ tối ƣu hơn. Thêm vào đó, kết quả thu đƣợc từ phương pháp làm trơn hàm mũ Winters còn đƣợc so sánh với mô hình SARIMA nhằm xác định kết quả dự báo dữ liệu chuỗi thời gian theo phƣơng pháp nào là tốt hơn.
Phƣơng pháp nghiên cứu đƣợc thực hiện bởi phƣơng pháp định lƣợng. Trong luận văn này, nội dung cần nghiên cứu chính là: (1) lý thuyết của dữ liệu chuỗi thời gian; (2) bốn giải thuật metaheuristic: giải thuật leo đồi, giải thuật tìm kiếm Tabu, giải thuật mô phỏng luyện kim và giải thuật mô phỏng luyện kim tái nung nóng; (3) phương pháp làm trơn hàm mũ Winters: mô hình cộng, mô hình nhân; (4) mô hình SARIMA hỗ trợ thực hiện dự báo dữ liệu chuỗi thời gian; (5) nghiên cứu và sử dụng phần mềm R; (6) phương pháp làm trơn hàm mũ Winters trong môi trƣờng trực tuyến. Và sau quá trình thử nghiệm, kết quả của luận văn nhƣ sau: - Tất cả các giải thuật metaheuristic đều xác định các hệ số alpha, beta, gamma là rất tốt và độ chính xác cao. - Giải thuật mô phỏng luyện kim tái nung nóng cho ra kết quả tốt nhất trong các giải thuật metaheuristic.
- Kết quả dự báo của phương pháp làm trơn hàm mũ Winters theo mô hình nhân khi áp dụng các giải thuật metaheuristic là rất tốt và tƣơng đƣơng với mô hình SARIMA. - Phương pháp làm trơn hàm mũ Winters còn có thể áp dụng cho môi trƣờng dự báo trực tuyến và kết quả dự báo là rất tốt. Cuối cùng, kết quả của luận văn này sẽ là nguồn tƣ liệu mới, một thông tin mới và bổ sung hữu ích vào lĩnh vực dự báo dữ liệu chuỗi thời gian. ii ABSTRACT The goal of this thesis is to prove metaheuristics better than brute force algorithm in estimating the value of alpha, beta, gamma parameters in Exponential Smoothing Winters method.
This thesis aims to evaluate performance of metaheuristics in order to find out the best algorithm. In addition, this forecasting result of Exponential Smoothing Winters method will be compared with SARIMA model. The method research is implemented by Quantitative Methods. The content of this thesis research consists of the following: (1) Theory of time series data; (2) Four metaheuristics: Hill Climbing algorithm, Tabu Search algorithm, Simulated Annealing algorithm and Simulated Annealing with Reheating algorithm; (3) Exponential Smoothing Winters method: additive components model, multiplicative components model; (4) SARIMA model for forecast of time series data; (5) Study and use the R software; (6) Exponential Smoothing Winters method in online prediction.
And the result of testing process as the below: - All metaheuristics can be used to estimate the values of alpha, beta, gamma parameters with high accuracy. - The Simulated Annealing with Reheating algorithm is the best algorithm in the four metaheuristics algorithms. - The forecasting result of Exponential Smoothing Winters method with multiplicative components model is very good and sometimes is better than SARIMA model. - Exponential Smoothing Winters method can used to forcast in online environment and the result is very good.
Finally, the results of this thesis will be a new reference material, a new and useful knowledge for forecast of time series data. iii LỜ Đ N Em xin cam đoan rằng tất cả những giải thuật, dữ liệu trong luận văn này do em tự nghiên cứu và thực hiện theo sự hƣớng dẫn của giáo viên hƣớng dẫn. Và những kết quả đƣợc thu đƣợc trong quá trình thực hiện và so sánh giữa các yêu cầu trong luận văn hoàn toàn khách quan và trung thực đúng với tinh thần của yêu cầu luận văn đã đƣa ra. iv DANH MỤC CHỮ VIẾT TẮT STT Chữ viết tắt Ý nghĩa 1 T Tính xu hƣớng 2 S Tính mùa 3 C Tính chu kỳ 4 I Tính bất thƣờng 5 ACF Hàm tự tƣơng quan 6 PACF Hàm tự tƣơng quan riêng phần 7 AR Mô hình tự hồi quy 8 MA Mô hình trung bình di động 9 ARMA AR + MA + có tính dừng 10 ARIMA AR + MA + không có tính dừng 11 NN Mạng thần kinh nhân tạo 12 MAPE Sai số phần trăm trung bình tuyệt đối 13 MAD Sai số trung bình tuyệt đối 14 MSD Sai số trung bình bình phƣơng 15 SSE Sai số tổng bình phƣơng 16 SHC Giải thuật leo đồi dốc nhất 17 RHC Giải thuật leo đồi ngẫu nhiên 18 NCHC Giải thuật leo đồi có xung đột ít nhất 19 WMA Trung bình di động có trọng số 20 E(X) Kỳ vọng của biến ngẫu nhiên X 21 Var(X) Phƣơng sai của biến ngẫu nhiên X 22 HICP Chỉ số giá tiêu dùng v DANH MỤC HÌNH Hình 2.1: Ví dụ về dữ liệu chuỗi thời gian .2: Tính xu hƣớng của dữ liệu chuỗi thời gian .3: Giá trị dự báo đƣợc xấp xỉ .4: Tính m a của dữ liệu chuỗi thời gian .5: Tính chu trình của dữ liệu chuỗi thời gian .6: Tính chu kỳ nhƣ là một phần của thành phần xu hƣớng .7: Ví dụ mô hình cộng.8: Ví dụ mô hình nhân.9: Hệ số làm trơn α lớn .10: Hệ số làm trơn α nhỏ .11: Phƣơng pháp làm trơn hàm mũ Holt với 0,1 và = 0,099 .12: Phƣơng pháp làm trơn hàm mũ Winters .13: Đoạn mã giả mô tả giải thuật leo đồi .14: Đoạn mã giả mô tả giải thuật tìm kiếm Tabu .15: Đoạn mã giả mô tả giải thuật mô phỏng luyện kim.16: Đoạn mã mô tả giải thuật mô phỏng luyện kim tái nung nóng .17: Cơ chế hoạt động của bộ đệm xoay vòng .3: Sự kết hợp AR(p) và MA(q) cho vào mô hình ARMA.4: Quy trình xác định hệ số ARIMA(p,d,q) .5: Quy trình xác định hệ số SARIMA(p,d,q)x(P,D,Q)s .6: Cấu trúc mạng thần kinh nhân tạo .7: Mạng thần kinh nhân tạo truyền thẳng .8: Mạng thần kinh nhân tạo hồi quy .9: Mô hình học với chuỗi thời gian .1: Giao điện khi sử dụng phƣơng pháp làm trơn hàm mũ Winters đƣợc ƣớc lƣợng bởi giải thuật metaheuristic .2: Giao diện ban đầu của phần mềm R .3: Kết quả dự báo Winters/Hill-Climbing theo mô hình nhân trên tập dữ liệu Fancy .4: Kết quả dự báo Winters/Tabu-Search theo mô hình nhân trên tập dữ liệu Fancy .5: Kết quả dự báo Winters/Simulated-Annealing theo mô hình nhân trên tập dữ liệu Fancy.6: Kết quả dự báo Winters/SA-with-Reheating theo mô hình nhân trên tập dữ liệu Fancy .7: Kết quả dự báo của mô hình SARIMA trên tập dữ liệu Fancy .8: Kết quả dự báo Winters/Hill-Climbing theo mô hình nhân trên tập dữ liệu Mdeaths .9: Kết quả dự báo Winters/Tabu-Search theo mô hình nhân trên tập dữ liệu Mdeaths .10: Kết quả dự báo Winters/Simulated-Annealing theo mô hình nhân trên tập dữ liệu Mdeaths .11: Kết quả dự báo Winters/SA-with-Reheating theo mô hình nhân trên tập dữ liệu Mdeaths .12: Kết quả dự báo của mô hình SARIMA trên tập dữ liệu Mdeaths 62 Hình 4.13: Kết quả dự báo Winters/Hill-Climbing theo mô hình nhân trên tập dữ liệu Ukgas .14: Kết quả dự báo Winters/Tabu-Search theo mô hình nhân trên tập dữ liệu Ukgas .
