Accession Number:

ADA455521

Title:

Optimizing the Replication of Multi-Quality Web Applications Using ACO and WoLF

Descriptive Note:

Master's thesis

Corporate Author:

AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH DEPT OF GRADUATE COMPUTER SCIENCE

Personal Author(s):

• Dressler, Judson C.

Report Date:

2006-09-14

Pagination or Media Count:

77.0

Abstract:

This thesis presents the adaptation of Ant Colony Optimization to a new NP-hard problem involving the replication of multi-quality database-driven web applications DAs by a large application service provider ASP. The ASP must assign DA replicas to its network of heterogeneous servers so that user demand is satisfied and replica update loads are minimized. The algorithm proposed,AntDA, for solving this problem is novel in several respects ants traverse a bipartite graph in both directions as they construct solutions, pheromone is used for traversing from one side of the bipartite graph to the other and back again, heuristic edge values change as ants construct solutions, and ants may sometimes produce infeasible solutions. Experiments show that AntDA outperforms several other solution methods, but there was room for improvement in the convergence rates of the ants. Therefore, in an attempt to achieve the goals of faster convergence and better solution values for larger problems, AntDA was combined with the variable-step policy hill-climbing algorithm called Win or Learn Fast WoLF. In experimentation, the addition of this learning algorithm in AntDA provided for faster convergence while outperforming other solution methods.

Descriptors:

• *ALGORITHMS
• *OPTIMIZATION
• *HEURISTIC METHODS
• *LEARNING
• *REPLICAS
• DATA BASES
• NETWORKS
• CLIENT SERVER SYSTEMS
• INTERNET
• RATES
• THESES
• SOLUTIONS(GENERAL)
• CONVERGENCE
• USER NEEDS

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE