Xtykutl

I am trying to come up with an algorithm in R to generate n sequences from a vector X of n amount of (all positive integer) input paramters while minimising the overlaps within an interval I of all sequence elements. There is an upperlimit ub for all x ⋹ X as well as the sequences generated.

Example:

ub = 100

n = 2

# initialise X with random values 

X = sample(1:ub, n, replace=F)

# [1] 20 30

# generate sequences

S = sapply(X, function(x) cumsum(rep(x,floor(ub/x))))

# [[1]]

# [1] 20 40 60 80 100



# [[2]]

# [1] 30 60 90

I currently implemented a function eval.f, which generates S from X and then iterates through all sequences s in S to check how many elements of s are within an interval I of all other elements of the other sequences in S:

ub = 100

n = 2

X = sample(1:ub, n, replace=F)   

I=10

eval.f<-function(X,

                 I,

                 ub){

S = sapply(X, function(x) cumsum(rep(x,floor(ub/x))))

return(sum(unlist(sapply(1:length(S), function(y){

    sapply(1:y, function(z){

      if(y!=z){

        sapply(S[[y]],function(w) abs(w-S[[z]]))

      }

    })

  }))<I))

}

For I = 10, the total number of overlaps would for above example be 5. However, I want to scale this to bigger values of n. Currently I implemented a simple loop with 10.000 iterations and randomly sample new values for X, every iteration counting the number of overlaps of the resulting sequences, retaining X with the lowest amount of overlaps:

# initialize

iterations<-10000

solutions<-X

overlaps<-eval.f(X,I,ub)

i<-1



while(i<iterations){

  new_X<-sample(1:ub, n, replace=F)

  new_overlaps<-eval.f(new_X,

                       I,

                       ub)

  if (new_overlaps<overlaps){

    overlaps<-new_overlaps

    solutions<-new_X

  }

  if(overlaps==0) break

  i<-i+1

}

Now my question: since I want to minimise the total amount of overlaps of all sequences s in S within I, my guess is that this could be achieved using non-linear programming, however I am unsure of the formulation and implementation in R. Would greatly appreciate any input!