PubTransformer

A site to transform Pubmed publications into these bibliographic reference formats: ADS, BibTeX, EndNote, ISI used by the Web of Knowledge, RIS, MEDLINE, Microsoft's Word 2007 XML.

Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.

Abstract We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.
PMID
Related Publications

An efficient and accurate solution methodology for bilevel multi-objective programming problems using a hybrid evolutionary-local-search algorithm.

Tight analysis of the (1+1)-EA for the single source shortest path problem.

An impatient evolutionary algorithm with probabilistic tabu search for unified solution of some NP-hard problems in graph and set theory via clique finding.

On the effect of populations in evolutionary multi-objective optimisation.

Runtime analysis of the (mu+1) EA on simple Pseudo-Boolean functions.

Authors

Mayor MeshTerms

Algorithms

Biological Evolution

Keywords
Journal Title evolutionary computation
Publication Year Start
%A Horoba, Christian
%T Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.
%J Evolutionary computation, vol. 18, no. 3, pp. 357-381
%D 00/2010
%V 18
%N 3
%M eng
%B We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.
%K Algorithms, Biological Evolution, Models, Statistical
%P 357
%L 381
%Y 10.1162/EVCO_a_00014
%W PHY
%G AUTHOR
%R 2010.......18..357H

@Article{Horoba2010,
author="Horoba, Christian",
title="Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.",
journal="Evolutionary computation",
year="2010",
volume="18",
number="3",
pages="357--381",
keywords="Algorithms",
keywords="Biological Evolution",
keywords="Models, Statistical",
abstract="We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.",
issn="1530-9304",
doi="10.1162/EVCO_a_00014",
url="http://www.ncbi.nlm.nih.gov/pubmed/20560760",
language="eng"
}

%0 Journal Article
%T Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.
%A Horoba, Christian
%J Evolutionary computation
%D 2010
%V 18
%N 3
%@ 1530-9304
%G eng
%F Horoba2010
%X We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.
%K Algorithms
%K Biological Evolution
%K Models, Statistical
%U http://dx.doi.org/10.1162/EVCO_a_00014
%U http://www.ncbi.nlm.nih.gov/pubmed/20560760
%P 357-381

PT Journal
AU Horoba, C
TI Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.
SO Evolutionary computation
JI Evol Comput
PY 2010
BP 357
EP 381
VL 18
IS 3
DI 10.1162/EVCO_a_00014
LA eng
DE Algorithms; Biological Evolution; Models, Statistical
AB We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.
ER

PMID- 20560760
OWN - NLM
STAT- MEDLINE
DA  - 20100803
DCOM- 20101105
LR  - 20101118
IS  - 1530-9304 (Electronic)
IS  - 1063-6560 (Linking)
VI  - 18
IP  - 3
DP  - 2010 Fall
TI  - Exploring the runtime of an evolutionary algorithm for the multi-objective
      shortest path problem.
PG  - 357-81
LID - 10.1162/EVCO_a_00014 [doi]
AB  - We present a natural vector-valued fitness function f for the multi-objective
      shortest path problem, which is a fundamental multi-objective combinatorial
      optimization problem known to be NP-hard. Thereafter, we conduct a rigorous
      runtime analysis of a simple evolutionary algorithm (EA) optimizing f.
      Interestingly, this simple general algorithm is a fully polynomial-time
      randomized approximation scheme (FPRAS) for the problem under consideration,
      which exemplifies how EAs are able to find good approximate solutions for hard
      problems. Furthermore, we present lower bounds for the worst-case optimization
      time.
FAU - Horoba, Christian
AU  - Horoba C
AD  - Fakultat fur Informatik, TU Dortmund, 44221 Dortmund, Germany.
      [email protected]
LA  - eng
PT  - Journal Article
PL  - United States
TA  - Evol Comput
JT  - Evolutionary computation
JID - 9513581
SB  - IM
MH  - *Algorithms
MH  - *Biological Evolution
MH  - Models, Statistical
EDAT- 2010/06/22 06:00
MHDA- 2010/11/06 06:00
CRDT- 2010/06/22 06:00
AID - 10.1162/EVCO_a_00014 [doi]
PST - ppublish
SO  - Evol Comput. 2010 Fall;18(3):357-81. doi: 10.1162/EVCO_a_00014.
TY  - JOUR
AU  - Horoba, Christian
PY  - 2010//
TI  - Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.
T2  - Evol Comput
JO  - Evolutionary computation
SP  - 357
EP  - 381
VL  - 18
IS  - 3
KW  - Algorithms
KW  - Biological Evolution
KW  - Models, Statistical
N2  - We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.
SN  - 1530-9304
UR  - http://dx.doi.org/10.1162/EVCO_a_00014
UR  - http://www.ncbi.nlm.nih.gov/pubmed/20560760
ID  - Horoba2010
ER  - 
<?xml version="1.0" encoding="UTF-8"?>
<b:Sources SelectedStyle="" xmlns:b="http://schemas.openxmlformats.org/officeDocument/2006/bibliography"  xmlns="http://schemas.openxmlformats.org/officeDocument/2006/bibliography" >
<b:Source>
<b:Tag>Horoba2010</b:Tag>
<b:SourceType>ArticleInAPeriodical</b:SourceType>
<b:Year>2010</b:Year>
<b:PeriodicalName>Evolutionary computation</b:PeriodicalName>
<b:Volume>18</b:Volume>
<b:Issue>3</b:Issue>
<b:Pages>357-381</b:Pages>
<b:Author>
<b:Author><b:NameList>
<b:Person><b:Last>Horoba</b:Last><b:First>Christian</b:First></b:Person>
</b:NameList></b:Author>
</b:Author>
<b:Title>Exploring the runtime of an evolutionary algorithm for the multi-objective shortest path problem.</b:Title>
 <b:ShortTitle>Evol Comput</b:ShortTitle>
<b:Comments>We present a natural vector-valued fitness function f for the multi-objective shortest path problem, which is a fundamental multi-objective combinatorial optimization problem known to be NP-hard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomial-time randomized approximation scheme (FPRAS) for the problem under consideration, which exemplifies how EAs are able to find good approximate solutions for hard problems. Furthermore, we present lower bounds for the worst-case optimization time.</b:Comments>
</b:Source>
</b:Sources>