ABSTRAKSI: Seiring perkembangan, algoritma TSP dikembangkan untuk memecahkan masalah klasterisasi dokumen dengan menganalogikan dokumen sebagai node. Algoritma ACO merupakan salah satu algoritma optimasi yang menyelesaikan permasalahan TSP. Algoritma ACO terdiri atas AS, ASrank, MMAS, EAS,dan ACS. Algoritma AS merupakan algoritma pertama yang diterapkan dengan menerapkan aturan transisi random proportional, namun untuk jumlah node yang banyak(>30 node), algoritma ini tidak optimal dan waktu eksekusi yang lama, Pengembangan algoritma AS, yaitu algoritma ASrank, MMAS, dan EAS juga belum memberikan solusi yang optimal dan waktu eksekusi yang stabil. Oleh karena itu, selanjutnya dikembangkan algoritma ACS sebagai perbaikan dari algoritma AS dengan menerapkan aturan transisi pseudorandom proportional. Pada Tugas Akhir akan diimplementasikan algoritma ACS sebagai perbaikan dari algoritma AS pada permasalahan klasterisasi.
Pengujian dilakukan untuk mengetahui perbandingan performansi algoritma ACS dan AS dalam klasterisasi dokumen. Dari hasil pengujian, bertambahnya jumlah semut yang digunakan memperbaiki total jarak yang dihasilkan oleh masing-masing algoritma pada Trial Phase. Untuk jumlah semut yang kecil, total jarak yang dihasilkan oleh algoritma ACS lebih baik dibandingkan algoritma AS. Bertambahnya jumlah semut dan jumlah dokumen, menambah lamanya waktu eksekusi, namun algoritma ACS selalu lebih cepat dibandingkan algoritma AS. Pada tahap Dividing Phase, koefisien attachment(δ) mempengaruhi jumlah klaster yang dibentuk, semakin kecil nilai δ, semakin sedikit jumlah klaster yang terbentuk.
Dalam melakukan klasterisasi dokumen,kualitas klaster yang dihasilkan tidak dapat dilihat dari jumlah semut dan total jarak yang dihasilkan algoritma AS dan ACS pada tahap Trial Phase. Pada hasil pengujian, nilai koefisien attachment yang menghasilkan nilai index Davies bou ldin yang optimal adalah data uji 40 dokumen=0.066, data uji 50 dokumen = 0.07, data uji 60 dokumen = 0.0875, data uji 80 dokumen = 0.1035. Dari hasil pengujian, algoritma ACS memerlukan waktu eksekusi yang lebih cepat dibandingkan algoritma AS, sebab pada algoritma ACS diterapkan aturan transisi pseudo-random proportional, dimana dalam pemilihan dokumen yang akan dilewati, semut dapat hanya menerapkan aturan eksploitasi yang memanfaatkan informasi yang sudah ada, tidak perlu menghitung probabilitas semua dokumen. Selain itu, aturan pembaharuan feromon global pada ACS juga memperbaharui jumlah feromon hanya pada tour terbaik saja, tidak di seluruh tour yang dilewati semua semut seperti pada algoritma AS.Kata Kunci : Klasterisasi dokumen, TSP, random proportional, pseudorandom proportional, Algoritma AS, algoritma ACS, Koefisien Attachment, Index Davies-Bouldin.ABSTRACT: With development, the TSP algorithm developed to solve the problem of clustering documents by analogising document as a node. ACO algorithm is one of optimization algorithms that solve the TSP. ACO algorithm consists of AS, ASrank, MMAS, EAS, and ACS. AS is the first algorithm that is applied by applying random proportional transition rule, but for the large number of nodes (> 30 nodes), this algorithm is not optimal and have long execution time. AS algorithm development, namely ASrank algorithm, MMAS, and EAS also has not provide optimal solutions and the stable execution time. Therefore, the ACS algorithm is then developed as an improvement from the AS algorithm by applying pseudorandom proportional transition rule. In this Final Project, ACS algoritham will be implemented as an improvement from the AS on matters of clustering algorithms.
On the clustering of documents, the quality of the resulting clusters can not be seen from the number of ants and generated a total distance of the AS and the ACS algorithm in Phase Trial stage. In the experiments, the value of the coefficient of attachment which produces the index value bou ldin Davies is the optimal test data 40 document = 0066, 50 test data documents = 0.07, test data = 0.0875 60 documents, 80 test data document = 0.1035. From the test results, the ACS algorithm requires a faster execution time compared to the AS algorithm, because at the ACS algorithm is applied the rules of the pseudo-random proportional transition, where the selection of documents that will be passed, the ant can only apply the rules of exploitation which utilize existing information, not need to calculate the probability of all documents. In addition, the global pheromone updating rule in ACS has also renewed the amount of pheromone on the tour only the best, not the entire tour that skipped all the ant algorithm as in the AS.Keyword: document clustering, TSP, random proportional, pseudorandom proportional, AS Algorithm, ACS Algorithm, Coefficient of Attachment, Davies-Bouldin Index.