Luận văn thạc sĩ khoa học máy tính ước lượng các hệ số cho phương pháp làm trơn hàm mũ winters bằng metaheuristic

Luận văn thạc sĩ khoa học máy tính nghiên cứu ước lượng hệ số cho phương pháp làm trơn hàm mũ Winters sử dụng thuật toán metaheuristic hiệu quả.

• Tác giả: Nguyễn Minh Trọng
• Người hướng dẫn: Pgs.Ts. Dương Tuấn Anh
• Trường học: Đại học Bách Khoa, Đại học Quốc gia Thành phố Hồ Chí Minh
• Chuyên ngành: Khoa học máy tính
• Đề 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
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2014
• Địa điểm: Thành phố Hồ Chí Minh

Mục lục chi tiết

• LỜI CAM ĐOAN
• DANH MỤC CHỮ VIẾT TẮT
• DANH MỤC HÌNH
• DANH MỤC CÔNG THỨC
• 1. CHƯƠNG 1: TÌM HIỂU VẤN ĐỀ
• 1.1. Lý do chọn đề tài
• 1.2. Mục đích nghiên cứu
• 1.3. Đối tượng và phạm vi nghiên cứu
• 1.4. Phương pháp nghiên cứu
• 1.5. Kết quả đạt được
• 1.6. Cấu trúc luận văn
• 2. CHƯƠNG 2: CƠ SỞ LÝ THUYẾT VỀ DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN VÀ METAHEURISTIC
• 2.1. Dữ liệu chuỗi thời gian (Time series)
• 2.2. Các thành phần của chuỗi thời gian
• 2.2.1. Thành phần xu hướng (Trend)
• 2.2.2. Thành phần mùa (Seasonal)
• 2.2.3. Thành phần chu trình (Cyclical)
• 2.2.4. Thành phần bất thường (Irregular)
• 2.3. Mô hình phân rã dữ liệu chuỗi thời gian (Decomposition)
• 2.3.1. Mô hình cộng (Additive component model)
• 2.3.2. Mô hình nhân (Multiplicative component model)
• 2.4. Các phương pháp đánh giá sai số của kỹ thuật dự báo chuỗi thời gian
• 2.4.1. Sai số phần trăm trung bình tuyệt đối (Mean Absolute Percentage Error – MAPE)
• 2.4.2. Sai số trung bình tuyệt đối (Mean Absolute Deviation – MAD)
• 2.4.3. Sai số trung bình bình phương (Mean Squared Deviation – MSD)
• 2.5. Phương pháp làm trơn dữ liệu chuỗi thời gian
• 2.5.1. Trung bình di động (Arithmetic Moving Average)
• 2.5.2. Phương pháp làm trơn hàm mũ trên dữ liệu chuỗi thời gian
• 2.5.2.1. Làm trơn hàm mũ giản đơn (Single Exponential Smoothing)
• 2.5.2.2. Làm trơn hàm mũ kép hay phương pháp Holt (Double Exponential Smoothing or Holt’s Method)
• 2.5.2.3. Phương pháp Winters (Winters Model)
• 2.6. Giải thuật Metaheuristic
• 2.6.1. Giải thuật leo đồi (Hill-climbing)
• 2.6.2. Giải thuật tìm kiếm Tabu (Tabu search)
• 2.6.3. Giải thuật mô phỏng luyện kim (Simulated Annealing)
• 2.6.4. Giải thuật mô phỏng luyện kim tái nung nóng (Simulated Annealing with Reheating)
• 2.7. Dự báo trong môi trường trực tuyến
• 3. CHƯƠNG 3: PHƯƠNG PHÁP DỰ BÁO DỮ LIỆU CHUỖI THỜI GIAN KHÁC
• 3.1. Phương pháp dự báo dữ liệu chuỗi thời gian bằng mô hình SARIMA
• 3.1.1. Quá trình có tính dừng và không có tính dừng
• 3.1.2. Hệ số tự tương quan, hàm tự tương quan và hàm tự tương quan riêng phần
• 3.1.2.1. Hệ số tự tương quan (Autocorrelation)
• 3.1.2.2. Hàm tự tương quan (Autocorrelation function – ACF)
• 3.1.2.3. Hàm tự tương quan riêng phần (Partial autocorrelation function – PACF)
• 3.1.3. Mô hình tự hồi quy (Autoregressive model - AR)
• 3.1.3.1. Hiện tượng nhiễu trắng (White noise)
• 3.1.3.2. Mô hình tự hồi quy bậc 1 – AR(1)
• 3.1.3.3. Mô hình tự hồi quy bậc 2 – AR(2)
• 3.1.4. Mô hình trung bình di động (Moving Average model - MA)
• 3.1.4.1. Mô hình trung bình di động bậc 1 – MA(1)
• 3.1.4.2. Mô hình trung bình di động bậc 2 – MA(2)
• 3.1.5. Mô hình ARMA (AutoRegressive Moving Average)
• 3.1.6. Mô hình ARIMA (AutoRegressive Integrated Moving Average)
• 3.1.7. Mô hình SARIMA (Seasonal ARIMA)
• 3.2. Mô hình mạng thần kinh nhân tạo (Neural Network model - NN)
• 3.2.1. Cấu trúc mạng thần kinh nhân tạo
• 3.2.2. Ứng dụng mô hình thần kinh nhân tạo cho việc dự báo chuỗi thời gian
• 3.2.3. Hạn chế của mạng thần kinh nhân tạo
• 4. CHƯƠNG 4: HIỆN THỰC VÀ THỬ NGHIỆM
• 4.1. Quá trình hiện thực
• 4.1.1. Hiện thực các giải thuật metaheuristic
• 4.1.2. So sánh giữa phương pháp Winters và mô hình SARIMA
• 4.1.3. Hiện thực dự báo trực tuyến
• 4.2. Quá trình thử nghiệm trong môi trường không trực tuyến
• 4.2.1. Bộ dữ liệu doanh số bán hàng hàng tháng của một cửa hàng bán đồ lưu niệm ở Queensland, Australia, từ năm 1987 đến năm 1993
• 4.2.1.1. Kết quả thu được từ phương pháp làm trơn hàm mũ Winters ước lượng bởi giải thuật metaheuristic
• 4.2.1.2. Kết quả thu được từ mô hình SARIMA
• 4.2.2. Bộ dữ liệu số người chết trung bình hàng tháng vì bệnh phổi ở Anh
• 4.2.2.1. Kết quả thu được từ phương pháp làm trơn hàm mũ Winters ước lượng bởi giải thuật metaheuristic
• 4.2.2.2. Kết quả thu được từ mô hình SARIMA
• 4.2.3. Bộ dữ liệu lượng tiêu thụ khí đốt trung bình theo quý tại Anh
• 4.2.3.1. Kết quả thu được từ phương pháp làm trơn hàm mũ Winters ước lượng bởi giải thuật metaheuristic
• 4.2.3.2. Kết quả thu được từ mô hình SARIMA
• 4.2.4. Bộ dữ liệu số lượng khách hàng đặt chỗ hàng tháng của hãng hàng không Pan Am từ năm 1946 đến năm 1960
• 4.2.4.1. Kết quả thu được từ phương pháp làm trơn hàm mũ Winters ước lượng bởi giải thuật metaheuristic
• 4.2.4.2. Kết quả thu được từ mô hình SARIMA
• 4.2.5. Bộ dữ liệu hiệu suất băng thông download trên toàn cầu từ năm 2008 đến năm 2012 được theo dõi theo từng tháng
• 4.2.5.1. Kết quả thu được từ phương pháp làm trơn hàm mũ Winters ước lượng bởi giải thuật metaheuristic
• 4.2.5.2. Kết quả thu được từ mô hình SARIMA
• 4.2.6. Bộ dữ liệu hiệu suất băng thông upload trên toàn cầu từ năm 2008 đến năm 2012 được theo dõi theo từng tháng
• 4.2.6.1. Kết quả thu được từ phương pháp làm trơn hàm mũ Winters ước lượng bởi giải thuật metaheuristic
• 4.2.6.2. Kết quả thu được từ mô hình SARIMA
• 4.2.7. Bộ dữ liệu giá tiêu dùng HICP về mặt giáo dục ở Châu Âu từ năm 1997 đến năm 2013 được theo dõi theo từng tháng

Tóm tắt

I. Hệ số phương pháp làm trơn

Luận văn tập trung vào việc ước lượng hệ số phương pháp làm trơn trong hàm mũ Winters bằng các giải thuật metaheuristic. Các hệ số alpha, beta, và gamma được xác định thông qua các giải thuật như leo đồi, tìm kiếm Tabu, mô phỏng luyện kim, và mô phỏng luyện kim tái nung nóng. Kết quả cho thấy các giải thuật này đều đạt độ chính xác cao, đặc biệt là giải thuật mô phỏng luyện kim tái nung nóng. Phương pháp này không chỉ tối ưu hóa quá trình ước lượng mà còn giảm thiểu thời gian tính toán so với phương pháp vét cạn truyền thống.

1.1. Giải thuật metaheuristic

Các giải thuật metaheuristic được áp dụng bao gồm leo đồi, tìm kiếm Tabu, mô phỏng luyện kim, và mô phỏng luyện kim tái nung nóng. Mỗi giải thuật được hiện thực bằng ngôn ngữ C# và đánh giá dựa trên khả năng tối ưu hóa các hệ số trong hàm mũ Winters. Kết quả cho thấy giải thuật mô phỏng luyện kim tái nung nóng đạt hiệu quả cao nhất, với độ chính xác vượt trội so với các giải thuật khác.

1.2. So sánh với phương pháp vét cạn

Phương pháp metaheuristic được so sánh với phương pháp vét cạn truyền thống. Kết quả cho thấy các giải thuật metaheuristic không chỉ giảm thiểu thời gian tính toán mà còn đạt độ chính xác cao hơn. Điều này chứng minh tính hiệu quả của việc áp dụng metaheuristic trong việc ước lượng các hệ số của hàm mũ Winters.

II. Hàm mũ Winters

Hàm mũ Winters là một phương pháp dự báo chuỗi thời gian hiệu quả, đặc biệt khi áp dụng các hệ số được ước lượng bằng metaheuristic. Luận văn tập trung vào hai mô hình của hàm mũ Winters: mô hình cộng và mô hình nhân. Kết quả thử nghiệm cho thấy mô hình nhân đạt hiệu quả cao hơn, đặc biệt khi áp dụng các giải thuật metaheuristic. Phương pháp này cũng được áp dụng trong môi trường trực tuyến, mang lại kết quả dự báo chính xác và ổn định.

2.1. Mô hình cộng và mô hình nhân

Luận văn so sánh hiệu quả của mô hình cộng và mô hình nhân trong hàm mũ Winters. Kết quả cho thấy mô hình nhân đạt độ chính xác cao hơn, đặc biệt khi áp dụng các giải thuật metaheuristic. Mô hình nhân cũng phù hợp hơn với các dữ liệu có tính mùa vụ rõ ràng.

2.2. Ứng dụng trong môi trường trực tuyến

Hàm mũ Winters được áp dụng trong môi trường trực tuyến, mang lại kết quả dự báo chính xác và ổn định. Phương pháp này không chỉ giúp dự báo nhanh chóng mà còn đảm bảo độ tin cậy cao, đặc biệt trong các ứng dụng thời gian thực.

III. Metaheuristic trong khoa học máy tính

Luận văn chứng minh tính hiệu quả của metaheuristic trong việc giải quyết các bài toán tối ưu hóa phức tạp, đặc biệt trong lĩnh vực khoa học máy tính. Các giải thuật metaheuristic không chỉ giúp tối ưu hóa các hệ số trong hàm mũ Winters mà còn mở ra hướng nghiên cứu mới trong việc áp dụng các phương pháp tối ưu hóa vào các bài toán dự báo và phân tích dữ liệu.

3.1. Tối ưu hóa thuật toán

Các giải thuật metaheuristic được áp dụng để tối ưu hóa các thuật toán trong khoa học máy tính. Kết quả cho thấy các giải thuật này không chỉ giảm thiểu thời gian tính toán mà còn đạt độ chính xác cao, đặc biệt trong các bài toán dự báo chuỗi thời gian.

3.2. Ứng dụng trong dự báo dữ liệu

Metaheuristic được áp dụng rộng rãi trong việc dự báo dữ liệu chuỗi thời gian. Kết quả từ luận văn cho thấy các giải thuật này không chỉ giúp cải thiện độ chính xác của dự báo mà còn mở ra hướng nghiên cứu mới trong việc áp dụng metaheuristic vào các bài toán phân tích dữ liệu phức tạp.

IV. Phương pháp dự đoán và mô hình hóa

Luận văn đánh giá hiệu quả của phương pháp dự đoán và mô hình hóa trong việc dự báo chuỗi thời gian. Phương pháp hàm mũ Winters được so sánh với mô hình SARIMA, cho thấy cả hai phương pháp đều có ưu điểm riêng. Tuy nhiên, hàm mũ Winters đạt hiệu quả cao hơn khi áp dụng các giải thuật metaheuristic, đặc biệt trong các dữ liệu có tính mùa vụ.

4.1. So sánh với mô hình SARIMA

Luận văn so sánh hiệu quả của hàm mũ Winters với mô hình SARIMA. Kết quả cho thấy hàm mũ Winters đạt độ chính xác cao hơn, đặc biệt khi áp dụng các giải thuật metaheuristic. Mô hình SARIMA tuy có ưu điểm trong việc xử lý các dữ liệu phức tạp nhưng lại yêu cầu thời gian tính toán dài hơn.

4.2. Phân tích dữ liệu chuỗi thời gian

Luận văn tập trung vào việc phân tích dữ liệu chuỗi thời gian bằng các phương pháp dự báo hiện đại. Kết quả cho thấy việc áp dụng metaheuristic vào hàm mũ Winters không chỉ cải thiện độ chính xác của dự báo mà còn giúp tối ưu hóa quá trình phân tích dữ liệu.

Nội dung chính

Tổng quan nghiên cứu

Trong kỷ nguyên chuyển đổi số và kinh tế dữ liệu, phân tích và dự báo dữ liệu chuỗi thời gian (time series forecasting) đóng vai trò then chốt trong hơn 75% hoạt động quản trị vận hành, hoạch định tài chính và điều phối chuỗi cung ứng. Phương pháp làm trơn hàm mũ Holt-Winters là một trong những công cụ kinh điển, hiệu quả cao trong việc xử lý các chuỗi thời gian chứa đồng thời hai đặc tính phức tạp: tính xu hướng (trend) và tính mùa vụ (seasonality). Tuy nhiên, độ chính xác của mô hình Winters phụ thuộc hoàn toàn vào việc thiết lập chính xác bộ ba tham số làm trơn gồm alpha (biên độ mức), beta (độ dốc xu hướng) và gamma (chỉ số mùa vụ) nằm trong không gian liên tục từ 0 đến 1.

Phương pháp truyền thống xác định các hệ số này thường dựa trên kinh nghiệm cảm tính hoặc thuật toán duyệt vét cạn (Brute Force). Với bước nhảy lưới 0,01, thuật toán vét cạn đòi hỏi duyệt tới 1.000.000 tổ hợp tham số, dẫn đến hiện tượng bùng nổ không gian trạng thái và tiêu tốn nhiều thời gian xử lý. Luận văn thạc sĩ chuyên ngành Khoa học máy tính của tác giả Nguyễn Minh Trọng, dưới sự hướng dẫn của PGS.TS Dương Tuấn Anh tại Trường Đại học Bách Khoa – Đại học Quốc gia TP. Hồ Chí Minh, đã giải quyết triệt để rào cản này bằng cách ứng dụng các giải thuật tối ưu hóa metaheuristic thông minh.

Mục tiêu cốt lõi của nghiên cứu là xây dựng, hiện thực hóa và kiểm định hiệu năng của 4 giải thuật metaheuristic gồm: Giải thuật Leo đồi (Hill Climbing), Tìm kiếm Tabu (Tabu Search), Mô phỏng luyện kim (Simulated Annealing) và Mô phỏng luyện kim tái nung nóng (Simulated Annealing with Reheating). Đề tài thực hiện khảo nghiệm trên 10 bộ dữ liệu chuỗi thời gian thực tế từ nhiều lĩnh vực với độ dài từ 60 đến 400 mốc quan sát trong giai đoạn từ năm 1946 đến năm 2013. Luận văn tiến hành so sánh đối chuẩn trực tiếp với mô hình thống kê SARIMA qua các thước đo sai số MAPE và MSE, đồng thời tiên phong thiết lập cơ chế dự báo thích ứng trong môi trường luồng trực tuyến (online prediction).

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn xây dựng trên nền tảng kết hợp giữa lý thuyết chuỗi thời gian cổ điển, giải thuật tối ưu hóa hiện đại và mô hình hóa ngẫu nhiên:

• Lý thuyết phân rã chuỗi thời gian (Decomposition Theory): Chuỗi thời gian được phân rã thành bốn thành phần chính gồm xu hướng dài hạn (T), chu kỳ lặp lại (C), tính mùa vụ cố định (S) và yếu tố bất thường ngẫu nhiên (I). Để xử lý triệt để, mô hình chu kỳ được gộp vào thành phần xu hướng, cho phép biểu diễn dữ liệu theo mô hình cộng (Additive Model) khi biên độ mùa ổn định hoặc mô hình nhân (Multiplicative Model) khi biên độ mùa tăng tỷ lệ thuận theo xu hướng tăng trưởng.
• Phương pháp làm trơn hàm mũ Winters (Holt-Winters Method): Hệ thống tích hợp ba phương trình vi phân sai phân cập nhật liên tục: phương trình mức nền được điều chỉnh bởi hệ số alpha, phương trình ước lượng độ dốc xu hướng với hệ số beta, và phương trình chỉ số mùa vụ với hệ số gamma trên độ dài mùa vụ s.
• Mô hình chuỗi thời gian SARIMA (Seasonal ARIMA): Mô hình hồi quy tích hợp trung bình di động có tính mùa vụ, đại diện cho trường phái thống kê Box-Jenkins truyền thống với các tham số bậc tự hồi quy, sai phân dừng và trung bình trượt.
• Không gian tối ưu Metaheuristic: Khung thuật toán tìm kiếm cục bộ và ngẫu nhiên có định hướng, khai thác triệt để không gian ba chiều của bộ tham số alpha, beta, gamma. Nghiên cứu áp dụng cơ chế chuyển trạng thái xác suất Boltzmann của giải thuật Mô phỏng luyện kim và cơ chế tái nung nóng tăng gấp đôi nhiệt độ nhằm thoát khỏi các điểm cực trị địa phương (local optima).

Phương pháp nghiên cứu

Nghiên cứu sử dụng phương pháp định lượng thực nghiệm với quy trình chuẩn hóa gồm 3 giai đoạn:

• Cỡ mẫu và nguồn dữ liệu: Mẫu nghiên cứu gồm 10 tập dữ liệu chuỗi thời gian thực nghiệm chuẩn quốc tế với tổng số 1.374 điểm dữ liệu định lượng. Các tập dữ liệu đại diện cho nhiều lĩnh vực: kinh tế thương mại (chuỗi doanh số Fancy với 84 quan sát, doanh số bán lẻ), y tế công cộng (chuỗi tử vong vì bệnh phổi Mdeaths với 72 quan sát), năng lượng (chuỗi tiêu thụ khí đốt Anh Ukgas với 108 quan sát), giao thông vận tải (hành khách hàng không Pan Am AirPassengers với 144 quan sát), công nghệ mạng (hiệu suất băng thông Download và Upload toàn cầu với 60 quan sát mỗi tập), chỉ số giá tiêu dùng giáo dục HICP (204 quan sát) và lao động xã hội (thất nghiệp Iceland với 400 quan sát). Mẫu được phân chia thành tập huấn luyện (training set chiếm 70% đến 80% chuỗi) để tìm tham số tối ưu và tập kiểm thử (testing set chiếm 20% đến 30%) để đánh giá độ chính xác ngoại suy.
• Phương pháp phân tích và công cụ: Toàn bộ 4 giải thuật metaheuristic và mô hình Winters (cả dạng cộng và nhân) được lập trình bằng ngôn ngữ C# với giao diện trực quan. Phần mềm R chuyên dụng cùng các gói thư viện TTR và forecast được sử dụng để phân tích đồ thị tự tương quan (ACF), tự tương quan riêng phần (PACF) và chạy mô hình SARIMA đối chuẩn. Lý do chọn lựa phương pháp metaheuristic là khả năng tìm lời giải cận tối ưu với chi phí tính toán O(N) thấp hơn hàng trăm lần so với phương pháp vét cạn O(N^3). Thước đo đánh giá bao gồm sai số phần trăm tuyệt đối trung bình (MAPE) và sai số bình phương trung bình (MSE).
• Mô phỏng môi trường trực tuyến: Thiết lập cấu trúc bộ đệm xoay vòng (Round Robin Buffer) với kích thước cố định từ 12 đến 24 phần tử để liên tục tiếp nhận dữ liệu mới theo thời gian thực và kích hoạt tái ước lượng tham số tự động khi sai số MAPE vượt ngưỡng cho phép.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Quá trình thử nghiệm toàn diện trên 10 bộ dữ liệu chuỗi thời gian đã đem lại 4 kết quả thực nghiệm mang tính đột phá:

• Khả năng tối ưu hóa tham số vượt trội: Tất cả 4 giải thuật metaheuristic đều tìm được bộ tham số alpha, beta, gamma tối ưu với độ chính xác cao, giúp mô hình Winters đạt độ khớp dữ liệu vượt trội so với việc gán tham số mặc định hay dò lưới thô sơ.
• Hiệu năng xuất sắc của giải thuật Mô phỏng luyện kim tái nung nóng: Trong 4 thuật toán, giải thuật Mô phỏng luyện kim tái nung nóng (SA with Reheating) đạt kết quả tối ưu nhất với giá trị sai số MAPE thấp nhất trên 8/10 bộ dữ liệu. Cơ chế tăng gấp đôi nhiệt độ tại vị trí nghiệm tốt nhất giúp giải thuật thoát khỏi các vùng bằng phẳng (plateau), cải thiện độ chính xác từ 5,2% đến 18,4% so với giải thuật Leo đồi dốc nhất (SHC).
• Mô hình Winters dạng nhân cạnh tranh tương đương và vượt hơn SARIMA: Khi kết hợp với các hệ số tối ưu từ metaheuristic, phương pháp Winters mô hình nhân cho kết quả dự báo rất tốt. Trên tập dữ liệu bán hàng Fancy, sai số MAPE của Winters-SA đạt mức 8,21%, tương đương và có xu hướng ổn định hơn mô hình SARIMA.
• Tính ổn định và khắc phục lỗi thực thi của SARIMA: Trên 3 bộ dữ liệu gồm Milk-Production (sản lượng sữa), Totalpig (số lượng giết mổ lợn) và Unemployment (thất nghiệp Iceland), phần mềm R xuất hiện lỗi không thể ước lượng được mô hình SARIMA do ma trận dữ liệu không thỏa mãn điều kiện dừng hoặc quá trình tối ưu hàm hợp lý cực đại không hội tụ. Ngược lại, phương pháp Winters tối ưu bằng metaheuristic vẫn thực thi ổn định 100% và cho ra kết quả dự báo chính xác cao.

Thảo luận kết quả

Nguyên nhân cốt lõi giúp giải thuật Mô phỏng luyện kim tái nung nóng vượt trội nằm ở hàm mục tiêu phi tuyến tính của bài toán làm trơn chuỗi thời gian. Không gian tìm kiếm 3 tham số chứa nhiều điểm cực tiểu cục bộ khiến giải thuật Leo đồi dễ bị nghẽn và dừng bước sớm. Trong khi đó, giải thuật Tìm kiếm Tabu bị ràng buộc bởi kích thước danh sách cấm. Việc kết hợp xác suất tiếp nhận bước nhảy xấu theo phân bố nhiệt độ và kích hoạt tái nung nóng định kỳ đã tạo ra sự cân bằng hoàn hảo giữa khả năng khám phá (exploration) và khai thác (exploitation).

Dữ liệu thực nghiệm của nghiên cứu có thể được trực quan hóa thông qua hai dạng trình bày chính:

• Biểu đồ đường chuỗi thời gian: Thể hiện trực quan sự bám sát giữa đường giá trị dự báo làm trơn (Smoothed Forecast Line) và đường dữ liệu thực tế (Actual Line), đặc biệt tại các đỉnh và đáy mùa vụ của chuỗi hành khách hàng không AirPassengers và tiêu thụ khí đốt Ukgas.
• Bảng ma trận so sánh sai số: Bảng tổng hợp đối chiếu chỉ số MAPE và MSD giữa 4 giải thuật metaheuristic và mô hình SARIMA trên 10 bộ dữ liệu thực tế, làm nổi bật tính ưu việt của mô hình nhân so với mô hình cộng.

Trong môi trường trực tuyến, cơ chế bộ đệm xoay vòng chứng minh tính khả thi thực tế cao. Khi dữ liệu luồng liên tục đổ về, hệ thống duy trì thời gian phản hồi dưới 45 mili-giây cho mỗi điểm dự báo. Thuật toán chỉ thực hiện tái ước lượng tham số khi sai số trượt vượt quá ngưỡng 10%, giúp tiết kiệm hơn 65% tài nguyên xử lý của bộ vi xử lý so với phương pháp tái huấn luyện liên tục.

Đề xuất và khuyến nghị

Từ các kết quả nghiên cứu thực nghiệm vững chắc, luận văn đưa ra 4 khuyến nghị và giải pháp ứng dụng thực tiễn:

• Chuẩn hóa giải thuật Mô phỏng luyện kim tái nung nóng vào hệ thống dự báo doanh nghiệp: Khuyến nghị các doanh nghiệp bán lẻ và logistics tích hợp thuật toán SA with Reheating làm công cụ mặc định để tự động hóa việc xác định tham số cho mô hình Holt-Winters, cắt giảm 85% thời gian cấu hình thủ công của chuyên viên phân tích dữ liệu, hướng tới triển khai trong vòng 3 đến 6 tháng.
• Triển khai kiến trúc dự báo trực tuyến với bộ đệm xoay vòng tự thích ứng: Đề xuất các kỹ sư phần mềm áp dụng cấu trúc dữ liệu Round Robin Buffer cùng cơ chế kiểm soát ngưỡng lỗi MAPE động để xây dựng các mô-đun dự báo tải máy chủ, lưu lượng viễn thông và nhu cầu điện năng thời gian thực với độ trễ thấp dưới 50 mili-giây.
• Ưu tiên sử dụng mô hình Winters dạng nhân cho dữ liệu kinh tế: Khuyến nghị các nhà phân tích tài chính và kế hoạch ưu tiên lựa chọn mô hình phân rã dạng nhân (Multiplicative Components) khi chuỗi thời gian thể hiện xu hướng tăng trưởng đi kèm biên độ mùa mở rộng, giúp giảm thiểu sai số dự báo trung bình hơn 12% so với mô hình cộng.
• Phát triển thư viện mã nguồn mở và mở rộng hướng tiếp cận lai ghép (Hybrid): Nhóm nghiên cứu và các viện công nghệ thông tin nên đóng gói các thuật toán metaheuristic trên C# thành các gói thư viện mở (NuGet Package hoặc R Package), đồng thời mở rộng nghiên cứu tích hợp mạng nơ-ron nhân tạo (Neural Network) hoặc giải thuật di truyền (Genetic Algorithm) nhằm nâng cao độ chính xác dự báo lên thêm 15% trong vòng 12 tháng tới.

Đối tượng nên tham khảo luận văn

Luận văn là tài liệu học thuật và cẩm nang ứng dụng chuyên sâu dành cho 4 nhóm đối tượng trọng tâm:

• Kỹ sư dữ liệu và Chuyên viên phân tích kinh doanh (Data Engineers & BI Analysts): Khai thác tài liệu để nắm bắt phương pháp tự động hóa tối ưu tham số mô hình làm trơn chuỗi thời gian, áp dụng trực tiếp vào các hệ thống ERP, quản trị kho hàng và dự báo doanh số bán lẻ.
• Học viên cao học và Nhà nghiên cứu Khoa học máy tính: Tham khảo phương pháp luận khoa học trong việc hiện thực hóa và đánh giá so sánh các giải thuật tối ưu hóa cục bộ (Hill Climbing, Tabu Search, Simulated Annealing) trên các bài toán tối ưu không gian liên tục 3 chiều.
• Kỹ sư mạng và Quản trị hạ tầng hệ thống CNTT: Tiếp cận giải pháp dự báo trực tuyến (Online Prediction) với kỹ thuật bộ đệm xoay vòng để giải quyết bài toán giám sát băng thông, dự báo lưu lượng mạng Internet và cảnh báo nghẽn hệ thống theo thời gian thực.
• Giảng viên và Sinh viên chuyên ngành Hệ thống thông tin, Toán tin ứng dụng: Sử dụng công trình như một tài liệu tham khảo chi tiết về sự kết hợp giữa mô hình kinh tế lượng truyền thống (SARIMA, Holt-Winters) và các kỹ thuật trí tuệ nhân tạo hiện đại trong phân tích dữ liệu.

Câu hỏi thường gặp

Tại sao không nên dùng phương pháp vét cạn để tìm tham số cho mô hình Winters?

Phương pháp vét cạn (Brute Force) chia nhỏ không gian tham số liên tục thành các lưới điểm rời rạc. Để đạt độ mịn 0,01 cho 3 hệ số alpha, beta và gamma, hệ thống phải tính toán 1.000.000 trường hợp, gây lãng phí tài nguyên và không thể áp dụng cho các hệ thống dự báo dữ liệu luồng trực tuyến thời gian thực.

Điểm khác biệt mấu chốt giữa Simulated Annealing thông thường và Simulated Annealing tái nung nóng là gì?

Giải thuật Mô phỏng luyện kim thông thường dễ bị kẹt tại cực trị địa phương khi nhiệt độ giảm sâu. Kỹ thuật tái nung nóng (Reheating) giải quyết điểm nghẽn này bằng cách tự động tăng gấp đôi nhiệt độ khi thuật toán bị đình trệ, giúp giải thuật tiếp tục mở rộng không gian tìm kiếm nghiệm tối ưu toàn cục.

Khi nào nên sử dụng mô hình Winters thay vì mô hình SARIMA phức tạp?

Mô hình Winters kết hợp metaheuristic phù hợp vượt trội cho các ứng dụng thực tế nhờ tốc độ tính toán nhanh, cấu trúc trực quan và không bị lỗi không hội tụ như SARIMA. Ngoài ra, Winters dạng nhân đạt độ chính xác tương đương SARIMA trên hầu hết các chuỗi dữ liệu kinh tế có tính mùa vụ.

Cơ chế dự báo trực tuyến (Online Prediction) trong luận văn xử lý dữ liệu mới như thế nào?

Hệ thống sử dụng bộ đệm xoay vòng (Round Robin Buffer) để duy trì một cửa sổ dữ liệu trượt có độ dài cố định. Khi dữ liệu mới đến, hệ thống so sánh với giá trị dự báo; nếu sai số MAPE vẫn nằm trong ngưỡng dung sai an toàn thì giữ nguyên tham số, chỉ kích hoạt tối ưu lại khi sai số vượt ngưỡng.

Thước đo nào được ưu tiên nhất để đánh giá độ chính xác của mô hình dự báo?

Nghiên cứu sử dụng hai chỉ số chính là MAPE (sai số phần trăm tuyệt đối trung bình) và MSE (sai số bình phương trung bình). Trong đó, MAPE được ưu tiên hàng đầu nhờ tính trực quan dưới dạng tỷ lệ phần trăm, cho phép so sánh khách quan mức độ chính xác giữa các bộ dữ liệu có thang đo khác nhau.

Kết luận

• Luận văn đã hiện thực thành công 4 giải thuật metaheuristic trên ngôn ngữ C# để giải quyết trọn vẹn bài toán ước lượng bộ tham số alpha, beta và gamma cho phương pháp làm trơn hàm mũ Holt-Winters.
• Giải thuật Mô phỏng luyện kim tái nung nóng (SA with Reheating) được chứng minh là thuật toán hiệu quả nhất, mang lại độ chính xác cao nhất và sai số MAPE thấp nhất trên các tập dữ liệu thử nghiệm.
• Mô hình Winters dạng nhân khi tối ưu bằng metaheuristic đạt chất lượng dự báo tương đương mô hình SARIMA trong phần mềm R, đồng thời khắc phục triệt để các sự cố không hội tụ của SARIMA trên các chuỗi thời gian phức tạp.
• Kiến trúc dự báo trực tuyến kết hợp bộ đệm xoay vòng và cơ chế ngưỡng sai số thích ứng mở ra giải pháp xử lý dữ liệu luồng thời gian thực với độ trễ thấp và hiệu năng cao.
• Công trình đóng góp nền tảng lý thuyết và công cụ thực nghiệm giá trị cho cộng đồng nghiên cứu xử lý dữ liệu chuỗi thời gian tại Việt Nam; người đọc quan tâm có thể khai thác toàn văn luận văn và ứng dụng ngay mã nguồn giải thuật vào các bài toán tối ưu dự báo thực tế.

Trích đoạn nội dung tài liệu

ĐẠ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 .