第一篇进化优化引论
第 1章绪论
你且问走兽,走兽必指教你；又问空中的飞鸟 ,飞鸟必告诉你；或与地说话 ,地必指教你,海中的鱼也必向你说明.约伯记 12:7-9
本书讨论求解优化问题的方法 .特别地 ,我们 1讨论用于优化的进化算法 .本书包括一些数学理论,但不应该把它看成是数学课本.它更多的是一本关于工程或应用于计算机科学的书.本书中所有优化方法都为了最终能用软件实现.本书旨在以最清楚但又严格的方式介绍进化优化算法 ,同时为读者提供足够先进的材料和参考文献 ,让他们准备好为进化算法添砖加瓦.
本章概览
本章在 1.1节概述本书用到的术语 .在 19页的缩写词表可能对读者有用 . 1.2节说明我为何决定撰写这本关于进化算法的书 ,希望它能达到的目标 ,以及与已有的进化算法专著的不同之处 . 1.3节讨论读者需要先修的课程 . 1.4节讨论布置习题的理念 ,以及如何得到习题答案 . 1.5节总结本书用到的数学符号 .读者在遇到不熟悉的符号时要记得回到这一节 ,在写家庭作业和做研究时也会用到这一节 . 1.6节概述本书 . 1.7节为采用本书开课的教师提供了一些重要的忠告 .这一节还就各章的重要性为教师提出了一些建议.
1.1术语
一些作者称进化算法为进化计算 .这样能强调进化算法需要在计算机上实施 .但进化计算也可能指不用于优化的算法 ;例如 ,最初的遗传算法并不是用于优化本身 ,而是想用来研究自然选择的过程 (参见第 3章).本书针对的是进化优化算法 ,它比进化计算更具体.
另外一些人称进化算法为基于种群的优化 .它强调进化算法一般是让问题的候选解种群随着时间的进化以得到问题的更好的解.然而,许多进化算法每次迭代只有单个候选
1本书采用常见的做法 ,我们这个词一般代指第三人 .有时候也用我们代指读者和作者 .在其他时候 ,我们代表在进化算法和优化领域里的教师和研究人员 .由上下文可以清楚区分其具体含义 .对我们这个词的使用无须过分解读 ;它只是一种书写风格并非要显示权威 .
4第 1章绪论
解 (例如 ,爬山法和进化策略 ).进化算法比基于种群的优化更一般化 ,因为进化算法还包括单一个体的算法.
一些作者称进化算法为计算机智能或计算智能 .这样做常常是为了区分进化算法与专家系统 ,在传统上专家系统一直被称为人工智能 .专家系统模仿演绎推理 ,进化算法则模仿归纳推理 .进化算法有时候也被看成是人工智能的一种 .计算机智能是比进化算法更一般的词 ,它包括像神经网络、模糊系统 ,以及人工生命这样的一些技术 .这些技术可应用于优化之外的问题 .所以 ,从不同的角度看 ,进化算法可能比计算机智能更一般化或更具体.
软计算是与进化算法有关的另一个词 .软计算与硬计算相对 .硬计算指的是准确的、精确的、数值上严格的计算 .软计算指的是不太准确的计算 ,比如人们在日常生活中的表现.软计算的算法针对那些困难的、带噪声的、多峰的和多目标的问题 ,计算出总体上还不错 (但不准确)的解.所以,进化算法是软计算的一个子集.
其他作者称进化算法为由自然启发的计算或仿生计算 .像差分进化和分布估计算法这些进化算法可能并非源于自然 .像进化策略和反向学习这些进化算法与自然过程联系甚微.进化算法比由自然启发的算法更一般化,因为进化算法包括非仿生算法.
进化算法还常常被称为机器学习.机器学习研究由经验学到的计算机算法.但这个领域经常包括很多不是进化算法的算法 .一般认为机器学习比进化算法更广 ,包括强化学习、神经网络、分簇、支持向量机以及其他方法 .
一些作者喜欢将进化算法称为启发式算法 .启发式来自 ηνρισκω这个希腊文的单词,在英语中它译作 eurisko.这个词的意思是找到 (.nd)或发现 (discovery).英语中的感叹词 eureka也来自这个词 ,当我们有新的发现或解决了一个问题时 ,用eureka来表示胜利 .启发式算法是利用经验法则或常识来解决问题的方法 .我们通常不会期望启发式算法能找到问题的最好答案 ,只会期望它能找到与最优解“足够接近”的解 .元启发式这个词被用来描述一系列启发式算法 .本书讨论的进化算法 ,如果不是全部 ,其中的绝大多数也都可以用不同方式在许多不同的选项和参数下实施 .所以 ,它们都可以称为元启发式 .例如 ,所有蚁群优化的一系列算法就可以称为蚁群元启发式.
大多数作者把进化算法与群智能算法区别开来 .群智能算法以自然中的群 (例如 ,蚁群或鸟群 )为基础 .蚁群优化 (第 10章)和粒子群优化 (第 11章)是两个突出的群智能算法 ,许多研究人员坚持认为它们不应该被归为进化算法 .一些作者则认为群智能算法是进化算法的一个子集 .例如 ,粒子群优化的一位发明者将它称为进化算法 [Shi and Eberhart, 1999].因为群智能算法与进化算法有相同的执行方式 ,即,每次迭代都改进问题的候选解的性能从而让解的种群进化 ,因此我们认为群智能算法是一种进化算法.
虽然术语不够确切且与上下文相关 ,但在本书中进化算法指的是经过多次迭代让问题的解进化的算法 .按照进化算法的生物学基础 ,它的一次迭代通常被称为代.不过进化算法的这个简单定义并不完美 ,举例来说 ,这个定义暗示梯度下降法也是一个进化算法 ,但没有谁会认可这个说法 .所以 ,在进化算法领域中术语的不统一会让人困惑 .一个算法是进化算法如果它通常被认为是进化算法 ,我们采用这个戏谑的定义 .这个循环定义一开
1.3先修课程 5
始有些麻烦 ,但一段时间之后 ,像我们这样在这个领域工作的人就习惯了 .自然选择被定义为适者生存,而适者被定义为最有可能的存活者.
1.2又一本关于进化算法的书
关于进化算法已有许多好书 ,这就提出了一个问题 :为什么又要写一本关于进化算法的书呢 ?撰写本书的原因是想提供一种教学的方法、观点和素材 ,其他书都没有这些内容.特别地,作者希望本书能够提供:
. 一种直截了当自下而上的方法 ,它能协助读者清楚理解书中讲述的进化算法 ,这种理解在理论上也是严格的 .许多书在讨论进化算法的变种时像菜谱一样完全没有理论上的支撑 .其他书读起来更像研究专著而不是课本 ,学工程的普通学生不能完全理解 .本书尝试通过易于实现的算法 ,连同一些严格的理论以及有关折中的讨论来获得一个平衡.
. 书中的简单例子让读者能够直观地理解进化算法的数学、方程和理论 .很多书介绍进化算法的理论 ,然后给出的例子或问题却并不适合直观理解 .其实 ,完全有可能给出一些只需要纸和笔就能求解的简单例子和问题 .这些简单的问题能让学生更直接地看到理论在实践中的作用.
.从作者的网址 1能得到书中所有例子的基于 MATLAB.的源代码 .别的课本也提供源代码 ,但它们常常不完整或已经过时 ,这会令读者困惑 .那个网址上还有作者的电邮地址 ,作者热烈欢迎读者的反馈、评论、改进意见和纠错 .当然 ,网页地址会过时 ,本书中算法的伪代码清单比任何具体的软件清单更长久 .注意 ,书中的例子和 MATLAB代码并不是高效的或有竞争力的优化算法 ;只是为了让读者理解算法的基本概念.严肃的研究或应用应该只在最初的时候依赖样本代码.
. 本书包括在大多数课本中没有的理论以及最近开发的进化算法 .它们包括进化算法的马尔可夫理论模型、进化算法的动态系统模型、人工蜂群算法、基于生物地理学的优化、反向学习、人工鱼群算法、混合蛙跳、细菌觅食优化和其他算法 .这些主题是对现状的补充 ,把它们放入书中不是想要与其他书一分高下 .不过 ,本书也不是要调查有关进化算法研究的各方面现状 .本书旨在就进化算法研究的许多领域做一个高层次的概述以帮助读者全面理解进化算法 ,并让读者对现状有一个良好的定位以便从事进一步的研究.
……
