A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators
The maximum <i>k</i>-coverage problem (MKCP) is a problem of finding a solution that includes the maximum number of covered rows by selecting <i>k</i> columns from an <i>m</i> <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" disp...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-04-01
|
| Series: | Biomimetics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2313-7673/10/5/274 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850127199448858624 |
|---|---|
| author | Yoon Choi Jingeun Kim Yourim Yoon |
| author_facet | Yoon Choi Jingeun Kim Yourim Yoon |
| author_sort | Yoon Choi |
| collection | DOAJ |
| description | The maximum <i>k</i>-coverage problem (MKCP) is a problem of finding a solution that includes the maximum number of covered rows by selecting <i>k</i> columns from an <i>m</i> <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>×</mo></mrow></semantics></math></inline-formula><i>n</i> matrix of 0s and 1s. This is an NP-hard problem that is difficult to solve in a realistic time; therefore, it cannot be solved with a general deterministic algorithm. In this study, genetic algorithms (GAs), an evolutionary arithmetic technique, were used to solve the MKCP. Genetic algorithms (GAs) are meta-heuristic algorithms that create an initial solution group, select two parent solutions from the solution group, apply crossover and repair operations, and replace the generated offspring with the previous parent solution to move to the next generation. Here, to solve the MKCP with binary and integer encoding, genetic algorithms were designed with various crossover and repair operators, and the results of the proposed algorithms were demonstrated using benchmark data from the OR-library. The performances of the GAs with various crossover and repair operators were also compared for each encoding type through experiments. In binary encoding, the combination of uniform crossover and random repair improved the average objective value by up to 3.24% compared to one-point crossover and random repair across the tested instances. The conservative repair method was not suitable for binary encoding compared to the random repair method. In contrast, in integer encoding, the combination of uniform crossover and conservative repair achieved up to 4.47% better average performance than one-point crossover and conservative repair. The conservative repair method was less suitable with one-point crossover operators than the random repair method, but, with uniform crossover, was better. |
| format | Article |
| id | doaj-art-922548637fb240b9b6fdf1e7a1a42ca1 |
| institution | OA Journals |
| issn | 2313-7673 |
| language | English |
| publishDate | 2025-04-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Biomimetics |
| spelling | doaj-art-922548637fb240b9b6fdf1e7a1a42ca12025-08-20T02:33:43ZengMDPI AGBiomimetics2313-76732025-04-0110527410.3390/biomimetics10050274A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic OperatorsYoon Choi0Jingeun Kim1Yourim Yoon2Department of Computer Science, Yonsei University, 50 Yonsei-ro, Seodaemoon-gu, Seoul 03722, Republic of KoreaDepartment of IT Convergence Engineering, Gachon University, 1342 Seongnam-daero, Sujeong-gu, Seongnam-si 13120, Gyeonggi-do, Republic of KoreaDepartment of Computer Engineering, Gachon University, 1342 Seongnam-daero, Sujeong-gu, Seongnam-si 13120, Gyeonggi-do, Republic of KoreaThe maximum <i>k</i>-coverage problem (MKCP) is a problem of finding a solution that includes the maximum number of covered rows by selecting <i>k</i> columns from an <i>m</i> <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>×</mo></mrow></semantics></math></inline-formula><i>n</i> matrix of 0s and 1s. This is an NP-hard problem that is difficult to solve in a realistic time; therefore, it cannot be solved with a general deterministic algorithm. In this study, genetic algorithms (GAs), an evolutionary arithmetic technique, were used to solve the MKCP. Genetic algorithms (GAs) are meta-heuristic algorithms that create an initial solution group, select two parent solutions from the solution group, apply crossover and repair operations, and replace the generated offspring with the previous parent solution to move to the next generation. Here, to solve the MKCP with binary and integer encoding, genetic algorithms were designed with various crossover and repair operators, and the results of the proposed algorithms were demonstrated using benchmark data from the OR-library. The performances of the GAs with various crossover and repair operators were also compared for each encoding type through experiments. In binary encoding, the combination of uniform crossover and random repair improved the average objective value by up to 3.24% compared to one-point crossover and random repair across the tested instances. The conservative repair method was not suitable for binary encoding compared to the random repair method. In contrast, in integer encoding, the combination of uniform crossover and conservative repair achieved up to 4.47% better average performance than one-point crossover and conservative repair. The conservative repair method was less suitable with one-point crossover operators than the random repair method, but, with uniform crossover, was better.https://www.mdpi.com/2313-7673/10/5/274maximum k-coverage problemgenetic algorithmcombinatorial optimizationbinary encodinginteger encoding |
| spellingShingle | Yoon Choi Jingeun Kim Yourim Yoon A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators Biomimetics maximum k-coverage problem genetic algorithm combinatorial optimization binary encoding integer encoding |
| title | A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators |
| title_full | A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators |
| title_fullStr | A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators |
| title_full_unstemmed | A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators |
| title_short | A Comparison of Binary and Integer Encodings in Genetic Algorithms for the Maximum <i>k</i>-Coverage Problem with Various Genetic Operators |
| title_sort | comparison of binary and integer encodings in genetic algorithms for the maximum i k i coverage problem with various genetic operators |
| topic | maximum k-coverage problem genetic algorithm combinatorial optimization binary encoding integer encoding |
| url | https://www.mdpi.com/2313-7673/10/5/274 |
| work_keys_str_mv | AT yoonchoi acomparisonofbinaryandintegerencodingsingeneticalgorithmsforthemaximumikicoverageproblemwithvariousgeneticoperators AT jingeunkim acomparisonofbinaryandintegerencodingsingeneticalgorithmsforthemaximumikicoverageproblemwithvariousgeneticoperators AT yourimyoon acomparisonofbinaryandintegerencodingsingeneticalgorithmsforthemaximumikicoverageproblemwithvariousgeneticoperators AT yoonchoi comparisonofbinaryandintegerencodingsingeneticalgorithmsforthemaximumikicoverageproblemwithvariousgeneticoperators AT jingeunkim comparisonofbinaryandintegerencodingsingeneticalgorithmsforthemaximumikicoverageproblemwithvariousgeneticoperators AT yourimyoon comparisonofbinaryandintegerencodingsingeneticalgorithmsforthemaximumikicoverageproblemwithvariousgeneticoperators |