## 4 The ARPO Metaheuristic
Third, the destroyed solution is re-constructed (completed) by adding new assets to the portfolio (lines 10-19). During this re-construction process, the selection of each new asset added to the portfolio is done following a 'friendship' criterion, i.e. : although the selection of the new asset is random, this new asset will be most likely selected among those assets that are highly compatible--i.e., showing a low covariance value--with the last asset added to the portfolio. This special behavior is attained throughout the use of a biased randomization selection process (line 14), which makes use of a geometric distribution of parameter beta (\(0<\mathit{beta}<1\)). More details on biased randomization processes can be found in [66; 67]. ```
1:procedureARPO(inputs, minReturn, maxTime, beta)
2:initSol \(\leftarrow\) genInitSol(inputs) \(\triangleright\) generate sol with highest possible return rate
3:if{getReturn(initSol) \(<\) minReturn} then\(\triangleright\) unfeasible problem
4:return unfeasible
5:endif
6:genFriendshipLists(inputs) \(\triangleright\) generate a sorted list of \"friends\" for each asset
7:baseSol \(\leftarrow\) QPOptimize(initSol, minReturn) \(\triangleright\) optimize levels for each asset in portf. 8:baseSol \(\leftarrow\) cleanSol(baseSol) \(\triangleright\) delete from portf. assets with level = 0
9:bestSol \(\leftarrow\) baseSol \(\triangleright\) initialize bestSol
10:elapsedTime \(\leftarrow\) 0
11:credit \(\leftarrow\) 0 \(\triangleright\) used in the acceptance criterion
12:while{elapsedTime \(<\) maxTime} do\(\triangleright\) iterated local search
13:newSol \(\leftarrow\) perturbateSol(baseSol, inputs, beta) \(\triangleright\) destruction-construction stages
14:if{getMaxReturnAsset(newSol) \(<\) minReturn} then\(\triangleright\) fix solution if unfeasible
15:newSol \(\leftarrow\) repairSol(newSol, inputs)
16:endif
17:if{newSol is in cache} then\(\triangleright\) already optimized levels
18:newSol \(\leftarrow\) loadFromCache(newSol) \(\triangleright\) use optimized levels saved in cache
19:else\(\triangleright\) apply a local search based on quadratic programming optimization
20:newSol \(\leftarrow\) QPOptimize(newSol, minReturn) \(\triangleright\) optimize levels f.e. asset in portf. 21:newSol \(\leftarrow\) cleanSol(newSol) \(\triangleright\) delete from portf. assets with level = 0
22:saveInCache(newSol)
23:endif
24:delta \(\leftarrow\) getRisk(newSol) - getRisk(baseSol) \(\triangleright\) newSol improves baseSol
25:if{delta < 0} then
26:credit \(\leftarrow\) -delta
27:baseSol \(\leftarrow\) newSol
28:if{getRisk(newSol) \(<\) getRisk(bestSol)} then\(\triangleright\) newSol improves bestSol
29:bestSol \(\leftarrow\) newSol
30:endif
31:else{delta \(>\) 0 and delta \(\leq\) credit} \(\triangleright\) acceptance criterion
32:credit \(\leftarrow\) 0
33:baseSol \(\leftarrow\) newSol
34:endif
35:update elapsedTime
36:endwhile
37:return bestSol
38:endprocedure
```  
**Algorithm 1** Main procedure of the ARPO algorithm (ILS framework). Finally, there might be times in which the newly generated solution does not fulfill the minimum return requirement. In those cases, a'repair' stage is used to swap a randomly selected asset in the current portfolio (lines 01-04) by a high-return asset not currently in the portfolio (lines 05-10) (Algorithm 3). As iterated local search and other similar approaches are stochastic in nature, it is not possible to give a sharp worst case complexity estimate for ARPO. However, experimentally, ILS and other similar approaches are found to perform well [69]. In our case, the time spent is bounded by the predefined time limit _maxTime_. Within the **while** loop, the search examines an ARPO perturbation, which is \(\Theta(n^{3})\). With an efficient random number generator, the other steps are constant or \(O(n)\) time. Thus, the total complexity is \(\Theta(n^{3})\) per iteration. ```
1:procedureperurbateSol(baseSol, inputs, beta)
2:newSol \(\leftarrow\) copySol(baseSol) \(\triangleright\) 1.