TPSO-DSDT粒子群算法在三维装箱问题上的应用

发布时间 2023-05-23 16:14:00作者: 多见多闻

组合算法是将传统启发式算法与数学规划算法结合元启发式算法共同工作进行相应的计算,还有融合多种算法所获得的计算方法,结合了所有算法自身的有点,规避其自身缺点从而达到解决装箱问题的最终目的。

现在,组合算法的整体规划绝大多数都是通过启发式算法完成的,局部优化的过程采用的是人工智能算法或数学规划。靳志宏[16]等基于货物承载力的限制设计建造了混合整数规划的优化集装箱装载方案,计算方法中融合了启发式算法以及预分配策略遗传算法,二者之间混合交互。

张德富等提出一种启发式算法和混合模拟退火算法相结合的组合算法,加入了“块”的思想,大大提高了装箱填充率。

何琨等设计了一种改进动作空间穴度为基础的算法,有机的将数学规划法以及启发式算法融合在一起,具体包含两部分,分别是:邻域搜索算法以及构造型算法,这里面构造型算法的主要责任是选择捆绑货物,将货物捆成一个大型长方体块,邻域搜索算法的处理是基于构造型算法进行的。

游伟等对解决三维装箱问题的偏随机秘钥混合遗传算法进行了完整的分析研究,这种方式对于求解三维装箱问题的时候比较容易暴露自己局部最优的缺陷,搜索货物装载序列通过偏随机秘钥遗传算法,优化货物布局通过启发式算法。

朱莹构造了一种包含动态空间划分的启发式算法,设计了两段实数遗传编码,在多目标多约束条件的装箱问题中取得了较明显的优化效果。

TPSO-DSDT粒子群算法

是一种基于群体智能的优化算法,它是将TPSO方法和DSDT方法相结合的一种优化算法。TPSO-DSDT粒子群算法通常用于解决多维、具有复杂非线性约束条件的高维优化问题。

在TPSO-DSDT粒子群算法中,优化问题可以被描述为一个多维函数的最大化或最小化问题。优化过程中,群体中的每个粒子代表一个可能的解决方案,而粒子的适应度则对应着优化目标函数的值。TPSO-DSDT粒子群算法通过不断调整粒子的位置和速度,以期望找到最小化或最大化目标函数的最优解。

TPSO-DSDT粒子群算法中,粒子是基于建立在TPSO方法和DSDT方法之上的模型来演化的。通过TPSO方法,粒子的位置和速度经常进行更新,以获取更好的解决方案。DSDT方法用来实现某些限制条件的纠正和微调,该方法能够自动调整群体中每个粒子的位置和速度,以确保所有解决方案都满足约束条件。

总的来说,TPSO-DSDT粒子群算法是一种能够解决高维优化问题的自适应算法,它结合了TPSO方法和DSDT方法两种技术的优点,提供了一个可靠的优化工具,用于解决实际的应用问题。

静态网结构通过调整参数的方式改善了算法的优化性能,不过静态网络这一结构对于算法演化的全过程里面不同粒子间具备的交互关系起到决定性的影响,如果不计粒子对应的适应性可能随着算法的演化而发生的变化,很难反映生物个体的趋利避害行为。通过动态群体拓扑结构,动态调整交互式对象的适应度,并对应选取与优势点最接近你的粒子,进而让优势点能够更加趋近于优势点,继而将不同粒子间存在的动态交互情况更显著的反应出来。这样就构建出能够将大自然优胜劣汰以及个体生物趋利避害的现象反应出来动态拓扑结构。首先,通过粒子适应度对节点与加边的构建与删除处理进行设计,构建以节点与加边改变为基础的动态拓扑结构;然后采用动态调整前适应度判断和动态调整时适应度判断相结合的方法,提出了双重判断动态拓扑粒子群算法;最后一步就是测试改进算法具体的收敛速度与寻优性能,同时和标准的TPSO与PSO算法展开对比,进而证明改进算法是否具有较高的有效性。

通过构建有向自组织动态拓扑结构,使算法能更真实地反映生物个体进化过程中趋利避害的本质。在搜索过程中,粒子都会选择向具有良好适应值的粒子学习,在每次搜索后,首先对群体中每一个粒子的适应值进行排序,以保留最佳适应值的粒子结构,其次采用节点度值进行选取,度值大的进行重构、加边,否则进行重构减边,然后,让有很好适应能力的节点有更多创建新学习对象的机会,如果在整个结构里面选取的学习对象是适应度较好的节点,也就是通过全局择优这一手段来完成加边操作,对于相邻节点的邻接点,选择适应度好的节点作为学习对象,即采用局部择优的方法对节点进行加边。
拓扑结构演化步骤:
(1) 群体拓扑的初始化处理:把含有粒子数量为N的群体拖布进行初始化处理,得到相距最近的邻耦合网络结构,也就是各粒子和其相邻的k/2 个粒子连接在一起,这里面粒子数量共为k = 2个;之后,于算法的每次迭代中执行以下操作:
(2) 计算每一个粒子适应值,并保持最佳粒子的拓扑不变;
(3) 将粒子当前的出度值与目标出度值进行比较,如果出度值小于目标出度值,则进行(4)、(5);
(4) 重新连接有向边:按照节点重构的理论将新粒子o引入拓扑结构,同时把其和原有节点进行连接,那么选取到j节点进行连接的几率大小是Ps t ;
(5) 加边处理:对各粒子具备的加边几率Pea t )( i=1,2, , ……N) 进行计算,按照概率进行选取,对粒子i进行选取;之后利用概率 p构建部分择优边(i, j),这时选取粒子 j的几率大小是Pl t ;相反,构建的整体择优边(i, j),粒子 j被选择的概率为Pg t  ;
(6) 比较粒子当前的出度值和目标出度值的大小,如果出度值大于目标出度值执行(6)、(7)否则执行(3)、(4);
(7) 重新连接有向边:按照节点重构的理论将新粒子o引入拓扑结构,同时把其和原有节点进行连接,那么选取到j节点进行连接的几率大小是 Ps t ;
(8) 减边处理:按照节点删除理论对粒子e进行d概率的删除操作,同时将和其相连的全部边进行删除处理;
(9) 判断结束条件:若没有达到设定的最大迭代次数,返回(2)或者(6),否则,结束演化。

TPSO粒子群算法

是一种智能算法,用于优化多元非凸函数。与其他常见的优化算法,如遗传算法和神经网络算法等相比,TPSO算法具有较高的收敛速度和稳定性。

在TPSO算法中,一组粒子分布在搜索空间中,每个粒子都表示一个潜在解。粒子之间通过交换信息,共同探索搜索空间,并迭代调整其位置和速度,以寻找最佳解。更具体地说,TPSO算法有以下步骤:

1.初始化粒子群:假设粒子群的大小为N,每个粒子初始化时随机生成一组状态,包括位置和速度。

2.计算适应度:定义优化函数,根据给定的目标函数计算每个粒子的适应度。适应度是衡量该粒子在该位置的性能的评价指标。

3.更新速度和位置:根据当前位置和速度的信息,对每个粒子进行调整,并在搜索空间中移动它们,以期望获得更好的解决方案。

4.更新全局最优解:对于每个粒子,如果它的位置最优,则将其作为全局最优解。

5.循环迭代:将步骤2-4循环迭代一定的次数或直到达到停止准则(例如达到目标函数阈值或达到最大迭代次数)。

整个TPSO算法的关键点是上述三个操作:初始化、迭代和更新。这些操作都可以根据具体问题,合理地确定参数和实现细节,以达到更好的优化效果。

DSDT粒子群算法

是一种全新的智能优化算法,是Discrete Small Decision Tree(离散小决策树)结合粒子群算法的一种优化方法。其核心是将粒子群算法的思想引入决策树的离散化过程中,通过粒子不断地移动来生成一颗最优的决策树。

DSDT粒子群算法与传统的决策树分类器相比,具有以下优点:

1.能处理离散型、连续型的数据。

2.具有较强的自适应性和泛化能力。

3.分类效果好,且易于理解和解释。

DSDT粒子群算法的主要步骤如下:

1.初始化粒子群的位置和速度。

2.根据粒子的位置,生成决策树。

3.根据粒子的适应度,更新粒子的速度和位置。

4.重复步骤2和3,直到满足收敛条件。

在DSDT粒子群算法中,每个粒子代表一颗决策树,每棵决策树都由多个决策节点构成。图像处理中,决策树可以表示为一个二维数组,每个节点表示为一个元素,元素可以表示为类别标签、阈值或某种特定条件。

DSDT粒子群算法通过粒子不断地移动,来找到最优的决策树。其中,每个粒子都有一个适应度值,表示该粒子对应的决策树的分类准确率。每次更新粒子的速度和位置时,需要考虑全局最优解和局部最优解的影响,以保证算法达到全局最优解。

总的来说,DSDT粒子群算法是一种高效的优化算法,可用于处理许多实际问题,例如数据挖掘、模式分类、图像处理等。