tailieunhanh - Một thuật toán hiệu quả dựa trên giải thuật tối ưu đàn kiến giải bài toán

Bài viết đề xuất một giải thuật CO cho bài toán | -trung tâm rời rạc. Trong thuật toán này, phương pháp CO được áp dụng dựa trên sự biểu diễn bài toán như một bài toán tối ưu hóa rời rạc hai mức. | Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin FAIR 9 Cần Thơ ngày 4-5 8 2016 DOI MỘT THUẬT TOÁN HIỆU QUẢ DỰA TRÊN GIẢI THUẬT TỐI ƯU ĐÀN KIẾN GIẢI BÀI TOÁN TRUNG TÂM Vũ Đức Quang1 Hoàng Xuân Huấn2 Đỗ Thanh Mai3 1 Đại học Sư phạm Đại học Thái Nguyên 2 Đại học Công nghệ Đại học Quốc gia Hà Nội 3 Bộ môn KHCB Khoa Ngoại ngữ Đại học Thái Nguyên vuducquang@ huanhx@ TÓM TẮT Bài toán trung tâm nhằm định vị điểm mở cơ sở cho hai đối thủ Trước và Sau đối thủ của Trước để mỗi người thu hút được thị phần lớn nhất cho mình đang là bài toán thời sự. Trong bài toán này Trước được mở p cơ sở và Sau được mở r cơ sở. Thông thường các khách hàng sẽ chọn cơ sở gần họ nhất làm nhà cung cấp cho họ. Chúng ta cần tìm cách chọn ra p vị trí đặt cơ sở cho Trước nhằm tối đa hóa thị phần và đó là lợi nhuận của mình với lưu ý là Sau cũng luôn tìm cách tối ưu hóa thị phần dựa trên phân bố cơ sở đã biết của Trước. Đây là một bài toán quy hoạch 2 mức thuộc loại NP-khó và đã có nhiều thuật toán được đề xuất. Trong bài báo chúng tôi đề xuất một thuật toán tối ưu đàn kiến có sử dụng tìm kiếm địa phương. Kết quả thử nghiệm cho thấy thuật toán mới đề xuất của chúng tôi so với 3 phương pháp công bố gần đây có sử dụng phần mềm công cụ CPLEX thì thuật toán thứ nhất có kết quả ngang bằng với kết quả của chúng tôi nhưng chạy chậm hơn thuật toán thứ hai có kết quả kém hơn kết quả của chúng tôi nhưng chạy nhanh hơn còn thuật toán thứ 3 cho kết quả ngang bằng và chạy nhanh hơn thuật toán của chúng tôi. Từ khóa thuật toán ACO tìm kiếm địa phương r p -trung tâm. I. GIỚI THIỆU Bài toán -trung tâm -centroid lần đầu tiên được Hakimi 11 nghiên cứu dưới dạng bài toán rời rạc có thể phát biểu như sau. Cho một tập hữu hạn các địa điểm có thể chọn để đặt các cơ sở dịch vụ và một tập hữu hạn của các vị trí của khách hàng ma trận là khoảng cách từ khách hàng tới cơ sở các giá trị xác định lợi nhuận .