GRASP: basic components and enhancements

GRASP (Greedy Randomized Adaptive Search Procedures) is a multistart metaheuristic for producing good-quality solutions of combinatorial optimization problems. Each GRASP iteration is usually made up of a construction phase, where a feasible solution is constructed, and a local search phase which starts at the constructed solution and applies iterative improvement until a locally optimal solution is found. While, in general, the construction phase of GRASP is a randomized greedy algorithm, other types of construction procedures have been proposed. Repeated applications of a construction procedure yields diverse starting solutions for the local search. This paper gives an overview of GRASP describing its basic components and enhancements to the basic procedure, including reactive GRASP and intensification strategies.     

Quantum-inspired evolutionary algorithm for analog test point selection

An important problem that arises in fault diagnosis of analog circuit for fault dictionary technique is the test point selection, which is known to be NP-hard. This paper develops a mathematical optimization model for analog test point selection (ATPS) problem and proposes a novel method to solve it based on quantum-inspired evolutionary algorithm (QEA). The proposed method uses the solution produced by the inclusive algorithm to initialize Q-bit individuals and presents a new fitness function to search the global minimum test point set. In addition, an approach for dynamically determining the magnitude of rotation angle is introduced to accelerate the convergent speed. The efficiency of the proposed algorithm is proven by one practical analog circuit example and a group of statistical experiments. Results show that the proposed algorithm, compared with other methods, finds the global minimum set of test points more efficiently and more accurately.     

Application of Rollout Strategy to Test Points Selection for Integer-Coded Fault Wise Table

Test points selection for integer-coded fault wise table is a discrete optimization problem. The global minimum set of test points can only be guaranteed by an exhaustive search which is eompurationally expensive. In this paper, this problem is formulated as a heuristic depth-first graph search problem at first. The graph node expanding method and rules are given. Then, rollout strategies are applied, which can be combined with the heuristic graph search algorithms, in a computationally more efficient manner than the optimal strategies, to obtain solutions superior to those using the greedy heuristic algorithms. The proposed rollout-based test points selection algorithm is illustrated and tested using an analog circuit and a set of simulated integer-coded fault wise tables. Computa- tional results are shown, which suggest that the rollout strategy policies are significantly better than other strategies.     

VLSI电路划分问题的分散搜索算法

电路划分是超大规模集成电路(VLSI)设计自动化中的一个关键阶段,是NP困难的组合优化问题.本文把基于顶点移动的Fiduccia-Mattheyses(FM)算法结合到分散搜索算法框架中,提出了电路划分的分散搜索算法.算法利用FM算法进行局部搜索,利用分散搜索的策略进行全局搜索.为满足该方法对初始解的质量和多样性的要求,采用贪心随机自适应搜索过程(GRASP)和聚类相结合的方法产生初始解.实验结果表明,算法可以求解较大规模的电路划分实例,且与基于多级框架的划分算法hMetis相比,划分的质量有明显的提高.     

A test points selection method for analog fault dictionary techniques

The problem of test point selection is important in the area of fault diagnosis and circuit testing. In this paper, the problem of near optimum test points set selection for analog fault dictionary is considered. This problem is formulated as a depth-first graph search problem. So the test points selection progress is transformed to a graph node expanding progress. The graph node construction method and node expanding procedure are given also. The proposed graph search method guarantee a maximum information increase of S _opt by adding a test point to S _opt each time, where S _opt is the desired test points set used on the path from current node to root node. So a global minimum test points set can be more likely achieved than other methods. The results of statistical experiments indicate that the proposed method more accurately finds the global minimum set of test points without increasing time complexity; therefore, it is a good solution to minimize the size of test points set.     

Test Points Selection for Analog Fault Dictionary Techniques

The test points selection problem for analog fault dictionary is researched extensively in many literatures. Various test points selection strategies and criteria for Integer-Coded fault wise table are described and compared in this paper. Firstly, the construction method of Integer-Coded fault wise table for analog fault dictionary is described. Secondly, theory and algorithms associated with these strategies and criteria are reviewed. Thirdly, the time complexity and solution accuracy of existing algorithms are analyzed and compared. Then, a more accurate test points selection strategy is proposed based on the existing strategies. Finally, statistical experiments are carried out and the accuracy and efficiency of different strategies and criteria are compared in a set of comparative tables and figures. Theoretical analysis and statistical experimental results given in this paper can provide an instruction for coding an efficient and accurate test points selection algorithm easily.     

A multi-objective genetic local search algorithm and itsapplication to flowshop scheduling

We propose a hybrid algorithm for finding a set of nondominated solutions of a multi objective optimization problem. In the proposed algorithm, a local search procedure is applied to each solution (i.e., each individual) generated by genetic operations. Our algorithm uses a weighted sum of multiple objectives as a fitness function. The fitness function is utilized when a pair of parent solutions are selected for generating a new solution by crossover and mutation operations. A local search procedure is applied to the new solution to maximize its fitness value. One characteristic feature of our algorithm is to randomly specify weight values whenever a pair of parent solutions are selected. That is, each selection (i.e., the selection of two parent solutions) is performed by a different weight vector. Another characteristic feature of our algorithm is not to examine all neighborhood solutions of a current solution in the local search procedure. Only a small number of neighborhood solutions are examined to prevent the local search procedure from spending almost all available computation time in our algorithm. High performance of our algorithm is demonstrated by applying it to multi objective flowshop scheduling problems     

加油站选择问题的贪心解法

贪心算法以其简单、直观、有效而受到人们的重视，特别是对于具有最优子结构和贪心选择性质的一类实际问题．它一般可以通过一系列局部最优选择来获得整体最优解。本文首先对加油站选择问题进行了分析，并给出了该类问题的贪心解法，同时对所提出算法的时间复杂度进行了分析。实验结果验证了所提出方法的有效性。     

A model for virtual network embedding using Artificial Bee Colony

In a network virtualization environment, a significant research problem is that of virtual network embedding. As the network virtualization system is distributed in nature, an effective solution on how to optimally embed a dynamically generated virtual network request on the substrate networks that are owned and managed by multiple infrastructure providers needs proper attention. The problem is computationally hard, and therefore, many approaches, implying heuristics/meta‐heuristics, have been applied for the same. A meta‐heuristic, Artificial Bee Colony algorithm is getting popular due to its robustness toward complex problem solving. A novel approach based on Artificial Bee Colony to address the dynamic virtual network embedding problem in a multiple infrastructure provider scenario is proposed in this work. Bee population is initialized by using a greedy heuristic in which the number of substrate networks together with virtual network requests constructs a bee. Generated solution, in the population, is improvised by using greedy selection that explores a local search method adopted by the bees. In greedy selection, the new candidate source is memorized by the bee if its fitness is better than the fitness of the existing source. The performance study of the proposed model is done by simulation over various metrics such as embedding cost, embedding time, and acceptance ratio. A comparative study is conducted with other nature‐inspired virtual network embedding algorithms on these metrics. The findings affirm that the proposed virtual network embedding approach performs well and produces better results.     

Selection of Minimal Test Points Set for Integer-Coded Fault Wise Table

Test points selection for integer-coded fault wise table is a discrete optimization problem. On one hand, traditional exhaustive search method is computationally expensive. On the other hand, the space complexity of traditional exhaustive is low. A tradeoff method between the high time complexity and low space complexity is proposed. At first, a new fault-pair table is constructed based on the integer-coded fault wise table. The fault-pair table consists of two columns： one column represents fault pair and the other represents test points set that can distinguish the corresponding faults. Then, the rows are arranged in ascending order according to the cardinality of corresponding test points set. Thirdly, test points in the top rows are selected one by one until all fault pair are isolated. During the test points selection process, the rows that contain selected test points are deleted and then the dimension of fault-pair table decreases gradually. The proposed test points selection algorithm is illustrated and tested using an integercoded fault wise table derived from a real analog circuit. Computational results suggest show policies are better than the exhaustive strategy.     

Diagnosis of a soft short and local variations of parameters occurring simultaneously in analog CMOS circuits

This paper is devoted to fault diagnosis of nonlinear analog CMOS circuits designed in nanometer technology. A method that allows diagnosing a single soft short and local parameter variations, occurring simultaneously, is developed. The method exploits DC measurements at limited number of points in the test phase. The diagnostic test leads to a system of nonlinear algebraic equations, not given in explicit analytical form, that may have multiple solutions. The solutions determine the sets comprising one soft short value and several values of the preliminary selected parameters. To find them an extended simplicial algorithm is developed. It allows tracing different space curves, leading to different solutions. Moreover, a procedure for selecting the actual solution from among the obtained ones is proposed. For illustration a representative numerical example is discussed in detail.     

一种针对频率分配问题的改进ANTS算法

频率分配问题是近年来通信领域研究的热点。针对FAP问题提出了一种结合模拟退火算法的改进ANTS算法。运用模拟退火算法产生次优解,利用次优解分配初始信息素,并利用ANTS算法来寻求最佳方案。在ANTS算法的每个蚂蚁寻找局部最优过程中,为了加快运算速度,对局部寻优过程进行了改进。实验结果表明,在解质量相当的情况下,该算法能够大大地加快收敛速度,特别是针对一些较复杂的分配情况,效果明显。     

基于贪心遗传算法求解0-1背包问题

在解决0-1背包问题中,将贪心算法和遗传算法相结合,提出了贪心遗传算法。通过算法构造出更优的新算子,与原有算子相比,既加快了算法的收敛速度,又克服了传统方法容易陷入局部最优的特点,提高了搜索效率。通过计算机仿真试验结果表明,贪心遗传算法相比普通的遗传算法具有更好的近似解,充分证明了贪心遗传算法来求解背包问题的有效性和实用性。     

Greedy Algorithm Applied to Relay Selection for Cooperative Communication Systems in Amplify-and-Forward Mode

Using a relaying system to provide spatial diversity and improve the system performance is a tendency in the wireless cooperative communications. Amplify-and-forward (AF) mode with a low complexity is easy to be implemented. Under the consideration of cooperative communication systems, the scenario includes one information source, M relay stations and N destinations. This work proposes a relay selection algorithm in the Raleigh fading channel. Based on the exhaustive search method, easily to realize, the optimal selection scheme can be found with a highly complicated calculation. In order to reduce the computational complexity, an approximate optimal solution with a greedy algorithm applied for the relay station selection is proposed. With different situations of the communication systems, the performance evaluation obtained by both the proposed algorithm and the exhaustive search algorithm are given for comparison. It shows the proposed algorithm could provide a solution approach to the optimal one.     

GWO与ABC的混合优化算法及其聚类优化

灰狼优化算法（Grey Wolf Optimizer,GWO）和人工蜂群算法（Artificial Bee Colony,ABC）是两种流行且高效的群智能优化算法.GWO具有局部搜索能力强等优势,但存在全局搜索能力弱等缺陷;而ABC具有全局搜索能力强等优点,但存在收敛速度慢等不足.为实现二者优势互补,提出了一种GWO与ABC的混合算法（Hybrid GWO with ABC,HGWOA）.首先,使用静态贪心算法替代ABC雇佣蜂阶段中的动态贪心算法来强化探索能力,同时为弥补其收敛速度降低的不足,提出一种新型的搜索蜜源方式;然后,去掉影响收敛速度的侦查蜂阶段,在雇佣蜂阶段再添加反向学习策略,以避免搜索陷入局部最优;最后,为了平衡以上雇佣蜂阶段的探索能力,在观察蜂阶段,自适应融合GWO,以便增强开采能力和提高优化效率.大量的函数优化和聚类优化的实验结果表明,与state-of-the-art方法相比,HGWOA具有更好的优化性能及更强的普适性,且能更好地解决聚类优化问题.     

Near-field time-frequency localization method using sparse representation

This paper presents a novel near-field source localization method based on the time-frequency sparse model.Firstly,the method converts the time domain data of array output into time-frequency domain by time-frequency transform;then constructs sparse localization model by utilizing the specially selected time-frequency points,and finally the greedy algorithms are chosen to solve the sparse problem to localize the source.When the coherent sources exist,we propose an additional iterative selection procedure to improve the estimation performance.The proposed method is suitable for uncorrelated and coherent sources,moreover,the improved estimation accuracy and the robustness to low signal to noise ratio(SNR) are achieved.Simulations results verify the efficiency of the proposed algorithm.     

A Novel Test Point Selection Method for Analog Fault Dictionary Techniques

Most of the recently reported test point selection algorithms for analog fault dictionary techniques are based on integer-coded table (ICT) technique. Hence, the accuracy of these algorithms is closely related to the accuracy of the ICT technique. Unfortunately, this technique is not accurate, especially when the size of fault dictionary is large. This paper proposes an accurate fault-pair Boolean table technique for the test point selection problem. First, the approach to transform the fault dictionary into a fault-pair Boolean table is introduced. Then, a test point selection algorithm based on the fault-pair Boolean table is proposed. Thirdly, several example circuits are used to illustrate the proposed algorithm. Simulated results indicate that the proposed method is more accurate than the other methods. Therefore, it is a good solution for minimizing the size of the test point set.     

基于贪心策略的大规模MIMO系统信号检测算法

针对传统球形译码性能和计算复杂度受到初始半径及搜索策略制约的问题,提出了一种新的基于M算法的贪心策略球形译码检测算法,对树搜索的方法进行了改进,先将该层信号集合中的距离增量进行排序,然后选择距离增量最小的M个点为信号点,这样每一次选取的信号点相对该层都是局部最优的.仿真结果表明,相比于传统球形译码检测算法,当M为1时,该算法可以降低约30％的计算复杂度.使球形译码算法的效率得到了很大的提高,可以运用于大规模MIMO系统中.     

Test generation for specification test of analog circuits using efficient test response observation methods

In this paper, a new automated test generation methodology for specification testing of analog circuits using test point selection and efficient analog test response waveform capture methods for enhancing the test accuracy is proposed. The proposed approach co-optimizes the construction of a multi-tone sinusoidal test stimulus and the selection of the best set of test response observation points. For embedded analog circuits, it uses a subsampling-based digitization method compatible with IEEE 1149.1 to accurately digitize the analog test response waveforms. The proposed specification approach uses ‘alternate test’ framework, in which the specifications of the analog circuit-under-test are computed (predicted) using statistical regression models that are constructed based on process variations and corresponding variations of test responses captured from different test observation points. The test generation process and the test point selection process aim to maximize the accuracy of specification prediction. Experimental results validating the proposed specification test approach are presented.     

一种基于混合智能算法的协作中继选择新方法

针对多用户多中继场景下协作通信系统的中继选择问题,提出了一种基于混合智能算法的协作中继选择新方法。不同于现有的为每个源节点分配一个中继节点的中继选择方法,新方法建立了为每个源节点分配一个或多个中继节点的优化模型,以最大化多用户多中继协作系统的最小接收信噪比为优化目标,采用结合了模拟退火与遗传算法的混合智能算法来搜寻中继选择问题的最优解。仿真结果表明,所提方法可显著提高目的端的接收信噪比,且算法具有较强的全局搜索和快速寻优能力。