@ Override protected void searchStep ( ) { // submit replicas for execution in thread pool // (future returns index of respective replica) for ( int i = 0 ; i < replicas . size ( ) ; i ++ ) { futures . add ( pool . submit ( replicas . get ( i ) , i ) ) ; } // logger.debug("{}: started {} Metropolis replicas", this, futures.size()); // wait for completion of all replicas and remove corresponding future while ( ! futures . isEmpty ( ) ) { // remove next future from queue and wait until it has completed try { int i = futures . poll ( ) . get ( ) ; // logger.debug("{}: {}/{} replicas finished", this, replicas.size()-futures.size(), replicas.size()); // update total number of accepted/rejected moves incNumAcceptedMoves ( replicas . get ( i ) . getNumAcceptedMoves ( ) ) ; incNumRejectedMoves ( replicas . get ( i ) . getNumRejectedMoves ( ) ) ; } catch ( InterruptedException | ExecutionException ex ) { throw new SearchException ( "An error occured during concurrent execution of Metropolis replicas " + "in the parallel tempering algorithm." , ex ) ; } } // consider swapping solutions of adjacent replicas for ( int i = swapBase ; i < replicas . size ( ) - 1 ; i += 2 ) { MetropolisSearch < SolutionType > r1 = replicas . get ( i ) ; MetropolisSearch < SolutionType > r2 = replicas . get ( i + 1 ) ; // compute delta double delta = computeDelta ( r2 . getCurrentSolutionEvaluation ( ) , r1 . getCurrentSolutionEvaluation ( ) ) ; // check if solutions should be swapped boolean swap = false ; if ( delta >= 0 ) { // always swap swap = true ; } else { // compute factor based on difference in temperature double b1 = 1.0 / ( r1 . getTemperature ( ) ) ; double b2 = 1.0 / ( r2 . getTemperature ( ) ) ; double diffb = b1 - b2 ; // randomized swap (with probability p) double p = Math . exp ( diffb * delta ) ; // generate random number double r = getRandom ( ) . nextDouble ( ) ; // swap with probability p if ( r < p ) { swap = true ; } } // swap solutions if ( swap ) { SolutionType r1Sol = r1 . getCurrentSolution ( ) ; Evaluation r1Eval = r1 . getCurrentSolutionEvaluation ( ) ; Validation r1Val = r1 . getCurrentSolutionValidation ( ) ; r1 . setCurrentSolution ( r2 . getCurrentSolution ( ) , r2 . getCurrentSolutionEvaluation ( ) , r2 . getCurrentSolutionValidation ( ) ) ; r2 . setCurrentSolution ( r1Sol , r1Eval , r1Val ) ; } } // flip swap base swapBase = 1 - swapBase ; }
In each search step every replica performs several steps after which solutions of adjacent replicas may be swapped .