群集智能研究进展

群集智能是指众多行为简单的个体相互作用过程中涌现产生的整体智能行为.从复杂系统研究的角度入手,以群集智能的基本原理为线索,对其系统结构、运行机理、建模工具、算法模型和典型应用等内容进行全面论述.首先围绕以蚁群和鸟群为代表的群集智能系统结构,分析说明了其中的个体属性、行为规则和交互方式,进而阐述和剖析了群集智能中的反馈机制和学习机制.在给出若干常用群集智能建模工具介绍的基础上,对蚁群觅食、蚁群聚类、蚁群劳动分工和鸟群觅食等4类群集智能模型进行了细致深入的探讨,旨在归纳提炼形成基于群集智能的复杂系统建模与仿真的一般性规律.最后综述了群集智能在工程优化、生产管理、机器人学、数据分析与模式识别等领域的典型应用情况并展望了群集智能的发展前景.     

考虑违约追偿和损失补偿的多中心集配网络联盟优化问题

针对多中心集配网络优化研究在网络联盟构建和机制设计方面存在的不足，研究考虑违约追偿和损失补偿的多中心集配网络联盟优化策略。首先，提出基于履约成员重要度的最小费用剩余节约方法，研究了履约成员应得利润问题，进而分别建立履约成员损失补偿和违约成员违约成本分摊模型，对履约成员应得补偿和违约成员违约成本进行了量化研究。其次，考虑违约行为导致的客户服务关系变化特征，构建了最小化网络运营总成本、车辆使用数以及服务等待时间的多目标优化模型。然后，提出了基于K-means多维聚类算法的CW-NSGA-Ⅲ混合启发式算法求解模型，该算法结合CW节约算法提高了初始可行解质量，应用精英保留策略增强了混合算法搜索性能，并引入基于路径偏移惩罚的边界交叉聚合方法改进了非支配解的选择机制，保证非支配解集的多样性，同时提高了其收敛速度，与MOGA、MOHSA和MOPSO算法进行对比分析，验证了算法的有效性。最后，结合实例对提出的模型和算法进行验证，并对不同违约成员数量和客户退出方式下的多中心集配网络优化结果进行了对比分析。结果表明，该方法能够量化违约成员违约成本，保障履约成员应得利润，完善联盟成员合作机制，并优化违约行为...     

安装时间与次序相关的生产调度干扰管理研究

在安装时间和次序相关的单机调度问题中,为应对突发性的工件优先级变动造成的影响,构建了双目标重调度模型。原目标为生产的流程时间,扰动目标为工件的加工次序扰动。针对模型中的双目标,设计了基于有效解的两阶段混合启发式算法进行求解,在原目标和扰动目标之间进行权衡。混合算法第一阶段里,基于任意单个工件次序变化将双目标问题转化成单目标TSP问题,利用最近邻域和插入混合求得单目标问题的若干解,构成初始种群。第二阶段中基于非支配排序遗传算法在处理多目标问题上的优势,对初始种群进行扩展搜索,最后输出问题的有效前沿。通过数值试验运算比较分析若干针对有效解集的指标,验证了混合算法求得的解集在多样性和临近性上要优于单纯的非支配排序遗传算法。该混合算法可以有效地解决具有安装时间的加工次序扰动问题。     

一种策略层项目计划的双目标优化方法

针对产品开发项目管理的实际情况,对策略层计划优化方法进行研究。以工作包的工作量估算为基础,以资源投入水平和工期最小化为目标,考虑各种约束条件,提出一种策略层项目计划问题的混合整数规划问题模型。以非支配遗传算法NSGA-II为基础框架,设计了一种改进的双目标遗传算法。该算法针对问题的特点,提出了基于资源平滑的解码算法。参考NSGA-III的关键特征,对拥挤密度计算方法进行改进。通过企业实际项目案例,验证了算法的性能和所提出的策略层项目计划方法的有效性。     

基于Dijkstra-PD-ACO算法的大城市公交线路优化与评价方法研究

城市公交线路的布设受到诸多影响因素的作用,单纯的追求线路单一指标的"最优"在实际公交线路优化时往往难以取得满意的效果。首先针对传统公交线路优化算法在求解线路优化问题中存在的不足,基于蚁群优化算法的寻优特性,结合Dijkstra算法在局部路径寻优中的优点,提出了Dijkstra蚁群混合优化算法。其次对于线路优化所得到的可行备选方案集,基于分层聚类主成分分析评价法进行优化效能评价。最后以合肥市一环内公交线路优化为实例进行验证。结果表明, 本文提出的方法在兼顾客流密度最大、出行路径最短的同时给出了有效公交线路备选方案,优化结果也符合合肥市的实际情况。同时,该方法对我国大中城市公交线网优化问题的研究具有一定的借鉴意义。     

加权折扣单机排序干扰管理模型和算法研究

为解决机器排序中由于干扰事件的发生使初始最优加工时间表无法按计划执行的问题,构建同时考虑原目标和扰动目标的双目标干扰管理模型,对初始最优加工时间表进行调整并对未完工工件进行重排序;在双目标干扰管理模型中,原目标由所有工件的加权折扣完工时间和来度量,扰动目标由重排序后工件完工时间的变化来度量;结合量子比特在表示解的多样性方面的优点和非支配排序遗传算法在处理多目标排序问题上的优点,设计一种量子遗传算法和非支配排序遗传算法相结合的启发式进化算法对构建的模型进行求解。在数值算例中,通过比较若干项针对有效解集的性能指标发现,该混合算法求得的有效解集在多样性和与最优有效前沿的邻近性等方面优于目前得到广泛应用的非支配排序遗传算法,验证了构建的模型和算法对于求解机器排序干扰管理问题的有效性。     

基于多分类器动态选择与成本敏感优化集成的电信客户流失预测研究

针对不同样本在特征空间中具有不同的区域特性和不同分类算法之间的预测互补性,在电信客户流失预测理论基础上,融合多分类器动态集成理论和成本敏感学习理论,建立了电信客户流失多分类器集成预测的利润函数,并提出了一类新的基于多分类器动态选择与成本敏感优化集成的电信客户流失预测模型.首先使用K均值聚类法聚类训练样本成多个分区;接着使用NaiveBayes算法、多层感知机算法和J48算法在各分区样本上构建客户流失预测子分类器;最后使用改进人工鱼群算法分别对各分区的子分类器进行成本敏感优化集成.实验结果表明,所提出的基于多分类器动态选择与成本敏感优化集成模型的分类性能不仅优于由训练集全体样本所构建的3个单模型,也优于基于改进人工鱼群算法优化集成这3个单模型而得到的集成模型.     

粒子群优化k均值的混合聚类算法研究

k均值算法是聚类分析的一种传统算法,在数据挖掘中等领域得到了广泛的应用.本文在分析k均值聚类算法存在问题的基础上,用粒子群算法优化k均值聚类算法,提出了一种新的混合聚类算法.理论分析和实验结果证明,该算法有很好的全局收敛性,不仅有效地克服了传统的k均值算法易陷入局部极小值和对初始值敏感的问题,而且具有较快的收敛速度.     

移动商务中面向客户细分的KSP混合聚类算法

数据挖掘技术中的聚类算法是解决客户细分问题的重要算法之一。为解决传统聚类算法在客户细分问题中分类精度较低、收敛速度较慢的问题,着重对比分析传统聚类算法中K-m eans、自组织映射网络和粒子群3种算法的不足,提出融合3种算法优点的混合型聚类算法,该算法利用K-m eans和自组织映射网络对初始聚类中心进行优化,结合粒子群优化和K-m eans优化聚类迭代过程,并在迭代优化过程中设计避免算法因早熟而停滞的机制。针对移动电子商务环境下的餐饮业客户细分问题,建立移动餐饮业客户细分模型,并利用混合型聚类算法、K-m eans、层级自组织映射网络和基于粒子群的K-m eans等4种算法对实际案例进行对比分析。研究结果表明,混合型聚类算法的聚类精度分别比其他3种算法高,同时还具有最快的收敛性能,更适用于客户细分问题。     

股票遴选与投资业绩——基于属性约简及动态时间规整距离

评价风险资产价值的指标(属性)有很多,以少量指标(属性)从数以千计的风险资产中筛选出有投资价值的资产对投资业绩影响重大。本文以股票市场为例,提出了基于属性约简及动态时间规整距离的股票遴选方法。首先利用基于属性重复度的改进属性约简算法筛选出能区分股票投资价值的约简属性集,之后将单指标动态时间规整算法拓展到多指标,建立股票间基于约简属性集的多维动态时间规整距离集,利用聚类技术对规整距离集进行聚类并通过拆分规整距离对股票进行类别划分,遴选收益-风险特征均较好的类别中的股票构建资产池。数值试验表明:随机模拟权重和均等权重投资组合的累积收益率均高于市场基准,且资产的优化配置进一步改善了投资组合的收益-风险特征。该方法通过属性约简降低了投资者评价股票投资价值的难度,通过多维动态时间规整距离度量了不同股票关于各指标(属性)时间序列变动趋势的相似程度;遴选过程基于历史数据,避免了主观因素的影响,且筛选结果具有稳健性。此外,该方法适合于一般风险资产的遴选,还可以将不同市场不同行业考虑在内,以便更好地实现分散化投资。     

一种求解双目标flow shop排序问题的进化算法

提出一种求解双目标flow shop排序的递进多目标进化算法.算法采用改进的精英复制策略,在实现精英保留的前提下降低了计算复杂性;通过递进进化模式增加群体多样性,改善了算法收敛性;通过群体进化过程中对非劣解集进行竞争型可变邻域启发式搜索,增强了算法局部搜索性能.采用新算法和参照算法NSGA-II对31个标准双目标flow shop算例进行优化.研究结果表明,新算法在所有算例的求解中均获得了优于NSGA-II的非劣解集,验证了算法的有效性.     

An efficient spread-based evolutionary algorithm for solving dynamic multi-objective optimization problems

Dynamic multi-objective optimization algorithms are used as powerful methods for solving many problems worldwide. Diversity, convergence, and adaptation to environment changes are three of the most important factors that dynamic multi-objective optimization algorithms try to improve. These factors are functions of exploration, exploitation, selection and adaptation operators. Thus, effective operators should be employed to achieve a robust dynamic optimization algorithm. The algorithm presented in this study is known as spread-based dynamic multi-objective algorithm (SBDMOA) that uses bi-directional mutation and convex crossover operators to exploit and explore the search space. The selection operator of the proposed algorithm is inspired by the spread metric to maximize diversity. When the environment changed, the proposed algorithm removes the dominated solutions and mutated all the non-dominated solutions for adaptation to the new environment. Then the selection operator is used to select desirable solutions from the population of non-dominated and mutated solutions. Generational distance, spread, and hypervolume metrics are employed to evaluate the convergence and diversity of solutions. The overall performance of the proposed algorithm is evaluated and investigated on FDA, DMOP, JY, and the heating optimization problem, by comparing it with the DNSGAII, MOEA/D-SV, DBOEA, KPEA, D-MOPSO, KT-DMOEA, Tr-DMOEA and PBDMO algorithms. Empirical results demonstrate the superiority of the proposed algorithm in comparison to other state-of-the-art algorithms.

     

Novel quadratic programming approach for time series clustering with biomedical application

Fundamental problems in data mining mainly involve discrete decisions based on numerical analyses of data (e.g., class assignment, feature selection, data categorization, identifying outlier samples). These decision-making problems in data mining are combinatorial in nature and can naturally be formulated as discrete optimization problems. One of the most widely studied problems in data mining is clustering. In this paper, we propose a new optimization model for hierarchical clustering based on quadratic programming and later show that this model is compact and scalable. Application of this clustering technique in epilepsy, the second most common brain disorder, is a case point in this study. In our empirical study, we will apply the proposed clustering technique to treatment problems in epilepsy through the brain dynamics analysis of electroencephalogram (EEG) recordings. This study is a proof of concept of our hypothesis that epileptic brains tend to be more synchronized (clustered) during the period before a seizure than a normal period. The results of this study suggest that data mining research might be able to revolutionize current diagnosis and treatment of epilepsy as well as give a greater understanding of brain functions (and other complex systems) from a system perspective. This work was partially supported by the NSF grant CCF 0546574 and Rutgers Research Council grant-202018.     

A multiobjective model and evolutionary algorithms for robust time and space assembly line balancing under uncertain demand

Changes in demand when manufacturing different products require an optimization model that includes robustness in its definition and methods to deal with it. In this work we propose the r-TSALBP, a multiobjective model for assembly line balancing to search for the most robust line configurations when demand changes. The robust model definition considers a set of demand scenarios and presents temporal and spatial overloads of the stations in the assembly line of the products to be assembled. We present two multiobjective evolutionary algorithms to deal with one of the r-TSALBP variants. The first algorithm uses an additional objective to evaluate the robustness of the solutions. The second algorithm employs a novel adaptive method to evolve separate populations of robust and non-robust solutions during the search. Results show the improvements of using robustness information during the search and the outstanding behavior of the adaptive evolutionary algorithm for solving the problem. Finally, we analyze the managerial impacts of considering the r-TSALBP model for the different organization departments by exploiting the values of the robustness metrics.     

一种差异工件单机批调度问题的蚁群优化算法

由于在利用蚁群算法构建差异工件(即工件有尺寸差异)单机批调度问题的解时,批的加工时间是不确定的.从而不能类似于经典调度问题的蚁群算法把批加工时间的倒数作为蚁群算法中的启发式信息,引入批的利用率和批的负载均衡率作为蚁群算法中的启发式信息,提出了JACO(ant colony optimization based a job sequence)和BACO(ant colony optimization based a batch sequence)两种蚁群优化算法.在算法JACO中,解的编码为工件序列,它对应着用BF(best fit)分批规则生成的调度方案,信息素代表工件间的排列顺序;在算法BACO中,解的编码为批序列,信息素代表工件间的批相关性,由此信息素通过中间信息素量来构造相应的解,并引入特定的局部优化策略,提高了算法的搜索效率.实验表明,与以往文献中的SA(simula-ted annealing)、GA(genetic algorithm)算法以及FFLPT(first-fit longest processing time)、BFLPT (best-fit longest processing time)启发式规则相比,算法JACO和BACO明显优于它们,且BACO算法比JACO算法效果更好.     

Planning of a decentralized distribution network using bilevel optimization

This paper proposes a bilevel optimization problem to model the planning of a distribution network that allows us to take into account how decisions made at the distribution stage of the supply chain can affect and be affected by decisions made at the manufacturing stage. Usually, the distribution network design problem decides on the opening of depots and the distribution from the depots to customers only and pays no attention to the manufacturing process itself. By way of example, the paper discusses the implications of formulating a bilevel model to integrate distribution and manufacturing, maintaining the hierarchy existing in the decision process. The resulting model is a bilevel mixed integer optimization problem. Hence, only small instances can be optimally solved in an acceptable computing time. In order to be able to solve the optimization model for realistic large systems, a metaheuristic approach based on evolutionary algorithms is developed. The algorithm combines the use of an evolutionary algorithm to control the supply of depots with optimization techniques to determine the delivery from depots to customers and the supply from manufacturing plants to depots. A computational experiment is carried out to assess the efficiency and robustness of the algorithm.     

基于多小波的数字水印优化

为了提高数字水印的实用性,必须保证水印的鲁棒性和透明性,为此充分考虑人类视觉系统特性,提出了一种基于多小波的数字水印优化方法。该方法利用Sa4多小波基进行数字水印嵌入,引入多目标优化手段对其嵌入深度进行优化调整,得到最佳嵌入效果。通过遗传算法实现的结果表明,该算法不仅对水印的攻击具有强鲁棒性,且能兼顾载体图像的质量。     

Hybrid Evolutionary Algorithms for Graph Coloring

A recent and very promising approach for combinatorial optimization is to embed local search into the framework of evolutionary algorithms. In this paper, we present such hybrid algorithms for the graph coloring problem. These algorithms combine a new class of highly specialized crossover operators and a well-known tabu search algorithm. Experiments of such a hybrid algorithm are carried out on large DIMACS Challenge benchmark graphs. Results prove very competitive with and even better than those of state-of-the-art algorithms. Analysis of the behavior of the algorithm sheds light on ways to further improvement.     

多油品供给受限下多油库被动配送车辆路径问题研究

成品油供给不足将导致加油站油品订单无法完全满足,如何安排有限油品的合理配送对保障能源供给安全至关重要。为此,本文考虑有限供给下不同客户配送的优先次序,开展配送计划、车辆调度和路径优化等油品配送网络规划活动,对多油品供给受限情况下多油库被动配送车辆路径问题（Multiple Depot Vehicle Routing Problem,MDVRP）进行深入研究。首先,文章构建了考虑需求优先等级和配送成本的多油品多油库车辆路径规划多目标优化模型。其次,采用多目标粒子群优化算法（Multi-Objective Particle Swarm Optimization,MOPSO）对模型进行求解,以实现车辆高效调度和油品配送路径优化。最后,基于CNPC在青岛市部分油库和加油站点的数据信息,构建油品配送网络进行实证检验。算例结果显示,配送车辆路径经过优化后,生成Pareto非劣解集,配送成本显著降低,配送满足率明显提高,这也进一步验证了该模型及相关算法的可行性和有效性。     

一种基于PIM与核方法的模糊聚类新算法

本文针对模糊C均值聚类在大数据量时收敛较慢以及不能对多种数据结构有效聚类的缺点,结合PIM算法与核方法提出了一种新的高效聚类算法———KPIM算法,并从理论上证明了该算法的收敛性.最后利用标准实验数据IRIS数据集测试,结果表明KPIM算法在保证收敛速度的同时,聚类效果更有效.