数学建模算法汇编

数学的本质在于它的自由.

—— 康托尔(Cantor)

经过上次的飞航杯竞赛,君君对数学建模产生了十分浓厚的兴趣。今天君君要掏出底牌,给童鞋们分享下君君学习到的一些十分接地气的建模算法。

人工蜂群算法(ABC算法)

01

人工蜂群算法(Artificial Bee Colony, ABC)是由Karaboga于2005年提出的一种新颖的基于群智能的全局优化算法,其直观背景来源于蜂群的采蜜行为,蜜蜂根据各自的分工进行不同的活动,并实现蜂群信息的共享和交流,从而找到问题的最优解。人工蜂群算法属于群智能算法的一种。

标准的ABC算法通过模拟实际蜜蜂的采蜜机制将人工蜂群分为3类:采蜜蜂观察蜂侦察蜂。整个蜂群的目标是寻找花蜜量最大的蜜源

在标准的ABC算法中,

采蜜蜂利用先前的蜜源信息寻找新的蜜源并与观察蜂分享蜜源信息;

观察蜂在蜂房中等待并依据采蜜蜂分享的信息寻找新的蜜源;

侦查蜂的任务是寻找一个新的有价值的蜜源,它们在蜂房附近随机地寻找蜜源。

主要流程便是不断寻找蜜源的过程:

1.初始化;

2.重复以下过程:

1)将采蜜蜂与蜜源一一对应,根据上面第一个公式更新蜜源信息,同时确定蜜源的花蜜量;

2)观察蜂根据采蜜蜂所提供的信息采用一定的选择策略选择蜜源,根据第一个公式更新蜜源信息,同时确定蜜源的花蜜量;

3)确定侦查蜂,并根据第三个公式寻找新的蜜源;

记忆迄今为止最好的蜜源;

3.判断终止条件是否成立;

通过上面不断寻优的过程,最终算出区域中的最优解。

BP神经网络算法

02

BP神经网络具有任意复杂的模式分类能力和优良的多维函数映射能力,解决了简单感知器不能解决的异或(Exclusive OR,XOR)和一些其他问题。从结构上讲,BP网络具有输入层隐藏层输出层;从本质上讲,BP算法就是以网络误差平方为目标函数、采用梯度下降法来计算目标函数的最小值。

BP神经网络是一种多层的前馈神经网络,其主要的特点是:信号是前向传播的,而误差是反向传播的。具体来说,对于如下的只含一个隐层的神经网络模型:

BP神经网络的过程主要分为两个阶段,第一阶段是信号的前向传播,从输入层经过隐含层,最后到达输出层;第二阶段是误差的反向传播,从输出层到隐含层,最后到输入层,依次调节隐含层到输出层的权重和偏置,输入层到隐含层的权重和偏置

目前,在人工神经网络的实际应用中,绝大部分的神经网络模型都采用BP网络及其变化形式。它也是前向网络的核心部分,体现了人工神经网络的精华。

进化算法

03

进化算法,或称“演化算法” (evolutionary algorithms, EAS) 是一个“算法簇”,尽管它有很多的变化,有不同的遗传基因表达方式,不同的交叉和变异算子特殊算子的引用,以及不同的再生选择方法,但它们产生的灵感都来自于大自然的生物进化。进化计算具有自组织、自适应、自学习的特性,能够不受问题性质的限制,有效地处理传统优化算法难以解决的复杂问题。

进化计算包括遗传算法(Genetic Algorithms)、遗传规划(Genetic Programming)、进化策略(Evolution Strategies)和进化规划(Evolution Programming)4种典型方法。

以遗传算法为例,其工作步骤可概括为:

(1) 对工作对象——字符串用二进制的0/1或其它进制字符编码。

(2) 根据字符串的长度L,随即产生L个字符组成初始个体。

(3) 计算适应度。适应度是衡量个体优劣的标志,通常是所研究问题的目标函数。

(4) 通过复制,将优良个体插入下一代新群体中,体现“优胜劣汰”的原则。

(5) 交换字符,产生新个体。交换点的位置是随机决定的

(6) 对某个字符进行补运算,将字符1变为0,或将0变为1,这是产生新个体的另一种方法,突变字符的位置也是随机决定的。

(7) 遗传算法是一个反复迭代的过程,每次迭代期间,要执行适应度计算、复制、交换、突变等操作,直至满足终止条件。

蚁群算法

04

蚁群算法是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

这种算法具有分布计算信息正反馈启发式搜索的特征,本质上是进化算法中的一种启发式全局优化算法。

将蚁群算法应用于解决优化问题的基本思路为:

蚂蚁的行走路径表示待优化问题的可行解,整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多,随着时间的推进,较短的路径上累积的信息素浓度逐渐增高,选择该路径的蚂蚁个数也愈来愈多。最终,整个蚂蚁会在正反馈的作用下集中到最佳的路径上,此时对应的便是待优化问题的最优解。

该算法的规则如下:

(1)感知范围

蚂蚁观察到的范围是一个方格世界,相关参数为速度半径,一般为3,可观察和移动的范围为3x3方格。

(2)环境信息

蚂蚁所在环境中有障碍物、其他蚂蚁、信息素,其中信息素包括食物信息素(找到食物的蚂蚁留下的)、窝信息素(找到窝的蚂蚁留下的),信息素以一定速率消失。

(3)觅食规则

蚂蚁在感知范围内寻找食物,如果感知到就会过去;否则朝信息素多的地方走,每只蚂蚁会以小概率犯错误,并非都往信息素最多的方向移动。蚂蚁找窝的规则类似,仅对窝信息素有反应。

(4)移动规则

蚂蚁朝信息素最多的方向移动,当周围没有信息素指引时,会按照原来运动方向惯性移动。而且会记住最近走过的点,防止原地转圈。

(5)避障规则

当蚂蚁待移动方向有障碍物时,将随机选择其他方向;当有信息素指引时,将按照觅食规则移动。

(6)散发信息素规则

在刚找到食物或者窝时,蚂蚁散发的信息素最多;当随着走远时,散发的信息素将逐渐减少。

君君粗略的讲解或许不能满足大噶对于学习狂热的激情,但足以引导大家学习的方向。

在这个寒冷的时节里

因为有你的关注

而变得温暖

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181206B1M7Y600?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券