We
call ourselves Homo sapiens – man the
wise –because our mental capacities are so important to us. For thousands of
years, we have tried to understand how we
think; that is, how a mere handful of stuff can perceive, understand,
predict, and manipulate a world of far larger and more complicated than itself-
which the field of Artificial Intelligence. AI currently encompasses a huge
variety of subfields, ranging from general- purpose areas, such as learning and
perception to such specific tasks as playing chess, proving mathematical theorems,
and diagnosing diseases.
Much
of the earlier works in AI focused on formal tasks – game playing and theorem
proving. One of the classical AI optimization problem and constraint
satisfaction problem is Travelling Salesman Problem (TSP) defined in 1800s by
the Irish mathematician William Rowan Hamilton and the British mathematician
Thomas Kirkman, which falls under the family of NP-Complete problem. In this
problem, a salesman has a list of cities, each of which he must visit exactly
once. There are direct roads between each pair of cities on the list and the
goal is to find the route the salesman should follow for the shortest possible
round trip that both starts and finishes at any one of the cities.
Travelling salesman problem (TSP) is one of the
classical but the most fundamental constraint satisfaction and optimization problem
in computer science and engineering. The problem is NP-hard and so far no efficient
algorithm has been developed. The TSP has many applications in the industrial
world like transportation, factory set-ups, and industrial design etc.
In
this problem, a salesman has a list of cities, each of which he must visit
exactly once. There are direct roads between each pair of cities on the list
and the goal is to find the route the salesman should follow for the shortest
possible round trip that both starts and finishes at any one of the cities.
In
this project, I have used one of the popular algorithm in AI known as Genetic
Algorithm. This algorithm exploits the evolutionary process relating Charles
Darwin’s famous theory of ‘Survival of
the Fittest’ and the biological background of the reproduction (meiotic). This algorithm consists of three major
phases of reproduction- selection, cross-over (aka recombination) and mutation.
After several epochs, an optimum solution to the problem is obtained.
full report is available here for download
No comments:
Post a Comment