Ovako, radim program u C-u, za kolegij na faksu, tema mi je problem trgovačkog putnika, trebam pokazati par algoritama za traženje najpovoljnijeg rješenja problema.
Među ostalim, htio bih se pozabaviti genetskim algoritmima i otprilike imam ideju kako to napraviti.
Imam gotovu mapu gradova, random generiram veliki skup mogućih ruta među tim gradovima. Kroz selekciju, mutacije i križanja među rutama, nakon dovoljno "generacija" populacije rješenja, trebao bih dobiti približno optimalno rješenje problema.
Imam ideju za selekciju populacije i mutacije nad pojedinim rutama, međutim problem mi stvara kako napraviti križanje među rutama. Svaka ruta izgleda kao polje Route[CityCount], početni i završni grad moraju biti 1. Dakle, trebam donekle jednostavan algoritam koji bi nekako iskombinirao dva niza brojeva bez da poremeti uvjet zadatka, odnosno da svaka ruta i dalje sadrži sve gradove bar i samo jednom.
Npr, imam rutu koja izgleda ovako:
1 3 5 2 4 1
i drugu rutu
1 4 5 3 2 1.
Ako ustanovim da je prva ruta bolja, htio bih (random) dio nje prekopirati u drugu, ali onda se još treba pobrinuti da nisam zeznuo drugu rutu. Neka prva ruta ostane nepromijenjena.
Ne znam uopće ima li smisla ovako nešto raditi, pošto nisam siguran hoće li, ako i uspijem ostvariti ovakvo križanje, doprinijeti poboljšanju nove rute ili ovo ispadne ekvivalentno običnom random mutiranju svake pojedine rute.
Prvi put se susrećem s genetskim algoritmima pa zaista ne znam što očekivati i kako napraviti. Da radim s populacijom subjekata koji imaju više mjerljivih svojstava, križanje mi ne bi bio problem. Ovdje mi se čini zaista zeznuto.
Unaprijed hvala i ispričavam se na podužem postu, pokušavao sam biti maksimalno jasan.