Evolutionary Algorithm Portfolios For Real-Parameter Optimization

Real-parameter optimization has widespread applications in the real world. In-spired from the evolution and self-adaptation mechanism from nature, evolutionary al-gorithms are a class of general purpose problem solving procedures. Due to their easeofimplementationandcapabilityofglobaloptimization, theyhavesuccessivelyappliedto various real-parameter optimization problems, and gained more and more attention.During past decades, numerous evolutionary algorithms and their variants have beenproposed for real-parameter optimization. On one hand, the emergence has boosted thedevelopment of the evolutionary real-parameter optimization area. On the other hand,it has also made it more difficult for practitioners to choose an appropriate algorithm fortheir problems. In practice, there is usually a user-defined time budget, within whichsolutions needs to be presented. In consequence, the problem of how to find as good aspossible solutions within a time budget is of great practical importance.For a given problem, there are usually a number of evolutionary algorithms thatare applicable. However, their performance may vary significantly from problem toproblem. It is usually the case that people do not know which algorithm could solve theproblem well in prior. Once the chosen algorithm does not work well, the limited timebudget might not allow trying another one. This implies that there is an inherent risk as-sociated with the selection of algorithms. We proposed a metric for comparing the risksof any two algorithms on a problem set, and discussed the rationality. For reducing therisk of algorithms, we further suggested that, instead of"betting"the entire time budgetona single algorithm, it would be less risky to distribute the time among multiple differ-ent algorithms. Based on the idea, a new approach named population-based algorithmportfolio(PAP)wasproposed. Ittakesmultiplealgorithmsasitsconstituentalgorithms,andallocatetimeamongthem. Alltheconstituentalgorithmsconductsearchinparallel.Interaction among the constituent algorithms was encouraged with a migration scheme.As a general framework rather than a specific algorithm, PAP is easy to implement, andcan accommodate any existing evolutionary algorithms. By theoretical analysis and ex-periments, we comprehensively evaluated its capability of leveraging the performanceof its constituent algorithms and reducing the risk.After that, we further discussed how to obtain as good as possible solutions for aset of problems, within a user-defined time budget. For a problem set, numerous algo-rithms can be applied as the candidate solvers. Instead of manually picking one from the candidate algorithms and assigning the entire time on it, it would be desirable toappend an algorithm selection phase before solving the problems. Based on the consid-eration, we proposed a novel approach, which takes PAP as the basic search procedure.It can automatically find a best PAP instantiation for the whole problem set, avoidingfind-tuningaspecificalgorithmforaspecificproblem. Furthermore, itdoesnotassumeany correlation between problems as well as candidate algorithms, and utilizes the per-formance information on the whole problem set. Though PAP has showed potential inleveraging the overall performance of its constituent algorithms, no work on how toselect an algorithm subset to construct the best PAP instantiation has been reported yet.We, for the first time, formalize the selection task as an optimization problem, and thenpresent two selection methods to accomplish the task efficiently. Experimental resultsshowed that, our approach is quite effective for solving a set of problems.In the last, we applied the PAP framework to synthesize unequally spaced anten-na arrays. Since both differential evolution and particle swarm optimizer have showedeffectiveness in the synthesis problem, we choose one variant of differential evolutionand one variant of particle swarm optimizer as the constituent algorithms, to constructPAP instantiation. By comparing to the state-of-the-art algorithm in the literature ofsynthesizing unequally spaced antenna arrays, we comprehensively evaluated the per-formance of our approach. On all the four synthesis problems, our approach found thebest objective function values, and also showed the best reliability. In addition, whenwe need solutions with higher quality, our approach is more efficient.