Exploring the runtime of an evolutionary algorithm for the multiobjective shortest path problem. 

Abstract  We present a natural vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase optimization time. 
PMID  20560760 
Related Publications 
Tight analysis of the (1+1)EA for the single source shortest path problem. On the effect of populations in evolutionary multiobjective optimisation. Runtime analysis of the (mu+1) EA on simple PseudoBoolean functions. 
Authors  
Mayor MeshTerms  
Keywords  
Journal Title  evolutionary computation 
Publication Year Start  20100101 
%A Horoba, Christian %T Exploring the runtime of an evolutionary algorithm for the multiobjective shortest path problem. %J Evolutionary computation, vol. 18, no. 3, pp. 357381 %D 00/2010 %V 18 %N 3 %M eng %B We present a natural vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase 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 multiobjective shortest path problem.", journal="Evolutionary computation", year="2010", volume="18", number="3", pages="357381", keywords="Algorithms", keywords="Biological Evolution", keywords="Models, Statistical", abstract="We present a natural vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase optimization time.", issn="15309304", 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 multiobjective shortest path problem. %A Horoba, Christian %J Evolutionary computation %D 2010 %V 18 %N 3 %@ 15309304 %G eng %F Horoba2010 %X We present a natural vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase 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 357381
PT Journal AU Horoba, C TI Exploring the runtime of an evolutionary algorithm for the multiobjective 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 vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase optimization time. ER
PMID 20560760 OWN  NLM STAT MEDLINE DA  20100803 DCOM 20101105 LR  20101118 IS  15309304 (Electronic) IS  10636560 (Linking) VI  18 IP  3 DP  2010 Fall TI  Exploring the runtime of an evolutionary algorithm for the multiobjective shortest path problem. PG  35781 LID  10.1162/EVCO_a_00014 [doi] AB  We present a natural vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase 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):35781. doi: 10.1162/EVCO_a_00014.
TY  JOUR AU  Horoba, Christian PY  2010// TI  Exploring the runtime of an evolutionary algorithm for the multiobjective 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 vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase optimization time. SN  15309304 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="UTF8"?> <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>357381</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 multiobjective shortest path problem.</b:Title> <b:ShortTitle>Evol Comput</b:ShortTitle> <b:Comments>We present a natural vectorvalued fitness function f for the multiobjective shortest path problem, which is a fundamental multiobjective combinatorial optimization problem known to be NPhard. Thereafter, we conduct a rigorous runtime analysis of a simple evolutionary algorithm (EA) optimizing f. Interestingly, this simple general algorithm is a fully polynomialtime 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 worstcase optimization time.</b:Comments> </b:Source> </b:Sources>