IDR - IIT Kharagpur

Enhancing Solution Quality of Multiobjective Combinatorial Optimization with Hybridization of Evolutionary Algorithm...

Enhancing Solution Quality of Multiobjective Combinatorial Optimization with Hybridization of Evolutionary Algorithm...

 

Enhancing Solution Quality Of Multiobjective Combinatorial Optimization With Hybridization Of Evolutionary Algorithm : Most of the multiobjective combinatorial optimization (MOCO) problems are NP-hard and intractable, hence the metaheuristics are the applicable methods to obtain promising solutions. In the metaheuristics, the multiobjective evolutionary algorithms (MOEAs) are specifically suitable as they find the multiple solutions spread across the Pareto-front in a single run. Much work have been done on solving the MOCO problems using MOEAs yet not much care have been taken to assess quality of the obtained solutions. In this work, we consider biobjective versions of some important MOCO problems namely, traveling salesman problem (TSP), diameter-cost spanning tree (MOST) problem, multiple edge-costs minimum spanning tree (mc-MST) problem, 0-1 knapsack problem and intersecting spanning trees from multiple geometric graphs problem and obtain solutions using state-of-the-art and well-known MOEAs. We consider multiple MOEAs, in all the problems, to explore the search space vastly and obtain the best possible solutions. We assess the obtained MOEA solutions in comparison to the solutions obtained by wellknown deterministic/stochastic heuristics. We could find heuristics for the TSP and 0-1 knapsack problem in the literature which yielded solution-fronts in the biobjective setting. We adapted OTTC, IR and RGH to yield solution-fronts in the biobjective setting for the MOST problem. We devised our own heuristics for the mc-MST problem and intersecting spanning trees from multiple geometric graphs problem to obtain solution-fronts in the biobjective setting.

Recent Submissions