DC FieldValueLanguage
dc.contributor.authorMaksimović, Zoranen
dc.contributor.authorKratica, Jozefen
dc.contributor.authorSavić, Aleksandaren
dc.date.accessioned2020-04-26T19:14:50Z-
dc.date.available2020-04-26T19:14:50Z-
dc.date.issued2017-11-01en
dc.identifier.issn1432-7643en
dc.identifier.urihttp://researchrepository.mi.sanu.ac.rs/handle/123456789/472-
dc.description.abstractIn this paper, a connected multidimensional maximum bisection problem is considered. This problem is a generalization of a standard NP-hard maximum bisection problem, where each graph edge has a vector of weights and induced subgraphs must be connected. We propose two metaheuristic approaches, a genetic algorithm (GA) and an electromagnetism-like metaheuristic (EM). The GA uses modified integer encoding of individuals, which enhances the search process and enables usage of standard genetic operators. The EM, besides standard attraction–repulsion mechanism, is extended with a scaling procedure, which additionally moves EM points closer to local optima. A specially constructed penalty function, used for both approaches, is performed as a practical technique for temporarily including infeasible solutions into the search process. Both GA and EM use the same local search procedure based on 1-swap improvements. Computational results were obtained on instances from literature with up to 500 vertices and 60,000 edges. EM reaches all known optimal solutions on small-size instances, while GA reaches all known optimal solutions except for one case. Both proposed methods give results on medium-size and large-scale instances, which are out of reach for exact methods.en
dc.publisherSpringer Link-
dc.relationGraph theory and mathematical programming with applications in chemistry and computer science-
dc.relationMathematical Modelas and Optimization Methods on Large-Scale Systems-
dc.relation.ispartofSoft Computingen
dc.subjectCombinatorial optimization | Electromagnetism-like approach | Evolutionary computation | Genetic algorithms | Graph bisectionen
dc.titleTwo metaheuristics for solving the connected multidimensional maximum bisection problemen
dc.typeArticleen
dc.identifier.doi10.1007/s00500-016-2203-1en
dc.identifier.scopus2-s2.0-84973154850en
dc.relation.firstpage6453en
dc.relation.lastpage6469en
dc.relation.issue21en
dc.relation.volume21en
dc.description.rankM22-
item.cerifentitytypePublications-
item.openairetypeArticle-
item.fulltextNo Fulltext-
item.grantfulltextnone-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
crisitem.author.orcid0000-0002-9752-0971-
crisitem.project.projectURLhttp://www.mi.sanu.ac.rs/novi_sajt/research/projects/174033e.php-
crisitem.project.projectURLhttp://www.mi.sanu.ac.rs/novi_sajt/research/projects/174010e.php-
crisitem.project.fundingProgramDirectorate for Computer & Information Science & Engineering-
crisitem.project.fundingProgramDirectorate for Engineering-
crisitem.project.openAireinfo:eu-repo/grantAgreement/NSF/Directorate for Computer & Information Science & Engineering/1740333-
crisitem.project.openAireinfo:eu-repo/grantAgreement/NSF/Directorate for Engineering/1740103-
Show simple item record

SCOPUSTM   
Citations

1
checked on Jul 12, 2024

Page view(s)

80
checked on May 9, 2024

Google ScholarTM

Check

Altmetric

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.