Computing a Finite Size Representation of the Set of Approximate Solutions of an MOP

Oliver Schuetze; Carlos A. Coello Coello; Emilia Tantar; El-Ghazali Talbi

inria-00269410, version 2

Computing a Finite Size Representation of the Set of Approximate Solutions of an MOP

Oliver Schuetze ¹, Carlos A. Coello Coello ², Emilia Tantar ², El-Ghazali Talbi ^{1, 3, 4, 5}

N° RR-6492 (2008)

Abstract: Recently, a framework for the approximation of the entire set of $\epsilon$-efficient solutions (denote by $E_\epsilon$) of a multi-objective optimization problem with stochastic search algorithms has been proposed. It was proven that such an algorithm produces -- under mild assumptions on the process to generate new candidate solutions --a sequence of archives which converges to $E_{\epsilon}$ in the limit and in the probabilistic sense. The result, though satisfactory for most discrete MOPs, is at least from the practical viewpoint not sufficient for continuous models: in this case, the set of approximate solutions typically forms an $n$-dimensional object, where $n$ denotes the dimension of the parameter space, and thus, it may come to perfomance problems since in practise one has to cope with a finite archive.\\ Here we focus on obtaining finite and tight approximations of $E_\epsilon$, the latter measured by the Hausdorff distance. We propose and investigate a novel archiving strategy theoretically and empirically. For this, we analyze the convergence behavior of the algorithm, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting approximation, and present some numerical results.

1: DOLPHIN (INRIA Futurs)
INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies
2: DOLPHIN (INRIA Lille - Nord Europe)
INRIA – CNRS : UMR8022 – Université Lille I - Sciences et technologies
3: Laboratoire d'Informatique Fondamentale et d'Intelligence Artificielle (LIFIA)
Institut National Polytechnique de Grenoble (INPG)
4: Laboratoire de Génie Informatique (LGI - IMAG)
IMAG – Université Joseph Fourier - Grenoble I
5: Laboratoire d'Informatique Fondamentale de Lille (LIFL)
CNRS : UMR8022 – Université Lille I - Sciences et technologies – Université Lille III - Sciences humaines et sociales – INRIA

inria-00269410, version 2
http://hal.inria.fr/inria-00269410
oai:hal.inria.fr:inria-00269410
From: Rapport De Recherche Inria <>
Submitted on: Friday, 4 April 2008 10:16:33
Updated on: Tuesday, 21 October 2008 16:58:13

See detailed view

Associated documents

PS :

PDF :

arXiv: 0804.0581

Export

Bibtex EndNote TEI RefWorks

%% inria-00269410, version 2
%% http://hal.inria.fr/inria-00269410
@techreport{schuetze:inria-00269410,
    hal_id = {inria-00269410},
    url = {http://hal.inria.fr/inria-00269410},
    title = {{Computing a Finite Size Representation of the Set of Approximate Solutions of an MOP}},
    author = {Schuetze, Oliver and Coello Coello, Carlos A. and Tantar, Emilia and Talbi, El-Ghazali},
    abstract = {{Recently, a framework for the approximation of the entire set of $\epsilon$-efficient solutions (denote by $E\_\epsilon$) of a multi-objective optimization problem with stochastic search algorithms has been proposed. It was proven that such an algorithm produces -- under mild assumptions on the process to generate new candidate solutions --a sequence of archives which converges to $E\_{\epsilon}$ in the limit and in the probabilistic sense. The result, though satisfactory for most discrete MOPs, is at least from the practical viewpoint not sufficient for continuous models: in this case, the set of approximate solutions typically forms an $n$-dimensional object, where $n$ denotes the dimension of the parameter space, and thus, it may come to perfomance problems since in practise one has to cope with a finite archive.\\ Here we focus on obtaining finite and tight approximations of $E\_\epsilon$, the latter measured by the Hausdorff distance. We propose and investigate a novel archiving strategy theoretically and empirically. For this, we analyze the convergence behavior of the algorithm, yielding bounds on the obtained approximation quality as well as on the cardinality of the resulting approximation, and present some numerical results.}},
    keywords = {multi-objective optimization; convergence; epsilon-efficient solutions; approximate solutions; stochastic search algorithms},
    language = {English},
    affiliation = {DOLPHIN - INRIA Futurs , DOLPHIN - INRIA Lille - Nord Europe , Laboratoire d'Informatique Fondamentale et d'Intelligence Artificielle - LIFIA , Laboratoire de G{\'e}nie Informatique - LGI - IMAG , Laboratoire d'Informatique Fondamentale de Lille - LIFL},
    type = {Research Report},
    institution = {INRIA},
    number = {RR-6492},
    year = {2008},
    pdf = {http://hal.inria.fr/inria-00269410/PDF/RR-6492.pdf},
}

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="report"><head>Research reports</head>
<biblStruct type="report" xml:id="inria-00269410"><monogr>
<author><persName><forename>Oliver</forename><surname>Schuetze</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">DOLPHIN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
</affiliation>
</author>
<author><persName><forename>Carlos A.</forename><surname>Coello Coello</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">DOLPHIN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
</affiliation>
</author>
<author><persName><forename>Emilia</forename><surname>Tantar</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lille - Nord Europe</orgName>
<orgName type="team">DOLPHIN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
</affiliation>
</author>
<author><persName><forename>El-Ghazali</forename><surname>Talbi</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Futurs</orgName>
<orgName type="team">DOLPHIN</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIFIA</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale et d'Intelligence Artificielle</orgName>
<country>FR</country>
<orgName type="institution">Institut National Polytechnique de Grenoble (INPG)</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LGI - IMAG</orgName>
<orgName type="team">Laboratoire de Génie Informatique</orgName>
<country>FR</country>
<orgName type="institution">IMAG</orgName>
<orgName type="institution">Université Joseph Fourier - Grenoble I</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LIFL</orgName>
<orgName type="team">Laboratoire d'Informatique Fondamentale de Lille</orgName>
<country>FR</country>
<orgName type="institution">CNRS : UMR8022</orgName>
<orgName type="institution">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution">Université Lille III - Sciences humaines et sociales</orgName>
<orgName type="institution">INRIA</orgName>
</affiliation>
</author>
<title type="main" level="m">Computing a Finite Size Representation of the Set of Approximate Solutions of an MOP</title><title type="main" level="m">Computing a Finite Size Representation of the Set of Approximate Solutions of an MOP</title><imprint><biblScope type="publicationDate">2008-00-00</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00269410</idno><idno type="HALFile">http://hal.inria.fr/inria-00269410/PDF/RR-6492.pdf</idno></biblStruct>
</listBibl>
</listBibl>