如何求解问题——现代启发式方法

　　 通过一系列贯穿于章节间的有趣难题，本书深入浅出地阐述了如何利用计算机来求解问题的一些现代启发式方法。
　　 全书包括两部分，共分15章。第1章指出了造成问题求解困难的主要原因。第2章简要介绍了一些基本概念。第3章和第4章综述了传统的优化算法，包括穷举搜索法、局部搜索法、贪婪法、分而治之法、动态规划法和分枝定界法等。第5章阐明了两种现代搜索算法，即模拟退火法和禁忌搜索法。以上各章构成了本书的第—部分。书中第二部分主要阐述求解问题的演化方法。第6章和第7章介绍了设计一般演化算法的细节问题。第8章至第10章分别对于TSP问题、约束处理问题以及如何调整算法等问题详细综述了如何采用演化方法来求解这些问题所作的大量努力。第11章讨论了随时间变化的环境和噪声问题。第12章和第13章分别提供了神经网络和模糊系统的有关内容。第14章对混合系统和扩展演化算法作了简短的一般性讨论。最后第15章总结了全书的内容并给出了在实际求解问题时部分有价值的提示。
　　 本书是一本学习如何通过现代启发式方法利用计算机来求解问题的教材，读者对象是高等学校理工科和经济管理专业的广大师生。同时本书丰富的文献综述对于从事计算机特定领域(如算法设计、演化计算、工程优化、神经网络、模糊系统等)研究的科技人员也具有很大的参考价值。
　　

i 我的三个小孩的年龄有多大?
1 为何有些问题难以求解?
1．1 搜索空间的大小
1．2 给问题建模
1．3 随时间而变化
1．4 约束
1．5 证明问题
1．6 你辉煌成就的机会
1．7 小结
li 一个模型有多重要?
2 基本概念
2．1 表示方式
2．2 目标
2．3 评估函数
2．4 定义一个搜索问题
2．5 邻域和局部最优解
2．6 爬山法
2．7 你会落入这种圈套吗?
2．8 小结

　　 在用纸和笔进行手工求解问题的时代，Polya的《How to Solve It》一书(1945年出版)曾经是一本为人们提供了如何用数学方法来求解问题的百科全书，它的出版获得了极大的成功，被翻译成17种语言并多次出版。而在计算机技术已迅猛发展的今天，许多实际问题的解答不再是用笔和纸所能计算的了。相反，我们必须采用一些计算机算法进行数值逼近和扩展问题的范围，这样才能求得这些问题的有用的答案。因此人们迫切需要一种改进的问题求解方法。本书正是顺应时代发展的要求，通过一系列贯穿于章节间的有趣难题，深入浅出地阐述了在21世纪如何利用计算机来求解问题的一些现代启发式方法。这些方法是Polya的专著中不可能涉及的，但对于人们求解一些实际问题却极其有效。
　　 我们一直与本书的第一作者美国北卡罗来纳大学的Zbigniew．Michalewicz教授保持着良好的合作关系，这本书的原版是他在组织并参加2000年在武汉大学举办的演化计算国际研讨会时带来的。我们发现任何理工科和经济管理专业的大学师生阅读此书后都会有所收获，不但可以从中学习到一些利用计算机求解问题的启发式方法，同时对于培养自己求解问题的创造性思维和基本技能也大有稗益。现在我们将本书推荐给广大读者，希望您能从中受益。并且，我们极力鼓励您在了解本书内容的同时，亲自动手编程去尝试和实践书中的难题以及附录B所提供的一些问题与项目，这样做收获会更大。
　　 本书的序言和第5章至第8章由曹宏庆翻译，第1章至第4章由李艳翻译，第9章至第11章由董红斌翻译，第12章至第15章以及附录A和附录B由吴志健翻译。书中所有插图的翻译及处理工作由吴志健和喻敬贤完成。我们对此书的翻译一直抱着认真和严谨的态度，对于在翻译过程中发现的原文中的一些错误和不解之处，都与作者通过电子邮件进行了反复的交流与讨论，校出了原文中20多处小错误，并结合作者提供的勘误表对原著中的其他错误进行了改正。本书由曹宏庆负责统稿和校正工作，最后由康立山教授审校定稿。此外，覃俊、邹秀芬、康卓、田琳、蒋华、何峰、周爱民、杨辉、闫震宇、付朋辉等老师和同学在阅读初稿的过程中提出了许多宝贵的修改意见，章毓文老师翻译了书中的谚语，在此一并表示感谢。最后，衷心感谢王国顺教授在为我们联系中国水利水电出版杜的过程中所给予的热心帮助。
　　 由于我们的水平有限，译文中不确与谬误之处在所难免，谨请读者批评指正。
　　 译者
　　 2002年9月于武汉
　　 译者通讯处：武汉大学软件工程国家重点实验室 邮编430072
　　 Email：jxyu＠whu．edu．cn (曹宏庆)
　　 llyyan2000＠21cn．com (李艳)
　　 hbdong@whu．edu．cn(董红斌)
　　 zjwu＠public．wh．hb．cn (吴志健)
　　

　　 很荣幸我能为本书的中文版写一个特别的序言。第一，这本书是由武汉大学软件工程国家重点宰验室演化计算研究室的成员翻译的。我曾多次到那里访问，访问中我结识了一些了不起的人物，参观了武汉的一些宏伟的名胜古迹，我与研究室之间建立了持续合作，并联合发表了一些论文。第二，这项工作是在我亲密的朋友康立山教授与曹宏庆博士的领导下完成。第三，我很高兴地看到中国读者能读到我早期研究成果的后续(我的前一本书： ‘
　　 Genetic Algorithms+Data Structures＝Evolution Programs已译成中文《演化程序——遗传算法与数据编码的结合》由科学出版社于2000年出版了)。在这本书里，我试图以更广阔的眼界来看待我所喜爱的主题——演化算法。一方面，我试图将这些算法置于其他的一些启发式方法(例如蚁族系统或模拟退火)和运筹学方法(例如线性规划)的框架之中；另一方面，我也试图以一种问题求解活动的一般的前因后果关系来描述它们。这就是为什么这本书包含我30多年来收集的许多有趣而又不同寻常的难题的原因。这些难题揭示了书中的一些观点。总之，本书最重要的一点是，一个人在求解问题时，既要广泛了解一些可用的工具和算法，同时也应掌握一些求解问题的技巧(这与其说是一门科学，不如说更是一门艺术)。
　　 我很希望中国读者会对这本书感兴趣。如果是这样的话，我可以承诺另一本书的出版(从现在算起可能是两年后的事)——一本描述将这些现代启发式方法应用于解决世界上一些最大公司的各种复杂问题的实例研究的书。我正在应用《如何求解问题——现代启发式方法》这本书中的一些基本原理来设计和实现几个复杂的系统。我几乎迫不及待地想
　　 报道这些结果了……
　　 祝各位读者好！
　　 Gyorgy Polya的《如何求解问题》(英文名：《How to Solve lt》)[287]一书被公认为是20世纪关于问题求解的最具贡献的重要文献之一。即使现在，当我们即将跨入新千年之际，这本书仍因其具有指导性的启发式思想而受广大师生所喜爱。此书的第一版面世于1945年，即第二次世界大战末和晶体管问世的前几年。这本书的出版很快获得了成功并在1957年又出了第二版。
　　 《如何求解问题》是一本关于如何用数学方法来解决问题的一些方法的总纲要。也就是说，此书不仅提供了一些技术和过程的具体实例，并且还在如何进行类比、如何使用辅助设备以及如何从求解目标到已知条件逆向地思考问题等方面提出了许多指导性意见。
　　 实质上而言，这是一部关于如何手工求解问题的百科全书，并且更重要的是它是一本关于如何建立问题和解决问题的论著。
　　 目前关于启发式求解问题的大多数文献对每种经典算法都提供了算法过程的详细描述。但遗憾的是，它们未能适当地指导人们何时可以使用这些算法，以及更重要地——何时不该使用这些算法。它们往往只提供了一本菜谱，而把决定某种特定方法是否适用于求解手边的问题的任务留给了读者。而读者通常对此毫无准备，既不知道其中可能涉及的有关问题，也不知道确实应该考虑的问题。
　　 这一状况无疑是计算机革命的必然结果。如果说是某个事件促使Polya的书出现后近50年的今天，人们迫切需要一种改进的问题求解方法的话，那就是廉价的功能强大的台式计算机的出现。许多实际的挑战性问题的解答不再是用笔和纸所能计算的了。我们通过采用计算机算法进行数值逼近和扩展问题的范围，可以求得这些问题的有用的答案。由于计算机如此高效，解题者总是试图去“塑造”(hack)一个解，或者至少看起来像是一个
　　解，而对该程序所实现的方法所作的一些假设并未给予充分的考虑。
　　 结果，尽管人们已经在医药、国防、工业和金融等领域的性能优化方面取得了巨大进展，但却几乎没有发挥我们成果的潜能。例如，采用线性规划方法代替手工计算和主观推测理应每年可以节省成百亿美元，但是在实际条件下，人们对这种方法总是运用不当。
　　 一些公司和个人总在不断地近乎盲目地急于找到适合问题求解的现成的商品软件，其实它们并不存在。一些过时的其实并不存在的解。你可以想象一下，如果真正合适的方法用于 求解问题，而这些问题远非简单的线性规划方法所能处理的话，那会节省甚至赚多少钱啊!
　　 随着世界的发展正越来越面向自由开放的市场，竞争就日益成为寻求更有效的求解问题方法的一种驱动力。达尔文的变化—选择法则与自由市场动力学之间存在着一个贴切的类比。不能获取所需资源的实业将宣告破产，经济上就等同于自然界的“适者生存、不适者被淘汰”。他们所需的就是略微胜过其竞争对手而使其停业，只有那些努力采用现代启发式方法去解决他们的问题而受益的个人、企业和代理商将能得以幸存。
　　 现在有必要对Polya的著作进行两方面的更新。首先，读者必须学习一些已有的特殊的技术，主要是一些计算机算法的应用；其次，读者必须懂得每种方法何时可以使用和何时不能使用以及如何构建自己的问题，以便能最好地应用一些启发式方法，而这些方法是Polya的专著——《如何求解问题》中所没有预料到的。
　　 本书首次尝试为21世纪提供有关问题求解方法的一本综述。书中的主要观点都是通过直接的说明、类比、示例以及一系列贯穿于论述和章节间的问题和难题来表述的。本书旨在提供一本有关现代启发式方法的教材。我们相信这样的一门课程对于理学、商学或工学领域的学生都是必需的。在阅读此书之前要求读者具备离散数学的一些基础知识并熟悉计算机编程。不具备这些基本技能的读者应该花些时间去获取它们，这样做是值得的。而那些希望对算法的数学背景有更深入了解的读者会发现这本书里的材料是一块通向更高级课程的有用的踏脚石。
　　 全书共分15章。首先从引言开始，我们对求解问题作了一般性的讨论。第1章指出了造成问题求解困难的主要根源。第2章简短地介绍了一些基本概念。第3章和第4章综述了一些经典的优化算法。第5章阐明了两种现代搜索算法。以上各章构成了本书的第一部分。继而我们转向求解问题的一种演化方法。第6章和第7章介绍了直觉和设计演化算法的一些细节。第8至第10章对于要求寻找项的特定排列、如何处理约束以及如何调整算法使适合于求解任务这些问题提出了一些挑战性观点。这些章节详细综述了人们在这些领域所作的诸多努力。第11章讨论了随时间变化的环境和噪声问题。按下来的两章(第12章和第13章)提供了关于神经网络和模糊系统的指南。第14章对混合系统和扩展演化算法作了简短的一般性讨论。第15章总结了全书的内容并给出了在实际求解问题时的一些有用提示。你会注意到在每一章(1，2等等)的前面都用一个相关难题的小节(1，量等等)举例说明即将阐明的观点——因为问题的求解应该具有趣味性。我们希望这种方式能使本书更加引人入胜。
　　 本书除了以上的主要内容外，还有两个补充信息的附录。附录A提供了概率论和统计学中一些基本概念，从概率的公理一直到统计的假设检验和线性回归。这一附录并不旨在提供随机过程的预备知识，而是为了阐明将概率论和统计学应用于问题求解时的一些重要观点。附录B列出了将本书用作大学课程的部分内容时建议采用的求解的问题和项目。
　　 即使你在阅读本书时缺乏一位老师的指导，我们也强烈地鼓励你在问题的求解中采取积极主动的态度，自己动手去实现、测试并应用你在这里所学的概念。附录B的内容可以充当这些应用的向导。
　　 我们感谢所有在这本书上花费了时间并与我们分享他们的思想的人们——这些思想是很有帮助的。特别地，我们要感谢Dan Ashlock，Ole Caprani，Tom English，Larry Fogel，Larry Hall，Jim Keller, Kenneth Keutz—Delgado，Martin Schmidt和Thomas Stidsen。我们还要感谢 Kumar Chellapilla，他不仅审阅了本书的章节，并且还对书中一些插图的绘制给予了重要帮助。我们也诚挚地感谢在过去的两年里一些合作者们的帮助，其中许多合作的成果包含在本书中。这些合作者包括Thomas Back，曹宏庆，Ole Caprani，Dipankar Dasgupta，Kalyan Deb，Gusz Eiben，Susana Esquivel，Raul Gallerd，Ozdemir GOl，Robert Hinterding，Slawomir Koziel，康立山，Moutaz Khouja，Witold Kosinski，Thiemo Krink,Guillermo LeguizamOn，