Untuk mensimulasikan proses reproduksi, GA mempergunakan operator crossover dan mutation untuk menghasilkan individu baru, dengan harapan individu baru tersebut dapat lebih baik dari parent-nya.
Operator crossover yang digunakan dalam penelitian ini adalah Distance Preserving Crossover (DPX). DPX dimotivasikan berdasarkan analisis Boese pada ruang pencarian dari TSP. Boese menyelidiki bahwa panjang rata-rata antara tour yang optimal secara lokal mirip atau serupa dengan tour yang merupakan optimum secara global. Karena itu, algoritma genetik berupaya melakukan ‘lompatan’ dalam ruang pencarian yang hampir mirip menuju global optimum. Tujuan dari DPX adalah menghasilkan suatu offspring (keturunan) yang memiliki jarak yang sama dari kedua parentnya seperti halnya jarak antara satu parent dengan parent yang lainnya. Pseudo code DPX untuk TSP ( Frisleben & Merz, 1996:2) dapat dilihat pada gambar berikut.
Cara kerja DPX dapat diterangkan sebagai berikut : isi dari parent pertama disalin ke offspring dan semua edge yang tidak terdapat pada parent 2 dihapus. Bagian-bagian yang dihasilkan dari tour yang terpecah-pecah tersebut kemudian disambungkan kembali tanpa menggunakan edge yang hanya terdapat pada salah satu dari kedua parent tersebut. Prosedur greedy reconnection dikembangkan untuk melakukan hal ini, jika edge ( i, j ) telah dihapus, diambil neighbor k dari i terdekat yang tersedia di antara endpoint pecahan tour yang tersisa dan edge ( i, k) ditambahkan ke dalam tour, hal tersebut dijalankan sampai edge ( i, k ) tidak terdapat pada salah satu dari kedua parentnya. Proses ini berlanjut sampai semua fragmen tersambung. Contoh penggunaan DPX untuk Symmetric TSP dapat dilihat pada gambar berikut.
Misalkan diberikan 2 buah parent seperti yang terlihat pada gambar di atas, maka langkah selanjutnya adalah menyalin parent 1 ke offspring dan menghapus edge yang tidak terdapat pada kedua parent, sehingga akan menghasilkan pecahan (fragment) tour 5 3 9 – 1 2 – 8 – 0 6 – 7 – 4.
Prosedur greedy reconnection digunakan untuk mengatur kembali sambungan yang terputus tersebut dengan menghasilkan offspring. Proses penyambungan kembali tersebut dapat dijelaskan sebagai berikut : Pertama-tama sebuah kota dipilih secara random sebagai titik awal untuk penyambungan kembali. Misalkan kota yang akan dipilih sebagai titik awal tersebut adalah kota 6, maka endpoint dari fragmen yang mengandung kota 6 (dalam hal ini kota 0 ) dipertimbangkan dan neighbor yang paling dekatnya dalam kumpulan (set) kota yang merupakan awal atau endpoint dari fragmen tour yang belum dikunjungi, yakni : { 5, 9, 1, 2, 4 }, ditentukan. Kota 8 dan 7 tidak terkandung dalam set ini sebab tidak diinginkannya untuk menyisipkan edge ( 0, 8 ) atau edge (0, 7) karena kedua edge tersebut tidak terdapat dalam parent 1 atau parent 2. Misalnya diasumsikan kota yang terdekat dengan kota 0 adalah kota 5, maka kota 0 disambungkan dengan kota 5, dan ujung dari fragmen yang disambungkan ( kota 9 ) perlu untuk dipertimbangkan untuk proses selanjutnya. Pada tahap ini set kandidat kota tersebut berubah menjadi { 2, 8, 7 }. Proses tersebut dilakukan berulang-ulang hingga semua fragmen disambungkan.
Untuk asymmetric TSP, pada saat proses greedy reconnection untuk penyambungan edge dilakukan, isi setiap fragmen yang akan disambungkan tidak boleh dibalik. Sebagai contoh, fragmen { 1, 2 } dan { 0, 6 } pada contoh di atas tidak boleh balik menjadi { 2, 1 } dan { 6, 0 }.
.
