精华内容
下载资源
问答
  • 离散优化和连续优化
    千次阅读
    2021-03-25 16:09:52

    凸优化学习------数学优化问题的分类

    一、 无约束优化和有约束优化

           在连续优化问题中,根据是否有变量的约束条件,可以将优化问题分为无约束优化问题和约束优化问题。有变量的约束条件则为约束优化问题,反之则为无约束优化问题。

    二、 线性优化和非线性优化

           目标函数和所有的约束函数都为线性函数,则该问题为线性规划问题(Linear Programming)。相反,如果目标函数或任何一个约束函数为非线性函数,则该问题为非线性规划问题(Nonlinear Programming)
           在非线性优化问题中,有一类比较特殊的问题是凸优化问题(Convex Programming)。在凸优化问题中,变量 x 的可行域为凸集,即对于集合中任意两点,它们的连线全部位于在集合内部。目标函数 f 也必须为凸函数,即满足
    在这里插入图片描述

           凸优化问题是一种特殊的约束优化问题,需满足目标函数为凸函数,并且等式约束函数为线性函数,不等式约束函数为凹函数。

    三、 连续优化和离散优化

            根据输入变量 x 的值域是否为实数域,数学优化问题可以分为离散优化问题和连续优化问题。

    3.1 连续优化问题

           连续优化(Continuous Optimization问题是目标函数的输入变量为连续变量 x ∈ Rd,即目标标函数为实函数。

    3.2 离散优化问题

    3.2.1 组合优化(Combinatorial Optimization):
           其目标是从一个有限集合中找出使得目标函数最优的元素。在一般的组合优化问题中,集合中的元素之间存在一定的关联,可以表示为图结构。典型的组合优化问题有旅行商问题、最小生成树问题、图着色问题等。很多机器学习问题都是组合优化问题,比如特征选择、聚类问题、超参数优化问题以及**结构化学习(Structured Learning)**中标签预测问题等。
    3.2.2 整数优化
           输入变量 x ∈ Zd为整数。一般常见的整数规划问题为整数线性规划(Integer Linear Programming,ILP)。整数线性规划的一种最直接的求解方法是:(1)去掉输入必须为整数的限制,将原问题转换为一般的线性规划问题,这个线性规划问题为原问题的松弛问题;(2)求得相应松弛问题的解;(3)把松弛问题的解四舍五入到最接近的整数。但是这种方法得到的解一般都不是最优的,因此原问题的最优解不一定在松弛问题最优解的附近。另外,这种方法得到的解也不一定满足约束条件。

    四、 单目标优化和多目标优化

    4.1 单目标优化(Single-Objective Optimization)

           所评测目标只有一个,只需要根据具体的满足函数条件,求得最值

    4.2 多目标优化(Multi-objective Optimization)

           多个评测函数的存在,而且使用不同的评测函数的解,也是不同的。也即是说:多目标优化问题中,同时存在多个最大化或是最小化的目标函数,并且,这些目标函数并不是相互独立的,也不是相互和谐融洽的,他们之间会存在或多或少的冲突,使得不能同时满足所有的目标函数。一般情况下多目标优化情况并没有唯一的全局最优解

    五、 静态规划和动态规划

    5.1 静态规划(Static Programming)

           静态规划简单来说是穷举事件所有解决方法,从中选出最优的一个解。静态规划最大的特点是时间复杂度特别高,当问题规划很大时计算量是一个天文数字。同时这种方法也有优点,就是穷举过程中我们始终存在着一个可行解。这种方法,从一个或多个可行解开始,通过不断迭代对现有可行解优化,最后得到最优解。这种方法称为静态规划。

    5.2 动态规划(Dynamic Programming)

           动态规划是运筹学的一个分支,是求解决策过程最优化的过程。是通过比较当前决策状态和未来几个状态的比较进行选取最优,关键点是找到状态转移方程。

    5.2.1 动态规划概念引入:

           有一类活动的过程,由于它的特殊性,可将过程分成若干个互相联系的阶段,在它的每一阶段都需要做决策,从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定,它依赖于当前面临的状态,又影响以后的发展。当各个阶段决策确定后,就组成一个决策序列,因而也就确定了整个过程的一条活动路线.这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程,这种问题称为多阶段决策问题。在多阶段决策问题中,各个阶段采取的决策,一般来说是与时间有关的,决策依赖于当前状态,又随即引起状态的转移,一个决策序列就是在变化的状态中产生出来的,故有“动态”的含义,称这种解决多阶段决策最优化的过程为动态规划方法。

    5.2.2 动态规划基本思想

           动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中,可能会有许多可行解。每一个解都对应于一个值,我们希望找到具有最优值的解。动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是,适合于用动态规划求解的问题,经分解得到子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样,但它们具有相同的填表格式。

    5.2.3 动态规划局限性:

           动态规划对于解决多阶段决策问题的效果是明显的,但是动态规划也有一定的局限性。首先,它没有统一的处理方法,必须根据问题的各种性质并结合一定的技巧来处理;另外当变量的维数增大时,总的计算量及存贮量急剧增大。因而,受计算机的存贮量及计算速度的限制,当今的计算机仍不能用动态规划方法来解决较大规模的问题,这就是**“维数障碍”**。

    六、 随机规划

           随机规划是规划论的一个分支,线性规划的推广。研究约束条件中的系数和目标函数中的参数均为随机变量时的线性规划问题。用于研究具有不确定性的决策问题。随机规划的中心问题是选择参数,使收益的数学期望达到最大,或使成本的数学期望达到极小。根据数学模型求得问题的最优解,但这个最优解一般不是一个确定值而是一个期望值。在随机规划中,需对随机变量进行描述,分析其概率分布,往往还要考虑各随机变量的自相关和互相关,因而在理论上和求解方法上都比确定性规划复杂得多。实际上,求解随机规划问题时,总是设法把它转化成确定性数学规划问题,再进行求解。如果随机变量的非确定性或者量的变化很小,对系统的性能不产生严重影响,可以用其数学期望代替这个非确定值,并用确定性方法求解;然后通过敏感性分析来估计非确定性因素对方案的影响程度。如果随机变量变化很大,用期望值可能使方案性能的评价受到很大影响,这时就要用随机规划方法求解。
    常见的随即规划问题:报童问题。
    常用方法:样本均值方法。

    七、 鲁棒规划

    7.1 鲁棒优化定义

           鲁棒优化的目的是求得这样一个解,对于可能出现的所有情况,约束条件均满足,并且使得最坏情况下的目标函数的函数值最优。 其核心思想是将原始问题以一定的近似程度转化为一个具有多项式计算复杂度的凸优化问题。鲁棒优化的关键是建立相应的鲁棒对等模型。然后利用相关的优化理论将其转化为可求解的“近似”鲁棒对等问题,并给出鲁棒最优解。

    7.2 鲁棒优化原理

           鲁棒优化与其它不确定优化方法的最大区别在于:
           ①鲁棒优化强调的是所谓的硬约束,寻求一个对于不确定输入的所有实现都能有良好性能的解,即不确定优化问题的解对于任何一个可能参数的实现都必须是可行的,而其它不确定优化问题并没有这个要求。
           ②鲁棒优化的建模思想与其它优化方法不同,它是以最坏情况下的优化为基础,这代表了一个保守的观点。得到的优化方案并不是最优的,但是,当参数在给定的集合内发生变化时,仍能确保优化方案是可行的,使模型具有一定的鲁棒性,即优化方案对参数扰动不敏感。
           ③鲁棒优化对于不确定参数没有分布假定,只是给出不确定参数集,不确定参数集合内的所有值都同等重要

    7.3 鲁棒优化适用范围

           鲁棒优化是解决内部结构和外部环境不确定环境下的一种新的优化方法。鲁棒优化解决内部结构变动问题时,主要是约束条件参数的不确定性或目标函数参数的不确定性解决外部环境变化时,主要是外界不确定性扰动。鲁棒优化己经从最初的线性优化鲁棒方法,发展到鲁棒优化理论的经典体系。与其它不确定优化问题的处理方法不同的是,鲁棒优化更加适用于如下情况:
           ①不确定优化问题的参数需要估计,但是有估计风险;
           ②优化模型中不确定参数的任何实现都要满足约束函数;
           ③目标函数或者优化解对于优化模型的参数扰动非常敏感;
           ④决策者不能承担小概率事件发生后所带来的巨大风险。

    八、 随即规划和鲁棒优化区别

           随机优化需要“不确定参数的分布模型”,鲁棒优化不需要“不确定参数的分布模型”。
           随机优化通过对随机参数取期望,将模型转化为确定性模型求解,它的解并不满足所有参数取值。
           鲁棒优化,只要不确定参数属于给定的不确定集合,它的解严格满足所有约束。

    最后求一波三连,hh.
    更多相关内容
  • 4 Classification of optimization problem (IP: integer programming, MINLP: mixed integer non-linear programming, MILP: mixed integer linear programming, LP: linear ...其中,离散优化又称组合优化. me..

    optimization分类

    在这里插入图片描述

    4 Classification of optimization problem
    (IP: integer programming,
    MINLP: mixed integer non-linear programming,
    MILP: mixed integer linear programming,
    LP: linear programming,
    QP: quadratic programming,
    NLP: non-linear programming)

    在这里插入图片描述
    出自

    其中,离散优化又称组合优化. means searching for an optimal solution in a finite or countably infinite set of potential solutions.

    在这里插入图片描述

    optimization按目标函数分类

    在这里插入图片描述
    source

    optimization按照决策变量分类

    在这里插入图片描述
    source

    optimization按照解决方法分类

    在这里插入图片描述
    具体算法介绍

    易混的概念

    离散优化

    是站在解的角度来看。变量是离散的。

    整数规划

    离散优化的下面,离散的变量同时还都是整数。同时,它是基于线性规划中,变量必须是整数的约束下提出来的。跟线性规划密切相关。JK

    studies linear programs in which some or all variables are constrained to take on integer values.

    1. 0-1整数规划(二元整数规划):对于每个选择,选或者不选,再加上约束,找最优解
    2. 有分支界定法,分支切割法可以精确求解,但是是np难的方法。
    3. 要快一些的话,有如近似算法(Approximation Algorithms),启发式算法(Heuristic Algorithms),遗传算法(Evolution Algorithms, Meta-Heuristic)等等。它们虽然不能求得整数规划的最优解,但是却能在短时间(通常多项式时间)内给出一个较好的可行解。

    组合优化

    和离散优化表达的是一个意思。摘自wiki原文

    Combinatorial optimization is concerned with problems where the set of feasible solutions is discrete or can be reduced to a discrete one.

    凸优化的概念

    简单的测试一个集合是不是凸的,只要任意取集合中的俩个点并连线,如果说连线段完全被包含在此集合中,那么这个集合就是凸集,例如左图所示。
    在这里插入图片描述

    • 凸优化有个非常重要的定理,即任何局部最优解即为全局最优解。

    期刊文献

    https://www.zhihu.com/question/31900230

    展开全文
  • 网络优化连续和离散模型 英文文字版 Dimitri P. Bertsekas
  • 网络优化连续和离散模型 . pdf
  • 本文提出了一种新颖的优化算法,即层次人工蜂群优化算法(HABC),以解决复杂的高维问题。... 针对一组20个连续和离散的基准测试问题进行了实验。 实验结果表明,与其他六种进化算法相比,HABC算法具有出色的性能。
  • 离散连续优化整合matlab程序,可以同时处理包含离散和连续变量的优化问题
  • 优化算法设计-面向离散优化问题构造型启发式改进搜索启发式的需求离散优化启发式特点构造型启发式贪婪构造型启发式算法 启发式的需求 大量的NP难、NP完全问题是几乎可以确定不存在多项式时间的精确算法,必须找...

    优化算法设计-面向离散优化问题构造型启发式和改进搜索

    启发式的需求

    大量的NP难、NP完全问题是几乎可以确定不存在多项式时间的精确算法,必须找合适的方法;很多大型离散优化问题,启发式方法简单、切实可行。

    离散优化

    离散优化:优化模型中决策变量如果存在离散变量,优化模型为离散优化(Discrete Optimization),否则称为连续优化。整数规划就是典型离散优化。

    启发式特点

    启发式方法,不追求一定是最优解(optimal),而是希望获得高质量的可行解(near-optimal feasible),当然,在部分情况下也可能就是得到了最优解 。 本部分关注严格意义上的启发式方法,不追求和精确算法的相似结构,而是基于问题的本身结构,寻找那些最有机会得到最优解、高质量解的办法。启发式方法可能结果很好,不过一般需要“大量的数
    据实例的评估”。

    构造型启发式

    第一类启发式算法为构造型启发式搜索算法,这个方法可以逐步建立一个高质量的解。该算法逐个选择离散决策变量的值,即从部分解开始一次只选择一个决策变量的值,每次迭代中当前决策定的情况下,一个先前自由的变量固定为一个可行数
    值,直到得到一个完整的可行解。

    基础构造型的启发式方法

    1. 初始化。从初始解 x(0) 开始,其全部变量都是待定自由的。设定 t =0。
    2. 逐步操作。选取解 x(t) 的一个自由分量 xp 并对其赋值,使得这个解有可能成为一个好的可行解。然后,x(t) 迭代更新解 x(t+1) ,解 x(t+1) 和 x(t) 除了已经固定的 xp,其他分量相同。
    3. 增量。增加 t = t+1,返回第 1 步。

    以上一个难点在于如何选择下一个待固定的自由变量
    并且确定它的值。贪婪 (greedy) 或短视 (myopic)
    法是解决这一问题最常见的方法。

    贪婪构造型启发式算法

    定义:贪婪构造型启发式算法每次迭代都会选择并固定下一个变量,这种方法在当前临时解的变量已经固定的情况下,使得下一个解能够最大限度地改进目标函数值。极少数情况下,贪婪算法能够保证产生一个精确。由于该算法在进行下次选择时只能依靠局部信息,因此在一般情况下样做存在风险,可能进入可行解空间中非常差区域。贪婪算法计算过程一般十分高效。

    :集合覆盖问题是非常著名的离散优化问题。例如救护车选点规划问题,城市可以分成不同的救护车服务区,每个车站的地点是多个备选点中选出来的,使得尽可能多人口(服务区)得到服务。
    在这里插入图片描述
    城市分 20 服务区,每个站点服务相邻的区,有 10 个备选的车站点。
    决策变量: x j = 1 o r 0 x_j = 1 or 0 xj=1or0
    假定最小化所需站点的总数目(成本系数等于1),模型为:
    m i n ∑ j = 1 10 c j x j = ∑ j = 1 10 x j min \sum_{j=1}^{10}{c_jx_j}=\sum_{j=1}^{10}{x_j} minj=110cjxj=j=110xj
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    :公司希望向多个客户运送需求品,由一个仓库提供货物,安排卡车进行运输。客户只能被卡车一次服务完成,且卡车不能超载。卡车需要往返仓库多次,完成运输。
    在这里插入图片描述
    此问题称为车辆路径问题(vehicle routing problem,VRP),是著名NP-hard问题。
    其数学建模难以非常简洁,本节探讨其构造型启发式
    方法。例如一种方法:

    展开全文
  • 针对炼油过程调度优化离散时间与连续时间建模方法在应用中的局限性,提出一种基于即时交货的离散时间建模方法.该方法总体上采用离散时间表示,通过对成品油交货环节相关部分更加细致的描述,使得交货活动能够在时间...
  • GA求解车间调度问题,遗传算法对所求解的优化问题没有太多的数学要求,由于他的进化特性,搜索过程中不需要问题的内在性质,对于任意形式的目标函数约束,无论是线性的还是非线性的,离散的还是连续的都可处理。
  • 这个全局优化问题可以使用连续离散决策变量进行参数化,并使用基本相同的差分进化 (DE) 方法进行处理,该方法考虑了最近巴塞尔银行监管协议强加的现实世界的约束。 这使我们能够在效率、鲁棒性收敛速度方面对...
  • 分享了樽海鞘优化算法的源代码及原文,亲测有效,欲求更多算法可进入空间查看
  • 2012年的一篇关于多目标跟踪的离散连续优化的论文的源程序,不过运行结果论文的实验结果有点出入,主要是论文中的程序作者进行了修改。
  • 但是大量重要的ILPINLP问题,并不存在多项式时间的解法,因此,启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间空间)下给出待解决组合优化问题每一个实例的一个可行解,该...

    启发式算法(heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。也就是说,在允许运行时长足够长的 情况下,确保得到一个最优方案。但是大量重要的ILP和INLP问题,并不存在多项式时间的解法,因此,启发式算法可以这样定义:一个基于直观或经验构造的算法,在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解,该可行解与最优解的偏离程度一般不能被预计。

    计算机科学的两大基础目标,就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标。 例如它常能发现很不错的解,但也没办法证明它不会得到较坏的解;它通常可在合理时间解出答案,但也没办法知道它是否每次都可以这样的速度求解。

    有时候人们会发现在某些特殊情况下,启发式算法会得到很坏的答案或效率极差,然而造成那些特殊情况的数据组合,也许永远不会在现实世界出现。因此现实世界中启发式算法常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

    启发式算法可分为传统启发式算法和元启发式算法。传统启发式算法包括构造型方法、局部搜索算法、松弛方法、解空间缩减算法等。 元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法、人工鱼群算法、人工蜂群算法、人工神经网络算法等。

    传统启发式算法

    1.构造性启发式算法

    该算法逐个选择离散决策变量的值,直到得到一个完整的可行解位置。该方法从部分解开始,一次只选择一个决策变量的值,经常在完成第一次可行方案时停止。

    基础的构造性搜索算法,从每一个自由决策变量的离散分类开始,在每次迭代中,在当前决策解固定的情况下,一个先前的自由变量固定为一个可行值,也就是说,当我们替换以前的固定值并且采用自由变量时,为新分量所选定的值不应该产生违反约束的情况。在最简单的情况下,当没有自由变量存在时,搜索过程停止。

    构造性搜索的主要难点在于,如何选择下一个待固定的自由变量并且确定它的值,而贪婪或者短视算法是解决这一问题最常见的方法。

    贪婪算法的规则是,在目前已知内容的基础上,选择固定被选中概率最大的变量,从而得到更好的可行解。由于该算法在进行下次选择时只能依靠局部信息,因此在一般情况下这样做存在一定风险,在贪婪算法中一个只有少数变量固定的并且看起来变现很好的解实际上会迫使搜索进入可行空间中非常差的区域。

    实际上,构造性搜索算法更适合求解大规模,并且通常是非线性的高度组合的离散模型或者需要快速求解的情况下,一般采用分支定界,分支切割等。

    2.局部搜索

    在搜索过程中,始终选择当前点的邻居中与离目标最近者的方向搜索。

    算法过程

    (1)随机选择一个初始的可能解x0 ∈D,xb=x0,P=N(xb);
         //D是问题的定义域, xb用于记录到目标位置的最优解,P为xb的邻域。
    (2)如果不满足结束条件,则: 
        //结束条件为循环次数或P为空等
    (3)Begin;
    (4)选择P的一个子集P',xn为P’的最优解 ;      
        //P’可根据问题特点,选择适当大小的子集。可按概率选择
    (5)如果f(xn)<f(xb),则xb=xn,P=N(xb),转(2);    
        //重新计算P,f(x)为指标函数
    (6)否则P=P-P',转(2);
    (7)End;
    (8)输出计算结果;
    (9)结束 ;

    3.爬山法

    将搜索过程比作爬山过程,在没有任何有关山顶的其他信息的情况下,沿着高度增加的方向爬。如果相邻状态没有比当前值更高,则算法停止,认为当前值即为顶峰。

    算法过程

    (1) 设置初始状态n=s0为当前状态;
    (2) 如果当前状态已达标,算法结束,搜索成功;
    (3)获取当前状态n的若干个临近状态m,计算这些h(m), nextn=min{h(m)};
    (4) IF h(n) < h(nextn) 
        THEN  n:=nextn;
        ELSE 取当前状态为最佳状态并退出;
    (5) GOTO (2)步;

    该算法在单峰的条件下,必能达到山顶。 
    显而易见爬山法对于复杂情况的求解会遇到以下问题: 
    (1)局部极值 
    (2)山脊:造成一系列的局部极值 
    (3)高原:平坦的局部极值区域——解决办法:继续侧向移动 
    目前有些改进的爬山法,比如随机爬山法、首选爬山法等等不再细说。它是禁忌搜索(Tabu Search)的基础,TS算法是在其上改进而来。

    元启发式算法(Meta-heuristic Algorithm)

    元启发式算法是启发式算法的改进,是随机算法与局部搜索算法相结合的产物。元启发式是一个迭代生成过程,通过对不同概念的智能组合,该过程以启发式算法实现对搜索空间的探索和开发。在这个过程中,学习策略被用来获取和掌握信息,以有效地发现近似最优解。

    1.禁忌搜索算法

    标记已经解得的局部最优解或求解过程,并在进一步的迭代中避开这些局部最优解或求解过程。局部搜索的缺点在于,太过于对某一局部区域以及其邻域的搜索,导致一叶障目。为了找到全局最优解,禁忌搜索就是对于找到的一部分局部最优解,有意识地避开它,从而或得更多的搜索区域

    (1)给定一个禁忌表(Tabu List)H=null,并选定一个初始解X_now.
    (2)如果满足停止规则,则停止计算,输出结果;否则,在X_now的领域中选出满足不受禁忌的候选集N(X_now).

    在N(X_now)中选择一个评价值最贱的解X_next,X_next:=X_now;更新历史记录H, 重复步骤(2).

     TS算法构成要素:

    (1)编码方式

    将不相同的n件物品分为m组,可以用的编码:

    a、带分隔符的顺序编码

    以自然数1~n分别代表n件物品,n个数加上m-1个分割符号混编在一起,随机排列。如:1-3-4-0-2-6-7-5-0-8-9

    b、自然数编码

    编码的每一位分别代表一件物品,而每一位的值代表该物品所在的分组。如:1-2-1-1-2-2-2-3-3

    (2)初始解的获取

    可以随机给出初始解,也可以事先使用其他启发式等算法给出一个较好的初始解。  

    (3)移动邻域

    移动是从当前解产生新解的途径,例如上述问题中用移动s产生新解s(x)。从当前解可以进行的所有移动构成邻域,也可以理解为从当前解经过“一步”可以到达的区域。

    (4)禁忌表

    禁忌表的作用:防止搜索出现循环

    a.记录前若干步走过的点、方向或目标值,禁止返回

    b.表是动态更新的

    c.表的长度称为Tabu-Size

    禁忌表的主要指标(两项指标)

    禁忌对象:禁忌表中被禁的那些变化元素

    禁忌长度:禁忌的步数

    禁忌对象(三种变化)

    以状态本身或者状态的变化作为禁忌对象

    以状态分量以及分量的变化作为禁忌对象

    采用类似的等高线做法,以目标值变化作为禁忌对象

    禁忌长度:可以是一个固定的常数(T=c),也可以是动态变化的,可按照某种规则或公式在区间内变化。

    禁忌长度过短,一旦陷入局部最优点,出现循环无法跳出;
    禁忌长度过长,候选解全部被禁忌,造成计算时间较大,也可能造成计算无法继续下去。
    (5)渴望水平函数

    A(x,s)一般为历史上曾经达到的最好目标值,若有C(s(x))<A(x,s)则S(x)是不受T表限制。即使s(x)∈T,仍可取 x=s(x)。A(x,s)称为渴望水平函数。

    (6)停止准则

    a.给定最大迭代步数(最常用 )

    b.设定某个对象的最大禁忌频率。

    c.设定适配值的偏离阈值。

    对搜索性能有影响的因素:
    禁忌长度
    控制其他变量,单就禁忌长度的选择而言,禁忌长度越短,机器内存占用越少,解禁范围更大(搜索范围上限越大),但很容易造成搜索循环(实际去搜索的范围却很小),过早陷入局部最优。禁忌长度过长又会导致计算时间过长。

    特赦规则
    通俗定义:对于在禁忌的对象,如果出现以下情况,不论现在对象的禁忌长度如何,均设为0 
    (1)基于评价值的规则,若出现一个解的目标值好于前面任何一个最佳候选解,可特赦; 
    (2)基于最小错误的规则,若所有对象都被禁忌,特赦一个评价值最小的解; 
    (3)基于影响力的规则,可以特赦对目标值影响大的对象。

    候选集
    候选集的大小,过大增加计算内存和计算时间,过小过早陷入局部最优。候选集的选择一般由邻域中的邻居组成,可以选择所有邻居,也可以选择表现较好的邻居,还可以随机选择几个邻居。

    评价函数
    评价函数分为直接评价函数和间接评价函数。 
    直接评价函数:上述例子,均直接使用目标值作为评价函数。 
    间接评价函数:反映目标函数特性的函数(会比目标函数的计算更为简便,用以减少计算时间等)。

    终止规则
    禁忌算法是一个启发式算法,我们不可能让搜索过程无穷进行,所以一些直观的终止规则就出现了 
    (1)确定步数终止,无法保证解的效果,应记录当前最优解; 
    (2)频率控制原则,当某一个解、目标值或元素序列的频率超过一个给定值时,终止计算; 
    (3)目标控制原则,如果在一个给定步数内,当前最优值没有变化,可终止计算。

    2.模拟退火(SA,Simulated Annealing)

    爬山法是完完全全的贪心法,每次都鼠目寸光的选择一个当前最优解,因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。

    模拟退火算法描述
            若J( Y(i+1) )>= J( Y(i) )  (即移动后得到更优解),则总是接受该移动

            若J( Y(i+1) )< J( Y(i) )  (即移动后的解比当前解要差),则以一定的概率接受移动,而且这个概率随着时间推移逐渐降低(逐渐降低才能趋向稳定)

      这里的“一定的概率”的计算参考了金属冶炼的退火过程,这也是模拟退火算法名称的由来。

      根据热力学的原理,在温度为T时,出现能量差为dE的降温的概率为P(dE),表示为:P(dE) = exp( dE/(kT) )

      其中k是一个常数,exp表示自然指数,且dE<0。这条公式说白了就是:温度越高,出现一次能量差为dE的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于dE总是小于0(否则就不叫退火了),因此dE/kT < 0 ,所以P(dE)的函数取值范围是(0,1) 。

      随着温度T的降低,P(dE)会逐渐降低。

    使用模拟退火算法解决旅行商问题
    旅行商问题 ( TSP , Traveling Salesman Problem ) :有N个城市,要求从其中某个问题出发,唯一遍历所有城市,再回到出发的城市,求最短的路线。

    旅行商问题属于所谓的NP完全问题,精确的解决TSP只能通过穷举所有的路径组合,其时间复杂度是O(N!) 。

    使用模拟退火算法可以比较快的求出TSP的一条近似最优路径。

    模拟退火解决TSP的思路:

    a. 产生一条新的遍历路径P(i+1),计算路径P(i+1)的长度L( P(i+1) )

    b. 若L(P(i+1)) < L(P(i)),则接受P(i+1)为新的路径,否则以模拟退火的那个概率接受P(i+1) ,然后降温

    c. 重复步骤1,2直到满足退出条件。

    产生新的遍历路径的方法有很多,下面列举其中3种:
    a. 随机选择2个节点,交换路径中的这2个节点的顺序。

    b. 随机选择2个节点,将路径中这2个节点间的节点顺序逆转。

    c. 随机选择3个节点m,n,k,然后将节点m与n间的节点移位到节点k后面。

    3.遗传算法

    遗传算法(Genetic Algorithm, GA)起源于对生物系统所进行的计算机模拟研究。它是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法,借鉴了达尔文的进化论和孟德尔的遗传学说。其本质是一种高效、并行、全局搜索的方法,能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最佳解。

    相关术语

    编码(coding):将物体的表现型用编码的方式转为程序可控的基因型。

    比如现在要计算北京、天津、广东、新疆这四个城市的一条最优路径,但算法程序不能够直接处理北京、天津、广东、新疆这些数据,所以我们得给它们编上号,北京(0)、天津(1)、广东(2)、新疆(3),路径(天津->新疆->北京->广东)可以表示成基因型串结构数据 (1302),这样算法程序只要直接处理它们的编号就行了。
    (1)二进制编码,基因用0或1表示(常用于解决01背包问题)

    如:基因A:00100011010 (代表一个个体的染色体)
    (2)互换编码(用于解决排序问题,如旅行商问题和调度问题)

    如旅行商问题中,一串基因编码用来表示遍历的城市顺序,如:234517986,表示九个城市中,先经过城市2,再经过城市3,依此类推。
    解码(decoding):基因型到表现型的映射。

    基因型(genotype):参数的因子;

    表现型(phenotype):根据不同因子最终展现的形态;

    适应度(fitness):度量某个结果的好坏。

    进化(evolution):不断剔除差的结果,最终逐步留下好的结果。

    选择(selection):以一定的概率从种群中选择若干个个体留下,并繁殖。选择过程是一种基于适应度的优胜劣汰的过程。

    复制(reproduction):将父本、母本的基因复制,以便产生下一代。

    交叉(crossover):两个染色体的某一相同位置处DNA被切断,前后两串分别交叉组合形成两个新的染色体。也称基因重组或杂交;

    (1)单交叉点法 (用于二进制编码)

    选择一个交叉点,子代在交叉点前面的基因从一个父代基因那里得到,后面的部分从另外一个父代基因那里得到。如:交叉前00000|01110000000010000
    ​11100|00000111111000101
    ​交叉后:
    ​00000|00000111111000101
    ​11100|01110000000010000
    ​(2)双交叉点法 (用于二进制编码)
    ​选择两个交叉点,子代基因在两个交叉点间部分来自一个父代基因,其余部分来自于另外一个父代基因.
    ​如:交叉前:
    ​01 |0010| 11
    ​11 |0111| 01
    ​交叉后:
    ​11 |0010| 01
    ​01 |0111| 11
    ​(3)基于“ 与/或 ”交叉法 (用于二进制编码)
    ​对父代按位"与”逻辑运算产生一子代A;按位”或”逻辑运算产生另一子代B。该交叉策略在解背包问题中效果较好 .
    ​如:交叉前:
    ​01001011
    ​11011101
    ​交叉后:
    ​01001001
    ​11011111
    ​(4)单交叉点法 (用于互换编码)
    ​选择一个交叉点,子代的从初始位置出发的部分从一个基因复制,然后在另一个基因中扫描,如果某个位点在子代中没有,就把它添加进去。
    ​如:交叉前:
    ​87213 | 09546
    ​98356 | 71420
    ​交叉后:
    ​87213 | 95640
    ​98356 | 72104
    ​(5)部分匹配交叉(PMX)法(用于互换编码)
    ​先随机产生两个交叉点,定义这两点间的区域为匹配区域,并用交换两个父代的匹配区域。
    ​父代A:872 | 130 | 9546
    ​父代B:983 | 567 | 1420    变为:
    ​TEMP A: 872 | 567 | 9546
    ​TEMP B: 983 | 130 | 1420
    ​对于 TEMP A、TEMP B中匹配区域以外出现的数码重复,要依据匹配区域内的位置逐一进行替换。匹配关系:1<——>5 3<——>6 7<——>0
    ​子代A:802 | 567 | 9143
    ​子代B:986 | 130 | 5427
    ​(6)顺序交叉法(OX) (用于互换编码)
    ​从父代A随机选一个编码子串,放到子代A的对应位置;子代A空余的位置从父代B中按B的顺序选取(与己有编码不重复)。同理可得子代B。
    ​父代A: 872 | 139 | 0546
    ​父代B: 983 | 567 | 1420
    ​交叉后:
    ​子代A: 856 | 139 | 7420
    ​子代B: 821 | 567 | 3904
    ​(7)循环交叉(CX)(用于互换编码)
    ​CX同OX交叉都是从一个亲代中取一些城市,而其它城市来自另外一个亲代,但是二者不同之处在于:OX中来自第一个亲代的编码子串是随机产生的,而CX却不是,它是根据两个双亲相应位置的编码而确定的。
    ​父代A:1 2 3 4 5 6 7 8 9
    ​父代B:5 4 6 9 2 3 7 8 1
    ​可得循环基因:1->5->2->4->3->6->9->7->8
    ​子代B的编码同理。(循环基因 5->1->4->2->6->3->9->7->8)
    变异(mutation):交叉后可能(很小的概率)对染色体进行更改,来防止算法过早收敛而陷入局部最优解中。

    变异概率Pm不能太小,这样降低全局搜索能力;也不能太大,Pm > 0.5,这时GA退化为随机搜索。

    (1)基本位变异算子(用于二进制编码)

    基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体,若需要进行变异操作的某一基因座上的原有基因值为0,则变异操作将其变为1;反之,若原有基因值为1,则变异操作将其变为0。

    变异前:000001110000000010000

    变异后:000001110001000010000

    (2)逆转变异算子(用于互换编码)(源代码中使用类似此方法)

    在个体中随机挑选两个逆转点,再将两个逆转点间的基因交换。

    变异前:1346798205

    变异后:1246798305

    个体(individual):指染色体带有特征的实体;

    种群(population):个体的集合,该集合内个体数称为种群的大小

    遗传算法步骤
    对潜在问题进行编码,初始化基因组,并根据基因组随机初始化种群,并指定繁衍代数。

    计算种群中每个个体的适应度,选择一定数目的留下,其余淘汰。

    在留下的个体中,随机繁衍,对分母基因进行交叉(极小概率变异),产生下一代。

    回到第2步进行循环。直到达到指定的繁衍代数

    4.蚁群优化算法

    简单介绍一下蚁群算法的思路。我们尝试复原一下蚂蚁寻找食物的场景。想象有一只蚂蚁找到了食物,这时它需要将食物带回蚁穴。对于这一只蚂蚁而言,它显然并不知道应该怎么走。那么,这只蚂蚁有可能会随机选择一条路线。

    这条路线很可能是一条远路。但是,蚂蚁一路上留下了记号,也就是信息素。如果这只蚂蚁继续不停地搬运食物,或者有许多其他蚂蚁一块搬运的话。他们总会在运气好的时候走到更快往返的路线上。蚂蚁选择的路越好,相同时间内往返的次数也就更多,也就在路上留下了更多的信息素。

    于是,蚂蚁们总会发现,有一些路径的信息素更浓,这些路径就是更好的路线。于是蚂蚁也就更多地向信息素更浓的路径上偏移。蚂蚁们不停重复这个过程,最终总能找到一条确定的路线,而这条路线就是蚂蚁们找到的最优路径。

    蚁群算法步骤
    初始化蚂蚁数量、可行路段、每条路段距离、每条路段的初始信息素大小等信息

    设定蚂蚁的起点、终点。

    蚂蚁从起点出发根据信息素浓度,有一定的概率性选择路段,浓度越高,概率越大,逐步回到终点。

    在蚂蚁走过的路径上,根据每条路段的长度按比例释放信息素,短的路段释放的信息素多,长的路段释放的信息素少。

    对所有路段的信息素进行挥发。

    回到第二步进行循环,直到蚂蚁数量迭代完。

    5.粒子群优化算法

    粒子群算法是模拟群体智能所建立起来的一种优化算法,粒子群算法可以用鸟类在一个空间内随机觅食为例,所有的鸟都不知道食物具体在哪里,但是他们知道大概距离多远,最简单有效的方法就是搜寻目前离食物最近的鸟的周围区域。所以,粒子群算法就是把鸟看成一个个粒子,并且他们拥有位置和速度这两个属性,然后根据自身已经找到的离食物最近的解和参考整个共享于整个集群中找到的最近的解去改变自己的飞行方向,最后我们会发现,整个集群大致向同一个地方聚集。而这个地方是离食物最近的区域,条件好的话就会找到食物。这就是粒子群算法。

    算法描述   
    所以,我们需要一个pbest来记录个体搜索到的最优解,用gbest来记录整个群体在一次迭代中搜索到的最优解。速度和粒子位置的更新公式如下:

        v[i] = w * v[i] + c1 * rand() *(pbest[i] - present[i]) + c2 * rand() * (gbest - present[i])    

        present[i]=present[i]+v[i]                                                      

        其中v[i]代表第i个粒子的速度,w代表惯性权值,c1和c2表示学习参数,rand()表示在0-1之间的随机数,pbest[i]代表第i个粒子搜索到的最优值,gbest代表整个集群搜索到的最优值,present[i]代表第i个粒子的当前位置。

    标准PSO算法的流程:
      Step1:初始化一群微粒(群体规模为m),包括随机位置和 速度;

      Step2:评价每个微粒的适应度;

      Step3:对每个微粒,将其适应值与其经过的最好位置 pbest作比较,如果较好,则将其作为当前的 最好位置pbest;

      Step4:对每个微粒,将其适应值与其经过的最好位置 gbest作比较,如果较好,则将其作为当前的 最好位置gbest;

      Step5:根据(2)、(3)式调整微粒速度和位置;

      Step6:未达到结束条件则转Step2。

    6.人工鱼群算法

    在一片水域中,鱼往往能自行或尾随其他鱼找到营养物质多的地方,因而鱼生存数目最多的地方一般就是本水域中营养物质最多的地方,人工鱼群算法就是根据这一特点,通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为,从而实现寻优。

    以下是鱼的几种典型行为:

    (1)觅食行为:一般情况下鱼在水中随机地自由游动,当发现食物时,则会向食物逐渐增多的方向快速游去。

    (2)聚群行为:鱼在游动过程中为了保证自身的生存和躲避危害会自然地聚集成群,鱼聚群时所遵守的规则有三条:

    分隔规则:尽量避免与临近伙伴过于拥挤;

    对准规则:尽量与临近伙伴的平均方向一致;

    内聚规则:尽量朝临近伙伴的中心移动。

    (3)追尾行为:当鱼群中的一条或几条鱼发现食物时,其临近的伙伴会尾随其快速到达食物点。

    (4)随机行为:单独的鱼在水中通常都是随机游动的,这是为了更大范围地寻找食物点或身边的伙伴。

    特点:

    1)具有较快的收敛速度,可以用于解决有实时性要求的问题;

    2)对于一些精度要求不高的场合,可以用它快速的得到一个可行解;

    3)不需要问题的严格机理模型,甚至不需要问题的精确描述,这使得它的应用范围得以延伸。

    停止条件:

    1) 判断连续多次所得的均方差小于允许的误差;

    2)判断某个区域的人工鱼群的数目达到某个比率;

    3)连续多次所获取的值均不能超过已找到的极值。

    4)迭代次数达到预设次数

    7.人工蜂群算法

    为了解决多变量函数优化问题Karaboga在2005年提出了人工蜂群算法ABC模型。

    1、 蜜蜂采蜜机理

    蜜蜂是一种群居昆虫,虽然单个昆虫的行为极其简单,但是由单个简单的个体所组成的群体却表现出极其复杂的行为。真实的蜜蜂种群能够在任何环境下,以极高的效率从食物源(花朵)中采集花蜜;同时,它们能适应环境的改变。

    蚁群产生群体智慧的最小搜索模型包含基本的三个组成要素:食物源、被雇佣的蜜蜂和未被雇佣的蜜蜂。两种最基本的行为模型:为食物源招募蜜蜂和放弃某个食物源。

    (1) 食物源

    食物源的价值由多方面因素决定,如:离蜂巢的远近、包含花蜜的丰富程度和获得花蜜的难易程度。使用单一的参数,食物源的“收益率”来代表以上各个因素。

    (2) 被雇佣的蜜蜂

    也称引领蜂,其与所采集的食物源一一对应。引领蜂储存有食物源的相关信息(相对与蜂巢的距离、方向和食物源的丰富程度等)并把这些信息以一定的概率与其他蜜蜂分享。

    (3) 未被雇佣的蜜蜂

    其主要任务是寻找和开采食物源。有两种未被雇佣的蜜蜂:侦查蜂和跟随蜂。侦查蜂搜索附近的新食物源;跟随蜂等在蜂巢里面并通过与引领蜂分享相关信息找到食物源。一般情况下,侦查蜂的数量是蜂群的5%--20%

    在群体智慧形成过程中,蜜蜂间交换信息是最重要的一环。舞蹈区是蜂巢中最为重要的信息交换地。蜜蜂的舞蹈也叫摇摆舞。食物源的信息在舞蹈区通过摇摆舞的形式与其他蜜蜂共享,引领蜂通过摇摆舞的持续时间等来表现食物源的收益率,故跟随蜂可以观察到大量的舞蹈并依据收益率来选择到哪个食物源采蜜。收益率与食物源被选择的可能性成正比。因而,蜜蜂被招募到一个食物源的概率与食物源的收益率成正比。

    初始时刻,蜜蜂以侦查蜂的方式搜索。其搜索可以由系统的先验知识决定,也可以完全随机。经过一轮侦查后,若蜜蜂找到食物源,蜜蜂利用它本身的存储能力记录位置信息并开始采蜜。此时,蜜蜂将称为“被雇佣者”。蜜蜂在食物源采蜜后回到蜂巢卸下蜂蜜,然后将有如下选择:

    (1) 放弃食物源而成为非雇佣蜂;

    (2) 跳摇摆舞为所对应的食物源招募更多的蜜蜂,然后回到食物源采蜜;

    (3) 继续在食物源采蜜而不进行招募。

    对于非雇佣蜂有如下选择:

    (1) 转变为侦查蜂并搜索蜂巢附近的食物源,其搜索可以由先验知识决定也可以完全随机;

    (2) 在观察完摇摆舞以后,被雇佣成为跟随蜂,开始搜索对应食物源领域并采蜜。

    2、 ABC算法原理

    在基本ABC算法中,人工蜂群包含三种个体:雇佣蜂、观察蜂和侦查蜂

    每个雇佣蜂对应一个确定的蜜源(解向量),并在迭代中对蜜源的领域进行搜索。

    根据蜜源的丰富程度(适应值的大小)采用轮盘赌的方式雇佣观察蜂采蜜(搜索新蜜源)

    如果蜜源多次更新没有改进,则放弃该蜜源,雇佣蜂转为侦查蜂随机搜索新蜜源。

    (1) 随机初始化

    (2) 新蜜源的更新搜索公式

    (3) 观察蜂选择雇佣蜂的概率

    (4) 侦查蜂的产生

    为了防止算法陷入局部最优,当蜜源迭代limit次没有改进时,便放弃该蜜源,并且将该蜜源记录在禁忌表中,同时该蜜源对应的雇佣蜂转变为侦查蜂按式(1)随机产生一个新的位置代替原蜜源。

    3、 控制参数

    (1) 蜜源的个数(与雇佣蜂或观察蜂相等)SN

    (2) 算法终止的最大进化数(maximum evaluation number)MEN

    (3) Limit

    基本ABC算法的流程为

    (1) 根据式(1)初始化种群解xi,i=1,2,…,SN;

    (2) 计算种群中各蜜蜂的适应值

    (3) cycle=1

    (4) repeat

    (5) 雇佣蜂根据(2)产生新的解vi并计算适应值

    (6) 雇佣蜂根据贪心策略选择蜜源

    (7) 根据(3)式计算选择蜜源xi的概率pi

    (8) 观察蜂根据概率pi选择蜜源xi,根据(2)式在该蜜源附近产生新的蜜源vi,并计算新蜜源vi的适应值

    (9) 观察蜂根据贪心算法选择蜜源

    (10) 决定是否存在需要放弃的蜜源,如果存在,根据(1)式随机产生一个蜜源代替它

    (11) 记录最优解

    (12) cycle = cycle + 1

    (13) until cycle=MCN

    4、 算法可能的改进方式

    (1) 新蜜源的搜索领域(2)式的改进(如:其他拓扑邻域)

    (2) 观察蜂选择雇佣蜂的概率(3)式的改进(如:动态的)

    8.人工神经网络算法

    这里不用多说了。

    总结:

    启发式算法蕴含着许多人生哲学,它虽不是数学方法,其思想更类似于人类解决问题的思想和一些人生中总结的道理,值得好好体会。最后用网上一段描述局部搜索的例子来作为总结:

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

    · 兔子朝着比现在高的地方跳去。他们找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是Iterative Improvement,它不能保证局部最优值就是全局最优值。

    ·兔子喝醉了。他随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,他渐渐清醒了并朝最高方向跳去。这就是模拟退火。

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

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

    参考:https://blog.csdn.net/zj15527620802/article/details/82121414 

    展开全文
  • 针对当网络使用睡眠调度并且节点的传输功率连续可调节时的最小功率广播调度问题,首先给出了一种计算节点内部最优发送调度的递归方法,然后提出了一种构造最小功率广播调度的离散粒子群算法。该算法搜索最优广播树...
  • 为了满足连续性,提出了一种改进的优先级解码方法,该方法适用于火车成对运行的任何情况,用于生成初始种群并将个人解码为轮换列车承担的运行任务。 为了将差分进化算法应用于组合优化问题,提出了基于群论的随机...
  • 利用罚函数处理离散变量,将混合离散优化问题*,转化为连续变量优化问题*。为了解决标准PSO可能陷入局部最优解而存在早熟收敛的问题,本文构造微粒的邻域结构,利用禁忌搜索(TS)算法具有较强的“爬山”能力的特点...
  • 粒子群算法优化不同维数的连续函数以与离散函数的最小值问题.doc
  • 解决了在一般工程结构设计实践中,多采用连续变量优化设计加圆整的办法得到近似的离散型结果.然而对高精度要求的工程结构,该方法的计算结果往往与实际相差较大.通过钻井用大型车装井架的实例计算表明,所提出的...
  • 针对蚁群算法只适用于离散优化问题的局限性收敛速度慢的问题,提出一种适合连续优化的量子蚁群算法。该方法直接采用量子位的相位对蚂蚁编码。首先根据基于信息素强度可见度构造的选择概率,选择蚂蚁的前进目标;...
  • 信号传播过程中因障碍物阻挡产生的阴影衰落对无线传感器网络的覆盖产生较大的影响。针对无线传感器网络的完全覆盖问题,基于自由空间环境下的规则部署方式,推导出在衰落阴影环境下,完全覆盖网络监测区域所需的最少...
  • 离散空间问题求解的蚁群算法引入连续空间, 针对多目标优化问题的特点, 提出一种用于求解带有约束 条件的多目标函数优化问题的蚁群算法. 该方法定义了连续空间中信息量的留存方式蚂蚁的行走策略, 并将信息...
  • 对影响预应力钢桁架优化设计的2类变量,包括连续的索力值和离散的截面尺寸进行研究。建立了以应力结构质量为约束条件、以最小化结构应变能为目标函数的数学优化模型。以杆件在预应力外荷载共同作用下储存应变能...
  • 将电力电子系统的最优控制问题变换为参数最优化问题。以正激开关稳压电源为例,建立其控制器小信号离散参数最...用SPICE-2仿真,比较了用连续离散两种非线性优化算法设计的正激开关电源瞬态响应及频率特性.
  • 离散空间问题求解的蚁群算法引入连续空间,针对多目标优化问题的特点,提出一种用于求解带有约束条件的多目标函数优化问题的蚁群算法。该方法定义了连续空间中信息量的留存方式蚂蚁的行走策略,并将信息素交流...
  • 通过δ 算子离散化模型,研究了连续时间线性定常随机系统的具有极点配置稳态方差指标的满意控制问题。利用线性矩阵不等式理论,给出设计满意控制器及优化采样周期的方法。数值算例验证了所提出方法的有效性。
  • 该算法基于量子态波函数描述微粒群粒子位置,结合遗传算法中的交叉、变异操作,采用随机键编码方法对连续空间内的解进行离散化,使得DQPS0能够直接用于求解车间生产调度这类组合优化问题.另外,针对JSP的复杂性,...
  • StochSD(随机系统动力学)是一个独特CSS软件包,用于连续离散以及组合的建模和仿真。 StochSD通过将离散对象建模为连续对象消除了许多问题和错误。... 灵敏度分析,优化和统计分析的工具是StochSD的一部分。
  • 仿真优化方法是离散事件动态系统研究的一种有效工具。对离散事件动态系统研究的仿真优化方法的最新进展进行了综述。根据仿真输入参数,分为连续参数方法和离散参数方法两种进行讨论。
  • 为解决连续属性无法直接用于粗糙集理论的问题,依据粗糙集连续属性离散化的根本要求,提出了一种基于二进制粒子群优化算法(Binary Particle Swarm Optimization,Binary PSO)的属性离散化方法。该方法将二进制粒子视...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,642
精华内容 20,256
关键字:

离散优化和连续优化

友情链接: jvrmlzipa.rar