Quintiq file version 2.0
|
#parent: #root
|
StaticMethod DependentPathStrategy (POAAlgorithm poa) as POAAlgorithm
|
{
|
TextBody:
|
[*
|
LibOpt_SuboptimizerPOA::StrategyStart( poa );
|
// -------------------------------------------------------------------------- //
|
// Strategy for dependent path problems, for example scheduling problems //
|
// -------------------------------------------------------------------------- //
|
|
strategy := poa.Strategy();
|
|
// ----- Parameters for the strategy -----
|
// 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, 140 );
|
// The percentage of available planelements that is destructed by the random
|
// destruction action
|
randomdestructionpercentage := LibOpt_SuboptimizerPOA::GetStrategySetting_RandomDestructionPercentage( poa, 30.0 );
|
// The duration between the possibility of a reset to the globally best solution
|
// found.
|
randomconstructiongroupsize := LibOpt_SuboptimizerPOA::GetStrategySetting_RandomConstructionGroupSize( poa, 1 );
|
// The duration between the possibility of a reset to the globally best solution
|
// found.
|
durationbetweenrestarttoglobal := LibOpt_SuboptimizerPOA::GetStrategySetting_DurationBetweenRestartToGlobal( poa, Duration::Seconds( 4.0 ) );
|
// The chance that a solution is restarted to the globally best solution
|
restarttoglobalchance := LibOpt_SuboptimizerPOA::GetStrategySetting_RestartToGlobalChance( poa, 0.9 );
|
|
// 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 iterativeduration =' , iterativeduration );
|
info( 'parameter nrthreads =' , nrthreads );
|
info( 'parameter maxpopulation =' , maxpopulation );
|
info( 'parameter randomdestructionpercentage =' , randomdestructionpercentage );
|
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' );
|
}
|
}
|
|
planstrategy := strategy.PlanStrategy();
|
// Apply parameter
|
planstrategy.MaxPopulation( maxpopulation );
|
// the population of moves per path is infinite
|
planstrategy.MaxPathPopulation( maxpopulation );
|
|
// -------------------------------------------------------------------------- //
|
// 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' );
|
// Room for one start solution.
|
iterativestep.StartSolutionPool().Capacity( 1 );
|
// Use initial solution as the single starting solution.
|
iterativestep.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.
|
iterativestep.Repetitions( nrthreads );
|
// 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 );
|
|
// Use random destruction, which choses randomly a number of planned elements
|
// to be destructed.
|
randomdestr := actions.NewRandomDestruction();
|
// The number of chosen elements is the percentage randomdestructionpercentage
|
// of the available elements. Typically before random destruction all elements
|
// will be planned.
|
randomdestr.Nodes( round( randomdestructionpercentage / 100.0 * nrplanelements ) );
|
|
// Use random construction, which
|
// (1) chooses a number of unplanned elements.
|
// (2) determines the best move for each element by making estimates for that
|
// move and propagating the moves that make it in the population.
|
// (3) carry out the 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 );
|
|
// Room for one start solution.
|
iterativestep.StartSolutionPool().Capacity( nrthreads );
|
|
// 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;
|
*]
|
}
|
