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
