Estimation of Distribution Algorithms, which employ probabilistic models to generate the next population, are new promising methods in the field of genetic and evolutionary algorithms. In the case of conventional Genetic and Evolutionary Algorithms are applied to Constraint Satisfaction Problems, it is well-known that the incorporation of the domain knowledge in the Constraint Satisfaction Problems is quite effective. In this paper, we constitute a memetic algorithm as a combination of the (...) class='Hi'>Estimation of Distribution Algorithm and a repair method. Experimental results on general Constraint Satisfaction Problems tell us the effectiveness of the proposed method. (shrink)

The Next Release Problem (NRP) is a combinatorial optimization problem that aims to find a subset of software requirements to be delivered in the next software release, which maximize the satisfaction of a list of clients and minimize the effort required by developers to implement them. Previous studies have applied various metaheuristics, mostly genetic algorithms. Estimation of Distribution Algorithms (EDA), based on probabilistic modelling, have been proved to obtain good results in problems where genetic algorithms struggle. In (...) this paper we propose to adapt three EDAs to tackle the multi-objective NRP in a fast and effective way. Results show that EDAs can be applicable to solve the NRP with rather good quality of solutions. Furthermore, we prove that their execution time can be significantly reduced using a per-iteration solution subset selection method while maintaining the overall quality of the solutions obtained, and they perform the best when limiting the search time as in an interactive tool that requires fast responsiveness. The experimental framework, code and datasets have been made public in a code repository. (shrink)

A theory of analogical mapping between source and target analogs based upon interacting structural, semantic, and pragmatic constraints is proposed here. The structural constraint of isomorphism encourages mappings that maximize the consistency of relational corresondences between the elements of the two analogs. The constraint of semantic similarity supports mapping hypotheses to the degree that mapped predicates have similar meanings. The constraint of pragmatic centrality favors mappings involving elements the analogist believes to be important in order to achieve (...) the purpose for which the analogy is being used. The theory is implemented in a computer program called ACME (Analogical Constraint Mapping Engine), which represents constraints by means of a network of supporting and competing hypotheses regarding what elements to map. A cooperative algorithm for parallel constraint satisfaction identities mapping hypotheses that collectively represent the overall mapping that best fits the interacting constraints. ACME has been applied to a wide range of examples that include problem analogies, analogical arguments, explanatory analogies, story analogies, formal analogies, and metaphors. ACME is sensitive to semantic and pragmatic information if it is available, and yet able to compute mappings between formally isomorphic analogs without any similar or identical elements. The theory is able to account for empirical findings regarding the impact of consistency and similarity on human processing of analogies. (shrink)

This paper provides a computational characterization of coherence that applies to a wide range of philosophical problems and psychological phenomena. Maximizing coherence is a matter of maximizing satisfaction of a set of positive and negative constraints. After comparing five algorithms for maximizing coherence, we show how our characterization of coherence overcomes traditional philosophical objections about circularity and truth.

In a seminal 1977 article, Rumelhart argued that perception required the simultaneous use of multiple sources of information, allowing perceivers to optimally interpret sensory information at many levels of representation in real time as information arrives. Building on Rumelhart's arguments, we present the Interactive Activation hypothesis—the idea that the mechanism used in perception and comprehension to achieve these feats exploits an interactive activation process implemented through the bidirectional propagation of activation among simple processing units. We then examine the interactive activation (...) model of letter and word perception and the TRACE model of speech perception, as early attempts to explore this hypothesis, and review the experimental evidence relevant to their assumptions and predictions. We consider how well these models address the computational challenge posed by the problem of perception, and we consider how consistent they are with evidence from behavioral experiments. We examine empirical and theoretical controversies surrounding the idea of interactive processing, including a controversy that swirls around the relationship between interactive computation and optimal Bayesian inference. Some of the implementation details of early versions of interactive activation models caused deviation from optimality and from aspects of human performance data. More recent versions of these models, however, overcome these deficiencies. Among these is a model called the multinomial interactive activation model, which explicitly links interactive activation and Bayesian computations. We also review evidence from neurophysiological and neuroimaging studies supporting the view that interactive processing is a characteristic of the perceptual processing machinery in the brain. In sum, we argue that a computational analysis, as well as behavioral and neuroscience evidence, all support the Interactive Activation hypothesis. The evidence suggests that contemporary versions of models based on the idea of interactive activation continue to provide a basis for efforts to achieve a fuller understanding of the process of perception. (shrink)

Bound-constrained optimization has wide applications in science and engineering. In the last two decades, various evolutionary algorithms were developed under the umbrella of evolutionary computation for solving various bound-constrained benchmark functions and various real-world problems. In general, the developed evolutionary algorithms belong to nature-inspired algorithms and swarm intelligence paradigms. Differential evolutionary algorithm is one of the most popular and well-known EAs and has secured top ranks in most of the EA competitions in the special session (...) of the IEEE Congress on Evolutionary Computation. In this paper, a customized differential evolutionary algorithm is suggested and applied on twenty-nine large-scale bound-constrained benchmark functions. The suggested C-DE algorithm has obtained promising numerical results in its 51 independent runs of simulations. Most of the 2013 IEEE-CEC benchmark functions are tackled efficiently in terms of proximity and diversity. (shrink)

The economical/environmental scheduling problem of the ship integrated energy system has high computational complexity, which includes more than one optimization objective, various types of constraints, and frequently fluctuated load demand. Therefore, the intelligent scheduling strategies cannot be applied to the ship energy management system online, which has limited computing power and storage space. Aiming at realizing green computing on SEMS, in this paper a typical SIES-EESP optimization model is built, considering the form of decision vectors, the economical/environmental optimization objectives, and (...) various types of real-world constraints of the SIES. Based on the complexity of SIES-EESPs, a two-stage offline-to-online multiobjective optimization strategy for SIES-EESP is proposed, which transfers part of the energy dispatch online computing task to the offline high-performance computer systems. The specific constraints handling methods are designed to reduce both continuous and discrete constraints violations of SIES-EESPs. Then, an establishment method of energy scheduling scheme-base is proposed. By using the big data offline, the economical/environmental scheduling solutions of a typical year can be obtained and stored with more computing resources and operation time on land. Thereafter, a short-term multiobjective offline-to-online optimization approach by SEMS is considered, with the application of multiobjective evolutionary algorithm and typical schemes corresponding to the actual SIES-EESPs. Simulation results show that the proposed strategy can obtain enough feasible Pareto solutions in a shorter time and get well-distributed Pareto sets with better convergence performance, which can well adapt to the features of real-world SIES-EESPs and save plenty of operation time and storage space for the SEMS. (shrink)

We consider a special case of heuristics, namely numeric heuristic evaluation functions, and their use in artificial intelligence search algorithms. The problems they are applied to fall into three general classes: single-agent path-finding problems, two-player games, and constraint-satisfaction problems. In a single-agent path-finding problem, such as the Fifteen Puzzle or the travelling salesman problem, a single agent searches for a shortest path from an initial state to a goal state. Two-player games, such as chess and checkers, involve an (...) adversarial relationship between two players, each trying to win the game. In a constraint-satisfaction, problem, such as the 8-Queens problem, the task is to find a state that satisfies a set of constraints. All of these problems are computationally intensive, and heuristic evaluation functions are used to reduce the amount of computation required to solve them. In each case we explain the nature of the evaluation functions used, how they are used in search algorithms, and how they can be automatically learned or acquired. (shrink)

For the application of the standard genetic algorithm in illustration art design, there are still problems such as low search efficiency and high complexity. This paper proposes an illustration art design model based on operator and clustering optimization genetic algorithm. First, during the operation of the genetic algorithm, the values of the crossover probability and the mutation probability are dynamically adjusted according to the characteristics of the population to improve the search efficiency of the algorithm, then the k-medoids algorithm is (...) introduced to optimize the clustering of the genetic algorithm, and a cost function is used to carry out and evaluate the quality of clustering to optimize the complexity of the original algorithm. In addition, a multiobjective optimization genetic algorithm with complex constraints based on group classification is proposed. This algorithm focuses on the problem of group diversity and uses k-means cluster analysis operation to solve the problem of group diversity. The algorithm divides the entire group into four subgroups and assigns appropriate fitness values to reflect the optimal preservation strategy. A large number of computer simulation calculations show that the algorithm can obtain a widely distributed and uniform Pareto optimal solution, the evolution speed is fast, usually only a few iterations can achieve a good optimization effect, and finally the improved genetic algorithm is used to design the random illustration art. The example simulation shows that the improved algorithm proposed in this paper can achieve higher artistic and innovative illustration art design. (shrink)

The field service scheduling problem is the key problem in field services. Field service pays particular attention to customer experience, that is, customer satisfaction. Customer satisfaction described by customer behavior characteristics based on the prospect theory is considered as the primary optimization goal in this paper. The knowledge of the insertion feasibility on the solution is analysed based on the skill constraint and time window. According to the knowledge, an initialization method based on the nearest heuristic algorithm (...) is constructed. Based on the prior knowledge of the FSSP and the endowment of the Fruit Fly Optimization Algorithm, two operators are defined according to the matrix encoding method. Based on these two operators, three search strategies are then proposed, and the smell-based search strategy and vision-based search strategy for the FOA are redesigned. To verify the performance of the algorithms, the proposed operators and strategies are tested and analysed in the well-known benchmark. Through comparison with the state-of-the-art algorithms, the results show that the proposed HFOA is an effective and efficient method to solve the FSSP with customer satisfaction. (shrink)

This volume contains the proceedings of three special sessions: Algebra and Computer Science, held during the Joint AMS-EMS-SPM meeting in Porto, Portugal, June 10–13, 2015; Groups, Algorithms, and Cryptography, held during the Joint Mathematics Meeting in San Antonio, TX, January 10–13, 2015; and Applications of Algebra to Cryptography, held during the Joint AMS-Israel Mathematical Union meeting in Tel-Aviv, Israel, June 16–19, 2014. Papers contained in this volume address a wide range of topics, from theoretical aspects of algebra, namely group theory, (...) universal algebra and related areas, to applications in several different areas of computer science. From the computational side, the book aims to reflect the rapidly emerging area of algorithmic problems in algebra, their computational complexity and applications, including information security, constraint satisfaction problems, and decision theory. The book gives special attention to recent advances in quantum computing that highlight the need for a variety of new intractability assumptions and have resulted in a new area called group-based cryptography. (shrink)

DCPS is a connectionist production system interpreter that uses distributed representations. As a connectionist model it consists of many simple, richly interconnected neuron‐like computing units that cooperate to solve problems in parallel. One motivation for constructing DCPS was to demonstrate that connectionist models are capable of representing and using explicit rules. A second motivation was to show how “coarse coding” or “distributed representations” can be used to construct a working memory that requires far fewer units than the number of different (...) facts that can potentially be stored. The simulation we present is intended as a detailed demonstration of the feasibility of certain ideas and should not be viewed as a full implementation of production systems. Our current model only has a few of the many interesting emergent properties that we eventually hope to demonstrate: It is damage‐resistant, it performs matching and variable binding by massively parallel constraint satisfaction, and the capacity of its working memory is dependent on the similarity of the items being stored. (shrink)

This research implements a recent evolutionary-based algorithm of equilibrium optimizer to resolve the constrained combined economic emission dispatch problem. This problem has two objective functions that represent the minimizing of generation costs and minimizing the emission of environmental pollution caused by generators. The proposed algorithm integrates the dominant criteria for multiobjective functions that allow the decision-maker to detect all the Pareto boundaries of constrained combined economic emission dispatch problem. In order to save the effort for the decision-maker to select (...) the best compromise alternative, a cluster study was carried out to minimize the size of the Pareto boundary to an acceptable size, representing all the characteristics of the main Pareto frontier. On the other hand, in order to deal with the infringement of constraints, a repair algorithm was used to preserve the viability of the particles. The proposed algorithm is applied to solve the standard 30-bus IEEE system with 6 generators to validate its robustness and efficiency to produce a well-distributed Pareto frontier for constrained combined economic emission dispatch problem. Compared with other studies, good results in solving constrained combined economic emission dispatch problem are obtained and a reasonable reduced Pareto set is found. (shrink)

Unsupervised learning techniques, e.g. clustering, is useful for obtaining a summary of a dataset. However, its application to large databases can be computationally expensive. Alternatively, useful information can also be retrieved from its subsets in a more efficient yet effective manner. This paper addresses the problem of finding a small subset of minority instances whose distribution significantly differs from that of the majority. Generally, such a subset can substantially overlap with the majority, which is problematic for conventional estimation (...) of distribution. This paper proposes a new approach for estimating a minority distribution based on Information Theoretic Framework, an extension of the Rate Distortion Theory for unsupervised learning tasks. Specifically, the proposed method estimates parameters which maximize the divergence between the minority and majority distributions, penalizes the redundancy of data expression based on the mutual information between the observed and hidden variables, and employs a hard assignment approximation to avoid computation of trivial conditional probabilities. The algorithm of the proposed method has no problem-dependent parameter and its time and space complexities are linear to the size of the minority subset. Experiments using artificial datasets show the proposed method yields significantly high precision and sensitivity in detecting minority subsets which substantially overlaps with the majority. The proposed method also substantially outperforms one-class classification and mixture estimation methods in real-world benchmark datasets for text and satellite imagery classification. (shrink)

This study suggests a new approach to EEG data classification by exploring the idea of using evolutionary computation to both select useful discriminative EEG features and optimise the topology of Artificial Neural Networks. An evolutionary algorithm is applied to select the most informative features from an initial set of 2550 EEG statistical features. Optimisation of a Multilayer Perceptron is performed with an evolutionary approach before classification to estimate the best hyperparameters of the network. Deep learning and (...) tuning with Long Short-Term Memory are also explored, and Adaptive Boosting of the two types of models is tested for each problem. Three experiments are provided for comparison using different classifiers: one for attention state classification, one for emotional sentiment classification, and a third experiment in which the goal is to guess the number a subject is thinking of. The obtained results show that an Adaptive Boosted LSTM can achieve an accuracy of 84.44%, 97.06%, and 9.94% on the attentional, emotional, and number datasets, respectively. An evolutionary-optimised MLP achieves results close to the Adaptive Boosted LSTM for the two first experiments and significantly higher for the number-guessing experiment with an Adaptive Boosted DEvo MLP reaching 31.35%, while being significantly quicker to train and classify. In particular, the accuracy of the nonboosted DEvo MLP was of 79.81%, 96.11%, and 27.07% in the same benchmarks. Two datasets for the experiments were gathered using a Muse EEG headband with four electrodes corresponding to TP9, AF7, AF8, and TP10 locations of the international EEG placement standard. The EEG MindBigData digits dataset was gathered from the TP9, FP1, FP2, and TP10 locations. (shrink)

This target article presents a new computational theory of explanatory coherence that applies to the acceptance and rejection of scientific hypotheses as well as to reasoning in everyday life, The theory consists of seven principles that establish relations of local coherence between a hypothesis and other propositions. A hypothesis coheres with propositions that it explains, or that explain it, or that participate with it in explaining other propositions, or that offer analogous explanations. Propositions are incoherent with each other if they (...) are contradictory, Propositions that describe the results of observation have a degree of acceptability on their own. An explanatory hypothesis is acccpted if it coheres better overall than its competitors. The power of the seven principles is shown by their implementation in a connectionist program called ECHO, which treats hypothesis evaluation as a constraint satisfaction problem. Inputs about the explanatory relations are used to create a network of units representing propositions, while coherende and incoherence relations are encoded by excitatory and inbihitory links. ECHO provides an algorithm for smoothly integrating theory evaluation based on considerations of explanatory breadth, simplicity, and analogy. It has been applied to such important scientific cases as Lovoisier's argument for oxygen against the phlogiston theory and Darwin's argument for evolution against creationism, and also to cases of legal reasoning. The theory of explanatory coherence has implications for artificial intelligence, psychology, and philosophy. (shrink)

This paper gives a brief survey of current research on the complexity of the constraint satisfaction problem over fixed constraint languages.

Constrained optimization plays an important role in many decision-making problems and various real-world applications. In the last two decades, various evolutionary algorithms were developed and still are developing under the umbrella of evolutionary computation. In general, EAs are mainly categorized into nature-inspired and swarm-intelligence- based paradigms. All these developed algorithms have some merits and also demerits. Particle swarm optimization, firefly algorithm, ant colony optimization, and bat algorithm have gained much popularity and they have successfully tackled various test (...) suites of benchmark functions and real-world problems. These SI-based algorithms follow the social and interactive principles to perform their search process while approximating solution for the given problems. In this paper, a multiswarm-intelligence-based algorithm is developed to cope with bound constrained functions. The suggested algorithm integrates the SI-based algorithms to evolve population and handle exploration versus exploitation issues. Thirty bound constrained benchmark functions are used to evaluate the performance of the proposed algorithm. The test suite of benchmark function is recently designed for the special session of EAs competition in IEEE Congress on Evolutionary Computation. The suggested algorithm has approximated promising solutions with good convergence and diversity maintenance for most of the used bound constrained single optimization problems. (shrink)

The year 2012 has witnessed worldwide celebrations of Alan Turing’s 100th birthday. A great number of conferences and workshops were organized by logicians, computer scientists and researchers in AI, showing the continued flourishing of computer science, and the fruitful interfaces between logic and computer science. Logic is no longer just the concept that Frege had about one hundred years ago, let alone that of Aristotle twenty centuries before. One of the prominent features of contemporary logic is its interdisciplinary character, connecting (...) across mathematics, philosophy, modern computer science, and even the cognitive and social sciences. -/- China is no exception. This special issue explores interfaces of logic with AI and other disciplines, and it attempts to give a bird’s eye view of the developing landscape of logic and AI in China. Our contributors come from computer science, AI, philosophy and linguistics, united by their interest in using formal logical tools and notions to deal with substantial problems in their fields. We are aware that AI is a vast area, and that the limitations of space in a volume like this may provide a somewhat incomplete or biased view. Still we hope that the six papers selected here illustrate the concerns and curiosity driving Chinese researchers, on topics shared with our colleagues around the world. -/- One of the active research areas in AI is planning under uncertainty, with incomplete knowledge, where a well-established logical framework is the action language of Son and Baral (Son and Baral 2001). This language can express the notions of sensing actions and making conditional plans. However, its current semantics is not yet satisfactory, since according to the semantics an agent would not have knowledge of what happens after a plan is executed, which can be a serious problem in a safety-critical environment. In their paper Proof Systems for Planning under Cautious Semantics (Shen and Zhao 2013), Yuping Shen and Xishun Zhao address this problem and propose a cautious and weakly cautious semantics for the action language. This new semantics enables the agent to know exactly what happens after executing an action. Hoare style proof systems are then proposed and proved to be sound and complete. What is more, the proposed new system reduces the reasoning complexity of the action language. -/- In Preferential Semantics for Plausible Subsumption in Possibility Theory (Qi and Zhang 2013), Guilin Qi and Zhizheng Zhang investigate another important issue in AI: how to handle exceptions in a knowledge-based system. This has become a hot topic in recent years, especially in ontological design, where description logics are widely used. The question then arises whether we can get a nonmonotonic extension of description logic. To answer this, the authors first propose three preferential semantics for plausible subsumption in the framework of possibility theory (Dubois and Prade 1985) and study their properties and their relationships. Then they introduce preferential subsumptions to a description logic-based knowledge system, and define an entailment relation of plausible subsumption. Moreover, they study reductions of the new semantics to standard semantics for an expressive description logic. -/- Counterfactual reasoning has been explored extensively by philosophers, cf. Lewis (1973), Stalnaker (1968). But in the last two decades, causal models have been proposed for modeling counterfactual reasoning by researchers in AI. In A Lewisian Logic of Causal Counterfactuals (Zhang 2013), Jiji Zhang studies classes of causal models and provides formal characterizations. In particular, a new logic system is proposed and proved complete for the class of ‘Lewisian models’ satisfying all the principles of David Lewis’s logic of counterfactuals. Moreover, Zhang compares his new framework with those of Lewis and Stalnaker, and also establishes formal connections with more recent approaches by Galles and Pearl, and by Halpern. -/- Consistency is a fundamental notion in logic, but it also plays a key role in many techniques for solving constraint satisfaction problems (Mackworth 1977). In Variable-Centered Consistency in Model RB (Li et al. 2013), Liang Li, Tian Liu and Ke Xu start with a discussion of i-consistency in ‘Model RB’ and ‘Model RD’, two models of random constraint satisfaction problems with growing domain size, then compare it with the notion of t-consistency and strong t-consistency in well-known earlier work by Freuder. After that, the authors define a new kind of variable-centered consistency, and show an upper bound on a suitably chosen parameter in Model RB and Model RD, such that up to this bound, all typical instances of Model RB are variable-centered consistent. -/- Language understanding is a cognitive process that human beings carry out every day. Metaphor is a pervasive phenomenon in natural languages, and its cognitive role calls for interpretation. There is a growing body of literature on cognitive mechanisms underlying metaphor. The paper An Ontology-Based Approach to Metaphor Cognitive Computation (Huang et al. 2013) by Xiaoxi Huang, Huaxin Huang, Beishui Liao, and Cihua Xu proposes a theoretical framework for metaphor understanding based on recent results from cognitive science (Shutova 2010). They then introduce ontology as a knowledge representation method, and present a new ontological model to formalize metaphor-based knowledge. An algorithmic description is provided using a quantitative measure of integrated degree, and its effectiveness is demonstrated. -/- Puzzles and their solution mechanisms are a recurrent theme in many fields. Dynamic epistemic logic (van Ditmarsch et al. 2007); (van Benthem 2011) is a recent framework that can handle information dynamics in knowledge puzzles. In Reasoning About Agent Types and the Hardest Logic Puzzle Ever (Liu and Wang 2013), Fenrong Liu and Yanjing Wang propose a new dynamic-epistemic logic that can specify different types of agents and analyse agents’ knowledge, communication and reasoning. To demonstrate its power, Smullyan’s well-known Knights and Knaves puzzles are formalized, as well as the Hardest Logic Puzzle Ever (HLPE) of Boolos (Boolos 1996). Moreover, a spectrum of new puzzles is found involving knowledge-based agent types, and their solution complexity is shown to be harder than that for existing logic puzzles. It is also shown that a version of HLPE in which the agents do not know the others’ types does not have a solution at all. -/- Finally, we would like to thank the editor of Minds and Machines, Gregory Wheeler, for his efficient assistance and kind support. We also thank Ties Nijssen at Springer for his encouragement to start this project at the first place. And of course, our appreciation goes to our authors, as well as all the colleagues who have helped us review the papers in this collection. (shrink)

This paper investigates the Generalized Traveling Salesman Problem (GTSP), which is an extension of the well-known Traveling Salesman Problem (TSP), and it searches for an optimal tour in a clustered graph, such that every cluster is visited exactly once. In this paper, we describe a novel Memetic Algorithm (MA) for solving efficiently the GTSP. Our proposed MA has at its core a genetic algorithm (GA), completed by a Chromosome Enhancement Procedure (CEP), which is based on a TSP solver and (...) the Shortest Path (SP) algorithm and for improving the convergence characteristics of the GA, a Local Search (LS) operation is applied for the best chromosomes in each generation. We tested our algorithm on a set of well-known instances from the literature and the achieved results prove that our novel memetic algorithm is highly competitive against the existing solution approaches from the specialized literature. (shrink)

Although the theory of memetics appeared highly promising at the beginning, it is no longer considered a scientific theory among contemporary evolutionary scholars. This study aims to compare the genealogy of memetics with the historically more successful gene-culture coevolution theory. This comparison is made in order to determine the constraints that emerged during the internal development of the memetics theory that could bias memeticists to work on the ontology of meme units as opposed to hypotheses testing, which was adopted (...) by the gene-culture scholars. I trace this problem back to the diachronic development of memetics to its origin in the gene-centered anti-group-selectionist argument of George C. Williams and Richard Dawkins. The strict adoption of this argument predisposed memeticists with the a priori idea that there is no evolution without discrete units of selection, which in turn, made them dependent on the principal separation of biological and memetic fitness. This separation thus prevented memeticists from accepting an adaptationist view of culture which, on the contrary, allowed gene-culture theorists to attract more scientists to test the hypotheses, creating the historical success of the gene-culture coevolution theory. (shrink)

Progress in the medical diagnostic is relentlessly pushing the measurement technology as well with its intertwined mathematical models and solutions. Mathematics has applications to many problems that are vital to human health but not for all. In this article we describe how the mathematics of acoustocerebrography has become one of the most important applications of mathematics to the problems of brain monitoring as well we will show some algebraic problems which still have to be solved. Acoustocerebrography is a set of (...) techniques of visualizing the state of brain tissue and its changes with use of ultrasounds, which mainly rely on a relation between the tissue density and speed of propagation for ultrasound waves in this medium. Propagation speed or, equivalently, times of arriving for an ultrasound pulse, can be inferred from phase relations for various frequencies. Since, due to Kramers-Kronig relations, the propagation speeds depend significantly on the frequency of investigated waves, we consider multispectral wave packages of the form W = ∑Hh=1 Ah · sin, n = 0,..., N – 1 with appropriately chosen frequencies fh, h = 1,...,H, amplifications Ah, h = 1,...,H, start phases ψh, h = 1,..., H and sampling frequency F. In this paper we show some problems of algebraic and, to some extend, algorithmic nature which raise up in this topic. Like, for instance, the influence of relations between the signal length and frequency values on the error on estimated phases or on neutralizing alien frequencies. Another problem is finding appropriate initial phases for avoiding improper distributions of peaks in the resulting signal or finding a stable algorithm of phase unwinding which is resistant to sudden random disruptions. (shrink)

In the context of solving large distributed constraint optimization problems, belief-propagation and incomplete inference algorithms are candidates of choice. However, in general, when the problem structure is very cyclic, these solution methods suffer from bad performance, due to non-convergence and many exchanged messages. As to improve performances of the MaxSum inference algorithm when solving cyclic constraint optimization problems, we propose here to take inspiration from the belief-propagation-guided decimation used to solve sparse random graphs. We propose the novel DeciMaxSum (...) method, which is parameterized in terms of policies to decide when to trigger decimation, which variables to decimate and which values to assign to decimated variables. Based on an empirical evaluation on a classical constraint optimization benchmarks, some of these combinations of policies, using periodic decimation, cycle detection-based decimation, parallel and non parallel decimation, random or deterministic variable selection and deterministic or random sampling for value selection, outperform state-of-the-art competitors in many settings. (shrink)

There exist two conjectures for constraint satisfaction problems of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain nontrivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities satisfied by its polymorphisms clone, together with the natural (...) uniformity on it, being nontrivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that [Formula: see text]-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking another approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a nontrivial system of linear identities, and obtain nontrivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every [Formula: see text]-categorical structure is homomorphically equivalent to a model-complete core. (shrink)

The aim of this study is to justify the belief that there are biological normative mechanisms that fulfill non-trivial causal roles in the explanations (as formulated by researchers) of actions and behaviors present in specific systems. One example of such mechanisms is the predictive mechanisms described and explained by predictive processing (hereinafter PP), which (1) guide actions and (2) shape causal transitions between states that have specific content and fulfillment conditions (e.g. mental states). Therefore, I am guided by a specific (...) theoretical goal associated with the need to indicate those conditions that should be met by the non-trivial theory of normative mechanisms and the specific models proposed by PP supporters. In this work, I use classical philosophical methods, such as conceptual analysis and critical reflection. I also analyze selected studies in the field of cognitive science, cognitive psychology, neurology, information theory and biology in terms of the methodology, argumentation and language used, in accordance with their theoretical importance for the issues discussed in this study. In this sense, the research presented here is interdisciplinary. My research framework is informed by the mechanistic model of explanation, which defines the necessary and sufficient conditions for explaining a given phenomenon. The research methods I chose are therefore related to the problems that I intend to solve. In the introductory chapter, “The concept of predictive processing”, I discuss the nature of PP as well as its main assumptions and theses. I also highlight the key concepts and distinctions for this research framework. Many authors argue that PP is a contemporary version of Kantianism and is exposed to objections similar to those made against the approach of Immanuel Kant. I discuss this thesis and show that it is only in a very general sense that the PP framework is neo-Kantian. Here we are not dealing with transcendental deduction nor with the application of transcendental arguments. I argue that PP is based on reverse engineering and abduction inferences. In the second part of this chapter, I respond to the objection formulated by Dan Zahavi, who directly accuses this research framework of anti-realistic consequences. I demonstrate that the position of internalism, present in the so-called conservative PP, does not imply anti-realism, and that, due to the explanatory role played in it by structural representations directed at real patterns, it is justified to claim that PP is realistic. In this way, I show that PP is a non-trivial research framework, having its subject, specific methods and its own epistemic status. Finally, I discuss positions classified as the socalled radical PP. In the chapter “Predictive processing as a Bayesian explanatory model” I justify the thesis according to which PP offers Bayesian modeling. Many researchers claim that the brain is an implemented statistical probabilistic network that is an approximation of the Bayesian 7 rule. In practice, this means that all cognitive processes are to apply Bayes' rule and can be described in terms of probability distributions. Such a solution arouses objections among many researchers and is the subject of wide criticism. The purpose of this chapter is to justify the thesis that Bayesian PP is a non-trivial research framework. For this purpose, I argue that it explains certain phenomena not only at the computational level described by David Marr, but also at the level of algorithms and implementation. Later in this chapter I demonstrate that PP is normative modeling. Proponents of the use of Bayesian models in psychology or decision theory argue that they are normative because they allow the formulation of formal rules of action that show what needs to be done to make a given action optimal. Critics of this approach emphasize that such thinking about the normativity of Bayesian modeling is unjustified and that science should shift from prescriptive to descriptive positions. In a polemic with Shira Elqayam and Jonathan Evans (2011), I show that the division they propose into prescriptivism and Bayesian descriptivism is apparent, because, as I argue, there are two forms of prescriptivism, i.e. the weak and the strong. I argue that the weak version is epistemic and can lead to anti-realism, while the strong version is ontic and allows one to justify realism in relation to Bayesian models. I argue that a weak version of prescriptivism is valid for PP. It allows us to adopt anti-realism in relation to PP. In practice, this means that you can explain phenomena using Bayes' rule. This does not, however, imply that they are Bayesian in nature. However, the full justification of realism in relation to the Bayesian PP presupposes the adoption of strong prescriptivism. This position assumes that phenomena are explained by Bayesian rule because they are Bayesian as such. If they are Bayesian in nature, then they should be explained using Bayesian modeling. This thesis will be substantiated in the chapters “Normative functions and mechanisms in the context of predictive processing” and “Normative mechanisms and actions in predictive processing”. In the chapter “The Free Energy Principle in predictive processing”, I discuss the Free Energy Principle (hereinafter FEP) formulated by Karl Friston and some of its implications. According to this principle, all biological systems (defined in terms of Markov blankets) minimize the free energy of their internal states in order to maintain homeostasis. Some researchers believe that PP is a special case of applying this principle to cognition, and that predictive mechanisms are homeostatic mechanisms that minimize free energy. The discussion of FEP is important due to the fact that some authors consider it to be important for explanatory purposes and normative. If this is the case, then FEP turns out to be crucial in explaining normative predictive mechanisms and, in general, any normative biological mechanisms. To define the explanatory possibilities of this principle, I refer to the discussion of its supporters on the issue they define as the problem of continuity and discontinuity between life and mind. A critical analysis of this discussion and the additional arguments I have formulated have allowed me to revise the explanatory ambitions of FEP. I also reject the belief that this principle is necessary to explain the nature of predictive mechanisms. I argue that the principle formulated and defended by Friston is an important research heuristic for PP analysis. 8 In the chapter “Normative functions and mechanisms in predictive processing”, I start my analyzes by formulating an answer to the question about the normative nature of homeostatic mechanisms. I demonstrate that predictive mechanisms are not homeostatic. I defend the view that a full explanation of normative mechanisms presupposes an explanation of normative functions. I discuss the most important proposals for understanding the normativity of a function, both from a systemic and teleosemantic perspective. I conclude that the non-trivial concept of a function must meet two requirements which I define as explanatory and normative. I show that none of the theories I have invoked satisfactorily meets both of these requirements. Instead, I propose a model of normativity based on Bickhard's account, but supplemented by a mechanistic perspective. I argue that a function is normative when: (1) it allows one to explain the dysfunction of a given mechanism; (2) it contributes to the maintenance of the organism's stability by shaping and limiting possible relations, processes and behaviors of a given system; and when (3) (according to the representational and predictive functions) it enables explaining the attribution of logical values of certain representations / predictions. In such an approach, a mechanism is normative when it performs certain normative functions and when it is constitutive for a specific action or behavior, despite the fact that for some reason it cannot realize it either currently or in the long-term. Such an understanding of the normativity of mechanisms presupposes the acceptance of the epistemic hypothesis. I argue that this hypothesis is not cognitively satisfactory, and therefore the ontic hypothesis should be justified, which is directly related to adopting the position of ontic prescriptivism. For this reason, referring to the mechanistic theory of scientific explanations, I formulate an ontical interpretation of the concept of a normative mechanism. According to this approach, a mechanism or a function is normative when they perform such and such causal roles in explaining certain actions and behaviors. With regard to the normative properties of predictive mechanisms and functions, this means that they are the causes of specific actions an organism carries out in the environment. In this way, I justify the necessity of accepting the ontic hypothesis and rejecting the epistemic hypothesis. The fifth chapter, “Normative mechanisms and actions in predictive processing”, is devoted to the dark room problem and the related exploration-exploitation trade-off. A dark room is the state that an agent could be in if it minimized the sum of all potential prediction errors. I demonstrate that, in accordance with the basic assumption of PP about the need for continuous and long-term minimization of prediction errors, such a state should be desirable for the agent. Is it really so? Many authors believe it is not. I argue that the test of the value of PP is the possibility of a non-trivial solution of this problem, which can be reduced to the choice between active and uncertainty-increasing exploration and safe and easily predictable exploitation. I show that the solution proposed by PP supporters present in the literature does not enable a fully satisfactory explanation of this dilemma. Then I defend the position according to which the full explanation of the normative mechanisms, and, subsequently, the solution to the dilemma of exploration and exploitation, involves reference to the existence of constraints present in the environment. The constraints 9 include elements of the environment that make a given mechanism not only causal but also normative. They are therefore key to explaining the predictive mechanisms. They do not only play the role of the context in which the mechanism is implemented, but, above all, are its constitutive component. I argue that the full explanation of the role of constraints in normative predictive mechanisms presupposes the integration of individual models of specific cognitive phenomena, because only the mechanistic integration of PP with other models allows for a non-trivial explanation of the nature of normative predictive mechanisms that would have a strong explanatory value. The explanatory monism present in many approaches to PP makes it impossible to solve the problem of the dark room. Later in this chapter, I argue that the Bayesian PP is normative not because it enables the formulation of such and such rules of action, but because the predictive mechanisms themselves are normative. They are normative because they condition the choice of such and such actions by agents. In this way, I justify the hypothesis that normative mechanisms make it possible to explain the phenomenon of agent motivation, which is crucial for solving the dark room problem. In the last part of the chapter, I formulate the hypothesis of distributed normativity, which assumes that the normative nature of certain mechanisms, functions or objects is determined by the relations into which these mechanisms, functions or objects enter. This means that what is normative (in the primary sense) is the relational structure that constitutes the normativity of specific items included in it. I suggest that this hypothesis opens up many areas of research and makes it possible to rethink many problems. In the “Conclusion”, I summarize the results of my research and indicate further research perspectives. (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)

A fixed-parameter is an algorithm that provides an optimal solution to a combinatorial problem. This research-level text is an application-oriented introduction to the growing and highly topical area of the development and analysis of efficient fixed-parameter algorithms for hard problems. The book is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the (...) essential from parameterized hardness theory with a focus on W [1]-hardness, which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology. Aimed at graduate and research mathematicians, programmers, algorithm designers and computer scientists, the book introduces the basic techniques and results and provides a fresh view on this highly innovative field of algorithmic research. (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 (...) class='Hi'>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)

Schedule planning is one of the most crucial issues for any airline company, because the profit of the company directly depends on the efficiency of the schedule. This paper presents a novel scheduling method which solves problems related to time scheduling, fleet assignment and maintenance routing simultaneously by Genetic Algorithms. Every schedule constraint is embeded in the fitness function, which is described as an object oriented model and works as a simulater developing itself over time, and whose solution is (...) executable without human correction. The schedular is able to solve the problems involving several hundred flights in a few hours, and the solutions are superior or equivalent to those by human experts in terms of the estimated profit. (shrink)

1. Argumentation, by considering arguments and their interactions, is a way of reasoning that has proven successful in many contexts, for instance, in multi-agent applications (Carrera & Iglesias,...

Motivated by constraint satisfaction problems, Feder and Vardi (SIAM Journal of Computing, 28, 57–104, 1998) set out to search for fragments of satisfying the dichotomy property: every problem definable in is either in P or else NP-complete. Feder and Vardi considered in this connection two logics, strict NP (or SNP) and monadic, monotone, strict NP without inequalities (or MMSNP). The former consists of formulas of the form , where is a quantifier-free formula in a relational vocabulary; and the (...) latter is the fragment of SNP whose formulas involve only negative occurrences of relation symbols, only monadic second-order quantifiers, and no occurrences of the equality symbol. It remains an open problem whether MMSNP enjoys the dichotomy property. In the present paper, SNP and MMSNP are characterized in terms of partially ordered connectives. More specifically, SNP is characterized using the logic D of partially ordered connectives introduced in Blass and Gurevich (Annals of Pure and Applied Logic, 32, 1–16, 1986), Sandu and Väänänen (Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 38, 361–372 1992), and MMSNP employing a generalization C of D introduced in the present paper. (shrink)

Model RB is a model of random constraint satisfaction problems, which exhibits exact satisfiability phase transition and many hard instances, both experimentally and theoretically. Benchmarks based on Model RB have been successfully used by various international algorithm competitions and many research papers. In a previous work, Xu and Li defined two notions called i-constraint assignment tuple and flawed i-constraint assignment tuple to show an exponential resolution complexity of Model RB. These two notions are similar to some (...) kind of consistency in constraint satisfaction problems, but seem different from all kinds of consistency so far known in literatures. In this paper, we explicitly define this kind of consistency, called variable-centered consistency, and show an upper bound on a parameter in Model RB, such that up to this bound the typical instances of Model RB are variable-centered consistent. (shrink)

This paper explores the ethical relevance of a precise new characterization of coherence as maximization of satisfaction of positive and negative constraints. A coherence problem can be stated by specifying a set of elements to be accepted or rejected along with sets of positive and negative constraints that incline pairs of elements to be accepted together or rejected together. Computationally tractable and psychologically plausible algorithms are available for determining the acceptance and rejection of elements in a way that reliably (...) approximates coherence maximization. This paper shows how justification of ethical principles and particular judgments can be accomplished by taking into account deductive, explanatory, analogical, and deliberative coherence. (shrink)

The statistical community has brought logical rigor and mathematical precision to the problem of using data to make inferences about a model’s parameter values. The TETRAD project, and related work in computer science and statistics, aims to apply those standards to the problem of using data and background knowledge to make inferences about a model’s specification. We begin by drawing the analogy between parameter estimation and model specification search. We then describe how the specification of a structural equation model (...) entails familiar constraints on the covariance matrix for all admissible values of its parameters; we survey results on the equivalence of structural equation models, and we discuss search strategies for model specification. We end by presenting several algorithms that are implemented in the TETRAD II program. (shrink)

Argumentation has been an important topic in knowledge representation, reasoning and multi-agent systems during the last twenty years. In this paper, we propose a new abstract framework where arguments are associated with a strength, namely a quantitative information which is used to determine whether an attack between arguments succeeds or not. Our Strength-based Argumentation Framework combines ideas of Preference-based and Weighted Argumentation Frameworks in an original way, which permits to define acceptability semantics sensitive to the existence of accruals between arguments. (...) The question of accruals arises in situations where several arguments defending the same position against another argument are unable to individually defeat this argument, but could do it collectively if they combine their strengths. We investigate some of the theoretical and computational properties of our new framework and semantics, and present a reasoning algorithm that is based on a translation of the problem into pseudo-boolean constraint satisfaction. This paper proposes an intuitive framework which allows strength compensations in an argumentation context where attacks may not succeed, completed by an approach which detects accruals throughout the reasoning process without requiring the elicitation of all compensatory combinations of arguments as an input. (shrink)

Argumentation has been an important topic in knowledge representation, reasoning and multi-agent systems during the last twenty years. In this paper, we propose a new abstract framework where arguments are associated with a strength, namely a quantitative information which is used to determine whether an attack between arguments succeeds or not. Our Strength-based Argumentation Framework (StrAF) combines ideas of Preference-based and Weighted Argumentation Frameworks in an original way, which permits to define acceptability semantics sensitive to the existence of accruals between (...) arguments. The question of accruals arises in situations where several arguments defending the same position (but from different points of view) against another argument are unable to individually defeat this argument, but could do it collectively if they combine their strengths. We investigate some of the theoretical and computational properties of our new framework and semantics, and present a reasoning algorithm that is based on a translation of the problem into pseudo-boolean constraint satisfaction. This paper proposes an intuitive framework which allows strength compensations in an argumentation context where attacks may not succeed, completed by an approach which detects accruals throughout the reasoning process without requiring the elicitation of all compensatory combinations of arguments as an input. (shrink)

Many contemporary philosophers favor coherence theories of knowledge (Bender 1989, BonJour 1985, Davidson 1986, Harman 1986, Lehrer 1990). But the nature of coherence is usually left vague, with no method provided for determining whether a belief should be accepted or rejected on the basis of its coherence or incoherence with other beliefs. Haack's (1993) explication of coherence relies largely on an analogy between epistemic justification and crossword puzzles. We show in this paper how epistemic coherence can be understood in terms (...) of maximization of constraint satisfaction, in keeping with computational models that have had a substantial impact in cognitive science. A coherence problem can be defined in terms of a set of elements and sets of positive and negative constraints between pairs of those elements. Algorithms are available for computing coherence by determining how to accept and reject elements in a way that satisfies the most constraints. Knowledge involves at least five different kinds of coherence - explanatory, analogical, deductive, perceptual, and conceptual - each requiring different sorts of elements and constraints. (shrink)

The fuzzy clustering algorithm has been widely used in the research area and production and life. However, the conventional fuzzy algorithms have a disadvantage of high computational complexity. This article proposes an improved fuzzy C-means algorithm based on K-means and principle of granularity. This algorithm is aiming at solving the problems of optimal number of clusters and sensitivity to the data initialization in the conventional FCM methods. The initialization stage of the K-medoid cluster, which is different from others, has a (...) strong representation and is capable of detecting data with different sizes. Meanwhile, through the combination of the granular computing and FCM, the optimal number of clusters is obtained by choosing accurate validity functions. Finally, the detailed clustering process of the proposed algorithm is presented, and its performance is validated by simulation tests. The test results show that the proposed improved FCM algorithm has enhanced clustering performance in the computational complexity, running time, cluster effectiveness compared with the existing FCM algorithms. (shrink)

We observe a number of connections between recent developments in the study of constraint satisfaction problems, irredundant axiomatisation and the study of topological quasivarieties. Several restricted forms of a conjecture of Clark, Davey, Jackson and Pitkethly are solved: for example we show that if, for a finite relational structure M, the class of M-colourable structures has no finite axiomatisation in first order logic, then there is no set (even infinite) of first order sentences characterising the continuously M-colourable structures (...) amongst compact totally disconnected relational structures. We also refute a rather old conjecture of Gorbunov by presenting a finite structure with an infinite irredundant quasi-identity basis. (shrink)

Journal of Mathematical Logic, Ahead of Print.

In order to deal with high-dimensional distributed data, this article develops a novel and communication-efficient approach for sparse and high-dimensional data with the penalized quantile regression. In each round, the proposed method only requires the master machine to deal with a sparse penalized quantile regression which could be realized fastly by proximal alternating direction method of multipliers algorithm and the other worker machines to compute the subgradient on local data. The advantage of the proximal ADMM algorithm is that it could (...) make every parameter of iteration to have closed formula even in high-dimensional case, which greatly improves the speed of calculation. As for the communication efficiency, the proposed method does not sacrifice any statistical accuracy and provably improves the estimation error obtained by centralized method, provided the penalty levels are chosen properly. Moreover, the asymptotic properties of the proposed estimation and the convergence of the algorithm are convincible. Especially, it presents extensive experiments on both the numerical simulations and the HIV drug resistance data analysis, which all confirm the significant efficiency of our proposed method in quantile regression for distributed data by comparative and empirical analysis. (shrink)