Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem

Jun He; Yong Wang; Yuren Zhou

doi:10.1007/978-3-319-16468-7_7

Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem

Jun He, Yong Wang, Yuren Zhou

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

2 Citations (Scopus)

155 Downloads (Pure)

Abstract

Multi-objective optimisation is regarded as one of the most promising ways for dealing with constrained optimisation problems in evolutionary optimisation. This paper presents a theoretical investigation of a multi-objective optimisation evolutionary algorithm for solving the 0-1 knapsack problem. Two initialisation methods are considered in the algorithm: local search initialisation and
greedy search initialisation. Then the solution quality of the algorithm is analysed in terms of the approximation ratio.

Original language	English
Title of host publication	Evolutionary Computation in Combinatorial Optimization
Editors	Gabriela Ochoa
Publisher	Springer Nature
Pages	74-85
Volume	9026
ISBN (Electronic)	978-3-319-16468-7
ISBN (Print)	978-3-319-16467-0, 3319164678
DOIs	https://doi.org/10.1007/978-3-319-16468-7_7
Publication status	Published - 15 Mar 2015

Publication series

Name	Lecture notes in Computer Science
Volume	9026

Access to Document

10.1007/978-3-319-16468-7_7

paper-B4-archiveSubmitted manuscript, 265 KBLicence: Unclear 1

Permanent link

Persistent link

Cite this

@inproceedings{e1157679be7c4ca08ca4cac0b3f1f2e4,

title = "Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem",

abstract = "Multi-objective optimisation is regarded as one of the most promising ways for dealing with constrained optimisation problems in evolutionary optimisation. This paper presents a theoretical investigation of a multi-objective optimisation evolutionary algorithm for solving the 0-1 knapsack problem. Two initialisation methods are considered in the algorithm: local search initialisation andgreedy search initialisation. Then the solution quality of the algorithm is analysed in terms of the approximation ratio.",

author = "Jun He and Yong Wang and Yuren Zhou",

year = "2015",

month = mar,

day = "15",

doi = "10.1007/978-3-319-16468-7_7",

language = "English",

isbn = "978-3-319-16467-0",

volume = "9026",

series = "Lecture notes in Computer Science",

publisher = "Springer Nature",

pages = "74--85",

editor = "Gabriela Ochoa",

booktitle = "Evolutionary Computation in Combinatorial Optimization",

address = "Switzerland",

}

Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem. / He, Jun; Wang, Yong; Zhou, Yuren.
Evolutionary Computation in Combinatorial Optimization. ed. / Gabriela Ochoa. Vol. 9026 Springer Nature, 2015. p. 74-85 (Lecture notes in Computer Science; Vol. 9026).

Research output: Chapter in Book/Report/Conference proceeding › Conference Proceeding (Non-Journal item)

TY - GEN

T1 - Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem

AU - He, Jun

AU - Wang, Yong

AU - Zhou, Yuren

PY - 2015/3/15

Y1 - 2015/3/15

N2 - Multi-objective optimisation is regarded as one of the most promising ways for dealing with constrained optimisation problems in evolutionary optimisation. This paper presents a theoretical investigation of a multi-objective optimisation evolutionary algorithm for solving the 0-1 knapsack problem. Two initialisation methods are considered in the algorithm: local search initialisation andgreedy search initialisation. Then the solution quality of the algorithm is analysed in terms of the approximation ratio.

AB - Multi-objective optimisation is regarded as one of the most promising ways for dealing with constrained optimisation problems in evolutionary optimisation. This paper presents a theoretical investigation of a multi-objective optimisation evolutionary algorithm for solving the 0-1 knapsack problem. Two initialisation methods are considered in the algorithm: local search initialisation andgreedy search initialisation. Then the solution quality of the algorithm is analysed in terms of the approximation ratio.

UR - http://hdl.handle.net/2160/30471

U2 - 10.1007/978-3-319-16468-7_7

DO - 10.1007/978-3-319-16468-7_7

M3 - Conference Proceeding (Non-Journal item)

SN - 978-3-319-16467-0

SN - 3319164678

VL - 9026

T3 - Lecture notes in Computer Science

SP - 74

EP - 85

BT - Evolutionary Computation in Combinatorial Optimization

A2 - Ochoa, Gabriela

PB - Springer Nature

ER -

Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem

Abstract

Publication series

Access to Document

Permanent link

Other files and links

Fingerprint

Evolutionary Approximation Algorithms for Optimization: Algorithm design and Complexity Analysis

Cite this

Analysis of Solution Quality of a Multiobjective Optimization-based Evolutionary Algorithm for Knapsack Problem

Abstract

Publication series

Access to Document

Permanent link

Other files and links

Fingerprint

Projects

Evolutionary Approximation Algorithms for Optimization: Algorithm design and Complexity Analysis

Cite this