The relationship between emergence of the shortest path and information value using ant-like agents

Ant-like agents forage between two points. These agents' probabilistic movements are based on the use of two pheromones; one marking trails towards the goal and another marking trails back to the starting point. Path selection decisions are influenced by the relative levels of attractive and repulsive pheromone in each agent's local environment. Our work in [5] evaluates three pheromone perception strategies, investigating path formation speed, quality, directionality, robustness and adaptability under different parameter settings(degree of randomness, pheromone evaporation rate and pheromone diffusion rate). We re-evaluate two of these strategies in terms of the amount of information they provide using Shannon's formulation [3, 4, 8, 9, 12, 14, 15, 16, 17]. We determine information as the difference between uncertainty before and after path selection decisions. Our focus in this paper is on investigating relationships between the emergence of the shortest path and the amount of stigmergic information that exists in the form of pheromone. Agents are deployed centrally and emergence measures are determined using the worst, reference and best cases observed in [5]. Additionally, the amount of local and global information that is available to agents in each movement step is evaluated. Furthermore, Pearson's correlation coefficients between measures of emergence and the amount of information are calculated. The significance of these correlation coefficients is tested using a 2 tailed test at 1% level of significance. Consequently the relationship between the amount of information and emergent behaviour is established. Significant relationships between information and the emergence of the shortest path exist when strong emergent behaviour is present.

A probabilistic movement model for shortest path formation in virtual ant-like agents

We propose a probabilistic movement model for controlling ant-like agents foraging between two points. Such agents are all identical, simple, autonomous and can only communicate indirectly through the environment. These agents secrete two types of pheromone, one to mark trails towards the goal and another to mark trails back to the starting point. Three pheromone perception strategies are proposed (Strategy A, B and C). Agents that use strategy A perceive the desirability of a neighbouring location as the difference between levels of attractive and repulsive pheromone in that location. With strategy B, agents perceive the desirability of a location as the quotient of levels of attractive and repulsive pheromone. Agents using strategy C determine the product of the levels of attractive pheromone with the complement of levels of repulsive pheromone. We conduct experiments to confirm directionality as emergent property of trails formed by agents that use each strategy. In addition, we compare path formation speed and the quality of the formed path under changes in the environment. We also investigate each strategy's robustness in environments that contain obstacles. Finally, we investigate how adaptive each strategy is when obstacles are eventually removed from the scene and find that the best strategy of these three is strategy A. Such a strategy provides useful guidelines to researchers in further applications of swarm intelligence metaphors for complex problem solving.

Upgrading arc median shortest path problem for an urban transportation network

In this paper, we propose an algorithm for an upgrading arc median shortest path problem for a transportation network. The problem is to identify a set of nondominated paths that minimizes both upgrading cost and overall travel time of the entire network. These two objectives are realistic for transportation network problems, but of a conflicting and noncompensatory nature. In addition, unlike upgrading cost which is the sum of the arc costs on the path, overall travel time of the entire network cannot be expressed as a sum of arc travel times on the path. The proposed solution approach to the problem is based on heuristic labeling and exhaustive search techniques, in criteria space and solution space, respectively. The first approach labels each node in terms of upgrading cost, and deletes cyclic and infeasible paths in criteria space. The latter calculates the overall travel time of the entire network for each feasible path, deletes dominated paths on the basis of the objective vector and identifies a set of Pareto optimal paths in the solution space. The computational study, using two small-scale transportation networks, has demonstrated that the algorithm proposed herein is able to efficiently identify a set of nondominated median shortest paths, based on two conflicting and noncompensatory objectives.

Solving the median shortest path problem in the planning and design of urban transportation networks using a vector labeling algorithm

This paper proposes an alternative algorithm to solve the median shortest path problem (MSPP) in the planning and design of urban transportation networks. The proposed vector labeling algorithm is based on the labeling of each node in terms of a multiple and conflicting vector of objectives which deletes cyclic, infeasible and extreme-dominated paths in the criteria space imposing cyclic break (CB), path cost constraint (PCC) and access cost parameter (ACP) respectively. The output of the algorithm is a set of Pareto optimal paths (POP) with an objective vector from predetermined origin to destination nodes. Thus, this paper formulates an algorithm to identify a non-inferior solution set of POP based on a non-dominated set of objective vectors that leaves the ultimate decision to decision-makers. A numerical experiment is conducted using an artificial transportation network in order to validate and compare results. Sensitivity analysis has shown that the proposed algorithm is more efficient and advantageous over existing solutions in terms of computing execution time and memory space used.

An amoeboid algorithm for shortest path in fuzzy weighted networks

Taking the uncertainty existing in edge weights of networks into consideration, finding shortest path in such fuzzy weighted networks has been widely studied in various practical applications. In this paper, an amoeboid algorithm is proposed, combing fuzzy sets theory with a path finding model inspired by an amoeboid organism, Physarum polycephalum. With the help of fuzzy numbers, uncertainty is well represented and handled in our algorithm. What's more, biological intelligence of Physarum polycephalum has been incorporate into the algorithm. A numerical example on a transportation network is demonstrated to show the efficiency and flexibility of our proposed amoeboid algorithm.

An algorithm to median shortest path problem (MSPP) in the design of urban transportation networks

This paper proposes an efficient solution algorithm for realistic multi-objective median shortest path problems in the design of urban transportation networks. The proposed problem formulation and solution algorithm to median shortest path problem is based on three realistic objectives via route cost or investment cost, overall travel time of the entire network and total toll revenue. The proposed solution approach to the problem is based on the heuristic labeling and exhaustive search technique in criteria space and solution space of the algorithm respectively. The first labels each node in terms of route cost and deletes cyclic and infeasible paths in criteria space imposing cyclic break and route cost constraint respectively. The latter deletes dominated paths in terms of objectives vector in solution space in order to identify a set of Pareto optimal paths. The approach, thus, proposes a non-inferior solution set of Pareto optimal paths based on non-dominated objective vector and leaves the ultimate decision to decision-makers for purpose specific final decision during applications. A numerical experiment is conducted to test the proposed algorithm using artificial transportation network. Sensitivity analyses have shown that the proposed algorithm is advantageous and efficient over existing algorithms to find a set of Pareto optimal paths to median shortest paths problems.

Rapid Physarum Algorithm for shortest path problem

As shortest path (SP) problem has been one of the most fundamental network optimization problems for a long time, technologies for this problem are still being studied. In this paper, a new method by integrating a path finding mathematical model, inspired by Physarum polycephalum, with extracted one heuristic rule to solve SP problem has been proposed, which is called Rapid Physarum Algorithm (RPA). Simulation experiments have been carried out on three different network topologies with varying number of nodes. It is noted that the proposed RPA can find the optimal path as the path finding model does for most networks. What is more, experimental results show that the performance of RPA surpasses the path finding model on both iterations and solution time. © 2014 Elsevier B.V.

Utility-aware social network graph anonymization

As the need for social network data publishing continues to increase, how to preserve the privacy of the social network data before publishing is becoming an important and challenging issue. A common approach to address this issue is through anonymization of the social network structure. The problem with altering the structure of the links relationship in social network data is how to balance between the gain of privacy and the loss of information (data utility). In this paper, we address this problem. We propose a utility-aware social network graph anonymization. The approach is based on a new metric that calculates the utility impact of social network link modification. The metric utilizes the shortest path length and the neighborhood overlap as the utility value. The value is then used as a weight factor in preserving structural integrity in the social network graph anonymization. For any modification made to the social network links, the proposed approach guarantees that the distance between vertices in the modified social network stays as close as the original social network graph prior to the modification. Experimental evaluation shows that the proposed metric improves the utility preservation as compared to the number-of-change metric.

An extension of the flower pattern diagram for roll forming

The initial process design of a roll forming system is often based on the traditional ‘flower pattern diagram’. In this diagram, the cross sections of the strip at each roll stand are superimposed on a single plane; the diagram is a 2D representation of the 3D process. In the present work, the flower pattern is extended into three dimensions. To demonstrate the method, the forming path or trajectory of a point at the edge of the strip during forming a V-section is considered. The forming path is a surface curve that lies on a cylindrical surface having its axis along the machine axis. This surface is unwrapped to give its plane development and important features of the forming process can be determined and are readily interpreted from this plane curve. It is shown that at any stage in the process, the axial strain and the curvature of the sheet adjacent to the point are dependent on the slope of the trajectory in this plane projection. This new diagram, which apparently has not been used previously, provides a useful initial method of examining the roll forming process and optimising the flower pattern. The model is purely geometric, as is the original flower pattern approach, and does not include the effect of material behaviour. The concept is applied to several cases available in the literature. It shows that the lowest level of shape defect in the part is achieved when the trajectory of the strip edge follows the shortest line length between the start and finish of forming, leading to the least longitudinal strain introduced in the flange. This trend is in agreement with previous experimental observations, suggesting that the analytical model proposed may be applied for early process design and optimisation before time-consuming numerical analysis is performed.

Information retrieval in documents using semantic criteria

The central problem of automatic retrieval from unformatted text is that computational devices are not adequately trained to look for associated information. However for complete understanding and information retrieval, a complete artificial intelligence would have to be built. This paper describes a method for achieving significant information retrieval by using a semantic search engine. The underlying semantic information is stored in a network of clarified words, linked by logical connections. We employ simple scoring techniques on collections of paths in this network to establish a degree of relevance between a document and a clarified search criterion. This technique has been applied with success to test examples and can be easily scaled up to search large documents.

T-OSN : a trust evaluation model in online social networks

Now days, the online social networks (OSN) have gained considerable popularity. More and more people use OSN to share their interests and make friends, also the OSN helps users overcome the geographical barriers. With the development of OSN, there is an important problem users have to face that is trust evaluation. Before user makes friends with a stranger, the user need to consider the following issues: Can a stranger be trusted? How much the stranger can be trusted? How to measure the trust of a stranger? In this paper, we take two factors, Degree and Contact Interval into consideration, which produce a new trust evaluation model (T-OSN). T-OSN is aimed to solve how to evaluate the trust value of an OSN user, also which is more efficient, more reliable and easy to implement. Base on our research, this model can be used in wide range, such as online social network (OSN) trust evaluation, mobile network message forwarding, ad hoc wireless networking, routing message on Internet and peer-to-peer file sharing network. The T-OSN model has following obvious advantages compare to other trust evaluate methods. First of all, it is not base on features of traditional social network, such as, distance and shortest path. We choose the special features of OSN to build up the model, that is including numbers of friends(Degree) and contact frequency(Contact Interval). These species features makes our model more suitable to evaluate OSN users trust value. Second, the formulations of our model are quite simple but effective. That means, to calculate the result by using our formulations will not cost too much resources. Last but not least, our model is easy to implement for an OSN website, because of the features that we used in our model, such as numbers of friends and contact frequency are easy to obtain. To sum up, our model is using a few resources to obtain a valuable trust value that can help OSN users to solve an important security problem, we believe that will be big step - or development of OSN.

Certificateless ignatures: New schemes and security models

We present a study of security in certificateless signatures. We divide potential adversaries according to their attack power, and for the first time, three new kinds of adversaries are introduced into certificateless signatures. They are Normal Adversary, Strong Adversary and Super Adversary (ordered by their attack power). Combined with the known Type I Adversary and Type II Adversary in certificateless cryptography, we then define the security of certificateless signatures in different attack scenarios. Our new security models, together with others in the literature, provide a clear definition of the security in certificateless signatures. Two concrete schemes with different security levels are also proposed in this paper. The first scheme, which is proven secure (in the random oracle model) against Normal Type I and Super Type II adversaries, has the shortest signature length among all known certificateless signature schemes. The second scheme is secure (in the random oracle model) against Super Type I and Type II adversaries. Compared with another scheme that has a similar security level, our second scheme requires less operational cost but a little longer signature length. Two server-aided verification protocols are also proposed to reduce the verification cost on the verifier.

A Physarum-inspired multi-agent system to solve maze

Physarum Polycephalum is a primitive unicellular organism. Its foraging behavior demonstrates a unique feature to form a shortest path among food sources, which can be used to solve a maze. This paper proposes a Physarum-inspired multi-agent system to reveal the evolution of Physarum transportation networks. Two types of agents – one type for search and the other for convergence – are used in the proposed model, and three transition rules are identified to simulate the foraging behavior of Physarum. Based on the experiments conducted, the proposed multiagent system can solve the two possible routes of maze, and exhibits the reconfiguration ability when cutting down one route. This indicates that the proposed system is a new way to reveal the intelligence of Physarum during the evolution process of its transportation networks.