第1章 绪论

1.1 最优化问题的研究意义

最优化问题与方法研究源于运筹学（Operational Research），学者们称它为数学规划（Mathematical Programming），是运筹学的主要分支之一[1]。在处理实际问题的时候，往往会遇到存在多个解的情况，如何根据问题本身的特点选择出一个最优或者次最优解，这是科学领域的最优化问题。本章将从单目标最优化问题、多目标优化问题、约束优化问题和离散优化问题4个方面进行阐述。

单目标最优化问题（Simple-Objective Optimization Problem，SOP）是“最优化问题”中较简单的一种情况，从一个问题所有可能的备选方案中，选择出一种最优的解决方案。从数学上来讲，最优化问题是研究一个给定的集合S上泛函J(u)的极小化或极大化问题；广义上来讲，最优化问题包括数学规划、图和网络、组合最优化、库存论、决策论、排队论、最优控制等；狭义上来讲，最优化问题仅指数学规划。最优化问题的解决方法广泛应用于生产管理、经济规划、工程设计、系统控制科学研究等领域。

然而大多数工程设计和科学研究领域中普遍存在的优化决策问题是多属性的，一般是对多个目标同时进行优化，从而找到满足多个目标的较好的设计方案，这就是所谓的多目标优化问题（Multi-Objective Optimization Problem，MOP）。MOP中的各个优化目标之间往往是相互联系但又彼此制约的，一个优化目标性能提升的同时往往会造成其他优化目标性能的降低甚至退化，即所求解的MOP中所有优化目标很难同时获得最优结果[2]。

现实生活中的优化问题大多是多目标优化问题，例如分布式电源选址方案的优化问题。分布式电源接入电网的做法改变了传统电网的运行模式，降低了电力损耗，提高了电力系统的稳定性和灵活性。如何选址建造分布式电源，同时保证电网损耗、电压稳定性及建造成本的最优，就是一个MOP[3]。又如当消费者购买汽车时，不同舒适度的汽车对应不同的价格，只是专注价格的消费者只需要挑选最便宜的汽车即可，同理只关注舒适度的消费者只需要挑选最舒适的即可。但在实际生活中，消费者总是想在满足自己舒适度要求的前提下选择最优惠的汽车，或者在自己可以承受的价格范围内，挑选舒适度最高的汽车，这就构成了一个双目标问题：一个是最小化价格目标问题，另一个是最大化舒适度目标问题。再如，在工业设计问题上，生产厂商会提出工业产品的造价最低、表现最优、稳定性最好等一系列目标，这些目标同时考虑优化就构成了多目标优化问题[4]。因此，可以说多目标优化问题在现实生活中随处可见，研究这类问题的求解方法具有非常重要的现实意义。MOP在工程应用等现实生活中非常普遍，并且处于非常重要的地位。随着科技的快速发展及全球经济竞争的不断加强，现实生活的问题变得越来越复杂，往往需要同时考虑多个目标的优化，因此，多目标优化逐渐发展为最优化问题研究范畴中一个极其重要的热点与方向。自20世纪60年代早期以来，MOP吸引了越来越多不同背景的研究人员的注意，尽管针对MOP提出了很多算法，这些算法也在一定程度上表现出令人满意的求解效果，但在某些问题的求解上仍存在诸如收敛速度慢、搜索能力差、早熟收敛等常见问题，目前，没有哪一种算法能够解决所有的优化问题。针对具体问题的特点，通过设计或改进算法的运行机制来解决不同类型的问题是非常有意义的。因此，针对MOP的研究是一个十分具有挑战性和重要意义与价值的课题。

MOP与SOP的不同之处在于单目标的优化结果是一个最优解，而对于MOP而言，不存在唯一的或者绝对的最优解。解决MOP的一个较好的办法就是对其中相互制约的各个目标予以综合考虑，即在多个目标之间进行协调并找出满意的非劣最优解，即Pareto最优解。由于Pareto最优解通常为一系列折衷解的集合，故将该集合称之为Pareto最优解集（Pareto Optimal Set）[1]。

但是现实生活中的大多数优化问题需要找到一个解，该解不仅要满足最优性，而且要满足一个或多个约束条件，这些问题统称为约束优化问题（Constrained Optimization Problem，COP）。通常来说，大多数约束优化问题是具有挑战性的，且难以求解。如何有效地求解约束优化问题被认为是计算机科学、运筹学和优化理论中极具挑战性的研究课题之一。本质上，约束优化问题可以看成约束处理和最优化问题的结合。

目前，根据进化计算中约束处理方法的研究进展，约束处理方法主要分为3类：罚函数方法、可行规则方法和多目标方法[5]。因原理简单和易于实现，罚函数方法是目前应用最广泛的约束处理方法之一。罚函数方法是指在目标函数中加入一个惩罚函数，将约束问题转换成一个无约束问题，该方法的难点在于罚参数的选择。可行规则方法建立在可行解要优于不可行解的偏好基础上，这里需满足3条比较规则：可行解要优于不可行解；当两个解都是可行时，选择目标函数值小的；当两个解都是不可行解时，选择违反约束小的。最近几年，多目标概念的思想已经被越来越多地用于进化计算中的约束处理，这种思想是将约束转换成一个或多个目标。根据处理约束的不同原则，有两类多目标方法：一类是有两个目标的——源目标函数和所有约束违反程函数；另一类是将每个约束看成一个目标。因此，对于有m个约束的多目标问题来说，加上原有的目标函数，总共有m+1个目标函数[6]。

随着社会的发展和经济的进步，优化问题出现了规模大、复杂多峰、非线性、不可微等特点，传统的优化算法已经无法快速、高效地解决此类优化问题，因此在传统的优化算法的基础之上，探索出更高效的现代化算法具有十分重要的意义。一般的优化方法只能求得连续变量的最优解，而传统的求离散问题的最优解是先用连续变量优化设计方法求连续变量的最优解，然后取整到离散值上，这就存在一些弊端，即得不到可行最优解，或者所得的解不是离散的最优解。然而，现实生活中很多问题常常涉及离散的属性值，这类问题被称为离散问题。当代的学者们针对这些离散问题提出了许多离散优化方法，如决策树、关联规则等，因此设计高性能、实用的离散优化方法对于社会具有非常重要的现实意义。