Quintiq file version 2.0
|
#parent: #root
|
StaticMethod IndependentPathStrategy (POAAlgorithm poa) as POAAlgorithm
|
{
|
TextBody:
|
[*
|
LibOpt_SuboptimizerPOA::StrategyStart( poa );
|
// -------------------------------------------------------------------------- //
|
// Strategy for independent path problems, for example vehicle routing //
|
// problems //
|
// -------------------------------------------------------------------------- //
|
|
strategy := poa.Strategy();
|
|
// ----- Parameters for the strategy -----
|
// String used to identify the expression used for time in this POA. This
|
// strategy needs an expression for time.
|
timeexpressionname := LibOpt_SuboptimizerPOA::GetStrategySetting_TimeExpressionName( poa, 'time' );
|
// The total duration of iteratively improving the solution in this strategy.
|
// This does not include the time spend on creating and improving an initial
|
// solution. More time spend on iterive improvement will give a higher chance
|
// on better results.
|
iterativeduration := LibOpt_SuboptimizerPOA::GetStrategySetting_IterativeDuration( poa, Duration::Seconds( 60 ) );
|
// The number of threads used throughout the strategy execution. The threads
|
// are all busy from begin till end.
|
nrthreads := LibOpt_SuboptimizerPOA::GetStrategySetting_NrThreads( poa, 3 );
|
|
// ----- Advanced Parameters for the strategy -----
|
// The number of moves (plan possibilities of planelements) that make it in the
|
// final population. Moves that are estimated to be better have a higher chance
|
// to be in the population. All moves in the population are fully propagated,
|
// after which the best move is carried out. A higher number will mean more
|
// precise results because full propagation gives the precise score of a move.
|
// This comes at the cost of more time needed in propagation.
|
maxpopulation := LibOpt_SuboptimizerPOA::GetStrategySetting_MaxPopulation( poa, 3 );
|
// The percentage of available planelements that is destructed by the random
|
// destruction action
|
randomdestructionpercentage := LibOpt_SuboptimizerPOA::GetStrategySetting_RandomDestructionPercentage( poa, 5.0 );
|
// The percentage of paths that is destructed by the path destruction action
|
pathdestructionpercentage := LibOpt_SuboptimizerPOA::GetStrategySetting_PathDestructionPercentage( poa, 0.0 );
|
// The chance during one iteration that the path destuction action is executed.
|
// Where as a minimum 1 path is destructed.
|
pathdestructionchance := LibOpt_SuboptimizerPOA::GetStrategySetting_PathDestructionChance( poa, 0.0 );
|
// The percentage of available planelements that is destructed by the area stop
|
// destruction action
|
areastopdestructionpercentage := LibOpt_SuboptimizerPOA::GetStrategySetting_AreaStopDestructionPercentage( poa, 17.0 );
|
// The chance during one iteration that the area stop destruction action is
|
// executed
|
areastopdestructionchance := LibOpt_SuboptimizerPOA::GetStrategySetting_AreaStopDestructionChance( poa, 0.5 );
|
// The number of unplanned elements that is considered by the random
|
// construction action
|
randomconstructiongroupsize := LibOpt_SuboptimizerPOA::GetStrategySetting_RandomConstructionGroupSize( poa, 7 );
|
// The duration between the possibility of a reset to the globally best solution
|
// found.
|
durationbetweenrestarttoglobal := LibOpt_SuboptimizerPOA::GetStrategySetting_DurationBetweenRestartToGlobal( poa, Duration::Seconds( 3.5 ) );
|
// The chance that a solution is restarted to the globally best solution
|
restarttoglobalchance := LibOpt_SuboptimizerPOA::GetStrategySetting_RestartToGlobalChance( poa, 0.6 );
|
|
// The duration between logging information during the iterative strategy
|
durationbetweeniterativereports := LibOpt_SuboptimizerPOA::GetStrategySetting_DurationBetweenIterativeReports( poa, Duration::Seconds( 5 ) );
|
// Log file name prefix. '' means no logging
|
logfilename := LibOpt_SuboptimizerPOA::GetStrategySetting_LogFileName( poa, '' );
|
// Toggle info statements
|
printinfo := LibOpt_SuboptimizerPOA::GetStrategySetting_PrintInfo( poa, true );
|
|
// -------------------------------------------------------------------------- //
|
// Print parameter values and initial score //
|
// -------------------------------------------------------------------------- //
|
|
if( printinfo )
|
{
|
info( 'parameter timeexpressionname =' , timeexpressionname );
|
info( 'parameter iterativeduration =' , iterativeduration );
|
info( 'parameter nrthreads =' , nrthreads );
|
info( 'parameter maxpopulation =' , maxpopulation );
|
info( 'parameter randomdestructionpercentage =' , randomdestructionpercentage );
|
info( 'parameter pathdestructionpercentage =' , pathdestructionpercentage );
|
info( 'parameter pathdestructionchance =' , pathdestructionchance );
|
info( 'parameter areastopdestructionpercentage =' , areastopdestructionpercentage );
|
info( 'parameter areastopdestructionchance =' , areastopdestructionchance );
|
info( 'parameter randomconstructiongroupsize =' , randomconstructiongroupsize );
|
info( 'parameter durationbetweenrestarttoglobal =' , durationbetweenrestarttoglobal );
|
info( 'parameter restarttoglobalchance =' , restarttoglobalchance );
|
info( 'parameter logfilename =' , logfilename );
|
info( 'initial score', strategy.BestSolution().TotalScore() );
|
}
|
|
// -------------------------------------------------------------------------- //
|
// Initialize general settings //
|
// -------------------------------------------------------------------------- //
|
|
// For all constraints change MaxDownStreamDepth to MaxNumber where applicable.
|
// For independent path problems MaxNumber gives generally the best results.
|
{
|
traverse( poa, Constraints.astype( POAEndConstraint ), c, c.MaxDownStreamDepth() <> Number::MaxNumber() )
|
{
|
c.MaxDownStreamDepth( Number::MaxNumber() );
|
debuginfo( 'Warning: POAEndConstraint', c.Role(), 'MaxDownStreamDepth was changed to MaxNumber, because that will improve the move estimates' );
|
}
|
|
traverse( poa, Constraints.astype( POACapacityConstraint ), c, c.MaxDownStreamDepth() <> Number::MaxNumber() )
|
{
|
c.MaxDownStreamDepth( Number::MaxNumber() );
|
debuginfo( 'Warning: POACapacityConstraint', c.Role(), 'MaxDownStreamDepth was changed to MaxNumber, because that will improve the move estimates' );
|
}
|
|
traverse( poa, Constraints.astype( POAInTimeConstraint ), c, c.MaxDownStreamDepth() <> Number::MaxNumber() )
|
{
|
c.MaxDownStreamDepth( Number::MaxNumber() );
|
debuginfo( 'Warning: POAInTimeConstraint', c.Role(), 'MaxDownStreamDepth was changed to MaxNumber, because that will improve the move estimates' );
|
}
|
}
|
|
timeexpression := select( poa, Expressions, e, true, e.Role() = timeexpressionname );
|
verify( not isnull( timeexpression ),
|
"The strategy needs an expression that is called 'time' and will be used as the expression representing time
|
" );
|
|
planstrategy := strategy.PlanStrategy();
|
// Apply parameter
|
planstrategy.MaxPopulation( maxpopulation );
|
// the population of moves per path is infinite
|
planstrategy.MaxPathPopulation( maxpopulation );
|
|
// -------------------------------------------------------------------------- //
|
// Initial Strategy //
|
// -------------------------------------------------------------------------- //
|
//
|
// The initial strategy will be used to plan all remaining planelements, and do
|
// some initial improvement. After that improvement will only be made by
|
// iterativestrategy.
|
|
initialstrategy := strategy.NewMetaStrategy( 'initialstrategy' );
|
if( logfilename <> '' )
|
{
|
initialstrategy.LogFileName( logfilename + '_InitialStrategy', true );
|
}
|
|
// The only step used in the initial strategy.
|
initialstep := initialstrategy.NewStep( 'initialstep' );
|
// Room for one start solution.
|
initialstep.StartSolutionPool().Capacity( 1 );
|
// Use initial solution as the single starting solution.
|
initialstep.StartSolutionPool().Add( poa.Solution() );
|
// The step is repeated a number of times equal to the number of threads, each
|
// time starting from the same initial solution. Each repetition is carried out
|
// by its own thread.
|
initialstep.Repetitions( nrthreads );
|
// The step happens once in each thread. It will not be carried out on the
|
// results of a previous iteration.
|
initialstep.MaximumIterationsActions( 1 );
|
// 1 000 000 seconds pratically infinity
|
initialstep.MaximumSecondsActions( 1000000.0 );
|
// The result of each thread is stored.
|
initialstep.ResultSolutionPool().Capacity( nrthreads );
|
|
actions := initialstep.Actions();
|
|
// Use insertion heuristic, which choses a path, and plans one element a time on
|
// that path based on the time expression. When no more elements fit on the path
|
// a new path is chosen. This continues until there are not paths left,
|
insertionheuristic := actions.NewInsertionHeuristic( timeexpression );
|
// Try to plan all unplanned planelements.
|
insertionheuristic.Nodes( Number::MaxNumber() );
|
|
// Use one node improvement action, which selects any planned or unplanned
|
// element and tries to find a better position for that element. Depending
|
// on the improvement made, a new element is selected and the process
|
// repeats itself.
|
onenodeimpr := actions.NewRandomOneNodeImprovement();
|
// By setting to 0.0 any improvement will make the process repeat itself.
|
onenodeimpr.MinimalImprovementPercentage().Set( 0.0 );
|
|
// Start execution of the strategy and display the duration
|
executestarttime := DateTime::ActualTime();
|
debuginfo( 'execute initial actions' );
|
initialstrategy.Execute( nrthreads, Real::MaxReal() );
|
debuginfo( 'initial actions execution duration', DateTime::ActualTime() - executestarttime );
|
|
// -------------------------------------------------------------------------- //
|
// Iterative Strategy //
|
// -------------------------------------------------------------------------- //
|
//
|
// iterativestrategy will repeatedly run on the start solution generated by
|
// initialstrategy.
|
|
iterativestrategy := strategy.NewMetaStrategy( 'iterativestrategy' );
|
if( logfilename <> '' )
|
{
|
iterativestrategy.LogFileName( logfilename + '_IterativeStrategy', true );
|
}
|
|
// The only step used in the iterative strategy.
|
iterativestep := iterativestrategy.NewStep( 'iterativestep' );
|
// Use the result of each thread for the initial stategy as starting point for
|
// the iterative strategy. One thread will start for each of these starting
|
// points.
|
iterativestep.StartSolutionPool().Use( initialstep.ResultSolutionPool() );
|
// There is no limit on the number of times this step starts again within a
|
// single thread.
|
iterativestep.MaximumIterationsActions( Number::MaxNumber() );
|
// Execution of the step must not take longer then the reporting duration.
|
iterativestep.MaximumSecondsActions( durationbetweenrestarttoglobal.MinutesAsReal() * 60.0 );
|
// The result of each thread is stored.
|
iterativestep.ResultSolutionPool().Capacity( nrthreads );
|
|
actions := iterativestep.Actions();
|
|
// The number of elements available for planning.
|
nrplanelements := poa.PlanElements( relsize );
|
|
randomstopdestr := actions.NewRandomStopDestruction();
|
randomstopdestr.SegmentsMinimum( round( randomdestructionpercentage / 100.0 * nrplanelements ) );
|
randomstopdestr.SegmentsMaximum( round( randomdestructionpercentage / 100.0 * nrplanelements ) );
|
randomstopdestr.SegmentLengthMaximum( 1 );
|
randomstopdestr.SegmentLengthMinimum( 1 );
|
|
// The number of paths available for planning.
|
nrpaths := sum( poa, PathTypes, t, true, t.MaxCount() );
|
|
// Use path destruction, which randomly chooses a number of paths to be
|
// destructed.
|
pathdestr1 := actions.NewRandomPathDestruction();
|
// The number of chosen paths is pathdestructionpercentage% of the available
|
// paths. Rounded, so possibly zero.
|
pathdestr1.Paths( maxvalue( 1, round( pathdestructionpercentage / 100.0 * nrpaths ) ) );
|
pathdestr1.ExecutionChance().Set( pathdestructionchance );
|
|
// Use area stop destruction, which choses one stop to be destructed and
|
// destructs the area surrounding that node. The length of the time expression
|
// transition between stops determines if two stops belong to the same area.
|
areastopdestr := actions.NewRandomAreaStopDestruction( timeexpression );
|
// By specifing the number of stops
|
areastopdestr.Stops( round( areastopdestructionpercentage / 100.0 * nrplanelements ) );
|
areastopdestr.ExecutionChance().Set( areastopdestructionchance );
|
|
// Use random construction, which
|
// (1) chooses a number of unplanned elements equal to
|
// 'randomconstructiongroupsize'.
|
// (2) determines the best move for each element by making estimates for all
|
// moves and propagating the moves that make it in the population.
|
// (3) carry out the best move of the element that was best
|
randomcons := actions.NewRandomConstruction();
|
// Set the number of unplanned elements to consider.
|
randomcons.GroupSize( randomconstructiongroupsize );
|
|
onenodeimpr := actions.NewRandomOneNodeImprovement();
|
// By setting to 0.0 any improvement will make the process repeat itself.
|
onenodeimpr.MinimalImprovementPercentage().Set( 0.0 );
|
|
// Keep executing the iterative meta strategy until the time limit is reached
|
iterativeendtime := DateTime::ActualTime() + iterativeduration;
|
lastreporttime := DateTime::ActualTime() - durationbetweeniterativereports;
|
while( DateTime::ActualTime() < iterativeendtime )
|
{
|
executeduration := minvalue( durationbetweenrestarttoglobal, iterativeendtime - DateTime::ActualTime() );
|
|
// Call meta strategy execution
|
iterativestrategy.Execute( nrthreads, executeduration.MinutesAsReal() * 60.0 );
|
|
// Fill start solution
|
traverse( iterativestep.ResultSolutionPool().UseSolutions(), Solutions, s )
|
{
|
if( Real::Random() < restarttoglobalchance )
|
{
|
iterativestep.StartSolutionPool().Add( strategy.BestSolution() );
|
}
|
else
|
{
|
iterativestep.StartSolutionPool().Add( s );
|
}
|
}
|
|
if( printinfo and DateTime::ActualTime() - lastreporttime >= durationbetweeniterativereports )
|
{
|
lastreporttime := DateTime::ActualTime();
|
|
info( 'iterative time remaining', iterativeendtime - DateTime::ActualTime() );
|
|
i := 0;
|
traverse( iterativestep.StartSolutionPool(), Solutions, s )
|
{
|
info( i, ': iterative result solution score', s.TotalScore() );
|
i++;
|
}
|
|
info( 'iterations', actions.Iterations().Value() );
|
info( 'improvement iterations', actions.IterationsImproved().Value() );
|
|
// After logging reset statistics for the next iteration
|
actions.ResetStatistics();
|
}
|
}
|
LibOpt_SuboptimizerPOA::StrategyFinish( poa );
|
return poa;
|
*]
|
}
|
