期刊
EVOLUTIONARY COMPUTATION
卷 19, 期 4, 页码 597-637出版社
MIT PRESS
DOI: 10.1162/EVCO_a_00039
关键词
Elementary landscape; fitness landscape; combinatorial optimization; decomposition methodology
资金
- Spanish Ministry of Science and Innovation
- FEDER [TIN2008-06491-C04-01]
- Andalusian government [P07-TIC-03044]
- Air Force Office of Scientific Research, Air Force Materiel Command, USAF [FA9550-08-1-0422]
A small number of combinatorial optimization problems have search spaces that correspond to elementary landscapes, where the objective function f is an eigenfunction of the Laplacian that describes the neighborhood structure of the search space. Many problems are not elementary; however, the objective function of a combinatorial optimization problem can always be expressed as a superposition of multiple elementary landscapes if the underlying neighborhood used is symmetric. This paper presents theoretical results that provide the foundation for algebraic methods that can be used to decompose the objective function of an arbitrary combinatorial optimization problem into a sum of subfunctions, where each subfunction is an elementary landscape. Many steps of this process can be automated, and indeed a software tool could be developed that assists the researcher in finding a landscape decomposition. This methodology is then used to show that the subset sum problem is a superposition of two elementary landscapes, and to show that the quadratic assignment problem is a superposition of three elementary landscapes.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据