Please use this identifier to cite or link to this item: https://www.um.edu.mt/library/oar/handle/123456789/93786
Title: Ant colony algorithms with applications
Authors: Chricop, Jan (2002)
Keywords: Information technology
Data mining
Quality of service (Computer networks)
Issue Date: 2002
Citation: Chircop J. (2002). Ant colony algorithms with applications (Bachelor's dissertation).
Abstract: Ant Colony Optimisation (ACO) is a relatively new meta-heuristic developed in the early nineties by Dorigo et al. [1, 2, 16]. It is inspired from the foraging behaviour of real ants. The interactions of pheromone (scent) laying and pheromone location are the means which guide ants towards food sources. Which interactions also enable the ants to find the shortest distance between food sources and their nest. This idea has been applied by Dorigo et al. over the Travelling Salesman Problem. This laid the foundations for the Ant System algorithms, which optimised version is called ACO. These algorithms were later extended to a number of other NP-Hard combinatorial problems. Nowadays most common NP-Hard problems have been implemented using ant algorithms. The main aim of this project is an attempt to demonstrate that these algorithms can be further extended to game playing problems, which are PSPACE-Hard. Conceptually this project is divided into three main phases. The first phase introduces a research section over foraging strategies employed by real ants, based on the Linepithaema Humile ant. This phase includes an overview of existing ant foraging simulation applications. It is summed up by the development of a proper ant foraging simulation program. The second phase concentrates on a deep analysis of the work developed by Dorigo et al. in which three NP-Hard applications are considered. These are, the Travelling Salesman Problem (TSP), the Vehicle Routing Problem (VRP), and the Single Machine Total Weighted Tardiness Problem (SMTWTP). All of which are implemented as separate applications. The third phase concentrates on game playing. The game selected for this purpose is Checkers (or draughts). A detailed overview of current Checkers programs are considered. This includes a number of search algorithms and board evaluation procedures. In this phase two Checkers playing programs are developed. The first is a traditional alpha-beta based game, whilst the second game called Game ACO (GACO), is where the new ant inspired search is applied. Experimentation is used to show the validity of these concepts, and conclusions are given over the results attained. Possible ideas for future developments are also introduced. Keywords: Ants, Foraging, Pheromone, Ant Systems, ACO, NP-Hard, PSPACE-Hard, VRP, SMTWTP, Mini-Max Search, Alpha-beta Search, Game Playing, Checkers and GACO.
Description: B.Sc. IT (Hons)(Melit.)
URI: https://www.um.edu.mt/library/oar/handle/123456789/93786
Appears in Collections:Dissertations - FacICT - 1999-2009
Dissertations - FacICTCS - 1999-2007

Files in This Item:
File Description SizeFormat 
B.SC.(HONS)IT_Chircop_Jan_2002.pdf
  Restricted Access
25.63 MBAdobe PDFView/Open Request a copy


Items in OAR@UM are protected by copyright, with all rights reserved, unless otherwise indicated.