智能优化算法_1

遗传算法是模拟生物在自然环境中的遗传和进化的过程而形成的自适应全局最优化搜索算法。

理论

达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代和子代之间，在性状上存在相似现象；变异是指父代和子代之间，以及子代的个体之间，在性状上存在差异的现象。在生物体内，遗传和变异的关系十分密切。一个生物的遗传往往会发生变异，而变异的性状有的可以遗传。

遗传物质的主要载体是染色体，基因是有遗传效应的片段，他储存着遗传信息，可以准确的复制，也可以发生突变。生物自身通过对基因的复制和交叉，是其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的便宜发生丰富多彩的变异现象。总结生物遗传和进化的规律有：

遗传学与遗传算法术语对应关系

遗传学术语	遗传算法术语
群体	可行解集
个体	可行解
染色体	可行解编码
基因	可行解编码的分量
基因形式	遗传编码
适应度	评价函数值
选择	选择操作
交叉	交叉操作
变异	变异操作

特点

算法是模拟生物在自然环境中的遗传和进化的过程形成的一种并行、高效、全局搜索的方法，他有几下特点：

领域

20世纪90年代以后，它作为一种高效、实用、鲁棒性强的优化技术，发展极为迅速，在机器学习、模式识别、神经网络、控制系统优化及社会科学等领域广泛应用。

算法流程

1. 初始化。设置进化代数计数器g=0，设置最大进化代数G，随机生成NP个个体作为初始群体P(0)；
2. 个体评价。计算群体P(t)中各个个体的适应度。
3. 选择运算。将选择算子作用于群体，根据个体的适应度，按照一定的规则或方法，选择一些优良的个体遗传到下一代群体。
4. 交叉运算。将交叉算子作用于群体，对选中的成对个体，以某一概率交换他们之间的部分染色体，产生新的个体。
5. 变异运算。将变异算子作用于群体，对选中的个体，以某一概率改变某一个或某一些基因值为其他的等位基因。群体P(t)经过选择、交叉和变异运算之后得到下一代群体P(t+1)。计算适应度值，并根据适应度值进行排序，准备进行下一次遗传操作。
6. 终止条件判断：若g<=G,则g=g+1，转到第2步；若，则输出最大适应度的个体作为最优解，终止计算。

理论

同其他进化算法一样，差分算法也是对候选解的种群进行操作，但其种群繁殖方案不同：它通过把种群中两个成员之间加权向量加到第三个成员上来产生新的参数向量，称“变异”；然后将变异向量的参数与另外预先确定的目标向量参数按一定的规则混合来产生新的试验向量，称“交叉”；最后，若试验向量的代价函数比目标向量的代价函数低，试验向量就在下一代中代替目标向量，称“选择”。种群中所有的成员必须当作目标向量进行一次这样的操作，以便在下一代中出现相同个数竞争者。在进化过程中对每一代的最佳参数向量进行评价，记录最小化过程。

这样利用随机偏差扰动产生新个体的方式，可以获得一个收敛性非常好的结果，引导搜索过程向全局最优解逼近。

特点

1. 结构简单，容易使用；
2. 性能优越。具有较好的可靠性、高效性和鲁棒性。
3. 自适应性。
4. 具有内在的并行性，可协同搜索，具有利用个体局部信息和群体全局信息知道算法进一步搜索的能力。在同样的精度下，查分进化算法具有更快的收敛速度。
5. 算法通用，可直接对结构对象进行操作，不依赖于问题信息，不存在对目标函数的限定。

领域

在人工神经元网络、电力、机械设计、机器人、信号处理、生物信息、经济学、现代农业和运筹学等。然而，尽管该算法获得了广泛研究，但相对于其他进化算法而言，研究成果相当分散，缺乏系统性，尤其在理论方面还没有重大的突破。

算法流程

操作流程如下：

上述的是最基本的差分进化算法操作程序，实际应用中还发展了几个变形形式，用符号：DE/x/y/z加以区分，其中x限定当前被变异的向量是“随机的”还是“最佳的”；y是所利用的差向量的个数；z指示交叉程序的操作方法，用bin表示。则基本的差分进化算法策略可描述为：DE/rand/1/bin.

还有其他形式：
1. DE/best/1/bin,其中

2. DE/rand-to-best/1/bin,其中

3. DE/best/2/bin,其中

4. DE/rand/2/bin,其中

还有交叉操作利用指数交叉的情况：DE/rand/1/exp…

理论

生物免疫系统是一个复杂的自适应系统。免疫系统能够识别出病原体，具有学习、记忆和模式识别能力，因此可以借鉴其信息处理机制来解决科学和工程问题。免疫算法正式基于生物免疫系统识别外部病原体并产生抗体对抗原的学习机制而提出的。

传统的免疫是指机体抗感染的防御能力，而现代免疫则指机体免疫系统识别和排除抗原性异物，从而维持机体生理平衡和稳定的功能。免疫是机体的一种生理反应，当病原体（抗原）进入人体时，这些抗原将刺激免疫细胞（淋巴B细胞、T细胞）产生一种抵抗该病原生物的特殊蛋白质——抗体。抗体能将病原生物消灭，并在将病原生物消灭之后，仍留在人体内，当同样的病原生物再次侵入人体时，该病原生物就会很快地被体内存留的抗体消灭。

免疫算法算子：亲和度评价算子、抗体浓度评价算子、激励度计算算子、免疫选择算子、克隆算子、变异算子、克隆抑制算子和种群刷新算子。由于算法的编码方式可能为实数编码、离散编码，不同编码方式下的算法算子也会有所不同。
免疫算法的种类：克隆选择算法、免疫遗传算法、反向选择算法、疫苗免疫算法等。

特点

自适应性、随机性、鲁棒性强、并行搜索机制、全局收敛性、种群多样保持性等优点。

领域

非线性最优化、组合优化、控制工程、机器人、故障诊断、图像处理等诸多领域。

算法流程

1. 首先进行抗原识别，即理解待优化问题，对问题进行可行性分析，提取先验知识，构造出合适的亲和度函数，并制定各种约束条件；
2. 产生初始抗体群，通过编码把问题的可行解表示成解空间中的抗体，在解的空间内随机产生一个初始种群。
3. 对种群中的每一个可行解进行亲和度评价。
4. 判断是否满足算法终止条件，满足，则终止寻优过程，输出最优结果，否则，继续寻优。
5. 计算抗体浓度和激励度。
6. 进行免疫处理，包括免疫处理、克隆、变异和克隆抑制。
   免疫选择：根据种群中抗体的亲和度和浓度计算结果选择优质抗体，使其活化；
   克隆：对活化的抗体进行克隆复制，得到若干副本；
   变异：对克隆得到的副本进行变异操作，使其发生亲和度变异；
   克隆抑制：对变异结果进行在选择，抑制亲和度低的抗体，保留高的变异结果。
7. 种群刷新：以随机生成的新抗体替代种群中激励度较低的抗体，形成新一代的抗体，转步骤3。

理论

蚁群算法是一种源于大自然生物世界的新的仿生进化算法，它是通过模拟自然界中蚂蚁集体寻径行为提出的一种基于种群的启发式随机搜索算法。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短途径，并且能随环境变化，适应性地搜索新的路径，产生新的选择。其根本原因是蚂蚁在寻找食物的时候，能在其走过的路经上释放一种特殊的分泌物——信息素，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上的信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下来的信息素也越来越多，后来的蚂蚁选择该路径的概率也就越高，从更增加了该路径上的信息素强度。而强大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制通过这种正反馈机制，蚂蚁最终可以发现最短的路径。
后续有改进的蚁群算法：
精英蚂蚁系统，额外的添加人工信息素；最大最小蚂蚁系统；基于排序的蚁群算法；自适应蚁群算法。

特点

具有分布式计算、无中心控制和分布式个体之间间接通信等特征。易于与其他优化算法相结合。
1. 一种本质上的并行算法；
2. 一种自组织算法。所谓自组织，就是组织力或组织指令来自于系统的内部，以区别其他组织。如果系统在获得空间、时间或功能结构的过程中，没有外界的特定干涉，就可以说系统是自组织的。简单的说，自组织就是系统从无序到有序的变化过程；
3. 具有较强的鲁棒性。
4. 一种正反馈算法。

领域

旅行商（TSP）问题、分配问题、车间作业调度（job-shop）问题等。

算法流程

1. 参数初始化。令时间t=0和循环次数Nc=0，设置最大循环次数G，将m个蚂蚁置于n个元素上，令有向图上每条边(i,j)的初始化信息量tij(t)=c表示常数，且初始时刻 δij(0)=0 δ i j ( 0 ) = 0 ;
2. 循环次数Nc=Nc+1；
3. 蚂蚁的禁忌表索引号k=1；
4. 蚂蚁数目k=k+1；
5. 蚂蚁个数根据状态转移概率公式计算的概率选择元素j并前进；
6. 修改禁忌表指针，及选择好之后将蚂蚁移动到新的元素，并把该元素移动到蚂蚁个体的禁忌表中；
7. 若集合C中元素为遍历完，即，则调到第4步；否则执行下一步；
8. 记录本次最佳路线；
9. 根据公式更新路径上的信息量；
10. 若满足结束条件，退出循环，输出最佳路线；否则清空禁忌表转到第2步。

理论

鸟类在捕食过程中，鸟群成员可以通过个体间的信息交流与共享获得其他成员的发现与飞行经历。在食物源零星分布并且不可预测的条件下，这种协作机制所带来的优势是决定性的，远远大于对食物的竞争所引起的劣势。该算法受鸟类捕食行为的启发并对这种行为进行模仿，将优化问题的搜索空间类比于鸟类的飞行空间，将每只鸟抽象为一个粒子，粒子无质量、无体积，用以表征问题的一个可行解，优化问题所要搜索的最优解等同于鸟类寻找的食物源。
粒子群算法的信息共享机制可以解释为一种共生合作的行为，即每个粒子都在不停的搜索，并且其搜索行为在不同的程度上受到群体中其他个体的影响，同时这些粒子还具备对所经历最佳位置的记忆能力，即其搜索行为在受其他个体影响的同时，还受到自身经验的引导。基于独特的搜索机制，粒子群算法首先生成初始种群，即在可行解空间和速度空间随机制初始化粒子的速度与位置，其中粒子的位置用于表征问题的可行解，然后通过种群间粒子个体的合作与竞争来求解优化问题。

算法：

假设在一个D维空间中，有N个粒子组成的一个群落，其中第i个粒子表示为一个D维空间的向量：
Xi=(xi1,xi2,xi3,...,xiD),i=1,2,...,N X i = ( x i 1 , x i 2 , x i 3 , . . . , x i D ) , i = 1 , 2 , . . . , N
第i个粒子的“飞行”速度也是一个D维的向量，记为：

第i个粒子迄今为止搜索到的最优位置称为个体极值，记为：

整个粒子群迄今为止搜索到的最有位置为全局极值，记为：

在找到这两个最优值时，粒子根据如下两式更新自己的速度和位置


其中c1，c2为学习因子，也称加速常数；r1，r2为[0,1]范围内的均匀随机数。更新速度的式子有三部分组成：第一部分为“惯性”或“动量”部分，反映了粒子的运动“习惯”，代表例子有维持自己先前速度的趋势；第二部分为“认知”部分，反映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位置逼近的趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或领域历史最佳位置逼近的趋势。

标准的粒子群算法由Y.H.Shi改进得到，加入了惯性权重 ，由于其能保证收敛较好的收敛结果，所以被默认为标准粒子群算法。

试验结果表明： 在0.8~1.2之间，粒子群算法有较快的收敛速度；而当 >1.2时，算法容易陷入局部极值。另外，搜索过程中可以对 进行动态调整：在算法开始时，可给 赋予较大正值，随着搜索的进行，可以线性地使 逐渐减小，这样在保证算法在刚开始各粒子都有较大的速度步长在全局范围内探测到较好的区域；而在后期，较小的 则保证粒子能够在极值点周围做精细的搜索，从而使算法有较大的概率向全局最优解位置收敛。对 调整，可以权衡全局搜索和局部搜索能力，目前，采用较多动态惯性权重值是Shi提出的线性递减权值策略，表达式如下：

其中， Tmax T m a x 表示最大进化代数； ωmin ω m i n 表示最小惯性权重； ωmax ω m a x 表示最大权重； t t 当前迭代次数，大多数应用中ωmax${\omega }_{max}$=0.9， ωmin ω m i n =0.4.

特点

该算法本质上是一种随机搜索算法，它能以较大概率收敛与全局最优解。实践表明，它适合在动态、多目标优化环境中的寻优，与传统优化算法相比，具有较快的计算速度和更好的全局搜索能力。

1. 基于群智能理论的优化算法；
2. 和遗传算法都是随机初始化种群，使用适应值来评价个体的优劣程度和进行一定的随机搜索。但粒子群算法根据自己的速度来决定搜索，没有遗传算法的交叉和变异。与进化算法相比，粒子群算法博爱留了基于种群的全局搜索策略，但是其采用的速度—位移模型操作简单，避免了复杂的遗传操作。
3. 由于每个粒子在算法结束都保留了其个体的极值，即粒子群算法除了可以找到问题的最优解外，还会得到若干较好的次优解，因此将粒子群算法用于调度和决策问题可以给出多种有意义的方案。
4. 算法特有的记忆使其可以动态的跟踪当前搜索情况并调整策略。粒子群算法对种群的大小不敏感，即使种群数目下降，性能下降也不是很大。

领域

目前算法已广泛应用于函数优化、神经网络训练、模式分类、模糊控制等领域。

算法流程

1. 初始化粒子群，包括群体规模N，每个粒子的位置 Xi X i ，速度 Vi V i 。
2. 计算每个粒子的适应度值 fit[i] f i t [ i ] ；
3. 对每一个粒子，用它的适应度值和个体极值 Pbest(i) P b e s t ( i ) 做比较，如果 fit[i]<Pbest(i) f i t [ i ] < P b e s t ( i ) ，则用 fit[i] f i t [ i ] 替换掉 Pbest(i) P b e s t ( i ) 。
4. 对每一个粒子，用它的适应度值和全局极值 Gbest(i) G b e s t ( i ) 做比较，如果 fit[i]<Gbest(i) f i t [ i ] < G b e s t ( i ) ，则用 fit[i] f i t [ i ] 替换掉 Gbest(i) G b e s t ( i ) 。
5. 迭代更新粒子的速度 Vi V i 和位置 Xi X i ；
6. 进行边界条件处理；
7. 判断算法终止条件是否满足，若是，结束算法，输出最优解，否则，返回步骤2。

理论

算法最早由Metopolis提出，它以优化问题求解过程与物理退火过程之间的相似性为基础，优化的目标函数相当于金属的内能，优化问题的自变量组合状态空间相当于金属的内能状态空间，问题的求解过程就是找一个组合状态，是目标函数值最小。利用Metopolis算法并适当的控制温度的下降过程实现模拟退火，从而达到求解全局优化问题的目的。

高温下，液体的大量分子彼此之间进行着相对自由流动，如果该液体慢慢的冷却，热能原子分子可动性就会消失。大量原子常常能够自行排列长行，形成一个纯净的晶体，该晶体在个方向上都完全有序地排列在几百万倍于单个原子的距离之内。对于这个系统来说，晶体的状态是能量最低状态，而所有缓慢冷却的系统都可以自达到这个最低能量状态。实际上，如果液态金属被迅速冷却，则他不会达到这一状态，而只能形成一种较高能量状态的多晶体状态。因此，这一过程的本质在于缓慢的冷却，以争取足够的时间，让大量原子在丧失可动性之前进行重新分布。简单而言，物理退火过程有以下几个过程组成：加温过程、等温过程和冷却过程。

相似关系表

物理退火	模拟退火
粒子状态	解
能量最低态	最优解
溶解过程	设定初温
等温过程	Metropolis采样过程

冷却 控制参数的下降
能量 目标函数

特点

该算法适用范围广，可靠性高，算法简单，便于实现，算法的策略有利于避免陷于局部最优解，具有十分强的鲁棒性，比起普通的优化搜索方法，有以下独特的方面：

领域

工程中已广泛的应用到生产调度、控制工程、机器学习、神经网络、模式识别、图像处理、离散/连续变量的结构优化问题等领域。

算法流程

1. 初始化：设置初始温度T0（充分大）、初始解状态X0（是迭代的起点）、每个T值的迭代次数L；
2. 对k=1，…，L做第3至6步；
3. 产生新解X’；
4. 计算增量detaE=E(X’)-E(X)，其中E(X)为评价函数；
5. 若detaE<0，则接受X’为新的当前解，否则以概率exp(-detaE/T接受X’作为新的当前解；
6. 如果满足终止条件，则输出当前解作为最优解，结束程序。
7. T逐渐减小，T->0然后转到第2步。

所谓禁忌，就是禁止重复前面的操作。为了改进局部领域搜索容易陷入局部最优点的不足，禁忌搜索算法引入了一个禁忌表，记录下已经搜索过的局部最优点，在下次搜索中，对禁忌表中的信息不再搜索或有选择的搜索，从而实现全局最优化。

理论

对于一个初始解，在一种领域范围内对其进行一些列变化，从而得到许多候选解。从这些候选解中选出最优候选解，将候选解对应的目标值与“best so far”状态进行比较。若其目标值优于“best so far”状态，就将该候选解解禁，用来替代当前最优解及其“best so far”状态，然后将其加入禁忌表，再讲禁忌表中相应对象的禁忌长度改变；如果所有的候选解中所对应的目标值都不存在优于“best so far”状态，就从这些候选解中选出不属于禁忌对象的最佳状态，并将其作为新的当前解，不用与当前最优解进行比较，直接将其所对应的对象作为禁忌对象，并将禁忌表中相应的晋级长度进行修改。

特点

与传统优化算法相比，主要特点：
1. 算法的新解不是在当前解得领域中随机产生，它要么是优于“best so far”的解，要么是非禁忌的最佳解，因此选取优良的概率远远大于其他劣质解得概率。
2. 具有灵活的记忆功能和藐视准则，并且在搜索过程中可以接受劣质解，所以具有较强的“爬山”能力，搜索时能够跳出局部最优解，转向解空间的其他区域，从而增大获得更好的全局最优解的概率。因此，禁忌搜索算法是一种拒不搜索能力很强的全局迭代寻优算法。

领域

迄今为止，禁忌搜索算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得很大成功，近年来在函数全局优化得到较多的研究，并迅速发展。

算法流程

1. 给定禁忌搜索算法参数，随机产生初始解x，置禁忌表为空。
2. 判断算法终止条件是否满足，是，结束算法，输出最优解，否则，继续
3. 利用当前解的领域函数产生其所有（或若干）领域解，并从中确定若干候选解。
4. 对候选解判断藐视准则是否满则，是，用满足藐视准则的最佳状态y替代x，应用于y对应的禁忌对象替换最早进入禁忌表的禁忌对象，同时用y替换“best so far”状态，然后转步骤6；否则，继续
5. 判断候选解对应的个对象的禁忌属性，选择候选解集中非禁忌对象对应的最佳状态为新的当前解，同事用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象。
6. 判断算法终止条件是否满足，是，结束算法，否则转步骤3.

神经网络或人工神经网络，是指用大量的简单计算单元（即神经元）构成的非线性系统，它在一定程度上模仿了人脑神经系统的信息处理、储存和检索功能，是对人脑神经玩过的某种简化、抽象和模拟。其工作方式分为学习和工作两种状态。

理论

神经网路的结构和基础原理是以人脑的组织结构和活动规律为背景的，它反映了人脑的某些基本特征，是人脑的某些抽象、简化和模仿。它由许多并行运算的简单功能单元——神经元组成，每个神经元有一个输出，他可以连接到许多其他神经元，每个神经元输入有多个连接通路，每个连接通路对应一个连接权系数。

领域

模式识别、故障检测、智能机器人、非线性系统辨识和控制、市场分析、决策优化、智能接口、知识处理、认知科学等。

特点

具有非线性映射能力；不需要精确的数学模型；擅长从输入输出数据中学习有用知识；容易实现并行计算；有大量的简单计算单元组成，易于用软硬件实现等。
1. 与传统的参数模型方法最大的不同在于它是数据驱动的自适应技术，不需要对问题做任何先验假设。
2. 具备泛化能力，泛化能力是指经训练后的学习模型对未来训练集中出现的样本作出正确反应的能力。
3. 是一个具有普遍适用性的函数逼近器。
4. 是非线性的方法。

模型

根据连接方式分为3类：
前馈神经网路：也称前向网络，他只在训练过程有反馈信号，而在分类过程中数据只能向前反馈。直到到达输出层，层间没有向后的反馈信号。BP神经网络属于前馈网络。
反馈神经网络：是一种从输入到输出具有反馈连接的神经网络，其结构比前馈网络要复杂得多，典型的有：Elman网路和Hopfield网络。
自组织网络：是一种无导师学习网路。它通过自动寻找样本中的内在规律和本质属性，自组织、自适应地改变网络参数与结构。

学习

主要是指使用学习算法来调整神经元间的连接权，使得网络输出更符合实际。学习分为有导师学习和无导师学习两类。有导师学习是将一组训练集送入网络，根据网络的实际输出与期望输出间的差别来调整连接权。无导师学习抽取样本集合中文翰的统计特性，并以神经元之间的连接权的形式储存在网络中。

有导师学习算法的主要步骤：
1. 从样本集合中取一个样本（Ai，Bi），其中Ai是输入，Bi是期望输出；
2. 计算网络的实际输出O；
3. 求D=Bi-O;
4. 根据D调整权矩阵W；
5. 对每个样本重复上述过程，知道对整个样本集来说，误差不超过规定范围为止。
Delta学习规则是一种简单的有导师学习算法，该算法根据神经元的实际输出与期望输出差别来调整连接权，气数学表示：

简单来讲就是：若神经元实际输出比期望输出大，则减小所有输入为正的连接权的权重，增大所有输入为负的连接权重；反之一样。
工作
神经元间的连接权保持不变，神经网路处于工作状态，作为分类器、预测器等使用。

[]引于文献：智能优化算法及其Matlab实例，包子阳，余继周 编著. 电子工业出版社。