auxGAPga | R Documentation |
A genetic algorithm with local heuristics for GAP.
auxGAPga(
cost,
profitOrLoss,
budget,
trials,
populationSize,
generations,
randomSeed = NULL,
maxCore = 7,
optim = "max"
)
cost |
A numeric matrix. Dimensionality = N(agents) |
profitOrLoss |
A numeric matrix of the same dimensionality of |
budget |
A numeric vector. Size = N(agents). |
trials |
An integer. Number of trials, aka the number of population sets. |
populationSize |
An integer. Size of each population. |
generations |
An integer. As reproduction iterates, if there have been |
randomSeed |
An integer or |
maxCore |
Maximal threads to invoke. No greater than the number of logical CPUs on machine. The algorithm multithreads over trials. |
optim |
A string. |
This algorithm is based on a foundational paper by Chu and Beasley (1997) and is carefully engineered towards speed. Besides the standard cross-over and mutation operations, the algorithm applies two local heuristics for educating the new borns. The first is to randomly pick a task from each overloaded agent and reassign the task to the next budget-sufficient agent — if there is any. The second is to raise the total profit by reassigning another agent for each task — if the reassignment would not result in overload. The algorithm outperforms most peer metaheuristics such as variants of simulated annealing and tabu search (Osman), and is highly effective for large and hard instances.
A list of 4:
totalProfitOrLoss |
Total profit or loss generated from the assignment. Negative infinity if no solution found. |
agentCost |
A numeric vector of total costs for each agent. Empty if no solution found. |
assignment |
An integer vector. |
populationInfo |
A list of 3: |
allGenes |
An N(task) |
allBudgetExceedance |
A numeric vector of the size of |
allProfitOrLoss |
A numeric vector of the size of |
The C++ implementation is fully independent and borrows no code from any commercial or open source.
# =============================================================================
# A trivial instance
# =============================================================================
profit = c(17,21,22,18,24,15,20,18,19,18,16,22,24,24,16,23,16,21,16,17,16,19,
25,18,21,17,15,25,17,24,16,20,16,25,24,16,17,19,19,18,20,16,17,21,
24,19,19,22,22,20,16,19,17,21,19,25,23,25,25,25,18,19,15,15,21,25,
16,16,23,15,22,17,19,22,24)
profit = t(matrix(profit, ncol = 5))
cost = c(8,15,14,23,8,16,8,25,9,17,25,15,10,8,24,15,7,23,22,11,11,12,10,17,16,
7,16,10,18,22,21,20,6,22,24,10,24,9,21,14,11,14,11,19,16,20,11,8,14,
9,5,6,19,19,7,6,6,13,9,18,8,13,13,13,10,20,25,16,16,17,10,10,5,12,23)
cost = t(matrix(cost, ncol = 5))
budget = c(36, 34, 38, 27, 33)
Nagent = 5L; Ntask = 15L
rst = FLSSS::auxGAPga(
cost, profit, budget, trials = 2, populationSize = 100, generations = 10000,
randomSeed = 42, maxCore = 2, optim = "max")
# =============================================================================
# A relatively hard instance.
# =============================================================================
# Download gapInstances.Rdata from
# https://github.com/WhateverLiu/gapInstances. Load it in R.
if (FALSE)
{
cost = gapC[[3]]$cost
loss = gapC[[3]]$loss
budget = gapC[[3]]$budget
# Intel CPU i7-4770 3.4GHz, g++ '-Ofast', 64-bit Windows 7.
system.time({rst = FLSSS::auxGAPga(
cost, loss, budget, trials = 7, randomSeed = 42, populationSize = 100,
generations = 500000, optim = "min", maxCore = 7)})
rst$totalProfitOrLoss # 1416
# user system elapsed
# 69.24 0.17 11.61
# The known optimum equals 1402 as the total loss.
}
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.