Compressed representation for higher-level meme space evolution : a case study on big knapsack problems
In the last decades, a plethora of dedicated heuristic and meta-heuristic algorithms have been crafted to solve complex optimization problems. However, it is noted that the majority of these algorithms are restricted to instances of small to medium size only. In today’s world, with the rapid growth...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/151353 |
| _version_ | 1826109599403474944 |
|---|---|
| author | Feng, Liang Gupta, Abhishek Ong, Yew-Soon |
| author2 | School of Computer Science and Engineering |
| author_facet | School of Computer Science and Engineering Feng, Liang Gupta, Abhishek Ong, Yew-Soon |
| author_sort | Feng, Liang |
| collection | NTU |
| description | In the last decades, a plethora of dedicated heuristic and meta-heuristic algorithms have been crafted to solve complex optimization problems. However, it is noted that the majority of these algorithms are restricted to instances of small to medium size only. In today’s world, with the rapid growth in communication and computation technologies, massive volumes of data are generated and stored daily, making it vital to explore learning and optimization techniques that can handle ‘big’ problems. In this paper, we take an important step in the aforementioned direction by proposing a novel, theoretically motivated compressed representation with high-level meme evolution for big optimization. In contrast to existing heuristics and meta-heuristics, which work directly on the solution space, the proposed meme evolution operates on a high-level meme space. In particular, taking knapsack problem as the case study, a meme, in the present case, represents a knowledge-block as an instruction for solving the knapsack problem. Since the size of the meme, as defined in this paper, is not strongly sensitive to the number of items in the underlying knapsack problem, the search in meme space provides a compressed form of optimization. In order to verify the effectiveness of the proposed approach we carry out a variety of numerical experiments with problem sizes ranging from the small (100 items) to the very large (10,000 items). The results provide strong encouragement for further exploration, in order to establish meme evolution as the gold standard in big optimization. |
| first_indexed | 2024-10-01T02:20:53Z |
| format | Journal Article |
| id | ntu-10356/151353 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T02:20:53Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1513532021-06-22T09:57:14Z Compressed representation for higher-level meme space evolution : a case study on big knapsack problems Feng, Liang Gupta, Abhishek Ong, Yew-Soon School of Computer Science and Engineering Data Science and Artificial Intelligence Research Centre Engineering::Computer science and engineering Meme Evolution Big Knapsack Problem In the last decades, a plethora of dedicated heuristic and meta-heuristic algorithms have been crafted to solve complex optimization problems. However, it is noted that the majority of these algorithms are restricted to instances of small to medium size only. In today’s world, with the rapid growth in communication and computation technologies, massive volumes of data are generated and stored daily, making it vital to explore learning and optimization techniques that can handle ‘big’ problems. In this paper, we take an important step in the aforementioned direction by proposing a novel, theoretically motivated compressed representation with high-level meme evolution for big optimization. In contrast to existing heuristics and meta-heuristics, which work directly on the solution space, the proposed meme evolution operates on a high-level meme space. In particular, taking knapsack problem as the case study, a meme, in the present case, represents a knowledge-block as an instruction for solving the knapsack problem. Since the size of the meme, as defined in this paper, is not strongly sensitive to the number of items in the underlying knapsack problem, the search in meme space provides a compressed form of optimization. In order to verify the effectiveness of the proposed approach we carry out a variety of numerical experiments with problem sizes ranging from the small (100 items) to the very large (10,000 items). The results provide strong encouragement for further exploration, in order to establish meme evolution as the gold standard in big optimization. Nanyang Technological University This work is partially supported under the National Natural Science Foundation of China (Grant No. 61603064), the Frontier Interdisciplinary Research Fund for the Central Universities (Grant No. 106112017CDJQJ188828), Chongqing application foundation and research in cuttingedge technologies (cstc2017jcyjAX0319) and the Data Science and Artificial Intelligence Center (DSAIR) at the Nanyang Technological University. 2021-06-22T09:57:14Z 2021-06-22T09:57:14Z 2019 Journal Article Feng, L., Gupta, A. & Ong, Y. (2019). Compressed representation for higher-level meme space evolution : a case study on big knapsack problems. Memetic Computing, 11(1), 3-17. https://dx.doi.org/10.1007/s12293-017-0244-3 1865-9284 0000-0002-8356-7242 https://hdl.handle.net/10356/151353 10.1007/s12293-017-0244-3 2-s2.0-85032657359 1 11 3 17 en Memetic Computing © 2017 Springer-Verlag GmbH Germany. All rights reserved. |
| spellingShingle | Engineering::Computer science and engineering Meme Evolution Big Knapsack Problem Feng, Liang Gupta, Abhishek Ong, Yew-Soon Compressed representation for higher-level meme space evolution : a case study on big knapsack problems |
| title | Compressed representation for higher-level meme space evolution : a case study on big knapsack problems |
| title_full | Compressed representation for higher-level meme space evolution : a case study on big knapsack problems |
| title_fullStr | Compressed representation for higher-level meme space evolution : a case study on big knapsack problems |
| title_full_unstemmed | Compressed representation for higher-level meme space evolution : a case study on big knapsack problems |
| title_short | Compressed representation for higher-level meme space evolution : a case study on big knapsack problems |
| title_sort | compressed representation for higher level meme space evolution a case study on big knapsack problems |
| topic | Engineering::Computer science and engineering Meme Evolution Big Knapsack Problem |
| url | https://hdl.handle.net/10356/151353 |
| work_keys_str_mv | AT fengliang compressedrepresentationforhigherlevelmemespaceevolutionacasestudyonbigknapsackproblems AT guptaabhishek compressedrepresentationforhigherlevelmemespaceevolutionacasestudyonbigknapsackproblems AT ongyewsoon compressedrepresentationforhigherlevelmemespaceevolutionacasestudyonbigknapsackproblems |