发帖
雷达卡
摘要翻译：
组合优化在许多领域得到了广泛的应用。不幸的是，许多组合优化问题是NP难问题，这意味着它们在实践中通常是不可解的。然而，往往没有必要有一个精确的解。在这种情况下，人们可以使用启发式方法在合理的时间内获得一个接近最优的解。重点研究了两个组合优化问题，即广义旅行商问题和多维指派问题。第一个问题是旅行商问题的重要推广；第二个是任意维数指派问题的推广。这两个问题都是NP-hard问题，都有大量的应用。在这项工作中，我们讨论了启发式设计和评估的不同方面。本研究涉及测试床的生成和分析、实现和性能问题、局部搜索邻域和有效的搜索算法、元启发式设计和memetic算法中的种群规模等广泛的相关课题。对于所考虑的问题，在局部搜索和模因算法方面得到了最重要的结果。在这两种情况下，我们通过系统化和改进以前的结果，显著地提高了现有的关于局部搜索邻域和算法的知识。我们已经提出了许多有效的启发式算法，这些算法在时间/质量要求的大范围内占据了现有算法的主导地位。在我们的模因算法中引入了几种新的方法，使它们成为解决相应问题的最先进的元启发式。人口规模是这些方法中最有希望的方法之一；它有望适用于几乎任何模因算法。
---
英文标题：
《Design, Evaluation and Analysis of Combinatorial Optimization Heuristic
Algorithms》
---
作者：
Daniel Karapetyan
---
最新提交年份：
2012
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Data Structures and Algorithms 数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science 计算机科学
二级分类：Discrete Mathematics 离散数学
分类描述：Covers combinatorics, graph theory, applications of probability. Roughly includes material in ACM Subject Classes G.2 and G.3.
涵盖组合学，图论，概率论的应用。大致包括ACM学科课程G.2和G.3中的材料。
--
一级分类：Mathematics 数学
二级分类：Optimization and Control 优化与控制
分类描述：Operations research, linear programming, control theory, systems theory, optimal control, game theory
运筹学，线性规划，控制论，系统论，最优控制，博弈论
--
---
英文摘要：
Combinatorial optimization is widely applied in a number of areas nowadays. Unfortunately, many combinatorial optimization problems are NP-hard which usually means that they are unsolvable in practice. However, it is often unnecessary to have an exact solution. In this case one may use heuristic approach to obtain a near-optimal solution in some reasonable time. We focus on two combinatorial optimization problems, namely the Generalized Traveling Salesman Problem and the Multidimensional Assignment Problem. The first problem is an important generalization of the Traveling Salesman Problem; the second one is a generalization of the Assignment Problem for an arbitrary number of dimensions. Both problems are NP-hard and have hosts of applications. In this work, we discuss different aspects of heuristics design and evaluation. A broad spectrum of related subjects, covered in this research, includes test bed generation and analysis, implementation and performance issues, local search neighborhoods and efficient exploration algorithms, metaheuristics design and population sizing in memetic algorithm. The most important results are obtained in the areas of local search and memetic algorithms for the considered problems. In both cases we have significantly advanced the existing knowledge on the local search neighborhoods and algorithms by systematizing and improving the previous results. We have proposed a number of efficient heuristics which dominate the existing algorithms in a wide range of time/quality requirements. Several new approaches, introduced in our memetic algorithms, make them the state-of-the-art metaheuristics for the corresponding problems. Population sizing is one of the most promising among these approaches; it is expected to be applicable to virtually any memetic algorithm.
---
PDF链接：
https://arxiv.org/pdf/1207.1794
京公网安备 11010802022788号
