In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected domi...In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected dominating set in an arbitrary graph.In this paper,based on cross-entropy method,we present a novel backbone formulation algorithm(BFA-CE)in wireless sensor network.In BFA-CE,a maximal independent set is got at first and nodes in the independent set are required to get their action sets.Based on those action sets,a backbone is generated with the cross-entropy method.Simulation results show that our algorithm can effectively reduce the size of backbone network within a reasonable message overhead,and it has lower average node degree.This approach can be potentially used in designing efficient broadcasting strategy or working as a backup routing of wireless sensor network.展开更多
针对一类广泛存在的生产装配问题,建立人机共同作业的资源约束U形装配线平衡问题(ResourceconstraintU-shaped assembly line balancing problem with man-robot cooperation,RCUALBP_MRC)模型。该模型中机器人与助理均为有限资源,机器...针对一类广泛存在的生产装配问题,建立人机共同作业的资源约束U形装配线平衡问题(ResourceconstraintU-shaped assembly line balancing problem with man-robot cooperation,RCUALBP_MRC)模型。该模型中机器人与助理均为有限资源,机器人可替代人工操作,助理可协助工人操作,优化目标为同时最小化总成本指标和最大化线效率以及负载标准差综合指标。一种用于求解RCUALBP_MRC的基于交叉熵(Cross-entropy,CE)方法与遗传算法(Geneticalgorithm,GA)的协同进化算法(CE-GACo-evolutionaryalgorithm,CE-GACEA)被提出。首先,根据问题特点,对解中工序子序列设计了一种基于工序选择因子的编码(Task selection factor based code,TSFBC)。其次,在算法的全局搜索阶段对解中工序子序列和机器人及助理子序列所确定的子空间,分别利用GA和CE的操作进行协同搜索,可丰富搜索方向并发现优质解区域;局部搜索阶段加入种群分裂-合并机制,可有效平衡算法的全局与局部搜索,改善算法性能。最后,通过在不同规模问题上的仿真试验和算法对比,验证所提CE-GACEA的有效性。展开更多
In this paper, we use the discontinuous exact penalty functions to solve the constrained minimization problems with an integral approach. We examine a general form of the constrained deviation integral and its analyti...In this paper, we use the discontinuous exact penalty functions to solve the constrained minimization problems with an integral approach. We examine a general form of the constrained deviation integral and its analytical properties. The optimality conditions of the penalized minimization problems are proven. To implement the al- gorithm, the cross-entropy method and the importance sampling are used based on the Monte-Carlo technique. Numerical tests show the effectiveness of the proposed algorithm.展开更多
We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method ...We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.展开更多
基金supported partially by the science and technology project of CQ CSTC(No.cstc2012jjA40037)
文摘In wireless sensor network,virtual backbone is a cost effective broadcasting method.Connected dominating set formation is proposed to construct a virtual backbone.However,it is NP-Hard to find a minimum connected dominating set in an arbitrary graph.In this paper,based on cross-entropy method,we present a novel backbone formulation algorithm(BFA-CE)in wireless sensor network.In BFA-CE,a maximal independent set is got at first and nodes in the independent set are required to get their action sets.Based on those action sets,a backbone is generated with the cross-entropy method.Simulation results show that our algorithm can effectively reduce the size of backbone network within a reasonable message overhead,and it has lower average node degree.This approach can be potentially used in designing efficient broadcasting strategy or working as a backup routing of wireless sensor network.
文摘针对一类广泛存在的生产装配问题,建立人机共同作业的资源约束U形装配线平衡问题(ResourceconstraintU-shaped assembly line balancing problem with man-robot cooperation,RCUALBP_MRC)模型。该模型中机器人与助理均为有限资源,机器人可替代人工操作,助理可协助工人操作,优化目标为同时最小化总成本指标和最大化线效率以及负载标准差综合指标。一种用于求解RCUALBP_MRC的基于交叉熵(Cross-entropy,CE)方法与遗传算法(Geneticalgorithm,GA)的协同进化算法(CE-GACo-evolutionaryalgorithm,CE-GACEA)被提出。首先,根据问题特点,对解中工序子序列设计了一种基于工序选择因子的编码(Task selection factor based code,TSFBC)。其次,在算法的全局搜索阶段对解中工序子序列和机器人及助理子序列所确定的子空间,分别利用GA和CE的操作进行协同搜索,可丰富搜索方向并发现优质解区域;局部搜索阶段加入种群分裂-合并机制,可有效平衡算法的全局与局部搜索,改善算法性能。最后,通过在不同规模问题上的仿真试验和算法对比,验证所提CE-GACEA的有效性。
基金supported by the National Natural Science Foundation of China (No. 10771133)the KeyDisciplines of Shanghai Municipality (Operations Research and Cybernetics) (No. S30104)
文摘In this paper, we use the discontinuous exact penalty functions to solve the constrained minimization problems with an integral approach. We examine a general form of the constrained deviation integral and its analytical properties. The optimality conditions of the penalized minimization problems are proven. To implement the al- gorithm, the cross-entropy method and the importance sampling are used based on the Monte-Carlo technique. Numerical tests show the effectiveness of the proposed algorithm.
基金Project supported by the National Natural Science Foundation of China (No.10671117)Shanghai Leading Academic Discipline Project (No.J050101)the Youth Science Foundation of Hunan Education Department of China (No.06B037)
文摘We propose a stochastic level value approximation method for a quadratic integer convex minimizing problem in this paper. This method applies an importance sampling technique, and make use of the cross-entropy method to update the sample density functions. We also prove the asymptotic convergence of this algorithm, and report some numerical results to illuminate its effectiveness.
