Stochastic robustness synthesis applied to a benchmark control problem

Stochastic robustness synthesis is used to find compensators that solve a benchmark problem. The synthesis minimizes a robustness cost function that is the weighted quadratic sum of stochastic robustness metrics. These metrics — probability of instability, probability of actuator saturation, and probability of settling time violation — are estimated using Monte Carlo analysis. A simple search method minimizes the robustness cost by selecting values for the design parameters of a linear quadratic Gaussian regulator. The resulting compensators are robust, require low actuator authority, and compare well with previous designs.     

Orthogonal projections applied to the assignment problem

This paper presents a significant improvement to the traditional neural approach to the assignment problem (AP). The technique is based on identifying the feasible space (F) with a linear subspace of R(n(2)), and then analyzing the orthogonal projection onto F. The formula for the orthogonal projection is shown to be simple and easy to integrate into the traditional neural model. This projection concept was first developed by Wolfe et al. (1993), but here we show that the projection can be computed in a much simpler way, and that the addition of a "clip" operator at the boundaries of the cube can improve the results by an order of magnitude in both accuracy and run time. It is proven that the array of numbers that define an AP can be projected onto F without loss of information and the network can be constrained to operate exclusively in F until a neuron is saturated (i.e., reaches the maximum or minimum activation). Two "clip" options are presented and compared. Statistical results are presented for randomly generated APs of sizes n=10 to n=50. The statistics confirm the theory.     

The parallel assignment problem redefined

The parallel assignment problem is slightly redefined using a subtler cost function that tends to reduce the number of extra assignments required. It is shown that the new problem, like the classical, is NP-hard. The new problem is then solved for the restricted case of assignment from invertible functions of single variables. For this restricted case and optimum solution can be found in linear time for both the classical problem and the new problem. However, the number of extra assignments required for the classical problem is equal to the number of cycles in the dependency graph, while in the new problem it is equal to the number of isolated cycles in the dependency graph which may be less     

The ant system applied to the quadratic assignment problem

In recent years, there has been growing interest in algorithms inspired by the observation of natural phenomena to define computational procedures that can solve complex problems. We describe a distributed heuristic algorithm that was inspired by the observation of the behavior of ant colonies, and we propose its use for the quadratic assignment problem. The results obtained in solving several classical instances of the problem are compared with those obtained from other evolutionary heuristics to evaluate the quality of the proposed system     

基于OpenMP求解QAP的并行粒子群优化算法

提出了一种基于OpenMP求解QAP的并行粒子群优化算法.该算法将遗传算法的交叉策略引入PSO算法中,同时采用禁忌搜索算法作为局部搜索算法.在QAPLIB实例上的测试结果表明,并行PSO算法在所有测试实例上都获得了超线性加速比,且运行结果优于串行算法.     

Scalability aspects of parallel multigrid

This paper summarizes theoretical and practical investigations into the effect of parallelization by grid-partitioning on the performance of multigrid methods for the solution of partial differential equations on general two-dimensional domains. Particular emphasis will be placed on the algorithmic scalability for MIMD distributed memory systems. Experimental results for two Navier-Stokes test problems, presented in the last section of the paper, show that the theoretically predicted dependency of the combined numerical and parallel efficiencies of multigrid methods on the number of processors employed is in fact very weak. This leads to the conclusion that multigrid is an appropriate candidate for solving partial differential equations on massively parallel machines.     

Scalability of parallel algorithm-machine combinations

Scalability has become an important consideration in parallel algorithm and machine designs. The word scalable, or scalability, has been widely and often used in the parallel processing community. However, there is no adequate, commonly accepted definition of scalability available. Scalabilities of computer systems and programs are difficult to quantify, evaluate, and compare. In this paper, scalability is formally defined for algorithm-machine combinations. A practical method is proposed to provide a quantitative measurement of the scalability. The relation between the newly proposed scalability and other existing parallel performance metrics is studied. A harmony between speedup and scalability has been observed. Theoretical results show that a large class of algorithm-machine combinations is scalable and the scalability can be predicted through premeasured machine parameters. Two algorithms have been studied on an nCUBE 2 multicomputer and on a MasPar MP-1 computer. These case studies have shown how scalabilities can be measured, computed, and predicted. Performance instrumentation and visualization tools also have been used and developed to understand the scalability related behavior     

求解频率指派问题的Multi-Quadric算法

为有效解决频率指派问题,提出了一种解决该问题的曲面拟合Multi-Quadric算法,算法将随机指派方案及其对应的干扰值作为多元散乱数据采样点,以此为基础进行多元散乱数据拟合,通过对拟合曲面极小值的寻找从而完成对频率指派问题的优化。优化结果可直接应用于实际工程,也可作为其它优化算法的初始解。算法在电台数量规模较大的应用中体现出良好的性能,算法结果作为蚁群、遗传算法的初始解,后继算法收敛速度明显提高。     

Elementary landscape decomposition of the frequency assignment problem

The Frequency Assignment Problem (FAP) is an important problem that arises in the design of radio networks, when a channel has to be assigned to each transceiver of the network. This problem is a generalization of the graph coloring problem. In this paper we study a general version of the FAP that can include adjacent frequency constraints. Using concepts from landscapes’ theory, we prove that this general FAP can be expressed as a sum of two elementary landscapes. Further analysis also shows that some subclasses of the problem correspond to a single elementary landscape. This allows us to compute the kind of neighborhood information that is normally associated with elementary landscapes. We also provide a closed form formula for computing the autocorrelation coefficient for the general FAP, which can be useful as an a priori indicator of the performance of a local search method.     

Sequential and parallel path-relinking algorithms for the quadratic assignment problem

The quadratic assignment problem, a classical combinatorial optimization problem, has garnered much attention due to its many applications and solution complexity. This research represents the first use of parallelization for path relinking within the QAP setting. We used a simple form of path relinking to focus on the parallel implementation's elements and to determine their impact when used with a method of this type. Our computational results demonstrate highly attractive outcomes despite the procedure's simplicity and show in particular the value of a well-designed parallelization process in this context.     

Massively parallel augmenting path algorithms for the assignment problem

In this paper we describe how to apply fine grain parallelism to augmenting path algorithms for the dense linear assignment problem. We prove by doing that the technique we suggest, can be efficiently implemented on commercial available, massively parallel computers. Using n processors, our method reduces the computational complexity from the sequentialO(n ³) to the parallel complexity ofO(n ²). Exhaustive experiments are performed on a Maspar MP-2 in order to determine which of the algorithmic flavors that fits best onto this kind of architecture.     

频率指配问题求解的模式分析核方法

为有效解决频率指配问题,提出了一种解决该问题的模式分析核方法,算法利用频率指配方案的评估函数值构建核矩阵,以核矩阵为基础在特征空间中运行聚类分析算法,对频率指配方案相似性进行度量,完成频率指配方案的归类划分。优化结果可直接作为跳频指配结果,也可作为其他优化算法的初始解。该算法在电台数量规模较大的应用中体现出良好的性能,算法结果作为蚁群、遗传算法的初始解,后继算法收敛速度明显提高。     

A new Multiobjective Artificial Bee Colony algorithm to solve a real-world frequency assignment problem

Artificial bee colony (ABC) is a recently introduced algorithm that models the behavior of honey bee swarm to address a multiobjective version for ABC, named Multiobjective Artificial Bee Colony algorithm (MO-ABC). We describe the methodology and results obtained when applying the new MO-ABC metaheuristic, which was developed to solve a real-world frequency assignment problem (FAP) in GSM networks. A precise mathematical formulation for this problem was used, where the frequency plans are evaluated using accurate interference information taken from a real GSM network. In this paper, our work is divided into two stages: In the first one, we have accurately tuned the algorithm parameters. Then, in the second step, we have compared the MO-ABC with previous versions of distinct multiobjective algorithms already developed to the same instances of the problem. As we will see, results show that this approach is able to obtain reasonable frequency plans when solving a real-world FAP. In the results analysis, we consider as complementary metrics the hypervolume indicator to measure the quality of the solutions to this problem as well as the coverage relation information.     

An ANTS heuristic for the frequency assignment problem

The problem considered in this paper consists in assigning frequencies to radio links between base stations and mobile transmitters in order to minimize the global interference over a given region. This problem is NP-hard and few results have been reported on techniques for solving it to optimality. We have applied to this problem an ANTS metaheuristic, that is, an approach following the ant colony optimization paradigm. Computational results, obtained on a number of standard problem instances, testify the effectiveness of the proposed approach.     

Algorithms for the generalized weighted frequency assignment problem

We report the performance of 15 construction heuristics to find initial solutions, and 4 search algorithms to solve a frequency assignment problem where the value of an assigned frequency is determined by the site where it is assigned. The algorithms were tested on 3 sets of problems, the first one corresponds to the well-known Philadelphia problems, and the last two correspond to situations frequently encountered when FM frequencies are assigned in Mexico. Our experimental results show that the construction heuristics that consider the weights of the sites perform well. Among the 4 search algorithms tested, the one based on cross entropy performed better than the others in small problems, whereas in large problems the algorithm based on simulated annealing performed the best.     

A multiobjective hybrid ant colony optimization approach applied to the assignment and scheduling problem

The assignment and scheduling problem is inherently multiobjective. It generally involves multiple conflicting objectives and large and highly complex search spaces. The problem allows the determination of an efficient allocation of a set of limited and shared resources to perform tasks, and an efficient arrangement scheme of a set of tasks over time, while fulfilling spatiotemporal constraints. The main objective is to minimize the project makespan as well as the total cost. Finding a good approximation set is the result of trade‐offs between diversity of solutions and convergence toward the Pareto‐optimal front. It is difficult to achieve such a balance with NP‐hard problems. In this respect, and in order to efficiently explore the search space, a hybrid bidirectional ant‐based approach is proposed in this paper, which is an improvement of a bi‐colony ant‐based approach. Its main characteristic is that it combines a solution construction developed for a more complicated problem with a Pareto‐guided local search engine.     

求解指派问题的一次性分配算法

匈牙利算法是求解指派问题的全局最优求解算法,但是经典的匈牙利算法存在着实现难、处理速度慢等不足。提出了一种改进匈牙利算法,对匈牙利算法寻找独立零的次序进行了改进,从而避免了匈牙利算法通常需要进行多次试分配的不足。针对改进前后两种算法的复杂度、运算时间、精确度等进行了对比分析,结果表明,改进的算法是一种高精度的近似最优求解算法;与匈牙利算法相比,改进的算法易于编程实现,且时间花费较低,是一种适用于工程实时应用的有效求解算法。     

Exploiting multilevel parallelism on a many-core system for the application of hyperheuristics to a molecular docking problem

The solution of Protein–Ligand Docking Problems can be approached through metaheuristics, and satisfactory metaheuristics can be obtained with hyperheuristics searching in the space of metaheuristics implemented inside a parameterized schema. These hyperheuristics apply several metaheuristics, resulting in high computational costs. To reduce execution times, a shared-memory schema of hyperheuristics is used with four levels of parallelism, two for the hyperheuristic and two for the metaheuristics. The parallel schema is executed in a many-core system in “native mode,” and the four-level parallelism allows us to take full advantage of the massive parallelism offered by this architecture and obtain satisfactory fitness and an important reduction in the execution time.     

改进人工蜂群算法求解信道分配问题

为求解频率分配问题提出一种改进人工蜂群算法。该算法保持人工蜂群算法原有搜索流程,引入蝙蝠算法回声定位的机制,令蜜蜂拥有蝙蝠的能力,在搜索过程中调节响度和频率逐渐接近目标,以提高频率分配过程中的局部搜索精度和效率。算法利用自然选择阈值来降低搜索过程中对当前全局最优解的依赖,以提高种群多样性,降低陷入局部最优解的可能性。经固定频率分配问题的仿真实验和与其他算法对比结果表明,本文算法不仅具有较快的全局收敛速度,而且有高质量的解和高的效率。