Optimizing discrete stochastic systems using simulated annealing and simulation

The objective of this paper is to present an integrated approach of two models: simulation and optimization. This approach is used to determine the design parameters of stochastically constrained systems where the measure of performance is available only via simulation. The optimization model is solved using simulated annealing (SA) for parameter selection followed by the use of Monte Carlo simulation to evaluate the measure of performance. Based on the expected simulation output, the parameter set is either accepted or rejected. A modified rejection/acceptance criterion is presented for the proposed SA algorithm taking into consideration the stochastic system constraints. Moreover, a control variate is employed as a variance reduction technique in order to obtain an efficient estimate of performance measure. The proposed approach is tested using three real cases of the multi-echelon repairable item inventory systems (MERIIS). The results show that the proposed method is efficient in determining an optimal choice of spares and repair channels in these systems.     

Applying simulated annealing for designing cellular manufacturing systems using MDmTSP

The design of cellular manufacturing systems involves many structural and operational issues. One of the important design steps is the formation of part families and machine cells (cell formation). Despite a large number of papers on cell formation published worldwide, only a handful incorporates operation sequence in layout design (intra-cell move calculations). We propose a solution to solve the part-family and machine-cell formation problem considering the within-cell layout problem, simultaneously. In this paper, the cellular manufacturing system is formulated as a multiple departures single destination multiple travelling salesman problem (MDmTSP) and a solution methodology based on simulated annealing is proposed to solve the formulated model. Numerical examples show that the proposed method is efficient and effective in finding optimal solutions. The results also indicate that the proposed approach performs well compared to some well-known cell formation methods.     

Simulation optimization using simulated annealing

The purpose of this study is to investigate the feasibility of using a simulated annealing algorithm in conjunction with a simulation model to find the optimal parameter levels at which to operate a system. In particular, we discuss an effort to use simulated annealing to find a combination of input parameter values for a model which optimizes a nonconvex, nonconcave objective function of the input parameters. In the absence on an optimal annealing schedule, we demonstrate that multiple runs of the simulated annealing algorithm can result in an optimal or near-optimal solution to the problem.     

Mapping computer-vision-related tasks onto reconfigurableparallel-processing systems

A tutorial overview of how selected computer-vision-related algorithms can be mapped onto reconfigurable parallel-processing systems is presented. The reconfigurable parallel-processing system assumed for the discussions is a multiprocessor system capable of mixed-mode parallelism; that is, it can operate in either the SIMD or MIMD modes of parallelism and can dynamically switch between modes at instruction-level granularity with generally negligible overhead. In addition, it can be partitioned into independent or communicating submachines, each having the same characteristics as the original machine. Furthermore, this reconfigurable system model uses a flexible multistage cube interconnection network, which allows the connection patterns among the processors to be varied. It is demonstrated how reconfigurability can be used by reviewing and examining five computer-vision-related algorithms, each one emphasizing a different aspect of reconfigurability     

Fuzzy model tuning using simulated annealing

This paper presents the use of simulated annealing metaheuristic for tuning Mamdani type fuzzy models. Structure of the Mamdani fuzzy model is learned from input–output data pairs using Wang and Mendel’s method and fuzzy c-means clustering algorithm. Then, parameters of the fuzzy system are tuned through simulated annealing. In this paper, we perform experiments to examine effects of (a) initial solution generated by Wang and Mendel’s method and fuzzy c-means clustering method, (b) membership function update procedure, (c) probability parameter for the calculation of the initial temperature, (d) temperature update coefficient used for cooling schedule, and (e) randomness level in the disturbance mechanism used in simulated annealing algorithm on the tuning of Mamdani type fuzzy models. Experiments are performed with Mackey–Glass chaotic time series. The results indicate that Wang and Mendel’s method provides better starting configuration for simulated annealing compared to fuzzy c-means clustering method, and for the membership function update parameter, MFChangeRate ∈  (0, 1], and the probability parameter for the calculation of the initial temperature, P₀ ∈  (0, 1), values close to zero produced better results.     

Flow-shop sequencing using hybrid simulated annealing

Simulated annealing (SA) heuristics have been successfully applied on a variety of complex optimization problems. This paper presents a new hybrid SA approach for the permutation flow-shop scheduling (FSS) problem. FSS is known to be NP-hard, and thus the right way to proceed is through the use of heuristics techniques. The proposed approach combines the characteristics of a canonical SA procedure together with features borrowed from the field of genetic algorithms (GAs), such as the use of a population of individuals and the use of a novel, non-standard recombination operator for generating solutions. The approach is easily implemented and performs near-optimal schedules in a rather short computation time. Experiments over multiple benchmarks test problems show that the developed approach has higher performance than that of other FSS meta-heuristic approaches, generating schedules of shorter makespans faster. The experiments include comparisons between the proposed hybrid model, a genetic algorithm, and two other standard simulated annealing approaches. The final solutions obtained by the method are within less than 1% in average from the optimal solutions obtained so far.     

Parallel simulated annealing using speculative computation

A parallel simulated annealing algorithm that is problem-independent, maintains the serial decision sequence, and obtains speedup which can exceed log₂P on P processors is discussed. The algorithm achieves parallelism by using the concurrency technique of speculative computation. Implementation of the parallel algorithm on a hypercube multiprocessor and application to a task assignment problem are described. The simulated annealing solutions are shown to be, on average, 28% better than the solutions produced by a random task assignment algorithm and 2% better than the solutions produced by a heuristic     

Two-dimensional equilibrium constraint layout using simulated annealing

This paper studies the layout optimization problem with equilibrium constraint. It is a two-dimensional packing problem with the industrial background of simplified satellite module layout design, and is known as NP-hard problem. By incorporating the heuristic neighborhood search mechanism and the adaptive gradient method into the simulated annealing procedure, a heuristic simulated annealing algorithm is put forward for this problem. The special neighborhood search mechanism can avoid the disadvantage of blind search in the simulated annealing algorithm, and the adaptive gradient method is used to execute local search and speed up finding the global optimal solution. Numerical examples are illustrated to verify the effectiveness of the proposed algorithm.     

Web newspaper layout optimization using simulated annealing

The Web newspaper pagination problem consists of optimizing the layout of a set of articles extracted from several Web newspapers and sending it to the user as the result of a previous query. This layout should be organized in columns, as in real newspapers, and should be adapted to the client Web browser configuration in real time. This paper presents an approach to the problem based on simulated annealing (SA) that solves the problem on-line, adapts itself to the client's computer configuration, and supports articles with different widths.     

Combining multiple clusterings using fast simulated annealing

This paper presents a fast simulated annealing framework for combining multiple clusterings based on agreement measures between partitions, which are originally used to evaluate a clustering algorithm. Although we can follow a greedy strategy to optimize these measures as the objective functions of clustering ensemble, it may suffer from local convergence and simultaneously incur too large computational cost. To avoid local optima, we consider a simulated annealing optimization scheme that operates through single label changes. Moreover, for the measures between partitions based on the relationship (joined or separated) of pairs of objects, we can update them incrementally for each label change, which ensures that our optimization scheme is computationally feasible. The experimental evaluations demonstrate that the proposed framework can achieve promising results.     

Message-routing systems for transputer-based multicomputers

The Tiny, CSN, Multiple Rings, and Ordered Dimensions, and interval labeling routing systems for transputer networks are reviewed. The systems are compared with respect to several criteria, such as adaptivity, deadlock freedom, generality, livelock freedom, and network latency     

Model-free optimization of fuzzy rule-based systems using evolutionstrategies

In this paper the applicability of evolution strategies, a special kind of evolutionary algorithms, to the problem of parameter optimization in the development of fuzzy rule-based systems is demonstrated. For this aim we introduce a shell which supports the design of any kind of rule based systems employing fuzzy logic for the formalization of imprecise reasoning processes and which optimizes all numerical parameters. This method works model-free, we do not need to know implicit features of the optimizing system.     

Mental map preserving graph drawing using simulated annealing

Visualizing graphs has been studied extensively in the community of graph drawing and information visualization over the years. In some applications, the user is required to interact with a graph by making slight changes to the underlying graph structure. To visualize graphs in such an interactive environment, it is desirable that the differences between the displays of the original and the modified graphs be kept minimal, allowing the user to comprehend the changes in the graph structure faster. As the mental map concept refers to the presentation of a person’s mind while exploring visual information, the better the mental map is preserved, the easier the structure change of a graph is understood. It is somewhat surprising that preserving the user’s mental map has largely been ignored in the graph drawing community in the past. We propose an effective mental-map-preserving graph drawing algorithm for straight-line drawings of general undirected graphs based on the simulated-annealing technique. Our experimental results and questionnaire analysis suggest this new approach to be promising.     

Solving power system optimization problems using simulated annealing

Based on the simulated annealing technique and the constrained form of power system optimization problems, this paper develops a simulated-annealing-based optimization algorithm for power-system optimization problems. The algorithm is general, and it possesses the ability to determine the global optimum solution. The developed algorithm is demonstrated by its application to the problem of the economic dispatch of electric power.     

Optimization of rule-based systems using state space graphs

Embedded rule-based expert systems must satisfy stringent timing constraints when applied to real-time environments. The paper describes a novel approach to reduce the response time of rule-based expert systems. The optimization method is based on a construction of the reduced cycle-free finite state space graph. In contrast with traditional state space graph derivation, the optimization algorithm starts from the final states (fixed points) and gradually expands the state space graph until all of the states with a reachable fixed point are found. The new and optimized system is then synthesized from the constructed state space graph. The authors present several algorithms implementing the optimization method. They vary in complexity as well as in the usage of concurrency and state-equivalency-both targeted toward minimizing the size of the optimized state space graph. Though depending on the algorithm used, optimized rule-based systems: (1) in general have better response time in that they require fewer rule firings to reach the fixed point; (2) are stable, i.e., have no cycles that would result in the instability of execution; and (3) have no redundant rules. They also address the issue of deterministic execution and propose optimization algorithms that generate the rule-bases with single corresponding fixed points for every initial state. The synthesis method also determines the tight response time bound of the new system and can identify unstable states in the original rule-base     

Improving inductive logic programming by using simulated annealing

In Inductive Logic Programming (ILP), algorithms that are purely of the bottom-up or top-down type encounter several problems in practice. Since a majority of them are greedy ones, these algorithms stop when finding clauses in local optima, according to the “quality” measure used for evaluating the results. Moreover, when learning clauses one by one, the induced clauses become less and less interesting as the algorithm is progressing to cover few remaining examples. In this paper, we propose a simulated annealing framework to overcome these problems. Using a refinement operator, we define neighborhood relations on clauses and on hypotheses (i.e. sets of clauses). With these relations and appropriate quality measures, we show how to induce clauses (in a coverage approach), or to induce hypotheses directly by using simulated annealing algorithms. We discuss the necessary conditions on the refinement operators and the evaluation measures to increase the effectiveness of the algorithm. Implementations (included a parallelized version of the algorithm) are described and experimentation results in terms of convergence of the method and in terms of accuracy are presented.     

Mapping of artificial neural networks onto message passing systems

Various Artificial Neural Networks (ANNs) have been proposed in recent years to mimic the human brain in solving problems involving human-like intelligence. Efficient mapping of ANNs comprising of large number of neurons onto various distributed MIMD architectures is discussed in this paper. The massive interconnection among neurons demands a communication efficient architecture. Issues related to the suitability of MIMD architectures for simulating neural networks are discussed. Performance analysis of ring, torus, binary tree, hypercube, and extended hypercube for simulating artificial neural networks is presented. Our studies reveal that the performance of the extended hypercube is better than those of ring, torus, binary tree, and hypercube topologies.     

New bounds for binary covering arrays using simulated annealing

Covering arrays (CAs) are combinatorial structures specified as a matrix of N rows and k columns over an alphabet on v symbols such that for each set of t columns (called the strength of the array) every t-tuple of symbols is covered. Recently they have been used to represent interaction test suites for software testing given that they provide economical sized test cases while still preserving important fault detection capabilities.This paper introduces an improved implementation of a simulated annealing algorithm, called ISA, for constructing CAs of strengths three through six over a binary alphabet (i.e., binary CAs). Extensive experimentation is carried out, using 127 well-known benchmark instances, for assessing its performance with respect to an existing simulated annealing implementation, a greedy method, and five state-of-the-art algorithms. The results show that our algorithm attains 104 new bounds and equals the best-known solutions for the other 23 instances consuming reasonable computational time. Furthermore, the implications of using these results as ingredients to recursive constructions are also analyzed.     

Design of bi-criteria kanban system using simulated annealing technique

In the kanban system, the main decision parameters are the number of kanbans and lot size. In this paper, an attempt has been made to set the number of kanbans at each station and the lot size required to achieve the best performance using simulated annealing technique. A simulation model with a single-card system has been designed and used for analysis. A bi-criterion objective function comprising of mean throughput rate and aggregate average kanban queue has been used for evaluation. Different perturbation schemes have been experimented and compared.     

基于模拟退火的多标记数据特征选择

多标记数据有很多的冗余特征和数据,为了解决多标记数据中冗余和无关特征,提高多标记学习算法的泛化能力。提出一个基于模拟退火的卷积式特征选择方法——SAML(simulated annealing based feature selection for multi-label data),已有的算法只是使用了遗传算法来进行优化,新算法采用模拟退火来寻找最优子集,其效果在已有的工作中表现出比前者遗传算法更好的效果。在用于公开评测的Yahoo网页分类数据集上的实验结果表明,SAML算法的性能优于新近提出的一些流行的多标记特征选择方法。