Searching Experience Sharing Based on Ant Colony Model

doi:10.4236/jsea.2012.59075

Paper Menu >>

Journal Menu >>

Journal of Software Engineering and Applications, 2012, 5, 645-652

http://dx.doi.org/10.4236/jsea.2012.59075 Published Online September 2012 (http://www.SciRP.org/journal/jsea) 645

Searching Experience Sharing Based on Ant Colony Model

Jung-Sing Jwo*, Chung-Ren Nian

Department of Computer Science, Tunghai University, Taichung, Chinese Taipei.

Email: *[email protected]

Received May 17th, 2012; revised June 20th, 2012; accepted July 2nd, 2012

ABSTRACT

Search engine is an important tool to all the Internet users. It helps users finding useful contents in the cyberspace.

However, searching experiences among different users are difficult to be shared and accumulated. In this paper, a con-

cept called search-trail is proposed. Based on ant colony model, search-trails are created from the searching steps to the

target contents. The search-trails built from various users are very similar to the trails generated in an ant colony. The

simulations of the proposed solution demonstrate that even in the case of few searching experienced users, the gener-

ated search-trails still possess 96.29% similarity to the expected ones in 60 days. It shows that the concept of

search-trails can really help users accumulating, sharing and reusing their search experiences.

Keywords: Ant Colony; Internet Search; Pheromone; Search Experience; Search-Trails

1. Introduction

Recently, using the contents and services published in the

web to help doing research work is indeed an efficient

and useful way. In fact, today’s Internet can be consid-

ered as the largest knowledge base that has ever existed.

In order to identify the required contents in this huge

knowledge base, utilizing search engines is the most

practical way [1-4].

The process of using a search engine is an interactive

process. Web users first submit their keywords and will

obtain a set of response URLs; by following these search

results users can retrieve the contents of these URLs.

This search steps are repeated until either the users are

satisfied by what have found or they become frustrated

and finally give up. For those people knowing what they

are searching, i.e., they know the exact keywords related

to the searching topics, current web search solutions are

good enough [5,6]. However if the research studies are

still in brainstorming stage, “what keywo rds are the right

ones” and “how to identify the next search from the cur-

rent search” sometimes are very difficult to be answered.

Especially, for the users without enough knowledge ab out

the research topic, search engines are still not helpful

enough.

From “human” point of view, one of the best ways to

tackle the above issues is to reuse someone’s experience.

Of course, this “someone” should be a knowledgeable

guy or a group of knowledgeable ones in the corre-

sponding field. Experience, in fact, is a kind of implicit

knowledge which is difficult to be expressed explicitly.

So, this raises a new issue: “Can we provide a mecha-

nism such that it can record those knowledgeable guys”

search experiences and let others share their experiences

later?”

Recording someone’s search steps is easy. The diffi-

cult part is how to keep “useful” search experiences in-

stead of all the search steps. In order to solve this issue,

by mimicking ants’ behavior, a new solution called

search-trail is proposed. Search-trail treats Internet world

as an ant colony [3,7] and each web user is treated as an

ant inside the ant co lony such that it is ab le to follow and

spread pheromones on the routes to the food sources. In

this case, these routes are the search steps approaching to

the target contents. As many ants searching the food

sources for a while, they can collaborate with each other

through pheromone spreading in the area. Some routes

will finally become useful search-trails leading to the

food sources while others may just disappear. The exist-

ing search-trails with strong pheromone can be treated as

an associated network of the related keywords and con-

tents. Search-trail map, a visualized interface, is pro-

posed to organize search-trails in a way such that they

can be easily reused and shared by either experienced or

inexperienced users. Un like traditional search technology,

Search-trail map tries to record how the users search

through the web.

In order to see how search-trail map influences the

search behaviors, a set of simulations is constructed. In

the simulation scenarios, the expected search-trails, i.e.

the right trails to the food sources, are assumed to be

*Corresponding a uthor.

Searching Experience Sharing Based on Ant Colony Model

646

known. The results of the simulations show that even in

the worst case, with 2% experienced, 8% standard, and

90% inexperienced users, the search-trails generated in

two months period are 96.29% similar to the expected

ones. For all other cases, the search-trails generated in

less than 30 days are 100% similar to the expected ones.

These simulations show that search-trail map can really

help users accumulating and sharing their search experi-

ences. Furthermore, these experiences can be polished

day after day just like what ants do in their colon y.

This paper is organized as follows. In Section 2, the

model of search-trail is introduced. The design of the

mechanism is given in Section 3. In order to show the

superiority of search-trail map, a set of simulations is

discussed in chapter 4. Section 5 is the conclusion re-

mark of this research.

2. Ant Colony Model for Search-Trail

In this section, ant colony model for search-trail is intro-

duced first. Ant colony model is originally inspired by

the ants’ foraging behavior. In the real world, ants com-

municate with each other by using an indirect communi-

cation called stigmergic [8]. In fact, two ants achieving

stigmergic communication is through releasing phero-

mone. Initially, ants wander randomly until some ants

find food. These ants release pheromone on the trails

back to their colony. The trails may be found by other

ants. Then, other ants may continue wandering randomly

or follow the trails they have found. In nature, phero-

mone evaporates over time. When the pheromone upon a

trail evaporates, its attrac tive strength is reduced. If an an t

follows a trail, it may release more pheromone to rein-

force the pheromone density. More ants travel through

the same trail, more pheromones are spread. Therefore,

important trails would remain with higher pheromone

density. On the other side, the pheromone evaporation

mechanism leads some trails to be discarded. Finally,

only good trails remain.

The idea of ant colony model has been applied to

many combinational optimization problems, such as

traveling salesman problem, assignments and scheduling

problems, or routing problems [9-12]. Algorithms based

on ant colony model treat ants as separate agents [13-15].

These ants walk around a graph representing the problem

to solve. The pheromones released on the edges influence

an ant to select its next step. For this kind of algorithms,

a mechanism acting as pheromone controller is required.

The pheromone controller reduces the density of phero-

mone level on edges to simulate the pheromone evapora-

tion process. By decreasing the pheromone density, the

influences from past experience are reduced and it en-

courages the exploration of new paths.

The idea of utilizing ant colony model for search-trails

is as follows. In a search-trail map, an Internet user is

treated as an ant. During its search process, keywords

and web pages being visited are recorded as the nodes of

a trail. For instance, at beginning a user chooses keyword

A to perform search and a set of URLs is returned by the

search engine. The user opens a page B from the returned

set and then follows a hyperlink available in B to another

page C. Then, this user might decide to reformulate the

search keyword as D and performs another search. A

page E from the new returned set is visited again. The

above search process can be modeled as a search-trail as

given in Figure 1(a). Note that keywords are in rectan-

gular shapes while pages are in oval shape s. Figure 1(b)

gives another example of search-trail.

When multiple searches performed, more than one

search-trail may appear and a map similar to the trails

inside an ant colony can be generated. A web user can

choose to follow any existing trail o r to create a new one

in the map. Pheromone is spread upon the edge of a

search-trail when a user is moving from one node to the

other thru the edge. If during a period of time an edge of

a search-trail has no any access, then a fix amount of

pheromone of the edge evaporates.

Based on the above model, u sers surely will create lots

of search-trails after a period of time. Of course, there

exist many target contents, i.e., similarly to the food

sources in the ant colony, such that no search-trails can

reach them. In the map, some search-trails attract more

users and become more concrete while others are dis-

carded finally. The detail mechanism for building search-

trail map is illustrated in the next section .

3. Search-Trail Map

To develop search-trail map based on ant colony model,

pheromone level control is the key issue. Instead of as-

signing a value to represent pheromone level at the very

beginning, the exact time that the pheromone will be

completely evaporated is used to represent the initial

pheromone level. When an ant travels thru an edge, the

(a)

(b)

Figure 1. Examples of search-trail model.

Searching Experience Sharing Based on Ant Colony Model

647

pheromone level of the edge is changed to the time by

adding a fixed time interval to its previous evaporated

time. Since pheromone is spread upon edges in a search-

trail map, maintaining each edge’s pheromone at its right

level is important. When the edges’ pheromone levels of

a node are all reduced to zero, the node will be removed

from the map.

To calculate the remaining pheromone level, it can just

subtract the current time from the completely evaporated

time. However, the evaporation rate of each edge is not a

constant value in a search-trail map. The reason why the

evaporation rates are different is that some unpopular but

important nodes could be removed from search-trail map

after a period of time. Popularity means lots of users are

interested in the topic. For exa mple, US President Obama

is the topic attracting many searches. Important but not

popular is the topic attracting few users. For example,

Kenya President Kibaki is important to some web users

but definitely is not as popular as President Obama. The

search-trails of the two presidents in the search-trail map

should maintain re adable as long as possible even though

the number of the search-trails of President Obama is

much larger than the number of President Kibaki. There-

fore, the evaporation rate in a search-trail map is adjusted

by the popularity. If a node has few out edges to the other

nodes, i.e., the degree of the node is small, we say the

node is an unpopular node and its out edges’ evaporation

rate is decreased. On the other hand, a popular node’s out

edges’ evaporation rate is increased. We may wonder

under this mechanism the popular nodes should be re-

moved quicker than unpopular nodes. The truth is a

popular node’s edge usually has more ants traveling thru

and therefore the pheromone released on the edge usually

is large. In fact, popular nodes are not easy to be re-

moved from a search-trail map.

It is obvious that the complexity of a search-trail map

is highly related to the number of the edges in the map.

In order to reduce the complexity, limiting a node’s de-

gree inside a preferred bound is reasonable since too

many edges are not helpful for searching.

Before introducing the solution in detail, we first

summarize all variables in Ta ble 1.

In order to guarantee a newly created edge can be no-

ticed by other users initially, the initial_pheromone_

value usually should be given a larger value. On the other

hand, for existing edges, if they can lead to some impor-

tant nodes, their pheromone values are accumulated by

passing-by users and therefore the pheromone_spread_

value is not necessary as big as the value of initial_

pheromone_value.

The data structures of Node, Edge, and Ant are given

in Figures 2-4 respectively.

Figure 5 is the major algorithm for search-trail solu-

tion. In this algorithm, when an ant moves from its cur-

rent node to another node named nextNode, the method

Ant_Movement (ant, nextNode) is invoked. The algorithm

starts by assigning the ant’s current location as firstNode,

then it checks whether edge e = (firstNode, nextNode)

has already existed in the search-trail map. If it does,

then the number of ants traveling thru e during the cur-

rent time interval is increased by one. If e is not existed

in the search-trail map, then e is created by executing the

Edge_Creation (firstNode, nextNode) method and e is

added into the search-trail map.

After a short period of time pheromone_update_time_

interval, a search-trail map needs to update the phero-

mone level of each edge. The algorithm is listed in Fig-

ure 6. In this algorithm, each edge’s evaporation_rate is

Table 1. Variable definitions.

Variables Description

evaporation_rate This variable is an edge variable. It indicates pheromone evaporation rate of a given edge.

edge_count This variable is a node variable. It indicates the current number of out edges of a given node.

preferred_edge_count This variable is a global variable. It indicates the maximum number of out edges of any node can exist in a

search-trail map.

pheromone_update_time_interval This variable is a global variable. It indicates the time interval to modify an edge’s pheromone in a search-trail

map.

completely_evaporated_time This variable is an edge variable. It indicates the time that an edge’s pheromone will be completely evaporated.

current_time This variable is a global variable. It indicates current time.

initial_pheromone_value This variable is a global variable. It indicates the initial pheromone value spread on a new created edge.

pheromone_spread_value This variable is a global variable. It indicates the amount of pheromone spread on an edge when a user travels

thru it.

number_of_ants This variable is an edge variable. It indicates the number of us ers that travelled through the edge during a

pheromone_update_time_interval.

Current This variable is an ant variable. It indicates the current position of the ant.

Searching Experience Sharing Based on Ant Colony Model

648

Node type

edge_count

Figure 2. Data structure for node.

Edge type

firstNode

nextNode

evaporation_rate

number_of_ants

completely_evaporated_time

Figure 3. Data structure for edge.

Ant type

Current

Figure 4. Data structure for ant.

Ant_Movement (Ant ant, Node nextNode){

define Node firstNode = Ant.current;

if (firstNode, nextNode) is an existing

edge in search-trail map {

let e = (firstNode, nextNode);

Ant_count (e);

} else {

e = Edge_Creation (firstNode,

nextNode);

add e to search-trail map;

}

ant.current nextNode;



}

Edge_Creation (Node firstNode, Node nextNode){

if nextNode doesn’t exist, create a new node

and assign the new node to nextNode;

define Edge e = (firstNode, nextNode);

e. completely_evaporated_time



current_time + initial_pheromone_value;

e.evaporation_rate 1;



return e;

}

Ant_Count (Edge e){

e. number_of_ants



e. number_of_ants + 1;

}

Figure 5. Ant movement algorithm.

updated according to its popularity. When evaporation_

rate is larger than one, it is said to be popular. Otherwise,

it is unpopular. The value of completely_evaporated_

time is updated according to the formula given in the

Figure 6. After updating completely_evaporated_time, it

verifies whether the edge is already evaporated by com-

paring it with current_time. If completely_evaporated_

ST-Map_Update (){

for each Edge e=(firstNode, nextNode) in ST-Map{

e.evaporation_rate



e.evaporation_rate 

countedgefirstNodee

countedgepreferred

_..

__ ;

e.completely_evaporated_time current_time + 

._ __

e completelyevaporatedtimecurrenttime

e evaporationrate

 +

antsofnumberetimespreadpheromone __.__ ;

If e.completely_evaporated_time < current_time {

remove e from ST-Map;

e.firstNode.edge_count =

e. firstNode.edge_count – 1;

}

If e.firstNode.edge_count <= 0{

remove e.firstNode from ST-Map;

}

Figure 6. Search-trail map pheromone update algorithm.

time is smaller than the current_time, which means the

edge is evaporated, the edge should be removed from the

search-trail map. If an edge is removed from the map, its

firstNode’s edge_count should also be reduced by one.

When a node’s edge_count becomes zero, it is removed

from the map.

4. Search-Trail Simulation

In order to see the impact on the web search when

adopting search-trail, an experiment is proposed. The

input to this experiment is as follows. There are 900

nodes and 3417 edges having been visited and gone thru

by many ants after a long enough period of time. Inside

this colony, there are totally 83 keywords and web con-

tents considered as “good” targets. Figure 7 is the visu-

alization map of the input. The trails with dark grey color

are the expected good search-trails to be generated after

simulation.

The simulation mechanism is given in Figure 8. It

starts by generating the above input map named “Refer-

ence Map”. Then, an Ant Dispatcher creates ants in every

dispatch_ant_time_interval time period. As many ants

join searching, some search-trails on the map become

strengthened. Meanwhile, according to the algorithm

stated in the previous section, the Pheromone Controller

is developed to control the pheromone level on the edges

of the simulated map. In the simulation, there are three

different categories of ants in the colony, namely, ex-

perienced users, standard users, and inexperienced users.

Each of these ants, its search experience is decided by

experience_level which indicates the probability of

choosing good nod es by its own. The av erage time for an

ant staying on a node is defined by sleep_time. The

probability of following existing search-trails is stored in

Searching Experience Sharing Based on Ant Colony Model 649

Figure 7. Scenario for the experiments.

Figure 8. Class diagram for simulation.

follow_trai l_percentage. The ant will finish its search

either the time it spends for search is more than search_

time or the good nodes it has found is more than satisfied_

node_number. Finally, the whole simulatio n is driven by

Time Controller. In the Time Controller, simulation_time

represents the duration of simulated days. Table 2 lists

all the key attributes of the classes.

Tables 3 and 4 contains the attribute values used in the

simulations done in this sectio n. In order to see how good

the search-trails generated by the ants after 30 days in

each simulation, a similarity formula to show the differ-

ence between the expected search-trails and the gener-

ated search-trails is given in the following:



Similarity

edgesin geneated search trailsexpected search trails







In the formula, the numerator represents the generated

search-trails that are expected and the denominator re-

presents the expected search-trails plus the wrong ones

generated by the ants. If all the search-trails generated by

the ants are expected, the value of the similarity will be

100%.

Based on the above introduction, four simulations are

performed. For Simulation 1, we assume 8% experienced,

32% standard, and 60% inexperienced users appearing in

the colony, respectively. For Simulation 2%, 6%, 24%,

and 70% of the three different category ants are assumed.

For Simulation 3, 4%, 16%, and 80% are assumed. For

Simulation 4, 2%, 8%, and 90% are assumed. Figures

9-12 are the results of the above four simulations respec-

tively.

In the above four simulations, each time we perform a

new simulation, the amount of inexperienced user is in-

creased while the amount of standard and experienced

user is decreased relatively. The search-trails generated

after day 1 are really random for all the four cases.

However, when more and more ants join into the search,

with the pheromone spread and evaporated, the search-

trails generated in the four cases are all gradually con-

verged to the expected search-trails. In fact, the first two

cases generate the exact expected search-trails in 30 days.

Table 2. Component attributes.

Component Parameter Description

Time Controller Simulation_time It indicates the period of simulated time.

Ant Dispatcher dispatch_ant_time_interval It indicates the frequency of an ant’s creation.

Experience_level It indicates the experience level of the ant.

sleep_time It indicates the time for the ant staying in a node.

satisfied_ node_value It indicates the number of the nodes the ant visited and then it will finish the search.

follow_trail_percentage It indicates the probability of the ant choosing existing search-trails.

Ant

search_time It indicates the time period the ant stay in searching. It is a random variable in nor mal distribution.

Searching Experience Sharing Based on Ant Colony Model

650

Table 3. Key component parameters.

Component Parameter Value

Time Controller simulation_time 30 days

initial_pheromone_value 3 days

pheromone_spread_value 1 hour

pheromone_update_time_interval 3 hours

Pheromone Controller

preferred_edge_count 3

Ant Dispatcher dispatch_ant_time_interval 3 min.

Simulation 1

Ant Type Experienced Users: 8% Standard User: 32% Inexperienced User: 60%

Search-trail

evolution

Day 1. 8.39%

Day 20. 92.59%

Day 10. 67.9%

Day 30. 100%

Day 1 Day 10 Day 20 Day 3 0

Similarity 8.39% 67.9% 92.59% 100%

Figure 9. Simulation 1.

Simulation 2

Ant Type Experienced Users: 6% Standard User: 24% Inexperienced User: 70%

Search-trail

evolution

Day 1. 7.89%

Day 20. 76.54%

Day 10. 41.97%

Day 30. 100%

Day 1 Day 10 Day 20 Day 30

Similarity 7.89% 41.97% 76.54% 100%

Figure 10. Simulation 2.

Searching Experience Sharing Based on Ant Colony Model 651

Table 4. Ants parameters.

Parameter Experienced Users Standard Users Inexperienced Users

experience_level 75% 50% 25%

sleep_time μ = 30 sec σ2 = 5 μ = 30 sec σ2 = 5 μ = 30 sec σ2 = 5

Satisified_node_value μ = 20 σ2 = 10 μ = 20 σ2 = 10 μ = 20 σ2 = 10

follow_trail_percentage 50% 50% 50%

search_time μ = 25 min σ2 = 5 μ = 25 min σ2 = 5 μ = 25 min σ2 = 5

Simulation 3

Ant Type Experienced Users: 4% Standard User: 16% Inexperienced User: 80%

search-trail

evolution

Day 1. 7.119%

Day 20. 66.66%

Day 10. 38.27%

Day 30. 91.35%

Day 1 Day 10 Day 20 Day 30

Similarity 7.11% 38.27% 66.66% 91.35%

Figure 11. Simulation 3.

Simulation 4

Ant Type Experienced Users: 2% Standard User: 8% Inexperienced User: 90%

search-trail

evolution

Day 1.9.63%

Day 20. 51.85%

Day 10. 29.62%

Day 30. 72.83%

Day 1 Day 10 Day 20 Day 30

Similarity 9.63% 29.62% 51.85% 72.83%

Figure 12. Simulation 4.

Searching Experience Sharing Based on Ant Colony Model

652

For the forth simulation, if the simulation period is ex-

tended to 60 days, the generated search-trail similarity

can reach 96.29%.

5. Conclusions

In this research a concept called search-trail is proposed.

Instead of the search targets, search-trail focuses more on

the search process. Based on ant colony model, search-

trails are created from the searching steps to the target

contents. The search-trails built from various users are

very similar to the trails generated in an ant colony. In

order to see the impact when adopting the proposed solu-

tion in a search community, four different simulations are

performed. The results show that search-trails really can

help users accumulating and sharing search experiences.

Even in the case of very few experienced users, the gen-

erated search-trails still possess 96.29% similarity to the

expected ones in 60 days.

The future work of this research is to integrate search-

trail into the curren t available search engines. In order to

achieve this goal, the complexity of the solution is re-

quired to be further polished.

REFERENCES

[1] P. Cimiano and S. Staab, “Learning by Googling,” SIG-

KDD Explorations, Vol. 6, No. 2, 2004, pp. 24-33.

doi:10.1145/1046456.1046460

[2] S. Lawrence and G. C. Lee, “Accessibility of Information

on the Web,” Nature, Vol. 400, 1999, pp. 107-109.

doi:10.1038/21987

[3] S. Lawrence and G. C. Lee, “Searching the Web: General

and Scientific Information Access,” IEEE Communica-

tions Magazine, Vol. 37, No. 1, 1999, pp. 116-122.

doi:10.1109/35.739314

[4] J. Pokorny, “Web Searching and Information Retrieval,”

Computing in Science & Engineering, Vol. 6, No. 4, 2004,

pp. 43-48. doi:10.1109/MCSE.2004.24

[5] A. Spink, R. Building, D. Wolfram and T. Saracevic,

“Searching the Web: The Public and Their Queries,”

Journal of the American Society for Information Science

and Technology, Vol. 52, 2001, pp. 226-234.

doi:10.1002/1097-4571(2000)9999:9999<::AID-ASI1591

>3.0.CO;2-R

[6] A. Spink, B. J. Jansen, C. Blakely and S. Koshman,

“Overlap among Major Web Search Engines,” 3rd Inter-

national Conference on Information Technology: New

Generation, Las Vegas, 10-12 April 2006, pp. 370-374.

[7] S. Goss, R. Beckers, J. L. Deneubourg, S. Aron and J. M.

Pasteels, “How Trail Laying and Trail Following Can

Solve Foraging Problems for Ant Colonies,” Behavioral

Mechanism of Food Selection, NATO ASI Series, Vol.

G20, 1990, pp. 661-678.

doi:10.1007/978-3-642-75118-9_32

[8] J.-L. Deneubourg, S. Aron, S. Goss and J.-M. Pasteels,

“The Self-Organizing Exploratory Pattern of the Argen-

tine Ant,” Journal of Insect Behavior, Vol. 3, No. 2, 1990,

pp. 159-168. doi:10.1007/BF01417909

[9] C. Blum and M. Sampels, “An Ant Colony Optimization

Slgorithm for Shop Scheduling Problems,” Journal of

Mathematical Modelling and Algorithms, Vol. 3, No. 2,

004, pp. 285-308.

[10] M. Dorigo and L. M. Gambardella, “Ant Colony System:

A Cooperative Learning Approach to the Traveling

Salesman Problem,” IEEE Transactions on Evolutionary

Computation, Vol. 1, No. 1, 1997, pp. 53-66.

doi:10.1109/4235.585892

[11] O. H. Hussein, T. N. Saadawi and M. J. Lee, “Probability

Routing Algorithm for Mobile Ad Hoc Networks Re-

sources Management,” IEEE Journal on Selected Areas

in Communications, Vol. 23, No. 12, 2005, pp. 2248-

2259. doi:10.1109/JSAC.2005.857205

[12] K. M. Sim and W. H. Sun, “Ant Colony Optimization for

Routing and Load-Balancing,” IEEE Transactions on

Systems, Man and Cybernetics, Vol. 33, No. 5, 2003, pp.

560-572. doi:10.1109/TSMCA.2003.817391

[13] M. Dorigo, G. D. Caro and L. M. Gambardella, “Ant

Algorithms for Discrete Optimization,” Artificial Life,

Vol. 5, No. 2, 1999, pp. 137-172.

doi:10.1162/106454699568728

[14] J. F. A. Traniello, “Colony Specificity in the Trail Phero-

mone of an Ant,” Naturwissenschaften, Vol. 67, No. 7,

1980, pp. 361-362. doi:10.1007/BF01106597

[15] S. Zheng, G. Zhang and Z. Zhou, “Ant Colony Optimiza-

tion Based on Pheromone Trail Centralization,” Proceed-

ings of the 6th World Congress on Intelligent Control and

Automation, Vol. 1, 2006, pp. 3349-3352.