This book constitutes the refereed proceedings of the Third International Symposium on Stochastic Algorithms: Foundations and Applications, SAGA 2005, held in Moscow, Russia in October 2005. The 14 revised full papers presented together with 5 invited papers were carefully reviewed and selected for inclusion in the book. The contributed papers included in this volume cover both theoretical as well as applied aspects of stochastic computations whith a special focus on new algorithmic ideas involving stochastic decisions and the (...) design and evaluation of stochastic algorithms within realistic scenarios. (shrink)

This article proposes a new problem which is called the Stochastic Travelling Advisor Problem in network optimization, and it is defined for an advisory group who wants to choose a subset of candidate workplaces comprising the most profitable route within the time limit of day working hours. A nonlinear binary mathematical model is formulated and a real application case study in the occupational health and safety field is presented. The problem has a stochastic nature in travelling and advising (...) times since the deterministic models are not appropriate for such real-life problems. The STAP is handled by proposing suitable probability distributions for the time parameters and simulating the problem under such conditions. Many application problems like this one are formulated as nonlinear binary programming models which are hard to be solved using exact algorithms especially in large dimensions. A novel binary version of the recently developed gaining-sharing knowledge-based optimization algorithm to solve binary optimization problems is given. GSK algorithm is based on the concept of how humans acquire and share knowledge during their life span. The binary version of GSK depends mainly on two stages that enable BGSK for exploring and exploitation of the search space efficiently and effectively to solve problems in binary space. The generated simulation runs of the example are solved using the BGSK, and the output histograms and the best-fitted distributions for the total profit and for the route length are obtained. (shrink)

This paper considers two kinds of stochastic reentrant job shop scheduling problems, i.e., the SRJSSP with the maximum tardiness criterion and the SRJSSP with the makespan criterion. Owing to the NP-complete complexity of the considered RJSSPs, an effective differential evolutionary algorithm combined with two uncertainty handling techniques, namely, DEA_UHT, is proposed to address these problems. Firstly, to reasonably control the computation cost, the optimal computing budget allocation technique is applied for allocating limited computation budgets to assure reliable evaluation (...) and identification for excellent solutions or individuals, and the hypothesis test technique is added to execute a statistical comparison to reduce some unnecessary repeated evaluation. Secondly, a reentrant-largest-order-value rule is designed to convert the DEA’s individual to the SRJSSP’s solution. Thirdly, a conventional active decoding scheme for the job shop scheduling problem is extended to decode the solution for obtaining the criterion value. Fourthly, an Insert-based exploitation strategy and an Interchange-based exploration strategy are devised to enhance DEA’s exploitation ability and exploration ability, respectively. Finally, the test results and comparisons manifest the effectiveness and robustness of the proposed DEA_UHT. (shrink)

This research proposes a modified metaheuristic optimization algorithm, named as improved stochastic fractal search, which is formed based on the integration of the quasiopposition-based learning and chaotic local search schemes into the original SFS algorithm for solving the optimal capacitor placement in radial distribution networks. The test problem involves the determination of the optimal number, location, and size of fixed and switched capacitors at different loading conditions so that the network total yearly cost is minimized with simultaneous (...) fulfillment of operating constraints. Also, the hourly on/off scheduling plans of switched shunt capacitors considering a modified cost objective function are obtained. The proposed ISFS algorithm has been tested on two IEEE 69-bus and 119-bus RDNs and a practical 152-bus RDN. For clarifying the effectiveness and validation of the ISFS, the simulated results have been compared with those of other previously utilized solution approaches in the literature as well as the original SFS. From result comparison, the proposed ISFS outperforms other previous approaches regarding solution quality and statistical performance for the compared cases, especially in the complex and large-scale networks. Notably, compared with the original SFS, the proposed ISFS shows a significantly better performance in all the tested cases. (shrink)

This paper applies a proposed modified stochastic fractal search algorithm (MSFS) for dealing with all constraints of optimal reactive power dispatch (ORPD) and finding optimal solutions for three different cases including power loss optimization, voltage deviation optimization, and L-index optimization. The proposed MSFS method is newly constructed in the paper by modifying three new solution update mechanisms on standard stochastic fractal search algorithm (SSFS). The first modification is to keep only one formula and abandon one formula (...) in the diffusion process while the second modification and the third modification are used in the first update and the second update. In two updates of SSFS, solutions with low quality are updated with high probability while other solutions with high quality do not get chances to be updated. This manner results in the fact that some promising solutions around the high quality solutions can be missed. In order to tackle this restriction, the second modification of MSFS is to newly update the worst solutions in the first update and the best solutions in the second update. In the third modification, all existing formulas of SSFS in the two updates are abandoned and the same new proposed technique is used for updating such solutions in two updates. Compared to SSFS, the three modifications can bring advantages to MSFS such as using smaller number of produced solutions per iteration, spending shorter execution time, finding better optimal solutions, and owning more stable search ability. Furthermore, the proposed method also sees its effectiveness and robustness over SSFS by testing on IEEE 30-bus system and IEEE 118-bus system with three different single objectives for each system. The proposed method can find less minimum, average, and maximum for all the cases in addition to faster search speed. Besides, the proposed method is also compared to other methods such as PSO-based method group, GA-based method group, DE-based method group, and other recent methods. Result comparisons also indicate that the proposed method can be more efficient than almost all these methods with respect to less minimum and smaller values of control parameters. As a result, evaluation of the performance of the proposed method is that it should be used for seeking solutions of ORPD problem. (shrink)

The evolution of boundedly rational rules for playing normal form games is studied within stationary environments of stochastically changing games. Rules are viewed as algorithms prescribing strategies for the different normal form games that arise. It is shown that many of the “folk results” of evolutionary game theory, typically obtained with a fixed game and fixed strategies, carry over to the present environments. The results are also related to some recent experiments on rules and games.

In this paper, I reflect on the puzzle that machine learning presents to social theory to develop an account of its distinct impact on social reality. I start by presenting how machine learning has presented a challenge to social theory as a research subject comprising both familiar and alien characteristics (1.). Taking this as an occasion for theoretical inquiry, I then propose a conceptual framework to investigate how algorithmic models of social phenomena relate to social reality and what their (...) class='Hi'>stochastic mode of operation entails in terms of their sociality (2.). Analyzed through a theoretical lens that relies on central tenets of sociological systems theory, I find that machine learning implies a distinct epistemic transformation, based on how algorithmic modeling techniques process meaning as represented in data embedded in vector space. Building on this characterization, I introduce my conceptualization of stochastic technology as distinct from mechanistic technologies that rely on causal fixation (3.). Based on this understanding, I suggest that real-world applications of machine learning are often characterized by a constitutive tension between the stochastic properties of their outputs and the ways in which they are put to use in practice. Focussing on the large language models LaMDA and ChatGPT, I examine the epistemological implications of LLMs to account for the confusion of correlation and causality as the root of this tension. Next, I illustrate my theoretical conception by way of discussing an essay on image models by German media artist Hito Steyerl (4.). Following a critical reflection on Steyerl's characterization of Stable Diffusion as a “white box ”, I finally propose to conceive ofmachine learning-based technologies as stochastic contingency machines that transform social indeterminacy into contingent observations of social phenomena (5.) In this perspective, machine learning constitutes an epistemic technology that operates on meaning as extractable from data by means of algorithmic data modeling techniques to produce stochastic accounts of social reality. (shrink)

A comprehensive introduction to optimization with a focus on practical algorithms for the design of engineering systems. This book offers a comprehensive introduction to optimization with a focus on practical algorithms. The book approaches optimization from an engineering perspective, where the objective is to design a system that optimizes a set of metrics subject to constraints. Readers will learn about computational approaches for a range of challenges, including searching high-dimensional spaces, handling problems where there are multiple competing objectives, and accommodating (...) uncertainty in the metrics. Figures, examples, and exercises convey the intuition behind the mathematical approaches. The text provides concrete implementations in the Julia programming language. Topics covered include derivatives and their generalization to multiple dimensions; local descent and first- and second-order methods that inform local descent; stochastic methods, which introduce randomness into the optimization process; linear constrained optimization, when both the objective function and the constraints are linear; surrogate models, probabilistic surrogate models, and using probabilistic surrogate models to guide optimization; optimization under uncertainty; uncertainty propagation; expression optimization; and multidisciplinary design optimization. Appendixes offer an introduction to the Julia language, test functions for evaluating algorithm performance, and mathematical concepts used in the derivation and analysis of the optimization methods discussed in the text. The book can be used by advanced undergraduates and graduate students in mathematics, statistics, computer science, any engineering field, (including electrical engineering and aerospace engineering), and operations research, and as a reference for professionals. (shrink)

With the rapid development of sensor technology for automated driving applications, the fusion, analysis, and application of multimodal data have become the main focus of different scenarios, especially in the development of mobile edge computing technology that provides more efficient algorithms for realizing the various application scenarios. In the present paper, the vehicle status and operation data were acquired by vehicle-borne and roadside units of electronic registration identification of motor vehicles. In addition, a motion model and an identification system for (...) the single-vehicle lane-change process were established by mobile edge computing and self-organizing feature mapping. Two scenarios were modeled and tested: lane change with no vehicles in the target lane and lane change with vehicles in the target lane. It was found that the proposed method successfully identified the stochastic parameters in the process of driving trajectory simulation, and the standard deviation between simulation and the measured results obeyed a normal distribution. The proposed methods can provide significant practical information for improving the data processing efficiency in automated driving applications, for solving single-vehicle lane-change applications, and for promoting the formation of a closed loop from sensing to service. (shrink)

Crew Pairing is one of the most important and difficult problems for airline companies. Nets to fuel costs, the crew costs constitute the largest cost of airlines, and the crew costs depend on the quality of the solution to the pairing problem. Conventional systems have been used to solve a daily model, which handles only regular flights with many simplifications, so a lot of corrections are needed to get a feasible solution and the quality of the solution is not so (...) high. A fully dated model, which handles regular flights and irregular flights simultaneously, is extremely hard and has not been solved directly hitherto. The number of irregular flights tend to increase in Europe and Japan, hence the resolution of the practical fully dated pairing system is desired. This paper presents a new approach which solves directly the fully dated crew pairing by Genetic Algorithms. GA is improved with stochastic processes to attack the fully dated model, and many heuristics are included in the decoding mecanism of the GA. For several hundred flights per day for fully dated 2 months scheduling period, the system found better or equivalent solutions to the human scheduler’s without any simplification from 5 to 20 times faster. (shrink)

Work in online learning traditionally considered induction-friendly (e.g. stochastic with a fixed distribution) and induction-hostile (adversarial) settings separately. While algorithms like Exp3 that have been developed for the adversarial setting are applicable to the stochastic setting as well, the guarantees that can be obtained are usually worse than those that are available for algorithms that are specifically designed for stochastic settings. Only recently, there is an increasing interest in algorithms that give (near-)optimal guarantees with respect to the (...) underlying setting, even in case its nature is unknown to the learner. In this paper, we review various online learning algorithms that are able to adapt to the hardness of the underlying problem setting. While our focus lies on the application of adaptive algorithms as meta-inductive methods that combine given base methods, concerning theoretical properties we are also interested in guarantees that go beyond a comparison to the best fixed base learner. (shrink)

HSimulator is a multithread simulator for mass-action biochemical reaction systems placed in a well-mixed environment. HSimulator provides optimized implementation of a set of widespread state-of-the-art stochastic, deterministic, and hybrid simulation strategies including the first publicly available implementation of the Hybrid Rejection-based Stochastic Simulation Algorithm. HRSSA, the fastest hybrid algorithm to date, allows for an efficient simulation of the models while ensuring the exact simulation of a subset of the reaction network modeling slow reactions. Benchmarks show that (...) HSimulator is often considerably faster than the other considered simulators. The software, running on Java v6.0 or higher, offers a simulation GUI for modeling and visually exploring biological processes and a Javadoc-documented Java library to support the development of custom applications. HSimulator is released under the COSBI Shared Source license agreement. (shrink)

This paper, using the author's decomposition method and recent generalizations, presents algorithms for an analytic solution of the stochastic Navier-Stokes system without linearization, perturbation, discretization, or restrictive assumptions on the nature of stochasticity. The pressure, forces, velocities, and initial/boundary conditions can be stochastic processes and are not limited to white noise. Solutions obtained are physically realistic because of the avoidance of assumptions made purely for mathematical tractability by usual methods. Certain extensions and further generalizations of the decomposition method (...) have provided the basis for the solution. (shrink)

In consideration of that the correlation between any two assets of the asset pool is always stochastic in the actual market and that collateralized debt obligation pricing models under nonhomogeneous assumptions have no semianalytic solutions, we designed a numerical algorithm based on randomized quasi-Monte Carlo simulation method for CDO pricing with stochastic correlations under nonhomogeneous assumptions and took Gaussian factor copula model as an example to conduct experiments. The simulation results of RQMC and Monte Carlo method were (...) compared from the perspective of variance changes. The results showed that this numerical algorithm was feasible, efficient, and stable for CDO pricing with stochastic correlation under nonhomogeneous assumptions. This numerical algorithm is expected to be extended to other factor Copula models for CDO pricing with stochastic correlations under nonhomogeneous assumptions. (shrink)

Although theoretical results for several algorithms in many application domains were presented during the last decades, not all algorithms can be analyzed fully theoretically. Experimentation is necessary. The analysis of algorithms should follow the same principles and standards of other empirical sciences. This article focuses on stochastic search algorithms, such as evolutionary algorithms or particle swarm optimization. Stochastic search algorithms tackle hard real-world optimization problems, e.g., problems from chemical engineering, airfoil optimization, or bioinformatics, where classical methods from mathematical (...) optimization fail. Nowadays statistical tools that are able to cope with problems like small sample sizes, non-normal distributions, noisy results, etc. are developed for the analysis of algorithms. Although there are adequate tools to discuss the statistical significance of experimental data, statistical significance is not scientifically meaningful per se. It is necessary to bridge the gap between the statistical significance of an experimental result and its scientific meaning. We will propose some ideas on how to accomplish this task based on Mayo's learning model. (shrink)

The probability ranking conclusion is an extension of the absolute form evaluation conclusion. Firstly, the random simulation evaluation model is introduced; then, the general idea of converting the traditional evaluation method to the random simulation evaluation model is analyzed; on this basis, based on the rule of “further ensuring the stability of the ranking chain on the basis of increasing the possibility of the ranking chain,” two methods of solving the probability ranking conclusion are given. Based on the rule of (...) “further guaranteeing the stability of the ranking chain on the basis of improving the likelihood of the ranking chain,” two methods are given to solve the likelihood conclusion. This paper argues that this absolute form of conclusion hinders the approximation of the theory to the essence of the actual problem and is an important reason for the problem of “non-consistency of multi-evaluation conclusions.” To address this problem, a stochastic simulation-based comprehensive evaluation solution algorithm based on the idea of “Monte Carlo simulation” is proposed, and the corresponding ranking method is investigated, which is characterized by generating evaluation conclusions with probability information, and thus has more advantages than the absolute conclusion form in terms of problem interpretability. The method is characterized by the generation of evaluation conclusions with probabilistic information and thus has more advantages than the absolute conclusion form in terms of problem interpretation. Because of the independence of the stochastic simulation solution method, it is applied to the “bottom-up” evaluation model as an example, and a novel autonomous evaluation method is constructed. Finally, the application of the stochastic simulation evaluation model is illustrated by an example and compared with the absolute form evaluation. The evaluation model is an extension of the traditional evaluation model, which can further broaden the practical application of comprehensive evaluation theory. (shrink)

In this paper, the covariance control algorithm for nonlinear stochastic systems using covariance feedback is studied. Covariance control of nonlinear systems scenario involves the theory of covariance control based on the idea of the covariance feedback. Therefore, the proposed covariance control algorithm is derived for our case, firstly by applying the covariance control method and linear approximation of nonlinear systems, and then it is achieved by adopting this method for a class of nonlinear stochastic systems by (...) using feedback linearization idea and a covariance feedback controller. The effectiveness of the proposed covariance feedback algorithm is studied using numerous simulations concerning different nonlinear case studies. (shrink)

In this paper, an in-depth study of interactive visual communication of network topology through non-line-of-sight congestion control algorithms is conducted to address the real-time routing problem of adapting to dynamic topologies, and a delay-constrained stochastic routing algorithm is proposed to enable packets to reach GB within the delay threshold in the absence of end-to-end delay information while improving network throughput and reducing network resource consumption. The algorithm requires each sending node to select an available relay set based (...) on the location of its neighbor nodes and channel state and computes transfer probabilities for each node in the relay set combining the remaining delay of the packet with the distance from the relay node to GB. Based on the obtained transfer probability and local channel state, the sending node passes the packet to the relay node. The convergence of the algorithm is proved and its performance is verified by simulation. The first part of the algorithm is based on the greedy algorithm to deploy and locate the network flying platform nodes with the goal of efficient coverage of the network flying platform nodes, considering the ground base station services. As the delay on each link varies due to the change of channel state, the source and relay nodes asynchronously update the data generation rate and the pairwise parameters based on the received local information and use the obtained optimal values to pass the packets to GB. (shrink)

Stochasticity and ambiguity are two aspects of uncertainty in economic problems. In the case of investments in risky assets, this uncertainty is manifested in the uncertainty of future returns. On the contrary, the complexity of the economic phenomenon itself and the ambiguity inherent in human thinking and judgment are characterized by indistinct boundaries. For the same problem, research from different perspectives can often provide us with more comprehensive and systematic information. Currently, the expected value of return or the variance representing (...) risk is still used as a rational investment criterion for both single-stage portfolios and multistage portfolios. However, in general, the greater the expected return of an investor, the greater the risk he should take. Different investors have different requirements for profitability, but regardless of their expected return, they always hope to find a set of portfolios that maximize the probability of achieving the expected rate of return. In this paper, after analyzing the development of portfolio investment theory research, we take fuzzy information processing as the entry point and systematically discuss the theory and methods of fuzzy modeling of portfolio investment decision-making from the perspective of fuzziness around the portfolio investment decision-making process. The results of the empirical analysis show that the existence of basis constraints affects investors’ investment strategies as well as their final returns, but there is a limit to the influence of basis constraints on portfolio performance, and investors can obtain optimal investment returns by selecting a reasonable number of securities to form a portfolio based on the characteristics of different securities. (shrink)

Residual useful lifetime prediction plays a key role of failure prediction and health management in equipment. Aiming at the problems of residual life prediction without comprehensively considering multistage and individual differences in equipment performance degradation at present, we explore a prediction model that can fit the multistage random performance degradation. Degradation modeling is based on the random Wiener process. Moreover, according to the degradation monitoring data of the same batch of equipment, we apply the expectation maximization algorithm to estimate (...) the prior distribution of the model. The real-time remaining life distribution of the equipment is acquired by merging prior information of real-time degradation data and historical degradation monitoring data. The accuracy of the proposed model is demonstrated by analyzing a practical case of metalized film capacitors, and the result shows that a better RUL estimation accuracy can be provided by our model compared with existing models. (shrink)

In this paper, a proposed modified stochastic fractal search algorithm is applied to find the most appropriate site and size of capacitor banks for distribution systems with 33, 69, and 85 buses. Two single-objective functions are considered to be reduction of power loss and reduction of total cost of energy loss and capacitor investment while satisfying limit of capacitors, limit of conductor, and power balance of the systems. MSFS was developed by performing three new mechanisms including new diffusion (...) mechanism and two new update mechanisms on the conventional stochastic fractal search algorithm. As a result, MSFS can reduce 0.002%, 0.003%, and 0.18% of the total power loss from SFS for the three study systems. As compared to other methods, MSFS can reduce power loss from 0.07% to 3.98% for the first system, from 3.7% to 7.3% for the second system, and from 0.92% to 6.98% for the third system. For the reduction of total cost, the improvement level of the proposed method over SFS and two other methods is more significant. It is 0.03%, 1.22%, and 5.76% for the second system and 2.31%, 0.87%, and 3.77% for the third system. It is emphasized that the proposed method can find the global optimal solutions for all study cases while SFS was still implementing search process nearby or far away from the solutions. Furthermore, MSFS can converge to the best solutions much faster than these compared methods. Consequently, it can be concluded that the proposed method is very effective for finding the best location and size of added capacitors in distribution power systems. (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)

Many stochastic search algorithms have recently been developed to make more remarkable progress than systematic search algorithms because stochastic algorithms sometimes solve large-scale constraint satisfaction problems in a practical time. However, such stochastic algorithms have the drawback of getting stuck in local optima which are not acceptable as final solutions. We analyze an iterative improvement algorithm from the viewpoint of constraint structures causing local optima. Using the graph-coloring problem with three colors, an archetype problem to evaluate (...) constraint satisfaction algorithms, we study the local graph structures around which so many conflicts thrash. We propose a key constraint structure, an LM pair, which may induce a local optimum, and clarify the mechanism of how conflicting colors for an LM pair obstruct the stepwise refinement of hill-climbing. Experimental results show that LM pairs are strongly correlated with the search efficiency of the stochastic search algorithm. (shrink)

We describe reversible adaptive trees, a class of stochastic algorithms modified from the formerly described adaptive trees. They evolve in time a finite subset of an ambient Euclidean space of any dimension, starting from a seed point and, accreting points to the evolving set, they grow branches towards a target set which can depend on time. In contrast with plain adaptive trees, which were formerly proven to have strong convergence properties to a static target, the points of reversible adaptive (...) trees are removed from the tree when they have not been used recently enough in a path from the root to an accreted point. This, together with a straightening process performed on the branches, permits the tree to follow some moving targets and still remain adapted to it. We then discuss in what way one can see such reversible trees as a model for a qualitative property of resilience, which leads us to discuss qualitative modeling. (shrink)

Much research has linked surprise to violation of expectations, but it has been less clear how one can be surprised when one has no particular expectation. This paper discusses a computational theory based on Algorithmic Information Theory, which can account for surprises in which one initially expects randomness but then notices a pattern in stimuli. The authors present evidence that a “randomness deficiency” heuristic leads to surprise in such cases.

Stochastic forecasts in complex environments can benefit from combining the estimates of large groups of forecasters (“judges”). But aggregating multiple opinions faces several challenges. First, human judges are notoriously incoherent when their forecasts involve logically complex events. Second, individual judges may have specialized knowledge, so different judges may produce forecasts for different events. Third, the credibility of individual judges might vary, and one would like to pay greater attention to more trustworthy forecasts. These considerations limit the value of simple (...) aggregation methods like linear averaging. In this paper, a new algorithm is proposed for combining probabilistic assessments from a large pool of judges. Two measures of a judge’s likely credibility are introduced and used in the algorithm to determine the judge’s weight in aggregation. The algorithm was tested on a data set of nearly half a million probability estimates of events related to the 2008 U.S. presidential election (∼ 16000 judges). (shrink)

In algorithmic randomness, when one wants to define a randomness notion with respect to some non-computable measure λ, a choice needs to be made. One approach is to allow randomness tests to access the measure λ as an oracle . The other approach is the opposite one, where the randomness tests are completely effective and do not have access to the information contained in λ . While the Hippocratic approach is in general much more restrictive, there are cases where the (...) two coincide. The first author showed in 2010 that in the particular case where the notion of randomness considered is Martin-Löf randomness and the measure λ is a Bernoulli measure, classical randomness and Hippocratic randomness coincide. In this paper, we prove that this result no longer holds for other notions of randomness, namely computable randomness and stochasticity. (shrink)

Learning in natural environments is often characterized by a degree of inconsistency from an input. These inconsistencies occur, for example, when learning from more than one source, or when the presence of environmental noise distorts incoming information; as a result, the task faced by the learner becomes ambiguous. In this study, we investigate how learners handle such situations. We focus on the setting where a learner receives and processes a sequence of utterances to master associations between objects and their labels, (...) where the source is inconsistent by design: It uses both “correct” and “incorrect” object‐label pairings. We hypothesize that depending on the order of presentation, the result of the learning may be different. To this end, we consider two types of symbolic learning procedures: the Object‐Label (OL) and the Label‐Object (LO) process. In the OL process, the learner is first exposed to the object, and then the label. In the LO process, this order is reversed. We perform experiments with human subjects, and also construct a computational model that is based on a nonlinear stochastic reinforcement learning algorithm. It is observed experimentally that OL learners are generally better at processing inconsistent input compared to LO learners. We show that the patterns observed in the learning experiments can be reproduced in the simulations if the model includes (a) an ability to regularize the input (and also to do the opposite, i.e., undermatch) and (b) an ability to take account of implicit negative evidence (i.e., interactions among different objects/labels). The model suggests that while both types of learners utilize implicit negative evidence in a similar way, there is a difference in regularization patterns: OL learners regularize the input, whereas LO learners undermatch. As a result, OL learners are able to form a more consistent system of image‐utterance associations, despite the ambiguous learning task. (shrink)

Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e., we are particularly interested in prediction (...) of Martin-Löf random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching measure satisfies this requirement with a large reserve. (shrink)

Polynomial clone reducibilities are generalizations of the truth-table reducibilities. A polynomial clone is a set of functions over a finite set X that is closed under composition and contains all the constant and projection functions. For a fixed polynomial clone ${\fancyscript{C}}$ , a sequence ${B\in X^{\omega}}$ is ${\fancyscript{C}}$ -reducible to ${A \in {X}^{\omega}}$ if there is an algorithm that computes B from A using only effectively selected functions from ${\fancyscript{C}}$ . We show that if A is Kurtz random and (...) ${\fancyscript{C}_{1} \nsubseteq \fancyscript{C}_{2}}$ are polynomial clones, then there is a B that is ${\fancyscript{C}_{1}}$ -reducible to A but not ${\fancyscript{C}_{2}}$ -reducible to A. This implies a generalization of a result first proved by Lachlan (Z Math Logik Grundlagen Math 11:17–44, 1965) for the case |X| = 2. We also show that the same result holds if Kurtz random is replaced by Kolmogorov–Loveland stochastic. (shrink)

Pseudorandom number generating algorithms play crucial roles in computer modeling and statistical modeling, but they have received little attention from philosophers of science. I revisit an argument that the success of practices in evolutionary biology using such algorithms in computer simulations provides evidence that evolutionary processes incorporate objective probabilities. I discuss the kind of stochasticity that pseudorandom number generators provide--what I call "pseudochance"--and argue that the argument from simulation practice, as well as other arguments, supports the view that evolutionary processes (...) incorporate pseudochance. I suggest that similar arguments might be given in other domains of science. (shrink)

The graph edit distance (GED) measures the dissimilarity between two graphs as the minimal cost of a sequence of elementary operations transforming one graph into another. This measure is fundamental in many areas such as structural pattern recognition or classification. However, exactly computing GED is NP-hard. Among different classes of heuristic algorithms that were proposed to compute approximate solutions, local search based algorithms provide the tightest upper bounds for GED. In this paper, we present K-REFINE and RANDPOST. K-REFINE generalizes and (...) improves an existing local search algorithm and performs particularly well on small graphs. RANDPOST is a general warm start framework that stochastically generates promising initial solutions to be used by any local search based GED algorithm. It is particularly efficient on large graphs. An extensive empirical evaluation demonstrates that both K-REFINE and RANDPOST perform excellently in practice. (shrink)

This book constitutes the refereed proceedings of the 12th International Conference on Theory and Applications of Satisfiability Testing, SAT 2009, held in Swansea, UK, in June/July 2009. The 34 revised full papers presented together with 11 revised short papers and 2 invited talks were carefully selected from 86 submissions. The papers are organized in topical sections on applications of SAT, complexity theory, structures for SAT, resolution and SAT, translations to CNF, techniques for conflict-driven SAT Solvers, solving SAT by local search, (...) hybrid SAT solvers, automatic adaption of SAT solvers, stochastic approaches to SAT solving, QBFs and their representations, optimization algorithms, distributed and parallel solving. (shrink)

This is a comprehensive discussion of complexity as it arises in physical, chemical, and biological systems, as well as in mathematical models of nature. Common features of these apparently unrelated fields are emphasised and incorporated into a uniform mathematical description, with the support of a large number of detailed examples and illustrations. The quantitative study of complexity is a rapidly developing subject with special impact in the fields of physics, mathematics, information science, and biology. Because of the variety of the (...) approaches, no comprehensive discussion has previously been attempted. This book will be of interest to graduate students and researchers in physics (nonlinear dynamics, fluid dynamics, solid-state, cellular automata, stochastic processes, statistical mechanics and thermodynamics), mathematics (dynamical systems, ergodic and probability theory), information and computer science (coding, information theory and algorithmic complexity), electrical engineering and theoretical biology. (shrink)

The results of evolutionary algorithms depend on population diversity that normally decreases by increasing the selection pressure from generation to generation. Usually, this can lead the evolution process to get stuck in local optima. This study is focused on mechanisms to avoid this undesired phenomenon by introducing parallel self-adapted differential evolution that decomposes a monolithic population into more variable-sized sub-populations and combining this with the characteristics of evolutionary multi-agent systems into a hybrid algorithm. The proposed hybrid algorithm operates (...) with individuals having some characteristics of agents, e.g. they act autonomously by selecting actions, with which they affect the state of the environment. Additionally, this algorithm incorporates two additional mechanisms: ageing and adaptive population growth, which help the individuals by decision-making. The proposed parallel differential evolution was applied to the CEC’18 benchmark function suite, while the produced results were compared with some traditional stochastic nature-inspired population-based and state-of-the-art algorithms. (shrink)

In this article we present symmetric diffusion networks, a family of networks that instantiate the principles of continuous, stochastic, adaptive and interactive propagation of information. Using methods of Markovion diffusion theory, we formalize the activation dynamics of these networks and then show that they can be trained to reproduce entire multivariate probability distributions on their outputs using the contrastive Hebbion learning rule (CHL). We show that CHL performs gradient descent on an error function that captures differences between desired and (...) obtained continuous multivariate probability distributions. This allows the learning algorithm to go beyond expected values of output units and to approximate complete probability distributions on continuous multivariate activation spaces. We argue that learning continuous distributions is an important task underlying a variety of real‐life situations that were beyond the scope of previous connectionist networks. Deterministic networks, like back propagation, cannot learn this task because they are limited to learning average values of independent output units. Previous stochastic connectionist networks could learn probability distributions but they were limited to discrete variables. Simulations show that symmetric diffusion networks can be trained with the CHL rule to approximate discrete and continuous probability distributions of various types. (shrink)

It was meaningful to predict the customers' decision-making behavior in the field of market. However, due to individual differences and complex, non-linear natures of the electroencephalogram signals, it was hard to classify the EEG signals and to predict customers' decisions by using traditional classification methods. To solve the aforementioned problems, a recurrent t-distributed stochastic neighbor embedding neural network was proposed in current study to classify the EEG signals in the designed brand extension paradigm and to predict the participants' decisions. (...) The recurrent t-SNE neural network contained two steps. In the first step, t-SNE algorithm was performed to extract features from EEG signals. Second, a recurrent neural network with long short-term memory layer, fully connected layer, and SoftMax layer was established to train the features, classify the EEG signals, as well as predict the cognitive performance. The proposed network could give a good prediction with accuracy around 87%. Its superior in prediction accuracy as compared to a recurrent principal component analysis network, a recurrent independent component correlation algorithm [independent component analysis ] network, a t-SNE support vector machine network, a t-SNE back propagation neural network, a deep LSTM neural network, and a convolutional neural network were also demonstrated. Moreover, the performance of the proposed network with different activated channels were also investigated and compared. The results showed that the proposed network could make a relatively good prediction with only 16 channels. The proposed network would become a potentially useful tool to help a company in making marketing decisions and to help uncover the neural mechanisms behind individuals' decision-making behavior with low cost and high efficiency. (shrink)

��The Coherent Approximation Principle (CAP) is a method for aggregating forecasts of probability from a group of judges by enforcing coherence with minimal adjustment. This paper explores two methods to further improve the forecasting accuracy within the CAP framework and proposes practical algorithms that implement them. These methods allow flexibility to add fixed constraints to the coherentization process and compensate for the psychological bias present in probability estimates from human judges. The algorithms were tested on a data set of nearly (...) half a million probability estimates of events related to the 2008 U.S. presidential election (from about 16000 judges). The results show that both methods improve the stochastic accuracy of the aggregated forecasts compared to using simple CAP. (shrink)

As an advanced network calculation mode, cloud computing is becoming more and more popular. However, with the proliferation of large data centers hosting cloud applications, the growth of energy consumption has been explosive. Surveys show that a remarkable part of the large energy consumed in data center results from over-provisioning of the network resource to meet requests during peak demand times. In this paper, we propose a solution to this problem by constructing a dynamic energy-efficient resource management scheme. As a (...) way of saving energy as well as maintaining cloud user’s quality of experience, the scheme presents a multitier cloud architecture by configuring physical machines into two pools: a hot pool and a warm pool. Each PM is configured with a resource search engine that finds an available virtual machine for the request, and a synchronous sleep mechanism is introduced to the warm pool. To analyze the end-to-end performance of the cloud system’s service with the proposed scheme, we establish a hybrid queueing system composed of three stochastic submodels by using a matrix-geometric solution. Accordingly, the average latency of requests and the energy-saving rate of the system are derived. Through numerical results, we show the influence of the synchronous sleep mechanism on the system performance. Moreover, from the perspective of economics, we build a system cost function to study the trade-off between different performance measures. An improved Salp Swarm Algorithm is presented to minimize the system cost and optimize the sleep parameter. (shrink)

Non-compensatory aggregation rules are applied in a variety of problems such as voting theory, multi-criteria analysis, composite indicators, web ranking algorithms and so on. A major open problem is the fact that non-compensability implies the analytical cost of loosing all available information about intensity of preference, i.e. if some variables are measured on interval or ratio scales, they have to be treated as measured on an ordinal scale. Here this problem has been tackled in its most general formulation, that is (...) when mixed measurement scales (interval, ratio and ordinal) are used and both stochastic and fuzzy uncertainties are present. Objectives of this article are first to present a comprehensive review of useful solutions already proposed in the literature and second to advance the state of the art mainly in the theoretical guarantee that weights have the meaning of importance coefficients and they can be summarized in a voting matrix. This is a key result for using non-compensatory Condorcet consistent rules. A proof on the probability of existence of ties in the voting matrix is also developed. (shrink)