TAILIEUCHUNG - Giải thuật mô phỏng tôi luyện với tiếp cận tìm kiếm tabu cho bài toán tối ưu tổ hợp

Trong bài báo này các tác giả giới thiệu các kết quả thử nghiệm cài đặt giải thuật SA, giải thuật TS và giải thuật lai ghép mô phỏng tôi luyện với tiếp cận Tabu ứng dụng cho bài toán người giao hàng. Kết quả thử nghiệm đối với bài toán này cho thấy giải thuật lai ghép cho kết quả ổn định hơn và thời gian tính toán nhanh hơn so với các giải thuật nguyên thủy. | GIẢI THUẬT MÔ PHỎNG TÔI LUYỆN VỚI TIÉP CẬN TÌM KIÉM TABU CHO BÀI TOÁN TÓI ưu TÔ HỢP Bùi Công Cường 1 Phí Anh Quân Z Phương Minh Nam l Viện Toán học 2 Cục Công nghệ Tin học nghiệp vụ - Bộ Công An Tóm tắt Giải thuật mô phỏng tôi luyện SA 5 và giãi thuật tìm kiếm Tabu TS 4 là các giài thuật tìm kiếm mang tính toàn cục có bước chuyển ngẫu nhiên. Do cả hai giãi thuật đểu tìm kiểm lời giãi tốt hơn từ một tập các lời giải lân cận của lời giải hiện tại nên một cách tự nhiên có thể kết hợp các ưu điểm của chúng đế đưa ra một giải thuật tốt hơn như định hướng cho bước tìm kiếm tiếp theo và tránh lặp lại những điểm tìm kiếm đã được khào sát. Trong bài báo này chúng tôi giới thiệu các kết quá thử nghiệm cài đặt giải thuật SA giãi thuật TS và giãi thuật lai ghép mó phỏng tôi luyện với tiếp cận Tabu ứng dụng cho bài toán người giao hàng. Kết quả thừ nghiệm đối với bài toán này cho thay giãi thuật lai ghép cho kết quá ổn định hơn và thời gian tính toán nhanh hơn so với các giải thuật nguyên thuỹ. Từ khoá Simulated Annealing SA Tabu Seacrh TS 1. GIÓI THIỆU CHUNG . Giải thuật mô phỏng tôi luyện Giải thuật mô phỏng tôi luyện SA được Kirkpatrick Gelatt và Vecchi 5 đề xuất năm 1983 khi mô phỏng toàn bộ quá trình tôi luyện kim loại sử dụng mô hình mô phỏng Monte Carlo Metropolis mờ rộng 7 . Giải thuật được mô tả như một dãy các mô phòng Metropolis hoạt động tại các điểm nhiệt độ cỏ giá trị giảm dần. Giải thuật SA xuất phát từ một điểm ngẫu nhiên Xo trong không gian tim kiếm cùa bài toán tối ưu hoá và nhiệt độ ban đầu To cao 5 7 . Nhiệt độ ban đầu được xác lập ở pha khởi tạo sao cho mọi chuyển dịch trạng thái đều được chấp rihận 9 . Các điểm lận cận j được chọn một cách ngẫu nhiên để trở thành điểm hiện tại i cho bước lặp tiếp theo. Điểm có giá trị hàm giá Fj nhỏ hơn giá trị hàm giá cùa điểm hiện tại Fi luôn được chấp nhận và điểm có giá trị hàm giá lớn hơn sẽ được chấp nhận với xác suất f AẠýì e í1 trong đó AF j Fj - Fị Tk- nhiệt độ tôi luyện hiện tại. Khi nhiệt độ Tk cao 1 tiến tới

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.