public abstract class AbstractMGAWeightRouting extends Object implements RunTimeLimit
Summary of the MGA:
MGACovWeightRouting
where the MGA estimates and generates the solutions based on the covariance of the variables.
To reduce the simulation time, we extends the basic algorithm of the MGA (described above)
to do a pre-scan the solutions with shorter simulations.
Then, the MGA will only simulate the most interesting solutions with normal simulation length.
This pre-scan procedure allows to avoid spending simulation time on bad solutions.
The parameter simRepRatio
controls the length of the short simulations,
and the parameter numNormalRatio
controls the number of solutions
(ratio relative to the elite population size P')
to simulate with normal simulation length.
As an extension to the standard MGA, the user can increase the weight of the best solution
of the current population by duplicating this best solution in the elite population.
Note that, the duplication adds more solutions to the elite population. If N is the
number of copies of the best solution, then the elite population will contain a total of
(P' + N - 1) solutions. The number of instances of the best solution is controlled with
the methods setBestSolPopRatio(double)
and getBestSolPopRatio()
.
Modifier and Type | Class and Description |
---|---|
static class |
AbstractMGAWeightRouting.Results
Contains the best solution vector and cost.
|
Modifier and Type | Field and Description |
---|---|
protected AbstractMGAWeightRouting.Results |
bestResults
The results of the last optimization run, or null if no optimization
was executed.
|
protected double |
bestSolPopRatio
Control the weight of the best elite solution (not necessarily the
best-to-date solution) in the elite population.
|
protected boolean[][] |
canServe
Matrix of size [numGroups][numTypes], where
the parameter
canServe[i][j] defines if
agent group i can serve call type j or not.
|
protected CallCenter |
cc
The call center model of the simulator.
|
protected boolean |
initUserParams
Use the user-defined parameters as the initial mean of the population.
|
protected double |
initUserParamsStdRatio
If
initUserParams is true, then the standard deviation
is set by this proportion of the mean parameter. |
protected int |
lastRunTimeSec
Saves the execution time in second of the last run.
|
protected int |
maxIt
The maximum number of iterations during the MGA.
|
protected int |
maxNoImprIt
The maximum number of iterations by MGA without any improvement.
|
protected boolean |
mgaSmoothing
If true, then the MGA performs a linear smoothing of the new
distribution parameters at the end of each iteration.
|
protected double |
mgaSmoothingRatio
The smoothing ratio to be used when
mgaSmoothing is set to true. |
double |
normalDistMinStd
Minimum standard deviation parameter when generating a normal random variable.
|
protected int |
numDimensions
Defines the number of variables to optimize.
|
protected int |
numGroups
The number of agent groups.
|
protected double |
numNormalRatio
This parameter controls the number of solutions to keep after the
pre-evaluation of the solutions simulated with fewer replications
(see the parameter
simRepRatio ). |
protected int |
numTypes
The number of call types.
|
protected RoutingObjectiveFunc |
objFunc
The objective function to minimize.
|
protected int |
popKeep
The elite population size in the MGA.
|
protected int |
popSize
The population size of the MGA at each iteration.
|
protected RandomStream |
rs
The random number generator to be used by the MGA.
|
protected CallCenterSim |
sim
The call center simulator.
|
protected double |
simRepRatio
This parameter is used to reduce the simulation length during the pre-evaluation
of the solutions in the population pool of the MGA.
|
protected ArrayList<Pair<Integer,Integer>> |
skillList
The complete list of skill by call type and agent group, where a skill
is defined by a Pair (call type, group).
|
protected int |
timeLimitSec
The optimization time limit in seconds.
|
protected double |
tol
The convergence tolerance stopping criteria.
|
protected int |
totalNumSkills
The total number of skills across all agent groups.
|
Constructor and Description |
---|
AbstractMGAWeightRouting(CallCenterSim sim,
RoutingObjectiveFunc objFunc)
Constructs the optimizer with the call center simulator and the objective function
to minimize.
|
Modifier and Type | Method and Description |
---|---|
protected abstract int |
computeNumDimensions()
Tell the optimizer the number of variables (or dimensions).
|
abstract double |
eval(double[] x)
Evaluate the solution and return the cost from the objective function.
|
abstract void |
exportSolution(String outputFn)
Create a parameter file that represents the model with the best routing solution found.
|
protected double[] |
generateSolution(double[] mean,
double[] std)
Generate a solution from a normal distribution with the given mean and
standard deviation.
|
AbstractMGAWeightRouting.Results |
getBestResults()
Get the best solution found.
|
double |
getBestScore()
Get the score of the best solution found.
|
double |
getBestSolPopRatio()
Get the duplication ratio of the best solution at the current iteration.
|
boolean |
getInitUserParams() |
double |
getInitUserParamsStdRatio() |
int |
getLastRunTimeSec()
Get the run time in seconds of the last execution.
|
boolean |
getMGASmoothing()
Get the MGA smoothing parameter.
|
double |
getMGASmoothingRatio()
The smoothing ratio to be used when
mgaSmoothing is set to true. |
double |
getNumNormalRatio()
Get the ratio (relative to the population to keep)
of number of solutions to simulate.
|
RandomStream |
getRandomStream()
Get the uniform random number generator that is used.
|
double |
getSimRepRatio()
Get the number of replications ratio between short and normal simulations.
|
List<Pair<Integer,Integer>> |
getSkillList()
Get the skill list of all agent groups.
|
int |
getTimeLimitSec()
Get the time limit in seconds.
|
int |
getTotalNumSkills()
Get the total number of skills across all agent groups.
|
protected abstract double[] |
initializeMean()
Method to initialize the mean vector.
|
protected abstract double[] |
initializeStd()
Method of initialize the standard deviation vector.
|
protected abstract boolean |
isSolutionValid(double[] x)
Check if the solution if valid.
|
void |
optimize(int popSize,
int popKeep,
int maxIt,
int maxNoImprIt,
double tol)
Execute the modified genetic algorithm optimization.
|
protected void |
printExtraInitialParameters()
Method can be overridden to print extra initial parameters.
|
protected void |
printOptimalSolution(double[] x)
Method can be overridden to print the optimal solution.
|
void |
setBestSolPopRatio(double r)
Give more weight to the best solution at the current iteration by duplicating this solution.
|
void |
setInitUserParams(boolean s)
Set to true to use the user-defined routing parameters as the
initial distribution means.
|
void |
setInitUserParamsStdRatio(double ratio)
Control the initial standard deviation parameters when this algorithm
takes the user-defined parameters as the initial distribution means.
|
void |
setMGASmoothing(boolean s)
Set the modified genetic algorithm update smoothing parameter.
|
void |
setMGASmoothingRatio(double r)
The smoothing ratio to be used when
mgaSmoothing is set to true. |
void |
setNumNormalRatio(double r)
Control the number of short simulation solutions to be simulated with normal
number of replications.
|
void |
setRandomStream(RandomStream s)
Set the uniform random number generator to be used.
|
void |
setSimRepRatio(double r)
Control the size of the short simulations.
|
void |
setTimeLimitSec(int sec)
Set the time limit in seconds.
|
protected boolean |
updateBestResults(double[] x,
double score)
Internal method to update the bestResults if the score is lower than the current
best results.
|
public double normalDistMinStd
protected boolean initUserParams
protected double initUserParamsStdRatio
initUserParams
is true, then the standard deviation
is set by this proportion of the mean parameter.
The computation of the standard deviation
will take the absolution value of the mean, so this parameter can only be positive.
The standard deviation will take the value of normalDistMinStd
, if
it is too small.protected CallCenterSim sim
protected CallCenter cc
protected RoutingObjectiveFunc objFunc
protected int numTypes
protected int numGroups
protected boolean[][] canServe
protected int numDimensions
protected int totalNumSkills
protected ArrayList<Pair<Integer,Integer>> skillList
protected AbstractMGAWeightRouting.Results bestResults
protected RandomStream rs
protected int popSize
protected int popKeep
popSize
.protected double bestSolPopRatio
The resulting elite population becomes also larger. A bigger value will make the algorithm converge faster to a local minimum.
protected int maxIt
protected int maxNoImprIt
protected double tol
protected double simRepRatio
numNormalRatio
.
During this pre-scan procedure, each of the popSize
solutions is simulated
the number of replications equal to this value times the minReplications
parameters of the simulator.
<p>
After performing the pre-evaluation, the MGA keeps the popKeep
times
numNormalRatio
lowest cost solutions, and it simulates these
solutions with the normal number of replications minReplications
specified in the simulator parameters.protected double numNormalRatio
simRepRatio
).
The number of most promising solutions that are simulated with
normal replication length is equal to this value times popKeep
.protected boolean mgaSmoothing
mgaSmoothingRatio
.protected double mgaSmoothingRatio
mgaSmoothing
is set to true.
This value must be between 0 and 1. The mean and standard deviation of the new
elite population will have a weight of mgaSmoothingRatio
and the current (old)
mean and standard deviation will have a weight of 1 minus this value.protected int lastRunTimeSec
protected int timeLimitSec
public AbstractMGAWeightRouting(CallCenterSim sim, RoutingObjectiveFunc objFunc)
sim
- the call center simulator.objFunc
- the objective function to minimize.public void setInitUserParams(boolean s)
setInitUserParamsStdRatio(double)
.s
- public boolean getInitUserParams()
public void setInitUserParamsStdRatio(double ratio)
ratio
- public double getInitUserParamsStdRatio()
public int getTotalNumSkills()
public List<Pair<Integer,Integer>> getSkillList()
protected abstract int computeNumDimensions()
public void setRandomStream(RandomStream s)
s
- the uniform random number generator to be used.public RandomStream getRandomStream()
public void setSimRepRatio(double r)
r
- the number of replications ratio between short and normal simulations.public double getSimRepRatio()
public void setNumNormalRatio(double r)
r
- the ratio (relative to the population to keep)
of number of solutions to simulate.public double getNumNormalRatio()
public void setBestSolPopRatio(double r)
r
- the ratio of the current best solution in the elite population.public double getBestSolPopRatio()
public void setMGASmoothing(boolean s)
setMGASmoothingRatio(double)
.s
- set to use update smoothing.public boolean getMGASmoothing()
public void setMGASmoothingRatio(double r)
mgaSmoothing
is set to true.
This value must be between 0 and 1. See setMGASmoothing(boolean)
.public double getMGASmoothingRatio()
mgaSmoothing
is set to true.
This value must be between 0 and 1. See setMGASmoothing(boolean)
.public void setTimeLimitSec(int sec)
RunTimeLimit
setTimeLimitSec
in interface RunTimeLimit
sec
- the time limit in seconds.public int getTimeLimitSec()
RunTimeLimit
getTimeLimitSec
in interface RunTimeLimit
public int getLastRunTimeSec()
RunTimeLimit
getLastRunTimeSec
in interface RunTimeLimit
public void optimize(int popSize, int popKeep, int maxIt, int maxNoImprIt, double tol)
popSize
- the population size at each iteration.popKeep
- the number of solutions to keep in each iteration.maxIt
- the maximum number of iterations.maxNoImprIt
- stopping condition: the maximum number of consecutive iterations without improving
the quantile cost (cost of the most expensive elite solution).tol
- the convergence threshold of the standard variation, the
algorithm stops when all the standard variations are below this level.protected void printExtraInitialParameters()
int, int, int, double)
will print the initial parameters
of the optimization function and those present in this abstract class.
But the user can print additional informations with this method.
This method is called before executing the optimization, right after
printing the initial parameters of this abstract class.protected abstract double[] initializeMean()
computeNumDimensions()
.protected abstract double[] initializeStd()
computeNumDimensions()
.protected void printOptimalSolution(double[] x)
x
- the solution vector to printprotected double[] generateSolution(double[] mean, double[] std)
mean
- the mean of each variable.std
- the standard deviation of each variable.protected abstract boolean isSolutionValid(double[] x)
x
- the solution to checkpublic abstract double eval(double[] x)
x
- the solutionprotected boolean updateBestResults(double[] x, double score)
x
- the new solution.score
- the corresponding score value.public AbstractMGAWeightRouting.Results getBestResults()
public double getBestScore()
public abstract void exportSolution(String outputFn)
outputFn
- filename to create.