结构黑科技—优化算法
前面几期，小i已经为大家介绍了结构优化的基本情况和基础理论。设想当我们通过各种条件构造了一个曲面，并以结构应变能最小为目标对曲面进行优化，如若有十个参数控制曲面，每个参数有10个可选值。那么，对于曲面就有1010个可能解，如采取枚举法求最优解，理论可行，可考虑到计算成本和计算时间基本是不可能实现的。
因此，就需要引入优化算法，在最短的时间找到最优解或近似最优解。下面小i就为大家介绍常用的几种优化算法。通过介绍，大家会发现，算法并不只属于大数据分析师和软件工程师，其实离结构工程师也并不遥远。
因为算法牵扯很多数学理论、计算公式、计算机语言等艰深的内容，如详细介绍完全掌握，对于结构工程师既费力气又无必要。因此，以下的介绍小i尽量用通俗的例子，让大家了解其基本原理，同时介绍一下我们如何简单应用。
遗传基因算法
遗传算法（Genetic Algorithms，GA）由J.Holland教授（美国）1975年首先提出，是一种灵感源于达尔文自然进化理论的启发式搜索算法。该算法反映了自然选择的过程，即最适者被选定繁殖，并产生下一代。
运算过程为初始化→个体评价→选择运算→交叉运算→变异运算→终止条件判断，运算过程就如物竞天择、适者生存，只有被选择的个体才会把自己的基因传下去。下面就用一个有趣的例子，帮助大家理解。
我想让机器人小i画出我的梦中情人（最优解）。小i当然不知道我梦中情人长啥样。小i的内心是奔溃的，只能一张张试。先画一张，问我像不像？我说不像，小i就重新画一张，直到我觉得像。
然而小i又不会画画，只会填格子。于是小i准备了一张1000×1000的格子纸，每个格子可以填黑色或者白色。那么总共有21000000种画法。如果我能坚持到宇宙毁灭，那可以每张都看，然后找到那个最像的，显然我和我的梦中情人都坚持不到。
于是我只允许小i画10万张，画不出来我就砸了它。小i很紧张，开始想办法，终于想到了遗传算法。
第一轮，小i随机画了1万张（初始种群）。这1万张里面，各种乱七八糟，有像星空的，像猪的，像石头的，等等。然后小i让我挑最像的（个体评价）。我强忍怒火，挑出来一堆猪、猴、狗，好歹是哺乳动物（选择运算）。
小i拿着我挑的“猪猴狗们”，如获至宝，开始第二轮，将这些画各种交叉变异一下。比如把一幅画的耳朵跟另一幅的鼻子换一下（交叉运算），或者再随机改个眼睛（变异运算）。然后又生成了1万张图让我挑。我挑出来一堆猴子猩猩，好歹是灵长类动物。
如此反复好多轮后，挑出来的开始像人了，虽然有男人、女人。慢慢地，开始有美女了。再慢慢地，就越来越像了。在画了10万张图后，终于找到一张还不错的。虽然可能不是梦中情人（精确解），但也很像了（次优解）。
这就是遗传算法。
虽然我们已经知道了遗传基因算法的计算过程，但真正使用它，需要大量的编程。因此，对于普通结构设计人员，应用智能优化算法解决实际设计问题存在很大的难度。Grasshopper中开发了相应的优化算法模块，工程师可以利用这个模块便利的解决复杂问题，例如建筑设计中结构优化、幕墙优化等。
下面是一个二维运算的简单例子，介绍Grasshopper优化模块的原理。下图为一个山脉模型，这个模型包含了两个变量（近似看为X、Y坐标），他们可以同时变化。我们需要找出最高山峰处所对应的坐标值。
在一开始，电脑随即洒出一大堆随机点，我们假定为100个。随后选出位置较高的50个点，并在其周围再随即布置100个点，可以知道这100个点相对于他们上一代，更加靠近山峰。后面不断重复上一步，直到找到最顶峰的点。以上以二维山峰优化为例，计算机当然不止能运算二维变量，当我们初始变量不断增加时，也能得出最优解。当然，所需时间也更长。
模拟退火算法
介绍模拟退火前，先介绍爬山算法。爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解中选择一个最优解作为当前解，直到达到一个局部最优解。
爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如下图所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。
这就是简单的爬山算法思想。
爬山法是完完全全的贪心法，每次都鼠目寸光的选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以上图为例，模拟退火算法在搜索到局部最优解A后，会以一定的概率接受到E的移动。也许经过几次这样的不是局部最优的移动后会到达D点，于是找到更优的B点。
关于爬山算法与模拟退火，有一个有趣的比喻：
爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
同样，Grasshopper也提供了相应模块进行模拟退火算法。在实际应用中，推荐先采用遗传算法进行优化筛选，再结合类模拟退火算法可以提高了局部寻优的能力，采取分层优化的思想，提高运算效率。
群体智能算法
群体智能算法主要模拟了昆虫、兽群、鸟群和鱼群的群集行为，这些群体按照一种合作的方式寻找食物，群体中的每个成员通过学习它自身的经验和其他成员的经验来不断地改变搜索的方向。群体智能优化算法的突出特点就是利用了种群的群体智慧进行协同搜索，从而在解空间内找到最优解。
常见的群体智能算法有蚁群算法（Ant Colony Optimization，简称ACO）[1992年提出]；粒子群优化算法（Particle Swarm Optimization，简称PSO）[1995年提出]。下面小i简要介绍一下这两种算法。
蚁群算法
蚁群算法由Marco Dorigo于1992年提出，其灵感来源于蚂蚁觅食行为，无论食物和蚁穴之间的关系如何，蚂蚁总能找到两者之间的最短路径。研究表明，蚂蚁在爬过的路上会留下一种称为信息素(pheromone)的挥发性的物质，它提供了蚂蚁之间相互交流的途径。
蚂蚁在行进过程中遵循一种概率选路方式，如果路径没有其它蚂蚁留下的信息素，它完全按照随机方式选路，否则选择该路径的概率与信息素的强度成正比。一段时间以后，选择某一路径的蚂蚁越多，留下信息素的强度就越大，蚂蚁就是通过这种方法来选择最短路径的。
蚁群算法是一种本质上并行的算法。每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信，它在问题空间的多点同时进行独立搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。
粒子群算法
粒子群优化算法是在1995年由Eberhart博士和Kennedy博士一起提出的，它源于对鸟群捕食行为的研究。
设想这么一个场景：一群鸟进行觅食，而远处有一片玉米地，所有的鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。那么找到玉米地的最佳策略，也是最简单有效的策略就是是搜寻目前距离玉米地最近的鸟群的周围区域。粒子群优化算法就是从这种群体觅食的行为中得到了启示，从而构建的一种优化模型。
在粒子群优化算法中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”，而问题的最优解就对应为鸟群要寻找的“玉米地”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值（fitness value），可以将其理解为距离“玉米地”的距离。在每次的迭代中，种群中的粒子除了根据自身的“经验”（历史位置）进行学习以外，还可以根据种群中最优粒子的“经验”来学习，从而确定下一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代，最终整个种群的粒子就会逐步趋于最优解。
算法应用
Grasshopper优化模块中没有提供群体智能算法，但Grasshopper为开源的软件平台，使用者可以用常用的C#、VB等计算机语言编写属于自己的插件。同时，也有很多已有人编写好的插件，分享在网上。有兴趣的读者，可以找找是否有适合自己的插件。
总 结
如今在结构设计，尤其是结构优化领域，对于算法的应用越来越广泛。以上小i为大家简要介绍了一下常用优化算法的原理，希望大家以后在碰到相应算法时，可以对其有一个宏观的概念。在随后的文章中，小i也会进一步为大家介绍拓扑优化、高度优化、网格优化等常用的结构优化内容和方法。
算法提供的是一种处理复杂问题的逻辑，而如何将其应用到实际工程中，还需要工程师去把控。算法就如一把宝剑，通过今天小i的介绍，大家知道了宝剑的出处、锋利度、上手度等，可选择哪把宝剑，并将其应用于实战，还需各位剑客把握。
在实际工程优化过程中，判断优化结果是局部最优解还是全局最优解，如何提高优化计算效率，如何确定优化参数，以及适当的人为干预，都需要工程师依靠力学知识和工程经验判断。不能把优化算法理解为“傻瓜”式的计算工具。
大家对于优化算法有任何见解和使用经验，欢迎留言与小i分享。
参考资料
1 优化算法综述——模电数电
2 如何通俗易懂地解释遗传算法？有什么例子？——丁不二、小象
3 模拟退火优化算法——智能算法
4 【趣味算法】争取几句话描述一下爬山法，模拟退火，遗传算法——数学中国
5 群体智能优化算法之粒子群优化算法——算法爱好者
6 【结构】结构优化与建筑生形——中天世纪
延伸阅读
转载本文请注明出处 iStructure微信公众号
开设iStructure公众号的初衷是分享结构工程领域的见闻、优秀的设计和自己一些不太成熟的思考，向更多人呈现结构设计有趣的一面。