International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395 -0056
Volume: 04 Issue: 04 | Apr -2017
p-ISSN: 2395-0072
www.irjet.net
Optimal Solution for Santa Fe Trail Ant Problem using MOEA Framework Parneet Aulakh1, Sarvesh Chopra2 1Research
Scholar, CT institute of engineering management and technology, Jalandhar,Punjab,India
2 Assistant
Professor, CT institute of engineering management and technology, Jalandhar, India
Abstract : Multi-objective optimization is also a
most real problems. Pareto optimality considers solutions to be superior or inferior to another solution only when it is superior in all objectives or inferior in all objectives, respectively. The Santa Fe Ant Problem is a conventional ideal problem that has been studied over the past two decades and is still being rigorously researched. Santa Fe Trail is well-known of its reputation of being hard due to evolutionary computing methods not solving it at much higher effectiveness than random search. NSGA II is an evolutionary algorithm in which the main advantage is that it handles multiobjective solution given in sets of solutions, which provide computation of an approximation of the entire Pareto front. The main problem with this algorithm is slow execution and on the contrary there is no guarantee for the solution as well. In terms of meta-heuristics, recently, scatter search techniques are getting more attention, because of their capability to efficiently explore a broad range of complex optimization problems. Hybrid algorithm can make good use of the characteristics of various algorithms to attain complementary advantages to optimize the algorithm’s performance and efficiency. In this, Santa Fe Trail Ant problem is solved in its best optimization valued solution using various techniques includes mainly Non-dominated Sorting Genetic Algorithm (NSGA II), Simulated Annealing and Scatter Search techniques. In previous work, Genetic Algorithm techniques to solve such problems does not produce much better results and hard to solve as well. NSGA II algorithm has been implemented to optimize Santa Fe Trail Ant problem. Later we will enhance the algorithms using simulated annealing and scatter search techniques over the NSGA II algorithm to calculate new performance matrices and will be useful for comparative study as well.
significant topic for research from past few decades. This is because of the multi-objective nature of real world problems. Most of the real world problems are complex and versatile in nature, and quite often need more than one conflicting objective functions to be optimized simultaneously. Researchers have developed many multiobjective optimization procedures. Santa Fe Trail Ant Problem has been widely used to analyze experiment and examine various evolutionary computing methods and multi-objective optimization problems. In this, Santa Fe Trail Ant problem is solved in its best optimization valued solution using various techniques includes mainly Nondominated Sorting Genetic Algorithm (NSGA II), Simulated Annealing and Scatter Search techniques. In previous work, Genetic Algorithm approach to solve these type of problems produce not much better results and difficult to solve as well. NSGA II algorithm has been implemented to optimize Santa Fe Trail Ant problem. Later we will enhance the algorithms using simulated annealing and scatter search techniques over the NSGA II algorithm to calculate new performance matrices and will be useful for comparative study as well. Keywords:Multi-objective optimization; NSGA II; Santa Fe Trail Ant problem; Simulated Annealing; Scatter Search
1. INTRODUCTION Optimization is the process of identifying the best solution among a set of alternatives .Whereas single objective optimization employs a single criterion for identifying the best solution among a set of alternatives, multi-objective optimization employs two or more criteria. The criteria used to compare solutions are known as objectives. As multiple objectives can conflict with one another i.e., improving one objective leads to the deterioration of another there is, generally speaking, no single optimal solution to multi-objective problems. Researchers have developed many multi-objective optimization procedures. For multi-objective optimization problems, there is not a single optimum solution, but a set of non-dominated optimal solutions called the Pareto set of solutions. The challenge is in the case of conflicting objectives, which is usually the case in
© 2017, IRJET
|
Impact Factor value: 5.181
2. SANTA FE TRAIL ANT PROBLEM The Santa Fe Trail ant problem is a conventional ideal problem that has been studied over the past two decades and is still being rigorously researched. Santa Fe Trail is well-known of its reputation of being “hard” due to evolutionary computing methods not solving it at much higher effectiveness than random search. The hardness has been ascribed to a fitness landscape that is difficult
|
ISO 9001:2008 Certified Journal
|
Page 207