Title Paper: Natural computing: A problem solving paradigm with granular information processing

Natural computing, inspired by biological course of action, is an interdisciplinary field that formalizes processes observed in living organisms to design computational methods for solving complex problems, or designing artificial systems with more natural behaviour. Based on the tasks abstracted from natural phenomena, such as brain modelling, self-organization, self-repetition, self evaluation, Darwinian survival, granulation and perception, nature serves as a source of inspiration for the development of computational tools or systems that are used for solving complex problems. Nature inspired main computing paradigms used for such development include artificial neural networks, fuzzy logic, rough sets, evolutionary algorithms, fractal geometry, DNA computing, artificial life and granular or perception-based computing. Information granulation in granular computing is an inherent characteristic of human thinking and reasoning process performed in everyday life. The present article provides an overview of the significance of natural computing with respect to the granulation-based information processing models, such as neural networks, fuzzy sets and rough sets, and their hybridization. We emphasize on the biological motivation, design principles, application areas, open research problems and challenging issues of these models.     

Building the fundamentals of granular computing: A principle of justifiable granularity

The study introduces and discusses a principle of justifiable granularity, which supports a coherent way of designing information granules in presence of experimental evidence (either of numerical or granular character). The term “justifiable” pertains to the construction of the information granule, which is formed in such a way that it is (a) highly legitimate (justified) in light of the experimental evidence, and (b) specific enough meaning it comes with a well-articulated semantics (meaning). The design process associates with a well-defined optimization problem with the two requirements of experimental justification and specificity. A series of experiments is provided as well as a number of constructs carried for various formalisms of information granules (intervals, fuzzy sets, rough sets, and shadowed sets) are discussed as well.     

Fuzzy rough granular neural networks, fuzzy granules, and classification

We introduce a fuzzy rough granular neural network (FRGNN) model based on the multilayer perceptron using a back-propagation algorithm for the fuzzy classification of patterns. We provide the development strategy of the network mainly based upon the input vector, initial connection weights determined by fuzzy rough set theoretic concepts, and the target vector. While the input vector is described in terms of fuzzy granules, the target vector is defined in terms of fuzzy class membership values and zeros. Crude domain knowledge about the initial data is represented in the form of a decision table, which is divided into subtables corresponding to different classes. The data in each decision table is converted into granular form. The syntax of these decision tables automatically determines the appropriate number of hidden nodes, while the dependency factors from all the decision tables are used as initial weights. The dependency factor of each attribute and the average degree of the dependency factor of all the attributes with respect to decision classes are considered as initial connection weights between the nodes of the input layer and the hidden layer, and the hidden layer and the output layer, respectively. The effectiveness of the proposed FRGNN is demonstrated on several real-life data sets.     

A granular computing framework for self-organizing maps

When using granular computing for problem solving, one can focus on a specific level of understanding without looking at unwanted details of subsequent (more precise) levels. We present a granular computing framework for growing hierarchical self-organizing maps. This approach is ideal since the maps are arranged in a hierarchical manner and each is a complete abstraction of a pattern within data. The framework allows us to precisely define the connections between map levels. Formulating a neuron as a granule, the actions of granule construction and decomposition correspond to the growth and absorption of neurons in the previous model. In addition, we investigate the effects of updating granules with new information on both coarser and finer granules that have a derived relationship. Called bidirectional update propagation, the method ensures pattern consistency among data abstractions. An algorithm for the construction, decomposition, and updating of the granule-based self-organizing map is introduced. With examples, we demonstrate the effectiveness of this framework for abstracting patterns on many levels.     

A similarity measure for fuzzy rulebases based on linguistic gradients

Fuzzy rulebases are an approximate representation of some interesting system. As such, they could potentially be used for indexing and searching candidate solutions in case-based reasoning (CBR) systems in a variety of application areas. However, there is currently no method for directly and efficiently determining the similarity between two rulebases, which is a necessary element of their use in any CBR system. We propose a method for measuring similarity between two linguistic fuzzy rulebases, based on the granular computing technique of linguistic gradients. The proposed similarity measure is based on comparing the linguistic structure of two rulebases, using the linguistic gradient operator to reveal that structure. Our algorithm operates at the level of linguistic rulebases, rather than a defuzzified reasoning surface, and thus belongs to the Computing-with-Words paradigm. In a validation experiment, we compare our new method with the root-mean-square difference between reasoning surfaces for 603 pairs of fuzzy rulebases drawn from the literature. A Spearman correlation analysis shows that our new linguistic method is consistent with the numerical RMS results, while being theoretically and empirically faster than computing an accurate RMS difference.     

Virtual worlds — past, present, and future: New directions in social computing

Virtual worlds, where thousands of people can interact simultaneously within the same three-dimensional environment, represent a frontier in social computing with critical implications for business, education, social sciences, and our society at large. In this paper, we first trace the history of virtual worlds back to its antecedents in electronic gaming and on-line social networking. We then provide an overview of extant virtual worlds, including education-focused, theme-based, community-specific, children-focused, and self-determined worlds – and we analyze the relationship among these worlds according to an initial taxonomy for the area. Recognizing the apparent leadership of Second Life among today's self-determined virtual worlds, we present a detailed case study of this environment, including surveys of 138 residents regarding how they perceive and utilize the environment. Lastly, we provide a literature review of existing virtual world research, with a focus on business research, and a condensed summary of research issues in education, social sciences, and humanities.     

Perception granular computing in visual haze-free task

In the past decade, granular computing (GrC) has been an active topic of research in machine learning and computer vision. However, the granularity division is itself an open and complex problem. Deep learning, at the same time, has been proposed by Geoffrey Hinton, which simulates the hierarchical structure of human brain, processes data from lower level to higher level and gradually composes more and more semantic concepts. The information similarity, proximity and functionality constitute the key points in the original insight of granular computing proposed by Zadeh. Many GrC researches are based on the equivalence relation or the more general tolerance relation, either of which can be described by some distance functions. The information similarity and proximity depended on the samples distribution can be easily described by the fuzzy logic. From this point of view, GrC can be considered as a set of fuzzy logical formulas, which is geometrically defined as a layered framework in a multi-scale granular system. The necessity of such kind multi-scale layered granular system can be supported by the columnar organization of the neocortex. So the granular system proposed in this paper can be viewed as a new explanation of deep learning that simulates the hierarchical structure of human brain. In view of this, a novel learning approach, which combines fuzzy logical designing with machine learning, is proposed in this paper to construct a GrC system to explore a novel direction for deep learning. Unlike those previous works on the theoretical framework of GrC, our granular system is abstracted from brain science and information science, so it can be used to guide the research of image processing and pattern recognition. Finally, we take the task of haze-free as an example to demonstrate that our multi-scale GrC has high ability to increase the texture information entropy and improve the effect of haze-removing.     

User goals in social virtual worlds: A means-end chain approach

The purpose of this study is twofold: first, to investigate user goals in social virtual worlds; second, to introduce a methodological alternative (i.e., a means-end chain approach) for analyzing user goals in cyberspaces. The data were acquired from a web survey, and were analyzed by means-end chain analysis (MECA), which produces users’ goal structure in reference to a hierarchical system of interrelated goals (Olson & Reynolds, 1983). The results show that people come to social virtual worlds to satisfy their social and hedonic needs, and to escape from real world constraints, as do virtual community members and virtual gamers; they also pursue unique activities, such as creating virtual objects and selling them. On the other hand, by clarifying relations among users’ goals, MECA provides a richer explanation for user goals than prior research which only offers separate user goals for cyberspace users without explanation of relationship among goals.     

Creating ambient music spaces in real and virtual worlds

Sound and, specifically, music is a medium that is used for a wide range of purposes in different situations in very different ways. Ways for music selection and consumption range from completely passive, almost unnoticed perception of background sound environments to the very specific selection of a particular recording of a piece of music with a specific orchestra and conductor at a certain event. Different systems and interfaces exist for the broad range of needs in music consumption. Locating a particular recording is well supported by traditional search interfaces via metadata. Other interfaces support the automatic creation of playlists via artist or album selection, up to more artistic installations of sound environments that users can navigate through. In this paper we present a set of systems that support the creation of as well as the navigation in musical spaces, both in the real world as well as in virtual environments. We show common principles and point out further directions for a more direct coupling of the various spaces and interaction methods, creating ambient sound environments and providing organic interaction with music for different purposes.

A new fuzzy relational clustering algorithm based on the fuzzy C-means algorithm

In this paper, we show how one can take advantage of the stability and effectiveness of object data clustering algorithms when the data to be clustered are available in the form of mutual numerical relationships between pairs of objects. More precisely, we propose a new fuzzy relational algorithm, based on the popular fuzzy C-means (FCM) algorithm, which does not require any particular restriction on the relation matrix. We describe the application of the algorithm to four real and four synthetic data sets, and show that our algorithm performs better than well-known fuzzy relational clustering algorithms on all these sets.     

A Note on Z-numbers

Decisions are based on information. To be useful, information must be reliable. Basically, the concept of a Z-number relates to the issue of reliability of information. A Z-number, Z, has two components, Z = (A, B). The first component, A, is a restriction (constraint) on the values which a real-valued uncertain variable, X, is allowed to take. The second component, B, is a measure of reliability (certainty) of the first component. Typically, A and B are described in a natural language. Example: (about 45 min, very sure). An important issue relates to computation with Z-numbers. Examples: What is the sum of (about 45 min, very sure) and (about 30 min, sure)? What is the square root of (approximately 100, likely)? Computation with Z-numbers falls within the province of Computing with Words (CW or CWW). In this note, the concept of a Z-number is introduced and methods of computation with Z-numbers are outlined. The concept of a Z-number has a potential for many applications, especially in the realms of economics, decision analysis, risk assessment, prediction, anticipation and rule-based characterization of imprecise functions and relations.     

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required.     

A two-phase hybrid heuristic algorithm for the capacitated location-routing problem

In this paper, we propose a two-phase hybrid heuristic algorithm to solve the capacitated location-routing problem (CLRP). The CLRP combines depot location and routing decisions. We are given on input a set of identical vehicles (each having a capacity and a fixed cost), a set of depots with restricted capacities and opening costs, and a set of customers with deterministic demands. The problem consists of determining the depots to be opened, the customers and the vehicles to be assigned to each open depot, and the routes to be performed to fulfill the demand of the customers. The objective is to minimize the sum of the costs of the open depots, of the fixed cost associated with the used vehicles, and of the variable traveling costs related to the performed routes. In the proposed hybrid heuristic algorithm, after a Construction phase (first phase), a modified granular tabu search, with different diversification strategies, is applied during the Improvement phase (second phase). In addition, a random perturbation procedure is considered to avoid that the algorithm remains in a local optimum for a given number of iterations. Computational experiments on benchmark instances from the literature show that the proposed algorithm is able to produce, within short computing time, several solutions obtained by the previously published methods and new best known solutions.     

Understanding users’ motivations to engage in virtual worlds: A multipurpose model and empirical testing

Despite the growth and commercial potential of virtual worlds, relatively little is known about what drives users’ motivations to engage in virtual worlds. This paper proposes and empirically tests a conceptual model aimed at filling this research gap. Given the multipurpose nature of virtual words the model integrates extrinsic and intrinsic motivation as behavioral determinants. By making use of the literature on information system value and motivation theory four important system-specific virtual world characteristics (economic value, ease of use, escapism, visual attractiveness) are added as motivational drivers. Using structural equation modeling on a sample of 846 users of the virtual world Second Life the hypotheses were tested. The results support the model; they confirm the role of extrinsic and intrinsic motivation as behavioral determinants and show how and to what extent the four system-specific elements function as motivational basis. Implications for research and practice are discussed.     

商空间理论(粒度计算方法)实现高精度模糊控制

该文应用商空间(粒度计算)理论,给出了高精度模糊控制器的实现方法。通过系统控制粒度的不断改变,采用粗粒度粗调、细粒度细调的方法,系统可以兼顾理想的稳态和瞬态性能指标。实践证明以上观点正确。     

基于模糊邻近关系的聚类结构分析

提出了基于粒度空间的模糊邻近关系聚类结构分析研究,探讨了模糊邻近关系的聚类结构特性。首先,给出粒度空间(或聚类结构)的表示和生成算法,引入关键点序列概念和最小动态连通图诠释模糊邻近关系聚类结构的生成过程;其次,引入模糊邻近关系关于聚类结构的同构和ε-相似的概念,给出了两个模糊邻近关系同构或ε-相似的判定定理;最后,引入模糊邻近关系关于聚类结构的强ε-相似的概念,研究了两个模糊邻近关系同构与强ε-相似之间的关系。这些研究结论为一般的聚类结构分析提供了研究工具。     

hGA: Hybrid genetic algorithm in fuzzy rule-based classification systems for high-dimensional problems

The aim of this work is to propose a hybrid heuristic approach (called hGA) based on genetic algorithm (GA) and integer-programming formulation (IPF) to solve high dimensional classification problems in linguistic fuzzy rule-based classification systems. In this algorithm, each chromosome represents a rule for specified class, GA is used for producing several rules for each class, and finally IPF is used for selection of rules from a pool of rules, which are obtained by GA. The proposed algorithm is experimentally evaluated by the use of non-parametric statistical tests on seventeen classification benchmark data sets. Results of the comparative study show that hGA is able to discover accurate and concise classification rules.     

Computing most probable worlds of action probabilistic logic programs: scalable estimation for 1030,000 worlds

The semantics of probabilistic logic programs (PLPs) is usually given through a possible worlds semantics. We propose a variant of PLPs called action probabilistic logic programs or -programs that use a two-sorted alphabet to describe the conditions under which certain real-world entities take certain actions. In such applications, worlds correspond to sets of actions these entities might take. Thus, there is a need to find the most probable world (MPW) for -programs. In contrast, past work on PLPs has primarily focused on the problem of entailment. This paper quickly presents the syntax and semantics of -programs and then shows a naive algorithm to solve the MPW problem using the linear program formulation commonly used for PLPs. As such linear programs have an exponential number of variables, we present two important new algorithms, called and to solve the MPW problem exactly. Both these algorithms can significantly reduce the number of variables in the linear programs. Subsequently, we present a “binary” algorithm that applies a binary search style heuristic in conjunction with the Naive, and algorithms to quickly find worlds that may not be “most probable.” We experimentally evaluate these algorithms both for accuracy (how much worse is the solution found by these heuristics in comparison to the exact solution) and for scalability (how long does it take to compute). We show that the results of are very accurate and also very fast: more than 10^30,000 worlds can be handled in a few minutes. Subsequently, we develop parallel versions of these algorithms and show that they provide further speedups.      

Finite interval tracking algorithm for nonlinear multi-agent systems with communication delays

We propose an iterative learning control (ILC) tracking strategy to solve the tracking problem of multi-agent systems with nonlinear dynamics and time-varying communication delays. The distributed tracking strategy, in which each tracking agent only utilises its own and neighbours’ information, enables the tracking agents successfully track a maneuvering target in a finite time interval although with presence of time delays. Compared with the existing related work, the quantitative relationship between the boundary of tracking errors and the estimation of time delays is derived. Furthermore, in many practical control problems, identical initialisation condition may not be satisfied, which is called initial-shift problem. Hence, a forgetting factor is introduced to deal with that problem. It is proved that the presented results are effective via conducting numerical examples.