优化算法综述
群智能算法是一种演化计算技术，蚁群算法和粒子群算法都是典型的群智能算法。蚁群算法是模拟蚂蚁觅食，已成功应用于许多离散优化问题。粒子群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食过程，但后来发现它是一种很好的优化工具。...
通常认为，算法时间复杂性存在多项式界时，计算时间是可以接受的，如果超出多项式界，计算时间将随实例 的增加而急速增长，在实际应用中难以被人们接受。如果算法的时间复杂性存在多项式的界，则称为P类(Polynomial bounded)问题，如快速傅里叶变换(FFT)算法，有许多问题，其算法的时间复杂性肯定超出多项式界，此外，还有若干问题未能证明它超出多项式界，但又未找到有效算法，这类问题称为非确定性多项式(Nondeterminstic Polynomial, NP)问题，简称NP问题。
旅行推销员问题(Travelling Salesman Problem, TSP)就是一个经典的人工智能难题，该问题描述为：有 个城市，推销员要到达每个城市各一次，回到起点，要求旅行路径最短。
穷举法是简单明了的搜索方法，该方法是在一个连续有限搜索空间或离散无限搜索空间中，计算空间每点的目标函数。许多问题所对应的搜索空间都很大，采用穷举法求解几乎是不可能的。
爬山法
爬山法也是常用的搜索方法，是寻找局部最优解的方法，只有当更好的解位于当前解附近的前提下，才能继续向次优解搜索。对于具有单峰分布的解空间，爬山法是行之有效的搜索算法，而对于多峰空间，则很难跳出局部最优解。
模拟退火(Simulated Annealing，SA)算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
模拟退火算法的思想最早由Metropolis等人于1953年提出，1983年Kirkpatrick等将其用于组合优化。该算法是一种基于蒙特卡洛(MenteCarlo)迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。SA算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解。
遗传算法(Genetic Algorithm, GA) 是一种通过模拟自然进化过程搜索最优解的方法，由美国Michigan大学的J.Holland于1975年提出。遗传算法从代表问题解集的初始种群开始，按照适者生存和优胜劣汰的原理，逐代演化出最优解。在每一代，根据个体的适应度值选择个体，并进行染色体的交叉和变异，产生出新的解集种群，这个过程导致种群像自然进化一样使后生代更适应环境。
遗传算法不能直接处理问题空间，必须把问题空间映射到遗传空间，把个体表示成由基因按一定结构组成的染色体，这一转换操作就叫染色体编码。遗传操作是对群体中的个体按其对环境的适应度施加一定的操作，从而实现优胜劣汰的进化过程。遗传操作包括选择、交叉和变异三个基本遗传算子。在遗传空间中，个体的迁移由染色体交叉和变异决定，交叉操作为GA提供了一种粗粒、大步伐的搜索手段。变异属于GA的辅助性搜索操作，其主要目的是维持解群体的多样性。一般，低频度的变异可防止群体中某些重要的染色体基因丢失，高频度的变异将使遗传算法趋于纯粹的随机搜索。变异概率通常取0.001左右。遗传算法通过交叉和变异这一对相互配合又相互竞争的操作使其兼顾全局和局部的均衡搜索能力。
Hopfield人工神经网络由美国物理学家Hopfield于1982年提出，是一种不带有学习功能的单层反馈式网络，引入非线性动力学中的能量函数概念，使神经网络的平衡稳定状态有了明确的判定依据，并给出了其硬件原理模型。该神经网络主要用于求解优化计算问题。
禁忌搜索(Tabu Search，TS）的思想最早由Glover于1986年提出，它是对局部领域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。TS算法通过引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化。相对于模拟退火和遗传算法，TS是又一种搜索特点不同的亚启发式(meta-heuristic)算法。
蚁群算法(Ant Colony Optimization，ACO)由Marco Dorigo于1992年提出，其灵感来源于蚂蚁觅食行为，无论食物和蚁穴之间的关系如何，蚂蚁总能找到两者之间的最短路径。研究表明，蚂蚁在爬过的路上会留下一种称为信息素(pheromone)的挥发性的物质，它提供了蚂蚁之间相互交流的途径。蚂蚁在行进过程中遵循一种概率选路方式，如果路径没有其它蚂蚁留下的信息素，它完全按照随机方式选路，否则选择该路径的概率与信息素的强度成正比。一段时间以后，选择某一路径的蚂蚁越多，留下信息素的强度就越大，而很少经过蚂蚁的路径，其信息素逐渐挥发掉，这就形成了一种正反馈，蚂蚁就是通过这种方法来选择最短路径的。
蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信，它在问题空间的多点同时进行独立搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。蚁群算法是一种正反馈的算法，具有较强的鲁棒性。
粒子群优化(Particle Swarm Optimization，PSO)算法是一种进化计算 (Evolutionary Computation)技术，由美国社会心理学家James Kennedy和电气工程师Russell Eberhart于1995年提出，该算法模拟鸟群的捕食行为。设想一个场景：一群鸟在随机搜索食物，在这个区域里只有一块食物，所有的鸟都不知道食物在哪里，但知道离食物还有多远，则最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。
利用PSO算法解决优化问题，每个优化解都是搜索空间中的一只鸟，称之为“粒子”，每个粒子都有一个优化问题对应的适应值(fitness value)，还有一个速度决定其飞行方向和距离。所有粒子追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每次迭代中，粒子通过跟踪两个"极值"来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest。另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。
演化博弈优化以经济学博弈理论为基础，其基本原理是将优化问题的搜索空间映射为博弈策略组合空间，优化目标函数映射为博弈效用函数，通过适应性主体的动态博弈演化过程智能地求解优化问题。
在非线性科学中，混沌(Chaos)现象指的是一种确定的但不可预测的运动状态。它的外在表现和纯粹的随机运动很相似，但混沌运动在动力学上是确定的，它的不可预测性是来源于运动的不稳定性。混沌是非线性动力系统的固有特性，是非线性系统普遍存在的现象。牛顿确定性理论能够充分处理的多维线性系统，而线性系统大多是由非线性系统简化来的。混沌现象对初值非常敏感，一个著名表述就是蝴蝶效应：北京的一只蝴蝶扇动一下翅膀，就会在日本引起一场飓风引发海啸最终导致日本毁灭。
关注 模电数电
微信扫一扫关注公众号
