基于改进K-means聚类和遗传算法的混合算法求解异构车辆路径问题

由于目前单一车型配送存在资源浪费和效率低下等问题,选取确定数量的不同车型对各客户点进行配送服务往往可以得到更优的配送路径方案。针对这一点,描述了一种异构车辆路径问题,并建立了具有固定车辆数且考虑固定成本、可变成本以及时间窗惩罚成本的混合整数规划模型。同时,提出了一种基于改进K-means聚类和遗传算法的混合算法对模型进行求解。实验仿真先求解不考虑时间窗的问题初步证明混合算法的有效性,再在带时间窗的问题中求解不同规模算例的单一及异构车型结果,以证明异构车型配送更优。最后,对该混合算法的求解结果与其他混合算法的求解结果进行对比分析,证明了混合算法的优越性。研究结果表明:该混合算法求解的异构车型结果优于单一车型,并且比其他混合算法求解的异构车型结果更优,异构车辆配送使用的配送车辆数更少,总成本也更低,该混合算法具有更好的效率和性能。

基于混合差分遗传算法的聚类车辆路径问题研究

针对所有客户被预先分配给若干聚类的聚类车辆路径问题,建立了相应的整数规划模型,提出基于差分进化和遗传算法的两级混合算法。在聚类层,运用差分进化算法进行优化,染色体基于聚类编号进行编码,采用扫描算法初始化种群,结合聚类层的编码特点,设计了基于升序排列的变异算子,在交叉环节考虑传统差分进化算法的缺陷,设计了考虑聚类服务数和装载率的混合交叉算子;在客户层,运用遗传算法进行优化,染色体基于客户编号进行编码,交叉策略采用基因子段的整体交叉,变异时采用位置交换、逆序、插入等策略。最后,利用标准测试库中的实例进行仿真,并与已知最优值进行对比分析,结果表明,算法具有一定的可行性和有效性。

一种基于遗传算法的混合聚类技术

模糊Ｃ－ 均值算法是一种比较有的数据聚类方法，然而在聚类数不能事先确定，或样本空间太大时，聚类非常困难。遗传算法是一种借鉴生物界自然选择和自然遗传机制的高度并行、随行、自适应的搜索算法。将遗传算法与模糊聚类技术结合起来，提出一种混合聚类的方案。该方案能够快速正确的实现聚类，且不需事先认定聚类数。实验结果令人满意。

遗传+模糊C-均值混合聚类算法

本文提出了一种新的结合遗传算法(GA)和模糊C^-均值算法(FCM)的混合聚类算法(HCA)。它通过对问题的解空间交替进行全局和局部搜索,达到快速收敛至全局最优解,较好地解决了GA在达到全局最优解前收敛慢和FCM算法容易陷入局部极小的问题。三组不同分布类型的数据聚类实验表明,该算法具有较好的通用性和有效性。

基于遗传算法的K-means初始化EM算法及聚类应用

混合高斯模型能够有效地拟合概率密度函数,常用的混合高斯概率密度模型参数估计方法是EM迭代算法,这种算法的缺点是估计精度过分依赖于初始值,而且不能估计模型阶数。基于遗传算法的K-means初始化EM算法可以同时估计模型阶数和参数。试验结果表明,该算法具有更好的聚类效果。

一种基于余弦因子改进的混合聚类算法

为了解决传统的K-means聚类算法全局优化性差,容易陷入局部最优的问题,用具有全局自适应优化特点的遗传算法与K-means算法结合来改善聚类效果.在此基础上提出了基于余弦因子改进的混合聚类算法(SGKM),在交叉和变异操作时用基因余弦因子(GCOS)进行个体控制,确保差的个体不会被引入下一代,并采用交叉和变异概率的自适应控制,结合了K-means算法的高效局部搜索和遗传算法的全局优化能力.实验结果表明,与其他基于K-means算法改进的聚类算法相比,SGKM算法能获得更小的簇内距和更大的簇间距,且数据对象的分类准确率有一定的提高.应用SGKM算法进行聚类不易受到不良个体的干扰,可以有效地改善聚类效果.

基于GA与PSO混合优化的Web文档聚类算法

Web文档聚类是web数据挖掘的重要任务之一,针对Web文档向量空间的高维性与数据聚类问题的最优化性质,采用LDA对文档向量空间进行降维,提出运用混合优化算法GA_PSO在此低维空间进行寻优,来发现Web文档集的最优簇结构.通过在真实数据集20Newsgroups的实验,结果表明我们的方法具有良好的聚类有效性,能较完全和准确地将主题相关的Web文档聚成一类.

基于混合聚类的覆盖网络组播服务节点选择模型

通过分析当前覆盖网络特点,以分层覆盖网络为基础构建特定源组播树,实现对组播服务节点MSNs的管理,并提出一种基于K-Medoids和遗传算法的模型,用于网络中MSNs的选择.结果表明,该模型有效克服了传统K-Medoids算法模型对初始中心选值敏感的问题和早熟收敛现象,使其针对覆盖网络组播服务节点的选择性能明显优于K-Medoids选择模型,平均收敛速度也提高近30%.

基于GASA-FCM混合聚类与霍夫变换的欠定混合矩阵估计

针对模糊C-均值聚类(fuzzy C-means clustering,FCM)算法在欠定混合矩阵估计中精度低、鲁棒性差的缺点,提出一种基于遗传模拟退火优化FCM(GASA-FCM)混合聚类和霍夫变换的欠定混合矩阵估计算法。该算法结合了模拟退火算法(simulated annealing algorithm,SA)全局搜索、高精度的优点和遗传算法(genetic algorithm,GA)强大的空间搜索能力,将经遗传模拟退火算法得到的聚类中心点赋给FCM,避免了初值选择的随机性。再利用霍夫变换对聚类得到的每一类数据的中心进行修正,提高混合矩阵的估计精度。实验结果表明,该算法明显改善了算法的稳定性和混合矩阵估计精度,具有一定的有效性和可行性。

共同配送选址-路径优化模型与算法

以北京市奶制品配送问题为场景,研究了共同配送选址-路径优化问题。建立了两层级带容量约束的共同配送选址-路径问题的混合整数规划模型,设计了求解模型的三阶段算法。第一阶段采用基于遗传算法的带容量限制的K-means聚类方法,将客户划分为若干客户集;第二阶段计算每个备选配送中心为每个客户集提供服务的最优配送路径及成本,在此基础上将共同配送中心选址与第二层级配送路径优化问题简化为配送中心选址和客户集分配问题,建立数学模型并利用Lingo软件求解;第三阶段确定从物流中心到共同配送中心的最优配送路径。通过对比两大品牌奶制品在北京地区各商超的单独配送与共同配送成本,验证了模型和算法的合理性和有效性。研究结果为解决不同类型产品共同配送网络优化等问题提供了决策依据。

混合智能系统R-FC-DENN及其实现

混合智能系统已成为人工智能的一个重要研究方向,本文依据认知心理学和模型集成理论,构建了集粗糙集理论、聚类理论、模糊逻辑理论、遗传算法理论、人工神经网络理论于一体的混合智能系统R-FC-DENN,该系统在数据的空间效能方面和算法的时间效率等方面比已有算法有较大的改进。以混合智能系统R-FC-DENN为例,基于Rosetta和Matlab 6.5平台,还开发了混合智能系统工具箱RFCDENN-Tool,为相关研究打下坚实的基础。

混合EM算法研究及聚类应用

混合高斯模型能够有效地拟合概率密度函数,常用的混合高斯概率密度模型参数估计方法是EM算法,这种算法的缺点是估计精度过分依赖于初始值,不能估计模型阶数,容易导致协方差矩阵出现奇异。基于遗传算法的Annealing-EM算法可以同时估计模型阶数和参数,有效地克服协方差矩阵出现奇异,将混合算法应用到聚类中,仿真结果表明该算法具有更好的聚类效果。

一种基于Web使用挖掘的个性化信息推荐系统实现方法

为了提高基于Web使用挖掘的个性化信息推荐的有效性和效率,提出了将顺序模式和KP混合聚类遗传算法相结合的推荐策略,在Web日志预处理的基础上,设计出了一种基于Web使用挖掘的个性化信息推荐系统RSPIBOWUM的框架结构,并给出了基于这一框架结构的实现流程。结果表明,本推荐策略可以进行有效的个性化信息推荐,提高个性化信息推荐的效率。

带并行批处理机的柔性作业车间调度问题研究

针对汽车模具铸造中一类带有单处理机和并行批处理机的混合加工模式,构建了以最小化最大完工时间为优化目标的带有并行批处理机的柔性作业车间调度模型。设计了一种改进遗传算法来求解该模型,在算法中提出了一种分块式集成解码规则,保证能在一次解码中得到混合活动调度方案。设计了一种聚类的选择算子,采用K-Means算法并根据适应度值将各个可行解分为多个性质相同的子类,选择留下不同子类中的染色体,且不同子类之间进行染色体交叉,拓宽种群的多样性。此外,为了改善算法的局部能力,设计了基于关键路径的局部搜索策略。仿真实验验证了所提出算法解决此类问题的可行性和有效性。

不确定车辆数的车辆路径问题模型和混合算法

提出用遗传算法 ( Genetic Algorithms,GA)和禁忌搜索算法 ( Tabu Search Algorithm,TSA)结合求解不确定车辆数的车辆路径问题。首先描述了带有能力约束的 VRP的数学模型 ,由于车辆数不确定 ,因此提出另一目标函数 ,即最小化车辆数 ,与最小化距离同为目标函数建立了双目标数学规划模型。在车辆数不确定的情况下 ,把聚类和排序有机地结合起来 ,并用 GA和 TSA相结合的混合算法对问题进行求解 ,即以 GA为主 ,把 TSA用在 GA的变异操作中 ,增强算法的爬山能力。实验结果表明 ,混合算法获得的最好解。

电子商务环境下基于B2C的物流配送路径优化

电子商务环境下的物流配送具有客户位置分散、订单多、批量小和重复线路多的特点,传统的线路优化方法都在不同程度上遇到各种问题。文中针对电子商务环境下的配送特殊性,采用改进两阶段算法混合进行求解。第一阶段用K-means聚类法将客户群分成若干区域,在每个区域又用扫描算法分解成若干符合约束条件的小规模子集;第二个阶段对各个分组内的客户点,就是一个个单独的TSP模型的线路优化问题,采用改进遗传算法进行优化求解。最后,结合具体实例,实验证明了该改进算法的有效性。

考虑多专业协同的装配线平衡问题研究

为改善飞机总装线平衡效果,提出考虑多专业协同分配的第一类装配线平衡方法。首先,分析各专业间的关联性,建立基于动态模糊聚类的专业划分方法,获取"资源-功能"的多专业集合;然后,根据飞机总装环境及所涉及专业的特点,建立了多专业协同分配的平衡模型;再根据专业划分结果及作业分配规则,提出了混合模拟退火-遗传算法(HSAGA),将专业间关联度高的作业分配到工作面(指专业关联度高的作业的集合,也指能完成一项装配任务的作业执行操作空间),实现工作面数的最小化;最后,以某型飞机总装作业为例,验证了平衡方法的有效性。