数学的本质在于它的自由.
—— 康托尔(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)散发信息素规则
在刚找到食物或者窝时,蚂蚁散发的信息素最多;当随着走远时,散发的信息素将逐渐减少。
君君粗略的讲解或许不能满足大噶对于学习狂热的激情,但足以引导大家学习的方向。
在这个寒冷的时节里
因为有你的关注
而变得温暖
领取专属 10元无门槛券
私享最新 技术干货