Aplikasi Algoritma Genetika Untuk Mencari Rute Tependek N-Buah Node

Persoalan pencarian rute terpendek dari sejumlah node pada penelitian ini termasuk pada persoalan optimasi travelling salesman problem, TSP kurva terbuka yang node asal dan node tujuan telah ditentukan. Bila dipandang dari sudut komputasinya persoalan ini sepintas sangat sederhana. Namun, pada kenyataanya jika jumlah node cukup banyak maka akan sangat sulit dan membutuhkan waktu yang cukup lama jika dikerjakan dengan perhitungan matematika biasa.

Salah satu algoritma yang muncul untuk menyelesaikan persoalan ini adalah algoritma genetika, AG.Pada peneletian ini akan dibuat program AG untuk mencari rute terpendek dari n buah node. Sistem AG didesain menggunakan representasi kromosom dengan skema pengkodean menggunakan skema permutation encoding.

Bebrapa pengujian telah dilakukan pada program AG ini. Pengujian dilakukan dengan variasi probabilitas pindah silang dan mutasi, variasi jumlah kromosom dalam satu populasi dan jumlah generasi. Dari hasil pengujian, dapat disimpulkan bahwa secara keseluruhan AG cukup efektif dan mudah digunakan dalam mencari solusi yang �bagus�.

short route Seeking Problem from a number of node at this research is inclusive of optimasi problem �Travelling Salesman Problem�, TSP Curve opened which origin node and target have been determined. When in the light of its computing is this problem cusorily very simple. But at the fact, if amount node of quite a lot hence will very difficult and require the sufficient time if done with the ordinary mathematics calculation. Complexity TSP of like this is equal to factorial the than amount node, n!.

One of algorithm which emerge to finish this problem is Genetic Algorithms, AG. At this research, program of AG will be made to look for the shortest route from n of nodes. AG System is designed use the chromosome representation with the code scheme �permutation encoding�.

Some examination have been done at this program. Examination done with the variation of crossover and mutation probability, variation of sum of chromosome in one population and generation. From examination result, inferential that as a whole effective AG enough and it is easy to used in searching �good� solution .