SOLVING MINIMUM SPANNING TREE PROBLEM WITH DNA COMPUTING

Molecular programming is applied to minimum spanning problem whose solution requires encoding of real values in DNA strands. A new encoding scheme is proposed for real values that is biologically plausible and has a fixed code length. According to the characteristics of the problem, a DNA algorithm solving the minimum spanning tree problem is given. The effectiveness of the proposed method is verified by simulation. The advantages and disadvantages of this algorithm are discussed.

Bottleneck Analysis of the Minimum Cost Problem for the Generalized Network Based on Augmented Forest Structure

The bottleneck analysis of the minimum cost problem for the generalized network (MCPGN) is discussed. The analysis is based on the network simplex algorithm, which gains negative cost graphs by constructing augmented forest structure, then augments flows on the negative cost graphs until the optimal revolution is gained. Bottleneck structure is presented after analyzing the augmented forest structure. The negative cost augmented graphs are constructed with the bottleneck structure. The arcs that block the negative cost augmented graph are the elements of the bottleneck. The bottleneck analysis for the generalized circulation problem, the minimum circulation problem and the circulation problem are discussed respectively as the basal problems, then that for MCPGN is achieved. An example is presented at the end.

A Novel Binary Firefly Algorithm for the Minimum Labeling Spanning Tree Problem

Given a connected undirected graph G whose edges are labeled,the minimumlabeling spanning tree(MLST)problemis to find a spanning tree of G with the smallest number of different labels.TheMLST is anNP-hard combinatorial optimization problem,which is widely applied in communication networks,multimodal transportation networks,and data compression.Some approximation algorithms and heuristics algorithms have been proposed for the problem.Firefly algorithm is a new meta-heuristic algorithm.Because of its simplicity and easy implementation,it has been successfully applied in various fields.However,the basic firefly algorithm is not suitable for discrete problems.To this end,a novel discrete firefly algorithm for the MLST problem is proposed in this paper.A binary operation method to update firefly positions and a local feasible handling method are introduced,which correct unfeasible solutions,eliminate redundant labels,and make the algorithm more suitable for discrete problems.Computational results show that the algorithm has good performance.The algorithm can be extended to solve other discrete optimization problems.

ON THE REGULARITY OF THE MINIMUM SOLUTION OF THE RESTRAINED VARIATIONAL PROBLEMS

This paper is concerned with the regularity of minimum solution u of the following functional L(u) = integral(Omega) a alpha(beta)(x)g(ij)(u)D alpha u(i)D(beta)upsilon(i)dx on the restraint E = {u is an element of W-0(1,2) (Omega, R(N))\parallel to u parallel to L(D) = 1}. Under appropriate conditions, the bounded minimum solution u of the above functional is proved to be nothing but Holder continuous.

Exact Algorithm to Solve the Minimum Cost Multi-Constrained Multicast Routing Problem

The optimal solution of the multi-constrained QoS multicast routing problem is a tree-like hierarchical structure in the topology graph. This multicast route contains a feasible path from the source node to each of the destinations with respect to a set of QoS constraints while minimizing a cost function. Often, it is a tree. In other cases, the hierarchies can return several times to nodes and links of the topology graph. Similarly to Steiner problem, finding such a structure is an NP-hard problem. The usual tree and topology enumeration algorithms applied for the Steiner problem cannot be used to solve the addressed problem. In this paper, we propose an exact algorithm based on the Branch and Bound principle and improved by the Lookahead technique. We show relevant properties of the optimum hierarchy permitting efficient pruning of the search space. To our knowledge, our paper is the first to propose an exact algorithm for this non-trivial multi-constrained optimal multicast route computation. Simulations illustrate the efficiency of the proposed pruning operations. The analysis of the execution time shows that in simple topologies and with tight QoS constraints the exact algorithm requires relatively little execution time. With loose constraints the computation time cannot be tolerated even for off-line route computation. In these cases, the solution is close to a Steiner tree and heuristics can be applied. These results can serve as basis for the design of efficient, polynomial-time routing algorithms.

Minimum Cost of Capacity Expansion for Time-Limited Transportation Problem On-Demand

The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all origins’ supply and all destinations’ demands as well as the expanding cost is minimum. Actually, MCCETLTPD is a balance transportation problem and a variant problem of minimum cost maximum flow problem. In this paper, by creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into searching feasible flow in the constructed network, and consequently, an algorithm MCCETLTPD-A is developed as MCCETLTPD’s solution method basing minimum cost maximum flow algorithm. Computational study validates that the MCCETLTPD-A algorithm is an efficient approach to solving the MCCETLTPD.

融合均值榜样的反向互学习水母搜索算法

为解决水母搜索算法(jellyfish search algorithm,JS)的洋流运动缺乏多样性、群内运动缺乏引导性、种群间信息无交流,造成搜索速度慢、稳定性差及易早熟的问题,构建了一种融合均值榜样的反向互学习水母搜索算法(oppositional-mutual learning jellyfish search algorithm based on mean-value example,OMLJS).首先在水母跟随洋流运动(全局搜索)部分,利用前两代水母的平均位置代替只考虑上一代水母的平均位置来引导水母个体的位置更新,提高算法的全局搜索能力;其次在水母的群内主动运动(局部搜索)部分,利用最优个体代替随机个体来引导水母进行更有效的搜索,加快算法的收敛速度;然后在水母进入下一次迭代前增加对水母种群进行动态反向互学习步骤,增加种群多样性及增强种群间的信息交流,达到互补另外两个策略,提高算法的整体优化性能.选用12个经典的基准测试优化函数,将OMLJS与5个对比算法从解的平均值、最优值及方差进行对比分析,并用于求解最小生成树问题,OMLJS能够更快地找到最小生成树.实验结果表明,OMLJS的收敛速度、求解精度明显提高.

最小支配阈值集问题的降阶回溯算法

图论中的最小支配阈值集问题是组合优化中的一个NP-Hard问题,该问题是最小支配集问题的一个扩展问题。基于给定无向图G=(V,E)和阈值r的最小支配阈值集问题进行研究,首先得出一些可以降低问题规模的数学性质并证明,利用这些性质可以减小问题规模,降低问题的求解难度;然后设计出上界子算法、下界子算法和降阶子算法,并基于这些子算法提出了一种可以减小问题规模同时得到最优解的降阶回溯算法BAR;最后,通过一个示例分析和若干随机算例测试验证了降阶回溯算法可有效降低问题的求解难度。

基于最小权覆盖的医药电商配送中心选址及区域覆盖优化研究

配送中心选址及区域划分是物流配送过程中的关键环节,直接决定了配送时效及配送成本,在当今电子商务领域显得尤为重要。本文针对国内医药电商企业,提出了一种考虑药品配送时效的配送中心选址策略;随后建立该问题的整数规划模型,采用最小权顶点覆盖方法描述问题,并通过优先队列分支限界算法对此模型进行求解,得出最优选址结果;最后按最小运费原则将被重复覆盖区域进行再划分,得到配送中心选址及区域划分最终方案。本文基于上述策略为国内某头部医药电商企业提供了两种选址方案:保留企业原有配送中心并确定新配送中心选址点(改进选址方案)和从企业所有需求节点中重新为配送中心选址(重选址方案),并使用企业真实销量和物流数据进行算例分析。

基于改进最小方差波束成形的心磁信号的源重建

由于冠心病患者的心磁图在信噪比较低时,最小方差波束成形(MV)方法的源重建效果不理想,提出一种基于改进最小方差波束成形(IMV)方法,在MV方法的基础上,使用导联矩阵和磁场信号二阶特征矩阵组成约束矩阵,构造新的空间滤波器的权矩阵,从而降低输出噪声功率增益。利用点扩散函数理论比较IMV方法和MV方法的空间谱估计的单源分辨率;利用3个电流偶极子产生36通道磁场仿真数据,采用IMV方法和MV方法在低信噪比下对仿真数据进行源重建;最后对3名冠心病患者的36通道心磁图的R波峰和T波峰时刻数据进行源重建。结果表明,IMV方法的单源分辨率更高,对仿真数据及冠心病患者心磁数据的重建精度更好。

求解最小支配集问题的禁忌遗传混合算法

将最小支配集问题转换为一系列判定问题k支配集问题,并提出一种禁忌遗传混合算法对k-DS问题进行求解。此算法将禁忌搜索算法和遗传算法两种启发式算法结合起来,互补不足。高效的邻域结构保证了算法的运行效率,禁忌策略防止算法过早陷入局部最优陷阱,遗传算法框架进一步增强了算法的疏散性。经过与现有求解最小支配集算法的结果进行分析比较,禁忌遗传混合算法的结果较其它算法更优。

两种高效局部搜索算法求解RB模型实例

RB(revised B)模型是一种在约束可满足问题中具备精确相变增长域的随机实例模型,提出两种高效的启发式局部搜索算法用于解决RB模型生成的大值域约束可满足问题。首先为基于权重指导搜索的W-MCH算法,该算法通过约束判断和违反约束数计分来进行搜索,并引入了基于约束违反概率的权重计算公式,根据其关联的约束权重进行修正,再对变量进行迭代调整。然后提出最小化值域的MDMCH算法,该算法通过记录违反约束和逐步消除已违反约束变量的启发式策略来减少搜索空间,并在最小化后的变量域内重新校准变量赋值,进而有效提高算法的收敛速度。此外,还提出了融入模拟退火策略的WSCH和MDSCH算法,这两种算法都能根据变量的表征特点对变量域进行针对性的搜索。实验结果表明,与多种启发式算法相比,这两种算法在精度与时间效率方面均呈现明显提升,在复杂难解的实例中能够提供高效的求解效率,验证了算法的有效性和优越性。

不平衡指派问题的主子阵算法

针对人数和任务数不相等的不平衡指派问题,提出了求解该类指派问题的主子阵算法.给出从低阶主子阵向高阶主子阵寻找主子阵行最小元的变换定理,并举例分析其具体的演算过程.该算法的特点是将求解变换限定在指派矩阵的主子阵上,即不需要考虑指派矩阵整体,只需要在指派矩阵局部进行运算,并从指派矩阵的1阶主子阵的行最小元出发,逐步有规律地找到各阶主子阵的行最小元,最终求得指派问题的最优解.

Finding the Minimum Ratio Traveling Salesman Tour by Artificial Ants

Ants of artificial colony are able to generate good solutions to the famous traveling salesman problem (TSP). We propose an artificial ants algorithm for solving the minimum ratio TSP, which is more general than the standard TSP in combinatorial optimization area. In the minimum ratio TSP, another criterion concerning each edge is added, that is, the traveling salesman can have a benefit if he travels from one city to another. The objective is to minimize the ratio between total costs or distances and total benefits. The idea of this type of optimization is in some sense quite similar to that of traditional cost-benefit analysis in management science. Computational results substantiate the solution quality and efficiency of the algorithm.

Gradient Gene Algorithm: a Fast Optimization Method to MST Problem

The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is introduced. Compared with other evolutionary algorithms on MST problem, it is more advanced: firstly, very simple and easy to realize; then, efficient and accurate; finally general on other combination optimization problems.

On the Artificial Equilibrium Points in a Generalized Restricted Problem of Three Bodies

The present article studies the stability conditions of central control artificial equilibrium generalized restricted problem of three bodies. It is generalized in the sense that here we have taken the larger primary body to be in shape of an oblate spheroid. The equilibrium points are sought by the application of the propellant for which it would just balance the gravitational forces. The launching flight of such a satellite is seen to be applicable for having arbitrary space stations for these different missions. Specialty of the result of the investigation lies in the fact that an arbitrary space station can be formed to attain any specified mission.

Shallow water bathymetry based on a back propagation neural network and ensemble learning using multispectral satellite imagery

The back propagation(BP)neural network method is widely used in bathymetry based on multispectral satellite imagery.However,the classical BP neural network method faces a potential problem because it easily falls into a local minimum,leading to model training failure.This study confirmed that the local minimum problem of the BP neural network method exists in the bathymetry field and cannot be ignored.Furthermore,to solve the local minimum problem of the BP neural network method,a bathymetry method based on a BP neural network and ensemble learning(BPEL)is proposed.First,the remote sensing imagery and training sample were used as input datasets,and the BP method was used as the base learner to produce multiple water depth inversion results.Then,a new ensemble strategy,namely the minimum outlying degree method,was proposed and used to integrate the water depth inversion results.Finally,an ensemble bathymetric map was acquired.Anda Reef,northeastern Jiuzhang Atoll,and Pingtan coastal zone were selected as test cases to validate the proposed method.Compared with the BP neural network method,the root-mean-square error and the average relative error of the BPEL method can reduce by 0.65–2.84 m and 16%–46%in the three test cases at most.The results showed that the proposed BPEL method could solve the local minimum problem of the BP neural network method and obtain highly robust and accurate bathymetric maps.

一种离散轨道数据约束下的地月三体轨道脉冲转移算法

针对地月圆型限制性三体模型下的多脉冲轨道转移问题,基于离散轨道数据提出了一种分层重构建模方法和双层优化求解算法。通过将最小脉冲问题分层重构,建模为双层优化问题,并给出双层优化求解算法实现了转移轨道设计:上层优化问题考虑了离散轨道数据约束,算法采用智能算法使其具有普适性和计算效率;下层优化问题则在始末状态约束、时间约束、脉冲约束和脉冲点约束等多种约束下仅优化脉冲序列,避免了对初始值的敏感性,算法通过序列二次规划方法可得到局部最优解。通过多种场景下的仿真验证,可得所提出的双层优化建模框架和求解算法适用于不同类型的轨道转移,实现了多脉冲的能量最优转移,通过对比仿真对于地月三体系统下特殊轨道之间的转移轨道设计具有重要意义。

区间图最小连通支配集问题的最优算法

针对区间图的最小连通支配集问题,设计简洁的线性算法。对该算法的时间、空间复杂度进行分析,并从实例和理论两方面验证其可行性和有效性。研究结果表明:该算法是线性的,即区间图上可在O(m+n)时间内找到一个最小连通支配集。