An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm

Claudio L.V. Lopes; Flávio V.C. Martins; Elizabeth F. Wanner; Kalyanmoy Deb

doi:10.1145/3449726.3459445

An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm

Claudio L.V. Lopes, Flávio V.C. Martins, Elizabeth F. Wanner, Kalyanmoy Deb

Research output: Chapter in Book/Published conference output › Conference publication

Abstract

Dominance move (DoM) is a quality indicator that compares two solution sets in a Pareto-optimal sense. The main issue related to DoM is its computational expense. A recent paper proposed a mixed-integer programming (MIP) approach for computing DoM that exhibited a computational complexity that is linear to the number of objectives and polynomial to the number of solutions. Even with this property, considering practical situations, the MIP-DoM calculation on some problems may take many hours. This paper presents an approximation method to deal with the problem using a cluster-based and divide-and-conquer strategy. Some experiments are tested, showing that the cluster based-algorithm is computationally much faster and makes a small percentage error from the original DoM value.

Original language	English
Title of host publication	GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion
Publisher	ACM
Pages	185-186
ISBN (Electronic)	9781450383516
DOIs	https://doi.org/10.1145/3449726.3459445
Publication status	Published - 8 Jul 2021
Event	2021 Genetic and Evolutionary Computation Conference, GECCO 2021 - Virtual, Online, France Duration: 10 Jul 2021 → 14 Jul 2021

Publication series

Name	GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

Conference

Conference	2021 Genetic and Evolutionary Computation Conference, GECCO 2021
Country/Territory	France
City	Virtual, Online
Period	10/07/21 → 14/07/21

Bibliographical note

Publisher Copyright:
© 2021 Owner/Author.

Keywords

cluster algorithms
computationally expensive optimization
evolutionary multi-objective optimization
machine learning
multi-objective optimization

Access to Document

10.1145/3449726.3459445

Cite this

Lopes, C. L. V., Martins, F. V. C., Wanner, E. F., & Deb, K. (2021). An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm. In GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion (pp. 185-186). (GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion). ACM. https://doi.org/10.1145/3449726.3459445

Lopes, Claudio L.V. ; Martins, Flávio V.C. ; Wanner, Elizabeth F. et al. / An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm. GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. ACM, 2021. pp. 185-186 (GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion).

@inproceedings{07169cd1eece4100ad1bb82605a29310,

title = "An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm",

abstract = "Dominance move (DoM) is a quality indicator that compares two solution sets in a Pareto-optimal sense. The main issue related to DoM is its computational expense. A recent paper proposed a mixed-integer programming (MIP) approach for computing DoM that exhibited a computational complexity that is linear to the number of objectives and polynomial to the number of solutions. Even with this property, considering practical situations, the MIP-DoM calculation on some problems may take many hours. This paper presents an approximation method to deal with the problem using a cluster-based and divide-and-conquer strategy. Some experiments are tested, showing that the cluster based-algorithm is computationally much faster and makes a small percentage error from the original DoM value.",

keywords = "cluster algorithms, computationally expensive optimization, evolutionary multi-objective optimization, machine learning, multi-objective optimization",

author = "Lopes, {Claudio L.V.} and Martins, {Fl{\'a}vio V.C.} and Wanner, {Elizabeth F.} and Kalyanmoy Deb",

note = "Publisher Copyright: {\textcopyright} 2021 Owner/Author.; 2021 Genetic and Evolutionary Computation Conference, GECCO 2021 ; Conference date: 10-07-2021 Through 14-07-2021",

year = "2021",

month = jul,

day = "8",

doi = "10.1145/3449726.3459445",

language = "English",

series = "GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion",

publisher = "ACM",

pages = "185--186",

booktitle = "GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion",

address = "United States",

}

Lopes, CLV, Martins, FVC, Wanner, EF & Deb, K 2021, An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm. in GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion, ACM, pp. 185-186, 2021 Genetic and Evolutionary Computation Conference, GECCO 2021, Virtual, Online, France, 10/07/21. https://doi.org/10.1145/3449726.3459445

An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm. / Lopes, Claudio L.V.; Martins, Flávio V.C.; Wanner, Elizabeth F. et al.
GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. ACM, 2021. p. 185-186 (GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion).

Research output: Chapter in Book/Published conference output › Conference publication

TY - GEN

T1 - An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm

AU - Lopes, Claudio L.V.

AU - Martins, Flávio V.C.

AU - Wanner, Elizabeth F.

AU - Deb, Kalyanmoy

PY - 2021/7/8

Y1 - 2021/7/8

N2 - Dominance move (DoM) is a quality indicator that compares two solution sets in a Pareto-optimal sense. The main issue related to DoM is its computational expense. A recent paper proposed a mixed-integer programming (MIP) approach for computing DoM that exhibited a computational complexity that is linear to the number of objectives and polynomial to the number of solutions. Even with this property, considering practical situations, the MIP-DoM calculation on some problems may take many hours. This paper presents an approximation method to deal with the problem using a cluster-based and divide-and-conquer strategy. Some experiments are tested, showing that the cluster based-algorithm is computationally much faster and makes a small percentage error from the original DoM value.

AB - Dominance move (DoM) is a quality indicator that compares two solution sets in a Pareto-optimal sense. The main issue related to DoM is its computational expense. A recent paper proposed a mixed-integer programming (MIP) approach for computing DoM that exhibited a computational complexity that is linear to the number of objectives and polynomial to the number of solutions. Even with this property, considering practical situations, the MIP-DoM calculation on some problems may take many hours. This paper presents an approximation method to deal with the problem using a cluster-based and divide-and-conquer strategy. Some experiments are tested, showing that the cluster based-algorithm is computationally much faster and makes a small percentage error from the original DoM value.

KW - cluster algorithms

KW - computationally expensive optimization

KW - evolutionary multi-objective optimization

KW - machine learning

KW - multi-objective optimization

UR - https://dl.acm.org/doi/10.1145/3449726.3459445

UR - http://www.scopus.com/inward/record.url?scp=85111030063&partnerID=8YFLogxK

U2 - 10.1145/3449726.3459445

DO - 10.1145/3449726.3459445

M3 - Conference publication

AN - SCOPUS:85111030063

T3 - GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

SP - 185

EP - 186

BT - GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion

PB - ACM

T2 - 2021 Genetic and Evolutionary Computation Conference, GECCO 2021

Y2 - 10 July 2021 through 14 July 2021

ER -

Lopes CLV, Martins FVC, Wanner EF, Deb K. An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm. In GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion. ACM. 2021. p. 185-186. (GECCO 2021 Companion - Proceedings of the 2021 Genetic and Evolutionary Computation Conference Companion). doi: 10.1145/3449726.3459445

An approximate MIP-DoM calculation for multi-objective optimization using affinity propagation clustering algorithm

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this