基于状态转移的组合优化方法
2010-8
西安交通大学出版社
王正元
259
无
随着社会发展，出现了大量组合优化问题，如资源配置、生产调度、VLSI技术、指挥控制等，迫切需要对这些问题进行快速、高效地求解。一般情况下，由于组合优化问题的可行解的数量随问题规模增大呈指数增长趋势，难以用较短时间精确求解较大规模的组合优化问题，人们只好采用简单的启发式方法获得问题的近似解，如贪婪算法、局部搜索方法等，这些简单的启发式方法对改进解的质量影响有限。从20世纪80年代开始，人们对现有方法存在的不足进行分析，并借鉴自然界的相关规律，陆续提出了一些新的优化算法，如模拟退火、禁忌搜索、遗传算法、神经网络、粒子群算法和蚁群算法等。这些方法的共同目标是减少搜索量、提高搜索效率。为达到这一目标，不同方法从各个角度完善搜索策略，希望能够得到最优解。依据“没有免费的午餐”定理，为了得到更好的解，就得付出更大的代价。如导引式局部搜索方法，求解时随着近似解的改进修改目标函数，使用同一种搜索方法就能得到更好的近似解，但是计算量成倍增加。如果利用问题的领域知识，可以设计更加快速高效的算法。如Pisinger等人提出了某些条件下0／1背包问题的快速精确求解方法，可以在很短的时间内获得问题的最优解；改进的I。in-Kernighan方法可以快速求取旅行推销员问题高质量的近似解。因此，怎样利用问题的领域知识设计更加有效的算法是组合优化方法研究的重点。
本书介绍了优化方法的相关概念、函数优化方法和启发式组合优化方法，重点阐述了基于状态转移的组合优化方法，并介绍了使用基于状态转移的组合优化方法研究0／1背包问题、加工排序问题、旅行推销员问题以及武器一目标分配问题求解方法的成果。 本书可作为优化技术相关专业高年级本科生、研究生的教学、辅导用书，也可作为相关科研工作者和技术人员的参考书。
前言第1章 概述 1.1 最优化问题及其分类 1.1.1 函数优化问题 1.1.2 组合优化问题 1.2 优化方法 1.3 邻域、计算复杂性与NP 1.3.1 邻域 1.3.2 计算复杂性 1.3.3 P、NP、NP-hard与NPC 1.4 近似求解方法及其评价 1.4.1 近似求解方法 1.4.2 基于目标函数值的评价方法 1.4.3 基于计算时间的评价方法 1.4.4 近似方法的综合评价第2章 函数优化方法第3章 组合优化方法第4章 基于状态转移的组合优化方法第5章 同顺序加工调度问题的求解方法第6章 0/1背包问题的精确求解方法第7章 旅行推销员问题求解方法第8章 武器-目标分配问题求解方法参考文献
插图：采用计算实例的方法评价近似方法时，我们不可能穷尽所有可能的实例，只能选择部分实例。怎样去选择（或者构造）测试算法的实例呢？为了使得测试评价结果更具有可信性，一般使用近似方法计算一些基准问题（Benchmark），通过求取的基准问题的解来反映近似方法的优劣。另外一种构造实例的方法是随机生成实例的方法，即按照一定的分布规律随机产生实例的数据。有时候使用某些近似方法求解一些问题时，发现求解比较困难，分析发现这是由于实例中数据间存在的特定关系引起的。为了使得生成的实例较好地反映出这一点（即具有代表性），选择多种不同概率分布函数作为实例数据服从的概率分布函数
《基于状态转移的组合优化方法》是由西安交通大学出版社出版的。
无