CHƯƠNG 1.1 CƠ SỞ LÝ LUẬN Trong các ứng dụng thực tế ở Việt Nam, (chẳng hạn nhóm bài toán vận trù học) hầu như đa số cách tiếp cận hiện nay là xây dựng các hệ thống thông tin phục vụ cho quá trình quản lý. Một mục tiêu cao nhất của các hệ thống này là giám sát được toàn bộ hoạt động của hệ thống và có thể cung cấp những thông tin thống kê phục vụ cho việc hoạch định. Tuy nhiên, việc hoạch định này chủ yếu là dựa vào kinh nghiệm, không có sự hỗ trợ mạnh mẽ từ máy tính. Kể cả khi điều hành một hoạt động (chẳng hạn như điều hành xe buýt), các quy trình và tham số của quy trình cũng chưa được xem xét một cách kỹ lưỡng để hoạt động điều hành đó đạt được độ hiệu quả cao nhất.
Những điểm yếu nêu trên có thể được giải quyết phần nào nếu biết sử dụng những thuật toán tối ưu được hiện thực trên máy tính. Rõ ràng đây là nhu cầu thấy rõ trong thực tế ngày nay ở Việt Nam. Trong thời gian làm việc với các nhóm nghiên cứu khác nhau (cả thiên về ứng dụng và về công nghệ thông tin), chúng tôi (những người làm về toán – tin) thấy nhu cầu có những thư viện (công cụ) tính toán mạnh, nhưng dễ sử dụng để đưa đến cho các nhà nghiên cứu ứng dụng. Nếu không có những thư viện như thế thì hầu như cách tiếp cận thông thường nhất của họ là mua (sử dụng) các sản phẩm của nước ngoài.
Điều này có thể đưa đến 2 điểm yếu : • Khó tiếp cận đến được một giải pháp tốt cho các bài toán đặc thù (ở Việt Nam). • Không nắm bắt được kiến thức, công nghệ của nước ngoài để sản sinh ra các sản phẩm (bài báo, phần mềm) mang dấu ấn của riêng mình. Ngoài ra, nếu không có những thư viện như trên thì việc sử dụng tài nguyên đã được đầu tư là lãng phí. Trong một thời gian dài quản lý PTN Tính toán khoa học có hệ thống tính toán khá mạnh [Nam07] (nhưng đã khá lỗi thời), nhưng hiệu suất sử dụng chưa đạt như mong đợi.
Một phần chính là các thư viện (công cụ) cung cấp trên đó còn khá hạn chế. Do đó chúng tôi thấy rất cần thiết để phát triển các thư 1 viện hỗ trợ để cung cấp cho các chuyên gia lĩnh vực ứng dụng. Trong khuôn khổ của đề tài, chúng tôi mong muốn tạo ra một thư viện cho lĩnh vực tối ưu rời rạc để ứng dụng vào các bài toán vận trù học trong thực tế.2 CÁC CÔNG TRÌNH NGHIÊN CỨU LIÊN QUAN Tính toán mềm (soft computing) không phải là một lĩnh vực mới mẻ trên thế giới và các thuật toán tối ưu (tìm kiếm) trong lĩnh vực này cũng đã được nghiên cứu rất nhiều. Các thuật toán meta-heuristic trong xu thế này đã được sử dụng rộng rãi trong nhiều nghiên cứu cơ bản và ứng dụng, cũng như đem lại nhiều hiệu quả kinh tế.
Tham khảo chi tiết về lĩnh vực nghiên cứu này có thể tìm thấy trong [Bian09]. Tuy nhiên cho đến ngày nay vẫn còn rất nhiều nghiên cứu trong lĩnh vực này nhằm giải quyết các thách thức chính sau: • Đặc thù của ứng dụng: có khá nhiều loại meta-heuristic và mỗi loại đều có những ưu và khuyết điểm đặc thù (ví dụ, SA khá tốt trong các bài toán tối ưu kỹ thuật với các hàm mục tiêu liên tục, nhưng lại không hoạt động tốt lắm trong các bài toán tối ưu trên đồ thị). Do đó, để có thể ứng dụng một loại meta-heuristic vào một ứng dụng cụ thể một cách hiệu quả, nhiều nghiên cứu và thử nghiệm tính toán phải được thực hiện. Đó là lý do chúng ta không thể áp dụng máy móc những tiếp cận dựa trên meta-heuristic đã có vào giải quyết những bài toán tối ưu xuất phát từ thực tế ngày nay.
Và đây cũng là động lực cho các nghiên cứu dựa trên meta-heuristic ngày nay. • Meta-optimization: như đã nêu trên, sử dụng một loại meta-heuristic cho một ứng dụng cụ thể có thể không đạt hiệu quả như mong muốn. Đó là thách thức mà các nghiên cứu ngày nay hướng đến một cách tiếp cận phối hợp các meta-heuristic khác nhau nhằm tận dụng các ưu thế đặc thù. Ngoài ra, lựa chọn một bộ các tham số tốt cho các meta-heuristic cũng không thực hiện được dễ dàng, và thường phải dựa trên nhiều tính toán thử nghiệm và kinh nghiệm của nhà khoa học.
Do đó, meta-optimization là một xu hướng phối hợp để cung cấp những giá trị tốt cho các thông số một cách tự động. • Sử dụng môi trường tính toán mạnh: giải quyết các bài toán tối ưu có không gian nghiệm lớn (hoặc phức tạp) yêu cầu những tài nguyên tính toán rất 2 mạnh, không chỉ hướng đến việc tìm ra lời giải nhanh, mà còn hướng đến chất lượng của lời giải tốt hơn. Đây cũng là xu thế đang được sử dụng mạnh mẽ ngày nay trong tính toán khoa học. Sử dụng hạ tầng tính toán mạnh trong meta-heuristic cũng không nằm ngoài xu thế này [Alba05, Hoff08].
Nhìn chung, các thách thức nêu trên không dễ giải quyết. Rõ ràng là để có thể tạo ra các tiếp cận meta-heuristic đặc thù cho một ứng dụng thì phải có sự hiểu biết khá tường tận về ứng dụng này (ví dụ về cấu trúc không gian nghiệm, cách biến đổi/di chuyển tốt trong không gian nghiệm, hàm lượng giá nghiệm …). Thách thức khoa học càng khó thì sự hiểu biết này càng quan trọng, và chỉ có những nhà nghiên cứu ứng dụng mới nắm bắt được. Vì thế việc xây dựng một công cụ hỗ trợ mạnh giúp các nhà khoa học tiếp cận nhanh đến các meta-heuristic là một nhu cầu rất lớn.
Và công cụ càng mạnh hơn nếu có khả năng triển khai tính toán trên những hệ thống tính toán mạnh, mà không cần nhiều hiểu biết (và thay đổi trong chương trình) khi làm việc trên những hệ thống như thế. Đây cũng chính là định hướng của đề xuất trong đề tài này. Cụ thể hơn đề tài mong muốn giải quyết một thách thức cụ thể hơn “xây dựng một thư viện lập trình hỗ trợ tối ưu tổ hợp”. Như ta đã biết, chất lượng của các giải pháp tìm kiếm tùy thuộc rất nhiều vào không gian và phương thức tìm kiếm.
Vì thế càng mở rộng vùng không gian tìm kiếm và mở rộng tính đa dạng tìm kiếm một cách hợp lý, kết quả tìm kiếm sẽ đạt gần giá trị tối ưu toàn cục. Tuy nhiên, dễ nhận ra rằng, việc tìm kiếm càng mở rộng, thời gian tìm kiếm sẽ gia tăng một cách đáng kể. Vì vậy nếu ứng dụng giải pháp tính toán song song, vừa tận dụng được ưu thế của từng thuật toán, tận dụng nguồn tài nguyên tính toán mạng lưới cải thiện đáng kể hiệu quả tính toán. Trên thế giới hiện nay cũng có những nghiên cứu tương tự.
Chúng cố gắng tạo ra những công cụ linh hoạt cho phép xây dựng các thuật toán dựa trên meta- heuristic, cũng như bổ sung các meta-heuristic mới khi cần thiết. Có hai xu hướng phát triển công cụ chính là mô hình hộp trắng và hộp đen. jMetal [Duri06], ParadisEO [Caho04], Shark [Igel08] theo mô hình hộp trắng, trong đó, người dùng có thể sử dụng các thành phần cơ bản được xây dựng sẵn, hoặc có thể thêm thuật toán mới bằng cách sử dụng các thành phần cơ bản có sẵn của công cụ. Ngược lại, 3 trong mô hình hộp đen, người dùng phải viết từ đầu nếu muốn thêm thuật toán mới.
Đây là mô hình áp dụng trong PISA [Bleu03]. Tuy nhiên với PISA, việc phát triển thuật toán có sẵn khá dễ dàng. Phần lớn các thư viện tìm kiếm meta-heuristic này đều không hỗ trợ cho tính toán song song. Chẳng hạn như jMetal, Shark, PISA or MOMHLib++ chỉ đáp ứng cho việc thực hiện tính toán tuần tự.
Bên cạnh đó, có nhiều khung ứng dụng có khả năng chạy song song như DGPE và ParadisEO. Có thể nói, công cụ mạnh nhất trong lĩnh vực nghiên cứu này là ParadisEO. Nó cung cấp khá nhiều tính năng mạnh (giải quyết các thách thức khoa học nêu trên) và đã ứng dụng khá hiệu quả vào nhiều bài toán tính toán lớn ngày nay trong: sinh – tin học [Tant06], thiết kế mạng di động [Talb07]. Một đóng góp quan trọng của ParadisEO là khả năng triển khai tính toán trên các hệ thống song song (sử dụng MPI) và phân bố (dùng MPICH- G2).
Tuy nhiên chúng không hỗ trợ cho xây dựng các ứng dụng trên mạng lưới. Các version ParadisEO sử dụng MPI, nhưng chúng chỉ chạy trên cụm hoặc các mạng máy trạm. ParadisEO-G là một cải tiến ParadisEO và nó có thể chạy trên môi trường mạng lưới bằng cách sử dụng MPICH-G2. Ví dụ khác là thư viện DGPF, nó hỗ trợ nhiều cách thực hiện như tuần tự, client-server hoặc P2P, nhưng để thực hiện ứng dụng, các dịch vụ thời gian chạy (runtime) phải được cài đặt trên tất cả các máy.
Tuy nhiên, sự phối hợp các meta-heuristic chưa được quan tâm nhiều trong ParadisEO. Việc kết hợp các meta-heuristic lại với nhau lấy cảm hứng từ tự nhiên là một chủ đề đang được quan tâm hiện nay. Người đọc có thể tham khảo trong [Yang13] để biết thêm tổng quan về hướng này. Việc phối hợp các meta-heuristic thành công có thể xem trong [Dom13], trong đó nhóm tác giả lấy cảm hứng từ việc kết hợp nên các hydro-carbon.
Đề tài của chúng tôi cũng đề xuất cách kết hợp các meta-heuristic lại với nhau, nhưng ở dạng tổng quát hơn trong một mô hình workflow, được sử dụng nhiều ngày nay trên các hệ thống tính toán lớn (ASKALON [Fahr05], Pegasus [Deel05]) và trong doanh nghiệp (BPEL, tham khảo thêm trong [Lour08]). Kết quả nghiên cứu ban đầu cũng đã được đưa vào sử dụng trong một đề tài khoa học công nghệ của Sở KHCN TP.HCM 2007-2009, “Xây 4 dựng công cụ lập trình cho tính toán thích nghi hiệu năng cao trên môi trường tính toán lưới’’ (đã nghiệm thu thành công). Hơn thế nữa, trong xu thế ảo hóa ngày nay thì việc sử dụng các hạ tầng tính toán có tính mềm dẻo cao là một hướng đi được các nhà nghiên cứu theo đuổi. Nghiên cứu công bố trong [Truong11] đã chỉ ra rằng với các nhóm nghiên cứu nhỏ thì hạ tầng tính toán đám mây là một hướng đi hợp lý.
Tuy nhiên, triển khai các tính toán trên những hạ tầng như thế vẫn còn nhiều thách thức khoa học. Trong nghiên cứu của chúng tôi chỉ mới dừng lại đăng ký triển khai trên hạ tầng dựa trên MPI cơ bản. Nhiều phương thức tính toán song song được đề xuất cho các thuật toán meta- heuristic và được chia thành 3 dạng. Cách đầu tiên là cố gắng thực hiện tính toán song song trong mỗi phương thức tìm kiếm.