现代优化计算方法 (2010 年度畅销榜NO.2872 )

本书系统介绍了禁忌搜索、模拟退火、遗传算法、人工神经网络和拉格朗日松弛等现代优化计算方法的模型与理论、应用技术和应用案例。
全书共6章，第1章介绍算法复杂性的基本概念和启发式算法的评价方法，后5章分别介绍各个现代优化计算方法。
本书可作为数学、管理科学、计算机科学、工业工程等学科中相关优化专业的研究生教材，也可供相关专业研究人员参考。

第1章 概论
1. 1 组合最优化问题
1. 2 计算复杂性的概念
1. 3 邻域概念
1. 4 启发式算法
1. 5 NP, NP-C和NP-hard概念
1. 6 小结
练习题
参考文献
第2章 禁忌搜索算法
2. 1 局部搜索
2. 2 禁忌搜索
2. 3 技术问题
2. 4 应用实例
练习题
参考文献
第3章 模拟退火算法
3. 1 模拟退火算法及模型
3. 2 马尔可夫链
3. 3 时齐算法的收敛性
3. 4 非时齐算法收敛性简介
3. 5 实现的技术问题
3. 6 应用案例--下料问题
练习题
参考文献
第4章 遗传算法
4. 1 遗传算法
4. 2 模板理论
4. 3 马尔可夫链收敛分析
4. 4 实现的技术问题
4. 5 遗传模拟退火算法
4. 6 应用案例--生产批量问题
练习题
参考文献
第5章 人工神经网络
5. 1 人工神经网络的基本概念
5. 2 单层前向神经网络
5. 3 多层前向神经网络
5. 4 竞争学习神经网络
5. 5 反馈型神经网络
练习题
参考文献
第6章 拉格朗日松弛算法
6. 1 基于规划论的松弛方法
6. 2 拉格朗日松弛方法的理论
6. 3, 拉格朗日松弛的进一步讨论
6. 4 拉格朗日松弛算法
6. 5 拉格朗日松弛在能力约束单机排序问题中
的应用
练习题
参考文献
索引及英文关键词

最优化是人们在工程技术. 科学研究和经济管理的诸多领域中经常遇到的问题. 结构设计要在满足强度要求等条件下使所用材料的总重量最轻, 资源分配要使各用户利用有限资源产生的总效益最大, 安排运输方案要在满足物资需求和装载条件下使运输总费用最低, 编制生产计划要按照产品工艺流程和顾客需求, 尽量降低人力. 设备. 原材料等成本使总利润最高. 可以预料, 随着科学技术尤其是计算机技术的不断发展, 以及数学理论与方法向各门学科和各个应用领域的更广泛. 更深入的渗透, 在即将到来的21世纪信息时代, 最优化理论和技术必将在社会的诸多方面起着越来越大的作用. 解决实际生活中优化问题的手段大致有以下几种：一是靠经验的积累, 凭主观作判断, 二是做试验选方案, 比优劣定决策, 三是建立数学模型, 求解最优策略. 虽然由于建模时要作适当简化, 可能使结果不一定非常完善, 但是它基于客观数据, 求解问题简便. 灵活. 经济, 而且规模可以很大(将来会越来越大). 人们还可以吸收从经验得到的规则, 用实验来不断校正建立的模型. 随着数学方法和计算机技术的进步, 用建模和数值模拟解决优化问题这一手段, 将会越来越显示出它的效能和威力. 显然, 在决策定量化. 科学化的呼声日益高涨的今天, 数学建模方法的推广应用是符合时代潮流和形势发展需要的. 最优化理论. 模型与方法所包含的内容很多, 国内已出版了不少教材和专著介绍其各个分支. 但是一方面, 近年来发展起来的. 有着广泛应用背景的规划模型(如随机规划. 模糊规划等), 以及一些已经为许多人采用. 受到广泛关注的优化算法(如模拟退火. 遗传算法等), 还缺乏详细和系统的介绍, 另一方面, 一些偏重优化理论和方法的教材, 其要求难以与工科学生的数学知识衔接, 也缺少对于应用来说十分重要的建模过程和软件介绍, 而一些比较通俗的运筹学教材, 则在加强理论基础, 适应学生将来从事科研工作需要上考虑较少. 我们这套教材试图弥补以上两方面的缺陷, 力求体现下述特点： 1. 内容既包含传统的线性规划与非线性规划等部分, 又纳入有广泛应用前景的随机规划和模糊规划, 在传统内容中, 既注重典型的数学思想和方法的系统叙述, 又引入丰富的建模实例. 2. 数学基础既与工科学生所学知识衔接, 又考虑到研究生阅读文献. 从事科研工作的需要, 适当提高理论基础的起点. 3. 对一般教材介绍的诸多算法进行精选, 配合介绍一些应用软件, 并引入近年来迅速发展的若干新算法. 本系列教材将陆续出版, 首批四册为：《线性与非线性规划》. 《网络优化》. 《现代优化计算方法》. 《随机规划与模糊规划》. 由于水平所限, 书中难免有缺陷和错误, 诚恳希望读者予以批评指正. 《最优化基础--模型与方法》系列教材编委会 1998年5月 系列教材编委会成员名单 (姓氏笔划为序) 本书序言 随着20世纪80年代初期禁忌搜索. 模拟退火. 遗传算法和人工神经网络算法的兴起, 科学工作者对这些算法的模型. 理论和应用技术等一系列问题进行着深入的研究, 并将这些算法称为现代优化算法. 现代优化算法的主要应用对象是优化问题中的难解问题, 也就是优化理论中的NP-hard问题. 正是因为很多实际优化问题的难解性, 和现代优化算法在一些优化问题中的成功应用, 使得现代优化算法成为解决优化问题的一种有力工具. 科学工作者对现代优化算法抱以极大的热情和期望, 几乎在各种难解的优化问题中, 他们都尝试这些算法的应用和比较其应用效果. 在国际和国内, 每一种现代优化算法都有相应的专著, 其中有较为详尽的理论和应用论述. 很多科学工作者期望对这些算法有一定的了解, 以在实际应用中有目的地采用. 基于人们的这些期望和关注, 我们将这些算法集于一书, 从简单实例的应用, 到其理论. 应用技术及应用案例的深入分析, 由易到难地向相关优化专业的硕士. 博士研究生介绍现代优化算法的相关模型. 理论. 应用技术和一些应用实例, 在国内, 这可能是首次尝试. 本书也可供科学研究人员在这些领域研究时参考. 我们不希望将现代优化算法中的诸多算法简单地堆集在一起, 而是设法将它们有机地集于一书. 基于这种想法, 本书由6章组成. 第1章介绍了现代优化算法要解决的问题及它们中的共同点, 并将本书各章衔接在一起. 第2章. 第3章. 第4章和第5章分别介绍禁忌搜索算法. 模拟退火算法. 遗传算法和人工神经网络算法, 这些是现代优化算法的组成. 第6章提供评价算法的一种工具：拉格朗日松弛算法. 第1章为概论. 首先介绍现代优化算法所要解决的组合优化问题. 通过复杂性概念的引入, 使得我们知道为什么和在什么情况下将现代优化算法应用到优化问题. 通过邻域和算法评价方法的介绍, 使我们找出现代优化算法的一些共同点. 由于有关复杂性概念的内容不易理解, 因此, 作者在处理这部分内容时, 以多个典型组合优化问题为背景, 通过对它们的一步步分析来介绍复杂性的一个个概念. 为了适应不同层次的读者, 本章将复杂性概念的内容分为1. 2节和1. 5节两部分. 1. 2节介绍了多项式时间可求得最优解的多项式问题. 1. 5节更进一步介绍了NP. NP-complete和NP-hard概念. 对学时要求较少或非运筹学专业学生的教学, 可以略去1. 5节. 将第2, 3, 4, 5这四章的内容作为一个整体, 从最容易理解的局部搜索算法开始, 逐步深入地介绍全局搜索的禁忌搜索算法, 带有随机搜索的模拟退火和遗传算法, 最后, 给出人工神经网络算法. 对学时要求较少或非运筹学专业学生的教学, 可以略去3. 2节. 3. 3节和4. 3节中的证明. 第6章拉格朗日松弛算法使得本书成为一个整体. 我们不仅要学会应用现代优化算法, 还应该学会评价这些算法. 对于极小化目标函数的优化问题, 现代优化算法能给出一个目标值不低于最优目标值的可行解, 当评价一个算法的计算效率时, 可行解目标值同最优目标值一个下界的差是评价的标准之一. 拉格朗日松弛算法则是提供最优目标值下界的工具之一. 对学时要求较少或非运筹学专业学生的教学, 可以参考下图教学内容： 本书是在1997年春季我校研究生"现代最优化算法"课程讲稿的基础上, 经过1998年和1999年两次讲授后整理和扩充而成的. 在此过程中, 研究生们给予了非常有益的建议. 自90年代初期, 姜启源教授和韩继业教授投入了很大的心血, 组织了组合优化问题讨论班并得到国家自然科学基金资助, 这个讨论班和基金资助使我们积累了大量有价值的材料. 在写作的过程中, 香港城市大学的黎建强和林国健教授提供的资料大大丰富了书中的内容. 谭泽光. 胡冠章. 林翠琴. 刘宝碇教授和张家伟同学等阅读并修改了我们的手稿, 给我们提出很多很好的建议. 在此, 对给予我们帮助的老师. 出版社的编辑和同学们表示感谢!对给予我们部分资助的教育部高等学校工科数学教育基地表示感谢!最后, 对我们家人的耐心和支持表示由衷的谢意! 由于我们的水平有限, 恳请读者对本书的不足之处批评指正. 邢文训 谢金星 1999年春于清华园