We formulate the problem of permuting a matrix to block angular form as the combinatorial minimization of an objective function. We motivate the use of simulated annealing (SA) as an optimization tool. We then introduce a heuristic temperature dependent penalty function in the simulated annealing cost function, to be used instead of the real objective function being minimized. Finally we show that this temperature dependent penalty function version of simulated annealing consistently outperforms the standard (...) simulated annealing approach, producing, with smaller running times, better solutions. We believe that the use of a temperature dependent penalty function may be useful in developing SA algorithms for other combinatorial problems. -/- . (shrink)

This paper presents a method to compute a posteriori probability intervals when the initial conditional information is also given with probability intervals. The right way to make an exact computation is with the associated convex set of probabilities. Probability trees are used to represent these initial conditional convex sets because they greatly save the space required. This paper proposes a simulated annealing algorithm, which uses probability trees to represent the convex sets in order to compute the a posteriori (...) intervals. (shrink)

This paper introduces the basic principle and application process of simulated annealing algorithm and improves the simulated annealing algorithm so that it can converge faster to get the new parameters of cultural and creative product design and make it more in line with the reality of engineering optimization. In the cultural creative industry, it is necessary to use the creatorʼs creativity and technology to derive and develop the original cultural resources with the help of various materialization (...) means, to refine the abstract and profound contents of cultural resources to make them more visualized, and to produce products with both spiritual and economic values through the multiple development and utilization of their intellectual property contents. By studying the feasibility analysis of the cultural and creative design, the design positioning of the cultural and creative products is determined. In this article, we use the simulated annealing method to simulate and analyse the condition values in the design process of cultural creative products. As the Internet era progresses, people have more diversified requirements for cultural and creative products, and they need to have innovative ideas to follow the trend, so the design of cultural and creative products can spread culture through different design expressions and media. As one of the important pillar industries for future development, cultural and creative products are characterized by a wide range of styles and practicality, which meet the aesthetic needs and fashion trends of modern people. (shrink)

The travelling salesman problem (TSP) belongs to the class of NP-hard problems, in which an optimal solution to the problem cannot be obtained within a reasonable computational time for large-sized problems. To address TSP, we propose a hybrid algorithm, called GA-TCTIA-LBSA, in which a genetic algorithm (GA), tour construction and tour improvement algorithms (TCTIAs) and a list-based simulated annealing (LBSA) algorithm are used. The TCTIAs are introduced to generate a first population, and after that, a search is continued (...) with the GA. The problem of premature convergence of the GA to local optimum is tackled by a method called social disaster technique. Afterwards, the LBSA is applied to generate a new population based on one of two proposed operators called packing and judgement day. The proposed algorithm is implemented in the MATLAB environment, and its two variants, called GA-TCTIA-LBSA packing and GA-TCTIA-LBSA judgement day, are tested on symmetric and asymmetric instances from TSPLIB. The overall results demonstrate that the proposed GA-TCTIA-LBSAs offer promising results, particularly for small-sized instances. (shrink)

The Genetic Algorithm (GA) and Simulated Annealing (SA), two techniques for global optimization, were applied to a reduced (simplified) form of the phase problem (RPP) in computational crystallography. Results were compared with those of "enhanced pair flipping" (EPF), a more elaborate problem-specific algorithm incorporating local and global searches. Not surprisingly, EPF did better than the GA or SA approaches, but the existence of GA and SA techniques more advanced than those used in this study suggest that these techniques (...) still hold promise for phase problem applications. The RPP is, furthermore, an excellent test problem for such global optimization methods. (shrink)

Of the many proposals for inferring genetic regulatory structure from microarray measurements of mRNA transcript hybridization, several aim to estimate regulatory structure from the associations of gene expression levels measured in repeated samples. The repeated samples may be from a single experimental condition, or from several distinct experimental conditions; they may be “equilibrium” measurements or time series; the associations may be estimated by correlation coefficients or by conditional frequencies (for discretized measurements) or by some other statistic. This paper describes two (...) elementary statistical difficulties for all such procedures, no matter whether based on Bayesian updating, conditional independence testing, or other machine learning procedures such as simulated annealing or neural net pruning. One difficulty obtains if large numbers of cells are aggregated in a measurement of expression levels from a common population of cells; the other obtains if small numbers of cells are aggregated or if samples are separately aggregated over different populations of cells. (shrink)

Motivation: One approach to inferring genetic regulatory structure from microarray measurements of mRNA transcript hybridization is to estimate the associations of gene expression levels measured in repeated samples. The associations may be estimated by correlation coefficients or by conditional frequencies or by some other statistic. Although these procedures have been successfully applied to other areas, their validity when applied to microarray measurements has yet to be tested. Results: This paper describes an elementary statistical difficulty for all such procedures, no matter (...) whether based on Bayesian updating, conditional independence testing, or other machine learning procedures such as simulated annealing or neural net pruning. The difficulty obtains if a number of cells from a common population are aggregated in a measurement of expression levels. Although there are special cases where the conditional associations are preserved under aggregation, in general inference of genetic regulatory structure based on conditional association is unwarranted. Contact: tchu@ andrew.cmu.edu. (shrink)

Of the many proposals for inferring genetic regulatory structure from microarray measurements of mRNA transcript hybridization, several aim to estimate regulatory structure from the associations of gene expression levels measured in repeated samples. The repeated samples may be from a single experimental condition, or from several distinct experimental conditions; they may be “equilibrium” measurements or time series; the associations may be estimated by correlation coefficients or by conditional frequencies (for discretized measurements) or by some other statistic. This paper describes two (...) elementary statistical difficulties for all such procedures, no matter whether based on Bayesian updating, conditional independence testing, or other machine learning procedures such as simulated annealing or neural net pruning. One difficulty obtains if large numbers of cells are aggregated in a measurement of expression levels from a common population of cells; the other obtains if small numbers of cells are aggregated or if samples are separately aggregated over different populations of cells. (shrink)

The N-Queens problem plays an important role in academic research and practical application. Heuristic algorithm is often used to solve variant 2 of the N-Queens problem. In the process of solving, evaluation of the candidate solution, namely, fitness function, often occupies the vast majority of running time and becomes the key to improve speed. In this paper, three parallel schemes based on CPU and four parallel schemes based on GPU are proposed, and a serial scheme is implemented at the baseline. (...) The experimental results show that, for a large-scale N-Queens problem, the coarse-grained GPU scheme achieved a maximum 307-fold speedup over a single-threaded CPU counterpart in evaluating a candidate solution. When the coarse-grained GPU scheme is applied to simulated annealing in solving N-Queens problem variant 2 with a problem size no more than 3000, the speedup is up to 9.3. (shrink)

This paper discusses DNA-based stochastic optimizations under the constraint that the search starts from a given point in a search space. Generally speaking, a stochastic optimization method explores a search space and finds out the optimum or a sub-optimum after many cycles of trials and errors. This search process could be implemented efficiently by ``molecular computing'', which processes DNA molecules by the techniques of molecular biology to generate and evaluate a vast number of solution candidates at a time. We assume (...) the exploration starting from a single point, and propose a method to embody DNA-based optimization under this constraint, because this method has a promising application in the research field of protein engineering. In this application, a string of nucleotide bases encodes a protein possessing a specific activity, which could be given as a value of an objective function. Thus, a problem of obtaining a protein with the optimum or a sub-optimum about the desired activity corresponds to a combinatorial problem of obtaining a base sequence giving the optimum or a sub-optimum in the sequence space. Biologists usually modify a base sequence corresponding to a naturally occurring protein into another sequence giving a desired activity. In other words, they explore the space in the proximity of a natural protein as a start point. We first examined if the optimization methods that involve a single start point, such as simulated annealing, Gibbs sampler, and MH algorithms, can be implemented by DNA-based operations. Then, we proposed an application of genetic algorithm, and examined the performance of this application on a model fitness landscape by computer experiments. These experiments gave helpful guidelines in the embodiments of DNA-based stochastic optimization, including a better design of crossover operator. (shrink)

Most current statistical natural language processing models use only local features so as to permit dynamic programming in inference, but this makes them unable to fully account for the long distance structure that is prevalent in language use. We show how to solve this dilemma with Gibbs sam- pling, a simple Monte Carlo method used to perform approximate inference in factored probabilistic models. By using simulated annealing in place of Viterbi decoding in sequence models such as HMMs, CMMs, (...) and CRFs, it is possible to incorporate non-local structure while preserving tractable inference. We use this technique to augment an existing CRF-based information extraction system with long-distance dependency models, enforcing label consistency and extraction template consistency constraints. This technique results in an error reduction of up to 9% over state-of-the-art systems on two established information extraction tasks. (shrink)

It is suggested that Walker's consolidation-based enhancement of memory during REM sleep corresponds to the simulated annealing technique used for function optimization, and that robotic and AI design could benefit from inclusion of a deliberate REM-like memory optimization phase.

This work proposes a hybrid heuristic algorithm to solve the bus rapid transit intelligent scheduling problem, which is a combination of the genetic algorithm, simulated annealing algorithm, and fitness scaling method. The simulated annealing algorithm can increase the local search ability of the genetic algorithm, so as to accelerate its convergence speed. Fitness scaling can reduce the differences between individuals in the early stage of the algorithm, to prevent the genetic algorithm from falling into a local (...) optimum through increasing the diversity of the population. It can also increase the selection probability of outstanding individuals, and speed up the convergence at the late stage of the algorithm, by increasing the differences between individuals. Using real operational data of BRT Line 1 in a city of Zhejiang province, the new scheduling scheme can be obtained through algorithm simulation. The passengers’ total waiting time in a single way will be reduced by 40 h on average under the same operating cost compared with the original schedule scheme in a day. (shrink)

Open Shop Scheduling Problem is one of the most important scheduling problems in the field of engineering and industry. This kind of problem includes m machines and n jobs, each job contains a certain number of operations, and each operation has a predetermined processing time on its corresponding machine. The order of processing of these operations affects the completion times of all jobs. Therefore, the purpose of OSSP is to achieve a proper order of processing of jobs using specified machines, (...) so that the completion time of all jobs is minimized. In this paper, the strengths and limitations of three methods are evaluated by comparing the results of solving the OSSP in large-scale and small-scale benchmarks. In this case, the minimized completion time and total tardiness are considered the objective functions of the adapted methods. To solve small-scale problems, we adapt a mathematical model called Multiobjective Mixed Linear Programming. To solve large-scale problems, two metaheuristic algorithms including Multiobjective Parallel Genetic Algorithm and Multiobjective Parallel Simulated Annealing are adapted. In experimental results, we randomly generated small-scale problems to compare MOMILP with the Genetic Algorithm and Simulate Annealing. To compare MOPSA and MOPGA with the state of the art and show their strengths and limitations, we use a standard large-scale benchmark. The simulation results of the proposed algorithms show that although the MOPSA algorithm is faster, the MOPGA algorithm is more efficient in achieving optimal solutions for large-scale problems compared with other methods. (shrink)

In order to become aware of inconsistencies, one must first construe of the world in a way that reflects its consistencies. This paper begins with a tentative model for how a set of discrete memories transforms into an interconnected worldview wherein relationships between memories are forged by way of abstractions. Inconsistencies prompt the invention of new abstractions. In regions of the conceptual network where inconsistencies abound, a cognitive analog of simulated annealing is in order; there is a willingness (...) to question previous assumptions—to ‘loosen’ conceptual relationships—so as to let new concepts thoroughly percolate through the worldview and exert the needed revolutionary effect. In so doing there is a risk of assimilating dangerous concepts. Repression arrests the process by which dangerous thoughts infiltrate the conceptual network, and deception blocks thoughts that have already been assimilated. These forms of self-initiated worldview inconsistency may evoke feelings of fragmentation at the level of the individual or the society. (shrink)

The input data to grammar learning algorithms often consist of overt forms that do not contain full structural descriptions. This lack of information may contribute to the failure of learning. Past work on Optimality Theory introduced Robust Interpretive Parsing (RIP) as a partial solution to this problem. We generalize RIP and suggest replacing the winner candidate with a weighted mean violation of the potential winner candidates. A Boltzmann distribution is introduced on the winner set, and the distribution’s parameter $T$ is (...) gradually decreased. Finally, we show that GRIP, the Generalized Robust Interpretive Parsing Algorithm significantly improves the learning success rate in a model with standard constraints for metrical stress assignment. (shrink)

This paper is about representations for Artificial Intelligence systems. All of the results described in it involve engineering the representation to make AI systems more effective. The main AI techniques studied here are varieties of search: path-finding in graphs, and probablilistic searching via simulated annealing and genetic algorithms. The main results are empirical findings about the granularity of representation in implementations of genetic algorithms. We conclude by proposing a new algorithm, called “Long-Term Evolution,” which is a genetic algorithm (...) running on an evolving problem description. We see this as modelling the evolution of a species from simpler (more coarsely described— fewer genes) types of organisms to more complex ones. The results, which are reported here of our experiments with the algorithm make it seem a promising optimisation technique. (shrink)

My life as a quantum physicist / M. Nakahara -- A review on operator quantum error correction - Dedicated to Professor Mikio Nakahara on the occasion of his 60th birthday / C.-K. Li, Y.-T. Poon and N.-S. Sze -- Implementing measurement operators in linear optical and solid-state qubits / Y. Ota, S. Ashhab and F. Nori -- Fast and accurate simulation of quantum computing by multi-precision MPS: Recent development / A. Saitoh -- Entanglement properties of a quantum lattice-gas model on (...) square and triangular ladders / S. Tanaka, R. Tamura and H. Katsura -- On signal amplification from weak-value amplification / Y. Shikano -- Topological protection of quantum information / K. Fujii -- Quantum annealing with antiferromagnetic fluctuations for mean-field models / Y. Seki and H. Nishimori -- A method to change phase transition nature - Toward annealing methods / R. Tamura and S. Tanaka -- Computational analysis of the first stage of the photosynthetic system, the light-dependent reaction, by quantum chemical simulation method / M. Tada-Umezaki -- Two-qubit gate operation on selected nearest neighboring qubits in a neutral atom quantum computer / E. Hosseini Lapasar... [et al.] -- A simple operator quantum error correction scheme avoiding fully correlated errors / C. Bagnasco, Y. Kondo and M. Nakahara -- Black hole predictability, classical and quantum / A. Ishibashi -- Classical field simulation of finite-temperature Bose gases / T. Sato -- Atomic quantum simulations of lattice gauge theory: Effect of gauge symmetry breaking / K. Kasamatsu, I. Ichinose and T. Matsui -- Recursive construction of noiseless subsystem for qudits / U. Gungordu... [et al.] -- Composite quantum gates for precise quantum control / M. Bando... [et al.] -- New formulation of statistical mechanics using thermal pure quantum states / S. Sugiura and A. Shimizu -- Thermodynamics in unitary time evolution / T. N. Ikeda -- Second law of thermodynamics with QC-mutual information / T. Sagawa. (shrink)

Many philosophers and psychologists argue that out everyday ability to predict and explain the actions and mental states of others is grounded in out possession of a primitive 'folk' psychological theory. Recently however, this theory has come under challenge from the simulation alternative. This alternative view says that human beings are able to predict and explain each other's actions by using the resources of their own minds to simulate the psychological aetiology of the actions of the others. This book and (...) the companion volume Folk Psychology: The Theory of Mind Debate together offer a richly woven fabric of philosophical and psychological theory, which promises to yield real insights into the nature of our mental lives. (shrink)

The structure of Au layers deposited by sputtering on oxidized p-type Si substrates is investigated by a combination of scanning electron microscopy and scanning probe microscopy. The effect of the temperature on the grain structure of the layers has been determined, revealing that an annealing temperature of 300° C results in a larger grain size and smoother surfaces but generates some cracks in the film surface. At an annealing temperature of 500° C, further grain growth is observed, but (...) a high density of cracks and voids also results while there is little enhancement regarding the smoothness of the grain surfaces. (shrink)

This paper discusses critically what simulation models of the evolution of cooperation can possibly prove by examining Axelrod’s “Evolution of Cooperation” (1984) and the modeling tradition it has inspired. Hardly any of the many simulation models in this tradition have been applicable empirically. Axelrod’s role model suggested a research design that seemingly allowed to draw general conclusions from simulation models even if the mechanisms that drive the simulation could not be identified empirically. But this research design was fundamentally flawed. At (...) best such simulations can claim to prove logical possibilities, i.e. they prove that certain phenomena are possible as the consequence of the modeling assumptions built into the simulation, but not that they are possible or can be expected to occur in reality. I suggest several requirements under which proofs of logical possibilities can nevertheless be considered useful. Sadly, most Axelrod-style simulations do not meet these requirements. It would be better not to use this kind of simulations at all. (shrink)

People are minded creatures; we have thoughts, feelings and emotions. More intriguingly, we grasp our own mental states, and conduct the business of ascribing them to ourselves and others without instruction in formal psychology. How do we do this? And what are the dimensions of our grasp of the mental realm? In this book, Alvin I. Goldman explores these questions with the tools of philosophy, developmental psychology, social psychology and cognitive neuroscience. He refines an approach called simulation theory, which starts (...) from the familiar idea that we understand others by putting ourselves in their mental shoes. Can this intuitive idea be rendered precise in a philosophically respectable manner, without allowing simulation to collapse into theorizing? Given a suitable definition, do empirical results support the notion that minds literally create surrogates of other peoples mental states in the process of mindreading? Goldman amasses a surprising array of evidence from psychology and neuroscience that supports this hypothesis. (shrink)

Baudrillard's bewildering thesis, a bold extrapolation on Ferdinand de Saussure's general theory of general linguistics, is in fact a clinical vision of contemporary consumer societies where signs don't refer anymore to anything except themselves. They all are generated by the matrix. Simulations never existed as a book before it was "translated" into English. Actually it came from two different bookCovers written at different times by Jean Baudrillard. The first part of Simulations, and most provocative because it made a fiction of (...) theory, was "The Procession of Simulacra." It had first been published in Simulacre et Simulations. The second part, written much earlier and in a more academic mode, came from L'Echange Symbolique et la Mort. It was a half-earnest, half-parodical attempt to "historicize" his own conceit by providing it with some kind of genealogy of the three orders of appearance: the Counterfeit attached to the classical period; Production for the industrial era; and Simulation, controlled by the code. It was Baudrillard's version of Foucault's Order of Things and his ironical commentary of the history of truth. The book opens on a quote from Ecclesiastes asserting flatly that "the simulacrum is true." It was certainly true in Baudrillard's book, but otherwise apocryphal.One of the most influential essays of the 20th century, Simulations was put together in 1983 in order to be published as the first little black book of Semiotext's new Foreign Agents Series. Baudrillard's bewildering thesis, a bold extrapolation on Ferdinand de Saussure's general theory of general linguistics, was in fact a clinical vision of contemporary consumer societies where signs don't refer anymore to anything except themselves. They all are generated by the matrix.In effect Baudrillard's essay was upholding the only reality there was in a world that keeps hiding the fact that it has none. Simulacrum is its own pure simulacrum and the simulacrum is true. In his celebrated analysis of Disneyland, Baudrillard demonstrates that its childish imaginary is neither true nor false, it is there to make us believe that the rest of America is real, when in fact America is a Disneyland. It is of the order of the hyper-real and of simulation. Few people at the time realized that Baudrillard's simulacrum itself wasn't a thing, but a "deterrence machine," just like Disneyland, meant to reveal the fact that the real is no longer real and illusion no longer possible. But the more impossible the illusion of reality becomes, the more impossible it is to separate true from false and the real from its artificial resurrection, the more panic-stricken the production of the real is. (shrink)

This unique volume introduces and discusses the methods of validating computer simulations in scientific research. The core concepts, strategies, and techniques of validation are explained by an international team of pre-eminent authorities, drawing on expertise from various fields ranging from engineering and the physical sciences to the social sciences and history. The work also offers new and original philosophical perspectives on the validation of simulations. Topics and features: introduces the fundamental concepts and principles related to the validation of computer simulations, (...) and examines philosophical frameworks for thinking about validation; provides an overview of the various strategies and techniques available for validating simulations, as well as the preparatory steps that have to be taken prior to validation; describes commonly used reference points and mathematical frameworks applicable to simulation validation; reviews the legal prescriptions, and the administrative and procedural activities related to simulation validation; presents examples of best practice that demonstrate how methods of validation are applied in various disciplines and with different types of simulation models; covers important practical challenges faced by simulation scientists when applying validation methods and techniques; offers a selection of general philosophical reflections that explore the significance of validation from a broader perspective. This truly interdisciplinary handbook will appeal to a broad audience, from professional scientists spanning all natural and social sciences, to young scholars new to research with computer simulations. Philosophers of science, and methodologists seeking to increase their understanding of simulation validation, will also find much to benefit from in the text. (shrink)

In this paper, we pursue three general aims: (I) We will define a notion of fundamental opacity and ask whether it can be found in High Energy Physics (HEP), given the involvement of machine learning (ML) and computer simulations (CS) therein. (II) We identify two kinds of non-fundamental, contingent opacity associated with CS and ML in HEP respectively, and ask whether, and if so how, they may be overcome. (III) We address the question of whether any kind of opacity, contingent (...) or fundamental, is unique to ML or CS, or whether they stand in continuity to kinds of opacity associated with other scientific research. (shrink)