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
