On the distribution of Pareto optimal solutions in alternative space – the investigation of multi objective permutation flow shop scheduling problems

Abstract

The paper presents a study of the search space topology in the context of global optimization under multiple objectives. While in mono criterion problems a single global optimum has to be identified, multi objective problems require the identification of a whole set of equal. Pareto optimal alternatives. It is unclear up to now, however, whether Pareto optimal solutions appear relatively concentrated in search space, or whether their relative positions are rather distant. This open issue is addressed to the multi objective permutation flow shop scheduling problems. Distance metrics is introduced to asses numerical evaluation of the concentration of Pareto sets. It can be seen that independent from the chosen optimality criteria, Pareto optimal alternatives appear relatively concentrated in alternative space. The result holds for an extensive range of generated problem instances for which the exact global optima are known as well as for benchmark instances taken from literature. The importance of the results can be seen in the context of metaheuristic local search approaches for which meaningful implications derive.

Pareto optimalių sprendimų paskirstymas alternatyvioje erdvėje ir daugiaaspekčių planavimo problemų tyrimas

Santrauka. Nagrinėjamos daugiatikslio optimizavimo problemos. Vieno kriterijaus uždaviniuose yra tik vienas globalinis optimumas, daugiatikslio optimizavimo uždaviniuose gaunama visa aibė Pareto optimalių alternatyvų. Iki šiol neaišku, ar tos alternatyvos arti viena kitos, ar nutolusios. Skaitmeninei Pareto aibės koncentracijai nustatyti pritaikyta „išsibarstymo“ įvertinimo metrodika. Pastebėta, jog nepriklausančios nuo pasirinkto optimalumo kriterijaus alternatyvos yra santykinai susikoncentravusios alternatyvioje erdvėje. Išspręsta daug skaičiavimo pavyzdžių, kurių tikslus globalinis optimumas buvo žinomas, taip pat lyginamųjų pavyzdžių iš įvairios literatūros. Skaičiavimo rezultatai yra svarbūs metaeuristiniams metodams tobulinti.

Reikšminiai žodžiai: landšafto profilis, daugiatikslė optimizacija, planavimas, vietinis tyrimas, globalinė optimizacija, metaeuristika.

First Published Online: 21 Oct 2010

Keyword : Fitness landscapes, multi objective optimization, flow shop scheduling, local search, global optimization, metaheuristic