Skip to content
Permalink
139d8af0c9
Switch branches/tags

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
Go to file
 
 
Cannot retrieve contributors at this time
222 lines (197 sloc) 5.92 KB
using StatsBase
function GT(a,b)
"""
GT function to be used in AST
"""
if a > b
return 1
else
return -1
end
end
function DIV(a,b)
"""
Protected division used in AST
"""
if abs(b) < 10.0^-10
return 1
else
return a/b
end
end
#=
macro create_function(names)
for name in eval(names)
ex = quote
function $(Symbol(name))(x,v)
fs = [:+, :-, :DIV, :GT]
ts = [:x,:v,-1]
return create_single_full_tree(4, fs, ts)
end
end
eval(ex)
end
end
=#
function create_full_tree(depth, fs, ts)
"""
Creates a single AST with full depth
Inputs
depth Current depth of tree. Initially called from main() with max depth
fs Function Set - Array of allowed functions
ts Terminal Set - Array of allowed terminal values
Output
Full AST of typeof()==Expr
"""
# If we are at the bottom
if depth == 1
# End of tree, return function with two terminal nodes
return Expr(:call, fs[rand(1:length(fs))], ts[rand(1:length(ts))], ts[rand(1:length(ts))])
else
# Not end of expression, recurively go back through and create functions for each new node
return Expr(:call, fs[rand(1:length(fs))], create_full_tree(depth-1, fs, ts), create_full_tree(depth-1, fs, ts))
end
end
function create_grow_tree(depth, fs, ts)
if depth == 1
return Expr(:call, fs[rand(1:length(fs))], ts[rand(1:length(ts))], ts[rand(1:length(ts))])
else
choice = rand(1:3)
if choice == 1
return Expr(:call, fs[rand(1:length(fs))], create_grow_tree(depth-1, fs, ts), create_grow_tree(depth-1, fs, ts))
elseif choice == 2
return Expr(:call, fs[rand(1:length(fs))], ts[rand(1:length(ts))], create_grow_tree(depth-1, fs, ts))
else
return Expr(:call, fs[rand(1:length(fs))], create_grow_tree(depth-1, fs, ts), ts[rand(1:length(ts))])
end
end
end
function tournament(scores, size)
"""
Does tournament selection for parents of next population
Inputs
scores Ordered dict of solution number and score
size Size of tournament population
Output
parent1 First parent to copy or crossover
parent2 Second parent to copy or crossover
"""
println(length(scores))
choices = sample(1:length(scores), size, replace=false)
p = []
for c in choices
push!(p, scores[c][2])
end
p = p / sum(p)
return sample(choices, WeightVec(p), 2, replace=false)
end
function crossover(parent1, parent2, max_depth)
"""
Crossover to generate next children
Inputs
parent1 Expression for parent1
parent2 Expression for parent2
max_depth Maximum depth of tree allowed
Output
child1 Child #1 of crossover
child2 Child #2 of crossover
"""
println(dump(parent1))
end
#=
Objective: Find minimum time vehicle control program
Terminal Set: x (position)
v (velocity)
-1
Function Set: +, -, *, DIV, GT, ABS
Cost: Time to bring behicle to phase plane origin
averaged over 20 random initial conditions
Gen. Limit: 50
Pop. Size: 500
Max Initial Tree Depth: 6
Init. Method: Ramped half-and-half
Max. Tree depth: 17
X-Over Prob.: 0.9
Mutation prob.: 0
Number of elites: 2
Selection: Tournament
=#
# Define x, v as globals because I can't figure out how to get
# around creating expressions and not being able to plug
# x and v into them for the past week
# Init everything
pop_size = 10
max_iterations = 1
max_initial_depth = 6
max_depth = 17
xover_prob = 0.9
fs = [:+, :-, :DIV, :GT]
ts = [:x,:v,-1]
tournament_size = 5
points = [rand(-0.75:0.05:.75,2) for i in 1:20]
elites = 2
tau = 0.02
max_time = 5
# Create initial population
population = []
for i in 1:pop_size/2
push!(population, create_full_tree(max_initial_depth, fs, ts))
push!(population, create_grow_tree(max_initial_depth, fs, ts))
end
# Init iterations, scores
iteration = 0
scores = Dict(string(i) => Float64(i) for i in 1:pop_size)
while iteration < max_iterations
# For each member in the population
for (index, member) in enumerate(population)
# For each x,v pair
times = []
for point in points
global x, v
x = point[1]
v = point[2]
t = 0
# Evaluate solution while we arent at max time or x,v~=0
while (t <= max_time) && (abs(x) > 0.01 && abs(v) > 0.01)
if eval(member) >=0
u = 1
else
u = 0
end
# Update x,v,t values
vk = v + tau*u
xk = x + tau*(v+vk)/2
v = vk
x = xk
t = t + tau
end
push!(times,t)
end
scores[string(index)] = mean(times)
end
# return list of sorted scores
sorted_scores = sort(collect(scores), by=x->x[2])
# Init next generation
next_population = []
# copy number of elites to next gen
for i in 1:elites
push!(next_population, population[Int(parse(Float64,sorted_scores[i][1]))])
end
println(next_population)
# Crossover
while length(next_population) < pop_size
# Choose parents with tournament selection
parents = tournament(sorted_scores, tournament_size)
parent1 = population[Int(parse(Float64,sorted_scores[parents[1]][1]))]
parent2 = population[Int(parse(Float64,sorted_scores[parents[2]][1]))]
println(parent1)
# See if we should crossover, if not copy
if rand() < xover_prob
child1,child2 = crossover(parent1, parent2, max_depth)
else
child1=parent1
child2=parent2
end
end
iteration += 1
end