R/method_search.R
method_search.RdThese functions search the space of memberships for the one that minimises some cost, such as the misfit of a blockmodel:
search_iterated() makes one random move at a time, keeps it where it
lowers the cost, and restarts from a perturbation of the best membership
every tenth step.
search_tabu() examines every move of one node to another group at
each step, takes the best of them, and forbids the reverse move for a
while, so that it can climb out of a local minimum.
These functions are not intended to be called directly,
but are called within node_in_block(), node_in_faction(), and
related functions.
They are exported and listed here to provide more detailed documentation.
search_iterated(cost, init, times, delta = NULL)
search_tabu(cost, init, times, delta = NULL)A function that takes a membership vector and returns a single number, the cost to be minimised.
An integer vector giving each node's group, the membership from which the search begins. The search keeps the number of groups that it holds.
Integer scalar, how many times the algorithm repeats its work. Where the algorithm is stochastic, this is how many times it runs, and the best or the most frequent result is kept. Where the algorithm searches, this is how many steps the search takes. More repetitions give a more reliable result and take longer, so each function documents its own default.
Optionally, a function that takes the current and a candidate
membership vector, and returns the change in cost from the one to the
other. Where the change can be found from the nodes that moved alone,
this is much faster than calculating the cost of every candidate afresh.
By default NULL, in which case cost is called on each candidate.
An integer vector the length of init,
giving each node's group in the best membership found,
with that membership's cost as the attribute "cost".
An iterated local search. Each step makes a weak perturbation, which
swaps two nodes between groups or moves one node out of a largest group,
and keeps it only where it lowers the cost.
Every tenth step, the search starts again from a stronger perturbation
of the best membership so far, a number of successive weak perturbations
of approximately the number of nodes divided by the number of groups.
times is the number of steps.
The moves keep the groups at near-equal size: groups that begin equal
stay equal, and groups that begin unequal move towards equal sizes.
That is what node_in_roulette() needs, but it means this
search cannot find, say, a small core beside a large periphery.
Since the moves are drawn at random, repeated runs may return different
memberships; set a seed to repeat one.
A tabu search. Each step examines every move of one node into another group, and takes the move that lowers the cost most: the steepest descent. Where no move lowers the cost, it takes the move that raises it least, the mildest ascent, and so leaves a local minimum instead of stopping in it. To keep the next step from simply undoing that move, the node may not return to the group it left for the next 15 steps, unless doing so would beat the best membership found so far.
A run ends after 20 steps in a row that do not improve on its best
membership, or after times steps, whichever comes first.
The search makes 10 runs, the first from init and the others from
random memberships with the same number of groups, and returns the best
membership of them all.
These three settings are those that the UCINET 'Factions' routine uses by
default, and are fixed here.
No move may empty a group, but otherwise the groups are free to take any size. A run is deterministic given where it starts, but nine of the ten starts are random, so set a seed to repeat a result. Note that the search may still end in a local minimum, and that it returns one membership even where several share the lowest cost.
Glover, Fred. 1989. "Tabu Search — Part I." ORSA Journal on Computing 1(3): 190-206. doi:10.1287/ijoc.1.3.190
Glover, Fred. 1990. "Tabu Search — Part II." ORSA Journal on Computing 2(1): 4-32. doi:10.1287/ijoc.2.1.4
mat <- manynet::as_matrix(ison_adolescents)
cost <- function(memb) sum(mat[outer(memb, memb, "!=")])
search_iterated(cost, init = rep(1:2, 4), times = 50)
#> [1] 2 1 1 1 1 2 2 2
#> attr(,"cost")
#> [1] 6
search_tabu(cost, init = rep(1:2, 4), times = 50)
#> [1] 1 1 1 1 1 1 1 2
#> attr(,"cost")
#> [1] 2