1 优化问题

　　优化，从字面来理解：采取一定的措施使变得优异。在计算机领域，优化往往是指通过算法得到要求问题的最优解。优化问题在生活中随处可见，比如：教室排课、机器人控制、流水线调度、行车路径规划、航班调度、金融分析等。

　　优化问题可以简要概述为：

　　1.1 优化问题要素

　　一个优化问题通常包含三个方面：决策变量、目标函数、约束。其中决策变量是可以改变、可以优化的量，通过变量的改变与优化，获取更好的结果，也可以理解为控制变量或者是一些决定性的参数;目标函数是用来评价是否向着好的方向发展的指标，是优化问题中的评判标准;约束是一个或者多个先决条件，限定了决策变量的具体的设置范围，在优化过程中是不可忽视的一部分。

　　1.2 优化问题分类

　　1.2.1 按照目标函数的数量：

　　单目标优化问题(Single-Objective Optimization Problem)：所评测目标只有一个，只需要根据具体的满足函数条件，求得最值。

　　多目标优化(Multi-objective Optimization Problem)：多个评测函数的存在，而且使用不同的评测函数的解，也是不同的。也即是说：多目标优化问题中，同时存在多个最大化或是最小化的目标函数，并且，这些目标函数并不是相互独立的，也不是相互和谐融洽的，他们之间会存在或多或少的冲突，使得不能同时满足所有的目标函数。

　　1.2.2 根据决策变量的性质：

　　数值优化问题：决策变量的取值往往是连续的，通常是一段连续定义域上连续函数求得最值的问题。

　　组合优化问题：决策变量包含离散变量，组合优化问题是对离散变量按照一定评价标准的排序、筛选或者分类。这些问题往往有很强的工程代表性，但是求解困难。

　　1.2.3 按照是否有约束：

　　有约束问题：它是在一系列约束条件下，寻找一组参数值，使某个或某一组函数的目标值达到最优。其中约束条件既可以是等式约束也可以是不等式约束。寻找这一组参数值的关键可是：满足约束条件和目标值要达到最优。

　　无约束优化问题：即不对定义域或值域做任何限制的情况下，求解目标的最优。主要的两个概念：步长和方向。初始点选择好之后，就可以按照各种不同的无约束最优化求解算法，求解最优值了。求解过程中主要涉及两个概念，即从初始点开始沿“哪个方向”以及“走多远”到达下一个点。所谓“走多远”即之前提的“步长”的概念，“哪个方向”即方向概念。

　　2 优化算法

　　求解优化问题的方法称为优化算法，在目标函数具有明确解析表达式且剃度可求、局部解较少的时候，通常采用传统的数学方法，比如：梯度下降法、牛顿法、拉格朗日乘数法等。但是如果函数没有明确的解析表达式，那么数学方法求解起来就比较困难，这个时候使用启发式或者是元启发式算法会更加合适。下面主要介绍启发式、元启发式算法中具有代表性的演化算法。

　　2.1 演化算法背景

　　在计算智能领域，演化算法(Evolutionary Algorithms，简称EA，或称进化算法)是演化计算的子集，是一种基于群体的元启发式最优化算法。这类算法主要是模仿生物进化行为的搜索算法，例如人类的进化行为和鸟群觅食行为等。该类算法无需问题的精确模型，可以解决黑箱问题，具有比较强的全局搜索能力。

　　这种全局搜索的能力，主要体现在以下方面：

　　2.1.1 有指导搜索：依据是每个个人的适应度值;

　　2.1.2 自适应搜索：通过进化操作改进群体性能;

　　2.1.3 渐进式寻优：每代进化的结果优异与上一代;

　　2.1.4 并行式搜索：对每一代群体所有个体同时进行;

　　2.1.5 黑箱式结构：只要研究输入和输出而不需考虑过程：

　　2.1.6 全局最优解：在整个搜索区域的各个部分同时进行;

　　2.1.7 内在学习型：学习是一种有保留的行为;

　　2.1.8 稳健性强：不同的条件和环境下算法适用性和有效性强。

　　演化算法使用了各种模拟生物演化机制的操作，具有深厚的生物学理论基础：遗传：父代利用遗传基因将自身的基因信息交付给下一代(子代)，属性特征相近或相同;变异：子代和父代，以及子代各个体之间存在这一定的差异，在进化过程中是随机发生的;生存斗争和适者生存(环境选择)：适应性较强的个体被保留下来，而适应性较弱的个体则被淘汰。

　　在群体中每一个个体都是问题的备选解，而适应度函数Fitness Function用于计算出每一个解的质量(也就是个体对于环境的适应度)。演化就是不断在群体中进行交配、变异、重组、选择这些操作进而找出最优解的过程。演化算法之所以在各种优化问题上都经常逼近最优解，是因为它不会对适应度的范围作出预先假设。

　　2.2 进化计算基本流程

　　常见的终止算法的方式有三种，阈值终止：为所需解定义一个阈值或阈值函数，当某代所得到的最优解个体已经达到了此阈值，则终止进化过程，并输出最优个体;最大进化代数终止：没有定义解阈值来对进化过程进行终止，进化完全依靠达到预先定义的最大进化代数来终止;最大评价次数终止：预先定义的最大评价次数，即适应度计算次数。

　　2.3 常见的进化计算算法：

　　演化算法的具体技术可以按照遗传信息表达方式、实现细节、以及特定问题的特定处理分类：

　　遗传算法(Genetic Algorithm)：这是演化算法中最常用的类型。起源于对生物系统进行的计算机模拟研究，模拟生物在自然环境中的遗传和进化过程中形成的一种自适应优化概率搜索算法。基本遗传算法只使用选择算子、交叉算子和变异算子这三种基本的遗传算子。

　　遗传规划(Genetic Programming)：这种技术用于生成一段计算机程序，其个体是可执行结构(如程序)，其适应度值是通过执行得到的，主要进化策略是交叉。

　　进化规划(Evolutionary Programming)：与遗传编程类似，只在表型空间进行操作，只使用变异操作，通常产生的子代数目和父代数目一致。

　　基因表型编程(Gene Expression Programming)：类似于遗传规划，基因表达规划同样以计算机程序群体来进行演化计算，但它探索了一种基因型-表现型系统，将不同大小的计算机程序都编码成固定长度的“线性染色体”。

　　进化策略(Evolution Strategy)：这种技术以实数向量作为个体，同样是在表型空间进行操作，子代由父代交叉(重组)后再变异产生，个体中不仅包含了其数值信息，而且还包含了变异信息，这种方法通常产生的子代数目要比父代多。

　　差分进化(Differential Evolution)：这种算法以向量的差为基础，是一种随机的并行直接搜索算法，可对非线性不可微连续空间函数进行最优化，具有易用性、稳健性和强大的全局寻优能力。优点：差异演化在求解非凸、多峰、非线性函数优化问题表现极强的稳健性;在同样的精度要求下,差异演化算法收敛的速度快;差异演化算法尤其擅长求解多变量的函数优化问题;操作简单,易编程实现。缺点是：由于差异演化的关键步骤变异操作是基于群体的差异向量信息来修正各个体的值, 随着进化代数的增加, 各个体之间的差异化信息在逐渐缩小, 以至于后期收敛速度变慢, 甚至有时会陷入局部最优点。

　　学习分类器系统(Learning classifier system，LCS)：这种技术的解是一组分类器(一组规则或者条件)。Michigan-LCS 在个体层面进行演化，而Pittsburgh-LCS使用分类器集合群体来演化。最初的时候这些分类器都是0-1编码的，如今包含实数、神经网络、或者S-expression。其适应度一般是分类器系统应用于强化学习或有监督学习时的准确率。

　　2.4 基于群体的演化算法

　　蚁群优化算法(Ant Colony Optimization Algorithm)：这种技术以蚂蚁觅食和通过信息素沟通寻路为基础，最早应用于解决著名的旅行商(TSP)问题，该算法采用了分布式正反馈并行计算机制，易于与其它方法结合，具有较强的鲁棒性。

　　人工蜂群算法(Artificial Bee Colony Algorithm)：其直观背景是源于蜂群的采蜜行为，将个体(蜜蜂)分为不同类型：诊察蜂、采蜜蜂和观察蜂。主要特点是不需要了解问题的特殊信息，只需要对问题进行优劣的比较，通过个体的局部寻优行为，最终再群体中使用全局最优值突现出来，有着较快的收敛速度。。

　　布谷鸟搜索(Cuckoo Search)：根据布谷鸟巢寄生的行为提出，同时使用了列维飞行机制，从实现的角度来看，我们可以使用以下简单的表示法，即巢穴中的每个蛋代表一个解决方案，而每个布谷鸟只能产一个蛋(因此代表一个解决方案)，目的是使用新的和潜在更好的解决方案(布谷鸟)来替换巢穴中不太好的解决方案。显然，该算法可以扩展到更复杂的情况，即每个嵌套有多个表示一组解的蛋。在目前的介绍中，我们将使用最简单的方法，即每个巢只有一个蛋。在这种情况下，蛋、巢或布谷鸟之间没有区别，因为每个巢对应一个蛋，也代表一只布谷鸟。

　　粒子群算法(Particle Swarm Optimization Algorithm)：是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法，粒子群优化中，每个优化问题的解被看做是搜索空间域内的一只鸟，称之为“粒子”，所有的粒子都有一个由被优化问题决定的适应度(Fitness Value)，每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置，每个粒子还有一个速度V来决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索，个体的位置由当前速度、个体历史最优位置pbest和群体历史最优位置gbest共同决定。优点是概念简单、可调参数少、容易应用、收敛快。

　　2.5 其他基于群体的元启发式方法

　　狩猎搜索(Hunting Search)：根据自然中的狩猎行为提出，一群捕食者，如狼群，组织它们的位置来包围猎物。捕食者中每一个个体的位置会根据其他个体，尤其是领袖的位置调整。这是一种适合组合优化问题的连续优化方法。

　　适应性维度搜索(Adaptive Dimensional Search)：不同于仿生的元启发式技术，适应性维度搜索没有模仿任何大自然中的现象。它使用简单的性能导向方法，每一次迭代过程都会更新搜索维度率(Search Dimension Ratio)。

　　萤火虫算法(Firefly Algorithm)：通过模仿萤火虫发光互相吸引的行为设计，萤火虫不分性别，这样一个萤火虫将会吸引到所有其他的萤火虫;吸引力与它们的亮度成正比，对于任何两个萤火虫，不那么明亮的萤火虫被吸引，因此移动到更亮的一个，然而，亮度又随着其距离的增加而减少;如果没有比一个给定的萤火虫更亮的萤火虫，它会随机移动。亮度应与目标函数联系起来。萤火虫算法是以自然为灵感的启发式优化算法。

　　高斯适应(Gaussian Adaptation)：一种基于信息论的方法， 用于最大化成品率、平均适应度、平均信息量等。参考热力学和信息论中的熵。

　　模因算法(Memetic algorithm)：这是一种混合方法，参考了理查德·道金斯的模因概念，通常采用基于群体的算法形式，再加上能够执行局部优化的个体学习过程。这种方法强调利用每个问题自身的特性，并调和局部搜索和全局搜索。

　　3 测试函数

　　详细测试函数集信息请参考郑州大学智能计算实验室网站：

　　(http://www5.zzu.edu.cn/cilab/Benchmark/wysyhwtcsj.htm)

　　

 

　　

 

　　3.1 评价指标

　　3.1.1 算法收敛性

　　在评价算法收敛性的时候，对于单目标问题，一般使用得是收敛迭代曲线(如下图所示)，对于多目标问题，往往使用IGD(反转世代距离)和HV(超体积)等指标。其中IGD同时考虑了解的收敛性和多样性，而HV着重考虑多样性。

　　3.1.2 统计行检验分析

　　对算法独立运行多次的结果进行统计检验分析，采用假设性检验(Wilcoxon Signed Rank Test)。