Pencarian tabu

Pencarian Tabu adalah metode pencarian metaheuristik yang menggunakan metode pencarian lokal untuk optimasi matematis. Algoritma ini dibuat oleh Fred W. Glover pada tahun 1986 dan diformalisasi pada tahun 1989. Pencarian lokal (ketetanggaan) mengambil solusi potensial terhadap suatu masalah dan memeriksa tetangga terdekatnya dengan harapan menemukan solusi yang lebih baik. Metode pencarian lokal seringkali terjebak di daerah suboptimal atau dataran tinggi dengan banyak solusi yang sama-sama cocok. Pencarian Tabu meningkatkan kinerja pencarian lokal dengan melonggarkan aturan dasarnya. Pertama, pada setiap langkah, pergerakan yang memburuk dapat diterima jika tidak ada pergerakan yang lebih baik. Selain itu, larangan diperkenalkan untuk mencegah pencarian kembali ke solusi yang telah dikunjungi sebelumnya. Implementasi pencarian tabu menggunakan struktur memori yang menggambarkan solusi yang dikunjungi atau seperangkat aturan yang disediakan pengguna. Jika suatu solusi potensial telah dikunjungi sebelumnya dalam jangka waktu pendek tertentu atau jika telah melanggar suatu aturan, maka solusi tersebut ditandai sebagai “tabu” (terlarang) sehingga algoritma tidak mempertimbangkan kemungkinan tersebut berulang kali.