Compressed representation for higher-level meme space evolution: a case study on big knapsack problems
Compressed representation for higher-level meme space evolution: a case study on big knapsack problems
复制标题
高级模因空间演化的压缩表示：大背包问题的案例研究
DOI：
10.1007/s12293-017-0244-3
复制
发表时间：
2017-10
影响因子：
4.7
通讯作者：
Ong Yew Soon
中科院分区：
文献类型：
--
作者：
Feng Liang;Gupta Abhishek;Ong Yew Soon
在过去的几十年中，人们设计了大量专用启发式和元启发式算法来解决复杂的优化问题。然而，值得注意的是，这些算法中的大多数仅限于中小型实例。在当今世界，随着通信和计算技术的快速发展，每天都会生成和存储大量数据，因此探索可以处理“大”问题的学习和优化技术至关重要。在本文中，我们在上述方向上迈出了重要的一步，提出了一种新颖的、有理论依据的压缩表示，具有用于大优化的高级模因进化。与直接在解决方案空间上工作的现有启发式和元启发式相反，所提出的模因进化在高级模因空间上运行。特别地，以背包问题作为案例研究，在本例中，模因代表知识块作为解决背包问题的指令。由于本文中定义的 meme 大小对底层背包问题中的项目数量并不强烈敏感，因此 meme 空间中的搜索提供了一种压缩形式的优化。为了验证所提出方法的有效性，我们进行了各种数值实验，问题规模从小（100 个项目）到非常大（10,000 个项目）不等。结果为进一步探索提供了强有力的鼓励，以将模因进化建立为大优化的黄金标准。
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.
登录
查看更多内容
影响因子：
4
作者：
Bansal, Jagdish Chand;Deep, Kusum
通讯作者：
Deep, Kusum
DOI：
10.1145/2598394.2605342
发表时间：
2014-07
期刊：
Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation
影响因子：
--
作者：
A. Engelbrecht
通讯作者：
A. Engelbrecht
影响因子：
14.3
作者：
Han, KH;Kim, JH
通讯作者：
Kim, JH
DOI：
10.1016/b978-0-12-409547-2.14581-0
发表时间：
2020
期刊：
Comprehensive Chemometrics
影响因子：
--
作者：
Federico Marini;Beata Walczak
通讯作者：
Federico Marini;Beata Walczak
DOI：
10.1201/9781003206477-5
发表时间：
2021-08
期刊：
Evolutionary Optimization Algorithms
影响因子：
--
作者：
A. Badar
通讯作者：
A. Badar