Optimasitraveling salesman problem dengan algoritma genetika menggunakan operator partially matched crossover

INDONESIA:

Traveling Salesman Problem (TSP) adalah suatu permasalahan untuk menemukan lintasan dari seorang salesman yang berawal dari sebuah lokasi asal, mengunjungi sebuah himpunan kota dan kembali lagi ke lokasi asal yang mana total dari jarak yang ditempuh adalah minimum dan setiap kota dilewati tepat hanya satu kali. Algoritma genetika adalah salah satu metode yang terbaik untuk menyelesaikan kasus TSP.

Penelitian ini difokuskan pada menemukan lintasan/rute terpendek menggunakan Algoritma Genetika. Asumsinya bahwa berawal dari suatu titik (node) awal kemudian melewati semua himpunan kota dan kembali lagi ke awal tanpa ada yang terlewati dua kali.

Langkah-langkah dalam Algoritma Genetika meliputi: (1) Inisialisasi Populasi, (2) Seleksi, (3) Crossover (kawin silang), dan (4) Mutasi. Metode yang digunakan untuk membangkitkan populasi awal adalah dengan Algoritma Random Generator. Inti dari Algortima Random Generator adalah pembangkitan bilangan acak untuk nilai setiap gen sesuai dengan representasi kromosom. Jumlah bilangan acak yang dibangkitkan sebanyak gen pada setiap kromosom. Metode yang digunakanuntuk proses seleksi adalah Roulette Wheel Selection. Metodeinimenggunakan roda roulette sebagai alat untuk menyeleksikromosom. Semakin besar probabilitas kumulatif suatu kromosom, semakin besar pula probabilitas terpilihnya kromosom tersebut untuk menjadi parent. Proses selanjutnya adalah cross over dengan menggunakan PMX (Partially Matched Crossover). Prosedur dalam menggunakan operator PMX adalah sebagai berikut: pertama tentukan dua posisi pada kromosom dengan aturan acak, substring yang berada dalam dua posisi ini dinamakan daerah pemetaan, kemudian tukar substring antar parent untuk menghasilkan keturunan, lalu tentukan hubungan pemetaan di antara dua daerah pemetaan, dan yang terakhir tentukan kromosom keturunan mengacu pada hubungan pemetaan. Proses mutasi menggunakan Swapping Mutation, yaitu dengan menukar posisi sebuah gen dengan gen sesudahnya.

Kesimpulan yang didapatkan setelah menyelesaikan TSP dengan Algoritma Genetika menggunakan PMX didapatkan solusi terbaik/rute terpendeknya adalah dengan jarak 158. Saran untuk penelitian selanjutnya adalah mengembangkan operator crossover untuk PMX agar menghasilkan solusi yang lebih baik.

English

Traveling Salesman Problem(TSP) is a problem to determine the pathofa salesman who came fromahome location, visiting aset of citieS and back to the home location where the total distance travele disminimum and each city passed right only one time. Genetic algorithmisone of the best methods to solve the TSP case.

This study focused on finding theshortest route/path using Genetic Algorithms. Assumption is that started froma point(node) then passes all initial set ofthe cityandbackagainto the beginning without any point passed twice.

Steps in Genetic Algorithms include: (1) Initialize population, (2) Selection, (3) Crossover, and (4) Mutation. The method used to generate the initial population of thealgorithmis the Random Number Generator. The essence of the algorithms Random Number Generator is generating random numbers to the value of each gene according to the representation of chromosomes. The number of random numbers generated as many genes on each chromosome. The method usedforthe selection process is the Roulette Wheel Selection. This method uses the roulette wheel as a tool for selecting chromosomes. The greater the cumulative probability of a chromosome, the greater the probability that elected to become the parent chromosome.The next process is to use a cross over PMX(Partially Matched Crossover). The procedure of using PMX operator is as follows: first define two position son the chromosome with random rules, substring that these two positions are in the area called mapping, then the substring swap between parent to produce off spring, and define the mapping relationships between the two regions mapping, and the latter refers to the off spring chromosomes specify the mapping relationship. Mutation processusing Swapping Mutation, ie by swapping the position of a gene by gene afterwards.
The conclusion obtained after completing the TSP with Genetic Algorithm usingPMX obtained the best solution/shortest routeis 1→7→2→6→5→3→4→1 with the total distance is 158.

Suggestions forfurtherresearchisto developforPMXcrossoveroperatorto producea better solution.