Applying Ant System for solving Unequal Area Facility Layout Problems

Ant Colony Optimization (ACO) is a young metaheuristic algorithm which has shown promising results in solving many optimization problems. To date, a formal ACO-based metaheuristic has not been applied for solving Unequal Area Facility Layout Problems (UA-FLPs). This paper proposes an Ant System (AS) (one of the ACO variants) to solve them. As a discrete optimization algorithm, the proposed algorithm uses slicing tree representation to easily represent the problems without too restricting the solution space. It uses several types of local search to improve its search performance. It is then tested using several case problems with different size and setting. Overall, the proposed algorithm shows encouraging results in solving UA-FLPs.     

On the K shortest path trees problem

We address the problem of finding the K best path trees connecting a source node with any other non-source node in a directed network with arbitrary lengths. The main result in this paper is the proof that the kth shortest path tree is adjacent to at least one of the previous (k-1) shortest path trees. Consequently, we design an O(f(n,m,C_max)+Km) time and O(K+m) space algorithm to determine the K shortest path trees, in a directed network with n nodes, m arcs and maximum absolute length C_max, where O(f(n,m,C_max)) is the best time needed to solve the shortest simple paths connecting a source node with any other non-source node.     

Choquet-based optimisation in multiobjective shortest path and spanning tree problems

This paper is devoted to the search of Choquet-optimal solutions in finite graph problems with multiple objectives. The Choquet integral is one of the most sophisticated preference models used in decision theory for aggregating preferences on multiple objectives. We first present a condition on preferences (name hereafter preference for interior points) that characterizes preferences favouring compromise solutions, a natural attitude in various contexts such as multicriteria optimisation, robust optimisation and optimisation with multiple agents. Within Choquet expected utility theory, this condition amounts to using a submodular capacity and a convex utility function. Under these assumptions, we focus on the fast determination of Choquet-optimal paths and spanning trees. After investigating the complexity of these problems, we introduce a lower bound for the Choquet integral, computable in polynomial time. Then, we propose different algorithms using this bound, either based on a controlled enumeration of solutions (ranking approach) or an implicit enumeration scheme (branch and bound). Finally, we provide numerical experiments that show the actual efficiency of the algorithms on multiple instances of different sizes.     

星载激光雷达云和气溶胶分类反演算法研究

激光探测对于获取云和气溶胶的垂直廓线,研究大气中云和气溶胶的垂直分布特征以及对全球气候变化的影响意义重大。而星载大气激光雷达云气溶胶分类算法的研究,对于激光雷达数据的参数反演及应用极为重要。针对激光条件下探测的云和气溶胶特有的光学信息和空间分布,结合概率统计与机器学习算法,提出了一种对于云/气溶胶、云相态及气溶胶子类型识别的分类算法,实现了星载激光雷达的大气特征层快速、有效分类。算法采用中国地区2016年CALIOP的观测数据作为样本数据,主要由三部分组成：（1）基于激光探测的云和气溶胶层不同的光学特性以及地理空间分布特征,分别构建了云和气溶胶的γ₅₃₂,χ,δ,Z和lat的五维概率密度函数,以此为基础构建云气溶胶的分类置信函数,并基于此实现了云和气溶胶类型的反演;（2）选取支持向量机(SVM)作为随机朝向冰晶粒子(ROI)和水云分类的算法模型基础,结合云层的γ₅₃₂,χ,δ Z和云顶温度T的概率密度函数构建ROI,水平朝向冰晶粒子(HOI)和水云的分类置信函数以修正SVM误分的特征层以及筛选出水云中少部分的HOI冰云,获得云相态的分类结果;（3）以各气溶胶子类型的光学以及空间分布特性为基础,采用决策树策略的气溶胶子类型识别算法实现了对气溶胶子类型的区分,完成气溶胶子类型的识别。利用现有CALIOP观测结果作为样本数据构建分类数据库,避免了对于地面以及航测数据的依赖,而机器学习则大大简化了算法的实现过程,使得云气溶胶分类更加高效。算法结果与正交极化云气溶胶激光雷达垂直特征层分布数据(CALIPSO VFM)产品对比分析：云层有98.51%一致性,气溶胶有88.43%的一致性,且白天比夜间一致性高。对于云相态分类,可以有效区分出水云和冰云,其中二者水云一致性高达93.44%。在气溶胶子类型反演结果中,可以准确识别出大多数气溶胶特征层子类型。霾、沙尘以及晴空三种典型情况下的反演结果均与CALIOP VFM产品数据具有较好的一致性。其中,霾天的大部分煤烟型以及污染型（污染沙尘以及污染大陆）气溶胶反演结果与VFM具有较好的一致性。沙尘天也能够获得较好的沙尘以及污染沙尘的结果。晴空为数不多的气溶胶层也取得了较为一致的结果。对于实现的星载大气激光雷达特征层分类算法,针对CALIOP激光测量的云气溶胶层的分类进行了重要的改进,在保证一定精度的基础上,简化了算法,提高了数据处理的效率,在下一步工作中,将分别构建不同时段和季节的分类模型以及提高两种不同偏振特性的冰云和气溶胶子类型的分类精度。     

双树小波变换与小波树稀疏联合的低场CS-MRI算法

压缩感知理论常用在磁共振快速成像上,仅采样少量的K空间数据即可重建出高质量的磁共振图像.压缩感知磁共振成像技术的原理是将磁共振图像重建问题建模成一个包含数据保真项、稀疏先验项和全变分项的线性组合最小化问题,显著减少磁共振扫描时间.稀疏表示是压缩感知理论的一个关键假设,重建结果很大程度上依赖于稀疏变换.本文将双树复小波变换和小波树稀疏联合作为压缩感知磁共振成像中的稀疏变换,提出了基于双树小波变换和小波树稀疏的压缩感知低场磁共振图像重建算法.实验表明,本文所提算法可以在某些磁共振图像客观评价指标中表现出一定的优势.     

A Contour Method on Cayley Trees

We consider finite-range lattice models on Cayley trees with two basic properties: the existence of only a finite number of ground states and with a Peierls type condition. We define the notion of a contour for the model on the Cayley tree. By a contour argument we show the existence of s different (where s is the number of ground states) Gibbs measures. Dedicated to N.N. Ganikhodjaev on the occasion of his 60th birthday. The work supported by NATO Reintegration Grant: FEL.RIG.980771.     

A heuristic for the Steiner problem in graphs

In this paper, we present a heuristic for the Steiner problem in graphs (SPG) along with some experimental results. The heuristic is based on an approach similar to Prim's algorithm for the minimum spanning tree. However, in this approach, arcs are associated with preference weights which are used to break ties among alternative choices of shortest paths occurring during the course of the algorithm. The preference weights are calculated according to a global view which takes into consideration the effect of all the regular nodes, nodes to be connected, on determining the choice of an arc in the solution tree.     

Computational algorithms for hierarchically structured project networks

A new approach to large size network management based on a structured network representation is proposed. Definitions of arc-structured and vertex-structured networks are given and an extension of topological sorting and time computation algorithms is described. A generalization of the concept of vertex-structured networks is discussed.     

The design of branch and bound algorithms for a class of nonlinear integer programs

This paper is concerned with computational experimentation leading to the design of effective branch and bound algorithms for an important class of nonlinear integer programming problems, namely linearly constrained problems, which are used to model several real-world situations. The main contribution here is a study of the effect of node and branching variable selection and storage reduction strategies on overall computational effort for this class of problems, as well as the generation of a set of adequate test problems. Several node and branching variable strategies are compared in the context of a pure breadth-first enumeration, as well as in a special breadth and depth enumeration combination approach presented herein. Also, the effect of using updated pseudocosts is briefly addressed. Computational experience is presented on a set of eighteen suitably-sized nonlinear test problems, as well as on some random linear integer programs. Some of the new rules proposed are demonstrated to be significantly superior to previously suggested strategies; interestingly, even for linear integer programming problems.     

Random walks on the Bethe lattice

We obtain random walk statistics for a nearest-neighbor (Pólya) walk on a Bethe lattice (infinite Cayley tree) of coordination numberz, and show how a random walk problem for a particular inhomogeneous Bethe lattice may be solved exactly. We question the common assertion that the Bethe lattice is an infinite-dimensional system.Supported in part by the U.S. Department of Energy.