Algorithms for uniform distribution of solutions over Pareto set, and their applications in risk management
Daug praktinių optimizacijos taikymų iš esmės yra daugiakriteriniai. Realybėje sprendžiant inžinerijos uždavinius, sprendimą priimantis asmuo gali atsižvelgti tik į kelis galimus sprendinius. Taigi, sprendimą priimantis asmuo turi gauti pakankamai Pareto taškų, kurie deramai padengtų minimalią aibę kriterijų erdvėje. Šiame kontekste yra labai svarbu turėti vienodai pasiskirsčiusią reprezentatyvią Pareto optimalių sprendinių aibę tam, kad gautume kuo daugiau informacijos apie visą Pareto paviršių patiriant mažiausius skaičiavimo kaštus. Tolygus sprendinių pasiskirstymas minimizuoja neištirtų sričių dydį, kitais žodžiais tariant, jis minimizuoja atstumą tarp potencialaus pageidautino sprendinio ir vieno iš gautųjų. Gerai žinoma, kad vienodas taškų pasiskirstymas yra sudėtinga užduotis net turint aiškiai apibrėžtas aibes. Šiame darbe pasiūlyti du algoritmai, surandantys tolygiai pasiskirsčiusius sprendinius Pareto aibėje. Pirmajame metode Pareto sprendiniai yra randami minimizuojant kriterijų svorinę sumą, kai svoriniai koeficientai kiekvienai tikslo funkcijai yra parenkami adaptyviai algoritmo viduje. Antrasis metodas nuosekliai sprendžia seką leksikografinio tikslo programavimo uždavinių su skirtingais nuorodų taškais, sąlygojančiais skirtingus sprendinius. Jų efektyvumas buvo įvertintas keturių matų atžvilgiu ir palygintas su metaeuristiniais algoritmais. Pasiūlyti adaptyvių svorių ir nuoseklus leksikografinio tikslo programavimo algoritmai buvo taikomi spręsti portfelio optimizavimo ir elektros energijos kontraktų įkainavimo uždavinius.
Engineering design optimization and many other practical optimization applications are generally multi-objective. In real industrial design the decision-maker is able to consider only a few possible solutions. Therefore, the decision-maker must be satisfied by obtaining enough Pareto optima to cover the minimal set in the criteria space properly. In such a context, it is crucial to have a uniform distribution of representative Pareto set to obtain maximum information on the whole Pareto surface at minimum computational cost. Uniform distribution is advantageous since it minimizes the size of not researched ’holes’ in the Pareto set, in other words it minimizes guaranteed distance between a potentially favorable solution and one of generated points. It is well known, however, that the uniform distribution of points is a difficult problem even for explicitly defined simple sets. In this research two methods for generating solutions uniformly distributed in the Pareto set are prosed. By the first method Pareto solutions are found minimizing weighted sums of objectives where weights are properly selected using branch and bound approach. The second method solves a sequence of lexicographic goal programming problems with different reference points producing different solutions. Their performance was estimated with regards to four performance metrics and compared with metaheuristics algorithms. The developed algorithms were applied to solve optimal portfolio selection problems as well as pricing tolling agreements problem.