第10讲智能优化算法简介

智能优化算法简介

山东轻工业学院数理学院

李彬自二十世纪七十年代末以来发展起来一些非传统的优化方法，这些方法都是根据某些物理或生物现象的启发而设计的，采用这些方法可以较充分的利用目标函数的全局信息，从而解决上述问题，这些方法主要包括：1、遗传算法：这种方法是模拟自然界生物体的遗传和变异过程而得到的.2、模拟退火：这种方法是模拟统计物理中的退火过程而设计的。3、人工神经网络：其中的某些模型比如Hopfield网络可以用来处理优化问题.4、禁忌搜索：这是模拟有记忆的智能过程的方法.5、蚁群算法：这是模拟蚂蚁寻找最优路径而设计的方法.引言局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：

为了找出地球上最高的山，一群有志气的兔子们开始想办法.1．兔子朝着比现在高的地方跳去.他们找到了不远处的最高山峰.但是这座山不一定是珠穆朗玛峰.这就是局部搜索，它不能保证局部最优值就是全局最优值.引言局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：

为了找出地球上最高的山，一群有志气的兔子们开始想办法.

2．兔子喝醉了.他随机地跳了很长时间.这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去.这就是模拟退火.引言局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：

为了找出地球上最高的山，一群有志气的兔子们开始想办法.

3．兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方.他们不知道自己的使命是什么.但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰.这就是遗传算法.

引言局部搜索，模拟退火，遗传算法，禁忌搜索的形象比喻：

为了找出地球上最高的山，一群有志气的兔子们开始想办法.

4.兔子们知道一个兔的力量是渺小的.他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号.他们制定了下一步去哪里寻找的策略.这就是禁忌搜索.

引言群体智能的定义受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群集智能的研究.群集智能(Swarm

Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解”.所谓群集智能指的是“无智能的主体通过合作表现出智能行为的特性”.

1.群体中相互合作的个体是分布式的(Distributed)，这样更能够适应当前环境下的工作状态;

2.没有中心的控制与数据，这样的系统更具有鲁棒性(Robust)，不会由于某一个或者某几个个体的故障而影响整个问题的求解.3.可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性.4.由于系统中个体的增加而增加的系统的通信开销在这里十分小.系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性(Simplicity).群体智能的特点和优点在计算智能(Computational

Intelligence)领域有两种基于群智能的算法：蚁群算法(Ant

Colony

Optimization)

是对蚂蚁群落食物采集过程的模拟，已经成功运用在很多离散优化问题上.

粒子群优化算法(Particle

Swarm

Optimization，PSO)是一种进化计算技术(Evolutionary

Computation)，由Eberhart博士和Kennedy博士发明.源于对鸟群捕食的行为研究.

群体智能算法1蚁群算法原理

蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大.

为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程.在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径.这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素.当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行.与此同时释放出与路径长度有关的信息素.路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候．选择激素浓度较高路径概率就会相对较大.这样形成一个正反馈.最优路径上的激索浓度越来越大．而其它的路径上激素浓度却会随着时间的流逝而消减.最终整个蚁群会找出最优路径.2简化的蚂蚁寻食过程1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程.2简化的蚂蚁寻食过程2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点.2简化的蚂蚁寻食过程3/3

假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2:1.

寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3:1.

若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁.再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4:1.

若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线.这也就是前面所提到的正反馈效应.3蚁群系统在TSP问题中的应用10城市TSP问题20城市TSP问题3蚁群系统在TSP问题中的应用30城市TSP问题48城市TSP问题PSO是模拟鸟群的捕食行为.设想这样一个场景：一群鸟在随机搜索食物，在这个区域里只有一块食物所有的鸟都不知道食物在那里，但是他们知道当前的位置距离食物还有多远.那么找到食物的最优策略是什么呢？最简单有效的就是搜寻目前距离食物最近的鸟的周围区域.PSO从这种模型中得到了启示并用于解决优化问题.在PSO中，每个优化问题的解是搜索空间中的一只鸟.我们称之为“粒子”.所有的粒子都有一个由被优化的函数决定的适应值(FitnessValue)，每个粒子还有