A directed quantile cross-entropy method for 0/1 knapsack problems

Libao Deng; Liyan Qiao; Xiyuan Peng

doi:10.1109/ICEMI.2009.5274055

A directed quantile cross-entropy method for 0/1 knapsack problems

Libao Deng^*
, Liyan Qiao
, Xiyuan Peng

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

Abstract

Cross-entropy method is base on probability density function. It is robust, easy to use. With analysis of advantages and disadvantages of the cross-entropy method, a directed quantile method based on cross-entropy is proposed. The main idea of the directed quantile cross-entropy method is to select alterable quantity vectors using for producing a "better" sample in the next iteration. The convergence speed and search best result of the directed quantile cross-entropy are tested using 0/1 knapsack problems. The experiments show that the search efficiency of the modified cross-entropy method is more significantly improved than quantum-inspired evolutionary algorithm and cross-entropy method.

Original language	English
Title of host publication	ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments
Publisher	IEEE Computer Society
Pages	319-322
Number of pages	4
ISBN (Print)	9781424438624
DOIs	https://doi.org/10.1109/ICEMI.2009.5274055
State	Published - 2009
Event	9th International Conference on Electronic Measurement and Instruments, ICEMI 2009 - Beijing, China Duration: 16 Aug 2009 → 19 Aug 2009

Publication series

Name	ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments

Conference

Conference	9th International Conference on Electronic Measurement and Instruments, ICEMI 2009
Country/Territory	China
City	Beijing
Period	16/08/09 → 19/08/09

Keywords

0/1 knapsack problems
Cross-entropy method
Optimization algorithm

Access to Document

10.1109/ICEMI.2009.5274055

Cite this

Deng, L., Qiao, L., & Peng, X. (2009). A directed quantile cross-entropy method for 0/1 knapsack problems. In ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments (pp. 319-322). Article 5274055 (ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments). IEEE Computer Society. https://doi.org/10.1109/ICEMI.2009.5274055

@inproceedings{803d5240bcec43a3a18cada7a2e916f4,

title = "A directed quantile cross-entropy method for 0/1 knapsack problems",

abstract = "Cross-entropy method is base on probability density function. It is robust, easy to use. With analysis of advantages and disadvantages of the cross-entropy method, a directed quantile method based on cross-entropy is proposed. The main idea of the directed quantile cross-entropy method is to select alterable quantity vectors using for producing a {"}better{"} sample in the next iteration. The convergence speed and search best result of the directed quantile cross-entropy are tested using 0/1 knapsack problems. The experiments show that the search efficiency of the modified cross-entropy method is more significantly improved than quantum-inspired evolutionary algorithm and cross-entropy method.",

keywords = "0/1 knapsack problems, Cross-entropy method, Optimization algorithm",

author = "Libao Deng and Liyan Qiao and Xiyuan Peng",

year = "2009",

doi = "10.1109/ICEMI.2009.5274055",

language = "英语",

isbn = "9781424438624",

series = "ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments",

publisher = "IEEE Computer Society",

pages = "319--322",

booktitle = "ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments",

address = "美国",

note = "9th International Conference on Electronic Measurement and Instruments, ICEMI 2009 ; Conference date: 16-08-2009 Through 19-08-2009",

}

Deng, L , Qiao, L & Peng, X 2009, A directed quantile cross-entropy method for 0/1 knapsack problems. in ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments., 5274055, ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments, IEEE Computer Society, pp. 319-322, 9th International Conference on Electronic Measurement and Instruments, ICEMI 2009, Beijing, China, 16/08/09. https://doi.org/10.1109/ICEMI.2009.5274055

A directed quantile cross-entropy method for 0/1 knapsack problems. / Deng, Libao ; Qiao, Liyan ; Peng, Xiyuan.
ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments. IEEE Computer Society, 2009. p. 319-322 5274055 (ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A directed quantile cross-entropy method for 0/1 knapsack problems

AU - Deng, Libao

AU - Qiao, Liyan

AU - Peng, Xiyuan

PY - 2009

Y1 - 2009

N2 - Cross-entropy method is base on probability density function. It is robust, easy to use. With analysis of advantages and disadvantages of the cross-entropy method, a directed quantile method based on cross-entropy is proposed. The main idea of the directed quantile cross-entropy method is to select alterable quantity vectors using for producing a "better" sample in the next iteration. The convergence speed and search best result of the directed quantile cross-entropy are tested using 0/1 knapsack problems. The experiments show that the search efficiency of the modified cross-entropy method is more significantly improved than quantum-inspired evolutionary algorithm and cross-entropy method.

AB - Cross-entropy method is base on probability density function. It is robust, easy to use. With analysis of advantages and disadvantages of the cross-entropy method, a directed quantile method based on cross-entropy is proposed. The main idea of the directed quantile cross-entropy method is to select alterable quantity vectors using for producing a "better" sample in the next iteration. The convergence speed and search best result of the directed quantile cross-entropy are tested using 0/1 knapsack problems. The experiments show that the search efficiency of the modified cross-entropy method is more significantly improved than quantum-inspired evolutionary algorithm and cross-entropy method.

KW - 0/1 knapsack problems

KW - Cross-entropy method

KW - Optimization algorithm

UR - https://www.scopus.com/pages/publications/71549171455

U2 - 10.1109/ICEMI.2009.5274055

DO - 10.1109/ICEMI.2009.5274055

M3 - 会议稿件

AN - SCOPUS:71549171455

SN - 9781424438624

T3 - ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments

SP - 319

EP - 322

BT - ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments

PB - IEEE Computer Society

T2 - 9th International Conference on Electronic Measurement and Instruments, ICEMI 2009

Y2 - 16 August 2009 through 19 August 2009

ER -

Deng L , Qiao L , Peng X. A directed quantile cross-entropy method for 0/1 knapsack problems. In ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments. IEEE Computer Society. 2009. p. 319-322. 5274055. (ICEMI 2009 - Proceedings of 9th International Conference on Electronic Measurement and Instruments). doi: 10.1109/ICEMI.2009.5274055

A directed quantile cross-entropy method for 0/1 knapsack problems

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this