MỘT KHUNG THỨC CHO GIẢI THUẬT MEMETIC
Phan Anh Tuấn, Dương Tuấn Anh
Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách khoa – ĐHQG Tp. HCM
patcse@gmail.com, dtanh@cse.hcmut.edu.vn

Tóm tắt
    Giải thuật Memetic, sự kết hợp giải thuật di truyền với tìm kiếm cục bộ, là một trong những siêu-heuristic mạnh nhất để giải những bài toán tối ưu tổ hợp phức tạp. Trong bài báo này, chúng tôi giới thiệu một khung thức hướng đối tượng mà hổ trợ cho việc xây dựng những giải thuật memetic với khả năng tái sử dụng tối đa. Khung thức này được phát triển bằng Java, sử dụng các mẫu thiết kế cho phép mở rộng dễ dàng và tiện dụng trong nhiều lãnh vực ứng dụng. Khung thức này đã được thử nghiệm qua việc xây dựng một giải thuật memetic để giải bài toán phủ tập.

    Từ khoá: Khung thức, mẫu thiết kế, giải thuật memetic, bài toán phủ tập.

A FRAMEWORK FOR MEMETIC ALGORITHMS
Phan Anh Tuan, Duong Tuan Anh
Faculty of Computer Science and Engineering, University of Technology – VNU HCMC
patcse@gmail.com, dtanh@cse.hcmut.edu.vn

Abstract
    Memetic algorithm, a combination of genetic algorithm with local search, is one of the most powerful metaheuristics to solve complex combinatorial optimization problems. In this paper, we will introduce an object-oriented framework which allows the construction of memetic algorithms with a maximum reuse. This framework has been developed in Java using design patterns to allow its easy extension and utilization in different problem domains. Our framework has been experimented through the development of a memetic algorithm for solving set covering problems. The development of this application shows that it is very effective to use the framework as a general tool for solving a specific problem by memetic algorithm.

    Key words: Framework; design patterns; memetic algorithm; set covering problem.