xxxxxxxxxx

5.7 s

Demo for the PlutoCon 201

Author: Daniel Molina Cabrera

Talk: Teaching Computer Sciences and Metaheuristics Algorithms using Pluto

xxxxxxxxxx

8.4 μs

Maximize Diversity Problem (MDP)

In this problem we have a set of data n and the target is to choose m of them (n < m) to maximize the distance between the selected. In other words, it is wanted $M \subset N$ that maximize $\sum_{i \in N} \sum_{j \in N} D_{i j}$ .

xxxxxxxxxx

10.9 μs

showvalues (generic function with 1 method)

xxxxxxxxxx

21.7 μs

Initial Set

Then, from the following data:

xxxxxxxxxx

4.1 μs

scene (generic function with 1 method)

xxxxxxxxxx

69.4 μs

xxxxxxxxxx

47.1 ms

xxxxxxxxxx

4.2 s

Distance of the problem

We are not going to work with the points, we are going to work using the distances between them.

xxxxxxxxxx

3.6 μs

ArgumentError: `DataFrame` constructor from a `Matrix` requires passing :auto as a second argument to automatically generate column names: `DataFrame(matrix, :auto)`

DataFrames.DataFrame(::Matrix{Float64})@dataframe.jl:363
top-level scope@Local: 3[inlined]

 
begin
    dists = pairwise(Euclidean(), problem, dims=1)
    df = DataFrame(dists)
    rename!(df, string.(1:n))
end

---

Problem: We choose the m value and the distance measure

xxxxxxxxxx

2.8 μs

m value:

xxxxxxxxxx

6.5 ms

metrica (generic function with 2 methods)

xxxxxxxxxx
 
function metrica(solucion, dists=dists)
    distancias = Float64[]
    for i in 1:m
        for j in (i+1):m
            push!(distancias, dists[solucion[i],solucion[j]])
        end
    end
    
    return sum(distancias)
end

48.5 μs

Solution for that problem

A random solution could be create easily choosing randomly m variable without repetition.

xxxxxxxxxx

3.7 μs

xxxxxxxxxx

30.2 μs

random solution: {2, 4, 8}

xxxxxxxxxx

148 ms

The interpretation of the solution will be:

xxxxxxxxxx

3.5 μs

plot_sol (generic function with 1 method)

xxxxxxxxxx

78.9 μs

In which the selected instances are in red, and the connexions with dashed lines. The fitness is obtained with the measure function.

xxxxxxxxxx

3.1 μs

UndefVarError: dists not defined

metrica(::Vector{Int64})@Other: 2
plot_sol(::Vector{Int64})@Other: 10
top-level scope@Local: 1

xxxxxxxxxx
 
plot_sol(solucion)

---

Local Search algorithm

The local search starts from an initial solution, and it is continuously improved. It can be described as:

Initial current solution is a random solution S.
If it has not yet finished (less than 100_000 evaluations or local optimum) continue steps 3-7.
Choose randomly a position i from S.
It create a new solution, in which the value of position i is changed by a new value j, where $j \in {N - s o l u c i o n [i]}$ .
Compare the new solution S' with the previous one.
If S' fitness is worse than the S fitness, go to step 2.
If it is better $S \leftarrow S^{'}$ and go to step 2.

xxxxxxxxxx

16.4 μs

BL (generic function with 1 method)

xxxxxxxxxx

93.5 μs

We apply the LS during iterations

xxxxxxxxxx

60.1 μs

UndefVarError: dists not defined

metrica(::Vector{Int64})@Other: 2
var"#BL#4"(::Int64, ::Nothing, ::typeof(Main.workspace75.BL), ::Vector{Int64})@Other: 3
top-level scope@Local: 2

xxxxxxxxxx
 
begin
    best, best_fit = BL(solucion, maxevals=maxevals)
    best_sol = join(string.(best), ", ")
    total = maxevals
    md"""
    The best found solution is **\{$(best_sol)\}** with fitness: **$(round(best_fit,digits=3))**
    """
end

---

UndefVarError: best not defined

top-level scope@Local: 1

xxxxxxxxxx
 
plot_sol(best)

---

We can see dynamically how it improves

xxxxxxxxxx

3.1 μs

Iteration:

xxxxxxxxxx

23.9 ms

UndefVarError: dists not defined

metrica(::Vector{Int64})@Other: 2
var"#BL#4"(::Int64, ::Nothing, ::typeof(Main.workspace75.BL), ::Vector{Int64})@Other: 3
top-level scope@Local: 2

xxxxxxxxxx
 
begin
    best_dyn, best_fit_dyn = BL(solucion, maxevals=slider)
    plot_sol(best_dyn)
end

---

showdf (generic function with 1 method)

xxxxxxxxxx

20.8 μs

plot_greedy (generic function with 1 method)

xxxxxxxxxx

85.6 μs

Greedy Algorithm

This algorithm tackle the previous problem. It is a variant of classic algorithm because we cannot create clusters due to the fact that we only know the distances between instances, so we cannot create intermediate positions.

xxxxxxxxxx

4.1 μs

Algorithm

Define $S e l = \emptyset$ , y $S$ ={todos los elementos}.
Calculate for each element i i its accumulated distance $d_{i} = \sum_{j \in S} D_{i j}$

xxxxxxxxxx

11.8 μs

accumulated_distance

UndefVarError: dists not defined

top-level scope@Local: 1

xxxxxxxxxx
 
accumulated_distance = rename!(sum(dists, dims=2) |> showdf, ["Distance"])

---

Set to $S e l$ the element $s o l_{1}$ which maximize $d_{i}$ , $S = {S - s o l_{i}}$ .

xxxxxxxxxx

6.3 μs

xxxxxxxxxx

44.0 μs

UndefVarError: dists not defined

top-level scope@Local: 4

xxxxxxxxxx
 
begin
    inicia_greedy
    local best
    best = argmax(sum(dists, dims=1))
    Sel = [best[2]]
    others = setdiff(1:n, Sel) |> collect
    first = true
    tam_others = n-1
    md"Sel: **$(showvalues(Sel))**"
end

---

for each element c from S, to calculate the minimum distance to each element of Set $\forall C \in S, d i s t (C, S e l) = m i n (D_{C s o l}), \forall s o l \in S e l$

xxxxxxxxxx

5.6 μs

UndefVarError: others not defined

top-level scope@Local: 1155

xxxxxxxxxx
 
@bind candidate_greedy Slider(1:size(others, 1))

---

UndefVarError: others not defined

top-level scope@Local: 1

xxxxxxxxxx
 
if candidate_greedy <= size(others, 1)
    plot_greedy(Sel, others[candidate_greedy])
else
    plot_greedy(Sel, others[end])
end

---

Choose the element c' with maximum dist(C, Sel).

xxxxxxxxxx

4.5 μs

select_best (generic function with 1 method)

xxxxxxxxxx

54.6 μs

Next step:

xxxxxxxxxx

25.4 ms

UndefVarError: Sel not defined

top-level scope@Local: 3

xxxxxxxxxx
 
begin
    if !doit
        best_next = select_best(Sel, others)
        md"Next better: **$(others[best_next])**"
    end
end

---

UndefVarError: Sel not defined

top-level scope@Local: 9

xxxxxxxxxx
 
begin
    local best
    
    if doit && size(Sel, 1) < m
        best = select_best(Sel, others)
        push!(Sel, others[best])
        deleteat!(others, best)
    end
    md"Sel: **$(showvalues(Sel))**, Others: **$(showvalues(others))**"
end

---