Informed Push & Pull Search for Solving Constrained Multi-Objective Optimisation

Abstract

Den siste tiden har forskning fokusert på Beskrankede Flerkriterie-Problemer (BFPer) ettersom beskrankninger byr på krevende utfordringer som må løses. For å overkomme denne utfordringen har nye kunstige testproblemer blitt utviklet for ̊a simulere problemer fra den virkelige verden. I tillegg har Flerkriterie Evolusjonære Algorithmer (EAer) blitt utvidet med Beskrankningshåndtering-metoder (BHMer) for å løse disse problemene. Vanligvis er oppførselen til BHMer kun påvirket av informasjon om selve populasjonen. Det har har vært lite bruk av informasjon innhentet under søket for å påvirke optimeringen av BFPer. Flere kriterier sammen med beskrankninger øker utfordringen med å konvergere mot optimale løsninger i tillegg til ̊å oppnå en høy dekningsgrad av løsninger som oppfyller beskrankningene. Nyere forskning har brakt frem et to-fase rammeverk kalt Push and Pull Search (PPS). PPS ignorerer beskrankninger under den første fasen av søket og fokuserer på å utforske en større del av søkerommet. Under den andre fasen av søket blir beskrankninger tatt med i beregningen og målet er da å finne optimale løsninger som ikke bryter beskrankningene til problemet. Denne avhandlingen utforsker bruken av informasjon innhentet under søket for å videreutvikle det nye rammeverket PPS. Herunder utforskes hvordan Grensesøk (GS) påvirker ytelse, håndtering av ulike problemkarakteristikker, traversering gjennom landskapet, og om hvordan visse deler av søkerommet blir foretrukket fremfor andre.

In recent years, Constrained Multi-Objective Problems (CMOPs) have gained a considerable focus by the research community as the existence of constraints provide challenges the field is struggling to solve. To overcome this obstacle, research has delved into the development of artificial problems to simulate their real-world coun- terparts and extending Multi-Objective Evolutionary Algorithms (MOEAs) with Constraint-Handling Methods (CHMs) to solve these problems. In general, CHMs within the field are influenced by information extracted from the current population alone. Thus, little work gathers knowledge during the search to influence the optimisation of the CMOP. Multiple objectives in conjunction with constraints add difficulty in converging towards optimal solutions, as well as coverage of all solutions fulfilling the constraints. Recent advances within this field introduced a biphasic framework, called Push and Pull Search (PPS). The original PPS ignores constraints during the first phase of the search to focus on exploration of the whole search space and approximating the unconstrained Pareto-optimal Front (PF). During the second phase, constraints are considered and previously infeasible solutions are evolved to become feasible in an effort to approximate the constrained PF. Splitting the Constrained Multi-Objective Evolutionary Algorithm (CMOEA) into two phases to meet the challenges of exploration and exploitation, this thesis further explores the use of landscape knowledge to enhance the newly developed PPS framework. The effect on search performance, different problem characteristics behaviour, traversal through constrained space and bias towards certain parts of the search space, introduced by Boundary Search (BS), are analysed and discussed.