• Login
    View Item 
    •   Home
    • UNDERGRADUATE THESES (Koleksi Skripsi Sarjana)
    • UT-Faculty of Mathematics and Natural Sciences
    • View Item
    •   Home
    • UNDERGRADUATE THESES (Koleksi Skripsi Sarjana)
    • UT-Faculty of Mathematics and Natural Sciences
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    PENYELESAIAN TRAVELLING SALESMAN PROBLEM (TSP) ASIMETRISDENGAN ALGORITMA GENETIK COMMONALITY

    Thumbnail
    View/Open
    Valentia Atiyatna - 051810101044.pdf (4.078Mb)
    Date
    2013-12-09
    Author
    Valentia Atiyatna
    Metadata
    Show full item record
    Abstract
    Travelling Salesman Problem (TSP) adalah suatu pencarian rute perjalanan n kota dengan biaya termurah dengan mengunjungi semua kota hanya satu kali. Biaya dapat diasumsikan sebagai jarak, waktu, bahan bakar, dan sebagainya. Berdasarkan biaya, permasalahan TSP dapat dibagi menjadi dua, yaitu TSP-simetris dan TSPasimetris. Pada TSP-simetris, biaya dari kota 1 ke kota 2 adalah sama dengan biaya dari kota 2 ke kota 1. Sedangkan pada TSP-asimetris, biaya dari kota 1 ke kota 2 tidak sama dengan biaya dari kota 2 ke kota 1. Algoritma Genetik Commonality merupakan suatu pengembangan dari algoritma Genetika. Jika dalam algoritma genetika baku, proses reproduksi dilakukan melalui operator tukar silang dan mutasi. Setiap kromosom dievaluasi dengan menggunakan fungsi fitness. Sedangkan pada algoritma genetik commonality, operasi tukar silang didefinisikan kembali dalam dua tahap (Chen & Stephen, 1999) : 1) memelihara common schema maksimal dari dua induk, dan 2) melengkapi solusi dengan construction heuristic. Karena keturunan yang dihasilkan akan lebih baik dibandingkan dengan kedua induknya, maka evolusi akan terjadi tanpa menyatakan seleksi alam secara eksplisit. Dengan kata lain, evolusi terjadi tanpa melibatkan fungsi fitness. Penelitian dilakukan dengan beberapa langkah. Langkah pertama membangkitkan populasi awal (rute awal) menggunakan construction heuristic dengan metode AI (Arbitrary Insertion). Langkah kedua melakukan reproduksi solusi baru dengan operasi tukar silang. Langkah ketiga membentuk populasi baru (kumpulan rute). Berdasarkan penelitian yang telah dilakukan, didapatkan hasil bahwa jarak perjalanan terpendeknya sepanjang 1007 km dengan rute 1-13-24-7-20-23-22-19-1621-25-4-11-9-15-18-14-2-17-8-10-12-5-3-6 dan diperoleh kesimpulan dapat dihasilkan jarak yang sama dengan rute yang berbeda disebabkan adanya proses penyisipan kota-kota yang tidak terdapat pada Graf Partial Order menggunakan metode AI.
    URI
    http://repository.unej.ac.id/handle/123456789/6942
    Collections
    • UT-Faculty of Mathematics and Natural Sciences [3424]

    UPA-TIK Copyright © 2024  Library University of Jember
    Contact Us | Send Feedback

    Indonesia DSpace Group :

    University of Jember Repository
    IPB University Scientific Repository
    UIN Syarif Hidayatullah Institutional Repository
     

     

    Browse

    All of RepositoryCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Context

    Edit this item

    UPA-TIK Copyright © 2024  Library University of Jember
    Contact Us | Send Feedback

    Indonesia DSpace Group :

    University of Jember Repository
    IPB University Scientific Repository
    UIN Syarif Hidayatullah Institutional Repository