Another remark, I just ran the (original) algorithm again, for 20 cities, 100 chromosomes, and modifying distances so 0,1,2,...,18,19 is the minimum path, for 500 iterations.
the "minimal" path found was 18 19 1 0 16 5 6 13 14 15 10 9 8 17 12 11 4 2 3 7 which is not too bad, all things considered. -------------------------------------------- On Tue, 12/22/15, 'Jon Hough' via Programming <[email protected]> wrote: Subject: Re: [Jprogramming] Genetic algorithms? To: [email protected] Date: Tuesday, December 22, 2015, 6:28 PM Thanks, Raul. It's a good point. This hasn't been validated at all. I suppose the lazy way to validate would be to force a single path to be minimal: modifydistance =: 3 : 0 'from to distance' =. y if. to = >: from do. distance =. 1 elseif. distance < 10 do. distance =. 10 end. from, to, distance ) Then, before running the algorithm do cities =. modifydistance"1 cities so the minimal path is definitely 0->1->2->...->MAX_CITY I ran my original algorithm with the modified distances, and it doesn't even come close to the optimal solution (after 500 iterations, which took about 2 minutes to run, for 26 cities). One point to note is the algorithm searches for the minimum hamiltonian path, not cycle, so presumably if it gets stuck at a non-optimal start city (i.e. doesn't make "city 0" the start city) it could throw it all off. But for whatever reason, the algorithm does not converge anywhere near the correct result. I don't know enough about genetic algorithms to know if this bad result is expected. e.g. it could be trapped in local minima or something. But anyway, it's a disappointing turn of events. Other points to note: Number of chromosomes is pretty small (~40), I think in general this should be much bigger. My original algorithm stops after a set number of iterations, not after convergence is found, which is not good. -------------------------------------------- On Tue, 12/22/15, Devon McCormick <[email protected]> wrote: Subject: Re: [Jprogramming] Genetic algorithms? To: "J-programming forum" <[email protected]> Date: Tuesday, December 22, 2015, 11:11 AM Thanks, everyone, for your responses. Hopefully I'll have some time over the holidays to look at this and compare it to some sources in C# I found online. On Mon, Dec 21, 2015 at 11:25 AM, Raul Miller <[email protected]> wrote: > Typo - last minute name change - the unused reference to nextchild, at > the end, should have been > > nextchildren=. nextchildren + 2 > > Thanks, > > -- > Raul > > > On Mon, Dec 21, 2015 at 8:13 AM, Raul Miller <[email protected]> > wrote: > > Here is a "slightly more j-like" re-implementation. > > > > I presume it's approximately a "work-alike". (I say approximately > > because of the random aspect of its implementation): > > > > NB. solution to the Traveling Salesman Problem using a genetic algorithm > > NB. to find the minimum cost path through all cities. > > > > require'stats' > > > > MUTATION_RATE=: 0.1 NB. rate of gene mutation after mating. > > POPULATION=: 40 NB. population of chromosomes > > MATING_POP=: <.POPULATION % 2 > > SELECTED_POP=: <.MATING_POP % 2 > > CITYCOUNT=: 26 NB. number of cities. > > > > list=: 2 comb CITYCOUNT > > > > NB. list of cities with random distances > > cities=: (list,.0)+1000*?0,.~1"0 list > > boxedcities=: <"1 list > > > > NB. create POPULATION chromsomes, each representing > > NB. a hamiltonian path on the city network. > > createChromosomes=: ] ?&.> POPULATION&$ > > > > chromosomes=: createChromosomes CITYCOUNT > > > > NB. calculates the cost of a single chromosome, > > NB. i.e. the total distance along the path > > NB. represented by the chromosome. > > cost=: 3 : 0 @> > > edges=. <"1 /:~"1 (2]\ > y) > > +/, 2{"1 ((edges ="0 _ boxedcities) # cities) > > > > ) > > > > NB. sort the paths, since we want the minimum cost. > > sortPaths=: chromosomes /: (cost"0 chromosomes) > > > > sortChromosomes=: ] /: cost"(0) > > > > smear1=:4 :0 > > have=. (e.~ i.@#) y > > if. 0 e. have do. > > (have i. 0) x} y > > else. > > y > > end. > > ) > > > > smear2=:4 :0 > > have=. (e.~ i.@-@#) y > > if. 0 e. have do. > > (have i. 0) x} y > > else. > > y > > end. > > ) > > > > mate=: 3 : 0 > > 'mother father child1 child2'=: y > > CUT=. 5 > > > > for_j. i. # mother do. > > if. j < CUT do. > > child1=. j smear1 child1 > > child2=. j smear1 child2 > > elseif. j > CUT do. > > child1=. j smear2 child1 > > child2=. j smear2 child2 > > end. > > end. > > > > NB. handle mutations > > mrate=. 100 * MUTATION_RATE > > chance=. ? 100 > > if. mrate < chance do. NB. always succeeds because ? is rigged > > mutated=. ~.? 2 # CITYCOUNT > > child1=. (<mutated) C. child1 > > end. > > chance=. ? 100 > > if. mrate < chance do. > > mutated=. ~. ? 2 # CITYCOUNT > > child2=. (<mutated) C. child2 > > end. > > > > child1;child2 > > ) > > > > > > NB. iterate for x generations, where one > > NB. iteration is the mating of all > > NB. matable chromosomes, and the sorting > > NB. of the new chromosomes by the cost function. > > NB. y is boxed ordered paths through the cities > > iterate=: 4 : 0 > > NB. only perform set number of iterations. Ideally > > NB. should only stop once the min cost stops changing > > NB. for a set number of iterations. > > c=. 0 > > for. i.#x do. > > c=. c + 1 > > nextchildren=. MATING_POP+0 1 > > for_j. i. SELECTED_POP do. > > choice=. ?SELECTED_POP > > newGeneration=. mate (j,choice,nextchildren) { y > > y=. newGeneration nextchildren } y > > nextchild=. nextchildren + 2 > > end. > > > > y=. sortChromosomes y > > end. > > y > > ) > > > > Note that I have left sample data generation the way that it was in > > the original (for example, sortChromosomes depends on the distances > > between cities). > > > > But I am not sure how you'd test something like this for correctness. > > And I'd need a good test heuristic before I could take this any > > further. > > > > Any suggestions? > > > > Thanks, > > > > -- > > Raul > > > > > > On Sun, Dec 20, 2015 at 1:54 AM, 'Jon Hough' via Programming > > <[email protected]> wrote: > >> I created a toy genetic algorithm program to solve the traveling > salesman problem for a randomly generated graph (cities with distances). > It's not written in very J-like code unfortunately. It also seems pretty > slow, possibly due to lots of in-place assignments. Anyway, it might > interest you. > >> > >> NB. solution to the Traveling Salesman Problem using a genetic algorithm > >> NB. to find the minimum cost path through all cities. > >> > >> MUTATION_RATE=: 0.1 NB. rate of gene mutation after mating. > >> POPULATION=: 40 NB. population of chromosomes > >> MATING_POP=: <.POPULATION % 2 > >> SELECTED_POP=: <.MATING_POP % 2 > >> CITYCOUNT=: 26 NB. number of cities. > >> > >> list=: (#~ </"1)@(#: i.@:(*/)) 2 # CITYCOUNT > >> > >> NB. list of cities with random distances > >> cities=: list,"(1 1) (1,~ 2!CITYCOUNT) $ 1000 * (? (2!CITYCOUNT) # 0) > >> boxedcities=: <"1 ( 0 1 {"1 cities) > >> > >> NB. create POPULATION chromsomes, each representing > >> NB. a hamiltonian path on the city network. > >> createChromosomes=: ] ?&.> (<"0@:(POPULATION&$)) > >> > >> chromosomes=: createChromosomes CITYCOUNT > >> > >> NB. calculates the cost of a single chromosome, > >> NB. i.e. the total distance along the path > >> NB. represented by the chromosome. > >> cost=: 3 : 0 > >> edges=. <"1 /:~"1 (2]\ > y) > >> +/, 2{"1 ((edges ="0 _ boxedcities) # cities) > >> > >> ) > >> > >> NB. sort the paths, since we want the minimum cost. > >> sortPaths=: chromosomes /: (cost"0 chromosomes) > >> > >> sortChromosomes=: ] /: cost"(0) > >> > >> mate=: 3 : 0 > >> mother=. >0{y > >> father=. >1{y > >> child1=. >2{y > >> child2=. >3{y > >> CUT=. 5 > >> > >> for_j. i. # mother do. > >> if. j < CUT do. > >> for_k. i. CITYCOUNT do. > >> if. -.(k e. child1) do. > >> child1=. k (j}) child1 > >> break. > >> end. > >> end. > >> for_k. i.CITYCOUNT do. > >> if. -.(k e. child2) do. > >> child2=. (k{father) j} child2 > >> break. > >> end. > >> end. > >> elseif. j > CUT do. > >> for_k. i. CITYCOUNT do. > >> k=. <: CITYCOUNT - k > >> if. -.(k e. child1) do. > >> child1=. (k) j}child1 > >> break. > >> end. > >> end. > >> for_k. i.CITYCOUNT do. > >> > >> k=. <: CITYCOUNT - k > >> if. -.((k{father) e. child2) do. > >> child2=. (k{father) j}child2 > >> break. > >> end. > >> end. > >> > >> > >> end. > >> end. > >> > >> > >> NB. handle mutations > >> mrate=. 100 * MUTATION_RATE > >> chance=. ?. 2 # 100 > >> if. mrate < 0{chance do. > >> mutated=. ? 2 # CITYCOUNT > >> m1=. (0{mutated){child1 > >> m2=. (1{mutated){child1 > >> child1=. (m2, m1) mutated} child1 > >> end. > >> > >> chance=. ?. 2 # 100 > >> if. mrate < 0{chance do. > >> mutated=. ? 2 # CITYCOUNT > >> m1=. (0{mutated){child2 > >> m2=. (1{mutated){child2 > >> child2=. (m2, m1) mutated} child2 > >> end. > >> > >> child1;child2 > >> ) > >> > >> > >> NB. iterate for x generations, where one > >> NB. iteration is the mating of all > >> NB. matable chromosomes, and the sorting > >> NB. of the new chromosomes by the cost function. > >> iterate=: 4 : 0 > >> generations=. x > >> orderedPaths=. y > >> op=. orderedPaths > >> > >> NB. only perform set number of iterations. Ideally > >> NB. should only stop once the min cost stops changing > >> NB. for a set number of iterations. > >> c=. 0 > >> while. c < generations do. > >> c=. c + 1 > >> nextchild=. MATING_POP > >> for_j. i. SELECTED_POP do. > >> mother=. j { op > >> father=. (? SELECTED_POP) { op > >> child1=. nextchild { op > >> child2=. (>: nextchild) { op > >> newGeneration=. mate mother,father,child1,child2 > >> > >> op=. newGeneration (nextchild, (>: nextchild)) } op > >> nextchild=. nextchild + 2 > >> > >> end. > >> > >> op=. sortChromosomes op > >> end. > >> op > >> ) > >> > >> > >> > >> > >> For example, > >> > >> ]a=. 100 iterate chromosomes > >> > >> will give a list of possible paths, the minimum cost path (found after > 100 iterations) is first. > >> > >> cost 0{ a > >> > >> gives the minimum cost. > >> > >> > >> -------------------------------------------- > >> On Fri, 12/18/15, Devon McCormick <[email protected]> wrote: > >> > >> Subject: [Jprogramming] Genetic algorithms? > >> To: "J-programming forum" <[email protected]> > >> Date: Friday, December 18, 2015, 5:52 AM > >> > >> Has anyone done work in J on genetic > >> algorithms? I'm thinking of coding > >> up something along these lines as I don't find any relevant > >> hits for this > >> on the J wiki. > >> > >> -- > >> > >> Devon McCormick, CFA > >> > >> Quantitative Consultant > >> ---------------------------------------------------------------------- > >> For information about J forums see http://www.jsoftware.com/forums.htm > >> ---------------------------------------------------------------------- > >> For information about J forums see http://www.jsoftware.com/forums.htm > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm > -- Devon McCormick, CFA Quantitative Consultant ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
