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
