第1章 绪论

1.1 引言

在工程、科学、经济和社会等众多领域中，存在着系统控制、机械设计、经济模型、生产调度、故障诊断、计算机工程等大量最优化问题。这些最优化问题按不同的规则可分为不同的类型，如按有无约束条件可分为无约束优化和约束优化；按变量的性质可分为离散优化和连续优化；按目标函数的个数可分为单目标优化和多目标优化；按函数和约束条件的性质可分为线性优化和非线性优化等[1]。为了达到最优化的目的，通常需要针对具体的实际问题建立相应的最优化模型，再根据模型的具体形式和特性选择适当的方法进行求解，这些求解最优化问题的方法称为最优化方法。近年来计算机技术和互联网技术的高速发展，为求解最优化问题提供了强有力的计算工具，使最优化方法得到了空前的发展。目前，最优化方法仍是一门处于迅速发展中的学科[2-5]。

传统最优化方法可分为解析法和迭代法两大类，其中迭代法应用最广泛，常用的有单纯形法、最速下降法、共轭梯度法、黄金分割法等[3]。传统最优化算法具有计算效率高、可靠性强、理论比较成熟等优点；但是通常要求待求解问题有精确的数学模型，对问题的依赖较强，处理非确定性信息的能力较差，并且只能找到问题的局部最优解。这些弱点使传统优化方法在解决许多实际问题时受到了限制[3-7]。现今工程实际和科学计算中的最优化问题通常具有大规模、高度非线性、多峰等特点，其目标函数有的是不连续的甚至不可微的，有的没有明确的数学形式，有的受噪声影响严重，有的具有大量局部最优解[7]。传统最优化方法已经难以满足这些复杂优化问题的求解要求，因此设计高效的最优化技术和最优化方法已成为目前国内外公认的亟待攻克的研究难点[3-8]。

多学科之间的相互渗透和相互促进为该问题的解决提供了新思路。近年来，随着自然学科和计算机学科交叉研究的深入发展，各种随机性（或启发式）最优化算法应运而生，例如进化算法（Evolutionary Algorithm，EA），包括遗传算法（Genetic Algorithm，GA）、进化策略（Evolutionary Strategy，ES）、进化规划（Evolutionary Programming，EP）和遗传程序设计（Genetic Programming，GP）；模拟退火（Simulated Annealing，SA）算法；粒子群优化（Particle Swarm Optimization，PSO）等[7]。这些算法以生物、统计物理、社会行为等背景，以群体为对象并以适应度等为衡量手段，采用概率统计等随机方式产生新群体，从本质上来说是一类具有自适应调节功能的搜索寻优技术，不需要导数信息，对函数的形态没有要求且适用范围广、顽健性强，已成功地用于求解各种复杂最优化问题[7]。其中，进化算法是一类基于进化思想而形成的最具代表性的启发式最优化算法，其自组织、自适应、自学习的特征，优胜劣汰的自然选择和简单的进化操作，使得进化算法不受搜索空间限制条件（如可微、连续、单峰等）的约束且不需要其他辅助信息（如导数），因而具有效率高、简单易操作、通用性强等特点[3-7]。然而，进化算法在求解某些高维多峰复杂最优化问题时易趋于早熟收敛而陷入局部最优解，另外也存在收敛速度慢、计算复杂度高、基础理论不完善等问题。这些缺陷已成为进化算法在实际应用中的瓶颈，亟待解决。

近年来设计高效的进化算法成为众多领域关注的热点，在有关应用数学和计算数学类、优化类、计算机类、工程设计类以及控制类等的国际重要学术期刊中已刊登大量相关论文，同时每年举办的各级别国际会议都涉及进化算法及其应用这一主题。在国内，国家自然科学基金委员会公布的“十五”期间资助的研究领域包括大规模工程和科学计算，鼓励新思想、新算法方面的创新性研究。自2007年至今的项目指南中，数理科学部拟资助的重点项目都涉及仿生优化方法、非线性优化、多目标优化等内容[7]。在此背景下，新兴高效的进化算法不断涌现，差分进化（Differential Evolution，DE）算法就是该领域内目前最具代表性、性能最优的进化算法之一。差分进化算法，又翻译为差异演化算法、差分演化算法或差异进化算法，是美国伯克利大学的Rainer Storn和Kenneth Price于1995年提出的一种基于种群差异的进化算法，具有记忆个体最优解和种群内信息共享的特点，即通过种群内个体间的合作与竞争来实现优化问题的求解，其本质上是一种基于实数编码的具有保优思想的贪婪遗传算法[1, 2]。Rainer Storn和Kenneth Price在其研究报告中称，DE算法在收敛速度和稳定性方面都超越了多种知名的随机优化算法，如退火单纯形（Annealed Nelder and Mead Strategy，ANM）算法、自适应模拟退火（Adaptive Simulated Annealing，ASA）算法、进化策略和随机微分方程（Stochastic Differential Equations，SDE）算法等[6]。J.Vestertron等人曾将DE算法与PSO算法等其他进化算法在34个广泛应用的Benchmark优化问题上进行了深入的比较研究，实验结果表明DE算法的性能优于PSO算法和其他进化算法[9]。目前，DE算法已成为一种公认的求解非线性、不可微、多极值最优化问题有效且顽健的方法，是进化算法领域中的一个重要分支，并在数字信号处理、神经网络优化、模式识别、机器人路径规划等工程领域取得了良好的应用效果[4]。

然而DE算法在实际应用中也存在一些不足之处，如在高维多峰复杂最优化问题上仍然存在易陷入局部最优、后期收敛速度慢、搜索具有一定盲目性、控制参数难以设定等问题。此外，DE算法本身不可直接用于求解多目标优化问题，在一定程度上限制了算法的应用范围[3-8]。国内DE算法的相关研究起步较晚，且大多跟从国外研究方向，不但研究人数少，而且研究成果与国外也存在一定差距，特别是在高维多目标优化方面的研究成果更少。

在此背景下，本书对DE算法的基础理论及实际工程应用进行了深入系统的研究。首先，对算法中的关键步骤进行改进，提升算法在高维多峰复杂最优化问题上的求解性能。其次，将DE算法应用于数字医学PET图像目标边缘提取、电子商务多边多议题协商等前沿新兴领域，在解决实际工程最优化问题的同时进一步扩展DE算法应用范围。再次，针对高维多目标环境下优化问题求解困难的本质原因，围绕影响算法性能的多项关键技术进行综合改进，设计了基于DE的进化多目标优化算法，有效提升10～30维高维复杂多目标优化问题的求解质量。最后，将改进后的高维多目标差分进化算法应用于智能交通系统中的城市智能化动态停车诱导、城市道路交叉口信号智能优化控制等前沿问题，有效解决了实际工程领域中的高维多目标优化问题。以上研究对DE算法的理论发展和实际应用产生了积极的推动作用，因此具有重要的学术意义和工程应用价值。