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
