Bagaimana cara meningkatkan algoritma genetika untuk TSP?

Ini adalah algoritma genetika saya, langkah demi langkah:

  1. Hasilkan dua populasi awal secara acak, dan pilih tur yang paling cocok dari keduanya.

  2. Lakukan persilangan terurut, yang memilih bagian acak dari tur kecocokan pertama dan mengisi sisanya dari tur kedua secara berurutan.

  3. Mutasi tur ini dengan menukar dua kota secara acak jika tur tersebut hanya 1,3 kali lebih baik dari tur 10% teratas dalam populasi awal (yang baru saja saya lakukan dengan induksi, memilih tur buruk yang dihasilkan) - Saya ingin sekali ubah ini tetapi tidak bisa memikirkan cara yang lebih baik.

    • The mutation is selected from a population of several mutations.

  4. Mengembalikan tur yang dihasilkan.

Namun mutasinya hampir SELALU lebih buruk, jika tidak sama dengan persilangan.

Saya sangat menghargai bantuan. Terima kasih!


python mutation traveling-salesman genetic-algorithm crossover
person sam price    schedule 06.12.2017    source sumber
comment
Jangan lakukan crossover. Itu tidak perlu.   -  person Ray    schedule 06.12.2017
comment
Persilangan sebenarnya meningkatkan apa yang dipilih dari populasi awal (orang tua) - tetapi tidak menghasilkan tur terbaik.   -  person sam price    schedule 06.12.2017
comment
Persilangan dan mutasi tidak menghasilkan gen yang lebih baik; mereka membuat gen yang berbeda. Memilih membuat segalanya lebih baik. Dan persilangan adalah komplikasi yang tidak perlu.   -  person Ray    schedule 06.12.2017
comment
Itu juga yang saya pikirkan, tetapi hilangkan persilangan dan mutasi dan yang Anda miliki hanyalah kekerasan. Saya perlu merancang algoritma genetika.   -  person sam price    schedule 06.12.2017
comment
Anda masih melakukan mutasi. Pilih secara acak di antara gen teratas & mutasikan. Ini bukan kekerasan, ini stokastik. Dan itu bersifat genetik karena gen Anda bermutasi.   -  person Ray    schedule 07.12.2017
comment
Jadi maksud Anda algoritme Anda adalah memaksakan solusi yang layak dan kemudian mengubahnya secara acak dan berharap solusi tersebut membaik? Saya tidak melihat bagaimana ini akan berhasil dengan baik. Saya sangat menghargai komentarnya.   -  person sam price    schedule 07.12.2017
comment
Anda tidak berharap keadaannya membaik; Anda benar-benar memilih yang terbaik untuk bermutasi. Seleksi adalah bagian terpenting. Begitulah cara kerja evolusi. Dan sekali lagi, seperti dalam evolusi alami, persilangan adalah opsional.   -  person Ray    schedule 08.12.2017
comment
Saya tahu Anda memilih yang terbaik untuk bermutasi, tetapi jika Anda memutasi yang terbaik seperti yang saya lakukan, yaitu hanya bertukar kota secara acak, maka Anda akan selalu mendapatkan solusi yang lebih buruk. Saya masih tidak mengerti mengapa Anda mengambil solusi yang baik dan kemudian menjalankan fungsi yang kemungkinan besar akan menjadikannya solusi yang lebih buruk.   -  person sam price    schedule 08.12.2017
comment
Mutasi tidak selalu menghasilkan solusi yang lebih buruk. Sekali lagi, crossover TIDAK menciptakan solusi yang lebih baik, namun juga menghasilkan solusi yang lebih buruk seperti mutasi.   -  person Ray    schedule 08.12.2017
comment
Selain itu, algoritma genetika lain yang menyelesaikan sdt, cukup menggunakan mutasi. Anda dapat mencarinya di YouTube.   -  person Ray    schedule 08.12.2017

Jawaban (1)


arrow_upward
0
arrow_downward

Masalah dalam GA adalah mempersempit ruang pencarian Anda terlalu cepat dan mencapai solusi maksimal lokal. Anda perlu memastikan bahwa Anda tidak memimpin solusi Anda dengan cara apa pun selain dalam fungsi seleksi/kebugaran. Jadi ketika Anda berkata,

mengapa Anda mengambil solusi yang baik dan kemudian menjalankan fungsi yang kemungkinan besar akan menjadikannya solusi yang lebih buruk

,alasannya adalah Anda INGIN mendapat kesempatan agar solusi tersebut mengambil langkah mundur, kemungkinan besar solusi tersebut perlu menjadi lebih buruk sebelum menjadi lebih baik. Jadi sebenarnya Anda harus menghilangkan logika penilaian apa pun dari operator genetika Anda, serahkan saja pada proses seleksi.

Selain itu, persilangan dan mutasi harus dilihat sebagai 2 cara berbeda dalam menghasilkan individu anak, Anda harus menggunakan salah satu cara tersebut. Dalam praktiknya, ini berarti Anda memiliki peluang untuk melakukan mutasi pada salah satu orang tua atau persilangan antara 2 orang tua. Biasanya peluang mutasi hanya 5% dan persilangan digunakan untuk menghasilkan 95% lainnya.

Persilangan menyimpan informasi genetik dari kedua orang tuanya (anak adalah bayangan cermin), sehingga satu anak akan lebih buruk dari orang tuanya dan yang lainnya lebih baik (atau keduanya sama). Jadi dalam hal ini dengan crossover, jika ada perubahan, Anda akan selalu mendapatkan individu yang lebih baik.

Di sisi lain, mutasi tidak memberikan jaminan akan adanya individu yang lebih baik, namun mutasi dilakukan dengan tujuan memperkenalkan data baru, membantu memindahkan GA dari skenario maksimal lokal. Jika mutasi gagal untuk memperbaiki individu dan memperburuk keadaan, maka kecil kemungkinannya untuk terpilih menjadi orang tua (yaitu Anda tidak memerlukan logika ini dalam operator mutasi itu sendiri).

Anda memilih yang terbaik untuk bermutasi

Hal ini tidak sepenuhnya benar, individu yang baik seharusnya mempunyai peluang lebih tinggi untuk terpilih. Di sini ada perbedaan halus bahwa individu BURUK juga dapat dipilih sebagai orang tua. Sekali lagi hal ini membantu mengurangi kemungkinan tercapainya solusi maksimal lokal. Hal ini juga berarti bahwa individu terbaik dalam suatu generasi bisa saja (dan seringkali memang demikian) justru menjadi lebih buruk. Untuk mengatasi hal ini kita biasanya menerapkan 'elitisme', dimana individu terbaik selalu disalin ke generasi berikutnya (yang sedang/tidak menjalani operasi).

Akan bermanfaat juga jika saya dapat mengomentari operator genetik mana yang Anda gunakan. Saya telah menemukan siklus persilangan dan mutasi inversi bekerja dengan baik menurut pengalaman saya.

person M. Mansell    schedule 16.01.2018