Chaitanya_Presentation

Download Report

Transcript Chaitanya_Presentation

Swarm Computing Applications
in Software Engineering
By
Chaitanya
Contents
Introduction
 Swarm Computing
 Ant colony optimization algorithms
 Applications in Software Engineering

2
Introduction
Software testing is an important and
valuable part of the software
development life cycle.
 Due to the time and cost constraints, it is
not possible to test the software manually
and fix the defects. Thus the use of test
automation plays a very important role in
the software testing process.

3
Swarm Computing
Swarm Computing/ Swarm Intelligence is
defined as the collective behavior of
decentralized, self-organized systems, natural or
artificial. The concept is employed in work on
artificial intelligence.
 The inspiration often comes from nature,
especially biological systems.

4
Swarm Computing
The agents follow very simple rules, and
although there is no centralized control
structure dictating how individual agents should
behave, local, and to a certain degree random,
interactions between such agents lead to the
emergence of "intelligent" global behavior.
 Natural examples of Swarm Intelligence include
ant colonies, bird flocking, animal herding,
bacterial growth, and fish schooling.

5
6
Features
Inherent parallelism
 Stochastic nature
 Adaptivity
 Use of positive feedback
 Autocatalytic in nature

7
Ant Colony Optimization (ACO)
Algorithms



ACOAs have been introduced as powerful tools to
solve order-based problems, such as the traveling
salesman problem (TSP) and the quadratic assignment
problems.
The main characteristics of ACSA are positive feedback,
distributed computation, and the use of a constructive
greedy heuristic.
ACOAs, to some extent, mimic the behavior of real
ants.
8
Natural Ants
Real ants are capable of finding the shortest
path from food sources to the nest without
using visual cues.
 They are also capable of adapting to changes in
the environment.

9
Food
10
11
12
Natural Ants
These capabilities ants have are essentially due
to what is called “pheromone trails” that ants
use to communicate information among
individuals regarding path and to decide where
to go.
 Ants deposit a certain amount of pheromone
while walking, and each ant probabilistically
prefers to follow a direction rich in pheromone
rather than a poorer one.

13
Agents in ACO
The ant colony optimization algorithm (ACO) is
a probabilistic technique for solving
computational problems which can be reduced
to finding good paths through graphs.
 The individual agents are rather simple.
However, when the entire colony foraging
towards the bait site complicated dynamics are
exhibited, achieving a super–nonlinear increase
in performance.

14
Applications of ACO
ACO algorithm techniques can be used in a
number of applications like controlling unmanned
vehicles, control nanobots within the body for the
purpose of killing cancer tumors. Swarm
intelligence has also been applied for data mining.
 Meta-Heuristic algorithms have been applied to
three areas of software engineering: test data
generation, module construction and cost/effort
prediction.
 But these algorithms can be applied to many
other operations in software engineering and
much research should be done in this field.

15
Application of ACO to software
testing
Three main activities normally associated with
software testing are:
 Test data generation,
 Test execution involving the use of test data and
the software under test and
 Evaluation of test results.
The process of test data generation involves
activities for producing a set of test data that
satisfied a chosen testing criterion.
16
Requirements for test case
generation
Transformation of the testing problem
into a graph.
 A heuristic measure for measuring the
“goodness” of paths through the graph.
 A mechanism for creating possible
solutions efficiently and a suitable
criterion to stop solution generation.
 A suitable method for updating the
pheromone.

17
The generated test suite has to satisfy
three criteria:
 All state coverage
 Feasibility
 Optimality
18
Coffee and Cocoa vending machine
example
19
Converted graph
20
Individual Agent properties
An ant k at a vertex of the graph is
associated with a four tuple:
 Vertex Track Set
 Target Set
 Connection Set
 Pheromone Trace Set
21
Algorithm for agent
Evaluation at vertex
-Update the track
-Evaluate connections
 Move to next vertex
-Select Destination
-Move
-Update Pheromone

22
Stopping criteria
All states have been visited at least once
 Search upper bound has been reached.

The final optimal solution can be obtained by examining all
of the solution candidates created by ant exploration.
23
24
Conclusions
Current research into the ASOA is still at a
nascent age.
 More potentially beneficial work remains to be
done, particularly in the areas of improvement
of its computation efficiency.

25
References
Automated Software Testing Using Meta-heuristic Technique
Based on An Ant Colony Optimization [Praveen Ranjan
Srivastava, Km Baby] 2010
 Reformulating Software Engineering as a search problem
[John Clarke, Bryan jones]
 An Ant Colony Optimization Approach to Test Sequence
Generation for State-Based Software Testing [Huaizhong
Li, Chiou Peng] 2005

26
THANK YOU
27