模糊聚类最优划分判定的一种新模型

针对聚类分析的模糊模式未解决的问题:模糊划分空间中模糊最优划分的判定问题,提出一个新的判定模型。给出基于新的最优划分判定模型的应用例子,验证了模型算法应用的可行性。     

弹性光网络一类调度问题的一个新模型和算法

采用网络功能虚拟化技术的弹性光网络是一种新型的网络,其数据中心的合理部署,路由的科学规划及频谱的最优分配是一个关键而具有挑战的问题.为了解决这个问题,建立了弹性光网络资源分配和任务调度问题一个新的优化模型,新模型以虚拟网络功能在数据中心部署的负载最均衡,经过数据中心节点的路径最短以及频谱占用最少为目标,可同时使虚拟网络功能在数据中心部署,路径规划和频谱分配方案最优.为有效求解该模型,分别设计了一个经过所选数据中心的最短路径策略,虚拟网络功能在数据中心的部署策略以及频谱分配策略,构造了初始种群的产生方法,设计了新的变异算子,在此基础上,提出了求解模型的一个新的进化算法.最后进行了仿真实验,结果表明,最大频隙号和数据中心VNF部署数目的标准差相比对比算法有明显降低,验证了所建模型和算法的有效性.     

基于随机动态规划的有限库存ATO系统优化控制

本文研究n维组件单一产品,有限库存的ATO系统。通过建立马尔可夫决策过程模型(MDP),构造优化算法,研究组件生产与库存的最优控制策略。最优策路可以表示为状态依赖型库存阈值,系统内任一组件的控制策略受其它组件库存状态的影响。利用最优控制理论动态规划方法和数值计算方法对最优控制策略的存在性、最优值的数值计算进行研究,建立更符合实际生产的ATO系统决策模型,进行相应的理论和实验验证,研究系统参数对最优策略的影响。     

带衰减观测和随机传感器偏差的多传感器AR信号融合辨识与估计

研究了带衰减观测和随机传感器偏差的多传感器AR信号融合辨识与估计问题.首先,将AR模型转换为状态空间模型,将状态和传感器偏差进行增广得到一个等价的状态空间模型,给出了当系统模型精确已知下的最优滤波算法.然后,当AR信号参数、衰减观测随机变量的数学期望和方差未知时,提出了两段辨识算法.第一段采用递推增广最小二乘法(RELS)得到AR信号参数的局部估值,并利用按矩阵加权线性无偏最小方差最优估计准则得到AR信号参数的融合估值.第二段利用相关函数得到虚拟观测噪声方差、衰减观测随机变量的数学期望和方差的估值.最后,将每时刻辨识的未知参数代入最优滤波算法中,获得分布式加权自校正融合滤波算法.分析了算法的收敛性.仿真验证了算法的有效性.     

人力资源多维分配问题的混合算法

针对已有多维分配问题求解算法复杂、耗时长及精度低等问题,本文将二部图中寻求最优匹配的方法进行推广,运用试分配、饱和路调整和增广路调整对多维分配问题的最优解进行搜索,提出了求解人力资源多维分配问题的最小零面优先分配混合算法和随机试分配混合算法,对算法的有效性进行了理论证明,并分析了算法的时间和空间复杂度;同时通过这两种混合算法对初始零元素数不同的代价矩阵求解时间的计算,以及与Lagrangian松弛算法和剪枝法的耗时、精度的对比,分别得到了两种混合算法的适用性和高效性,最后通过算例验证了算法的有效性。     

基于新型核与灰度序列的时滞GM(1,N)模型及其应用

为了解决GM(1,N)模型在新型核与灰度的基础上,对驱动项的延迟作用机理不明确的问题,将时滞参数引入到GM(1,N)模型的驱动项中,构建了基于新型核与灰度的时滞GM(1,N)模型,分析了时滞参数的辨识方法,讨论了新模型的建模机理。为了更好地对该模型的有效性进行验证,将优化的时滞GM(1,N)模型对南京市的雾霾进行预测分析,选择GM(1,N)模型、一元回归模型与文中的优化模型进行对比。结果显示,优化模型对PM₁₀浓度的拟合精度更高,且误差均控制在5%之内,从而验证了提出的优化模型适用于具有时滞特征数据的模拟和预测。     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

一类一维在线单位聚类问题的随机近似算法

在给定的度量空间中, 单位聚类问题就是寻找最少的单位球来覆盖给定的所有点。这是一个众所周知的组合优化问题, 其在线版本为: 给定一个度量空间, 其中的n个点会一个接一个的到达任何可能的位置, 在点到达的时候必须给该点分配一个单位聚类, 而此时未来点的相关信息都是未知的, 问题的目标是最后使用的单位聚类数目最少。本文考虑的是带如下假设的一类一维在线单位聚类问题: 在相应离线问题的最优解中任意两个相邻聚类之间的距离都大于0.5。本文首先给出了两个在线算法和一些引理, 接着通过0.5的概率分别运行两个在线算法得到一个组合随机算法, 最后证明了这个组合随机算法的期望竞争比不超过1.5。     

线性双层规划的改进PCP全局求解算法

本文采用K-T条件将线性双层规划模型改写为单层规划后,将参数引入上层目标函数,构造了含参线性互补问题(PLCP)并给出它的一些性质。进而通过改进Lemke算法的进基规则,在保持互补旋转算法原有优势的基础上,引入充分小正数ε,设计了改进参数互补旋转(PCP)算法求取全局最优解,最后通过两个算例说明了其有效性。     

自适应最优混合差异聚类算法

针对多维情况下,数据量很大,不可避免的受到噪声干扰,因此需对原始数据进行必要的处理。本文用二次差异序度调整一次差异度,提出了自适应最优混合差异聚类算法,该算法具有谱系结构,这在地层划分,时间序列分析等应用上极其重要,在地层划分上,本文给出了一个实例,我们可以看到谱系结构的重要性。对无序样品给出了相应的最优聚类算法,并分析了西安地下水文的分布情况。     

云计算环境资源监控系统研究

为保障云计算平台的可靠性,基于Ganglia,采用Eucalyptus开源云平台,提出了云计算平台资源监控系统架构.从总体结构、监控信息处理流程等多个方面对监控系统进行了详细阐述,提出了动态更换虚拟机簇头的算法,并对算法与原型系统进行了验证和性能评测.分析与评测结果表明,所提系统能够适用于云计算环境资源信息的实时监测与预警,具备系统开销较低,用户接口友好的特点,能准确反映系统、虚拟机的负载信息,有助于云计算系统服务可靠性的提升.簇头动态更换算法能及时发现失效的簇头并更换为更健壮的虚拟机,保证了监测系统的正常运行.     

基于外包决策的并行调度随机模型

在传统的并行机器调度问题基础上引入了不确定随机变量,同时考虑了以产品外包为能力拓展形式的现代生产模式,建立了基于外包决策的并行调度随机模型.模型以带有拖期惩罚函数的最大化利润为目标,以遗传算法这种进化的启发式计算方法寻找最优解.同时引入虚拟机器的概念,实现了对外包情形下机器调度问题的有效处理和简化.实例证明,该模型更符合现代生产模式,极大地提高了企业的工作效率和经济效益.     

考虑机器能耗的绿色作业车间调度问题

针对传统作业车间调度,在保证交货期的前提下,以机器能耗最小为目标研究带有关机/重启策略的绿色车间调度问题。首先建立数学规划模型,然后在遗传算法的框架下,根据问题特点提出了一种局部调整的解码方式,在排产时进行工序的移动并确定其开始加工时刻。最后进行小规模算例运算,验证数学规划模型的有效性,再利用算例对基于局部调整解码和顺序解码的遗传算法进行对比测试,结果表明提出的局部调整解码可以在降低机器能耗的同时提高求解效率。     

Heuristics approach to printed circuit board insertion problem

This paper studies the operation of a surface mount technology (SMT) machine which basically consists of three main movable parts: an X–Y table containing a printed circuit board (PCB), ten rotating ‘pick-and-place’ heads and a carriage feeder of reels. The machine inserts electronic components into defined positions on a PCB and the components are supplied from a set of reels each containing a tape of identical components. In the current production setup, the assembly plan comprising both the insertion sequence of components and the placement orders of the reels in the feeder is by human experience. Our study suggests that the problem is computationally difficult for its mathematical optimum with the insertion problem alone being NP-complete. We propose a heuristic solution technique of low computational complexity to find a better assembly plan comprising of the assembly sequence of electronic components and the placement order of the reels in the feeder. The algorithm developed combines the physical constraints of the SMT machine and a ‘grouping’ concept that takes advantage of the natural structure of a PCB. Using multiple reels in the PCB insertion problem are also considered. Simulated results are reported on a set of illustrative data.     

基于DC规划方法的稀疏临近支持向量机

为了提高临近支持向量机（PSVM）的数值表现,在PSVM的模型中引入了$\ell_0$-范数正则项,提出了稀疏临近支持向量机模型（SPSVM）,从而提高分类器的特征选择能力。然而带有$\ell_0$-范数正则项的问题往往是NP-难问题,为了克服这一问题,采用非凸连续函数近似$\ell_0$-范数,并通过适当的DC分解将问题转化成DC规划问题进行求解,同时还讨论了算法的收敛性。数值实验结果表明不论是在仿真数据还是在实际数据中,所提出的方法是比较有效稳定的。     

A novel method for optimal capacitor placement and sizing in distribution systems with nonlinear loads and DG using GA

A genetic algorithm (GA) is proposed for simultaneous power quality improvement, optimal placement and sizing of fixed capacitor banks in radial distribution networks with nonlinear loads and distributed generation (DG) imposing voltage–current harmonics. In distribution systems, nonlinear loads and DGs are often considered as harmonic sources. For optimizing capacitor placement and sizing in the distribution system, objective function includes the cost of power losses, energy losses and capacitor banks. At the same time, constraints include voltage limits, number/size of installed capacitors (at each bus) and the power quality limits of standard IEEE-519. In this study, new fitness function is used to solve the constrained optimization problem with discrete variables. Simulation results for two IEEE distorted networks (18-bus and 33-bus test systems) are presented and solutions of the proposed method are compared with those of previous methods described in the literature. The main contribution of this paper is computing the (near) global solution with a lower probability of getting stuck at a local optimum and weak dependency on initial conditions, while avoiding numerical problems in large systems. Results show that proposed method could be effectively used for optimal capacitor placement and sizing in distorted distribution systems.     

A new multiobjective allocator of capacitor banks and distributed generations using a new investigated differential evolution

This article has investigated a new multiobjective allocation of optimal sizing and sitting of distributed generation (DG) units and capacitor banks in simultaneous mode to improve reliability and reduce energy losses. The proposed method consists of four objectives, that is, cost of energy not supplied, system average interruption duration index, costs of energy loss and investment. A novel structure differential evolution has been suggested to solve this nonlinear complex problem and its results are compared with related values of genetic algorithm and simple differential evolutionary algorithm. In addition to the novel objective function, the other contribution of this article is proposing a new model for load and energy cost. Three types of DGs, that is, wind turbine, solar cell, and diesel generator have been used in placement process. To verify the comprehensiveness of the proposed function, three scenarios have been introduced: scenario i: first, placement of DGs, then capacitor banks, scenario ii: first, placement of capacitor banks, and then DGs, and scenario iii: simultaneous placement of DGs and capacitor banks. Simulations have been carried out on one part of practical distribution network in Metropolitan Tabriz in North West of Iran. The results of simulations have been discussed and analyzed using the five novel indices. The obtained simulation results using proposed function shows that the simultaneous placement of DGs and capacitor banks results in more reduction of the energy losses and increase improvements of reliability indices as well as voltage profile. © 2013 Wiley Periodicals, Inc. Complexity 19: 40–54, 2014     

Knot Placement for B-Spline Curve Approximation via $L_{∞, 1}$-Norm and Differential Evolution Algorithm

In this paper, we consider the knot placement problem in B-spline curve approximation. A novel two-stage framework is proposed for addressing this problem. In the first step, the $l_{\infty, 1}$-norm model is introduced for the sparse selection of candidate knots from an initial knot vector. By this step, the knot number is determined. In the second step, knot positions are formulated into a nonlinear optimization problem and optimized by a global optimization algorithm — the differential evolution algorithm (DE). The candidate knots selected in the first step are served for initial values of the DE algorithm. Since the candidate knots provide a good guess of knot positions, the DE algorithm can quickly converge. One advantage of the proposed algorithm is that the knot number and knot positions are determined automatically. Compared with the current existing algorithms, the proposed algorithm finds approximations with smaller fitting error when the knot number is fixed in advance. Furthermore, the proposed algorithm is robust to noisy data and can handle with few data points. We illustrate with some examples and applications.     

需要安装时间的平行多功能机排序问题的启发式算法

考虑需要安装时间的平行多功能机排序问题。在该模型中,每个工件对应机器集合的一个子集,其只能在这个子集中的任一台机器上加工,称这个子集为该工件的加工集合;工件分组,同组工件具有相同的加工时间和加工集合,不同组中的工件在同一台机器上连续加工需要安装时间,目标函数为极小化最大完工时间。对该问题NP-难的一般情况设计启发式算法:首先按照特定的规则将所有工件组都整组地安排到各台机器上,然后通过在各机器间转移工件不断改进当前最大完工时间。通过与下界的比较检验算法的性能,大量的计算实验表明,算法是实用而有效的。     

Single machine scheduling with semi-resumable machine availability constraints

This paper considers the semi-resumable model of single machine scheduling with a non-availability period. The machine is not available for processing during a given time interval. A job cannot be completed before the non-availability period will have to partially restart after the machine has become available again. For the problem with objective of minimizing makespan, the tight worst-case ratio of algorithm LPT is given, and an FPTAS is also proposed. For the problem with objective of minimizing total weighted completion time, an approximation algorithm with worst-case ratio smaller than 2 is presented. Two special cases of the latter problem are also considered, and improved algorithms are given.