Examples

Some examples on using the package.

Defining Search Spaces

The available search spaces can be defined using different methods, depending on the requirements.

Permutation Space

Firstly, import the package.

julia> using SearchSpaces

Define a search space defined by permuting five positive integers $1,2,\ldots, 5$.

julia> space = PermutationSpace(5)PermutationSpace{Vector{Int64}}([1, 2, 3, 4, 5], 5)
julia> rand(space) # sample one random element5-element Vector{Int64}:
 2
 1
 5
 4
 3

Permutations of an array of elements:

julia> space = PermutationSpace([:red, :green, :blue])PermutationSpace{Vector{Symbol}}([:red, :green, :blue], 3)
julia> rand(space)3-element Vector{Symbol}:
 :green
 :blue
 :red

k-permutation of elements:

julia> k = 22
julia> space = PermutationSpace([:red, :green, :blue, :alpha], k)PermutationSpace{Vector{Symbol}}([:red, :green, :blue, :alpha], 2)
julia> rand(space)2-element Vector{Symbol}:
 :green
 :blue

Bit arrays

An array of bits can be defining by providing the number of bits:

julia> n_bits = 44
julia> space = BitArraySpace(n_bits)BitArraySpace(4)
julia> rand(space)4-element Vector{Bool}:
 0
 0
 0
 1

Box-Constrained Space (Hyperrectangle)

A box-constrained space (a.k.a. hyperrectangle) is defined by providing lower bounds and lower bounds.

Defining a 5-dimensional hyperrectangle with vertices in 0 and 1.

julia> space = BoxConstrainedSpace(lb = zeros(5), ub = ones(5))BoxConstrainedSpace{Float64}([0.0, 0.0, 0.0, 0.0, 0.0], [1.0, 1.0, 1.0, 1.0, 1.0], [1.0, 1.0, 1.0, 1.0, 1.0], 5, true)
julia> rand(space)5-element Vector{Float64}:
 0.9960705772749037
 0.8974433545148671
 0.9869964864491805
 0.6187220310090221
 0.5734627475580487

A 3-dimensional integer box-constrained space with values between -10 and 10.

julia> space = BoxConstrainedSpace(lb = fill(-10, 3), ub = fill(10, 3))BoxConstrainedSpace{Int64}([-10, -10, -10], [10, 10, 10], [20, 20, 20], 3, true)
julia> rand(space)3-element Vector{Int64}:
 -3
  8
 -6

By default, the lower and upper bounds are rigid, one can specify whether the bounds are rigid or not.

julia> space = BoxConstrainedSpace(lb = zeros(2), ub = ones(2), rigid=false)BoxConstrainedSpace{Float64}([0.0, 0.0], [1.0, 1.0], [1.0, 1.0], 2, false)

An interval can be defined as:

julia> my_interval = (-π..π)BoxConstrainedSpace{Float64}([-3.141592653589793], [3.141592653589793], [6.283185307179586], 1, true)
julia> rand(my_interval)1.9218607948542896

Mixed spaces

Mixed space can be compose using Cartesian product.

julia> space = MixedSpace(:X => PermutationSpace(3), :Y => BitArraySpace(3), :Z => BoxConstrainedSpace(lb = zeros(2), ub = ones(2)))MixedSpace defined by 3 subspaces:
X => PermutationSpace{Vector{Int64}}([1, 2, 3], 3)
Y => BitArraySpace(3)
Z => BoxConstrainedSpace{Float64}([0.0, 0.0], [1.0, 1.0], [1.0, 1.0], 2, true)
julia> rand(space)Dict{Symbol, Vector} with 3 entries:
  :Z => [0.146004, 0.390729]
  :X => [2, 1, 3]
  :Y => Bool[0, 1, 0]

julia> space = MixedSpace(:x => 1:10, :y => [:red, :green], :z => PermutationSpace(1:3))MixedSpace defined by 3 subspaces:
x => PermutationSpace{UnitRange{Int64}}(1:10, 1)
y => PermutationSpace{Vector{Symbol}}([:red, :green], 1)
z => PermutationSpace{UnitRange{Int64}}(1:3, 3)
julia> rand(space)Dict{Symbol, Any} with 3 entries:
  :y => :green
  :z => [3, 2, 1]
  :x => 8

Sampling Random Elements

Random elements in a search space can sampled using rand method.

search_space = PermutationSpace([:red, :green, :blue])
rand(search_space)

3-element Vector{Symbol}:
 :blue
 :green
 :red

Sampling ten elements:

rand(search_space, 10)

10-element Vector{Vector{Symbol}}:
 [:red, :green, :blue]
 [:blue, :green, :red]
 [:red, :blue, :green]
 [:blue, :green, :red]
 [:blue, :green, :red]
 [:red, :green, :blue]
 [:green, :blue, :red]
 [:green, :blue, :red]
 [:red, :blue, :green]
 [:red, :green, :blue]

Sampling three elements:

mixed = MixedSpace(:x => 1:10, :y => [:red, :green], :z => PermutationSpace(1:3))
rand(mixed, 3)

3-element Vector{Dict{Symbol, Any}}:
 Dict(:y => :green, :z => [2, 1, 3], :x => 8)
 Dict(:y => :red, :z => [1, 2, 3], :x => 4)
 Dict(:y => :red, :z => [3, 1, 2], :x => 1)

Sampling All Elements

Warning

Sampling and collecting all elements in search space can overflow memory.

Implemented samplers return an iterator to avoid memory overflow.

search_space = PermutationSpace([:red, :green, :blue])
for x in GridSampler(search_space)
    @show x
end

x = [:red, :green, :blue]
x = [:red, :blue, :green]
x = [:green, :red, :blue]
x = [:green, :blue, :red]
x = [:blue, :red, :green]
x = [:blue, :green, :red]

Similarly:

GridSampler(PermutationSpace([:red, :green, :blue])) |> collect

6-element Vector{Any}:
 [:red, :green, :blue]
 [:red, :blue, :green]
 [:green, :red, :blue]
 [:green, :blue, :red]
 [:blue, :red, :green]
 [:blue, :green, :red]

Mixing Spaces

We can mix spaces via Cartesian product.

bounds = BoxConstrainedSpace(lb = zeros(Int, 5), ub = ones(Int, 5))
permutations = PermutationSpace([:red, :green, :blue])
bits = BitArraySpace(3)

BitArraySpace(3)

Performing Cartesian product:

mixed = bounds × permutations × bits

MixedSpace defined by 3 subspaces:
S3 => BitArraySpace(3)
S2 => PermutationSpace{Vector{Symbol}}([:red, :green, :blue], 3)
S1 => BoxConstrainedSpace{Int64}([0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], 5, true)

Sampling a random element:

rand(mixed)

Dict{Symbol, Vector} with 3 entries:
  :S2 => [:green, :blue, :red]
  :S1 => [1, 1, 1, 1, 0]
  :S3 => Bool[0, 1, 0]

Cardinality (number of elements)

cardinality(mixed)

Finding Elements

A search space is only a place where certain items are. However, those elements appear under the presence of a sampler. Let's find the argument that minimizes function.

Finding the argument that minimizes a given function.

julia> searchspace = MixedSpace(
                           :N    => 1:50,
                           :flag => [true, false],
                           :p    => BoxConstrainedSpace(0.0, 1)
                           );
julia> f(x) = x[:flag] ? sum(1:x[:N])-x[:p] : x[:p] + sum(1:x[:N])f (generic function with 1 method)
julia> argmin(f, GridSampler(searchspace))Dict{Symbol, Real} with 3 entries:
  :N    => 1
  :p    => 1.0
  :flag => true

Cardinality

The number of elements in a set is known as the cardinality. The package includes a method to compute this value:

The number of permutation strings of size 3:

julia> space = PermutationSpace([:red, :green, :blue])PermutationSpace{Vector{Symbol}}([:red, :green, :blue], 3)
julia> cardinality(space)6

The number of bit arrays of size 10:

julia> space = BitArraySpace(10)BitArraySpace(10)
julia> cardinality(space)1024

Number of 5-dimensional arrays of integers:

julia> space = BoxConstrainedSpace(lb = zeros(Int, 5), ub = ones(Int, 5))BoxConstrainedSpace{Int64}([0, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], 5, true)
julia> cardinality(space)32

Number of 5-dimensional arrays of Floats:

julia> space = BoxConstrainedSpace(lb = zeros(5), ub = ones(5))BoxConstrainedSpace{Float64}([0.0, 0.0, 0.0, 0.0, 0.0], [1.0, 1.0, 1.0, 1.0, 1.0], [1.0, 1.0, 1.0, 1.0, 1.0], 5, true)
julia> cardinality(space)Inf

Is an element in the search space?

Once a search space is defined, maybe we would like to know whether an element is in the search space. We can use the in method:

julia> space = BoxConstrainedSpace(lb = zeros(3), ub = ones(3))BoxConstrainedSpace{Float64}([0.0, 0.0, 0.0], [1.0, 1.0, 1.0], [1.0, 1.0, 1.0], 3, true)
julia> [0.0, 0, 0] in spacetrue
julia> [100.0, 0, 0] in spacefalse
julia> [1, 1, 1] in spacefalse

Note that the last example returned false due to the vector of integers is not in the space of floats.

Solving the 8-Queens problem

This example illustrates how to finding all solutions for the 8-queens problem.

Let's represent a chessboard using an 8-permutation. Here, chessboard[i] = j means that there is a queen in the row i and column j. The main idea is to find all chessboard configurations such that the queens are not attacking each other.

using SearchSpaces

chessboards = PermutationSpace(8)

PermutationSpace{Vector{Int64}}([1, 2, 3, 4, 5, 6, 7, 8], 8)

A valid chessboard is obtained when any queen is attacking another queen. The following function is used to check that:

function isvalid(chessboard)
   # check attack in both diagonas for each queen
   for i = 1:length(chessboard)
       Δrows = i + chessboard[i]
       Δcols = i - chessboard[i]
       for j = (i+1):length(chessboard)
           # check diagonals
           if  j + chessboard[j] == Δrows || j - chessboard[j] == Δcols
               return false
           end
       end
   end
   true
end

isvalid (generic function with 1 method)

Now, let's compute all chessboards (valid or not) by brute force using the grid sampler.

sampler = GridSampler(chessboards);

Once the sampler is instantiated, we can filter those valid chessboards.

all_valid_chessboard = filter(isvalid, collect(sampler))

92-element Vector{Any}:
 [1, 5, 8, 6, 3, 7, 2, 4]
 [1, 6, 8, 3, 7, 4, 2, 5]
 [1, 7, 4, 6, 8, 2, 5, 3]
 [1, 7, 5, 8, 2, 4, 6, 3]
 [2, 4, 6, 8, 3, 1, 7, 5]
 [2, 5, 7, 1, 3, 8, 6, 4]
 [2, 5, 7, 4, 1, 8, 6, 3]
 [2, 6, 1, 7, 4, 8, 3, 5]
 [2, 6, 8, 3, 1, 4, 7, 5]
 [2, 7, 3, 6, 8, 5, 1, 4]
 ⋮
 [7, 3, 1, 6, 8, 5, 2, 4]
 [7, 3, 8, 2, 5, 1, 6, 4]
 [7, 4, 2, 5, 8, 1, 3, 6]
 [7, 4, 2, 8, 6, 1, 3, 5]
 [7, 5, 3, 1, 6, 8, 2, 4]
 [8, 2, 4, 1, 7, 5, 3, 6]
 [8, 2, 5, 3, 1, 7, 4, 6]
 [8, 3, 1, 6, 2, 5, 7, 4]
 [8, 4, 1, 3, 6, 2, 7, 5]

Print resulting chessboard:

function print_chessboard(chessboard)
    println("Chessboard: ", chessboard)
    for i in eachindex(chessboard)
        for j in eachindex(chessboard)
            print(chessboard[i]==j ? "Q " : "_ ")
        end
        println()
    end
end

print_chessboard (generic function with 1 method)

print_chessboard(first(all_valid_chessboard))

Chessboard: [1, 5, 8, 6, 3, 7, 2, 4]
Q _ _ _ _ _ _ _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
_ _ _ _ _ _ Q _
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _

print_chessboard(last(all_valid_chessboard))

Chessboard: [8, 4, 1, 3, 6, 2, 7, 5]
_ _ _ _ _ _ _ Q
_ _ _ Q _ _ _ _
Q _ _ _ _ _ _ _
_ _ Q _ _ _ _ _
_ _ _ _ _ Q _ _
_ Q _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _