2
$\begingroup$

I have a function that I am trying to optimize using Particle Swarm Optimization.

The objective function gets a binary string. These binary strings are candidate solutions of the subject function. I can measure the dissimilarity between two solutions by the Jaccard Coefficient, but I need to move one solution towards another by a factor, meaning I need a vector.

Are there any methods to do that?

Example:

a = 0011001 
b = 0011010

I want to move a towards b by the factor of 0.4. So I need to find another string that is similarity between a is 0.6 and similarity between b is 0.4.

Actually strings are much longer. I am trying to somehow represent binary data n-dimensional space and then represent a vector from one point to another.

I hope I have explained myself clearly.

$\endgroup$

1 Answer 1

3
$\begingroup$

If your strings are sufficiently long, you can compute the weighted average of $a$ and $b$, $c = (1-\lambda) a + \lambda b$, interpret each value as a probability, and sample according to those probabilities.

The result is only approximate, i.e., $ d(a,c) \approx \lambda d(a,b) $ and $ d(b,c) \approx (1-\lambda) d(a,b) $, but that should be sufficient for your purposes.

n <- 1e4
a <- sample(c(TRUE,FALSE), n, replace=TRUE)
b <- sample(c(TRUE,FALSE), n, replace=TRUE)
lambda <- .1
jaccard <- function(a,b) sum( a & b ) / ( length(a) - sum( !a & !b ) )
distance <- function(a,b) 1 - jaccard(a,b)
distance(a,b)
x <- (1 - lambda) * a + lambda * b
x <- runif(n) < x
distance(a,x) / distance(a,b)  # Around lambda
distance(b,x) / distance(a,b)  # Around 1 - lambda

Another approach, to optimize discrete functions, would be to use simulated annealing (you need to define a notion of "neighbouring string", e.g., one that only differs by one bit) or genetic algorithms (you need to define a notion of "crossover").

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.