Phân tích dữ liệu chuỗi thời gian cho bài toán dự báo

GIỚI THIỆU

Đặt v ấn đề

Công nghệ điện toán đám mây mang lại nhiều lợi ích cho cả nhà cung cấp và người sử dụng Nhà cung cấp tối ưu hóa việc sử dụng máy chủ vật lý bằng cách chia sẻ tài nguyên giữa nhiều khách hàng Người sử dụng không cần lo lắng về chi phí cơ sở hạ tầng, chỉ phải trả tiền cho thời gian sử dụng theo mô hình PAYG (trả theo mức sử dụng) Chính vì vậy, dịch vụ lưu trữ đám mây ngày càng trở nên phổ biến.

Điện toán đám mây nổi bật với tính năng co giãn tài nguyên, giúp tăng cường khả năng sử dụng và chất lượng dịch vụ cho các ứng dụng Chức năng này thường được cung cấp thông qua dịch vụ tự động mở rộng quy mô, dựa trên hai kỹ thuật chính là Ngưỡng.

Mặc dù công nghệ thông tin đang phát triển mạnh mẽ, kỹ thuật ngưỡng vẫn được áp dụng rộng rãi trong thực tế, trong khi kỹ thuật dự đoán vẫn chỉ là một chủ đề nghiên cứu hấp dẫn do nhiều rào cản trong việc ứng dụng Một trong những vấn đề chính là nếu mô hình dự đoán có độ chính xác thấp, điều này có thể dẫn đến tình trạng thiếu hoặc thừa tài nguyên, gây tốn kém chi phí cho người sử dụng và ảnh hưởng đến chất lượng dịch vụ cung cấp.

Mô hình dự đoán cần đạt độ chính xác cao và sử dụng nhiều tài nguyên đồng thời, như RAM, CPU và thời gian truy cập ổ cứng, để đưa ra quyết định mở rộng hệ thống hiệu quả Đồng thời, các mô hình này phải đơn giản trong việc triển khai và vận hành, nhưng vẫn đảm bảo hiệu quả dự báo Cuối cùng, hệ thống tự động mở rộng tài nguyên cần có cơ chế quyết định để đảm bảo chất lượng dịch vụ (QoS) theo thỏa thuận mức dịch vụ (SLA) giữa khách hàng và nhà cung cấp.

Luận văn này tập trung vào việc dự báo và cung cấp tài nguyên trên ĐTĐM, nhằm giải quyết các vấn đề quan trọng trong lĩnh vực này, với các yêu cầu cụ thể được đặt ra.

1 Xây dựng được mô hình dự báo chuỗi thời gian đơn giản và hiệu quả

2 Thiết kế được hệ thống co giãn tài nguyên có thể sử dụng mô hình dự báo tài nguyên sẽ sử dụng trong tương lai

3 Hệ thống co giãn tài nguyên phải có thành phần ra quyết định để đánh giá kết quả dự báo đồng thời kích hoạt cơ chế ra quyết định tăng giảm tài nguyên

Cách tiếp cận

Luận văn giới thiệu mô hình mạng nơ-ron tự cấu trúc (SSNN), được huấn luyện bằng giải thuật tối ưu hóa cải tiến dựa trên hệ sinh thái tự nhiên (IAEO) Mô hình này được phát triển từ ý tưởng về mạng nơ-ron với tầng ẩn tự tổ chức, mang lại hiệu quả cao trong việc xử lý và phân tích dữ liệu.

Giải thuật IAEO, được cải tiến từ giải thuật tối ưu hóa AEO, kết hợp với chức năng SONIA để tạo ra mô hình dự báo tài nguyên IAEO-SSNN Mô hình này có cấu trúc đơn giản hơn so với mạng MLP và mạng SONIA.

Để đánh giá khả năng ứng dụng thực tế của mô hình dự báo tài nguyên, luận văn đề xuất hệ thống tự động co giãn tài nguyên với ba thành phần chính: Extraction, Learning và Scaling Mô đun Extraction chịu trách nhiệm thu thập, lưu trữ và tiền xử lý dữ liệu Mô đun Learning sử dụng mô hình dự đoán tài nguyên IAEO-SSNN để huấn luyện và dự báo Cuối cùng, mô đun Scaling bao gồm hai thành phần chính là Forecasting và Decision.

Sau khi hoàn thành mô hình huấn luyện từ mô-đun Learning, thành phần Forecasting sẽ tiến hành dự đoán tài nguyên sử dụng Mô-đun Decision sẽ áp dụng phương pháp ra quyết định dựa trên giá trị tài nguyên dự đoán từ mô-đun Forecasting cùng với hai yếu tố quan trọng trong ĐTĐM là chất lượng dịch vụ QoS và thỏa thuận mức dịch vụ SLA.

Các mô hình và hệ thống đề xuất đã được thử nghiệm và đánh giá trên tập dữ liệu theo dõi cụm máy chủ thực tế của Google từ năm 2011 Kết quả cho thấy rằng mô hình dự báo tài nguyên dữ liệu chuỗi thời gian kết hợp trong hệ thống co giãn tài nguyên đạt hiệu quả tốt và có thể áp dụng thực tiễn.

Các đóng góp của luận văn

1 Đề xuất mô hình dự báo chuỗi thời gian sử dụng mạng tự tổ chức kết hợp với giải thuật cải tiến IAEO bên trên tạo thành mô hình IAEO-SSNN

2 Đề xuất hệ thống tự động co giãn tài nguyên sử dụng mô hình dự báo chuỗi thời gian IAEO-SSNN để học tập và dự đoán tài nguyên sử dụng trong tương lai Hệ thống gồm 3 thành phần chính là Extraction, Learning và Scaling

3 Đề xuất mô đun ra quyết định (Decision) trong thành phần Scaling, có sử dụng thuật toán dựa vào tài nguyên dự đoán và những yếu tố về chất lượng dịch vụ (QoS) cũng như thỏa thuận hợp đồng (SLA) để ra quyết định co giãn tài nguyên

Kết quả những đóng góp trên giải quyết được 3 yêu cầu đề ra bên trên.

Bố cục luận văn

Bài báo này được cấu trúc thành các chương rõ ràng Chương 2 phân loại và phân tích các nghiên cứu liên quan, làm nổi bật sự khác biệt và đóng góp của luận văn Chương 3 trình bày các đề xuất của luận văn, bao gồm hệ thống tự động co giãn tài nguyên, mô hình dự đoán và giải thuật huấn luyện Chương 4 thực hiện các thí nghiệm với các mô hình dự đoán khác nhau, đánh giá ảnh hưởng của chúng đến kết quả của hệ thống tự động co giãn qua nhiều độ đo Cuối cùng, Chương 5 tổng kết các kết luận đạt được trong luận văn.

CÁC NGHIÊN CỨU LIÊN QUAN

Điện toán đám mây và các vấn đề liên quan

Trước đây, các trang web và ứng dụng thường hoạt động trên các hệ thống riêng biệt, nhưng sự ra đời của điện toán đám mây (ĐTĐM) đã cho phép hợp nhất tài nguyên hệ thống thành kho chứa chung Nhờ vào việc sử dụng tài nguyên chung, các ứng dụng có thể hoạt động độc lập mà không cần quan tâm đến cấu hình cụ thể hay sự tương tác với các ứng dụng khác Đặc điểm linh hoạt trong việc cấp phát tài nguyên theo yêu cầu của ĐTĐM mang lại nhiều lợi ích, giúp loại bỏ sự cần thiết phải đầu tư vào phần cứng cụ thể cho từng nhiệm vụ.

Nhà cung cấp dịch vụ điện toán đám mây phải đối mặt với thách thức trong việc đáp ứng nhu cầu tài nguyên theo xu hướng mở rộng hoặc thu hẹp Ví dụ, lưu lượng truy cập thay đổi của các website có thể dẫn đến tình trạng quá tải, ảnh hưởng đến chất lượng trải nghiệm người dùng và doanh thu của doanh nghiệp Ngược lại, việc cung cấp dư thừa tài nguyên không chỉ lãng phí mà còn gia tăng chi phí cho doanh nghiệp Thường thì, các doanh nghiệp phải lập kế hoạch chi tiết về dung lượng cần sử dụng và đầu tư lớn vào phần cứng và phần mềm.

SW này thường được cấp phép với dung lượng cố định Minh họa ở Hình 2.1

Hình 2.1 Mô tả tài nguyên cung cấp cố định theo yêu cầu của doanh nghiệp (nguồn [1])

Nhiều lần, do sự thay đổi trong dự báo sử dụng và lập kế hoạch dung lượng, chúng ta thấy rằng dung lượng phần cứng (HW) và phần mềm (SW) thường bị sử dụng quá mức Điều này xảy ra vì nhu cầu thực tế thường không khớp với dự đoán Các hệ thống hoạt động hiệu quả trong thời gian cao điểm nhưng lại nhàn rỗi phần lớn thời gian sau đó Hơn nữa, đôi khi các doanh nghiệp trực tuyến dự đoán sai và yêu cầu HW, SW ít hơn so với mức sử dụng thực tế Hiện tượng này thường xảy ra trong mùa nghỉ lễ khi lưu lượng truy cập của người dùng rất khó dự đoán.

Hình 2.2 Mô tả sự cung cấp thừa tài nguyên (bên trái) và cung cấp thiếu tài nguyên

Để giải quyết vấn đề cung cấp tài nguyên điện toán đám mây, cần xây dựng một hệ thống có khả năng mở rộng và thu hẹp linh hoạt theo lưu lượng tải Hệ thống tự co giãn tài nguyên có thể áp dụng ba kỹ thuật chính: Chu kỳ, Ngưỡng và Dự đoán Tuy nhiên, hai kỹ thuật Chu kỳ và Ngưỡng gặp phải nhược điểm là không thể đáp ứng ngay lập tức các yêu cầu tài nguyên từ ứng dụng và khó xác định giá trị ngưỡng hợp lý, dẫn đến lãng phí hoặc thiếu hụt tài nguyên Do đó, bài viết này sẽ tập trung vào kỹ thuật Dự đoán.

Hình 2.3 Mô hình dự đoán tài nguyên (nguồn [1])

Kỹ thuật dự đoán dựa trên dữ liệu thống kê giúp phân tích và dự báo nhu cầu tài nguyên trong tương lai bằng cách sử dụng thông tin từ quá khứ Điều này cho phép hệ thống điều chỉnh tài nguyên một cách hợp lý, từ đó nâng cao chất lượng dịch vụ và tối ưu hóa chi phí Hình 2.3 minh họa sự tương đồng giữa tài nguyên sử dụng thực tế và tài nguyên dự đoán, cho thấy kết quả dự đoán rất chính xác.

Kỹ thuật cốt lõi được sử dụng trong bài viết này là phân tích chuỗi thời gian (TS), nhằm tìm ra các dấu hiệu lặp lại trong việc sử dụng tài nguyên để dự đoán tương lai Mặc dù phương pháp này hiệu quả, nhưng nó vẫn có nhược điểm là phụ thuộc vào chất lượng của mô hình dự đoán và mô hình ra quyết định Nếu mô hình dự đoán chính xác, thì kết quả sẽ đáng tin cậy hơn.

Hệ thống hoạt động hiệu quả khi mô hình dự đoán chính xác, tránh tình trạng thừa hoặc thiếu tài nguyên Tuy nhiên, nhiều mô hình mặc dù có độ chính xác cao nhưng lại quá phức tạp hoặc mất nhiều thời gian để huấn luyện, gây ảnh hưởng đến khả năng cung cấp tài nguyên kịp thời và chất lượng trải nghiệm người dùng Do đó, việc thiết kế một mô hình đơn giản nhưng hiệu quả là một tiêu chí quan trọng trong luận văn.

Các phương pháp dự đoán chuỗi thời gian

2.2.1 Các phương pháp tuyến tính

Hiện nay, có hai cơ chế co giãn tài nguyên là phản ứng và chủ động Cơ chế phản ứng đáp ứng sự thay đổi đột ngột của tài nguyên theo giá trị ngưỡng, trong khi cơ chế chủ động dự đoán nhu cầu tài nguyên trong tương lai và điều chỉnh trước khi có yêu cầu Luận văn này sẽ tập trung phân tích các nghiên cứu liên quan đến cơ chế chủ động.

Cơ chế chủ động yêu cầu mô hình dự đoán phải chính xác và đơn giản, đặc biệt trong bài toán dự đoán tài nguyên sử dụng trong tương lai, thường áp dụng cho dữ liệu chuỗi thời gian Dữ liệu chuỗi thời gian là tập hợp các giá trị quan sát được sắp xếp theo thời gian với khoảng cách cố định, ví dụ như 10 giây, 30 giây, hay 1 phút Mô hình dự đoán sử dụng các giá trị quan sát gần nhất trong một cửa sổ trượt, có dạng 𝑥(t), 𝑥(t − 1), … , 𝑥(t − w + 1), để dự đoán giá trị tại thời điểm tương lai 𝑥(t + r), trong đó r là khoảng thời gian trong tương lai cần dự đoán.

Hình 2.4: Tổng quan các phương pháp dự báo chuỗi thời gian

Dự đoán chuỗi thời gian đang thu hút sự chú ý từ các nhà nghiên cứu, với mục tiêu nâng cao độ chính xác của các mô hình dự đoán Hình 2.4 minh họa hệ thống phân cấp các phương pháp chuỗi thời gian trước đây cùng với phương pháp luận được đề xuất trong văn bản này.

Trong bài viết này, chúng tôi đã sử dụng một số mô hình thống kê tuyến tính như tự hồi quy (AR), trung bình trượt (MA), tự hồi quy và trung bình trượt (ARMA) và mô hình ARIMA để so sánh Bên cạnh đó, phương pháp dự đoán tài nguyên tuyến tính khác như liên tiến lũy thừa kép (DES) cũng được đề cập Tuy nhiên, nhược điểm lớn của các mô hình này là chúng giả định dữ liệu có dạng tuyến tính và tuân theo một phân phối thống kê nhất định, điều này hạn chế khả năng áp dụng của chúng trong thực tế, nơi mà dữ liệu thường phi tuyến và có độ phức tạp cao.

2.2.1 Mạng nơ-ron truyền thống

Trước năm 2000, mô hình mạng nơ-ron nhận tạo, đặc biệt là mạng MLP sử dụng thuật toán GD và kỹ thuật lan truyền ngược, đã được phát triển để giải quyết các bài toán phi tuyến tính như dự đoán dòng chảy cho quản lý lũ, phân loại dựa trên điện cơ (EMG) và phát hiện bất thường Tuy nhiên, mạng MLP gặp khó khăn về thời gian huấn luyện khi tăng số lượng tầng và unit, đồng thời có nguy cơ tối ưu hóa cục bộ Để khắc phục nhược điểm này, mạng nơ-ron hồi quy (RNN) ra đời, thích hợp cho dữ liệu chuỗi thời gian, nhưng chỉ nhớ được các giá trị gần Mô hình LSTM, phát triển từ RNN, có khả năng học quan hệ dài hạn nhờ vào các cell với ba cổng: cổng vào, cổng quên và cổng ra Nghiên cứu áp dụng LSTM cho dự báo thời tiết với dữ liệu từ Wunderground API cho thấy độ chính xác cao hơn so với RNN và MLP.

Mặc dù RNN và LSTM phù hợp cho dữ liệu chuỗi thời gian, nhưng chúng có cấu trúc phức tạp và thời gian huấn luyện lâu Vì vậy, nhiều mô hình mạng đơn giản hơn đã được phát triển, đạt độ chính xác tương đương với các mô hình hồi quy truyền thống.

Mạng nơ-ron FLNN, được đề xuất trong nghiên cứu [12], chỉ gồm hai tầng đầu vào và đầu ra, giúp rút ngắn thời gian huấn luyện Mặc dù không có tầng ẩn, FLNN vẫn có khả năng học được các quan hệ phi tuyến tính giữa đầu vào và đầu ra nhờ vào các hàm mở rộng ở đầu vào Nghiên cứu [13] chỉ ra rằng FLNN có hiệu quả vượt trội trong việc dự báo tài nguyên so với mạng MLP và có thể cạnh tranh với các mô hình như RNN và LSTM Tuy nhiên, thách thức lớn nhất của FLNN là lựa chọn các hàm mở rộng phù hợp cho từng bài toán cụ thể.

2.2.2 Mạng nơ-ron tự tổ chức

Mô hình SONIA, tương tự như FLNN, nổi bật với tính đơn giản, thời gian huấn luyện nhanh và độ chính xác tốt Với chỉ một tầng ẩn, số lượng đơn vị trong tầng này được học từ tập dữ liệu huấn luyện, giúp mô hình vừa đơn giản vừa nhanh hơn so với các mô hình như RNN, LSTM và MLP với nhiều tầng ẩn Sự áp dụng giải thuật đột biến số đơn vị trong tầng ẩn giúp tăng khả năng nhận diện của mạng MLP khi tiếp nhận nhiều dữ liệu chưa biết Hơn nữa, nhờ vào giải thuật lấy cảm hứng từ giải thuật miễn dịch, khả năng tổng quát hóa của SONIA tốt hơn so với MLP Tuy nhiên, mô hình SONIA vẫn tồn tại nhược điểm do sử dụng giải thuật học GD.

Thuật toán Gradient Descent (GD) trong lan truyền ngược sai số thường gặp vấn đề rơi vào điểm cực trị địa phương, làm chậm tốc độ hội tụ Việc chọn đúng tham số đầu vào có thể giúp thoát khỏi các cực trị này, nhưng không đảm bảo rằng điểm tiếp theo sẽ tốt hơn Để khắc phục tình trạng này, nghiên cứu đã đề xuất sử dụng giải thuật đàn ong (ABC) thay thế GD trong mạng SONIA, với thực nghiệm cho thấy ABC hiệu quả hơn trong việc huấn luyện mạng Giải thuật đàn ong thuộc nhóm giải thuật bầy đàn, là một trong những phương pháp tối ưu hóa lấy cảm hứng từ tự nhiên.

Các giải thuật lấy cảm h ứng từ tự nhiên

Tính toán lấy cảm hứng từ tự nhiên đang thu hút sự chú ý lớn từ các nhà nghiên cứu, đặc biệt là các giải thuật metaheuristics dựa trên hành vi và giao tiếp xã hội của các cá thể trong quần thể sinh vật Những thuật toán này được ưa chuộng nhờ vào những đặc điểm nổi bật như dễ hiểu và thực hiện bằng ngôn ngữ lập trình, khả năng mở rộng từ tìm kiếm cục bộ đến tìm kiếm toàn cục, và không yêu cầu thông tin về gradient như các thuật toán truyền thống.

Giải thuật GD có khả năng vượt qua điểm yếu hội tụ sớm, nhờ vào việc lấy cảm hứng từ tự nhiên để giải quyết các bài toán tối ưu hóa Các giải thuật này mô phỏng các đặc tính sinh học hoặc hành vi vật lý của các loài sinh vật Do đó, các giải thuật metaheuristics có thể được phân loại thành nhiều nhánh khác nhau dựa trên nguồn cảm hứng này.

2.1 mô tả tổng quan các loại giải thuật metaheuristic và nguồn gốc của giải thuật đề xuất)

Nhóm giải thuật dựa trên tiến hóa lấy cảm hứng từ quy luật tiến hóa của sinh vật trong tự nhiên Quá trình tìm kiếm bắt đầu bằng việc tạo ra một tập hợp các cá thể ngẫu nhiên, mỗi cá thể đại diện cho một lời giải cho bài toán Tập hợp này sẽ được phát triển cho đến khi đạt được điều kiện dừng của bài toán Một số giải thuật nổi tiếng trong nhóm này bao gồm Genetic Algorithm (GA), mô phỏng quy luật tiến hóa của Darwin, cùng với các giải thuật khác như Differential Evolution (DE) và Flower Pollination Algorithm (FPA).

Pollination Algorithm (FPA), Coral Reefs Optimization (CRO) [18]

Nhóm swarm-based là nhóm nổi bật và phát triển mạnh nhất trong các nhóm thuật toán, thể hiện hành vi của động vật như virus, chim, cá, chó, mèo và sự giao tiếp của chúng Giải thuật nổi tiếng nhất trong nhóm này là Particle Swarm Optimization (PSO), được lấy cảm hứng từ hành vi xã hội của chim PSO cũng là nền tảng cho nhiều giải thuật khác, bao gồm Bacterial Foraging Optimization (BFO), Whale Optimization Algorithm (WOA) và Sailfish Optimization (SFO).

Nhóm thuật toán dựa trên vật lý bao gồm các phương pháp được phát triển từ các nguyên lý và công thức vật lý, từ trái đất đến vũ trụ Một số thuật toán nổi bật trong nhóm này là Tối ưu hóa Lỗ đen (BHO), được lấy cảm hứng từ lý thuyết về lỗ đen; Tối ưu hóa Kéo co (TWO), dựa trên trò chơi kéo co và các định luật Newton; và Tối ưu hóa Phản ứng hạt nhân (NRO), lấy cảm hứng từ các va chạm và phản ứng của hạt nhân nguyên tử.

Nhóm human-based là nhóm đặc biệt nhất, được lấy cảm hứng từ hành động và giao tiếp xã hội hàng ngày của con người Một số thuật toán nổi tiếng trong nhóm này bao gồm Brain Storm Optimization (BSO), dựa trên cách con người hình thành ý tưởng, và Teaching Learning-based Optimization (TLO).

- [27]) lấy cảm hứng từ việc cách mà các giáo viên dạy học và các học viên tiếp nhận kiến thức

Nhóm system-based lấy cảm hứng từ các hệ thống chung như hệ sinh thái, hệ miễn dịch và hệ thống mạng máy tính Một ví dụ điển hình là Hệ thống miễn dịch nhân tạo, mô phỏng các quy tắc và đặc điểm học tập của hệ miễn dịch động vật có xương sống để giải quyết vấn đề Bên cạnh đó, thuật toán tối ưu hóa trung tâm mầm mô tả các vùng tối và sáng của Trung tâm mầm, cùng với các quá trình cạnh tranh như mở rộng vô tính, liên kết tế bào T và phân rã tín hiệu sống trong hệ thống miễn dịch.

Hình 2.5: Tổng quan các loại giải thuật Metaheuristics

Tối ưu hóa dựa trên hệ sinh thái nhân tạo (AEO) là một thuật toán mới, mô phỏng dòng năng lượng trong hệ sinh thái trái đất với ba hành vi chính: sản xuất, tiêu thụ và phân hủy Nghiên cứu cho thấy AEO có khả năng cạnh tranh với các thuật toán nổi tiếng như GA, PSO và WOA trong việc giải quyết các hàm chuẩn khác nhau Tuy nhiên, AEO vẫn gặp một số hạn chế, bao gồm quá trình cập nhật theo hệ số trọng số tuyến tính có thể làm giảm khả năng thăm dò và khai thác, dẫn đến chất lượng giải pháp cuối cùng không cao Thêm vào đó, việc thiếu chiến lược duy trì sự đa dạng trong các giải pháp có thể gây ra trì trệ hoặc dẫn đến tối ưu cục bộ.

Dựa vào những phân tích bên trên, những điểm dưới đây là sự đóng góp của luận văn này:

 Đề xuất giải thuật cải tiến tối ưu hóa lấy cảm hứng từ hệ sinh thái (IAEO)

 Đề xuất mô hình mạng tự cấu trúc (SSNN) lấy cảm hứng từ mạng SONIA được huấn luyện bởi giải thuật IAEO có tên gọi IAEO-SSNN

 Đề xuất hệ thống tự động co giãn tài nguyên gồm 3 mô-đun: Extraction, Learning và Scaling để có thể ứng dụng mô hình dự báo IAEO-SSNN

Đề xuất mô-đun ra quyết định nhằm sử dụng kết quả từ mô hình dự đoán, đồng thời xem xét các đặc tính của hệ thống ĐTĐM như chất lượng dịch vụ (QoS) và việc vi phạm thỏa thuận mức dịch vụ (SLA).

Mạng tự tổ chức SONIA

Mạng SONIA bao gồm ba tầng: tầng đầu vào, tầng ẩn tự tổ chức và tầng đầu ra Trong đó, vec-tơ đầu vào và tầng ẩn được xem như kháng thể và quả bóng nhận diện tương ứng Quá trình hình thành quả bóng nhận diện diễn ra thông qua việc xây dựng các nốt trong tầng ẩn.

Cấu trúc mạng tự tổ chức SONIA bao gồm các tầng đầu vào và ẩn, trong đó đầu ra của tầng đầu vào là các giá trị đã được chuẩn hóa xi (i=1, 2, NI) Đầu ra của tầng ẩn được xác định bằng khoảng cách giữa các nốt ẩn và nốt đầu vào, được tính theo phương trình (1).

Mạng SONIA được định nghĩa với các kết nối giữa các đơn vị đầu vào và ẩn, được biểu diễn bởi ma trận trọng số wHij, trong đó j là chỉ số của đơn vị ẩn và i là chỉ số của đơn vị đầu vào Hàm kích hoạt f được áp dụng cho đầu ra của mạng để tạo ra đầu ra cuối cùng.

Trong mạng SONIA, k = 1, , NO và wOjk biểu thị kết nối giữa nốt ẩn thứ j và nốt đầu ra thứ k, trong khi bOk là giá trị bias của nốt đầu ra k và hàm g là hàm kích hoạt Mạng SONIA có khả năng tự động xây dựng tầng ẩn từ bộ dữ liệu huấn luyện thông qua hai giai đoạn: xây dựng tầng ẩn (CHL) và đột biến tầng ẩn (MHL) Đối với mỗi đơn vị tầng ẩn, hai giá trị quan trọng được lưu lại là số lượng vec-tơ đầu vào kết nối với đơn vị tầng ẩn thứ j và giá trị cụm trung tâm của HU, phản ánh trọng số liên kết giữa tầng đầu vào và tầng ẩn.

11 ẩn Ví dụ 1 HU thứ j là (tj, wHj) trong đó tj ∈ N như đã nói bên, còn 𝑤 𝐻𝑗 [𝑤 𝐻1𝑗 , 𝑤 𝐻2𝑗 , … , 𝑤 𝐻𝑁𝑂𝑗 ] 𝑇 (j = 1, …, NH)

2.4.1 Giải thuật xây dựng tầng ẩn

Algorithm 1: Constructing Hidden Layers involves processing a normalized training dataset consisting of M samples, with stimulation levels (sl) ranging from 0 to 1 and positive numbers (ps) also within the interval (0, 1) The output of this algorithm includes the hidden units and the central values associated with each hidden unit.

2 Khởi tạo đơn vị tầng ẩn thứ 1 (t1, wH1) với t1=0, wH1 là vector đầu vào được lấy ngẫu nhiên từ tập dữ liệu huấn luyện

3.1 For j = 1 to NH, tìm khoảng cách giữa đầu vào thứ m và trung tâm cụm của

𝑑 𝑚𝑗 = √∑ 𝑁𝐼 𝑖=1 (𝑠 𝑚𝑖 − 𝑤 𝐻𝑖𝑗 ) 2 3.2 Chọn khoảng cách gần nhất c = arg minj dmj

3.3 Nếu khoảng cách ngắn nhất dmc sl (đầu vào không tìm thấy HU gần nó)

 Tạo nốt ẩn mới ( tNH , wH NH ) với tNH = 0 và wH NH = sm

4 Kết thúc vòng lặp for

Trong đó: smi là thành phần thứ i của vector sm wHij là thành phần thứ i của vector wHj

𝛾 là số dương - positive number ps 𝜖 (0, 1)

M : số lượng mẫu dữ liệu đem đi học

NH : số lượng hidden unit, NH sẽ tăng liên tục trong quá trình học

Ncluster : là biến đếm số lượng cụm của tẩng ẩn (số lượng node)

Quá trình này nhằm hình thành các cụm dữ liệu, hay còn gọi là các đơn vị tầng ẩn, từ dữ liệu đầu vào Khoảng cách Euclidean được áp dụng để đo khoảng cách giữa dữ liệu đầu vào và trung tâm cụm, giúp mạng lưới khám phá và phân tích dữ liệu hiệu quả hơn.

12 được các thông tin địa phương của dữ liệu huấn luyện dẫn đến việc cải thiện khả năng nhận diện cũng như tổng quát hóa

Gọi (sm , ym) (m = 1, , M, M ∈ N) là tập các cặp (đầu vào, đầu ra) sẽ được học Giải thuật 1 mô tả cách xây dựng tầng ẩn (CHL)

Gi ả i thu ậ t 2 : Độ t bi ế n t ầ ng ẩ n (Mutation Hidden Layer) Đầu vào : Tập HU và số dữ liệu thuộc hidden unit đó, distance_level: dl ϵ (0, 1) Đầu ra : Tập HU mới

1 Thêm 2 hidden unit vào điểm đầu và điểm cuối của không gian đầu vào bằng cách:

3 Sắp xếp thành phần thứ i (wHi 1, , wHi NH) của giá trị trung tâm của HU

6 Tính khoảng cách giữa 2 hidden unit liền kề theo: dab = √∑ 𝑁𝐼 𝑖=1 (𝑤 𝐻𝑗,𝑖 − 𝑤 𝐻𝑗 +1,𝑖 ) 2

7 If (dab > dl) và (tj < threshold và tj+1 < threshold):

9 Tạo nốt ẩn mới (tNH, wH NH) với tNH = 0 và wH NH được lấy ngẫu nhiên từ 2 hidden unit liền kề j và j + 1

Trong đó: M: số lượng dữ liệu đem huấn luyện

NH: số lượng hidden unit (số lượng cụm) wHj, i là thành phần thứ i của vector wHj wHj+1, i là thành phần thứ i của vector wHj+1

Ncluster : là biến đếm số lượng cụm của tẩng ẩn (số lượng node)

Trong SONIA, giai đoạn đột biến tầng ẩn đóng vai trò quan trọng trong việc xử lý dữ liệu thử nghiệm chưa biết, với những đặc tính khác biệt so với dữ liệu huấn luyện Việc tạo ra đột biến đơn vị tầng ẩn diễn ra trong vùng chưa có đơn vị tầng ẩn nào, và sự bổ sung này được coi là việc thêm dữ liệu nhân tạo vào khu vực đó.

Cải thiện sự phân bố dữ liệu huấn luyện và khả năng tổng quát hóa của mạng là mục tiêu chính trong giai đoạn đột biến đơn vị tầng ẩn Sau khi khởi tạo tế bào B, cần kiểm tra xem đã đủ Hidden Units (HU) để bao quát toàn bộ không gian đầu vào hay chưa Nếu khoảng cách giữa hai HU hàng xóm lớn hơn khoảng cách giới hạn dl 𝜖 (0, 1) và số lượng vec-tơ đầu vào liên kết với hai HU này ít hơn ngưỡng cho phép, cần thực hiện điều chỉnh phù hợp.

Trong quá trình xây dựng mạng nơ-ron, một HU mới sẽ được thêm vào giữa hai HU liền kề với vector trung tâm được xác định ngẫu nhiên xung quanh giá trị trung tâm của khoảng cách giữa hai HU Giải thuật 2 mô tả chi tiết phương pháp đột biến tầng ẩn (MHL) Sau khi hoàn thành việc xây dựng tầng ẩn và bộ trọng số giữa tầng ẩn và tầng đầu vào, tập trọng số giữa tầng ẩn và đầu ra sẽ được tối ưu hóa thông qua giải thuật Gradient Descent.

Giải thuật tối ưu hóa hệ sinh thái (AEO)

Giải thuật tối ưu hóa hệ sinh thái nhân tạo (AEO) là một thuật toán tối ưu hóa dựa trên sự tương tác và chuyển động của các sinh vật trong hệ sinh thái AEO có hai giai đoạn chính: thăm dò và khai thác, tương tự như các giải thuật metaheuristics khác Giai đoạn thăm dò tập trung vào việc tìm kiếm ngẫu nhiên để khám phá toàn bộ không gian tìm kiếm, trong khi giai đoạn khai thác liên quan đến quá trình phân hủy Để cân bằng giữa hai giai đoạn này, tác giả đã đề xuất thêm công đoạn sản xuất.

Trong hệ sinh thái AEO, có ba loại sinh vật: sinh vật sản xuất, sinh vật tiêu thụ và sinh vật phân hủy Trong đó, sinh vật sản xuất thường được xem là tác nhân tiêu cực nhất, trong khi sinh vật phân hủy đóng vai trò tích cực nhất, còn sinh vật tiêu thụ nằm giữa hai loại này Mỗi sinh vật có mức năng lượng hoặc dinh dưỡng nhất định, với mức cao hơn biểu thị giá trị thể chất tốt hơn trong việc giảm thiểu tác động Bài viết sẽ tóm tắt các giai đoạn sản xuất, tiêu thụ và phân hủy, để biết thêm chi tiết, vui lòng tham khảo [30].

Trước khi trình bày ba giai đoạn trong AEO, chúng tôi đã tóm tắt quy trình khởi tạo cần thiết cho tất cả các thuật toán metaheuristic Thuật toán đầu tiên tạo ra N cá thể (N giải pháp cho bài toán) với số chiều tìm kiếm D, bằng cách áp dụng phân phối đều (URD) trong không gian tìm kiếm theo phương trình (3).

Trong bài viết này, 𝑋 𝑖,𝑗 đại diện cho vector vị trí ngẫu nhiên của lời giải, trong khi 𝑋 𝑖,𝑗 𝑚𝑖𝑛 và 𝑋 𝑖,𝑗 𝑚𝑎𝑥 là giá trị nhỏ nhất và lớn nhất trong miền giá trị Giá trị ngẫu nhiên 𝑟𝑎𝑛𝑑 𝑖,𝑗 được lấy từ hàm uniform Cuối cùng, lời giải sẽ được đánh giá thông qua giá trị fitness dựa trên hàm mục tiêu.

Trong giai đoạn này, nhà sản xuất, được coi là tác nhân tồi tệ nhất, sẽ được thay đổi thông qua việc thiết lập các giới hạn thấp hơn và cao hơn, trong khi bộ phân hủy sẽ hướng dẫn các tác nhân này.

Giai đoạn sản xuất này hình thành một cá thể mới trong số các tác nhân tốt nhất Xbest, cùng với 14 nhân khác đang tìm kiếm các khu vực làm giàu Bất kỳ cá nhân nào khác được tạo ra ngẫu nhiên trong không gian tìm kiếm sẽ thay thế cho tác nhân cũ Quá trình này có thể được mô hình hóa bằng các phương trình toán học (4) và (5).

Trong công thức 𝑔 𝑚𝑎𝑥 )𝑟 1 (5), 𝑔 và 𝑔 𝑚𝑎𝑥 lần lượt đại diện cho vòng lặp hiện tại và số vòng lặp tối đa Giá trị 𝑟 1 là một số ngẫu nhiên được phân phối đồng đều trong khoảng [0, 1] Hệ số trọng số tuyến tính được ký hiệu là 𝛼, trong khi 𝑋rand là lời giải ngẫu nhiên.

Giai đoạn này xảy ra khi quá trình sản xuất hoàn tất, trong đó các sinh vật tiêu thụ như động vật ăn cỏ, động vật ăn thịt, và động vật ăn tạp cập nhật dinh dưỡng thông qua việc tiêu thụ các sinh vật có giá trị dinh dưỡng thấp hơn hoặc nhà sản xuất Tác giả của giải thuật AEO đã đề xuất sử dụng kĩ thuật Levy-flight để mô tả quá trình tìm kiếm thức ăn của nhiều loại động vật khác nhau, đóng vai trò là nhà điều hành tiêu thụ Để giảm độ phức tạp trong việc điều chỉnh tham số, hệ số tiêu thụ được mô hình hóa dưới dạng một bước đi ngẫu nhiên không có tham số trong phương trình (6).

Công thức ∁= 𝑣 1 / 2𝑣 2, với 𝑣 1 và 𝑣 2 thuộc phân phối chuẩn N(0, 1), cho thấy rằng C là hệ số hỗ trợ các cá thể thoát khỏi tối ưu cục bộ, từ đó mở rộng khả năng tìm kiếm đến nhiều khu vực khác.

 Động vật ăn cỏ: Tác nhân này chỉ có thể lấy dinh dưỡng từ nhà sản xuất X1 và được lập mô hình bởi (7)

 Động vật ăn thịt: Tác nhân này lấy dinh dưỡng từ người tiêu dùng ngẫu nhiên có dinh dưỡng cao hơn được lập mô hình bởi (8)

Động vật ăn tạp là những sinh vật có khả năng hấp thụ dinh dưỡng từ cả thực vật và động vật, cho phép chúng lấy được nguồn dinh dưỡng phong phú hơn từ nhiều nguồn khác nhau Chúng có thể được mô hình hóa bằng phương trình (9).

Công thức 𝑋 𝑔+1 𝑖 = 𝑋 𝑔 𝑖 + 𝐶(𝑟 2 𝑋 𝑔 𝑖 − 𝑋 𝑔 1 ) + (1 − 𝑟 2 )(𝑋 𝑔 𝑖 − 𝑋 𝑔 𝑗 ) mô tả cách cập nhật chiến lược của một tác nhân trong một quần thể, với 𝑖 ∈ [2, , N] và 𝑗 được chọn ngẫu nhiên từ khoảng [2, i-1], đảm bảo 𝑖 ≠ 𝑗 Biến 𝑟 2 là một số ngẫu nhiên theo phân phối chuẩn trong khoảng [0, 1] Chiến lược này nhấn mạnh quá trình thăm dò, cho phép tác nhân cải thiện hiệu suất bằng cách học hỏi từ các tác nhân khác hoặc từ những tác nhân kém nhất trong quần thể.

Quá trình khai thác liên quan đến giai đoạn phân hủy, trong đó cá thể bắt đầu phân hủy các phần còn lại của một cơ thể đã chết, được mô tả bởi phương trình (10).

𝑋 𝑔+1 𝑖 = 𝑋 𝑏𝑒𝑠𝑡 + 𝐷(𝑒𝑋 𝑏𝑒𝑠𝑡 − ℎ𝑋 𝑔 𝑖 ) (10) trong đó 𝐷 = 3𝑢, 𝑢 ∈ 𝑁(0,1) là hệ số phân rã 𝑒 = 𝑟 3 𝑟𝑎𝑛𝑑𝑖([1 − 2]) − 1 và

ℎ = 2𝑟 3 − 1 là hai tham số trọng lượng 𝑟 3 là số ngẫu nhiên thuộc chuẩn uniform trong phạm vi [0, 1] Cuối cùng, sơ đồ thuật toán AEO được trình bày trong Hình 2.7

Hình 2.7 Sơ đồ thuật toán AEO

MÔ HÌNH DỰ BÁO ĐỀ XUẤT

Giải thuật đề xuất IAEO

Trong bài viết này, chúng tôi sẽ đi sâu vào kĩ thuật Levy-flight và cách kết hợp nó hiệu quả với giải thuật AEO Kĩ thuật Levy-flight không chỉ nâng cao khả năng tìm kiếm toàn cầu (GS) mà còn cải thiện khả năng tìm kiếm cục bộ (LS).

Kỹ thuật Levy-flight là một tập hợp các quy trình ngẫu nhiên không tuân theo phân phối Gaussian, với các bước đi ngẫu nhiên được lấy từ phân phối ổn định Levy Phân phối này được mô tả bằng công thức luật lũy thừa đơn giản 𝐿(𝑠) = |𝑠| −1−𝛽, trong đó 0 < β < 2.

< 𝛽 < 2 là một chỉ số, s là độ dài bước nhảy Từ quan điểm toán học, nó có thể được mô tả theo phương trình (11) ( [31], [32])

Trong bài viết này, 𝜇 đại diện cho thông số vị trí hoặc dịch chuyển, 𝛾 là thông số tỷ lệ với điều kiện 𝛾 > 0, và s là độ dài bước của một lần đi bộ ngẫu nhiên Chúng tôi áp dụng phân bố ổn định Levy đối xứng, có thể có giá trị dương hoặc âm, trong thuật toán của Mantegna [33] Độ dài bước s được mô tả chi tiết trong phương trình (12).

Trong bài viết này, chúng ta xem xét công thức 𝜎 𝑣 = 1 (14), trong đó 𝜇 và 𝑣 là các giá trị từ phân phối chuẩn Phân phối cho 𝑠 tuân theo phân phối Levy với điều kiện |𝑠| ≥ |𝑠 0 |, trong đó 𝑠 0 là độ dài bước tối thiểu Hàm Gamma, ký hiệu là 𝛤(.), được ước tính theo phương trình (15).

Luận văn đề xuất một kỹ thuật sử dụng kích thước bước được tạo ra từ phân phối Levy nhằm khám phá và khai thác hiệu quả khu vực tìm kiếm Kích thước bước này có thể được tính toán theo công thức (16).

Công thức tính bước đi trong vòng lặp hiện tại được biểu diễn như sau: 𝑠𝑡𝑒𝑝(𝑔) = 0.01 ∗ 𝑠(𝑔) ∗ 𝑢𝑛𝑖𝑓𝑜𝑟𝑚(0,1) Trong đó, 𝑔 đại diện cho vòng lặp hiện tại và thế hệ Hệ số nhân 0.01 được áp dụng để giảm kích thước bước, bởi vì kích thước bước được tạo ra từ phân phối Levy thường có giá trị rất lớn.

Tham số 𝛽 là yếu tố quan trọng nhất trong kỹ thuật Levy-flight, với giá trị 𝛽 lớn giúp tăng xác suất khám phá các vùng chưa được biết đến, giảm nguy cơ bị kẹt ở các điểm tối ưu cục bộ Ngược lại, giá trị 𝛽 nhỏ làm giảm xác suất nhảy, cải thiện khả năng khai thác cục bộ Giá trị 𝛽 được khuyến nghị nằm trong khoảng [0, 2] Hình 3.1 minh họa sự khác biệt giữa bước nhảy ngẫu nhiên và bước nhảy Levy, trong đó bước nhảy Levy-flight có thể thực hiện các bước nhảy xa hoặc gần một cách ngẫu nhiên, giúp các thuật toán metaheuristic thoát khỏi các điểm tối ưu cục bộ.

Hình 3.1: Sự khác biệt giữa bước nhảy ngẫu nhiên và bước nhảy Levy (nguồn internet)

Thuật toán AEO nổi bật với khả năng tìm kiếm toàn cầu hiệu quả, nhưng lại gặp phải vấn đề về tốc độ hội tụ thấp trong khu vực tối ưu do tốc độ thăm dò cao hơn trong giai đoạn sản xuất và tiêu thụ so với giai đoạn phân hủy Để khắc phục điều này, luận văn đề xuất áp dụng kỹ thuật Levy-flight nhằm cải thiện đồng thời khả năng thăm dò (tìm kiếm toàn cầu) và khả năng khai thác (tìm kiếm cục bộ) của thuật toán AEO.

3.1.1 Cải thiện giai đoạn tiêu thụ

Trong giai đoạn này, trước khi xác định loại tác nhân là động vật ăn cỏ, động vật ăn tạp hay động vật ăn thịt, cần cập nhật vị trí của nó bằng phương trình tương ứng Tác nhân có 50% khả năng cập nhật vị trí từ một trong ba sinh vật sống và 50% khả năng sử dụng kỹ thuật Levy-flight với 𝛽 = 1,5.

Để đảm bảo tác nhân có thể thoát khỏi tối ưu địa phương và khám phá những giải pháp cao hơn, giá trị 𝛽 được đặt là 1,5 Đồng thời, 𝑋 𝑏𝑒𝑠𝑡 được sử dụng để hướng dẫn tác nhân nhảy về phía giải pháp tốt nhất.

3.1.2 Cải thiện giai đoạn phân hủy (decomposition)

Trong giai đoạn này, trước khi áp dụng kỹ thuật Levy-flight, luận văn giới thiệu phương trình cập nhật mới cho AEO, loại bỏ các tham số không cần thiết và thay thế tham số D bằng một vector phân phối chuẩn D-chiều Chiến lược này nhằm tăng cường khả năng tìm kiếm cục bộ trong mọi chiều không gian tìm kiếm.

Kỹ thuật Levy-flight được áp dụng trong giai đoạn tiêu thụ, trong đó tác nhân có 50% khả năng cập nhật vị trí thông qua quy trình phân rã và 50% khả năng sử dụng kỹ thuật Levy-flight với 𝛽 = 0,5 theo (19).

Để đảm bảo rằng tác nhân có bước nhảy ngắn nhằm tìm kiếm xung quanh vị trí của cá thể tốt nhất 𝑋 𝑏𝑒𝑠𝑡, giá trị 𝛽 được đặt là 0.5, giúp cải thiện khả năng khai thác Các phương trình được đề xuất không chỉ nâng cao khả năng tìm kiếm cục bộ mà còn cải thiện tìm kiếm toàn cục, từ đó tạo ra giải pháp tối ưu hiệu quả và tăng tốc độ hội tụ Thuật toán này được gọi là Improved Artificial Ecosystem Optimization (IAEO), với mã giả của giải thuật IAEO được trình bày trong Giải thuật 3.

Gi ả i thu ậ t 3: Improved Artificial Ecosystem Optimization (IAEO) Đầu vào : Số lượng giải pháp N, số vòng lặp lớn nhất gmax Đầu ra : Giải pháp tốt nhất Xbest

1 : Khởi tạo quần thể ngẫu nhiên và gán g = 0

2 : Đánh giá giá trị fitness của từng gải pháp

3 : Sắp xếp quần thể theo giá trị giảm dần của fitness (fitness càng bé thì giải pháp càng tốt nếu bài toán là tìm minimum)

4 : Tìm giải pháp tốt nhất hiện tại Xbest

6: Cập nhật giải pháp tồi nhất X1 bởi (4)

11: Cập nhật vị trí của giải pháp Xi bởi phương trình (7) 12: Else If 1/3 1, số lượng máy ảo (VMs) cung cấp sẽ vượt quá dự đoán, dẫn đến khả năng cao không vi phạm SLA Tuy nhiên, việc cung cấp quá nhiều VMs sẽ gây ra tình trạng thừa tài nguyên, làm tăng đáng kể chi phí cho người dùng.

Giá trị L được sử dụng để đếm số lần hệ thống vi phạm SLA trong khoảng thời gian L trước đó Mặc dù L có ảnh hưởng đến giá trị VMs cung cấp cuối cùng, nhưng tác động của nó không lớn bằng giá trị s.

 Do vậy, thực nghiệm này luận văn thử nghiệm một số giá trị s và L hợp lí để đánh giá hệ thống co giãn tài nguyên như sau:

Bảng 5.6 trình bày sự so sánh kết quả vi phạm SLA giữa các mô hình với L = 1 và các giá trị s khác nhau Kết quả cho thấy, khi giá trị s = 0.75, tất cả các mô hình đều có tỷ lệ vi phạm SLA lớn hơn 0.7.

Hình 5.2 thể hiện biểu đồ so sánh chỉ số ADI của các mô hình dự đoán khác nhau với ngưỡng tài nguyên sử dụng chấp nhận được vào khoảng [60%, 80%]

Khi phân tích Bảng 5.6, ta nhận thấy rằng khi giá trị s càng nhỏ (s