穷举法
列举所有可能,然后一个个去,得到最优的结果。如图一,需要从A点一直走到G点,才能知道,F是最高的(最优解)。这种算法得到的最优解肯定是最好的,但也是效率最低的。
穷举法虽然能得到最好的最优解,但效率是极其低下的。为了能提高效率,可以不要枚举所有的结果,只枚举结果集中的一部分,如果某个解在这部分解中是最优的,那么就把它当成最优解。显然这样有可能不能得到真正的最优解,但效率却比穷举法高很多。
只枚举部分解的方法很多。
贪心法
在枚举所有解时,当遇到的解在当前情况下是最优时,就认为它是最优解。如图一,当从A点到B点时,由于B点比A点的解更优,所以会认为B点是最优解。
显然这样的效率很高,但得到的最优解质量也很差。
爬山法
贪心法是只和前面的一个比较,为了提高最优解的质量,可以不仅和前一个解比较,也和后一个解比较,如果比前面和后面的解都优,那么就认为它是最优解。如图一,当到C点时,发现它比前面的B和后面的D点的解都好,所以认为它是最优解。
模拟退火算法
爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。
如图一,搜索到A点后就停止了搜索。如果能跳出局部最优解,那么得到的最优解的质量相对就会好很多。如当搜索到A点时以一定的概率跳转到另外一个地方。这样就有可能跳出局部最优解A。如果经过一定次数的跳跃,跳到了E点,那么就会找到全局的最优解了。
如果这个概率不变,那么就会一直跳跃下去,不会结束。可以让这个概率逐渐变小,到最后趋于稳定。这里的概率逐渐减小类似于金属冶炼的退火过程,所以称之为模拟退火算法。
模拟退火算法(Simulated Annealing,SA)最早由Kirkpatrick等应用于组合优化领域,它是基于Mente-Carlo迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部最优解能概率性地跳出并最终趋于全局最优。
模拟退火算法的关键在于控制温度(概率)降低快慢的参数r,这个参数范围是0<r<1。如果参数r过大,则搜索到全局最优解的可能会较高,但搜索的过程也就较长。若r过小,则搜索的过程会很快,但最终可能会达到一个局部最优值。
模拟退火算法不能保证得到真正的最优解,但它能在效率不错的情况下得到质量较高的最优解。
遗传算法
遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,生物在繁衍发展的过程,会通过繁殖,发生基因交叉,基因突变,适应度低的个体会被逐步淘汰,而适应度高的个体会越来越多。那么经过N代的自然选择后,保存下来的个体都是适应度很高的。
遗传算法初始是一个较差解的解集种群,通过遗传交叉繁殖出下一代的解集种群。在交叉的过程中,有一定的概率发生基因突变。在下一代的解集种群中,通过适者生存的自然选择,淘汰那些较差的解(个体),只让较好的解(个体)繁殖后代,这样产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境。经过许多代的繁殖和自然选择后,就能得到接近于真正最优解的解。
可以用精英主义原则来对基本遗传算法进行优化。所谓精英主义原则,就是为了防止进化过程中产生的最优解被交叉和变异所破坏,可以将每一代中的最优解原封不动的复制到下一代中。
蚁群算法
蚁群算法(Ant Colony Optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。
蚂蚁在路径上前进时会根据前边走过的蚂蚁所留下的分泌物选择其要走的路径。其选择一条路径的概率与该路径上分泌物的强度成正比。因此,由大量蚂蚁组成的群体的集体行为实际上构成一种学习信息的正反馈现象:某一条路径走过的蚂蚁越多,后面的蚂蚁选择该路径的可能性就越大。蚂蚁的个体间通过这种信息的交流寻求通向食物的最短路径。
蚁群算法就是根据这一特点,通过模仿蚂蚁的行为,从而实现寻优。当程序最开始找到目标的时候,路径几乎不可能是最优的,甚至可能是包含了无数错误的选择而极度冗长的。但是,程序可以通过蚂蚁寻找食物的时候的信息素原理,不断地去修正原来的路线,使整个路线越来越短,最终找到最佳路线。
这种优化过程的本质在于:
选择机制:信息素越多的路径,被选择的概率越大。
更新机制:路径上面的信息素会随蚂蚁的经过而增长,而且同时也随时间的推移逐渐挥发消失。
协调机制:蚂蚁间实际上是通过分泌物来互相通信、协同工作的。通过个体之间的信息交流与相互协作最终找到最优解,使它具有很强的发现较优解的能力。
出错机制:显然如果蚂蚁都往信息素多的地方移动,会导致局部最优解的问题。可是,总有些具有叛逆精神的蚂蚁,会不往信息素较多的地方移动,从而可以跳出局部最优解,找到全局的最优解。
- 大小: 16 KB
分享到:
相关推荐
人工智能-项目实践-优化算法-遗传算法、禁忌搜索、模拟退火、蚁群算法 遗传算法、禁忌搜索、模拟退火、蚁群算法 解决三十个城市的旅行商问题 人工智能课的一次作业,py写的,来自我这个新手码农 以下是三十个城市...
详细介绍了神经网络算法、粒子群算法、遗传算法、模糊逻辑控制、免疫算法、蚁群算法、小波分析算法及其MATLAB的实现方式等内容; 第二部分详细介绍了智能算法的工程中的应用问题,包括模糊神经网络在工程中的应用、...
美赛算法实现,各种智能算法(遗传算法、模拟退火算法、蚁群算法、粒子算法、神经网络算法等)实现和优化 美赛算法实现,各种智能算法(遗传算法、模拟退火算法、蚁群算法、粒子算法、神经网络算法等)实现和优化 ...
ACM集训、国赛、美赛算法实现,各种智能算法(遗传算法、模拟退火算法、蚁群算法、粒子算法、神经网络算法等)实现和优化 ACM集训、国赛、美赛算法实现,各种智能算法(遗传算法、模拟退火算法、蚁群算法、粒子算法...
该资源中包含遗传算法,蚁群算法,模拟退火算法的程序
遗传算法、禁忌搜索、模拟退火、蚁群算法 解决三十个城市的旅行商问题python实现
智能优化算法研究(模拟退火法、神经网络、蚁群算法、遗传算法)
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、...TSP旅行商问题的遗传算法、蚁群算法、模拟退火算法、禁忌搜索算法求解源码+项目说明.zip
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计...基于遗传算法+蚁群算法+模拟退火算法和禁忌搜索算法解决旅行商问题(源码+项目说明).zip
应用遗传算法、禁忌搜索、模拟退火、蚁群算法 解决三十个城市的旅行商问题 包含了三十个城市的坐标 适用于新手简单易懂
系统介绍智能优化算法的一般内容和方法,包含遗传算法 模拟退火 禁忌搜索 蚁群算法,以及新进发展起来的算法.
Matlab 智能优化算法 (粒子群算法、模拟退火算法、差分进化算法、蚁群算法) 附matlab源代码
基于遗传算法、粒子群算法、模拟退火、蚁群算法、免疫优化算法、鱼群算法,旅行商问题仿真(完整源码+数据).zip 已获导师指导并通过的97分的高分课程设计项目,可作为课程设计和期末大作业,下载即用无需修改,项目...
圆排列问题的蚁群模拟退火算法 智能混合优化策略及其在流水作业调度中的应用 蚁群算法在QoS网络路由中的应用 一种改进的自适应路由算法 基于蚁群算法的煤炭运输优化方法 基于蚁群智能和支持向量机的人脸性别分类...
受自然启发的方法是蚁群优化、遗传算法和模拟退火,它们生成全局传递函数以将输入图像转换为更高对比度的图像,同时试图保持图像的自然外观。 图像增强器方法的详细信息发表在我们的论文中:DSP(pdf或...
遗传算法、禁忌搜索、模拟退火、蚁群算法 解决三十个城市的旅行商问题 人工智能课的一次作业
MATLAB使用遗传算法,蚁群算法,模拟退火,禁忌搜索以及个算法的改进对vrptw带时间窗的车辆路径规划问题进行求解,其中遗传算法增加了大规模邻域搜索,蚁群算法增加了最大最小蚂蚁系统,模拟退火增加了重升温过程。...
目前存在的网格任务调度策略,如遗传算法、蚁群算法、模拟退火算法、禁忌算法等,皆优缺点分明,都不能够单独实现对网格任务的最优调度,而且没有将遗传算法和蚁群算法结合在一起来解决网格任务调度问题的策略。...
集训、国赛、美赛算法实现,各种智能算法(遗传算法、模拟退火算法、蚁群算法、粒子算法、神经网络算法等)实现和优化.zip